Skip to main content
SpringerLink
Log in

A Network Flow Algorithm for Reconstructing Binary Images from Discrete X-rays

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

We present a new algorithm for reconstructing binary images from their projections along a small number of directions. Our algorithm performs a sequence of related reconstructions, each using only two projections. The algorithm makes extensive use of network flow algorithms for solving the two-projection subproblems.

Our experimental results demonstrate that the algorithm can compute highly accurate reconstructions from a small number of projections, even in the presence of noise. Although the effectiveness of the algorithm is based on certain smoothness assumptions about the image, even tiny, non-smooth details are reconstructed exactly. The class of images for which the algorithm is most effective includes images of convex objects, but images of objects that contain holes or consist of multiple components can also be reconstructed very well.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.

  2. R.P. Anstee, “The network flows approach for matrices with given row and column sums”, Discrete Math., Vol. 44, pp. 125–138, 1983.

    Article  MATH  MathSciNet  Google Scholar 

  3. E. Barcucci, A. Del Lungo, M. Nivat, and R. Pinzani, “Reconstructing convex polyominoes from horizontal and vertical projections”, Theoret. Comput. Sci., Vol. 155, pp. 321–347, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  4. K.J. Batenburg, “A new algorithm for 3D binary tomography”,in Proceedings of the Workshop on Discrete Tomography and its Applications, New York, Electron. Notes Discrete Math., Vol. 20, 2005, pp. 247–261.

    Article  Google Scholar 

  5. S. Brunetti, A. Del Lungo, F. Del Ristoro, A. Kuba, and M. Nivat, “Reconstruction of 4- and 8-connected convex discrete sets from row and column projections”, Linear Algebra Appl., Vol. 339, pp. 37–57, 2001.

    Article  MATH  MathSciNet  Google Scholar 

  6. S. Brunetti and A. Daurat, “An algorithm for reconstructing lattice convex sets”, Theoret. Comput. Sci., Vol. 304, pp. 35–57, 2003.

    Article  MATH  MathSciNet  Google Scholar 

  7. P. Fishburn, P. Schwander, L. Shepp, and R. Vanderbei, “The discrete Radon transform and its approximate inversion via linear programming”, Discrete Appl. Math., Vol. 75, pp. 39–61, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  8. H.N. Gabow and R.E. Tarjan, “Faster scaling algorithms for network problems”, SIAM J. Comput., Vol. 18, pp. 1013–1036, 1989.

    Article  MATH  MathSciNet  Google Scholar 

  9. D. Gale, “A theorem on flows in networks”, Pacific J. Math., Vol. 7, pp. 1073–1082, 1957.

    MATH  MathSciNet  Google Scholar 

  10. R.J. Gardner, Geometric Tomography, Cambridge University Press, New York, 1995.

    MATH  Google Scholar 

  11. R.J. Gardner and P. Gritzmann, “Discrete tomography: determination of finite sets by X-rays”, Trans. Amer. Math. Soc., Vol. 349, pp. 2271–95, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  12. R.J. Gardner, P. Gritzmann, and D. Prangenberg, “On the computational complexity of reconstructing lattice sets from their X-rays”, Discrete Math., Vol. 202, pp. 45–71, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  13. A.V. Goldberg, “An efficient implementation of a scaling minimum-cost flow algorithm”, J. Algorithms, Vol. 22, pp. 1–29, 1997.

    Article  MathSciNet  Google Scholar 

  14. P. Gritzmann, S. de Vries, and M. Wiegelmann, “Approximating binary images from discrete X-rays”, SIAM J. Optim., Vol. 11, pp. 522–546, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  15. P. Gritzmann, D. Prangenberg, S. de Vries, and M. Wiegelmann, “Success and failure of certain reconstruction and uniqueness algorithms in discrete tomography”, Int. J. Imag. Syst. Tech., Vol. 9, pp. 101–109, 1998.

    Article  Google Scholar 

  16. L. Hajdu and R. Tijdeman, “Algebraic aspects of discrete tomography”, J. Reine Angew. Math., Vol. 534, pp. 119–128, 2001.

    MATH  MathSciNet  Google Scholar 

  17. L. Hajdu and R. Tijdeman, “An algorithm for discrete tomography”, Linear Algebra Appl., Vol. 339, pp. 147–169, 2001.

    Article  MATH  MathSciNet  Google Scholar 

  18. G.T. Herman and A. Kuba, (Eds.), Discrete Tomography: Foundations, Algorithms and Applications, Birkhäuser, Boston, 1999.

    MATH  Google Scholar 

  19. J.R. Jinschek, K.J. Batenburg, H. Calderon, D. Van Dyck, F.-R. Chen, and C. Kisielowski, “Prospects for bright field and dark field electron tomography on a discrete grid”, Microsc. Microanal., Vol. 10 Suppl. 3, Cambridge Journals Online, 2004.

  20. J.R. Jinschek, H.A. Calderon, K.J. Batenburg, V. Radmilovic and C. Kisielowski, “Discrete Tomography of Ga and InGa Particles from HREM Image Simulation and Exit Wave Reconstruction”, MRS Proc., Vol. 839, pp. 4.5.1–4.5.6, 2004.

    Google Scholar 

  21. C. Kisielowski, P. Schwander, F. Baumann, M. Seibt, Y. Kim, and A. Ourmazd, “An approach to quantitative high-resolution transmission electron microscopy of crystalline materials”, Ultramicroscopy, Vol. 58, pp. 131–155, 1995.

    Article  Google Scholar 

  22. H.J. Ryser, “Combinatorial properties of matrices of zeros and ones”, Canad. J. Math., Vol. 9, pp. 371–377, 1957.

    MATH  MathSciNet  Google Scholar 

  23. A. Schrijver, Combinatorial Optimization. Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003.

    MATH  Google Scholar 

  24. P. Schwander, C. Kisielowski, F. Baumann, Y. Kim, and A. Ourmazd, “Mapping projected potential, interfacial roughness, and composition in general crystalline solids by quantitative transmission electron microscopy”, Phys. Rev. Lett., Vol. 71, pp. 4150–4153, 1993.

    Article  Google Scholar 

  25. C.H. Slump and J.J. Gerbrands, “A network flow approach to reconstruction of the left ventricle from two projections”, Comput. Gr. Im. Proc., Vol. 18, pp. 18–36, 1982.

    Article  Google Scholar 

  26. K. Tanabe, “Projection method for solving a singular system”, Numer. Math., Vol. 17, pp. 203–214, 1971.

    Article  MATH  MathSciNet  Google Scholar 

  27. B. Wang and F. Zhang, “On the precise number of (0,1)-matrices in A(R,S)”, Discrete Math., Vol. 187, pp. 211–220, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  28. S. Weber, C. Schnörr, and J. Hornegger, “A linear programming relaxation for binary tomography with smoothness priors”, Electron. Notes Discrete Math., Vol. 12, 2003.

Download references

Author information

Authors and Affiliations

  1. Leiden University and CWI, The Netherlands

    Kees Joost Batenburg

Authors
  1. Kees Joost Batenburg
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kees Joost Batenburg.

Additional information

Kees Joost Batenburg received his PhD degree in Mathematics from the University of Leiden, The Netherlands, in 2006. He also holds a M.Sc. degree in Computer Science. From 2002 to 2006 he worked as a PhD student at CWI in Amsterdam and at the University of Leiden. He is currently a postdoctoral researcher at the Vision Lab of the University of Antwerp, Belgium.

His research interests include theory and applications of discrete tomography, combinatorial optimization and natural computing (evolutionary algorithms, neural networks).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Batenburg, K.J. A Network Flow Algorithm for Reconstructing Binary Images from Discrete X-rays. J Math Imaging Vis 27, 175–191 (2007). https://doi.org/10.1007/s10851-006-9798-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-006-9798-2

Keywords

Search

Navigation