Probabilistic Reconstruction of hv-convex Polyominoes from Noisy Projection Data

• Autorzy: Goupy A. , Pagani S. M. C.

Identyfikatory

DOI

10.3233/FI-2014-1115

• Języki publikacji: EN

Abstrakty

EN

In this paper the well-known problem of reconstructing hv-convex polyominoes is considered from a set of noisy data. Differently from the usual approach of Binary Tomography, this leads to a probabilistic evaluation in the reconstruction algorithm, where different pixels assume different probabilities to be part of the reconstructed image. An iterative algorithm is then applied, which, starting from a random choice, leads to an explicit reconstruction matching the noisy data.

Słowa kluczowe

EN

hv-convex polyomino; noisy data; polyomino; reconstruction algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 1/2
• Strony: 117--134
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Goupy A.

• ENSTA ParisTech 828, Bd des Maréchaux, 91762 Palaiseau, France

autor

Pagani S. M. C.

• Dipartimento di Matematica “F. Brioschi”, Politecnico di Milano, Piazza Leonardo da Vinci, 32, I-20133 Milano, Italy

Bibliografia

• [1] Alpers, A., Brunetti, S.: Stability results for the reconstruction of binary pictures from two projections, Image and Vision Computing, 25(10), 2007, 1599 – 1608, ISSN 0262-8856, Discrete Geometry for Computer Imagery 2005.
• [2] Alpers, A., Gritzmann, P., Thorens, L.: Stability and instability in discrete tomography, in: Digital and image geometry, vol. 2243 of Lecture Notes in Comput. Sci., Springer, Berlin, 2001, 175–186.
• [3] Balazs, P.: Reconstruction of canonical hv-convex discrete sets from horizontal and vertical projections, Proceedings of IWCIA ’09, Lecture Notes in Comput. Sci., 5852, Springer-Verlag, Berlin, Heidelberg, 2009, ISBN 978-3-642-10208-0.
• [4] Balazs, P., Balogh, E., Kuba, A.: Reconstruction of 8-connected but not 4-connected hv-convex discrete sets, Discrete Appl. Math., 147, 2005, 149–168.
• [5] Balogh, E., Kuba, A., Dévényi, C., Del Lungo, A.: Comparison of algorithms for reconstructing hv-convex discrete sets, Linear Algebra Appl., 339, 2001, 23–35.
• [6] Barcucci, E., Brocchi, S.: Solving multicolor discrete tomography problems by using prior knowledge, Fund. Inform., 125(3-4), 2013, 313–328, ISSN 0169-2968.
• [7] Barcucci, E., Del Lungo, A., Nivat, M., Pinzani, R.: Reconstructing convex polyominoes from horizontal and vertical projections, Theoretical Computer Science, 155, 1996, 321–347.
• [8] Batenburg, K. J., Fortes, W., Hajdu, L., Tijdeman, R.: Bounds on the quality of reconstructed images in binary tomography, Discrete Appl. Math., 161(15), 2013, 2236–2251.
• [9] Batenburg, K. J., Sijbers, J.: DART: a Practical Reconstruction Algorithm for Discrete Tomography, IEEE Trans. Image Processing, 20(9), 2011, 2542–2553.
• [10] Blondin Massé, A., Brlek, S., Frosini, A., Labbé, S., Rinaldi, S.: Reconstructing words from a fixed palindromic length sequence, in: Fifth IFIP International Conference on Theoretical Computer Science—TCS 2008, vol. 273 of IFIP Int. Fed. Inf. Process., Springer, New York, 2008, 101–114.
• [11] Brunetti, S., Dulio, P., Peri, C.: Discrete Tomography determination of bounded lattice sets from four X-rays, Discrete Applied Mathematics, 161 (15), 2013, 2281–2292.
• [12] Brunetti, S., Dulio, P., Peri, C.: On the Non-Additive Sets of Uniqueness in a Finite Grid, Proceedings of DGCI, 2013, Lecture Notes in Comput. Sci., 7749, Springer-Verlag, Berlin, Heidelberg, 2013, ISBN 978-3-642-37066-3.
• [13] Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.: A tomographical characterization of L-convex polyominoes, in: Discrete geometry for computer imagery, vol. 3429 of Lecture Notes in Comput. Sci., Springer, Berlin, 2005, 115–125.
• [14] Chrobak, M., Durr, C.: Reconstructing hv-Convex Polyominoes from Orthogonal Projections, Information Processing Letters, 69, 1999, 283–289.
• [15] Dahl, G., Flatberg, T.: Optimization and reconstruction of hv-convex (0, 1)-matrices, Discrete Appl. Math., 151, 2005, 93–105.
• [16] van Dalen, B.: Stability results for uniquely determined sets from two directions in discrete tomography, Discrete Math., 309(12), 2009, 3905–3916, ISSN 0012-365X.
• [17] Del Lungo, A., Nivat, M., Pinzani, R.: The number of convex polyominoes reconstructible from their orthogonal projections, Discrete Math., 157, 1996, 65–78.
• [18] Gardner, R. J., Gritzmann, P.: Discrete tomography: determination of finite sets by X-rays, Trans. Am. Math. Soc., 349(6), 1997, 2271–2295.
• [19] Picouleau, C.: Reconstruction of convex polyominoes from orthogonal projections of their contours, Theoret. Comput. Sci., 346, 2005, 439–454.
• [20] Varga, L., Nyúl, L. G., Nagy, A., Balázs, P.: Local Uncertainty in Binary Tomographic Reconstruction, Proceedings of the IASTED International Conference on Signal Processing, Pattern Recognition and Applications, IASTED, ACTA Press, Calgary, AB Canada, 2013, ISBN 978-0-88986-954-7.