Solving Multicolor Discrete Tomography Problems by Using Prior Knowledge

• Autorzy: Barcucci E. , Brocchi S.
• Języki publikacji: EN

Abstrakty

EN

Discrete tomography deals with the reconstruction of discrete sets with given projections relative to a limited number of directions, modeling the situation where a material is studied through x-rays and we desire to reconstruct an image representing the scanned object. In many cases it would be interesting to consider the projections to be related to more than one distinguishable type of cell, called atoms or colors, as in the case of a scan involving materials of different densities, as a bone and a muscle. Unfortunately the general n-color problem with n > 1 is NP-complete, but in this paper we show how several polynomial reconstruction algorithms can be defined by assuming some prior knowledge on the set to be rebuilt. In detail, we study the cases where the union of the colors form a set without switches, a convex polyomino or a convex 8-connected set. We describe some efficient reconstruction algorithms and in a case we give a sufficient condition for uniqueness.

Słowa kluczowe

EN

discrete tomography; problem solving; prior learning; image reconstruction

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 125, nr 3/4
• Strony: 313--328
• Opis fizyczny: Bibliogr. 19 poz., wykr.

Twórcy

autor

Barcucci E.

• Dipartimento di Sistemi e Informatica, Università di Firenze, Viale Morgagni, 65 - 50134 Firenze, Italy

autor

Brocchi S.

• Dipartimento di Sistemi e Informatica, Università di Firenze, Viale Morgagni, 65 - 50134 Firenze, Italy

Bibliografia

• [1] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993
• [2] B. Aspvall, M.F. Plass, R.E. Tarjan, A linear-time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters 8, pp. 121-123, 1979
• [3] P. Balazs, Reconstruction of canonical hv-convex discrete sets from horizontal and vertical projections, Proceedings of 13th International Workshop on Combinatorial Image Analysis, Lecture Notes in Computer Science 5852, pp. 280-288, 2009
• [4] P. Balazs, E. Balogh, A. Kuba, Reconstruction of 8-connected but not 4-connected hv-convex discrete sets, Discrete Applied Mathematics, Vol. 147, pp. 149-168, 2005
• [5] E. Barcucci, S. Brocchi, A. Frosini, Solving the two color problem - An heuristic algorithm, Proceedings of the 14th International Workshop on Combinatorial Image Analysis, Lecture Notes in Computer Science, Vol. 6636, 2011
• [6] E. Barcucci, A. Del Lungo, M. Nivat, R. Pinzani, Reconstructing convex polyominoes from horizontal and vertical projections, Theoretical Computer Science, Volume 155, Issue 2, pp 321-347, March 1996
• [7] E. Barcucci, A. Del Lungo, M. Nivat, R. Pinzani, Reconstructing convex polyominoes from horizontal and vertical projections II, Lecture Notes in Computer Science, pp 295-306, volume 1176, 1996
• [8] S. Brocchi, A. Frosini, C. Picouleau, Reconstruction of binary matrices under fixed size neighborhood constraints, Theoretical Computer Science, Vol. 406, pp. 43-54, 2008
• [9] S. Brocchi, A. Frosini, S. Rinaldi, Solving some instances of the 2-color problem, Discrete Geometry for Computer Imagery, 15th IAPR International Conference, Proceedings, Lecture Notes in Computer Science, Vol. 5810, pp. 505-516,2009
• [10] S. Brocchi, A. Frosini, S. Rinaldi, A reconstruction algorithm for a subclass of instances of the 2-color problem, Theoretical Computer Science, Volume 412, Advances in Discrete Geometry for Computer Imagery, Issue 36 pp. 4795-4804, August 2011
• [11] S. Brunetti, A. Del Lungo, F. Del Ristoro, M. Nivat, A. Kuba, Reconstruction of 8- and 4-connected convex discrete sets from row and column projections, Linear Algebra and its Applications 339, pp 37-57, 2001
• [12] G. Castiglione, A. Frosini, A. Restivo, S. Rinaldi, A tomographical characterization of L-convex polyomi- noes, Proceedings of Discrete Geometry for Computer Imagery 12th International Conference (DGCI2005), Lecture Notes in Computer Science, pp. 115-125, 2006
• [13] M. Chrobak, C. Durr, Reconstructing hv-Convex Polyominoes from Orthogonal Projections, Inf. Process. Lett. 69 (6), pp. 283-289, 1999
• [14] M-C. Costa, D. de Werra, C. Picouleau, D. Schindl, A solvable case of image reconstruction in discrete tomography, Discrete Applied Mathematics, Volume 148(3), pp 240-245, 2005
• [15] A. Del Lungo, M. Nivat, R. Pinzani, The number of convex polyominoes reconstructible from their orthogonal projections, Discrete Mathematics, Volume 157, Number 1, pp. 65-78(14), 1 October 1996
• [16] C. Diirr, F. Guinez, M. Matamala, Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard, A Solution to the 2-Atom Problem in Discrete Tomography, SIAM J. Discrete Math. 26(1), pp. 330-352, 2012
• [17] S. W. Golomb, Polyominoes: puzzles, patterns, problems and packing, Princeton Academic Press, 1996
• [18] H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canadian Journal of Mathematics, Vol. 9, pp. 371-377, 1957
• [19] G. J. Woeginger, The reconstruction of polyominoes from their orthogonal projections, Information Processing Letters, Vol. 77, pp. 225-229, 2001