**Benchmark Collections for
the Reconstruction of hv-Convex Discrete Sets**

The goal of *Binary Tomography*
is to reconstruct discrete sets (finite subsets of the 2D integer lattice
defined up to translation) from the number of its elements lying on lattice lines
along several directions (called projections). A discrete set can also be
represeneted by a binary image formed from unitary cells or by binary matrices
as well. When only the horozontal and vertical projections are given then the
task of reconstruction can be regarded as finding a binary matrix with given
row and column sums. This task is often very underdetermined, that is there can
be several (possibly very different) solutions. In order to reduce this
ambiguity we usually suppose that the set to be reconstructed satisfies some
geometrical constrains. Informally, a discrete set is called hv-convex if its
rows and columns consist of consecutive black pixels. Due to the strong (and
sometimes surprising) theoretical results the class of hv-convex discrete sets
is frequently studied in discrete tomography. This class (and its subclasses)
allows comparisons of reconstruction methods from the viewpoint of speed,
accuracy, noise-sensitivity, etc. The key to obtain exact comparisons is to
develop unifrom random generators for those classes and - with the aid of them - to generate benchmark collections which then can be used in each test
scenario. To help the "Discrete Tomography community" we offer here several
uniformly generated benchmark collections free to download. Each collection
contains a README file which describes the structure of the files. If you have
any questions, suggestions, observations, or you need hv-convex discrete sets
of other structures feel free to contact me at [pbalazs at inf dot u-szeged dot
hu].

Péter Balázs, PhD

assistant professor

Department of Image Processing and
Computer Graphics

University of Szeged, HUNGARY

**hv-convex polyominoes **

In the class of hv-convex
4-connceted discrete sets (also called hv-convex polyominoes) several
polynomial-time reconstruction algorithms are known which use the horizontal
and vertical projections. The time-complexity of the fastest one is of O(mn∙min{m^{2},n^{2}}).
Our bechmark collections for this class are generated by an extension of the
method [1]. When using these collections, please refer to [A1] and [A2]

ˇ
Collection 1: 100-100 hv-convex polyominoes of size 10×10,
20×20, ..., 100×100 (download - 353 KB)

ˇ
Collection 2: 100-100 hv-convex polyominoes of size 150×150,
200×200, ..., 500×500 (download - 2.29 MB)

[A1] W. Hochstättler, M. Loebl, C. Moll, Generating
convex polyominoes at random, Discrete Math. 153 (1996) 165-176.

[A2] P. Balázs, A benchmark set for the
reconstruction of hv-convex discrete sets, Discrete Appl. Math. 157 (2009) 3447-3456.

**hv-convex 8-connected
but not 4-connected discrete sets **

Surprisingly, the reconstruction
from two projections in this class can be performed in O(mn∙min{m,n})
time. Sets of small sizes (Collection 3) are generated by the method of [B1].
Large sets according to their semiperimeters (Collection 4) are generated by
the method of [B2]. If you use Collection 3, please refer to [B1] and [B2],
when using Collection 4, please refer to [B2].

ˇ
Collection 3: 100-100 hv-convex 8- but not 4-connected
discrete sets of size 10×10, 20×20, ..., 100×100 (download - 291 KB)

ˇ
Collection 4: 100-100 hv-convex 8- but not 4-connected
discrete sets of semiperimeter 100, 200, ..., 1000 (download - 2.09 MB)

[B1] P. Balázs, A framework for generating some
discrete sets with disjoint components by using uniform distributions, Theoret.
Comput. Sci. 406 (2008) 15-23.

[B2] P. Balázs, A benchmark set for the
reconstruction of hv-convex discrete sets, Discrete Appl. Math. 157 (2009) 3447-3456.

**general hv-convex
discrete sets **

In this general class the reconstruction
from two projections is known to be NP-hard. When using Collection 5 of
discrete sets of smaller sizes, please refer to [C1] and [C2]. If you use
Collection 6 of sets of greater sizes, please refer to [C1].

ˇ
Collection 5: 100-100 general hv-convex discrete sets of
size 10×10, 20×20, ..., 100×100 (download - 335
KB)

ˇ
Collection 6: 100-100 general hv-convex discrete sets of
semiperimeter 100, 200, ..., 1000 (download - 2.22
MB)

[C1] P. Balázs, A benchmark set for the
reconstruction of hv-convex discrete sets, Discrete Appl. Math. 157 (2009)
3447-3456

[C2] P. Balázs, A framework for generating some
discrete sets with disjoint components by using uniform distributions, Theoret.
Comput. Sci. 406 (2008) 15-23.

History:

09.11.2009 References [A2], [B2], and [C1] were updated

21.04.2009 Webpage launched