Multiple View Geometry of General Algebraic Curves

We introduce a number of new results in the context of multi-view geometry from general algebraic curves. We start with the recovery of camera geometry from matching curves. We first show how one can compute, without any knowledge on the camera, the homography induced by a single planar curve. Then we continue with the derivation of the extended Kruppa's equations which are responsible for describing the epipolar constraint of two projections of a general algebraic curve. As part of the derivation of those constraints we address the issue of dimension analysis and as a result establish the minimal number of algebraic curves required for a solution of the epipolar geometry as a function of their degree and genus.We then establish new results on the reconstruction of general algebraic curves from multiple views. We address three different representations of curves: (i) the regular point representation in which we show that the reconstruction from two views of a curve of degree d admits two solutions, one of degree d and the other of degree d(d – 1). Moreover using this representation, we address the problem of homography recovery for planar curves, (ii) dual space representation (tangents) for which we derive a lower bound for the number of views necessary for reconstruction as a function of the curve degree and genus, and (iii) a new representation (to computer vision) based on the set of lines meeting the curve which does not require any curve fitting in image space, for which we also derive lower bounds for the number of views necessary for reconstruction as a function of curve degree alone.     

Theory and Practice of Projective Rectification

This paper gives a new method for image rectification, the process of resampling pairs of stereo images taken from widely differing viewpoints in order to produce a pair of matched epipolar projections. These are projections in which the epipolar lines run parallel with the x-axis and consequently, disparities between the images are in the x-direction only. The method is based on an examination of the fundamental matrix of Longuet-Higgins which describes the epipolar geometry of the image pair. The approach taken is consistent with that advocated by Faugeras (1992) of avoiding camera calibration. The paper uses methods of projective geometry to determine a pair of 2D projective transformations to be applied to the two images in order to match the epipolar lines. The advantages include the simplicity of the 2D projective transformation which allows very fast resampling as well as subsequent simplification in the identification of matched points and scene reconstruction.     

A localized method for intersecting plane algebraic curve segments

We present a local method for the computation of the intersections of plane algebraic curve segments. The conventional method of intersection is global, because it must first find all of the intersections between two curves before it can restrict the segments in question; hence, it cannot take advantage of situations dealing with the intersection of short-curve segments on complex curves. Our local method, on the other hand, will directly find only those intersections that lie on the segments, as it is based upon an extension of methods for tracing along a curve.This author's research was supported by the National Science Foundation under Grant IRI-8910366This author's research was supported by the National Science Foundation under Grant CCR-8810568     

实平面奇异代数曲线的全局B样条逼近

提出了一种用k次B样条曲线全局逼近实平面k次代数曲线的算法,每个连通部分用一条B样条曲线逼近.它适合于任意亏格的不可约的实平面代数曲线(包括含奇异点的曲线).这种逼近建立在所提出的代数曲线胀开采样的基础上,这种胀开采样算法从本质上解决了奇异点周围采样难的问题.实验结果表明,该方法的逼近精度高于已有算法.     

Algebraic pruning: a fast technique for curve and surface intersection

Computing the intersection of parametric and algebraic curves and surfaces is a fundamental problem in computer graphics and geometric modeling. This problem has been extensively studied in the literature and different techniques based on subdivision, interval analysis and algebraic formulation are known. For low degree curves and surfaces algebraic methods are considered to be the fastest, whereas techniques based on subdivision and Bézier clipping perform better for higher degree intersections. In this paper, we introduce a new technique of algebraic pruning based on the algebraic approaches and eigenvalue formulation of the problem. The resulting algorithm corresponds to computing only selected eigenvalues in the domain of intersection. This is based on matrix formulation of the intersection problem, power iterations and geometric properties of Bézier curves and surfaces. The algorithm prunes the domain and converges to the solutions rapidly. It has been applied to intersection of parametric and algebraic curves, ray tracing and curve-surface intersections. The resulting algorithm compares favorably with earlier methods in terms of performance and accuracy.     

Symbolic parametrization of curves

If algebraic varieties like curves or surfaces are to be manipulated by computers, it is essential to be able to represent these geometric objects in an appropriate way. For some applications an implicit representation by algebraic equations is desirable, whereas for others an explicit or parametric representation is more suitable. Therefore, transformation algorithms from one representation to the other are of utmost importance.We investigate the transformation of an implicit representation of a plane algebraic curve into a parametric representation. Various methods for computing a rational parametrization, if one exists, are described. As a new idea we introduce the concept of working with classes of conjugate (singular or simple) points on curves. All the necessary operations, like determining the multiplicity and the character of the singular points or passing a linear system of curves through these points, can be applied to such classes of conjugate points. Using this idea one can parametrize a curve if one knows only one simple point on it. We do not propose any new method for finding such a simple point. By classical methods a rational point on a rational curve can be computed, if such a point exists. Otherwise, one can express the coordinates of such a point in an algebraic extension of degree 2 over the ground field.     

Algebraic functions for recognition

In the general case, a trilinear relationship between three perspective views is shown to exist. The trilinearity result is shown to be of much practical use in visual recognition by alignment-yielding a direct reprojection method that cuts through the computations of camera transformation, scene structure and epipolar geometry. Moreover, the direct method is linear and sets a new lower theoretical bound on the minimal number of points that are required for a linear solution for the task of reprojection. The proof of the central result may be of further interest as it demonstrates certain regularities across homographics of the plane and introduces new view invariants. Experiments on simulated and real image data were conducted, including a comparative analysis with epipolar intersection and the linear combination methods, with results indicating a greater degree of robustness in practice and a higher level of performance in reprojection tasks     

空间代数曲线的参数化逼近

提出一种用三次B样条曲线逼近空间代数曲线的方法.对非奇异的情况,先用随机微分方程方法采样,然后对采样点进行聚类排序,最后用三次B样条曲线逼近有序点列;而对包含奇异点的情况,则将空间曲线双有理映射成平面曲线,采用已有的含奇异点的平面代数曲线的采样及排序方法来实现对应空间曲线的采样及排序.两种情况都获得了优于其它方法的逼近效果.     

Method for intersecting algebraic surfaces with rational polynomial patches

The paper presents a hybrid algorithm for the computation of the intersection of an algebraic surface and a rational polynomial parametric surface patch. This algorithm is based on analytic representation of the intersection as an algebraic curve expressed in the Bernstein basis; automatic computation of the significant points of the curve using numerical techniques, subdivision and convexity properties of the Bernstein basis; partitioning of the intersection domain at these points; and tracing of the resulting monotonic intersection segments using coarse subdivision and faceting methods coupled with Newton techniques. The algorithm described in the paper treats intersections of arbitrary order algebraic surfaces with rational biquadratic and bicubic patches and introduces efficiency enhancements in the partitioning and tracing parts of the solution process. The algorithm has been tested with up to degree four algebraics and bicubic patches.     

基于平面的便携式结构光系统柔性标定方法

对于便携式结构光系统, 该系统必须适合方便使用. 因此, 针对该系统的标定方法也必须采用方便且便宜的设备, 诸如具有两个或三个正交平面或者需要额外固定措施的一些设备则不宜采用. 同时针对快速三维获取的目的, 应该采用估计便携式结构光系统投影矩阵的方法. 本文针对便携式结构光系统的上述应用需求, 提出了一种基于平面的便携式结构光系统柔性标定方法. 该方法需要一个标定模板和一个参考模板. 标定模板被固定在一个平面上, 而参考模板则通过LCD投影仪被投射到该平面上. 通过交比和极几何约束, 可以获得分别对投影仪和相机的世界坐标系和图像坐标系的点对应坐标. 通过这些点对应坐标, 即可完成整个系统的标定. 实验结果表明该方法具有很高的准确性和鲁棒性．     

Projection matrix by orthogonal vanishing points

Calculation of camera projection matrix, also called camera calibration, is an essential task in many computer vision and 3D data processing applications. Calculation of projection matrix using vanishing points and vanishing lines is well suited in the literature; where the intersection of parallel lines (in 3D Euclidean space) when projected on the camera image plane (by a perspective transformation) is called vanishing point and the intersection of two vanishing points (in the image plane) is called vanishing line. The aim of this paper is to propose a new formulation for easily computing the projection matrix based on three orthogonal vanishing points. It can also be used to calculate the intrinsic and extrinsic camera parameters. The proposed method reaches to a closed-form solution by considering only two feasible constraints of zero-skewness in the internal camera matrix and having two corresponding points between the world and the image. A nonlinear optimization procedure is proposed to enhance the computed camera parameters, especially when the measurement error of input parameters or the skew factor are not negligible. The proposed method has been run on real and synthetic data for more precise evaluations. The provided experimental results demonstrate the superiority of the proposed method.     

隐式曲面／参数曲面的求交算法

本文介绍了一种实用有效的隐式曲面／参数曲面求交算法。算法主要分为两部分：特征初始点的求取和单调段的跟踪。解双变量多项式方程求解特征初始点。跟踪在三维空间进行，易于控制跟踪步长和离散交点对交线的逼近精度。算法不离散参数曲面，不漏交。     

三角网格上的代数曲面重建

提出一种用分片代数曲面构造三角曲面片的方法,利用具有公共边的2个三角形区域的4个顶点的函数值以及公共边2个端点的外法向量来构造一个二次曲面V(g)和一个截面V(h),其交V(g,h)即为2个三角曲面片的公共边界曲线.对每个已确定了边界条件的三角片内部进一步划分成3部分,每部分各自定义一个三次代数曲面.这3个三次代数曲面不仅在其交线处光滑拼接,而且分别沿三角形的边界与V(g)光滑拼接,从而构成一个具有GC1连续性的分片代数曲面.对于只属于一个三角片的边界留有一个自由度,可对曲面形状加以控制.     

Automatic parameterization of rational curves and surfaces III: Algebraic plane curves

We present algorithms to compute the genus and rational parametric equations, for implicitly defined irreducible plane algebraic curves of arbitrary degree. Rational parameterizations exist for all irreducible algebraic curves of genus 0. The genus is computed by a complete analysis of the singularities of plane algebraic curves, using affine quadratic transformations. The rational parameterization techniques, essentially, reduce to solving symbolically systems of homogeneous linear equations and the computation of polynomial resultants.     

Extrinsic calibration of a camera and laser range finder using a new calibration structure of a plane with a triangular hole

Sensor fusion of a camera and laser range finder is important for the autonomous navigation of mobile robots. Finding the transformation between the camera and laser range finder is the first necessary step for the fusion of information. Many algorithms have been proposed, but these tend to require many different steps in order to achieve reliable and accurate results. A calibration structure that has triangular hole on its plane is proposed for the extrinsic calibration of a camera and laser range finder. Locations of laser scan data that are invisible on the calibration plane can be determined using property on the proposed calibration structure. First, we classify the laser scan data into two groups where one is on the plane and the other is off the plane. Then, we determine the absolute location of the laser scan data on the plane through a search of the parameters of the line. Finally, we can establish 3D-3D correspondences between the camera and laser range finder. Extrinsic calibration between a camera and laser range finder is found using a conventional 3D-3D transformation computing algorithm. Keywords: Calibration k]camera k]extrinsic calibration k]laser range finder     

A unified algorithm for finding the intersection curve of surfaces

In this papaer,an INTEGRAL CURVE ALGORITHM is presented,which turns the intersection curve of surfaces into the form of integral one and then uses “PREDICTORCORRECTOR” technique to evaluate the intersection of surfaces.No matter how the surfaces are defined,the method always deals with the intersection curves in the same way.To find a point on the curve one need only to calculate the JACOBI determinants of “PREDICTOR point”and “CORRECTOR point” while the second order precision is guatanteed.Thus,not only is the problem of finding the intersection of surfaces resolved,but also the algorithms for generating both plane curve and space curve are unified.     

Set-theoretic generators of rational space curves

We show how to calculate three low degree set-theoretic generators (i.e., algebraic surfaces) for all rational space curves of low degree (degree ≤6$\le 6$) as well as for all higher degree rational space curves where at least one element of their μ$\mu$-basis has degree 1 from a μ$\mu$-basis of the parametrization. In addition to having low degree, at least two of these surface generators are always ruled surfaces. Whenever possible we also show how to compute two set-theoretic complete intersection generators for these rational space curves from a μ$\mu$-basis of their parametrization.     

Recognizing algebraic surfaces from their outlines

The outline in a single picture of a generic algebraic surface of degree three or greater completely determines the projective geometry of the surface. The result holds for a generic perspective view of a generic algebraic surface, where the camera calibration parameters and the focal point are unknown. Known camera calibration appears not to reduce the projective ambiguity. The result is constructive.     

平面代数曲线间最近距离的计算

通过几何观察,指出一条曲线上的最近点是另一条曲线的等距曲线与该曲线的切点这一事实,同时提出基于等距思想的方法来求解2条平面代数曲线间的最近距离．该方法几何意义明显,可同时用来计算代数曲线／参数曲线间的最近距离．对于平面二次曲线,采用文中方法得到的单变量多项式方程次数比已有类似方法中结果方程的次数更低,从而可以降低方程求解的计算复杂度或提高求解的稳定性．