Calculus of variations and image segmentation

doi:10.1016/j.jphysparis.2003.09.008

Journal of Physiology-Paris

Volume 97, Issues 2–3, March–May 2003, Pages 343-353

https://doi.org/10.1016/j.jphysparis.2003.09.008 Get rights and content

Abstract

A survey of free discontinuity problems related to image segmentation is given. The main properties and open problems about Mumford and Shah and Blake and Zisserman functionals are shown together with an extensive bibliography about recent mathematical developments.

Introduction

Calculus of variations is the framework where energy minimization and equilibrium notions find a precise language and formalizations by means of variational principles.

Image segmentation is a relevant problem both in digital image processing and in the understanding of biological vision.

This paper contains a brief survey of recent results in mathematical analysis which are related to the formulation and testing of algorithms for automatic segmentation of digital images as well as the understanding of visual perception.

There exist many different ways to define the tasks of segmentation (template matching, component labeling, thresholding, boundary detection, quad-trees, texture matching, texture segmentation) and there is no universally accepted notion (optimality criteria for segmentation, analogies and differences between biological and automata perspective in segmentation): this exposition is confined to some models for decomposing an image field, where is given a function describing the signal intensity associate to each point (typically the light intensity on a screen image). Such purpose has a clear connection with the problem of optimal partitions of a domain minimizing the length of the boundaries. In simple words the segmentation we look for provides a cartoon of the given image satisfying some requirements: the decomposition of the image is performed by choosing a pattern of lines of steepest discontinuity of the light intensity, and this pattern will be called segmentation.

The segmentation can be achieved by several techniques (see [23], [29], [32], [34], [38]). We describe some approaches based on variational principles: that is procedures of minimization for suitable integral energy associated to admissible segmentations of the given image. We emphasize that the functions describing the light intensity in admissible segmentations can display discontinuities.

These segmentation models are useful in robot vision description but can provide also some hints to relevant questions in physiology of vision. For instance these models may help in understanding how the huge amount of data contained in a single image can be reduced and quickly processed, still preserving the essential geometric patterns which are the cornerstone in the interpretation of the image.

The variational formalizations of segmentation models provided deeper understanding of image analysis, produced intriguing mathematical questions (some of them still open) and entailed global estimates for geometric quantities in visual and automatic perception at both low and high level.

We collect here several results obtained in recent years by many authors based on the innovative notion of free discontinuity problems introduced by Ennio De Giorgi [25]. In such framework, modern tools of Geometric Measure Theory and recent developments about minimal surfaces and regularity of extremals in calculus of variations allow the study of problems coupling bulk and surface terms: in such context discontinuous (in the mathematical sense) solutions are admissible and sometimes their discontinuities are the main features of the solution.

We outline the main properties of two variational models known in the literature as the Mumford and Shah model (see [36]) and the Blake and Zisserman model (see [9]). These approaches balance carefully signal smoothing and segmentation length; often they are more accurate in detecting discontinuities than Laplacian zero-crossing or other filtering techniques.

We just quote here other variational models about segmentation focusing occlusions: Mumford et al. [35], Bellettini and March [8]; and models adding an explicit extra term for segmentation curvature in the energy functionals: Bellettini et al. [7].

We limit our discussion to bi-dimensional, monochromatic images. About the colour case we refer to the analysis of vector-valued signals [11], [19].

In this paper we consider only bi-dimensional analogic images, which are an idealized description of digital images when the (pixels or receptors) frequency sampling goes to infinity. We assume that both the image and its reconstruction are defined at each point of the field, instead of in a discrete array of pixels in a monitor screen, or random grains in a photographic picture.

The exposition is aimed also to non-specialists in calculus of variations; for this reason we skip the analysis in a general context and confine ourselves to model cases: somewhere the statements are given under redundant assumptions in order to simplify the exposition.

We refer to the enclosed bibliography and to the web-page of the Research Group in calculus of variations and geometric measure theory http://cvgmt.sns.it.

Section snippets

Mumford and Shah functional

Given a bounded open set $Ω⊂ R^{2}$ , we consider the following functional, introduced in [36] by Mumford and Shah, $MS (K,u):=∫∫_{Ω⧹K} ∥ D u∥^{2} +μ|u−g|^{2} d x_{1} d x_{2} +α length (K∩Ω),$ where K⊂R² is the union of a (a priori unknown) family of curves, x=(x₁,x₂) denotes a point in $Ω$ , $length (K∩Ω)$ denotes the sum of the length of these curves and u is a differentiable scalar function in $Ω⧹K$ ; by ∥Du∥ we denote the euclidean norm of the gradient $D u=(∂ u ∂ x_{1}, ∂ u ∂ x_{2})$ of u. The datum g is a given bounded function defined on $Ω$ . We

Blake and Zisserman functional

The study of minimizing functionals depending on a second order bulk energy and a surfacic (better to say lineic in the present two dimensional situation) discontinuity energy has recently attracted the interest of many researchers in connection with problems in fracture theory, optimal partitions, elastic-plastic plates [14], [28], [37] and image segmentation.

In this section we focus the functional depending on higher order derivatives [9], [16] $BZ (K_{0},K_{1},u):=∫∫_{Ω⧹(K_{0}∪K_{1})} ∥ D^{2} u∥^{2} +μ|u−g|^{2} d x_{1} d x_{2} +α$

Free discontinuity problems

Minimization of $MS$ and $BZ$ functionals are free discontinuity problems, in the sense that among the unknowns there are sets which are not necessarily boundaries.

The general approach introduced by De Giorgi in [25] to solve free discontinuity problems is a subtle application of the direct methods in calculus of variations. The first step is the weak formulation of the minimum problem in a suitable function space, called $SBV (Ω)$ , whose elements admit discontinuities only along sets of dimension

Acknowledgements

Work partially supported by MIUR COFIN 2000 Project “Calcolo delle Variazioni”, by Politecnico di Milano Project “Analisi di Problemi Variazionali e Differenziali” and by MIUR Project (Cluster 15, Legge 488) “Riconoscimento ed Elaborazione d’Immagini con Applicazioni in Medicina e Industria”.

References (38)

G. Alberti et al.
The calibration method for the Mumford–Shah functional
C.R. Acad. Sci. Paris, Ser. I Math.
(1999)
M. Carriero et al.
Necessary conditions for extremals of Blake and Zisserman functional
C. R. Acad. Sci. Paris, Ser. I
(2002)
R. March
Visual reconstruction with discontinuities using variationa methods
Image and Vision Computing
(1992)
L. Ambrosio
A compactness theorem for a special class of functions of bounded variation
Boll. Un. Mat. It.
(1989)
L. Ambrosio et al.
Variational approximation of a second order free discontinuity problem in computer vision
SIAM J. Math. Anal.
(2001)
L. Ambrosio et al.
Higher integrability of the gradient and dimension of the singular set for minimizers of the Mumford–Shah functional
Calc. Var.
(2003)
L. Ambrosio et al.
Functions of bounded variations and free discontinuity problems
(2000)
L. Ambrosio et al.
Approximation of functionals depending on jumps by elliptic functionals via Γ-convergence
Comm. Pure Appl. Math.
(1991)
G. Bellettini et al.
Semicontinuity and relaxation properties of a curvature depending functional in 2D
Ann. Sc. Norm. Super. Pisa, Cl. Sci. Ser. IV
(1993)
G. Bellettini, R. March, Variational approximation of a model for image segmentation with overlapping regions, in: G....

A. Blake et al.

Visual Reconstruction

(1987)

A. Bonnet et al.

Crack-tip is a global Mumford–Shah minimizer

Astérisque

(2001)

M. Carriero et al.

S^k-valued maps minimizing the L^p norm of the gradient with free discontinuities

Ann. Sc. Norm. Pisa, Ser. IV

(1991)

M. Carriero, A. Leaci, D. Pallara, E. Pascali, Euler conditions for a minimum problem with free discontinuity surfaces....

M. Carriero et al.

Special bounded Hessian an elastic–plastic plate

Rend. Accad. Naz. delle Scienze (dei XL), (109)

(1992)

M. Carriero et al.

Free gradient discontinuities

M. Carriero, A. Leaci, F. Tomarelli, A second order model in image segmentation: Blake and Zisserman functional, in: R....

M. Carriero et al.

Strong minimizers of Blake and Zisserman functional

Ann. Sc. Norm. Super. Pisa, Ser. IV

(1997)

M. Carriero et al.

Density estimates and further properties of Blake and Zisserman functional

Cited by (21)

A candidate local minimizer of Blake and Zisserman functional
2011, Journal des Mathematiques Pures et Appliquees
We show Euler equations fulfilled by strong minimizers of Blake and Zisserman functional. We prove an Almansi-type decomposition and provide explicit coefficients of asymptotic expansion for bi-harmonic functions in a disk with a cut from center to boundary. We deduce the stress intensity factor and modes coefficients of the leading term in the expansion around crack-tip for any locally minimizing triplet of the main part of Blake and Zisserman functional in the strong formulation. We exhibit explicitly a non-trivial candidate for minimality which has a crack-tip and fulfills all integral and geometric conditions of extremality.
On démontre les équations dʼEuler vérifiées par les triplets minimisants de la fonctionnelle de Blake et Zisserman. On démontre lʼexistence dʼune décomposition de type Almansi pour les fonctions biharmoniques dans un disque privé dʼun rayon. On obtient le terme principal du développement au voisinage dʼun crack-tip. On exhibe explicitement un candidat minimiseur non-trivial qui satisfait toutes les conditions nécessaires dʼextrémalité.
How do high-level specifications of the brain relate to variational approaches?
2007, Journal of Physiology Paris
High-level specification of how the brain represents and categorizes the causes of its sensory input allows to link “what is to be done” (perceptual task) with “how to do it” (neural network calculation). In this article, we describe how the variational framework, which encountered a large success in modeling computer vision tasks, has some interesting relationships, at a mesoscopic scale, with computational neuroscience. We focus on cortical map computations such that “what is to be done” can be represented as a variational approach, i.e., an optimization problem defined over a continuous functional space. In particular, generalizing some existing results, we show how a general variational approach can be solved by an analog neural network with a given architecture and conversely. Numerical experiments are provided as an illustration of this general framework, which is a promising framework for modeling macro-behaviors in computational neuroscience.
Almansi Decomposition and Expansion of a Polyharmonic Function Near a Crack-Tip
2024, Journal of Convex Analysis
Elastic-brittle reinforcement of flexural structures
2021, arXiv
Elastic-brittle reinforcement of flexural structures
2021, Atti della Accademia Nazionale dei Lincei, Classe di Scienze Fisiche, Matematiche e Naturali, Rendiconti Lincei Matematica e Applicazioni
Segmentation and inpainting of color images
2018, Journal of Convex Analysis

View all citing articles on Scopus

View full text

Calculus of variations and image segmentation

Abstract

Introduction

Section snippets

Mumford and Shah functional

Blake and Zisserman functional

Free discontinuity problems

Acknowledgements

C.R. Acad. Sci. Paris, Ser. I Math.

C. R. Acad. Sci. Paris, Ser. I

Image and Vision Computing

A compactness theorem for a special class of functions of bounded variation

Boll. Un. Mat. It.

Variational approximation of a second order free discontinuity problem in computer vision

SIAM J. Math. Anal.

Higher integrability of the gradient and dimension of the singular set for minimizers of the Mumford–Shah functional

Calc. Var.

Functions of bounded variations and free discontinuity problems

Approximation of functionals depending on jumps by elliptic functionals via Γ-convergence

Comm. Pure Appl. Math.

Semicontinuity and relaxation properties of a curvature depending functional in 2D

Ann. Sc. Norm. Super. Pisa, Cl. Sci. Ser. IV

Visual Reconstruction

Crack-tip is a global Mumford–Shah minimizer

Astérisque

Sk-valued maps minimizing the Lp norm of the gradient with free discontinuities

Ann. Sc. Norm. Pisa, Ser. IV

Special bounded Hessian an elastic–plastic plate

Rend. Accad. Naz. delle Scienze (dei XL), (109)

Free gradient discontinuities

Strong minimizers of Blake and Zisserman functional

Ann. Sc. Norm. Super. Pisa, Ser. IV

Density estimates and further properties of Blake and Zisserman functional

S^k-valued maps minimizing the L^p norm of the gradient with free discontinuities