On The Primal and Dual Formulations Of The Discrete Mumford-Shah Functional

Nelly PustelnikICASSP 2023 · DOI

TL;DR

This paper bridges the gap between primal and dual formulations of the discrete Mumford-Shah (D-MS) functional, a powerful tool for image restoration and contour detection. By establishing this equivalence, the authors unlock a wider range of efficient optimization algorithms, including advanced proximal methods, for tackling complex image processing tasks.

What Problem Does This Paper Address?

Image processing tasks like denoising and segmentation often require finding a "clean" image from a degraded observation. The Mumford-Shah (MS) functional, and its discrete counterpart (D-MS), are classic approaches that excel at this by promoting piecewise smooth images and simultaneously detecting edges (contours). However, minimizing the D-MS functional is notoriously challenging due to its non-convex nature. While primal and dual formulations of the D-MS functional were explored in the past, recent advancements in D-MS have led to new formulations for which the equivalence between primal and dual forms hasn't been fully established. This paper aims to fill that gap, providing a unified framework that can leverage a broader spectrum of optimization techniques.

Methods

The core contribution of this paper is the derivation of the dual formulation for a specific, modern version of the discrete Mumford-Shah functional. This functional is inspired by the Ambrosio-Tortorelli formulation and is presented as Problem 1 in the paper. The authors achieve this by leveraging the concept of proximity operators, a fundamental tool in convex and non-convex optimization.

They then explore two main algorithmic strategies:

  • Alternating Minimization for the Primal: This approach, based on the semi-linearized PAM procedure, involves iteratively updating the image estimate and the edge variables. It can utilize either gradient-based or proximal updates for the data-fidelity term.
  • Gradient-Based Algorithms for the Dual: For the derived dual formulation, which turns out to be smooth (under specific assumptions), the authors propose gradient descent and proximal gradient descent methods.

Crucially, the paper also investigates the use of a BFGS (Broyden–Fletcher–Goldfarb–Shanno) algorithm, a quasi-Newton method, for minimizing the dual formulation. This is significant because BFGS is a higher-order optimization method that can often converge faster than first-order methods, especially for smooth problems.

Datasets

Not discussed in the paper. The experiments use synthetic images for denoising and restoration tasks.

Key Insights and Ideas

  • Bridging the Primal-Dual Divide: The paper successfully establishes a formal link between primal and dual formulations for a contemporary D-MS functional. This is important because it allows researchers to choose the formulation that best suits their algorithmic needs and computational resources.
  • Unlocking Optimization Power: By providing the dual formulation, the paper opens the door to applying a wider array of optimization techniques. This includes powerful proximal algorithms that can handle non-smoothness efficiently and, as demonstrated, even higher-order methods like BFGS.
  • Smoothness of the Dual: Under certain common assumptions (e.g., quadratic data fidelity and specific choices for edge and contour penalties), the dual formulation becomes smooth. This is a significant advantage, as smooth optimization problems are generally easier to solve and allow for faster convergence with methods like gradient descent and BFGS.
  • Algorithm Comparison: The paper provides valuable insights into the practical performance of different algorithms. It highlights that proximal-based methods often outperform their gradient-only counterparts, and that primal-SLPAM (a primal method) is particularly efficient. The comparison with BFGS on the dual problem shows its competitive performance, suggesting that higher-order methods are indeed beneficial.

Key Results

The paper demonstrates through numerical experiments that:

  • Primal-SLPAM is consistently one of the fastest algorithms for minimizing the primal objective function.
  • Dual-BFGS shows very competitive performance, often matching or even surpassing first-order primal and dual methods, especially in restoration scenarios.
  • The choice between primal and dual methods can depend on the specific problem configuration (denoising vs. restoration).

Limitations and Future Work

The authors acknowledge the following:

  • Convergence Guarantees: While the paper discusses algorithms with convergence guarantees (e.g., using Kurdyka-Łojasiewicz properties), the extension to dimension 2 using ADMM (Alternating Direction Method of Multipliers) comes with weaker convergence guarantees.
  • Future Work: The authors suggest establishing convergence rates for strongly convex functions and identifying specific regimes where one method might be preferable over another. They also point out the growing interest in deep learning architectures that can incorporate model-based minimization procedures, and how the flexibility offered by primal and dual formulations can be leveraged for designing such architectures.

Summary updated

BibTeX
@inproceedings{pustelnik2023primal,
  author = {Nelly Pustelnik},
  title = {{On The Primal and Dual Formulations Of The Discrete Mumford-Shah Functional}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2023},
  doi = {10.1109/icassp49357.2023.10095610},
}

Loading related content...

Figure