We study the centroid with respect to the class of information-theoretic Burbea-Rao divergences that generalize the celebrated Jensen-Shannon divergence by measuring the non-negative Jensen difference induced by a strictly convex and differentiable function. Although those Burbea-Rao divergences are symmetric by construction, they are not metric since they fail to satisfy the triangle inequality. We first explain how a particular symmetrization of Bregman divergences called Jensen-Bregman distances yields exactly those Burbea-Rao divergences. We then proceed by defining skew Burbea-Rao divergences, and show that skew Burbea-Rao divergences amount in limit cases to compute Bregman divergences. We then prove that Burbea-Rao centroids can be arbitrarily finely approximated by a generic iterative concave-convex optimization algorithm with guaranteed convergence property. In the second part of the paper, we consider the Bhattacharyya distance that is commonly used to measure overlapping degree of probability distributions. We show that Bhattacharyya distances on members of the same statistical exponential family amount to calculate a Burbea-Rao divergence in disguise. Thus we get an efficient algorithm for computing the Bhattacharyya centroid of a set of parametric distributions belonging to the same exponential families, improving over former specialized methods found in the literature that were limited to univariate or “diagonal” multivariate Gaussians. To illustrate the performance of our Bhattacharyya/Burbea-Rao centroid algorithm, we present experimental performance results fork-means and hierarchical clustering methods of Gaussian mixture models.

Motion estimation is known to be a non-convex optimization problem. This non-convexity comes from several ambiguities in motion estimation such as the aperture problem, or fast motion relative to the magnitude of the image gradient. In this paper, we propose a fast random search algorithm to estimate motion. Randomized algorithms are very popular in computer science and optimization for non-convex problems. However, to the best of our knowledge none has been used so far for motion estimation, due to complexity constraints. In this paper, we propose two fast algorithms to perform random search on image pixels. One produces a dense optical flow by matching patches. The other one takes advantage of a quad tree or segmentation tree structure of the image to estimate motion in regions of increasing size. Quantitative and visual results show that the motion obtained seems to be a very advantageous compromise between speed and quality of estimated motion.

Earth Mover Distance (EMD) is a popular distance to compute distances between Probability Density Functions (PDFs). It has been successfully applied in a wide selection of problems of image processing. This success comes from two reasons, a physical one, since it computes a physical cost to transport an element of mass between two images or two histograms, and a statistical one, since it is a cross-bin metric (as opposed to a bin-wise metric). In computer vision, these features are useful since small variation of illuminance can shift the histogram. However, histograms are not a sufficient statistic to discriminate images since they ignore all geometric correlations. In addition, transport also called flow of an histogram loose the information of geometric flow to warp one image on to an other. This paper proposes a new construction of EMD between images. This construction approximates the EMD between two images, by computing a pixel-wise transport at the complexity cost of computing an EMD between 1-D Histograms and preserves the geometrical and topological structure of the image. This construction simply relies on a segmentation of the image (also called superpixelization of the image). Results on matching on images shows the stability of the method even when the superpixelizations are highly inconsistent across images.

Bhattacharrya distance (BD) is a widely used distance in statistics to compare probability density functions (PDFs). It has shown strong statistical properties (in terms of Bayes error) and it relates to Fisher information. It has also practical advantages, since it strongly relates on measuring the overlap of the supports of the PDFs. Unfortunately, even with common parametric models on PDFs, few closed-form formulas are known. Moreover, the BD centroid estimation was limited to univariate gaussian PDFs in the literature and no convergence guarantees were provided. In this paper, we propose a closed-form formula for BD on a general class of parametric distributions named exponential families. We show that the BD is a Burbea-Rao divergence for the log normalizer of the exponential family. We propose an efficient iterative scheme to compute a BD centroid on exponential families. Finally, these results allow us to define a Bhattacharrya hierarchical clustering algorithms (BHC). It can be viewed as a generalization of k-means on BD. Results on image segmentation shows the stability of the method.

This paper deals with region-of-interest (ROI) tracking in video sequences. The goal is to determine in successive frames the region which best matches, in terms of a similarity measure, a ROI defined in a reference frame. Some tracking methods define similarity measures which efficiently combine several visual features into a probability density function (PDF) representation, thus building a discriminative model of the ROI. This approach implies dealing with PDFs with domains of definition of high dimension. To overcome this obstacle, a standard solution is to assume independence between the different features in order to bring out low-dimension marginal laws and/or to make some parametric assumptions on the PDFs at the cost of generality. We discard these assumptions by proposing to compute the Kullback-Leibler divergence between high-dimensional PDFs using the k th nearest neighbor framework. In consequence, the divergence is expressed directly from the samples, i.e., without explicit estimation of the underlying PDFs. As an application, we defined 5, 7, and 13-dimensional feature vectors containing color information (including pixel-based, gradient-based and patch-based) and spatial layout. The proposed procedure performs tracking allowing for translation and scaling of the ROI. Experiments show its efficiency on a movie excerpt and standard test sequences selected for the specific conditions they exhibit: partial occlusions, variations of luminance, noise, and complex motion.

This paper deals with region-of-interest (ROI) tracking in video sequences. The goal is to determine in successive frames the region which best matches, in terms of a similarity measure, an ROI defined in a reference frame. Two aspects of a similarity measure between a reference region and a candidate region can be distinguished: radiometry which checks if the regions have similar colors and geometry which checks if these colors appear at the same location in the regions. Measures based solely on radiometry include distances between probability density functions (PDF) of color. The absence of geometric constraint increases the number of potential matches. A soft geometric constraint can be added to a PDF-based measure by enriching the color information with location, thus increasing the dimension of the domain of definition of the PDFs. However, high-dimensional PDF estimation is not trivial. Instead, we propose to compute the Kullback-Leibler distance between high-dimensional PDFs without explicitly estimating the PDFs. The distance is expressed directly from the samples using the k-th nearest neighbor framework. Tracking experiments were performed on several standard sequences.

This paper deals with region-of-interest (ROI) segmentation in video sequences. The goal is to determine in successive frames the region which best matches, in terms of a similarity measure, a ROI defined in a reference frame. Color and geometry can be combined in a joint PDF. However such high-dimensional PDFs being hard to estimate, measures based on PDF distances may lead to incorrect segmentations. Here, we propose to use an estimate of the Kullback-Leibler divergence adapted to high-dimensional PDFs. It is defined from the samples using the kth-nearest neighbor (kNN) framework and it is differentiated for active contour implementation and expressed in both the continuous form and a kNN form. Results are presented on standard sequences.

Tracking can be achieved using region active contours based on homogeneity models (intensity, motion...). However the model complexity necessary to achieve a given accuracy might be prohibitive. Methods based on salient points may not extract enough of these for reliable motion estimation if the object is too homogeneous. Here we propose to compute the contour deformation based on its neighborhood. Motion estimation is performed at contour samples using a block matching approach. First, partial background masking is applied. Since outliers may then bias the motion estimation, a robust, nonparametric estimation using entropy as a similarity measure between blocks is proposed. Tracking results on synthetic and natural sequences are presented.

We focus on motion estimation using a block matching approach and suggest using a minimum-entropy criterion. Many entropy-based estimation procedures exist, such as plug-in estimators based on Parzen windowing. We consider here an alternative that is applicable to data of any dimension and that circumvents the critical issues raised by kernel-based methods. To the best of our knowledge, this criterion has not yet been considered for image processing problems. The inherent robustness property of entropy is expected to provide a robust and efficient estimation of the motion vector of a block of a video sequence. In particular, the minimum-entropy estimator should be robust to occlusions and variations of luminance, for which standard approaches like SSD usually meet their limitations.

This paper deals with motion estimation and segmentation in video sequences. Some methods of motion computation between two consecutive frames of a video sequence are based on the minimization of the square error of the prediction error. More robust estimators such as absolute value or M-estimators were proposed but these estimators loose their efficiency when the data do not have parametric distributions. We relax the parametric assumption on the prediction error distribution and propose to use a nonparametric estimator for the motion estimation : the entropy of the prediction error. We use the same criterion to perform a spatio-temporal segmentation of the sequence using an active contour algorithm. Segmentation and tracking tests on a textured synthetic and a real sequence, compared to a standard method in motion segmentation, tends to show that our method is more stable and accurate.