Markov Random Fields and Computer Vision

MARKOV FIELDS AND LOW LEVEL VISION TASKS
GIBBS SAMPLERS AND PARAMETER ESTIMATION
CONTOURS EXTRACTION AND TEXTURE SEGMENTATION

MARKOV FIELDS AND LOW LEVEL VISION TASKS
1984-1994

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 .
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.

GIBBS SAMPLERS AND PARAMETER ESTIMATION
1984-1994

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 this domain and many others.
With B. CHALMOND, C. GRAFFIGNE, I. GAUDRON, we also 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.

CONTOURS EXTRACTION AND TEXTURE SEGMENTATION
1984-1994

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, namely : Continuous Contour Lines extraction, Texture and Color Segmentation . These two problems have a natural duality, and we understood through various experiments and conceptual analysis, that it was best to handle them in mutual interaction. 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 JiaPing 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 region, “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. With SAGEM R&D, 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 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 the 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 roads, rivers, vehicles, buildings on 2D satellite images, printed characters on digitized paper maps, texture defects in quality control by industrial cameras, geological horizons on 2D sismic images. For midlevel scene analysis tasks, the low level dual tasks “texture segmentation / contour lines extraction” was 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.