An extension to the randomized hough transform exploiting connectivity

Finding global curve segments in an image is an important task. For such a task, a new branch of Hough Transform algorithms, called probabilistic Hough Transforms, has been actively developed in recent years. One of the first was a new and efficient probabilistic version of the Hough Transform for curve detection, the Randomized Hough Transform (RHT). In this paper, a novel extension of the RHT, called the Connective Randomized Hough Transform (CRHT), is suggested to improve the RHT for line detection in complex and noisy pictures. The CRHT method combines the ability of the Hough Transform for global feature extraction with curve fitting techniques by exploiting the connectivity of local edge image points. Tests demonstrate the high speed and low memory usage of the CRHT, as compared both to the Standard Hough Transform and the basic RHT.     

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

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

The adaptive hough transform

We introduce the Adaptive Hough Transform, AHT, as an efficient way of implementing the Hough Transform, HT, method for the detection of 2-D shapes. The AHT uses a small accumulator array and the idea of a flexible iterative "coarse to fine" accumulation and search strategy to identify significant peaks in the Hough parameter spaces. The method is substantially superior to the standard HT implementation in both storage and computational requirements. In this correspondence we illustrate the ideas of the AHT by tackling the problem of identifying linear and circular segments in images by searching for clusters of evidence in 2-D parameter spaces. We show that the method is robust to the addition of extraneous noise and can be used to analyze complex images containing more than one shape.     

Randomized Hough Transform (RHT): Basic Mechanisms,Algorithms, and Computational Complexities

Recently, a new curve detection approach called the randomized Hough transform (RHT) was heuristically proposed by the authors, inspired by the efforts of using neural computation learning techniques for curve detection. The preliminary experimental results and some qualitative analysis showed that in comparison with the Hough transform (HT) and its variants, the RHT has advantages of fast speed, small storage, infinite range of the parameter space, and high parameter resolution, and it can overcome several difficulties encountered with the HT methods. In this paper, the basic ideas of RHT are further developed into a more systematic and theoretically supported new method for curve detection. The fundamental framework and the main components of this method are elaborated. The advantages of RHT are further confirmed. The basic mechanisms behind these advantages are exposed by both theoretical analysis and detailed experimental demonstrations. The main differences between RHT and some related techniques are elucidated. This paper also proposes several improved algorithms for implementing RHT for curve detection problems in noisy images. They are tested by experiments on images with various kinds of strong noise. The results show that the advantages of RHT are quite robust. Moreover, the implementations of these algorithms are modeled by a generalized Bernoulli process, allowing probability analysis on these algorithms to estimate their computational complexities and to decide some important parameters for their implementations. It is shown quantitatively that the complexities are considerably smaller than those of the HT.     

基于机器视觉的公差检测系统算法研究与应用——自适应边缘检测与修正Hough变换

介绍了基于机器视觉的几何量和位置公差检测中常见的计算模型、图像处理和直线拟合一般算法，进一步介绍了一种自适应的边缘检测方法。着重分析了传统的Hough变换的优势和缺点，在此基础上提出了适应形位公差检测特点的修正Hough变换算法。自适应边缘检测方法被应用于检测实际工程的图像边缘，检测到的边缘区域在亚像素之内；修正的Hough变换算法也被运用于相应工程的直线拟合，与传统的Hough算法相比，结果表明其速度更快、精度更高，抗干扰能力更强，其拟合直线的极径精度可达到0．1个像素，极角精度可达0．01°。     

Constrained Hough Transforms for Curve Detection

This paper describes techniques to perform fast and accurate curve detection using constrained Hough transforms, in which localization error can be propagated efficiently into the parameter space. We first review a formal definition of Hough transform and modify it to allow the formal treatment localization error. We then analyze current Hough transform techniques with respect to this definition. It is shown that the Hough transform can be subdivided into many small subproblems without a decrease in performance, where each subproblem is constrained to consider only those curves that pass through some subset of the edge pixels up to the localization error. This property allows us to accurately and efficiently propagate localization error into the parameter space such that curves are detected robustly without finding false positives. The use of randomization techniques yields an algorithm with a worst-case complexity ofO(n), wherenis the number of edge pixels in the image, if we are only required to find curves that are significant with respect to the complexity of the image. Experiments are discussed that indicate that this method is superior to previous techniques for performing curve detection and results are given showing the detection of lines and circles in real images.     

结合LTS和Hough变换的直线检测算法

为提高Hough变换检测直线的精度,提出一种结合Hough变换与截断最小二乘法的直线检测算法。利用Hough变换确定图像中直线所在的大致区域,提取候选区域内的特征点集,采用截断最小二乘法拟合得到精确的直线参数。实验结果表明,该算法的检测率和检测精度较高,对Hough变换的分辨率要求较低,整体空间开销较小。     

图像中网格直线的检测方法的研究

首先分析了图像边缘特性以及Laplacian算子检测图像边缘的基本原理,提出了一种新的边缘检测算法,能准确地检测出图像中的目标边缘;在确定直线参数时,先使用Hough变换检测第一条最为明显的直线,然后去掉该直线以及附近的点,然后再次对图像进行Hough变换,并重复此过程,直到找到所有的直线;使用此改进后的Hough变化能够准确地检测到图像中构成网格的直线的参数.     

Hypothesis testing: a framework for analyzing and optimizing Houghtransform performance

In this paper a formal, quantitative approach to designing optimum Hough transform (HT) algorithms is proposed. This approach takes the view that a HT is a hypothesis testing method. Each sample in the HT array implements a test to determine whether a curve with the given parameters fits the edge point data. This view allows the performance of HT algorithms to be quantified. The power function, which gives the probability of rejection as a function of the underlying parametric distribution of data points, is shown to be the fundamentally important characteristic of HT behaviour. Attempting to make the power function narrow is a formal approach to optimizing HT performance. To illustrate how this framework is useful the particular problem of line detection is discussed in detail. It is shown that the hypothesis testing framework leads to a redefinition of the HT in which the values are a measure of the distribution of points around a curve rather than the number of points on a curve. This change dramatically improves the sensitivity of the method to small structures. The solution to many HT design problems can be posed within the framework, including optimal quantizations and optimum sampling of the parameter space. In this paper the authors consider the design of optimum I-D filters, which can be used to sharpen the peak structure in parameter space. Results on several real images illustrate the improvements obtained     

基于随机Hough变换的零基线正弦曲线检测

研究零基线正弦曲线的随机Hough变换的最小点集、收敛映射和动态链接表结构3个基本问题,提出改进的三点拟合零基线正弦曲线的方法,给出零基线正弦曲线的随机Hough变换检测算法,并分析算法的计算性能和存储量性能。仿真实验表明该方法的有效性。     

A Bayesian approach to the Hough transform for line detection

This paper explains how to associate a rigorous probability value to the main straight line features extracted from a digital image. A Bayesian approach to the Hough Transform (HT) is considered. Under general conditions, it is shown that a probability measure is associated to each line extracted from the HT. The proposed method increments the HT accumulator in a probabilistic way: first calculating the uncertainty of each edge point in the image and then using a Bayesian probabilistic scheme for fusing the probability of each edge point and calculating the line feature probability.     

一种在图象中检测网格直线的新方法

设计了一个扩展Robert算子,该算子能够在有噪声的情形下对图象中各种宽度的线条进行检测。当使用Hough变换确定直线的参数时,首先只用Hough变换检测第一条最为显著的直线,随后去掉该条直线及其附近的点,然后再次对图象进行Hough变换,并重复此过程,直到找到所有直线或者Hough变换后参数平面上的值都小于某个阈值为止。使用此改进后的Hough变换能够准确地检测到图象中构成网格的直线的参数。给出了具体的检测例子。     

Real-time precise detection of regular grids and matrix codes

The traditional approach in detecting sets of concurrent and/or parallel lines is to first detect lines in the image and then find such groups of them which meet the concurrence condition. The Hough Transform can be used for detecting the lines and variants of HT such as the Cascaded Hough Transform can be used to detect the vanishing points. However, these approaches disregard much of the information actually accumulated to the Hough space. This article proposes using the Hough space as a 2D signal instead of just detecting the local maxima and processing them. On the example of QRcode detection, it is shown that this approach is computationally cheap, robust, and accurate. The proposed algorithm can be used for efficient and accurate detection and localization of matrix codes (QRcode, Aztec, DataMatrix, etc.) and chessboard-like calibration patterns.     

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

Genetic Algorithm for the Extraction of Nonanalytic Objects from Multiple Dimensional Parameter Space

A new approach of the Hough transform is proposed, which makes use of the genetic searching algorithm. By using this proposed algorithm, we can resolve the main obstacle of the Hough transform, which demands an enormous amount of storage for the Hough space. The idea of this genetic Hough technique is applicable to the recognition of both analytic and nonanalytic patterns. Based on the analysis of peak formation in the 4D generalized Hough transform's parameter space, a fitness function is derived, which represents the statistical weight of the existence of desired objects. By using the genetic approach to extract peaks in the parameter space, the physical storage for the 4D Hough parameter domain is not required during the detection while the accuracy of the detected parameters can be significantly improved.     

基于改进Hough变换的车道线检测技术

为提高车道线识别的实时性和可靠性,提出了一种基于改进Hough变换的车道线检测方法;在图像预处理时对不同光照图像进行分类处理,得到二值化图像;利用极角约束Hough变换进行车道线初始定位;根据前一帧图像信息使用基于动态ROI的Hough变换进行车道跟踪;算法加入了车道线检测失效判别模块,以提高检测的可靠性;由于该方法减少了图像空间中被投票的目标点数,缩小Hough变换的投票空间,在一定程度上提高了车道检测的实时性和稳定性;实验结果表明,在结构化道路上,对于不同的路况,算法均具有较好的实时性和鲁棒性。     

Detecting line segments in an image – a new implementation for Hough Transform

The conventional Hough Transform is a technique for detecting line segments in an image. The conventional Hough Transform transforms image points into lines in the parameter space. If there are collinear image points, the lines transformed from the points intersect at a point in the parameter space. Determining the intersection is generally carried out through the “voting method”, which partitions the parameter space into squared meshes. A problem with the voting method involves determining the resolution required for partitioning the parameter space. In this paper, we present a solution to this problem. We propose to transform an image point into a belt, whose width is a function of the width of a line in the image. We then determine the intersection of numerous belts to detect a line segment. An iterated algorithm based the transformation for detecting line segments is presented in this paper.     

Fuzzy cell Hough transform for curve detection

In this paper a new variation of Hough Transform is proposed. It can be used to detect shapes or contours in an image, with better accuracy, especially in noisy images. The parameter space of Hough Transform is split into fuzzy cells which are defined as fuzzy numbers. This fuzzy split provides the advantage to use the uncertainty of the contour point location which is increased when noisy images are used. By using fuzzy cells, each contour point in the spatial domain contributes in more than one fuzzy cell in the parameter space. The array that is created after the fuzzy voting process is smoother than in the crisp case and the effect of noise is reduced. The curves can now be detected with better accuracy. The computation time that is slightly increased by this method, can be minimized in comparison with classical Hough Transform, by using recursively the fuzzy voting process in a roughly split parameter space, to create a multiresolution fuzzily split parameter space.     

A Real-Time Image Segmentation on a Massively Parallel Architecture

The method described in this paper enables the two end points of a straight line to be obtained by a Modified Double Hough Transform (MDHT). It consists respectively of line detection, followed by segment extraction. The significance of this work is that the hardware implementation is based on the Content Addressable Memory (CAM) concept. Hence, during the first HT, voting is achieved for the every scan line of image, not every edge pixel. Therefore, all the steps which form the first HT: voting, thresholding and local maximum are achieved in a low constant time. The two end points of the line are extracted through the second HT. Here, a local neighbor parallel search is also achieved at the end of each scan line of the image not at every edge pixel. Therefore, the execution time is low since the neighboring range does not exceed a few lines. Experimental results are given to show the accuracy of our approach for use in high performance pattern recognition systems.