Skip to main content

2017 | OriginalPaper | Buchkapitel

A Novel Convex Relaxation for Non-binary Discrete Tomography

verfasst von : Jan Kuske, Paul Swoboda, Stefania Petra

Erschienen in: Scale Space and Variational Methods in Computer Vision

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present a novel convex relaxation and a corresponding inference algorithm for the non-binary discrete tomography problem, that is, reconstructing discrete-valued images from few linear measurements. In contrast to state of the art approaches that split the problem into a continuous reconstruction problem for the linear measurement constraints and a discrete labeling problem to enforce discrete-valued reconstructions, we propose a joint formulation that addresses both problems simultaneously, resulting in a tighter convex relaxation. For this purpose a constrained graphical model is set up and evaluated using a novel relaxation optimized by dual decomposition. We evaluate our approach experimentally and show superior solutions both mathematically (tighter relaxation) and experimentally in comparison to previously proposed relaxations.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
3.
Zurück zum Zitat Batenburg, K.J.: A network flow algorithm for reconstructing binary images from continuous X-rays. JMIV 30(3), 231–248 (2008)MathSciNetCrossRef Batenburg, K.J.: A network flow algorithm for reconstructing binary images from continuous X-rays. JMIV 30(3), 231–248 (2008)MathSciNetCrossRef
4.
Zurück zum Zitat Batenburg, K.J., Sijbers, J.: DART: a practical reconstruction algorithm for discrete tomography. IEEE TIP 20(9), 2542–2553 (2011)MathSciNet Batenburg, K.J., Sijbers, J.: DART: a practical reconstruction algorithm for discrete tomography. IEEE TIP 20(9), 2542–2553 (2011)MathSciNet
5.
Zurück zum Zitat Bussieck, M., Hassler, H., Woeginger, G.J., Zimmermann, U.T.: Fast algorithms for the maximum convolution problem. Oper. Res. Lett. 15, 1–5 (1994)MathSciNetCrossRefMATH Bussieck, M., Hassler, H., Woeginger, G.J., Zimmermann, U.T.: Fast algorithms for the maximum convolution problem. Oper. Res. Lett. 15, 1–5 (1994)MathSciNetCrossRefMATH
6.
Zurück zum Zitat Carvalho, B.M., Herman, G.T., Matej, S., Salzberg, C., Vardi, E.: Binary tomography for triplane cardiography. In: Kuba, A., Šáamal, M., Todd-Pokropek, A. (eds.) IPMI 1999. LNCS, vol. 1613, pp. 29–41. Springer, Heidelberg (1999). doi:10.1007/3-540-48714-X_3 CrossRef Carvalho, B.M., Herman, G.T., Matej, S., Salzberg, C., Vardi, E.: Binary tomography for triplane cardiography. In: Kuba, A., Šáamal, M., Todd-Pokropek, A. (eds.) IPMI 1999. LNCS, vol. 1613, pp. 29–41. Springer, Heidelberg (1999). doi:10.​1007/​3-540-48714-X_​3 CrossRef
7.
Zurück zum Zitat Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Birkhäuser, Basel (2013)CrossRefMATH Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Birkhäuser, Basel (2013)CrossRefMATH
8.
Zurück zum Zitat Gouillart, E., Krzakala, F., Mzard, M., Zdeborov, L.: Belief-propagation reconstruction for discrete tomography. Inverse Prob. 29(3), 035003 (2013)MathSciNetCrossRefMATH Gouillart, E., Krzakala, F., Mzard, M., Zdeborov, L.: Belief-propagation reconstruction for discrete tomography. Inverse Prob. 29(3), 035003 (2013)MathSciNetCrossRefMATH
9.
Zurück zum Zitat Kappes, J.H., Petra, S., Schnörr, C., Zisler, M.: TomoGC: binary tomography by constrained graphcuts. In: Gall, J., Gehler, P., Leibe, B. (eds.) GCPR 2015. LNCS, vol. 9358, pp. 262–273. Springer, Cham (2015). doi:10.1007/978-3-319-24947-6_21 CrossRef Kappes, J.H., Petra, S., Schnörr, C., Zisler, M.: TomoGC: binary tomography by constrained graphcuts. In: Gall, J., Gehler, P., Leibe, B. (eds.) GCPR 2015. LNCS, vol. 9358, pp. 262–273. Springer, Cham (2015). doi:10.​1007/​978-3-319-24947-6_​21 CrossRef
10.
Zurück zum Zitat Keiper, S., Kutyniok, G., Lee, D.G., Pfander, G.E.: Compressed sensing for finite-valued signals. ArXiv e-prints, September 2016 Keiper, S., Kutyniok, G., Lee, D.G., Pfander, G.E.: Compressed sensing for finite-valued signals. ArXiv e-prints, September 2016
11.
Zurück zum Zitat Liao, H.Y., Herman, G.T.: Automated estimation of the parameters of Gibbs priors to be used in binary tomography. Discret. Appl. Math. 139(1–3), 149–170 (2004)MathSciNetCrossRefMATH Liao, H.Y., Herman, G.T.: Automated estimation of the parameters of Gibbs priors to be used in binary tomography. Discret. Appl. Math. 139(1–3), 149–170 (2004)MathSciNetCrossRefMATH
12.
Zurück zum Zitat Mohammad-Djafari, A.: Gauss-Markov-Potts priors for images in computer tomography resulting to joint optimal reconstruction and segmentation. Int. J. Tomogr. Stat. 11(W09), 76–92 (2008)MathSciNet Mohammad-Djafari, A.: Gauss-Markov-Potts priors for images in computer tomography resulting to joint optimal reconstruction and segmentation. Int. J. Tomogr. Stat. 11(W09), 76–92 (2008)MathSciNet
13.
14.
Zurück zum Zitat Schüle, T., Schnörr, C., Weber, S., Hornegger, J.: Discrete tomography by convex-concave regularization and D.C. programming. Discret. Appl. Math. 151, 229–243 (2005)MathSciNetCrossRefMATH Schüle, T., Schnörr, C., Weber, S., Hornegger, J.: Discrete tomography by convex-concave regularization and D.C. programming. Discret. Appl. Math. 151, 229–243 (2005)MathSciNetCrossRefMATH
15.
Zurück zum Zitat Sontag, D., Globerson, A., Jaakkola, T.: Introduction to dual decomposition for inference. In: Optimization for Machine Learning. MIT Press (2011) Sontag, D., Globerson, A., Jaakkola, T.: Introduction to dual decomposition for inference. In: Optimization for Machine Learning. MIT Press (2011)
16.
Zurück zum Zitat Tarlow, D., Swersky, K., Zemel, R.S., Adams, R.P., Frey, B.J.: Fast exact inference for recursive cardinality models. In: UAI (2012) Tarlow, D., Swersky, K., Zemel, R.S., Adams, R.P., Frey, B.J.: Fast exact inference for recursive cardinality models. In: UAI (2012)
17.
Zurück zum Zitat Weber, S., Schnörr, C., Hornegger, J.: A linear programming relaxation for binary tomography with smoothness priors. In: IWCIA (2003) Weber, S., Schnörr, C., Hornegger, J.: A linear programming relaxation for binary tomography with smoothness priors. In: IWCIA (2003)
18.
Zurück zum Zitat Werner, T.: A linear programming approach to max-sum problem: a review. IEEE TPAMI 29(7), 1165–1179 (2007)CrossRef Werner, T.: A linear programming approach to max-sum problem: a review. IEEE TPAMI 29(7), 1165–1179 (2007)CrossRef
19.
Zurück zum Zitat Zisler, M., Petra, S., Schnörr, C., Schnörr, C.: Discrete tomography by continuous multilabeling subject to projection constraints. In: Rosenhahn, B., Andres, B. (eds.) GCPR 2016. LNCS, vol. 9796, pp. 261–272. Springer, Cham (2016). doi:10.1007/978-3-319-45886-1_21 CrossRef Zisler, M., Petra, S., Schnörr, C., Schnörr, C.: Discrete tomography by continuous multilabeling subject to projection constraints. In: Rosenhahn, B., Andres, B. (eds.) GCPR 2016. LNCS, vol. 9796, pp. 261–272. Springer, Cham (2016). doi:10.​1007/​978-3-319-45886-1_​21 CrossRef
Metadaten
Titel
A Novel Convex Relaxation for Non-binary Discrete Tomography
verfasst von
Jan Kuske
Paul Swoboda
Stefania Petra
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-58771-4_19