Error Correction for Discrete Tomography

• Autorzy: Ceko Matthew , Hajdu Lajos , Tijdeman Rob

Identyfikatory

DOI

10.3233/FI-222154

• Języki publikacji: EN

Abstrakty

EN

Discrete tomography focuses on the reconstruction of functions from their line sums in a finite number d of directions. In this paper we consider functions f : A → R where A is a finite subset of ℤ2 and R an integral domain. Several reconstruction methods have been introduced in the literature. Recently Ceko, Pagani and Tijdeman developed a fast method to reconstruct a function with the same line sums as f. Up to here we assumed that the line sums are exact. Some authors have developed methods to recover the function f under suitable conditions by using the redundancy of data. In this paper we investigate the case where a small number of line sums are incorrect as may happen when discrete tomography is applied for data storage or transmission. We show how less than d/2 errors can be corrected and that this bound is the best possible. Moreover, we prove that if it is known that the line sums in k given directions are correct, then the line sums in every other direction can be corrected provided that the number of wrong line sums in that direction is less than k/2. [

Słowa kluczowe

EN

discrete tomography; error correction; line sums; polynomial-time algorithm; Vandermonde determinant

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 189, nr 2
• Strony: 91--112
• Opis fizyczny: Bibliogr. 42 poz.

Twórcy

autor

Ceko Matthew

• School of Physics and Astronomy Monash University, Melbourne, Australia

autor

Hajdu Lajos

• Institute of Mathematics, University of Debrecen, Debrecen, Hungary

autor

Tijdeman Rob

• Mathematical Institute, Leiden University, Leiden, The Netherlands

Bibliografia

• [1] Alpers A, Gritzmann P. On the reconstruction of static and dynamic discrete structures. In: The Radon Transform. De Gruyter; 2019. p. 297-342.
• [2] Batenburg KJ, Sijbers J. DART: a practical reconstruction algorithm for discrete tomography. IEEE Transactions on Image Processing. 2011;20(9):2542-53. doi:10.1109/TIP.2011.2131661.
• [3] Ceko M, Petersen T, Svalbe I, Tijdeman R. Boundary ghosts for discrete tomography. Journal of Mathematical Imaging and Vision. 2021;63(3):428-40. doi:10.1007/s10851-020-01010-2.
• [4] Dulio P, Frosini A, Pagani SM. Geometrical characterization of the uniqueness regions under special sets of three directions in discrete tomography. In: Discrete Geometry for Computer Imagery. vol. 9647. Springer; 2016. p. 105-16. doi:10.1007/978-3-319-32360-2 8.
• [5] Gardner R, Gritzmann P. Discrete tomography: determination of finite sets by X-rays. Transactions of the American Mathematical Society. 1997;349(6):2271-95.
• [6] Guédon J, Normand N. The Mojette transform: the first ten years. In: Discrete Geometry for Computer Imagery. Springer; 2005. p. 79-91. doi:10.1007/978-3-540-31965-8 8.
• [7] Hajdu L, Tijdeman R. Algebraic aspects of discrete tomography. J reine angew Math. 2001;534:119-28. doi:10.1515/crll.2001.037.
• [8] Herman GT. Fundamentals of computerized tomography: Image reconstruction from projections. Springer Science & Business Media; 2009. doi:10.1007/978-1-84628-723-7.
• [9] Herman GT, Kuba A. Advances in discrete tomography and its applications. Springer Science & Business Media; 2008. doi:10.1007/978-0-8176-4543-4.
• [10] Stolk A, Batenburg KJ. An algebraic framework for discrete tomography: Revealing the structure of dependencies. SIAM Journal on Discrete Mathematics. 2010;24(3):1056-79.
• [11] Fishburn PC, Lagarias JC, Reeds JA, Shepp LA. Sets uniquely determined by projections on axes II Discrete case. Discrete Mathematics. 1991;91(2):149-59. doi:10.1016/0012-365X(91)90106-C.
• [12] Salzberg PM, Figueroa R. Tomography on the 3D-torus and crystals. In: Discrete tomography: Foundations, algorithms, and applications. Springer Science & Business Media; 2012. p. 417-34. doi:10.1007/978-1-4612-1568-4 19.
• [13] Blawat M, Gaedke K, Huetter I, Chen XM, Turczyk B, Inverso S, et al. Forward error correction for DNA data storage. Procedia Computer Science. 2016;80:1011-22. doi:10.1016/j.procs.2016.05.398.
• [14] Parrein B, Normand N, Guédon JP. Multimedia forward error correcting codes for wireless LAN. Annals of Telecommunications-annales des télécommunications. 2003;58(3-4):448-63. doi:10.1007/BF03001024.
• [15] Autrusseau F, Le Callet P. A robust image watermarking technique based on quantization noise visibility thresholds. Signal Processing. 2007;87(6):1363-83. doi:10.1016/j.sigpro.2006.11.009.
• [16] Urvoy M, Goudia D, Autrusseau F. Perceptual DFT watermarking with improved detection and robustness to geometrical distortions. IEEE Transactions on Information Forensics and Security. 2014;9(7):1108-19.doi:10.1109/TIFS.2014.2322497.
• [17] Kingston A, Autrusseau F. Lossless image compression via predictive coding of discrete Radon projections. Signal Processing: Image Communication. 2008;23(4):313-24. doi:10.1016/j.image.2008.03.001
• [18] Chandra SS, Svalbe ID, Guédon J, Kingston AM, Normand N. Recovering missing slices of the discrete Fourier transform using ghosts. IEEE Transactions on Image Processing. 2012;21(10):4431-41. doi:10.1109/TIP.2012.2206033.
• [19] Normand N, Svalbe I, Parrein B, Kingston A. Erasure coding with the finite Radon transform. In: 2010 IEEE Wireless Communication and Networking Conference. IEEE; 2010. p. 1-6. doi:10.1109/WCNC.2010.5506385.
• [20] Pertin D, d’Ippolito G, Normand N, Parrein B. Spatial implementation for erasure coding by Finite Radon Transform. In: International Symposium on signal, Image, Video and Communication 2012; 2012. p. 1-4.
• [21] Katz MB. Questions of uniqueness and resolution in reconstruction from projections. vol. 26. Springer Science & Business Media; 2013. doi:10.1007/978-3-642-45507-0.
• [22] Wiegelmann M. Gr¨obner bases and primal algorithms in discrete tomography. TU München; 1999.
• [23] Gardner RJ, Gritzmann P, Prangenberg D. On the computational complexity of reconstructing lattice sets from their X-rays. Discrete Mathematics. 1999;202(1-3):45-71. doi:10.1016/S0012-365X(98)00347-1.
• [24] Gardner RJ, Gritzmann P, Prangenberg D. On the computational complexity of determining polyatomic structures by X-rays. Theoretical computer science. 2000;233(1-2):91-106. doi:10.1016/S0304-3975(97)00298-3.
• [25] Dulio P, Pagani SM. A rounding theorem for unique binary tomographic reconstruction. Discrete Applied Mathematics. 2019;268:54-69. doi:10.1016/j.dam.2019.05.005.
• [26] Dulio P, Frosini A, Pagani SM. Uniqueness regions under sets of generic projections in discrete tomography. In: Discrete Geometry for Computer Imagery. Springer; 2014. p. 285-96. doi:10.1007/978-3-319-09955-2 24.
• [27] Dulio P, Frosini A, Pagani SM. A geometrical characterization of regions of uniqueness and applications to discrete tomography. Inverse problems. 2015;31(125011):285-96. doi:10.1088/0266-5611/31/12/125011.
• [28] Dulio P, Pagani S, Frosini A. Regions of uniqueness quickly reconstructed by three directions in discrete tomography. Fundamenta Informaticae. 2017;155(4):407-23. doi:10.3233/FI-2017-1592.
• [29] Pagani SM, Tijdeman R. Algorithms for linear time reconstruction by discrete tomography. Discrete Applied Mathematics. 2019;271:152-70. doi:10.1016/j.dam.2019.07.012.
• [30] Ceko M, Pagani SM, Tijdeman R. Algorithms for linear time reconstruction by discrete tomography II. Discrete Applied Mathematics. 2021;298:7-20. doi:10.1016/j.dam.2021.03.008.
• [31] Herman GT, Kuba A. Discrete tomography: Foundations, algorithms, and applications. Springer Science & Business Media; 2012. doi:10.1007/978-1-4612-1568-4.
• [32] Golub GH, Van Loan CF. Matrix computations. JHU press; 2013. ISBN-10:1421407949, 13:978-1421407944.
• [33] Hajdu L, Tijdeman R. Bounds for approximate discrete tomography solutions. SIAM Journal on Discrete Mathematics. 2013;27(2):1055-66. doi:10.1137/120883268.
• [34] Alpers A, Gritzmann P. On stability, error correction, and noise compensation in discrete tomography. SIAM Journal on Discrete Mathematics. 2006;20(1):227-39. doi:10.1137/040617443.
• [35] Donoho DL. For most large underdetermined systems of linear equations the minimal `1-norm solutionis also the sparsest solution. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences. 2006;59(6):797-829. doi:10.1002/cpa.20132.
• 36] Wright J, Ma Y. Dense Error Correction Via `1-Minimization. IEEE Transactions on Information Theory. 2010;56(7):3540-60. doi:10.1109/TIT.2010.2048473.
• [37] Candés EJ, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory. 2006;52(2):489-509. doi:10.1109/TIT.2005.862083.
• [38] Hajdu L, Tijdeman R. Consistency conditions for discrete tomography. Fundamenta Informaticae.
• 2017;155(4):425-47. doi10.3233/FI-2017-1593.
• [39] van Dalen B. Dependencies between line sums. Leiden University; 2007.
• [40] Floyd R, Rivest R. The algorithm SELECT–for finding the i-th smallest of n elements (Algorithm 489). Communications of the ACM, L. 1975;18:173.
• [41] Cohen H. A course in computational algebraic number theory. vol. 138. Springer Science & Business Media; 2013.
• [42] Ceko M, Pagani SM, Tijdeman R. Algorithms for linear time reconstruction by discrete tomography in three dimensions. arXiv preprint arXiv:201005868. 2020.