Dense Projection Tomography on the Triangular Tiling

• Autorzy: Nagy B. , Lukić T.

Identyfikatory

DOI

10.3233/FI-2016-1350

• Języki publikacji: EN

Abstrakty

EN

In this paper, we consider the binary tomography reconstruction problem. A new approach is proposed what exploits a possibility provided by the natural structure of the triangular grid, which is not available in the case of the classical square grid. In contrast to the square grid, in the case of the triangular grid information need for the reconstruction of the unknown image is increasing when not only one, but two projections are used by lanes. In this way, the number of Δ and ∇ shaped pixels per lane can be determined. We propose this type of projection approach and call it dense projections. The reconstruction is based on three projection directions by the lane directions of the grid (they are analogous to row and column directions on the square grid). Our algorithm is deterministic and uses energy minimization technique to find (near) optimal solution in a reasonable time. The experimental evaluation of the new method, using regular hexagon shaped test images, is given. Comparison with reconstructions based on the square grid is also considered.

Słowa kluczowe

EN

approximate solution; dense projection approach; energy minimization; tomography; triangular grids

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 2
• Strony: 125--141
• Opis fizyczny: Bibliogr. 44 poz., fot., rys., tab.

Twórcy

autor

Nagy B.

• Faculty of Arts and Sciences, Eastern Mediterranean University Famagusta, North Cyprus, Mersin-10, Turke
• Faculty of Informatics, University of Debrecen, Debrecen, Hungary

autor

Lukić T.

• Faculty of Technical Sciences, University of Novi Sad Novi Sad, Serbia

Bibliografia

• [1] Chang SK, Chow CK. The reconstruction of three-dimensional obejcts from two orthogonal projections and its application to cardiac cineangiography. IEEE Trans Comp. 1973;C-22:18–28.
• [2] Prause GPM, Onnasch DGW. Binary reconstruction of the heart chambers from biplane angiographic image sequences. IEEE Trans Med Imag. 1997;15:532–546. doi: 10.1109/42.511756.
• [3] Whale A, Wellnhofer E, Mugaragu I, Sauer HU, Oswald H, Fleck E. Assessment of diffuse coronary artery disease by quantitative analysis of coronary morpholgy based upon 3-D reconstruction from biplane angiograms. IEEE Trans Med Image. 1995;14:230–241. doi:10.1109/42.387704.
• [4] Wahle A, Lopez JJ, Olszewski ME, Vigmostad SC, Chandran KB, Rossen JD, et al. Plaque development, vessel curvature, and wall shear stress in coronary arteries assessed by X-ray angiography and intravascular ultrasound. Med Image Anal. 2006;10:611–631.
• [5] Krimmela S, Baumann J, Kiss Z, Kuba A, Nagy A, Stephan J. Discrete tomography for reconstruction from limited view angles in non-destructive testing. Electronic Notes in Discrete Mathematics. 2005;20:455474. doi:10.1016/j.endm.2005.05.078.
• [6] Herman GT, Kuba A. Advances in Discrete Tomography and Its Applications. Birkhäuser; 2007. ISBN: 9780817645434, 9780817636142. doi:10.1007/978-0-8176-4543-4.
• [7] Fortes W, Batenburg KJ. A Method for Feature Detection in Binary Tomography. In: Proceedings of Discrete Geometry for Computer Imagery, LNCS. vol. 7749. Sevilla, Spain; 2013. p. 372–382. doi:10.1007/978-3-642-37067-0 32.
• [8] Gara M, Tasi TS, Balazs P. Learning Connectedness and Convexity of Binary Images from Their Projections. Pure Mathematics and Applications. 2009;20:27–48.
• [9] Herman GT, Kuba A. Discrete Tomography: Foundations, Algorithms and Applications. Birkhäuser; 1999.
• [10] Herman GT. Fundamentals of computerized tomography: Image reconstruction from projection (2nd ed.). Springer-Verlag; 2009. ISBN: 978-1-85233-617-2, 978-1-84628-723-7.
• [11] Gardner RJ, Gritzmann P. Uniqueness and Complexity in Discrete Tomography. In: Discrete Tomography: Foundations, Algorithms and Applications. Birkhäuser; 1999.
• [12] Kong TY, Herman GT. Tomographic Equivalence and Switching Operations. In: Discrete Tomography: Foundations, Algorithms and Applications. Birkhäuser; 1999.
• [13] Klette R, Rosenfeld A. Digital geometry. Geometric methods for digital picture analysis. Morgan Kaufmann Publishers, San Francisco, CA, Elsevier Science B.V., Amsterdam; 2004.
• [14] Matej S, Vardi A, Herman GT, Vardi E. Binary Tomography Using Gibbs Priors. In: Discrete Tomography: Foundations, Algorithms and Applications. Birkhäuser; 1999.
• [15] Deutsch ES. Thinning algorithms on rectangular, hexagonal and triangular arrays. Comm of the ACM. 1972; 15:827–837. doi:10.1145/361573.361583.
• [16] Nagy B. Characterization of digital circles in triangular grid. Pattern Recognition Letters. 2004;25(11):1231–1242. Available from: http://dx.doi.org/10.1016/j.patrec.2004.04.001.
• [17] Kardos P, Palágyi K. On topology preservation for triangular thinning algorithms. In: Proceedings of the IWCIA. vol. 7655 of LNCS. Springer; 2012. p. 128–142. doi:10.1007/978-3-642-34732-0 10.
• [18] Nagy B. Cellular topology and topological coordinate systems on the hexagonal and on the triangular grids. Ann Math Artif Intell. 2015;75(1-2):117–134. doi:10.1007/s10472-014-9404-z.
• [19] Nagy B. Shortest path in triangular grids with neighbourhood sequences. Journal of Computing and Information Technology. 2003;11:111–122. doi:10.2498/cit.2003.02.04.
• [20] Nagy B. A symmetric coordinate frame for hexagonal networks. In: Proceedings of the IS-TCS’04 (ACM Conf. Theoretical Computer Science, Ljubljana, Slovenia); 2004. p. 193–196.
• [21] Nagy B. Isometric transformations of the dual of the hexagonal lattice. In: Proceedings of the ISPA’09, Salzburg, Austria; 2009. p. 432–437. doi:10.1109/ISPA.2009.5297709.
• [22] Nagy B, Barczi K. Isoperimetrically optimal Polygons in the Triangular Grid. In: Proceedings of the IWCIA’11, Madrid, Spain. vol. 6636 of LNCS. Springer; 2011. p. 194–207. doi:10.1007/978-3-642-21073-0 19.
• [23] Nagy B, Barczi K. Isoperimetrically Optimal Polygons in the Triangular Grid with Jordan-type Neighbourhood on the Boundary. International Journal of Computer Mathematics. 2013;90(8):1629–1652. doi:10.1080/00207160.2012.737914.
• [24] Batenburg KJ. A Network Flow Algorithm for Binary Image Reconstruction from Few Projections. In: Proceedings of 13th Proc. of 13th International Conference on Discrete Geometry for Computer Imagery (DGCI). vol. 4245 of LNCS. Springer-Verlag; 2006. p. 86–97. doi:10.1007/11907350 8.
• [25] Weber S, Nagy A, Schüle T, Schnörr C, Kuba A. A Benchmark Evaluation of Large-Scale Optimization Approaches to Binary Tomography. In: Proc. of 13th International Conference on Discrete Geometry for Computer Imagery (DGCI). vol. 4245 of LNCS. Szeged, Hungary: Springer-Verlag; 2006. p. 146–156. doi:10.1007/11907350 13
• [26] Varga L, Balázs P, Nagy A. Direction-dependency of binary tomographic reconstruction algorithms. Graphical Models. 2011;73:365–375. doi:10.1016/j.gmod.2011.06.006.
• [27] Moisi E, Nagy B. Discrete Tomography on the Triangular Grid: a Memetic Approach. In: Proc. of 7th International Symposium on Image and Signal Processing and Analysis (ISPA 2011). Dubrovnik, Croatia; 2011. p. 579–584.
• [28] Moisi E, Nagy B, Cretu V. Reconstruction of binary images represented on equilateral triangular grid using evolutionary algorithms. Soft Computing Applications. 2013;195:561–571. doi:10.1007/978-3-642-33941-7 49.
• [29] Lukić T, Nagy B. Energy-minimization based Discrete Tomography Reconstruction Method for Images on Triangular Grid. In: Proceedings of Combinatorial Image Analysis - 15th International Workshop (IWCIA). vol. 7655 of LNCS. Austin (TX), USA: Springer-Verlag; 2012. p. 274–284. doi:10.1007/978-3-642-34732-0 21, Available from: http://dx.doi.org/10.1007/978-3-642-34732-0_21.
• [30] Lukić T, Nagy B. Deterministic discrete tomography reconstruction by energy minimization method on the triangular grid. Pattern Recognition Letters. 2014;49:11–16. doi:10.1016/j.patrec.2014.05.014.
• [31] Ryser HJ. Combinatorial properties of matrices of zeros and ones. Can J Math. 1957;9:371–377.
• [32] Gale D. A theorem on flows in networks. Pacific J Math. 1957;7(2):1073–1082.
• [33] Tikhonov AN, Arsenin VY. Solutions of Ill-Posed Problems. Winston and Wiley; 1977.
• [34] Schüle T, Schnörr C, Weber S, Hornegger J. Discrete Tomography by Convex-concave Regularization and D.C. Programming. Discrete Appl Math. 2005;151:229–243. doi:10.1016/j.dam.2005.02.028.
• [35] Lukić T, Lindbald J, Sladoje N. Regularized Image Denoising Based on Spectral Gradient Optimization. Inverse Problems. 2011;27:17 pp. doi:10.1088/0266-5611/27/8/085010.
• [36] Birgin EG, Martínez JM, Raydan M. Algorithm 813: SPG - Software for convex-constrained optimization. ACM Transactions on Mathematical Software. 2001;27:340–349.
• [37] Lukić T, Lukity A. A Spectral Projected Gradient Optimization for Binary Tomography. In: Computational Intelligence in Engineering. vol. 313 of SCI. Springer-Verlag; 2010. p. 263–272. doi:10.1007/978-3-642-15220-7 21.
• [38] Grippo L, Lampariello F, Lucidi S. A Nonmonotone Line Search Technique for Newton’s Method. SIAM J Numer Anal. 1986;23:707–716.
• [39] Barzilai J, Borwein JM. Two point step size gradient methods. IMA Journal of Numerical Analysis. 1988;8: 141–148.
• [40] Raydan M. The Barzilai and Browein Gradient Method for the Large Scale Unconstrained Minimization Problem. SIAM J of Optimization. 1997;7:26–33.
• [41] Birgin EG, Martínez JM. Spectral Conjugate Gradient Method for Unconstrained Optimization. Appl Math Optimization. 2001;43:117–128. doi:10.1007/s00245-001-0003-0.
• [42] Birgin EG, Martínez JM, Raydan M. Nonmonotone Spectral Projected Gradient Methods on Convex Sets. SIAM J on Optimization. 2000;10(4):1196–1211. doi:10.1137/S1052623497330963.
• [43] Birgin EG, Martínez JM. A box-constrained optimization algorithm with negative curvature directions and spectral projected gradients. Computing. 2001;15:49–60. doi:10.1007/978-3-7091-6217-0 5.
• [44] Aerle WV, Batenburg KJ, Sijbers J. Automatic parameter estimation for the discrete algebraic reconstruction technique (DART). IEEE Transactions on Image Processing. 2012;21:4608–4621. doi:10.1109/TIP.2012.2206042.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.