A Hough transform based line recognition method utilizing both parameter space and image space

Hough Transform (HT) is recognized as a powerful tool for graphic element extraction from images due to its global vision and robustness in noisy or degraded environment. However, the application of HT has been limited to small-size images for a long time. Besides the well-known heavy computation in the accumulation, the peak detection and the line verification become much more time-consuming for large-size images. Another limitation is that most existing HT-based line recognition methods are not able to detect line thickness, which is essential to large-size images, usually engineering drawings. We believe these limitations arise from that these methods only work on the HT parameter space. This paper therefore proposes a new HT-based line recognition method, which utilizes both the HT parameter space and the image space. The proposed method devises an image-based gradient prediction to accelerate the accumulation, introduces a boundary recorder to eliminate redundant analyses in the line verification, and develops an image-based line verification algorithm to detect line thickness and reduce false detections as well. It also proposes to use pixel removal to avoid overlapping lines instead of rigidly suppressing the N×N neighborhood. We perform experiments on real images with different sizes in terms of speed and detection accuracy. The experimental results demonstrate the significant performance improvement, especially for large-size images.     

A new and efficient transform for curve detection

A new transform for curve detection, called the Curve-Fitting Hough Transform (CFHT), is proposed. In the conventional Hough Transform (HT) and its variants, both storage and computation grow exponentially with the number of parameters. The CFHT is advantageous over the conventional HT and variants in its high speed, small storage, arbitrary parameter range, and high parameter resolution. This is achieved by fitting a segment of the curve to be detected to a small neighborhood of edge points. If the fitting error is less than a given threshold, the parameters obtained from curve fitting are used to map an edge element to a single point in the parameter space. A multidimensional ordered parameter list is used to accumulate the occurrences of the curve to be detected.     

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 neural implementation of the Hough transform and the advantages of explaining away

The Hough transform (HT) is widely used for feature extraction and object detection. However, during the HT individual image elements vote for many possible parameter values. This results in a dense accumulator array and problems identifying the parameter values that correspond to image features. This article proposes a new method for implementing the voting process in the HT. This method employs a competitive neural network algorithm to perform a form of probabilistic inference known as “explaining away”. This results in a sparse accumulator array in which the parameter values of image features can be more accurately identified. The proposed method is initially demonstrated using the simple, prototypical, task of straight line detection in synthetic images. In this task it is shown to more accurately identify straight lines, and the parameter of those lines, compared to the standard Hough voting process. The proposed method is further assessed using a version of the implicit shape model (ISM) algorithm applied to car detection in natural images. In this application it is shown to more accurately identify cars, compared to using the standard Hough voting process in the same algorithm, and compared to the original ISM algorithm.     

Optimising the application of the Hough transform for automatic feature extraction from geoscientific images

We have adapted the Hough transform to extract linear features successfully from geoscientific datasets. The Hough transform is used in an automatic technique, which makes use of a parameter space to describe features of interest in images. This method has been widely applied in machine vision for recognition of features in highly structured images. Geoscientific data is more demanding. Features of interest within scenes of natural environments exist on all scales, are often partially obscured and the images are usually noisy. Pre-processing of images before the HT is essential. Adaptations of the HT to cope with particular properties of geoscientific data include: optimising the dimensions of the discrete transform domain; using feature-modelling to cancel lines found; transforming multi-scale tiles of the original image and correcting amplitudes in the transformed domain to account for the position of features. These specific adaptations produce a method for automatic feature detection which requires the user to select only two parameters. Output of the procedure is rich in feature content and accurate, leaving a clean result for statistical analysis. This optimised HT is robust for natural scenes, coping in particular with short line-segments.     

Detection of linear and planar structures in 3D subsurface images by iterative dimension reduction

A unified framework for detecting both linear and planar structures in three-dimensional (3D) images is developed. The method uses an iterative detection and removal strategy. The dimension reduction scheme reduces the search space for lines by first finding 2D planes and then searching for lines in the selected planes only. Thus the computational time of the method is lower than the 3D Hough Transform (HT) for lines. The proposed method is tested using experimental Ground Penetrating Radar (GPR) data taken over buried pipes, however the method is general enough to be applied to any situation where linear or planar structures need to be identified in 3D data.     

A Hough transform for detecting the location and orientation ofthree-dimensional surfaces via color encoded spots

Video-rate three-dimensional (3-D) acquisition is desirable, in particular for capturing the mouth's shape when modeling the vocal tract. In a new structured light technique, scenes are illuminated by an array of circular spots which are color encoded to resolve spatial ambiguity. The position and shape of the imaged spots depend on the location and orientation of the illuminated 3-D surface. We present a novel 3-D Hough transform (HT) to detect 3-D surface location and orientation via the imaged spots, with voting constraints applied to maximize potential accuracy. This new technique is demonstrated to successfully extract the 3-D data for a moving face from images acquired at video-rate.     

用改进的前向神经网络实现离散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.     

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

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

一种快速的人工场景图像消失点检测方法

人工场景中包含了大量的空间平行线以及垂直边,这些空间平行线映射到图像中相交产生的交点即消失点。消失点检测对摄像机标定、三维场景重建等都有着重要的意义。传统的消失点检测算法往往基于二维霍夫参数空间,复杂度高、效率低。因此,提出一种新的方法,先检测图像中较长的边界线,并将检测到的线段进行筛选、分组;然后利用消失点与焦距之间的制约关系,确定三向消失点的位置以及焦距的大小。该方法将传统的二维霍夫参数空间转换为二级一维霍夫参数空间。实验表明,这种方法运算复杂度低、运行时间短。在室外场景图像中,鲁棒性好,且保持较高的准确率。     

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

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

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

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

A novel Hough transform based on eliminating particle swarm optimization and its applications

Hough transform (HT) is a well established method for curve detection and recognition due to its robustness and parallel processing capability. However, HT is quite time-consuming. In this paper, an eliminating particle swarm optimization (EPSO) algorithm is employed to improve the speed of a HT. The parameters of the solution after Hough transformation are considered as the particle positions, and the EPSO algorithm searches the optimum solution by eliminating the “weakest” particles to speed up the computation. An accumulation array in Hough transformation is utilized as a fitness function of the EPSO algorithm. The experiments on numerous images show that the proposed approach can detect curves or contours of both noise-free and noisy images with much better performance. Especially, for noisy images, it can archive much better results than that obtained by using the existing HT algorithms.     

用于形状检测的极标编码多分辨率Hough变换

本文提出一种利用Hough变换作形状检测的方法,称为极标编码多分辨率Hough变 换,它将模板和图象都用极坐标表示为一维序列,这不但简化了Hough变换的映射运算,而 且借此可以构成图象空间和参数空间对等的多分辨率描述,使检测可由低分辨率向高分辨率 以一种类似树搜索的方式高效地实现.文中给出了实验结果.     

Houhg变换OCR图象倾斜矫正方法

在光学字符识别（OCR）图象扫描输入的过程中,扫描图象或多或少会出现某种程度的倾斜,这种图象的倾斜不仅会给下一步字符的切割造成困难,也影响最终的字符识别精度,通常情况下,为避免用户重新扫描,可以通过软件方法对图象进行矫正,为此提出一种利用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.     

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.     

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.