8th IAPR - TC-15 Workshop on Graph-based Representations in Pattern Recognition
May 18-20, 2011
Münster (Germany)

Prof. Olivier Lezoray, University of Caen, France
Title: Partial Difference Equations (PdE) on Graphs for Image and Data Processing
Abstract: In image processing and computer vision, techniques based on energy minimization and Partial Differential Equations (PDEs) have shown their efficiency in solving many important problems, such as smoothing, denoising, interpolation and segmentation. Solutions of such problems can be obtained by considering the input discrete data as continuous functions defined on a continuous domain, and by designing continuous PDEs whose solutions are discretized in order to fit with the natural discrete domain. An alternative methodology to continuous PDEs-based regularization, is to formalize the problem directly in a discrete setting that is not necessarily a grid. However, PDE-based methods are difficult to adapt for data that live on non Euclidean domains since the discretization of the underlying differential operators is difficult for high dimensional data. Problems involving PDEs can be reduced to algebraic ones of a very much simpler structure by replacing the differentials by difference equations on graphs. As a consequence, it is possible to provide methods that mimic on graphs well-known PDE variational formulations under a functional analysis point of view. One way to tackle this is to use Partial difference Equations (PdE) over graphs. Conceptually, PdEs mimic PDEs in domains having a graph structure. Our proposed PdE framework unifies local and nolocal processing of images and allows most PDEs to be extended to graphs. In this talk, I will present nonlocal difference operators on graphs and will use the framework of PdEs to transcribe PDEs on graphs:

• a nonlocal discrete regularization on graphs as a framework for data simplification and interpolation,
• a formulation of mathematical morphology that considers a discrete version of PDEs-based approaches over weighted graphs,
• an adaptation of the Eikonal equation for data clustering and image segmentation.

This talk presents a joint work with A. Elmoataz.

Prof. Milan Sonka, University of Iowa, USA
Title: Graph Algorithmic Techniques for Biomedical Image Segmentation: LOGISMOS
Abstract : Accurate and reliable image segmentation is of paramount importance in medical image analysis. With a widespread use of 3D/4D imaging modalities like MR, MDCT, ultrasound, or OCT in routine clinical practice, physicians are faced with ever-increasing amounts of image data to analyze and quantitative outcomes of such analyses are increasingly important. Yet, daily interpretation of clinical images is still typically performed visually and qualitatively, with quantitative analysis being an exception rather than the norm. Since performing organ/object segmentations in 3D or 4D is infeasible for a human observer in clinical setting due to the time constraints, quantitative and highly automated analysis methods must be developed. Situation is similar when analyzing research animal images or biological images of living cells from microscopic images. Utilizing contextual information of mutually related surfaces and objects is hypothesized to increase segmentation robustness.
Our method for simultaneous segmentation of multiple interacting surfaces belonging to multiple interacting objects will be presented. The reported method is part of the family of graph-based image segmentation methods dubbed LOGISMOS for Layered Optimal Graph Image Segmentation of multiple Objects and Surfaces. This family of methods guarantees solution optimality with directly applicability to n-D problems. While LOGISMOS is generally applicable to a multitude of image segmentation problems, its utility and performance will be demonstrated on a knee-joint bone and cartilage segmentation task. The framework consists of the following main steps: 1) Shape model construction, 2) Pre-segmentation, 3) Cross-object surface mapping, 4) Multi-object, multi-surface graph construction, and 5) final segmentation and quantitative analysis. The functionality and performance of our method will be demonstrated in 3-D MR images of the knee joint originating from the NIH-supported Osteoarthritis Initiative Study. Additional applications of the methods to cardiovascular MR, pulmonary CT and ophthalmic OCT images will be presented demonstrating the broad applicability of the developed algorithmic concepts.