Markov Random Fields and Computer Vision
LOW LEVEL VISION TASKS
GIBBS RELAXATION TECHNIQUES AND PARAMETERS ESTIMATION
CONTOUR LINES EXTRACTION AND TEXTURE SEGMENTATION
3D-OBJECTS RECONSTRUCTION X-RAY TOMOGRAPHY AND ULTRASOUND SENSORS
THE “SUDIMAGE” CONSULTING GROUP
MARKOV RANDOM FIELDS AND IMAGE ANALYSIS
The 1984 seminal paper of D. and S. GEMAN on Markov random fields and image restoration lifted only a corner of the veil for exploration and development of image modelization by random vector fields in dimension 2 or 3, having the spatial Markov property.
I soon felt that it was possible to conceive and implement a unified « energy minimization » methodology, rooted in Markov random field models of digital images, to cover all the essential tasks of low level vision [restoration, reconstruction, contour lines extraction, texture segmentation, optical flow analysis on video-sequences].
This long range research program was the topic of a scientific communication I gave at the annual meeting of France Mathematical Society (SMF) in 1986, and which was reprinted in 2003 in a collection of selected SMF papers, with an added commentary by Jean-Michel MOREL. He pointed out the links between the research goals I had then set for Markov fields models in image analysis, and the breakthrough approach of image analysis by “continuous” energy minimisation and variational calculus, which MOREL impulsed in the mid nineties, along with Pierre-Louis LIONS, David MUMFORD, and altri.
I undertook and directed this massive research program on Markov random fields and image analysis, which lasted about 10 years, in tight collaboration with a group of twelve young PhDs in applied mathematics , including nine of my own PhD students:
Michel LEVY, Bernard CHALMOND, Christine GRAFFIGNE, Laurent YOUNES, Olivier CATONI, Isabelle GAUDRON, Francois COLDEFY, Jia Ping WANG, Etienne GOUBET, Christophe LABOURDETTE, Jen Feng YAO, Wei Fei XIONG .
This enthusiastic and gifted team of researchers became the backbone of the SUDIMAGE consulting group in computer vision , which I launched in 1989 .
>>Back to Top
GIBBS RELAXATION TECHNIQUES AND PARAMETER ESTIMATION
After GEMAN’s papers, it had become mathematically clear that Markov random fields were essentially Gibbs measures defined by an adequate “Gibbs like” energy function, which associated an energy value to each global “image configuration”, high energy configurations being the less likely to be observed.
Here an “image configuration” is any complete set of values for local vector descriptors of the image, with one vector descriptor assigned to each pixel site of the image. Gibbs energies adequate for this context naturally include “interaction terms” between local descriptors , with a “small” bounded range for these spatial interactions terms
I had perceived very early that a key point to efficiently implement an image analysis task was to cleverly select a rich enough descriptor at each image site, so that the “unobserved” part of the descriptor contained the “local solution” of the image analysis task, and so that the observed part of the descriptor played the role of local constraints on the local solution. The role of global energy minimization was then essentially, through local spatial interactions, to smooth out the global field of local solutions.
Energy minimization becomes then essentially an iterative “relaxation” task, implying large numbers of successive modifications for the “optimal” descriptor field.
Actually, classical computer vision, had in the late seventies already introduced several ad hoc and half-hazard “relaxation schemes” to regularize contours for instance, but with no clear rigorous probabilistic concept to really understand and optimize seriously the relaxation approach.
I hence focused Michel LEVY’s PhD thesis on the mathematical comparative study of classical computer vision relaxation approaches and Markov random fields stochastic relaxation schemes. His results, and computing experiments with stochastic relaxation through simulated annealing, quickly clarified that simulated annealing was (on 1986 computers!) a much too lengthy computing task for fast image analysis, so that we implemented much faster relaxation algorithms, in the spirit of BESAG and altri, for efficient minimization of the Gibbs-Markov fields energies adapted to image analysis.
The second key point I understood in my own initial reflexions on this topic was that practical but rigorous algorithmics for empirical parameter estimation of Gibbs energy functions would boost up the adequation between these Markov random field models and given classes of images. Laurent YOUNES, in his PhD thesis under my direction, proved the consistency of adaptive parameter estimators for Markov fields, interwoven with stochastic Gibbs relaxation.
This was the successful beginning of a ten years intensive scientific collaboration in image analyzis that I had the pleasure to maintain and deepen with L. YOUNES, while he was clearly becoming an internationally known expert in these areas.
Simultaneously, in collaboration with B. CHALMOND, C. GRAFFIGNE, I. GAUDRON, we introduced qualitative “polyhedral boxes” for fast localization of unknown parameter vectors for Markov random fields, whereby qualitative simple and intuitive local probabilistic statements about the families of images to modelize were directly transformed into linear inequalities for the unknown vector of parameters controlling the Markov random field model.
This provided good initial points for Monte-Carlo “relaxation / estimation" techniques such as those studied in depth by L. YOUNES in his PhD and subsequent papers.
>>Back to Top
CONTOUR LINES EXTRACTION AND TEXTURE SEGMENTATION
A basic scientific step for our SUDIMAGE group was to attack, by Markov random fields modelizations, two of the main celebrated “low level” image analysis task identified by David MARR :
- Continuous Contour Lines extraction
- Texture and Color Segmentation into homogeneous zones
These two problems have a natural duality, and we understood through various experiments and conceptual analyzis, that it was best to handle them in mutual interaction.
In collaboration with C. GRAFFIGNE, J.P. WANG, L. YOUNES, we introduced efficient combinations of Markov random fields models and local texture descriptors derived from Wavelet analysis and Fast Fourier Transform, to implement automatic segmentation of complex textures on aerial and satellite images, for 3 main types of image sensor acquisition : visible spectrum, radar ultrahigh frequency spectrum, infra-red spectrum.
The PhD thesis of J.P. WANG, under my direction, and with the active support of C. GRAFFIGNE and L. YOUNES attacked very efficiently the dual task of image segmentation into homogeneous regions with smooth boundaries.
Our Markov random fields approach used three types of smoothing constraints in the Gibbs global energy :
- “surface” terms forcing compactness and connectedness of image regions
- “line” terms forcing continuity and smoothness of regions boundaries
- “localization” terms forcing boundaries to live near high “texture contrasts” detected
by adequate local image filters
This fundamental discrete variational problem in image analysis was thus quite nicely mapped out, drawing on the concrete know-how of the whole SUDIMAGE group. J.P. WANG’s algorithmic tenacity combined with programming virtuosity led to a powerful “Markov random field” segmentation software which he and the SUDIMAGE group used in numerous further image analysis applications.
In R&D collaboration with the SAGEM corporation we then developed, on the basis of Gibbs energy minimization principles, a prototype scientific software for automatic “scene content reading” of scanned cartographic paper documents, such as Michelin roadmaps. This advanced project, jointly implemented in 18 months by R. AZENCOTT, C. GRAFFIGNE, F. COLDEFY, I. GAUDRON, J.F. YAO, had a strong technical impact on the industrial applications which the SAGEM R&D vision group was focusing on .
As in numerous other computerized image applications realized by my SUDIMAGE R&D group, through the PhD theses of J.P WANG, F. COLDEFY, J.F. YAO, et altri, the automatic “scene content reading” of Michelin standard roadmaps involved several overlapping mid-level vision tasks, dedicated to extraction of low-level “operational” scene elements such as :
- extraction of roads, rivers, vehicles, buildings, … on 2D satellite images
- extraction of printed characters on image documents
- extraction of connected texture defects in quality control by industrial cameras
- extraction of geological horizons on 2D sismic images
For this type of midlevel scene analyzis tasks, the low level dual tasks “texture segmentation / contour lines extraction” implemented a useful “smoothed out” and distributed extraction of locally consistent local visual features, each local feature potentially carrying a small but significant information.
But the midlevel tasks just listed required other types of mathematical concepts centering on automatic recognition of “shape signatures” regrouping “local features”. This became naturally one of my major scientific goals for the SUDIMAGE R&D group.
>>Back to Top
MARKOV RANDOM FIELDS AND 3D-OBJECTS RECONSTRUCTION
X-RAY TOMOGRAPHY AND ULTRASOUND SENSOR
Simultaneously, feeling that 3D Markov random field techniques were a powerful conceptual tool to smooth out local detections of 3D features, I launched with the SUDIMAGE group a series of exploratory R&D applications of 3D Markov random fields to the efficient spatial reconstruction of “matter density” distribution in opaque 3D-objects.
In practical terms, the physical “image” data were here acquired through sophisticated physical devices and sensors such as X-Ray tomography, Ultrasound sensors, Foucault currents.
Our intensive team scientific work (R. AZENCOTT, B. CHALMOND, F. COLDEFY, E. GOUBET, J.P. WANG) first enabled 3D Markov random field applications to multi-films X-Rays image restoration, as well as to reconstruction of small 3D “defects” within large opaque solids, by X-Ray tomography based on a very small number of X-Rays 2D-views.
Such 3D reconstruction problems arose at Centre d’Energie Atomique for plasma monitoring in scientific small scale “cold nuclear experiments”, or for in depth safety inspection of massive equipments, as well at Electricite de France (EDF) in the context of safety control for large equipments in electric production plants.
The corresponding inverse problem is here severely ill-posed, and to solve it correctly, one must impose “regularizing” constraints on the unknown 3D density distribution of matter. We showed that adequate pragmatic constraints can reasonably be implemented by ad hoc 3D Markov fields.
With the help of B. CHALMOND, I maintained a long term and very fruitful scientific collaboration with the R&D departments of EDF on these topics, beginning with support for the PhD thesis written by Francois COLDEFY under my direction. COLDEFY showed that Markov random fields were an efficient way of consistently patching together local “defects” informations extracted from small finite sets of X-Rays views of a 3D solid object.
In collaboration with EDF, we used similar, but technically much more complex relaxation methods, to reconstruct 3D defects on the basis of large datacubes recorded by industrial ultrasound sensors.
Concretized in the PhD thesis of E. GOUBET, with the intelligent and creative support of F. COLDEFY, our ultrasound methodology implied massive pretreatments by wavelet analysis along ultrasound main propagation rays, and Gibbs energy function modelization of desirable characteristics for 3D spatial distribution of defects. Actual 3D defects localization on connected compact sets of “voxels” was then achieved by stochastic relaxation to minimize the 3D energy function.
I naturally gave numerous graduate courses on Markov Random Fields and computer vision within the Paris Universities so called “DEA cursus”, and summarized our main advances in an invited advanced course for the 1995 International Summer School on Image Analysis organized by Henri MAITRE (Ecole Nationale Telecoms) at Les Houches France.
>>Back to Top
MARKOV RANDOM FIELDS AND COMPUTER VISION
As early as 1985, I clearly understood that research in artificial vision, crucially needed to preserve a good mix of rigorous mathematical theory and of intensive computer validations on concrete industrial applications to automatic image analysis and computer vision.
This required short-term R&D industrial collaborations and middle-term scientific partnerships with innovative large industrial companies and state subsidized institutions, as well as sizable financial support to buy and maintain adequate computing hardware, and to pay market level salaries for computing engineers and system engineers.
This led me in 1989, after three years of purely theoretical work, to create SUDIMAGE, a self-supported advanced consulting group in image analysis, gathering on a part-time basis a dozen of young Phds listed in the preceding paragraphs, most of them applied mathematicians then linked to CNRS, ENS Cachan, University of Paris 11, etc.
The initial cash investment of $ 10,000 was put up by myself, B. CHALMOND, and C. GRAFFIGNE, and the group then succeeded in completely self-subsidizing its intensive R&D developments until 1999.
As founder and scientific director of SUDIMAGE from 1989 to 1999, I had the constant sophisticated and dedicated support of three highly competent specialists in computer vision (B. CHALMOND, C. GRAFFIGNE, L. YOUNES), and thus led the realization of more than 30 advanced R&D industrial projects in applied image analysis, such as :
- 3D reconstruction : X-ray tomography with small number of views (EDF, CEA-DAM)
- 3D reconstruction : Ultrasound image analysis (EDF)
- 3D reconstruction : Foucault currents multi-images analysis (FRAMATOME)
- 3D reconstruction : Magnetic resonance MNR medical imaging (GENERAL ELECTRIC)
- Automated quality control through computer vision (PSA)
- Contour lines extraction and Satellite images segmentation (MATRA, SAGEM, MS2I)
- Texture wavelet analysis and segmentation for infra-red images (SEFT, SAT)
- Texture wavelet analysis and segmentation for radar images (CELAR)
- Patterns extraction in sismic images analysis for geological exploration (TOTAL, ELF)
- 2D shapes extraction in low level scene analysis (THOMSON,DASSAULT,AEROSPATIALE)
- 2D shapes recognition (CEA-DAM)
- 2D image content automatic indexation (ALCATEL)
Thus SUDIMAGE provided for 10 years a fertile and quite unusual opportunity for a group of talented french probabilists and applied mathematicians to apply daring and advanced new probabilistic approaches towards the solution of industrial problems in artificial vision.
>>Back to Top
|
