Metrics for 3D Rotations: Comparison and Analysis

3D rotations arise in many computer vision, computer graphics, and robotics problems and evaluation of the distance between two 3D rotations is often an essential task. This paper presents a detailed analysis of six functions for measuring distance between 3D rotations that have been proposed in the literature. Based on the well-developed theory behind 3D rotations, we demonstrate that five of them are bi-invariant metrics on SO(3) but that only four of them are boundedly equivalent to each other. We conclude that it is both spatially and computationally more efficient to use quaternions for 3D rotations. Lastly, by treating the two rotations as a true and an estimated rotation matrix, we illustrate the geometry associated with iso-error measures.

A Metric Approach to nD Images Edge Detection with Clifford Algebras

The aim of this paper is to perform edge detection in color-infrared images from the point of view of Clifford algebras. The main idea is that such an image can be seen as a section of a Clifford bundle associated to the RGBT-space (Red, Green, Blue, Temperature) of acquisition. Dealing with geometric calculus and covariant derivatives of appropriate sections with respect to well-chosen connections allows to get various color and temperature information needed for the segmentation. We show in particular how to recover the first fundamental form of the image embedded in a LSHT-space (Luminance, Saturation, Hue, Temperature) equipped with a metric tensor. We propose applications to color edge detection with some constraints on colors and to edge detection in color-infrared images with constraints on both colors and temperature. Other applications related to different choices of connections, sections and embedding spaces for nD images may be considered from this general theoretical framework.

Generating Segmented Quality Meshes from Images

Techniques devoted to generating triangular meshes from intensity images either take as input a segmented image or generate a mesh without distinguishing individual structures contained in the image. These facts may cause difficulties in using such techniques in some applications, such as numerical simulations. In this work we reformulate a previously developed technique for mesh generation from intensity images called Imesh. This reformulation makes Imesh more versatile due to an unified framework that allows an easy change of refinement metric, rendering it effective for constructing meshes for applications with varied requirements, such as numerical simulation and image modeling. Furthermore, a deeper study about the point insertion problem and the development of geometrical criterion for segmentation is also reported in this paper. Meshes with theoretical guarantee of quality can also be obtained for each individual image structure as a post-processing step, a characteristic not usually found in other methods. The tests demonstrate the flexibility and the effectiveness of the approach.

Stratified Self-Calibration and Metric Reconstruction for Zooming/Refocusing Circular Motion Sequences

Self-calibration for imaging sensors is essential to many computer vision applications. In this paper, a new stratified self-calibration and metric reconstruction method is proposed for zooming/refocusing cameras under circular motion. With the assumption of known rotation angles, the circular motion constraints are first formulated. By enforcing the constraints gradually, metric reconstruction is retrieved up to a two-parameter ambiguity. The closed form expression of the absolute conic w.r.t. the two parameters is deduced. The ambiguity is then resolved with the square pixel assumption of the camera. The advantages of this method are mainly as follows:

An Improved LOT Model for Image Restoration

Some second order PDE-based image restoration models such as total variation (TV) minimization or ROF model of Rudin et al. (Physica D 60, 259–268, 1992) can easily give rise to staircase effect, which may produce undesirable blocky image. LOT model proposed by Laysker, Osher and Tai (IEEE Trans. Image Process. 13(10), 1345–1357, 2004) has alleviated the staircase effect successfully, but the algorithms are complicated due to three nonlinear second-order PDEs to be computed, besides, when we have no information about the noise, the model cannot preserve edges or textures well. In this paper, we propose an improved LOT model for image restoration. First, we smooth the angle θ rather than the unit normal vector n, where n=(cos θ,sin θ). Second, we add an edge indicator function in order to preserve fine structures such as edges and textures well. And then the dual formulation of TV-norm and TV _g -norm are used in the numerical algorithms. Finally, some numerical experiments prove our proposed model and algorithms to be effective.

Transport of Relational Structures in Groups of Diffeomorphisms

This paper focuses on the issue of translating the relative variation of one shape with respect to another in a template centered representation. The context is the theory of Diffeomorphic Pattern Matching which provides a representation of the space of shapes of objects, including images and point sets, as an infinite dimensional Riemannian manifold which is acted upon by groups of diffeomorphisms. We discuss two main options for achieving our goal; the first one is the parallel translation, based on the Riemannian metric; the second one, based on the group action, is the coadjoint transport. These methods are illustrated with 3D experiments.

An Algorithm for Image Denoising with Automatic Noise Estimate

In this paper, we propose a general algorithm for image denoising when no a priori information on the noise is available. The image denoising problem is formulated as an inequality constrained minimization problem where the objective is a general convex regularization functional and the right-hand side of the constraint depends on the noise norm and is not known. The proposed method is an iterative procedure which, at each iteration, automatically computes both an approximation of the noise norm and an approximate solution of the minimization problem. Experimental results demonstrate the effectiveness of the proposed automatic denoising procedure.

Topological Repairing of 3D Digital Images

We present here a new randomized algorithm for repairing the topology of objects represented by 3D binary digital images. By “repairing the topology”, we mean a systematic way of modifying a given binary image in order to produce a similar binary image which is guaranteed to be well-composed. A 3D binary digital image is said to be well-composed if, and only if, the square faces shared by background and foreground voxels form a 2D manifold. Well-composed images enjoy some special properties which can make such images very desirable in practical applications. For instance, well-known algorithms for extracting surfaces from and thinning binary images can be simplified and optimized for speed if the input image is assumed to be well-composed. Furthermore, some algorithms for computing surface curvature and extracting adaptive triangulated surfaces, directly from the binary data, can only be applied to well-composed images. Finally, we introduce an extension of the aforementioned algorithm to repairing 3D digital multivalued images. Such an algorithm finds application in repairing segmented images resulting from multi-object segmentations of other 3D digital multivalued images.

A Lie-Group Formulation of Kinematics and Dynamics of Constrained MBS and Its Application to Analytical Mechanics

A Lie-group formulation for the kinematics and dynamics ofholonomic constrained mechanical systems (CMS) is presented. The kinematics ofrigid multibody systems (MBS) is described in terms of the screw system of theMBS. Using Lie-algebraic properties of screw algebra, isomorphicto se(3), allows a purely algebraic derivation of the Lagrangian motion equations. As such the Lie-group SE(3) ... SE(3) (n copies) is theambient space of a MBS consisting of n rigid bodies. Any parameterizationof the ambient space corresponds to a chart on the MBS configuration space ⁿ. The key to combine differential geometric and Lie-algebraic approaches is the existence of kinematic basic functions whichare push forward maps from the tangent bundle Tⁿ to the Lie-algebra of the ambient space.MBS with kinematic loops are CMS subject to holonomic constraints, holonomicCMS. Constraint equations are formulated on the ambient space based on achart on ⁿ. Explicitly considering the Lie-algebraicstructure of se(3) as semidirect sum of the algebra oftranslations and rotations enables to reduce the number of holonomicconstraints for cut joints. It is shown that third order Lie-brackets are sufficient to obtain any subalgebra of se(3).Differential geometric aspects of the kinematics of MBS with open and closedkinematic chains are considered. The distribution in any configuration andthe subalgebra generated by the screw system of a mechanism is the key todetect singularities and to analyze the structure of the set of singularpoints.     

Scalable landmark recognition using EXTENT

We have proposed the EXTENT system for automated photograph annotation using image content and context analysis. A key component of EXTENT is a Landmark recognition system called LandMarker. In this paper, we present the architecture of LandMarker. The content of a query photograph is analyzed and compared against a database of sample landmark images, to recognize any landmarks it contains. An algorithm is presented for comparing a query image with a sample image. Context information may be used to assist landmark recognition. Also, we show how LandMarker deals with scalability to allow recognition of a large number of landmarks. We have implemented a prototype of the system, and present empirical results on a large dataset.

Real-time image segmentation based on a parallel and pipelined watershed algorithm

The watershed transformation is a popular image segmentation technique for gray scale images. This paper describes a real-time image segmentation based on a parallel and pipelined watershed algorithm which is designed for hardware implementation. In our algorithm: (1) pixels in a given image are repeatedly scanned from top-left to bottom-right, and then from bottom-right to top-left, in order to achieve high performance on a pipelined circuit by simplifying memory access sequences, (2) all steps in the algorithm are executed at the same time in the pipelined circuit, (3) the amount of data that are scanned is gradually reduced as the calculation progresses by memorizing which data are modified in the previous scan, and (4) N pixels can be processed in parallel. In our current implementation on an off-the-shelf field-programmable gate array board, up to four pixels can be processed in parallel. The performance for 512 × 512 pixel images is fast enough to be the first step in real-time applications.

Geodesic Gaussian kernels for value function approximation

The least-squares policy iteration approach works efficiently in value function approximation, given appropriate basis functions. Because of its smoothness, the Gaussian kernel is a popular and useful choice as a basis function. However, it does not allow for discontinuity which typically arises in real-world reinforcement learning tasks. In this paper, we propose a new basis function based on geodesic Gaussian kernels, which exploits the non-linear manifold structure induced by the Markov decision processes. The usefulness of the proposed method is successfully demonstrated in simulated robot arm control and Khepera robot navigation.

Fast and accurate map merging for multi-robot systems

We present a new algorithm for merging occupancy grid maps produced by multiple robots exploring the same environment. The algorithm produces a set of possible transformations needed to merge two maps, i.e translations and rotations. Each transformation is weighted, thus allowing to distinguish uncertain situations, and enabling to track multiple cases when ambiguities arise. Transformations are produced extracting some spectral information from the maps. The approach is deterministic, non-iterative, and fast. The algorithm has been tested on public available datasets, as well as on maps produced by two robots concurrently exploring both indoor and outdoor environments. Throughout the experimental validation stage the technique we propose consistently merged maps exhibiting very different characteristics.

Convex Hodge Decomposition and Regularization of Image Flows

The total variation (TV) measure is a key concept in the field of variational image analysis. In this paper, we focus on vector-valued data and derive from the Hodge decomposition of image flows a definition of TV regularization for vector-valued data that extends the standard componentwise definition in a natural way. We show that our approach leads to a convex decomposition of arbitrary vector fields, providing a richer decomposition into piecewise harmonic fields rather than piecewise constant ones, and motion texture. Furthermore, our regularizer provides a measure for motion boundaries of piecewise harmonic image flows in the same way, as the TV measure does for contours of scalar-valued piecewise constant images.

The partitioned dynamic-priority scheduling of sporadic task systems

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal. A quantitative characterization of its worst-case performance is provided in terms of resource augmentation.

On a Method of Paired Representation: Enhancement and Decomposition by Series Direction Images

In the paired representation, a two-dimensional (2-D) image is represented uniquely by a complete set of 1-D signals, so-called splitting-signals, that carry the spectral information of the image at frequency-points of specific subsets that divide the whole domain of frequencies. Image processing can thus be reduced to processing of splitting-signals and such process requires a modification of only a few spectral components of the image, for each signal. For instance, the α-rooting method of image enhancement can be fulfilled through processing one or a few splitting-signals. Such process can even be accomplished without computing the 2-D Fourier transforms of the original and enhanced images. To show that, we present an effective formula for inverse 2-D N×N-point paired transform, where N is a power of 2. The representation of the image and 2-D DFT by paired splitting-signals leads to the new concepts of direction and series images, that define the resolution and periodic structures of the image components, which can be packed in the form of the “resolution map” of the size of the image. Simple method of image enhancement by series images is described.

基于黎曼流形的平面目标识别

平面目标识别中的几何形变可用射影变换群描述. 与紧致李群SO(n, R)不同, 正则化的射影变换群, 即非紧致李群SL(n, R)上由黎曼度量决定的黎曼指数映射不同于由单参数子群决定的李群指数映射. 基于黎曼流形优化算法得到取值于特殊线性群SL(3, R)的样本的内蕴均值和协方差矩阵, 并依此构建李群正态分布. 利用此先验知识, 根据贝叶斯定理进行简单背景下的平面目标的识别实验. 结果表明, 利用射影变换群的统计特性可有效提高平面目标识别的成功率.     

Spatial Query Estimation without the Local Uniformity Assumption

Existing estimation approaches for spatial databases often rely on the assumption that data distribution in a small region is uniform, which seldom holds in practice. Moreover, their applicability is limited to specific estimation tasks under certain distance metric. This paper develops the Power-method, a comprehensive technique applicable to a wide range of query optimization problems under both L_∞ and L₂ metrics. The Power-method eliminates the local uniformity assumption and is, therefore, accurate even for datasets where existing approaches fail. Furthermore, it performs estimation by evaluating only one simple formula with minimal computational overhead. Extensive experiments confirm that the Power-method outperforms previous techniques in terms of accuracy and applicability to various optimization scenarios.

(Φ,Φ<Superscript>*</Superscript>) Image Decomposition Models and Minimization Algorithms

We propose in this paper minimization algorithms for image restoration using dual functionals and dual norms. In order to extract a clean image u from a degraded version f=Ku+n (where f is the observation, K is a blurring operator and n represents additive noise), we impose a standard regularization penalty Φ(u)=∫ φ(|Du|)dx<∞ on u, where φ is positive, increasing and has at most linear growth at infinity. However, on the residual f−Ku we impose a dual penalty Φ^*(f−Ku)<∞, instead of the more standard fidelity term. In particular, when φ is convex, homogeneous of degree one, and with linear growth (for instance the total variation of u), we recover the (BV,BV ^*) decomposition of the data f, as suggested by Y. Meyer (Oscillating Patterns in Image Processing and Nonlinear Evolution Equations, University Lecture Series, vol. 22, Am. Math. Soc., Providence, 2001). Practical minimization methods are presented, together with theoretical, experimental results and comparisons to illustrate the validity of the proposed models. Moreover, we also show that by a slight modification of the associated Euler-Lagrange equations, we obtain well-behaved approximations and improved results.

A Fourier Domain Framework for Variational Image Registration

Vector fields arise in many problems of computer vision, particularly in non-rigid registration. In this paper, we develop coupled partial differential equations (PDEs) to estimate vector fields that define the deformation between objects, and the contour or surface that defines the segmentation of the objects as well. We also explore the utility of inequality constraints applied to variational problems in vision such as estimation of deformation fields in non-rigid registration and tracking. To solve inequality constrained vector field estimation problems, we apply tools from the Kuhn-Tucker theorem in optimization theory. Our technique differs from recently popular joint segmentation and registration algorithms, particularly in its coupled set of PDEs derived from the same set of energy terms for registration and segmentation. We present both the theory and results that demonstrate our approach.