An Algorithm for the Reconstruction of hv-convex Planar Bodies by Finitely Many and Noisy Measurements of their Coordinate X-rays

• Autorzy: Vincze C. , Nagy A.

Identyfikatory

DOI

10.3233/FI-2015-1270

• Języki publikacji: EN

Abstrakty

EN

Parallel X-rays are functions that measure the intersection of a given set with lines parallel to a fixed direction in R2. The reconstruction problem concerning parallel X-rays is to reconstruct the set if the parallel X-rays into some directions are given. There are several algorithms to give an approximate solution of this problem. In general we need some additional knowledge on the object to obtain a unique solution. By assuming convexity a suitable finite number of directions is enough for all convex planar bodies to be uniquely determined by their X-rays in these directions [13]. Gardner and Kiderlen [12] presented an algorithm for reconstructing convex planar bodies from noisy X-ray measurements belonging to four directions. For a reconstruction algorithm assuming convexity we can also refer to [17]. An algorithm for the reconstruction of hv-convex planar sets by their coordinate X-rays (two directions) can be found in [18]: given the coordinate X-rays of a compact connected hv-convex planar set K the algorithm gives a sequence of polyominoes Ln all of whose accumulation points (with respect to the Hausdorff metric) have the given coordinate X-rays almost everywhere. If the set is uniquely determined by the coordinate X-rays then Ln tends to the solution of the problem. This algorithm is based on generalized conic functions measuring the average taxicab distance by integration [21]. Now we would like to give an extension of this algorithm that works in the case when only some measurements of the coordinate X-rays are given. Following the idea in [12] we extend the algorithm for noisy X-ray measurements too.

Słowa kluczowe

EN

convex romains; coordinate axes; finite fields; image reconstruction algorithm; generalization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 141, nr 2/3
• Strony: 169--189
• Opis fizyczny: Bibliogr. 21 poz., tab.

Twórcy

autor

Vincze C.

• Institute of Mathematics, University of Debrecen P. O. Box 12, 4010 Debrecen, Hungary

autor

Nagy A.

• Institute of Mathematics, MTA-DE Research Group ”Equations Functions and Curves” Hungarian Academy of Sciences and University of Debrecen P. O. Box 12, 4010 Debrecen, Hungary

Bibliografia

• [1] P Balázs, A benchmark set for the reconstruction of hv-convex discrete sets, Discrete Applied Mathematics, 157 (2009) 3447–3456.
• [2] E. Balogh, A. Kuba, C. Dévényi A. Del Lungo and R. Pinzani, Comparison of algorithms for reconstructing hv-convex discrete sets, Linear Algebra and its Applications, 339 (2001) 23–35.
• [3] E. Barcucci, A. Del Lungo, M. Nivat and R. Pinzani, Reconstructing convex polyominoes from horizontal and vertical projections, Theoretical Computer Science, 155 (1996) 321–347.
• [4] M. Barczy, Cs. Noszály, Á . Nagy and Cs. Vincze, A Robbins-Monro-type algorithm for computing global minimizer of generalized conic functions, Optimization, published online 19 May 2014, Arxiv:1301.6112.
• [5] G. Bianchi, A. Burchard, P. Gronchi and A. Volcic, Convergence in Shape of Steiner Symmetrization, Indiana University Math. Journal, Vol. 61, No. 4. (2012), 1695-1709.
• [6] S. Brunetti and A. Daurat, An algorithm reconstructing lattice convex sets. Theoretical Computer Science, 304 (2003) 35–57.
• [7] S. Brunetti, P. Dulio and C. Peri, Discrete tomography determination of bounded lattice sets from four X-rays. Discrete Applied Mathematics, 161 (15) (2013) 2281–2292.
• [8] A. Daurat. Determination of Q-convex sets by X-rays, Theoretical Computer Science, 332 (1-3) (2005) 19–45.
• [9] R. J. Gardner. Geometric Tomography, Cambridge University Press, New-York, 1995, second ed., 2006.
• [10] R. J. Gardner and P. Gritzmann, Discrete tomography: Determination of finite sets by X-rays. Transactions of the American Mathematical Society, 349 (1997) 2271–2295.
• [11] R. J. Gardner and P. Gritzmann, Uniqueness and complexity in discrete tomography. in Discrete Tomography: Foundations, Algorithms and Applications, ed. by G. T. Herman and A. Kuba, Birkhäuser, Boston, (1999) 85–113.
• [12] R. J. Gardner and M. Kiderlen, A solution to Hammer’s X-ray reconstruction problem, Advances in Mathematics, 214 (2007) 323–343.
• [13] R. J. Gardner and P. McMullen, On Hammer’s X-ray problem, Journal of the London Mathematical Society, (2) 21 (1980) 171–175.
• [14] P. Gritzmann, B. Langfeld and M. Wiegelmann, Uniqueness in discrete tomography: three remarks and a corollary. SIAM Journal of Discrete Mathematics, 25 (2011) 1589–1599.
• [15] L. Hajdu and R. Tijdeman, Algebraic aspects of discrete tomography. J. Reine Angew. Math., 534 (2001), 119–128.
• [16] L. Hajdu, Unique reconstruction of bounded sets in discrete tomography. Electronic Notes in Discrete Mathematics, 20 (2005) 15–25.
• [17] D. Kölzow, A. Kuba and A. Volˇciˇc, An algorithm for reconstructing convex bodies from their projections. Discrete and Computational Geometry, 4 (1989) 205–237.
• [18] Á . Nagy and Cs. Vincze, Reconstruction of hv-convex sets by their coordinate X-ray functions, Journal of Mathematical Imaging and Vision, Vol. 49/3 (2014), 569-582.
• [19] Á . Nagy and Cs. Vincze, Generalized conic functions of hv-convex planar sets: continuity properties and relations to X-rays, accepted for publication in Aequationes Mathematicae, published online 17. Dec. 2014, Arxiv:1303.4412.
• [20] Cs. Vincze and Á Nagy, An introduction to the theory of generalized conics and their applications, Journal of Geometry and Physics, Vol. 61/4 (2011) 815–828.
• [21] Cs. Vincze and Á . Nagy, On the theory of generalized conics with applications in geometric tomography, Journal of Approximation Theory, 164 (2012) 371–390.