Algorithm for Reconstructing 3D-Binary Matrix with Periodicity Constraints from Two Projections

Authors: V. Masilamani, Kamala Krithivasan

Abstract:

We study the problem of reconstructing a three dimensional binary matrices whose interiors are only accessible through few projections. Such question is prominently motivated by the demand in material science for developing tool for reconstruction of crystalline structures from their images obtained by high-resolution transmission electron microscopy. Various approaches have been suggested to reconstruct 3D-object (crystalline structure) by reconstructing slice of the 3D-object. To handle the ill-posedness of the problem, a priori information such as convexity, connectivity and periodicity are used to limit the number of possible solutions. Formally, 3Dobject (crystalline structure) having a priory information is modeled by a class of 3D-binary matrices satisfying a priori information. We consider 3D-binary matrices with periodicity constraints, and we propose a polynomial time algorithm to reconstruct 3D-binary matrices with periodicity constraints from two orthogonal projections.

Keywords: 3D-Binary Matrix Reconstruction, Computed Tomography, Discrete Tomography, Integral Max Flow Problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072495

References:

[1] F. Andrea. Complexity Results and Reconstruction Algorithms for Discrete Tomography. PhD thesis, University of Siena, Siena, Italy, 2003.
[2] T. H. Cormen, C. E. Leiserson and R. L.Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, USA, 1990.
[3] D. Gale. A theorem on flows in networks. Pacific. J. Math., 7:1073- 1082, 1957.
[4] R. J. Gardner and P. Gritzmann. Discrete tomography: determination of finite sets by X-rays. Trans. Amer. Math. Soc., 349:2271-2295, 1997.
[5] G. T. Herman and A. Kuba, editors. DISCRETE TOMOGRAPHY Foundations, Algorithms, and Applications. Birkhauser, 1999.
[6] G. T. Herman and A. Kuba, editors. DISCRETE TOMOGRAPHY Foundations, Algorithms, and Applications, chapter Binary tomography using Gibbs priors. Birkhauser, 1999.
[7] G. T. Hermann and A. kuba. Discrete tomography in medical imaging. Proceedings of the IEEE, 91(10):1612-1626, 2003.
[8] H.J.Ryser. Combinotorial properties of matrices of zeroes and ones. Canad. J. Math., 9:371-377, 1957.
[9] R. W. Irving and M. R. Jerrum. Three-dimensional statistical data security problems. SIAM Journal of computing, 23(1):170-184, 1994.
[10] C. Kiesielolowski, P. Schwander, F. H. Baumann, M. Seibt, Y. Kim and A. Ourmazd. An approach to quantitative hight-resolution transmission electron microscopy of crystalline materials. Ultramicroscopy, 58:131- 155, 1995.
[11] G. P. M. Prause and D. G. W. Onnasch. Binary reconstruction of the heart chambers from biplane angiographic image sequence. IEEE Transactions Medical Imaging, 15:532-559, 1996.
[12] A. R. Shliferstien and Y. T. Chien. Switching components and the ambiguity problem in the reconstruction of pictures from their projections. Pattern Recognition, 10(5):327-340, 1978.