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²,n²}). 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