Joint Image Reconstruction and Segmentation Using the Potts Model

Martin Storath; Andreas Weinmann; Jürgen Frikel; Michael Unser

Source-linked AI summary

Joint Image Reconstruction and Segmentation Using the Potts Model

Martin Storath, Andreas Weinmann, Jürgen Frikel, Michael Unser

arXiv:1405.5850v3May 22, 2014math.OCcs.NAmath.NAphysics.med-ph

TL;DR

Incomplete and noisy imaging data make reconstruction severely ill-posed, while the Potts problem is algorithmically challenging. The paper splits the Potts problem into efficiently solvable subproblems, achieving an almost perfect Shepp-Logan reconstruction and segmentation from seven projections and reliable segmentation on physical PET data.

Problem
Incomplete, noisy, and sometimes blurred imaging data make reconstruction severely ill-posed, with small data perturbations potentially causing large reconstruction errors.
Source: §1 · p. 2
Method
The method splits the discrete Potts problem into tractable subproblems, using a near-isotropic discretization and requiring no a priori segment count or gray levels.
Source: §1 · p. 3, §2 · p. 6, §5 · p. 22
Results
The method achieves an almost perfect reconstruction and segmentation of the Shepp-Logan phantom from as few as seven projections.
Source: §1 · p. 4
Takeaways & Limitations
The method also yields reliable segmentation of anatomic structures in physical PET data and is demonstrated on spherical Radon and blurred vector-valued data.
Source: §1 · p. 4
The described dense-sampling procedure applies only to densely sampled data and produces unacceptably large errors with sparse-angle data.
Source: §3.2 · p. 21

Abstract

from arXiv · show

We propose a new algorithmic approach to the non-smooth and non-convex Potts problem (also called piecewise-constant Mumford-Shah problem) for inverse imaging problems. We derive a suitable splitting into specific subproblems that can all be solved efficiently. Our method does not require a priori knowledge on the gray levels nor on the number of segments of the reconstruction. Further, it avoids anisotropic artifacts such as geometric staircasing. We demonstrate the suitability of our method for joint image reconstruction and segmentation. We focus on Radon data, where we in particular consider limited data situations. For instance, our method is able to recover all segments of the Shepp-Logan phantom from $7$ angular views only. We illustrate the practical applicability on a real PET dataset. As further applications, we consider spherical Radon data as well as blurred data.

1. Introduction

Incomplete, noisy, and sometimes blurred imaging data make reconstruction ill-posed, while the Potts model can jointly reconstruct piecewise-constant images and segment them. The paper introduces a splitting-based method and demonstrates its use across sparse Radon, PET, spherical Radon, and deconvolution settings.

1. Introduction

Incomplete, noisy, or blurred data can make imaging severely ill-posed, so small data perturbations may cause large reconstruction errors and some features may be invisible.The paper notes that recovering an object at a coarser scale can still be useful, for example for locating organs in surgery planning.Source: §1 · p. 2
The Potts model penalizes discontinuity length while fitting the data, and its piecewise-constant solution provides both an approximate reconstruction and a partition of the image domain.The paper states that joint reconstruction and segmentation typically perform better than successive application of the two steps.Source: §1 · p. 2
The proposed splitting reduces the Potts problem to a Tikhonov-regularized linear system and dynamic-programming subproblems, without fixing gray values, segment count, or an initial guess.The algorithm is proved to converge and is described as highly parallelizable and easy to implement.Source: §1 · pp. 3–4
From seven projections, the method almost perfectly reconstructs and segments the Shepp-Logan phantom, and it also yields high-quality results with noise and reliable segmentation on a physical PET phantom.The paper also discusses photoacoustic tomography with spherical Radon data and deconvolution of vector-valued data.Source: §1 · p. 4

1.1. Potts Regularization in Inverse Problems

Potts regularization fits inverse problems with operators that may not be boundedly invertible, but continuous-domain minimizers are not guaranteed, unlike in the discrete setup.Existing regularization results assume bounded, non-degenerate piecewise-constant solutions with at most a fixed number of values.Source: §1.1 · p. 4

1.2. Existing Algorithmic Approaches to Potts and Related Problems

Prior approaches include active contours and graph cuts, while total-variation relaxations are convex but can lack sharply localized boundaries in limited-data settings.Active contours require an initial-contour and gray-value-count guess; graph cuts require discretizing the solution values, and non-convex priors and ℓ0 transformations are also discussed.Source: §1.2 · pp. 5–6

1.3. Organization of the Article

The article proceeds from the splitting and more isotropic discretizations to applications on Radon and spherical Radon data, real PET data, and deconvolution.It also discusses general data terms and proves algorithm convergence.Source: §1.3 · p. 6

2. A Splitting Approach for the Potts Problem

The section presents a splitting approach that decomposes the discrete Potts problem into tractable subproblems, using neighborhoods designed to approximate Euclidean boundary length. It also analyzes convergence, showing that the sequence is Cauchy and the auxiliary sequences converge to the same limit.

2.1. Basic Splitting Algorithm for an Anisotropic Discretization

The anisotropic axis-aligned discretization measures boundary length in the Manhattan metric and can cause staircasing; ADMM makes its split subproblems separately tractable.The image-data subproblem is a classical L2 Tikhonov regularization, while the directional terms decompose into univariate Potts problems.Source: §2 · p. 6, §2.1 · pp. 7–8
The basic anisotropic regularizer counts horizontal and vertical pixel differences, using coordinate-axis finite differences with unit weights.Source: §2.1 · p. 6

2.2. Design of Isotropic Discretizations

The isotropy ratio E improves from E0 ≈ 1.41 for N0 to E1 ≈ 1.08 for N1 and E2 ≈ 1.03 for N2; N2 weights are more isotropic than those of.N1 adds diagonal directions and N2 adds knight-move differences.Source: §2.2 · pp. 8, 11, Figure 3 · p. 10

2.3. Splitting Scheme for General Discretizations

For a general finite-difference neighborhood, ADMM splits the Potts problem into univariate Potts problems along induced paths and a Tikhonov regularization subproblem.The anisotropic splitting is a special case of this general scheme.Source: §2.3 · p. 12

2.4. Solution of the Subproblems

Univariate Potts subproblems can be solved exactly by dynamic programming in polynomial time; the cited algorithm runs in O(n^2) time and O(n) space.The Tikhonov subproblem is solved through its normal equation, for example with conjugate gradients.Source: §2.4 · pp. 12–13

2.5. General Data Terms

The algorithm also accommodates data terms beyond L2, including Lp terms for p ≥ 1 and Huber terms, when their proximity operators can be evaluated efficiently.Source: §2.5 · p. 14

2.6. Convergence

With increasing μk and νk = 0 for all k, the general ADMM iteration converges, with μk residuals tending to zero for each split variable.Convergence with general νk is left as an open problem.Source: §2.6 · p. 14
Under the stated assumption on μ_k, v^k is Cauchy and therefore converges to a limit v*.The proof establishes the Cauchy property for v^k before concluding its convergence.Source: §2.6 · p. 16
Each auxiliary sequence u_s^k converges, and its limit equals v*.The argument first shows u_s^k − v^k → 0 for every s, then uses convergence of v^k.Source: §2.6 · p. 16

3. Application to Radon Data

The paper applies joint reconstruction and segmentation to Radon data, including sparse-angle and noisy cases, and evaluates results on a physical PET phantom. The experiments show strong recovery with few projections, while parameter choice and noise affect small structures.

3. Application to Radon Data

The application produces a piecewise-constant reconstruction that induces a partition of the image domain, using Radon data from CT and PET settings.Segmentation quality is assessed with the Rand index against ground-truth partitions induced by piecewise-constant images.Source: §3 · pp. 16–17

3.1. Radon Data with Sparse Angular Sampling

From 7 projections, the Potts method achieves an almost perfect Shepp-Logan segmentation; TV quality decreases significantly below 17 projections.Filtered backprojection produces strong artifacts in this undersampled setting.Source: Figure 4 · p. 18, §3.1 · p. 19
Classical reconstruction followed by segmentation performs poorly in sparse-angle data, unlike the proposed joint approach.The comparison uses α-expansion graph-cut for the subsequent segmentation.Source: §3.1 · p. 19
Higher γ removes smaller details, while macrostructures remain recovered in the 12-projection noise-free experiment.With Gaussian noise at 12 angles, small structures vanish but large-scale structures are recovered reliably.Source: §3.1 · p. 19, Figure 5 · p. 19, Figure 6 · p. 20

3.2. Radon Data with Dense Angular Sampling

For dense sampling at 360 angles, large geometric structures remain reliably segmented even at very high noise levels.Source: Figure 7 · p. 20, §3.2 · p. 21
A filtered-backprojection-type solution for the Tikhonov subproblem is an efficient alternative for dense data, but produces unacceptably large errors with sparse angles.The authors describe this alternative as applicable only to densely sampled data.Source: §3.2 · pp. 20–21

3.3. Real Radon Data from a PET Device

On sparsely sampled PET data from a physical thorax phantom, the method jointly reconstructs and segments the lungs, spine, and thorax body.The PET model reduces to the classical Radon-transform setup after accounting for known attenuation.Source: §3.3 · p. 21, Figure 8 · p. 21

4. Further Applications

The paper extends joint reconstruction and segmentation to spherical Radon data and blurred images. In these applications, it reports recovery from sparse measurements and restoration of blurred data.

4.1. Spherical Radon Data

With 7 spherical-Radon angles, the method almost perfectly recovers the Shepp-Logan image, while FBP-type and total-variation reconstructions show severe artifacts.The experiment uses 7 equispaced angles and 512 equispaced radii.Source: §4.1 · p. 22, Figure 9 · p. 22

4.2. Blurred Data

For deblurring, the method handles vector-valued images at linear cost in channel dimension, and a positive coupling sequence can improve motion-blur restoration.Processing a color image costs about three times as much as processing a grayscale image.Source: §4.2 · p. 22

5. Conclusion

The conclusion presents the splitting approach as a way to solve the Potts problem efficiently using near-isotropic approximations. It reports recovery from seven projections for two Radon-data settings, along with results on incomplete, noisy, and real tomographic data.

5. Conclusion

The approach uses near-isotropic approximations of length terms to split the Potts problem into subproblems solvable by efficient algorithms.The conclusion describes these approximations as enabling the splitting.Source: §5 · pp. 22–23
In Gaussian-blurred, extreme-noise data, increasing isotropy makes the reconstructed segment boundaries smoother.The figure uses a Gaussian kernel with standard deviation 10 and noise level 0.5.Source: Figure 10 · p. 23
For simulated horizontal motion blur, the traffic-sign letters are recovered almost perfectly, with better results using νk = µk/S than νk = 0.The blur length is 65 pixels and the Gaussian noise level is 0.1.Source: Figure 11 · p. 23
The algorithm recovers every Shepp-Logan segment from seven projections of both Radon and spherical Radon data, and also gives high-quality results on incomplete, noisy, and real tomographic data.The conclusion states that the real-data application is joint reconstruction and segmentation.Source: §5 · p. 23

Appendix A. Proof of Equation (28)

The proof rewrites the cost functional using substitutions, then characterizes its minimizer through a normal equation. Fourier analysis and the Fourier-slice theorem are used to derive the stated relation.

Appendix A. Proof of Equation (28)

Setting u = v − z and g = f − Rz rewrites the cost functional as a Tikhonov-type objective in u.The rewritten expression is ∥Ru − g∥2^2 + α∥u∥2^2.Source: Appendix A · p. 23
The minimizer uα satisfies the normal equation R*Ruα + αuα = R*g.The proof identifies this as the normal equation associated with the rewritten objective.Source: Appendix A · p. 24
The proof Fourier-transforms the normal equation, applies the convolution theorem, and then uses the Fourier-slice theorem to derive the relation for uα.It also notes that formula (A.2) is a special case of a formula derived in [49, Sec. 7].Source: Appendix A · p. 24