Jérôme Darbon

Global optimization for first order Markov random fields with submodular priors

Abstract

This paper copes with the optimization of Markov Random Fields with pairwise interactions defined on arbitrary graphs. The set of labels is assumed to be linearly ordered and the priors are supposed to be submodular. Under these assumptions we propose an algorithm which computes an exact minimizer of the Markovian energy. Our approach relies on mapping the original into a combinatorial one which involves only binary variables. The latter is shown to be exactly solvable via computing a maximum flow. The restatement into a binary combinatorial problem is done by considering the level-sets of the labels instead of the label values themselves. The submodularity of the priors is shown to be a necessary and sufficient condition for the applicability of the proposed approach.

Continue reading

A note on the discrete binary Mumford-Shah model

Abstract

This paper is concerned itself with the analysis of the two-phase Mumford-Shah model also known as the active contour without edges model introduced by Chan and Vese. It consists of approximating an observed image by a piecewise constant image which can take only two values. First we show that this model with the $L^1$-norm as data fidelity yields a contrast invariant filter which is a well known property of morphological filters. Then we consider a discrete version of the original problem. We show that an inclusion property holds for the minimizers. The latter is used to design an efficient graph-cut based algorithm which computes an exact minimizer. Some preliminary results are presented.

Continue reading

The biosecure geometry-based system for hand modality

Abstract

We present an identification and authentification system based on hand modality which is part of a reference system for all modalities developed within the Biosecure consortium. It relies on simple geometric features extracted from hand boundary. The different steps of this system are detailed, namely: pre-processing, feature extraction and hand matching. This system has been tested on the Biosecure hand database which consists of 4500 hand images of 750 individuals. Results are detailed with respect to different enrolment conditions such as population size, enrolment size, and image resolution.

Continue reading

The use of levelable regularization functions for MRF restoration of SAR images

Abstract

It is well-known that Total Variation (TV) minimization with L2 data fidelity terms (which corresponds to white Gaussian additive noise) yields a restored image which presents some loss of contrast. The same behavior occurs for TVmodels with non-convex data fidelity terms that represent speckle noise. In this note we propose a new approach to cope with the restoration of Synthetic Aperture Radar images while preserving the contrast.

Continue reading

A note on nice-levelable MRFs for SAR image denoising with contrast preservation

Abstract

Continue reading

An efficient algorithm for connected attribute thinnings and thickenings

Abstract

Connected attribute filters are anti-extensive morphological operators widely used for their ability of simplifying the image without moving its contours. In this paper, we present a fast, versatile and easy-to-implement algorithm for grayscale connected attribute thinnings and thickennings, a subclass of connected filters for the wide range of non-increasing attributes. We show that our algorithm consumes less memory and is computationally more efficient than other available methods on natural images.

Continue reading

Approximate probabilistic model checking for programs

Abstract

In this paper we deal with the problem of applying model checking to real programs. We verify a program without constructing the whole transition system using a technique based on Monte-Carlo sampling, also called “approximate model checking”. This technique combines model checking and randomized approximation. Thus, it avoids the so called state space explosion phenomenon. We propose a prototype implementation that works directly on C source code. It means that, contrary to others approaches, we do not need to use a specific language nor specific data structures in order to describe the system we wish to verify. Finally, we present experimental results that show the effectiveness of the approach applied to finding bugs in real programs.

Continue reading

Shape-based hand recognition

Abstract

The problem of person recognition and verification based on their hand images has been addressed. The system is based on the images of the right hands of the subjects, captured by a flatbed scanner in an unconstrained pose at 45 dpi. In a preprocessing stage of the algorithm, the silhouettes of hand images are registered to a fixed pose, which involves both rotation and translation of the hand and, separately, of the individual fingers. Two feature sets have been comparatively assessed, Hausdorff distance of the hand contours and independent component features of the hand silhouette images. Both the classification and the verification performances are found to be very satisfactory as it was shown that, at least for groups of about five hundred subjects, hand-based recognition is a viable secure access control scheme.

Continue reading

On a polynomial vector field model for shape representation

Abstract

In this paper we propose an efficient algorithm to perform a polynomial approximation of the vector field derived from the usual distance mapping method. The main ingredients consist of minimizing a quadratic functional and transforming this problem in an appropriate setting for implementation. With this approach, we reduce the problem of obtaining an approximating polynomial vector field to the resolution of a not expansive linear algebraic system. By this procedure, we obtain an analytical shape representation that relies only on some coefficients. Fidelity and numerical efficiency of our approach are presented on illustrative examples.

Continue reading

Image restoration with discrete constrained Total Variation—part I: Fast and exact optimization

Abstract

This paper deals with the total variation minimization problem in image restoration for convex data fidelity functionals. We propose a new and fast algorithm which computes an exact solution in the discrete framework. Our method relies on the decomposition of an image into its level sets. It maps the original problems into independent binary Markov Random Field optimization problems at each level. Exact solutions of these binary problems are found thanks to minimum cost cut techniques in graphs. These binary solutions are proved to be monotone increasing with levels and yield thus an exact solution of the discrete original problem. Furthermore we show that minimization of total variation under $L^1$ data fidelity term yields a self-dual contrast invariant filter. Finally we present some results.

Continue reading