Abstract
Tomography deals with the reconstruction of images from their projections. In this paper we focus on tomographic reconstruction of binary images (i.e., black-and-white) that do not have an intrinsic lattice structure from a small number of projections. We describe how the reconstruction problem from only two projections can be formulated as a network flow problem in a graph, which can be solved efficiently. When only two projections are used, the reconstruction problem is severely underdetermined and many solutions may exist. To find a reconstruction that resembles the original image, more projections must be used. We propose an iterative algorithm to solve the reconstruction problem from more than two projections. In every iteration a network flow problem is solved, corresponding to two of the available projections. Different pairs of projection angles are used for consecutive iterations. Our algorithm is capable of computing high quality reconstructions from very few projections. We evaluate its performance on simulated projection data and compare it to other reconstruction algorithms.
Chapter PDF
Similar content being viewed by others
References
Kak, A.C., Slaney, M.: Principles of Computerized Tomographic Imaging. SIAM, Philadelphia (2001)
Natterer, F.: The Mathematics of Computerized Tomography. SIAM, Philadelphia (2001)
Herman, G.T., Kuba, A. (eds.): Discrete Tomography: Foundations, Algorithms and Applications. Birkhäuser Boston (1999)
Batenburg, K.J.: Reconstructing Binary Images from Discrete X-Rays. CWI Report PNA-E0418 (submitted, 2004)
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)
Batenburg, K.J.: A Network Flow Algorithm for Binary Tomography Without an Intrinsic Lattice (preprint, 2006), www.math.leidenuniv.nl/~kbatenbu
Gale, D.: A Theorem on Flows in Networks. Pacific. J. Math. 7, 1073–1082 (1957)
Bertsekas, D.P., Tseng, P.: RELAX-IV: A Faster Version of the RELAX Code for Solving Minimum Cost Flow Problems. LIDS Technical Report LIDS-P-2276. MIT (1994)
Weber, S., Schnörr, C., Hornegger, J.: A Linear Programming Relaxation for Binary Tomography with Smoothness Priors. Electron. Notes Discrete Math. 12 (2003)
Weber, S., Schüle, T., Schnörr, C., Hornegger, J.: A Linear Programming Approach to Limited Angle 3D Reconstruction from DSA Projections. Special Issue of Methods of Information in Medicine 4, 320–326 (2004)
ILOG CPLEX, http://www.ilog.com/products/cplex/
Batenburg, K.J.: A New Algorithm for 3D Binary Tomography. Electron. Notes Discrete Math. 20, 247–261 (2005)
Weber, S., Schüle, T., Hornegger, J., Schnörr, C.: Binary Tomography by Iterating Linear Programs from Noisy Projections. In: Klette, R., Žunić, J. (eds.) IWCIA 2004. LNCS, vol. 3322, pp. 38–51. Springer, Heidelberg (2004)
Schüle, T., Schnörr, C., Weber, S., Hornegger, J.: Discrete Tomography by Convex-Concave Regularization and D.C. Programming. Discrete Appl. Math. 151, 229–243 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Batenburg, K.J. (2006). A Network Flow Algorithm for Binary Image Reconstruction from Few Projections. In: Kuba, A., Nyúl, L.G., Palágyi, K. (eds) Discrete Geometry for Computer Imagery. DGCI 2006. Lecture Notes in Computer Science, vol 4245. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11907350_8
Download citation
DOI: https://doi.org/10.1007/11907350_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-47651-1
Online ISBN: 978-3-540-47652-8
eBook Packages: Computer ScienceComputer Science (R0)