Spirograph theory: a framework for calculations on digitized straight lines

Using diagrams called ``spirographs' a general theory is developed with which one can easily perform calculations on various aspects of digitized straight lines. The mathematics of the theory establishes a link between digitized straight lines and the theory of numbers (Farey series, continued fractions). To show that spirograph theory is a useful unification, we derive two previously known advanced results within the framework of the theory, and new results concerning the accuracy in position of a digitized straight line as a function of its slope and length.     

Geometry and construction of straight lines in log-polar images

This paper investigates, how straight lines are mapped to the non-Euclidean log-polar image plane and how their properties in log-polar coordinates can be used to perform two fundamental measurement operations: the construction of straight lines of given orientation angle and the measurement of distances along these lines. It is shown, how the two operations can be efficiently implemented for discrete log-polar images. The usefulness of the developed theory is demonstrated by applying it to different image processing tasks. As a first example, it is used for line and circle detection in log-polar sampled images. As a second example, it is used to construct epipolar lines and perform disparity estimation in log-polar images. Experiments with both synthetic and real images are presented, and the feature detection results are quantitatively evaluated.     

基于直线和二次曲线的多回路平面曲线分割

提出了一种多回路平面曲线的分割算法。算法以直线段和二次曲线段作为拟合的基本单元，通过边缘跟踪把多回路的平面曲线分割成曲线段或单回路的封闭曲线，然后在曲线曲率不连续处继续分割。针对一次分割时可能会产生的迷向问题，提出了基于对偶原理的线段合并技术。该算法的结果能简单有效地描述场景中的物体，使高级视觉任务更简单。实验结果表明算法能取得较好的效果。     

Affine transformations for digitized spatial data in geology

Affine transformations are among the most basic and useful geometrical operations in computer applications in geology. Homogeneous coordinates extend their applicability. The methods are essential in handling digitized locational data and are applicable widely in other graphical applications such as calibrating data sets for plotting, and in shape comparison and spatial analysis. Affine transformations alter the length of lines and the angles between them, whereas straight lines remain straight, parallel lines remain parallel, and the ratio in which a point divides a line remains the same.Their geometrical significance indicates that they can be visualized readily, and the corresponding operations in matrix algebra provide a straightforward method of computer implementation. A transformation matrix is calculated from four calibration points, the coordinates of which are known before and after transformation. Multiplication of coordinates in the initial frame of reference by the transformation matrix converts them to coordinates in the new frame of reference. A listing of relevant FORTRAN programs is given, with examples.     

Curvature estimation along noisy digital contours by approximate global optimization

In this paper, we introduce a new curvature estimator along digital contours, which we called global min-curvature (GMC) estimator. As opposed to previous curvature estimators, it considers all the possible shapes that are digitized as this contour, and selects the most probable one with a global optimization approach. The GMC estimator exploits the geometric properties of digital contours by using local bounds on tangent directions defined by the maximal digital straight segments. The estimator is then adapted to noisy contours by replacing maximal segments with maximal blurred digital straight segments. Experiments on perfect and damaged digital contours are performed and in both cases, comparisons with other existing methods are presented.     

Surface area estimation of digitized 3D objects using quasi-Monte Carlo methods

A novel and efficient quasi-Monte Carlo method for estimating the surface area of digitized 3D objects in the volumetric representation is presented. It operates directly on the original digitized objects without any surface reconstruction procedure. Based on the Cauchy-Crofton formula from integral geometry, the method estimates the surface area of a volumetric object by counting the number of intersection points between the object's boundary surface and a set of uniformly distributed lines generated with low-discrepancy sequences. Using a clustering technique, we also propose an effective algorithm for computing the intersection of a line with the boundary surface of volumetric objects. A number of digitized objects are used to evaluate the performance of the new method for surface area measurement.     

基于单应矩阵的直线匹配

提出了在单应矩阵原理约束下进行直线匹配的算法。首先利用单应矩阵将从不同影像上提取出的直线集变换到同一影像坐标系下;然后结合直线自身的几何特性及其特性支持区域的灰度特性,初步确定同名直线;最后依据左右一致性准则,剔除错误匹配。当引入直线特性支持区域的灰度测度时,只考虑几何变形和灰度畸变较小的一侧,提高了匹配的可靠性。实验表明,该算法简单、易行,并有效解决了部分被遮挡直线以及断裂直线的匹配问题。     

Discrete representation of straight lines

If a continuous straight line segment is digitized on a regular grid, obviously a loss of information occurs. As a result, the discrete representation obtained (e.g., a chaincode string) can be coded more conveniently than the continuous line segment, but measurements of properties (such as line length) performed on the representation have an intrinsic inaccuracy due to the digitization process. In this paper, two fundamental properties of the quantization of straight line segments are treated. 1) It is proved that every ``straight' chaincode string can be represented by a set of four unique integer parameters. Definitions of these parameters are given. 2) A mathematical expression is derived for the set of all continuous line segments which could have generated a given chaincode string. The relation with the chord property is briefly discussed.     

Design of perimeter estimators for digitized planar shapes

Measurement of perimeters of planar shapes from their digitized images is an important task of computer vision systems. A general methodology for the design of simple and accurate parameter estimation algorithms is described. It is based on minimizing the maximum estimation error for digitized straight edges over all orientations. Two perimeter estimators are derived and their performance is tested and digitized circles using computer simulations. The experimental results may be used to predict the performance of the algorithm on shapes with arbitrary contours of continuous curvature. The simulations also show that fast and accurate perimeter estimation is possible, even for objects that are small relative to pixel size     

参数控制的边缘直线提取算法

提出了在灰度图像上使用参数控制的边缘直线提取算法，解决了图像理解过程中高效地提取边缘直线这一困难的问题。在计算出直线位置和方向的基础上，还能够计算直线的对比度、宽度、倾斜度等属性。实验显示，算法速度快、精度高、提取结果信息量丰富。     

A real-time processor for the Hough transform

The Hough transform method for recognition can cope effectively with noisy backgrounds and gaps in boundaries. However, long computation time and large memory requirements have prevented it from being used in real-time applications. An architecture devised to solve those problems, with a focus on detecting straight lines, is presented. Examples are given of the use of an experimental hardware model for automatic inspection and measurement of objects in factories and laboratories. It took less than one second from picture input to straight line parameter reproduction for these examples     

图像主特征直线的检测算法

直线特征的检测是计算机视觉与图像处理的基本任务之一。主特征直线是图像中最显著而且被人们最为关心的一些直线。本文提出了从图像中自动检测主特征直线的算法。首先利用图像分割算法分析得到图像的特征边缘,然后用短线段逼近这些边缘像素,接着用动态聚类算法对这些线段进行聚类,并用直线拟合聚类中的线段得到所有可能存在的直线,最后根据直线有效性度量找到其中有效性最高的直线就是主特征直线。最后本文给出了主特征直线在图像自动修复和自动美学构图中的应用实例。     

Extracting Straight Lines

This paper presents a new approach to the extraction of straight lines in intensity images. Pixels are grouped into line-support regions of similar gradient orientation, and then the structure of the associated intensity surface is used to determine the location and properties of the edge. The resulting regions and extracted edge parameters form a low-level representation of the intensity variations in the image that can be used for a variety of purposes. The algorithm appears to be more effective than previous techniques for two key reasons: 1) the gradient orientation (rather than gradient magnitude) is used as the initial organizing criterion prior to the extraction of straight lines, and 2) the global context of the intensity variations associated with a straight line is determined prior to any local decisions about participating edge elements.     

Piecewise straight-line correlation algorithm for navigation of autonomous systems with robotics applications

Autonomous moving systems, such as free moving robots and ‘nursing’ robots, accumulate errors during path tracking. While moving, correlation between measurement of the pattern characterizing the path and a previously recorded pattern stored in the computer of the tracking system can be found. Based on this correlation, it is possible to evaluate the system deviations from the desired path and calculate the required action to correct the movement of the vehicle. For certain applications the path characterizing pattern can be based on piecewice sections of nonparallel straight lines. The pattern can be obtained by filtering the straight lines from a picture of the path vicinity. To perform the required correlation between the actual measurement and this pattern a novel correlation algorithm, based on MSD (Mean Square Difference), is derived. MSD has an advantage over other methods for path pattern correlation, when there are no scaling errors between the measurement and the pattern in memory. Moreover, MSD converges to ML (Maximum Likelihood) for errors which are small with respect to the pattern measurement. Two main issues in implementing the new correlation process are discussed:

1. The near optimum performance of the new correlation algorithm, along with its simplicity, and the way in which it ‘handles’ real-time calculations with minimum computational effort.
2. The evaluation of the performance bound for the correlation process.

It is shown that, with the proposed method, deterministic errors in measuring the distances to these lines do not affect the correlation in the longitudinal (x) direction. Thus, only random measurement errors among the lines will cause correlation errors in x. In the lateral (y) direction, however, the obtained error is identical in size to the bias error.     

Convex Digital Polygons,Maximal Digital Straight Segments and Convergence of Discrete Geometric Estimators

Discrete geometric estimators approach geometric quantities on digitized shapes without any knowledge of the continuous shape. A classical yet difficult problem is to show that an estimator asymptotically converges toward the true geometric quantity as the resolution increases. For estimators of local geometric quantities based on Digital Straight Segment (DSS) recognition this problem is closely linked to the asymptotic growth of maximal DSS for which we show bounds both about their number and sizes on Convex Digital Polygons. These results not only give better insights about digitized curves but indicate that curvature estimators based on local DSS recognition are not likely to converge. We indeed invalidate a conjecture which was essential in the only known convergence theorem of a discrete curvature estimator. The proof involves results from arithmetic properties of digital lines, digital convexity, combinatorics and continued fractions.     

直线剖分平面算法的实现和应用

本文引入一种称为“区域树”的二叉树结构来表示若干直线由于相交而形成的对平面的剖分,并以之实现了一个“增加构造”方式的直线剖分平面算法。算法可用于解决许多与平面直线图形有关的问题,本文给出了如下应用实例：点定位问题,半平面公共交问题,简单多边形凸分解问题,简单多边形求交问题。     

A way to detect the straight line trajectory of an immovable point for estimating parameters of geometrical transformation of 3D images

When 3D images are matched by using the immovable point method, the problem of detecting the straight lines in the binary 3D image that consists of points suspicious for immobility occurs. True immovable points are a thin approximately straight line being among the chaotically dispensing points. False straight line trajectories, which are parallel to the true one, are also possible. In this work a procedure for searching all straight lines in 3D binary images and detecting the true trajectory among them is described.     

面向像对直线特征匹配的线特征矫正与提纯方法

目的 像对直线特征匹配是计算机视觉的重要研究内容,现有这类匹配方法均存在不同程度的误匹配问题。导致此问题的主要因素包括直线检测结果没有位于图像的真正边缘处、缺乏匹配线对的一致性校验。为此本文提出一种面向像对直线特征匹配的线特征矫正与提纯方法。方法 首先提取像对的边缘特征获得二值化边缘图,通过边缘梯度图及梯度矢量图（GVF）建立梯度引力图。其次,采用直线检测方法提取像对的直线特征,并通过梯度引力图矫正直线位置。最后,采用点特征匹配结果计算像对极线,并结合直线匹配结果确定最后的局部校验特征区域,通过随机抽样一致小邻域范围内特征相似性校验直线匹配结果,从而剔除误匹配直线。结果 对一组宽基线像对进行匹配实验,与直接采用直线匹配算法获得的匹配结果相比,矫正后的匹配结果剔除了大部分误匹配线对,将匹配准确率从50%提高到84%,继续提纯该匹配结果获得了100%的匹配准确率。在另一组宽基线像对的匹配实验中,经本文方法处理后的匹配准确率提高近30%。与前两组实验相比,第3组实验的像对摄影姿态变化不大,仅在尺度上有所区别,经本文方法处理后配准率从92%提高到100%。结论 采用本文方法可以大幅提高像对直线特征匹配的准确率,同时该方法可以很容易对其他直线匹配结果进行校正与提纯,具备较高的实用性。     

Line-drawing interpretation: straight lines and conic sections

Line drawings of man-made scenes often exhibit instances of straight lines and conic sections, i.e. ellipses, parabolas, and hyperbolas. Constraints imposed on the scene by such instances are investigated, under the assumption of general viewpoint, i.e. the mapping of the viewed surface onto the line drawing is stable under perturbation of the viewpoint within some open set. Both orthographic and perspective projection are considered. The viewed surfaces are assumed to be piecewise C³. It is shown that straight lines and conic sections in line drawings are projections of scene edges which are also straight lines and conic sections, respectively. It is also shown that scene events which project onto straight lines or conic sections cannot be combinations of view-point-independent and viewpoint-dependent edges. Further, continuous-surface-normal depth discontinuities which project onto straight lines can be locally described by developable surfaces, and those which project onto conic sections can be locally described by nondevelopable quadric surfaces. Each of these quadric surfaces is determined up to four degrees-of-freedom by its projection     

遥感多光谱影像空间分解力增强的融合方法

探讨了采用HIS变换对遥感多光谱影像与航片数字化影像进行融合的方法。试验结果表明所提出的方法是确实可行的。融合后的影像不仅在很大程度上保留了原多光谱影像的光谱特征,而且将其空间分解力提高到原光谱影像的近3倍,因而增强了多光谱影像的判读和量测能力。