3D object recognition using invariants of 2D projection curves

This paper presents a new method for recognizing 3D objects based on the comparison of invariants of their 2D projection curves. We show that Euclidean equivalent 3D surfaces imply affine equivalent 2D projection curves that are obtained from the projection of cross-section curves of the surfaces onto the coordinate planes. Planes used to extract cross-section curves are chosen to be orthogonal to the principal axes of the defining surfaces. Projection curves are represented using implicit polynomial equations. Affine algebraic and geometric invariants of projection curves are constructed and compared under a variety of distance measures. Results are verified by several experiments with objects from different classes and within the same class.     

Application of REDUCE-2 algebraic manipulation system in calibration problems of track chamber picture processing devices

The problem is considered of correcting nonlinear coordinate distortions generated by cathode ray tube scanner. Orthogonal bivariate polynomials are used to solve the computational part of this problem. The symbolic algebraic algorithm, proposed for the evaluation of orthogonal polynomials, is performed by the REDUCE-2 algebraic manipulation system.     

Using symbolic computation to find algebraic invariants

Implicit polynomials have proved themselves as having excellent representation power for complicated objects, and there is growing use of them in computer vision, graphics, and CAD. A must for every system that tries to recognize objects based on their representation by implicit polynomials are invariants, which are quantities assigned to polynomials that do not change under coordinate transformations. In the recognition system developed at the Laboratory for Engineering Man-Machine Studies in Brown University (LEMS), it became necessary to use invariants which are explicit and simple functions of the polynomial coefficients. A method to find such invariants is described and the new invariants presented. This work addresses only the problem of finding the invariants; their stability is studied in another paper     

An integrated approach for range image segmentation and representation

This paper proposes an efficient method for the segmentation and representation of 3D rigid, solid objects from its range images using differential invariants derived from classical differential geometry. An efficient algorithm for derivation of surface curvatures, which are affine invariants, at smooth surface patches is proposed. The surface is approximated by Bezier and Beta-splines to compare qualitatively the proposed segmentation scheme. This scheme leads to derivation of surface features, which provides a very robust surface segmentation. An integrated approach represents the surface in terms of plane, quadric and superquadric surface.Experiments show excellent performance and together with the inherent parallelism make the scheme a promising one. Present experiments were conducted on some real range images where most of the parts of the object are planar.     

隐含多项式曲线曲面拟合次数的确定研究

选用合适次数的隐含多项式曲线曲面描述目标物体是处理和识别目标物体的关键,因而需要在理论上解决隐含多项式曲线或者曲面的次数确定问题.根据目标物体本身的特征,从理论上得出隐含多项式曲线描述物体的次数确定定理,并给出了具体计算公式.该方法首先由给定物体边界的轮廓检测出其驻点数,然后根据驻点数得到拟合隐含多项式曲线方程次数的下界,进而推广到三维物体的隐含多项式曲面拟合次数的确定.最后给出的应用实例进一步验证了算法的有效性与可操作性.     

An automatic method for generating affine moment invariants

Affine moment invariants are important if one wants to recognize the surface of a plane in three dimensions when the orientation of the plane is not known beforehand and only two-dimensional information is available. The notion of generating function is introduced as a simple and straightforward way to derive various affine invariants. By this notion, we can get the explicit construction of much more affine moment invariants. Based on this conclusion, a large set of invariant polynomials can be generated automatically and immediately by the algorithm we have designed. These new affine moment invariants can be applied to recognize the image. Approaches in this paper will improve the practicability of affine invariants in object recognition applications.     

Geometric Moments and Their Invariants

Moments and their invariants have been extensively used in computer vision and pattern recognition. There is an extensive and sometimes confusing literature on the computation of a basis of functionally independent moments up to a given order. Many approaches have been used to solve this problem albeit not entirely successfully. In this paper we present a (purely) matrix algebra approach to compute both orthogonal and affine invariants for planar objects that is ideally suited to both symbolic and numerical computation of the invariants. Furthermore we generate bases for both systems of invariants and, in addition, our approach generalises to higher dimensional cases.     

Fast Ray Tracing of Arbitrary Implicit Surfaces with Interval and Affine Arithmetic

Existing techniques for rendering arbitrary-form implicit surfaces are limited, either in performance, correctness or flexibility. Ray tracing algorithms employing interval arithmetic (IA) or affine arithmetic (AA) for root-funding are robust and general in the class of surfaces they support, but traditionally slow. Nonetheless, implemented efficiently using a stack-driven iterative algorithm and SIMD vector instructions, these methods can achieve interactive performance for common algebraic surfaces on the CPU. A similar algorithm can also be implemented stacklessly, allowing for efficient ray tracing on the GPU. This paper presents these algorithms, as well as an inclusion-preserving reduced affine arithmetic (RAA) for faster ray-surface intersection. Shader metaprogramming allows for immediate and automatic generation of symbolic expressions and their interval or affine extensions. Moreover, we are able to render even complex forms robustly, in real-time at high resolution .     

Exact Computation of the Topology and Geometric Invariants of the Voronoi Diagram of Spheres in 3D

In this paper, we are addressing the exact computation of the Delaunay graph (or quasi-triangulation) and the Voronoi diagram of spheres using Wu’s algorithm. Our main contributions are first a methodology for automated derivation of invariants of the Delaunay empty circumsphere predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are applying Wu’s algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial we obtain is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu’s algorithm on the invariants. Finally, we present an incremental algorithm for the construction of Voronoi diagrams and Delaunay graphs of spheres in 3D and its application to Geodesy.     

Cross-weighted moments and affine invariants for image registrationand matching

A framework for deriving a class of new global affine invariants for both object matching and positioning based on a novel concept of cross-weighted moments with fractional weights is presented. The fractional weight factor allows for a more flexible range to balance between the capability to discriminate between objects that differ only in small shape details and the sensitivity of small shape details to the presence of the noise. Moreover, it makes it possible to arrive at low order (zero order) affine invariants that are more robust than those derived from higher order regular moments. The affine transformation parameters are recovered from the zero and the first order cross-weighted moments without requiring any feature point correspondence information. The equations used to find the affine transformation parameters are linear algebraic. The sensitivity of the cross-weighted moment invariants to noise, missing data, and perspective effects is shown on real images     

When is it Possible to Identify 3D Objects From Single Images Using Class Constraints?

One approach to recognizing objects seen from arbitrary viewpoint is by extracting invariant properties of the objects from single images. Such properties are found in images of 3D objects only when the objects are constrained to belong to certain classes (e.g., bilaterally symmetric objects). Existing studies that follow this approach propose how to compute invariant representations for a handful of classes of objects. A fundamental question regarding the invariance approach is whether it can be applied to a wide range of classes. To answer this question it is essential to study the set of classes for which invariance exists. This paper introduces a new method for determining the existence of invariant functions for classes of objects together with the set of images from which these invariants can be computed. We develop algebraic tests that determine whether the objects in a given class can be identified from single images. These tests apply to classes of objects undergoing affine projection. In addition, these tests allow us to determine the set of views of the objects which are degenerate. We apply these tests to several classes of objects and determine which of them is identifiable and which of their views are degenerate.     

An Algorithm for Nonparametric Decomposition of Differential Polynomials

Last decades, one of the most important problems of symbolic computations (see [7]) is the development of algorithms for solving algebraic and differential equations, in particular, those for factoring linear ordinary differential operators (LODO) [1–4]. In this paper, the problems of LODO factorization and decomposition of ordinary polynomials [5, 6] are generalized: an algorithm is proposed for decomposition of differential polynomials that allows one to find a particular solution to a complex algebraic differential equation (an example is provided in the end of the paper).     

Affine moment invariants generated by graph method

The paper presents a general method of an automatic deriving affine moment invariants of any weights and orders. The method is based on representation of the invariants by graphs. We propose an algorithm for eliminating reducible and dependent invariants. This method represents a systematic approach to the generation of all relevant moment features for recognition of affinely distorted objects. We also show the difference between pseudoinvariants and true invariants.     

The 3L algorithm for fitting implicit polynomial curves andsurfaces to data

We introduce a completely new approach to fitting implicit polynomial geometric shape models to data and to studying these polynomials. The power of these models is in their ability to represent nonstar complex shapes in two(2D) and three-dimensional (3D) data to permit fast, repeatable fitting to unorganized data which may not be uniformly sampled and which may contain gaps, to permit position-invariant shape recognition based on new complete sets of Euclidean and affine invariants and to permit fast, stable single-computation pose estimation. The algorithm represents a significant advancement of implicit polynomial technology for four important reasons. First, it is orders of magnitude taster than existing fitting methods for implicit polynomial 2D curves and 3D surfaces, and the algorithms for 2D and 3D are essentially the same. Second, it has significantly better repeatability, numerical stability, and robustness than current methods in dealing with noisy, deformed, or missing data. Third, it can easily fit polynomials of high, such as 14th or 16th, degree. Fourth, additional linear constraints can be easily incorporated into the fitting process, and general linear vector space concepts apply     

Combined blur and affine moment invariants and their use in pattern recognition

The paper is devoted to the recognition of objects and patterns deformed by imaging geometry as well as by unknown blurring. We introduce a new class of features invariant simultaneously to blurring with a centrosymmetric PSF and to affine transformation. As we prove in the paper, they can be constructed by combining affine moment invariants and blur invariants derived earlier. Combined invariants allow to recognize objects in the degraded scene without any restoration.     

基于协方差矩阵的仿射不变量

为了对仿射变形的物体进行有效和正确的识别,构造了一种新的仿射不变量.构造的主要过程是：先计算图像的协方差矩阵,接着计算该矩阵的特征值和特征向量,再构造出一组同心椭圆,这些椭圆以图像质心为中心,以两个特征向量为长、短轴,且轴长和两个特征值的平方根成正比,进而利用图像紧化原理和仿射变换的有关性质推导出一组仿射不变量.文中将仿射不变量用于模式识别,获得很高的识别率.     

基于组合不变矩和神经网络的三维物体识别

在三维物体识别系统中,提出将三维物体的Hu不变矩和仿射不变矩两者的低阶矩组合作为三维物体的特征,结合改进的BP神经网络应用于三维物体的分类识别。理论分析和仿真实验表明组合这两种矩特征进行物体识别,性能优于单独使用Hu不变矩,如果进一步对这两种组合的矩特征进行主成分分析处理,可显著提高系统识别性能,并减少网络的训练时间。     

基于Mean Shift的相似性变换和仿射变换目标跟踪算法

传统的Mean Shift (MS) 算法只能对发生平移和尺度变化的目标进行跟踪,而对于具有相似性变换或者更复杂的仿射变换的目标跟踪效果很不理想或无法跟踪。为了解决这一问题,提出了两种基于MS的改进算法。第一种算法针对仿射变换,根据奇异值分解理论,仿射变换矩阵可以分解成两个旋转矩阵和一个对角矩阵的乘积,在此基础上建模了一种新的候选目标模型。通过Bhattacharyya系数将目标跟踪问题转化成以仿射变换参数为变量的最优化问题,推导相关参量的一阶偏导数并令其为零从而得出相对于仿射变换的MS算法。另外,针对进行相似性变换的目标也提出了一种新的候选目标模型,并用类似的梯度下降算法估计目标的平移向量和旋转角度。实验结果表明,提出的算法能够跟踪具有相似性变换或仿射变换的目标,比传统的MS算法具有更好的跟踪性能。