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

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.

• V. Masilamani
• Kamala Krithivasan

• 3D-Binary Matrix Reconstruction
• Computed Tomography
• Discrete Tomography
• Integral Max Flow Problem.

[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.