Applying the Hough transform pseudo-linearity property to improve computing speed

This work describes a general method of acceleration of the convergence of the Hough transform based, on the one hand, on an improvement of the image analysis speed, and, on the other hand, on the space undersampling of the image. This method is used in image processing to extract lines, circles, ellipses or arbitrary shapes. The results presented are applied to the detection of straight-line segments and ellipses, but can be extended to any type of transform.     

局部PCA参数约束的Hough多椭圆分层检测算法

针对随机Hough变换(RHT)在复杂图像中检测圆及椭圆时随机采样所造成的大量无效采样、无效累积以及运算时间长等问题,提出基于局部PCA感兴趣参数约束Hough多椭圆分层检测思路。首先利用边缘检测算子获得边缘信息并去除边缘交叉点,在边缘图像中标记并提取出满足一定长度的连续曲线段;其次利用线段PCA方向分析确定是否属于有效曲线段;然后,对所有感兴趣曲线段按照标记顺序依次利用椭圆拟合办法初步得到感兴趣椭圆粗略参数,根据拟合结果进而模糊约束Hough变换参数搜索范围,得到精确椭圆参数;最后利用检测结果更新图像空间,删除已经检测到的椭圆,依次进行,直到所有椭圆检测完毕。实验结果表明,该算法在计算、存储消耗上均大大减少。     

A hierarchical approach for fast and robust ellipse extraction

This paper presents a hierarchical approach for fast and robust ellipse extraction from images. At the lowest level, the image is described as a set of edge pixels, from which line segments are extracted. Then, line segments that are potential candidates of elliptic arcs are linked to form arc segments according to connectivity and curvature conditions. Next, arc segments that belong to the same ellipse are grouped together. Finally, a robust statistical method, namely RANSAC, is applied to fit ellipses to groups of arc segments. Unlike Hough Transform based algorithms, this method does not need a high dimensional parameter space, and so it reduces the computation and storage requirements. Experiments on both synthetic and real images demonstrate that the proposed method has excellent performance in handling occlusion and overlapping ellipses.     

基于边界曲线弧分割的多椭圆检测

不同于传统的Hough变换算法,提出一种基于边界弧分割的椭圆检测方法。首先将边界从交点处分割成弧段,将得到弧段划分为长弧和短弧两组并按长度降序排序,然后从两组中找出属于某个椭圆的若干弧段,利用最小二乘法拟合得到候选椭圆并验证是否为真正椭圆。实验表明该算法能快速检测出图中椭圆,运行时间远小于采用随机Hough变换算法,在具有噪声、椭圆残缺的情况下仍能有较好的检测结果。     

A fast and effective ellipse detector for embedded vision applications

Several papers addressed ellipse detection as a first step for several computer vision applications, but most of the proposed solutions are too slow to be applied in real time on large images or with limited hardware resources. This paper presents a novel algorithm for fast and effective ellipse detection and demonstrates its superior speed performance on large and challenging datasets. The proposed algorithm relies on an innovative selection strategy of arcs which are candidate to form ellipses and on the use of Hough transform to estimate parameters in a decomposed space. The final aim of this solution is to represent a building block for new generation of smart-phone applications which need fast and accurate ellipse detection also with limited computational resources.     

A decomposable parameter space for the detection of ellipses

Hough transform is a well-known method for detecting parametric curves in binary images. One major drawback of the method is that the transform requires time and memory space exponential in the number of parameters of the curves. An effective approach to reduce both the time and space requirement is the parameter space decomposition. In this paper, we present two methods for the detection of ellipses based on the straight line Hough transform (SLHT).

The SLHT of a curve in the θ-π space can be expressed as the sum of two terms, namely, the translation term, and the intrinsic term. One useful property of this representation is that it allows the translation, rotation and intrinsic parametersof the curve be separated easily. Timing performance of the proposed methods compares favorably with the other Hough-based methods.     

Hough变换的特性分析:一种全局观点(II)

使用基本Hough变换进行椭圆的检测与提取,利用形状在投影时各投影区间中点是否在一条有效的正弦曲线上来检测形状是否具有中心对称性;结合对投影区间长度变化规律的分析,实现了在二维空间中椭圆的检测,并通过仿真实验说明了该方法的有效性;利用整周期上峰值线的对称性确定了多个形状投影分布的判定,使得对几何基元的提取纳入了统一的框架.     

Determination of three-dimensional object location and orientationfrom range images

A technique for determining the distortion parameters (location and orientation) of general three-dimensional objects from a single range image view is introduced. The technique is based on an extension of the straight-line Hough transform to three-dimensional space. It is very efficient and robust, since the dimensionality of the feature space is low and since it uses range images directly (with no preprocessing such as segmentation and edge or gradient detection). Because the feature space separates the translation and rotation effects, a hierarchical algorithm to detect object rotation and translation is possible. The new Hough space can also be used as a feature space for discriminating among three-dimensional objects     

基于Hough变换的图象检测对偶点法

提出了图形边界对偶点的概念,证明了对对称图形对偶点的存在性及其关于平移、缩放和旋转组合变换的不变性;结合Hough变换,建立了一种快速的图象检测方法,详细给出圆和椭圆检测的对偶点算法,并补充了文献[1]中公式的不足,实验结果表明,该对偶点法除保留了Hough变换法的容错性和鲁棒性外,还具有很快的计算速度,而且可以灵活地应用于解决一些较难的图象检测问题。     

On the inverse Hough transform

In this paper, an inverse Hough transform algorithm is proposed. This algorithm reconstructs correctly the original image, using only the data of the Hough transform space and it is applicable to any binary image. As a first application, the inverse Hough transform algorithm is used for straight-line detection and filtering. The lines are detected not just as continuous straight lines, which is the case of the standard Hough transform, but as they really appear in the original image, i.e., pixel by pixel. To avoid the quantization effects in the Hough transform space, inversion conditions are defined, which are associated only with the dimensions of the images. Experimental results indicate that the inverse Hough transform algorithm is robust and accurate     

Recognition of digital curves scanned from paper drawings using genetic algorithms

After analyzing the existing methods, based on holo-extraction method of information, this paper develops a recognition method of digital curves scanned from paper drawings for subsequent pattern recognition and 3D reconstruction. This method is first to construct the networks of single closed region (SCRs) of black pixels with all the information about both segments and their linking points, to classify all the digital contours represented by SCRs into three types: straight-line segments, circular arcs, and combined lines, and then to decompose the combined lines into least basic sub-lines or segments (straight-line segments or circular arcs) with least fitting errors using genetic algorithms with adaptive probabilities of crossover and mutation and to determine their relationships (intersecting or being tangential to each other). It is verified that the recognition method based on the networks of SCRs and the genetic algorithm is feasible and efficient. This method and its software prototype can be used as a base for further work on subsequent engineering drawing understanding and 3D reconstruction.     

正交距离椭圆拟合法的推广及其实现

同心椭圆弧的拟合问题存在于计算机视觉、天文图像处理、CAD等领域。将椭圆的正交几何距离拟合算法推广到多个同心椭圆弧拟合上,提出一种同心椭圆弧拟合的处理方法。文中还给出了该方法实现的具体步骤和伪代码,该方法将单一圆、椭圆的拟合以及多个同心圆和椭圆的拟合统一了起来。实验表明该方法稳定、有效。     

Real-time system for elliptical-based face detection

In this paper, we present a real-time ellipse detector in gray scale images with a new multiple stage architecture based on a 3-accumulator version of the Fast Hough Transform with a previous Canny edge extraction. The system can be applied to detect different elliptical objects and is robust to incomplete ellipses, cluttered backgrounds and illumination changes. It achieves 12 frames per second on a PC Pentium 4, 2.80 GHz. Experimental results, focusing on faces, with both static and video images are showed. The presented ellipse detector can be used as a preprocessing module in a face tracking or recognition application.     

Detection of incomplete ellipse in images with strong noise by iterative randomized Hough transform (IRHT)

An iterative randomized Hough transform (IRHT) is developed for detection of incomplete ellipses in images with strong noise. The IRHT iteratively applies the randomized Hough transform (RHT) to a region of interest in the image space. The region of interest is determined from the latest estimation of ellipse parameters. The IRHT “zooms in” on the target curve by iterative parameter adjustments and reciprocating use of the image and parameter spaces. During the iteration process, noise pixels are gradually excluded from the region of interest, and the estimation becomes progressively close to the target. The IRHT retains the advantages of RHT of high parameter resolution, computational simplicity and small storage while overcoming the noise susceptibility of RHT. Indivisible, multiple instances of ellipse can be sequentially detected. The IRHT was first tested for ellipse detection with synthesized images. It was then applied to fetal head detection in medical ultrasound images. The results demonstrate that the IRHT is a robust and efficient ellipse detection method for real-world applications.     

基于椭圆拟合的快速钢管计数方法

为满足钢管计数中精度和速度的需求,提出了一种新型的椭圆检测方法.该方法避开了Hough变换或随机Hough变换的复杂性,直接通过边缘跟踪对椭圆进行拟合,通过其它边缘像素对拟合结果进行校验和对比,对概率超过阈值的无包含椭圆进行计数.在边缘检测过程中对Robert算子进行了改进,并在阈值分割前对边缘进行了增强,在阈值分割后对边缘进行了保持连通性的细化.根据需要还可以在计数过程中加入人工指导.实验结果表明,该方法能快速准确地检测出图像中所有椭圆.     

基于Hough变换的金刚石颗粒测量方法研究

针对金刚石颗粒图像分析时的颗粒边缘非闭合性问题,本文提出了一种基于Hough变换的金刚石颗粒测量新方法。该方法首先对图像进行形态学去噪、平滑滤波和Canny边缘检测等预处理,得到金刚石颗粒图像的初始边缘曲线,然后采用Hough变换提取边缘曲线的直线特征,并通过极径和极角对多个直线特征进行判断和图形识别,得到确定的金刚石颗粒边缘轮廓,最后对得到的边缘轮廓进行拟合,测量出金刚石颗粒的粒径、椭圆度和圆度等参数大小。该方法在VC+ 环境下,用OpenCV编程技术对其进行了实验验证,结果表明：该方法可以准确快速地测量出金刚石颗粒特征参数,为金刚石颗粒的等级评定提供了技术支持。     

基于最小二乘修正的随机Hough变换直线检测

利用Hough变换进行直线检测时,由于直线在参数空间中的映射容易受到邻近目标、噪声以及本身非理想状态的干扰,算法中的投票过程较易出现无效累积,进而导致虚检、漏检及端点定位不准等问题.针对传统方法的上述缺陷,提出了一种基于 ρ-θ 域最小二乘拟合修正的随机Hough变换的直线检测方法.首先, 在随机抽样时利用像素-长度比值对抽样的有效性进行判定,剔除不在直线上的抽样点对;然后, 对邻域相关点进行 ρ-θ 域的最小二乘拟合,得到修正后的直线参数用于累加投票,投票过程中设定累加阈值,通过检测峰值点逐次检出疑似长直线;最后, 通过设定断裂阈值对每条长直线进行筛选和分段,定位出直线段的端点.仿真实验表明,所提方法在投票时有效抑制了复杂环境对局部最大值的干扰,使直线检测的准确率得到显著提升.     

Old and new straight-line detectors: Description and comparison

Straight-line detection is important in several fields such as robotics, remote sensing, and imagery. The objective of this paper is to present several methods, old and new, used for straight-line detection. We begin by reviewing the standard Hough transform (SHT), then three new methods are suggested: the revisited Hough transform (RHT), the parallel-axis transform (PAT), and the circle transform (CT). These transforms utilize a point-line duality to detect straight lines in an image. The RHT and the PAT should be faster than the SHT and the CT because they use line segments whereas the SHT uses sinusoids and CT uses circles. Moreover, the PAT, RHT, and CT use additions and multiplications whereas the SHT uses trigonometric functions (sine and cosine) for calculation. To compare the methods we analyze the distribution of the frequencies in the accumulators and observe the effect on the detection of false local maxima. We also compare the robustness to noise of the four transforms. Finally, an example with a real image is given.     

A note on polygonal and elliptical approximation of mechanical parts

A previous paper described a method of extracting long sequences of border points from images of mechanical parts, by linking points having high edge values that lie on the borders of thresholded regions. This paper develops methods of fitting polygons and arcs of ellipses to the border sequences. The results are applied to finding small holes in images of connecting rods.     

Accurate matching of two-dimensional shapes using the minimal tolerance zone error

Automated visual geometric inspection of machined parts depends upon the ability to determine the underlying parameters of a shape model that will best fit the reference shape to the real shape captured. This paper presents a parametric approach for the matching of two-dimensional profiles, which are composed of straight-line segments and circular arcs, based on the tolerancing requirements defined by the AINSI standards. The shape matching problem is formulated as a minimax optimization model and a procedure for solving this optimization model is developed. Experimental results have shown the proposed algorithm to be consistently accurate and extremely fast.