Skip to main content
SpringerLink
Log in

Efficient Binary Tomographic Reconstruction

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

Abstract

Tomographic reconstruction of a binary image from few projections is considered. A novel heuristic algorithm is proposed, the central element of which is a nonlinear transformation ψ(p)=log(p/(1−p)) of the probability p that a pixel of the sought image be 1-valued. It consists of backprojections based on ψ(p) and iterative corrections. Application of this algorithm to a series of artificial test cases leads to exact binary reconstructions, (i.e., recovery of the binary image for each single pixel) from the knowledge of projection data over a few directions. Images up to 106 pixels are reconstructed in a few seconds. A series of test cases is performed for comparison with previous methods, showing a better efficiency and reduced computation times.

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.

Institutional subscriptions

Fig. 1
Algorithm 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Atkinson, C., Soria, J.: An efficient simultaneous reconstruction technique for tomographic particle image velocimetry. Exp. Fluids 47, 553–568 (2009)

    Article  Google Scholar 

  2. Baruchel, J., Buffière, J.-Y., Cloetens, P., di Michiel, M., Ferrié, E., Ludwig, W., Maire, E., Salvo, L.: Advances in synchrotron radiation microtomography. Scr. Mater. 55, 41–46 (2006)

    Article  Google Scholar 

  3. Basu, S., Bresler, Y.: \({\mathcal{O}}(N^{2} \log_{2}N)\) filtered backprojection reconstruction algorithm for tomography. IEEE Trans. Image Process. 9, 1760–1773 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  4. Basu, S., Bresler, Y.: Error analysis and performance optimization of fast hierarchical backprojection algorithms. IEEE Trans. Image Process. 10, 1103–1117 (2001)

    Article  MATH  Google Scholar 

  5. Batenburg, K.J.: A network flow algorithm for reconstructing binary images from discrete X-rays. J. Math. Imaging Vis. 27, 175–191 (2007)

    Article  MathSciNet  Google Scholar 

  6. Batenburg, K.J.: A network flow algorithm for reconstructing binary images from continuous X-rays. J. Math. Imaging Vis. 30, 231–248 (2008)

    Article  MathSciNet  Google Scholar 

  7. Batenburg, K.J., Sijbers, J.: Generic iterative subset algorithms for discrete tomography. Discrete Appl. Math. 157, 438–451 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  8. Byrne, C.L.: Iterative image reconstruction algorithms based on cross-entropy minimization. IEEE Trans. Image Process. 2, 96–103 (1993)

    Article  Google Scholar 

  9. Byrne, C.L.: Erratum and addendum to ‘Iterative image reconstruction algorithms based on cross-entropy minimization’. IEEE Trans. Image Process. 4, 226–227 (1995)

    Google Scholar 

  10. Byrne, C.L.: Block-iterative methods for image reconstruction from projections. IEEE Trans. Image Process. 5, 792–794 (1996)

    Article  Google Scholar 

  11. Byrne, C.L.: Iterative algorithms for deblurring and deconvolution with constraints. Inverse Probl. 14, 1455–1467 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  12. Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489–509 (2006)

    Article  MATH  Google Scholar 

  13. Carvalho, B.M., Herman, G.T., Matej, S., Salzberg, C., Vardi, E.: Binary tomography for triplane cardiography. In: Kuba, A., et al. (eds.) IPMI’99. LNCS, vol. 1613, pp. 29–41. Springer, Berlin (1999)

    Google Scholar 

  14. Censor, Y.: Binary steering in discrete tomography reconstruction with sequential and simultaneous iterative algorithms. Linear Algebra Appl. 339, 111–124 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  15. Darroch, J.N., Ratcliff, D.: Generalized iterative scaling for log linear models. Ann. Math. Stat. 43, 1470–1480 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  16. Donoho, D.L.: Neighborly polytopes and sparse solution of underdetermined linear equations. Technical Report, Department of Statistics, Stanford University (2004)

  17. Donoho, D.L., Tanner, J.: Counting the faces of randomly-projected hypercubes and orthants with applications. Discrete Comput. Geom. 43, 522–541 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  18. Donoho, D.L., Tanner, J.: Precise undersampling theorems. Proc. IEEE 98, 913–924 (2010)

    Article  Google Scholar 

  19. Elsinga, G.E., Scarano, F., Wieneke, B., van Oudheusden, B.W.: Tomographic particle image velocimetry. Exp. Fluids 41, 933–947 (2006)

    Article  Google Scholar 

  20. Fishburn, P., Schwander, P., Shepp, L., Vanderbei, R.: The discrete Radon transform and its approximate inversion via linear programming. Discrete Appl. Math. 75, 39–61 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  21. Gardner, R.J.: Geometric Tomography. Cambridge University Press, New York (2006)

    Book  MATH  Google Scholar 

  22. Gardner, R.J., Gritzmann, P.: Discrete tomography: determination of finite sets by X-rays. Trans. Am. Math. Soc. 349, 2271–2295 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  23. Gardner, R.J., Gritzmann, P., Prangenberg, D.: On the computational complexity of reconstructing lattice sets from their X-rays. Discrete Math. 202, 45–71 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  24. Gouillart, E., Krzakala, F., Mezard, M., Zdeborová, L.: Belief propagation reconstruction for discrete tomography. Inverse Probl. 29, 035003 (2013)

    Article  Google Scholar 

  25. Gritzmann, P., de Vries, S., Wiegelmann, M.: Approximating binary images from discrete X-rays. SIAM J. Optim. 11, 522–546 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  26. Herman, G.T., Kuba, A. (eds.): Discrete Tomography: Foundations, Algorithms and Applications. Bikhäuser, Boston (1999)

    MATH  Google Scholar 

  27. Herman, G.T., Kuba, A. (eds.): Advances in Discrete Tomography and Its Applications. Bikhäuser, Basel (2007)

    MATH  Google Scholar 

  28. Herman, G.T., Lent, A.: Iterative reconstruction algorithms. Comput. Biol. Med. 6, 273–294 (1976)

    Article  Google Scholar 

  29. Kak, A.C., Slaney, M.: Principles of Computerized Tomographic Imaging. SIAM, Philadelphia (2001)

    Book  Google Scholar 

  30. Liao, H.Y., Herman, G.T.: Direct Image Reconstruction-Segmentation as Motivated by Electron Microscopy. In: Herman, G.T., Kuba, A. (eds.): Advances in Discrete Tomography and Its Applications. Bikhäuser, Basel (2007)

    Google Scholar 

  31. Manku, G.S., Rajagopalan, S., Lindsay, B.G.: Approximate medians and other quantiles in one pass and with limited memory. In: ACM SIGMOD, vol. 12, pp. 426–435 (1998)

    Google Scholar 

  32. Mersereau, R.M.: Direct Fourier transform techniques in 3-D image reconstruction. Comput. Biol. Med. 6, 247–258 (1976)

    Article  Google Scholar 

  33. Needell, D., Ward, R.: Stable image reconstruction using total variation minimization. SIAM J. Imaging Sci. 6, 1035–1058 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  34. Schmidlin, P.: Iterative Separation of Sections in Tomographic Scintigrams. Nucl. Med., vol. 15. Schattauer, Stuttgart (1972)

    Google Scholar 

  35. Sina Jafarpour, S., Xu, W., Hassibi, B., Calderbank, A.R.: Efficient and robust compressed sensing using optimized expander graphs. IEEE Trans. Inf. Theory 55, 4299–4308 (2009)

    Article  Google Scholar 

  36. Slump, C.H., Gerbrands, J.J.: A network flow approach to reconstruction of the left ventricle from two projections. Comput. Graph. Image Process. 18, 18–36 (1982)

    Article  Google Scholar 

  37. Varga, L., Balázs, P., Nagy, A.: Direction-dependency of a binary tomographic reconstruction algorithm. In: Barneva, R.P., et al. (eds.) CompIMAGE 2010. Lect. Notes in Comput. Sci., vol. 6026, pp. 242–253 (2010)

    Google Scholar 

  38. Weber, S., Schnörr, C., Hornegger, J.: A linear programming relaxation for binary tomography with smoothness priors. Electron. Notes Discrete Math. 12 (2003)

  39. Weber, S., Nagy, A., Schüle, T., Schnörr, C., Kuba, A.: A benchmark evaluation of large-scale optimization approaches to binary tomography. In: Kuba, A., Nyúl, L.G., Palágyi, K. (eds.) Lect. Notes in Comput. Sci., vol. 4245, pp. 146–156 (2006)

    Google Scholar 

  40. Zang, C.: Private communication (2011)

Download references

Acknowledgements

Communication of the raw tomographic data shown in Fig. 4 by E. Gouillart (CNRS/Saint-Gobain, Aubervilliers, France) and C. Zang (RWTH, Aachen, Germany) is gratefully acknowledged. We are also indebted to E. Gouillart for the suggestion that boundary sites may be an appropriate measure of complexity as proposed in Ref. [24]. We also thank an anonymous reviewer for interesting and constructive remarks. This work is supported by the French Agence Nationale de la Recherche through “RUPXCUBE” (ANR-09-BLAN-0009-01) and “EDDAM” (ANR-11-BS09-027) projects.

Author information

Authors and Affiliations

  1. LMT-Cachan (ENS de Cachan/CNRS/UPMC/PRES UniverSud Paris), 61 avenue du Président Wilson, 94235, Cachan, France

    Stéphane Roux, Hugo Leclerc & François Hild

Authors
  1. Stéphane Roux
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hugo Leclerc
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. François Hild
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stéphane Roux.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Roux, S., Leclerc, H. & Hild, F. Efficient Binary Tomographic Reconstruction. J Math Imaging Vis 49, 335–351 (2014). https://doi.org/10.1007/s10851-013-0465-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-013-0465-0

Keywords

Search

Navigation