Emerging Trends in Visual Computing

We list the abstracts of the distinguished speakers that participated to the 2008 LIX fall colloquium.

This paper surveys Delaunay-based meshing techniques for curved objects, and their application in medical imaging and in computer vision to the extraction of geometric models from segmented images. We show that the so-called Delaunay refinement technique allows to mesh surfaces and volumes bounded by surfaces, with theoretical guarantees on the quality of the approximation, from a geometrical and a topological point of view. Moreover, it offers extensive control over the size and shape of mesh elements, for instance through a (possibly non-uniform) sizing field. We show how this general paradigm can be adapted to produce anisotropic meshes, i.e. meshes elongated along prescribed directions. Lastly, we discuss extensions to higher dimensions, and especially to space-time for producing time-varying 3D models. This is also of interest when input images are transformed into data points in some higher dimensional space as is common practice in machine learning.

Intrinsic curvature flows can be used to design Riemannian metrics by prescribed curvatures. This chapter presents three discrete curvature flow methods that are recently introduced into the engineering fields: the discrete Ricci flow and discrete Yamabe flow for surfaces with various topology, and the discrete curvature flow for hyperbolic 3-manifolds with boundaries. For each flow, we introduce its theories in both the smooth setting and the discrete setting, plus the numerical algorithms to compute it. We also provide a brief survey on their history and their link to some of the engineering applications in computer graphics, computer vision, medical imaging, computer aided design and others.

Information geometry emerged from studies on invariant properties of a manifold of probability distributions. It includes convex analysis and its duality as a special but important part. Here, we begin with a convex function, and construct a dually flat manifold. The manifold possesses a Riemannian metric, two types of geodesics, and a divergence function. The generalized Pythagorean theorem and dual projections theorem are derived therefrom. We construct alpha-geometry, extending this convex analysis. In this review, geometry of a manifold of probability distributions is then given, and a plenty of applications are touched upon. Appendix presents an easily understable introduction to differential geometry and its duality.

In this paper, we consider Voronoi diagrams from the view point of affine differential geometry. A main object of affine differential geometry is to study hypersurfaces in an affine space that are invariant under the action of the group of affine transformations. Since incidence relations (configurations of vertexes, edges, etc.) in computational geometry are invariant under affine transformations, we may say that affine differential geometry gives a new sight in computational geometry.

The Euclidean distance function can be generalized by a divergence function in affine differential geometry. For such divergence functions, we show that Voronoi diagrams on statistical manifolds are invariant under ( − 1)-conformal transformations. We then give some typical figures of Voronoi diagrams on a manifold. These figures may give good intuition for Voronoi diagrams on a manifold because the figures or constructing algorithms on a manifold strongly depend on the realization or on the choice of local coordinate systems. We also consider the upper envelope type theorems on statistical manifolds, and give a constructing algorithm of Voronoi diagrams on ( − 1)-conformally flat statistical manifolds.

Main issue of High Resolution Doppler Imagery is related to robust statistical estimation of Toeplitz Hermitian positive definite covariance matrices of sensor data time series (e.g. in Doppler Echography, in Underwater acoustic, in Electromagnetic Radar, in Pulsed Lidar...). We consider this problem jointly in the framework of Riemannian symmetric spaces and the framework of Information Geometry. Both approaches lead to the same metric, that has been initially considered in other mathematical domains (study of Bruhat-Tits complete metric Space and Upper-half Siegel Space in Symplectic Geometry). Based on Frechet-Karcher barycenter definition and geodesics in Bruhat-Tits space, we address problem of N Covariance matrices Mean estimation. Our main contribution lies in the development of this theory for Complex Autoregressive models (maximum entropy solution of Doppler Spectral Analysis). Specific Blocks structure of the Toeplitz Hermitian covariance matrix is used to define an iterative and parallel algorithm for Siegel metric computation. Based on Affine Information Geometry theory, we introduce for Complex Autoregressive Model, Kähler metric on reflection coefficients based on Kähler potential function given by Doppler signal Entropy. The metric is closely related to Kähler-Einstein manifold and complex Monge-Ampere Equation. Finally, we study geodesics in space of Kähler potentials and action of Calabi and Kähler-Ricci Geometric Flows for this Complex Autoregressive Metric. We conclude with different results obtained on real Doppler Radar Data in HF and X bands : X-band radar monitoring of wake vortex turbulences, detection for Coastal X-band and HF Surface Wave Radars.

In this paper, we consider the task of clustering multivariate normal distributions with respect to the relative entropy into a prescribed number, k, of clusters using a generalization of Lloyd’s k-means algorithm [1]. We revisit this information-theoretic clustering problem under the auspices of mixed-type Bregman divergences, and show that the approach of Davis and Dhillon [2] (NIPS*06) can also be derived directly, by applying the Bregman k-means algorithm, once the proper vector/matrix Legendre transformations are defined. We further explain the dualistic structure of the sided k-means clustering, and present a novel k-means algorithm for clustering with respect to the symmetrical relative entropy, the J-divergence.Our approach extends to differential entropic clustering of arbitrary members of the same exponential families in statistics.

Computational photography combines plentiful computing, digital sensors, modern optics, actuators, and smart lights to escape the limitations of traditional cameras, enables novel imaging applications and simplifies many computer vision tasks. However, a majority of current Computational photography methods involves taking multiple sequential photos by changing scene parameters and fusing the photos to create a richer representation. Epsilon photography is concerned with synthesizing omnipictures and proceeds by multiple capture single image paradigm (MCSI).The goal of Coded computational photography is to modify the optics, illumination or sensors at the time of capture so that the scene properties are encoded in a single (or a few) photographs. We describe several applications of coding exposure, aperture, illumination and sensing and describe emerging techniques to recover scene parameters from coded photographs.

This chapter surveys recent progress in constant-working-space algorithms for problems related to image processing. An extreme case is when an input image is given as read-only memory in which reading an array element is allowed but writing any value at any array element is prohibited, and also the number of working storage cells available for algorithms is at most some constant. This chapter shows how a number of important fundamental problems can be solved in such a highly constrained situation.

This paper presents a framework to define an objective measure of the similarity (or dissimilarity) between two images for image processing. The problem is twofold: 1) define a set of features that capture the information contained in the image relevant for the given task and 2) define a similarity measure in this feature space.

This framework is applied to a query-by-example image retrieval task. Experiments on two publicly available databases showed the potential of our SMP approach. In particular, it performed comparably to a SIFT-based retrieval method and two versions of a fuzzy segmentation-based method (the UFM and CLUE methods), and it exhibited some robustness to different geometric and radiometric deformations of the images.

This paper introduces recent methods for large scale image search. State-of-the-art methods build on the bag-of-features image representation. We first analyze bag-of-features in the framework of approximate nearest neighbor search. This shows the sub-optimality of such a representation for matching descriptors and leads us to derive a more precise representation based on 1) Hamming embedding (HE) and 2) weak geometric consistency constraints (WGC). HE provides binary signatures that refine the matching based on visual words. WGC filters matching descriptors that are not consistent in terms of angle and scale. HE and WGC are integrated within an inverted file and are efficiently exploited for all images, even in the case of very large datasets. Experiments performed on a dataset of one million of images show a significant improvement due to the binary signature and the weak geometric consistency constraints, as well as their efficiency. Estimation of the full geometric transformation, i.e., a re-ranking step on a short list of images, is complementary to our weak geometric consistency constraints and allows to further improve the accuracy.

Concepts from Information Theory have been used quite widely in Image Processing, Computer Vision and Medical Image Analysis for several decades now. Most widely used concepts are that of KL-divergence, minimum description length (MDL), etc. These concepts have been popularly employed for image registration, segmentation, classification etc. In this chapter we review several methods, mostly developed by our group at the Center for Vision, Graphics & Medical Imaging in the University of Florida, that glean concepts from Information Theory and apply them to achieve analysis of Diffusion-Weighted Magnetic Resonance (DW-MRI) data.

This relatively new MRI modality allows one to non-invasively infer axonal connectivity patterns in the central nervous system. The focus of this chapter is to review automated image analysis techniques that allow us to automatically segment the region of interest in the DWMRI image wherein one might want to track the axonal pathways and also methods to reconstruct complex local tissue geometries containing axonal fiber crossings. Implementation results illustrating the algorithm application to real DW-MRI data sets are depicted to demonstrate the effectiveness of the methods reviewed.

Computational anatomy is an emerging discipline that aims at analyzing and modeling the individual anatomy of organs and their biological variability across a population. The goal is not only to model the normal variations among a population, but also discover morphological differences between normal and pathological populations, and possibly to detect, model and classify the pathologies from structural abnormalities. Applications are very important both in neuroscience, to minimize the influence of the anatomical variability in functional group analysis, and in medical imaging, to better drive the adaptation of generic models of the anatomy (atlas) into patient-specific data (personalization).

However, understanding and modeling the shape of organs is made difficult by the absence of physical models for comparing different subjects, the complexity of shapes, and the high number of degrees of freedom implied. Moreover, the geometric nature of the anatomical features usually extracted raises the need for statistics and computational methods on objects that do not belong to standard Euclidean spaces. We investigate in this chapter the Riemannian metric as a basis for developing generic algorithms to compute on manifolds. We show that few computational tools derived from this structure can be used in practice as the atoms to build more complex generic algorithms such as mean computation, Mahalanobis distance, interpolation, filtering and anisotropic diffusion on fields of geometric features. This computational framework is illustrated with the joint estimation and anisotropic smoothing of diffusion tensor images and with the modeling of the brain variability from sulcal lines.