Real-time CAM-based Hough transform algorithm and its performance evaluation

Abstract. This paper proposes a highly parallel Hough transform algorithm for real-time straight-line extraction and its hardware implementation on a content-addressable memory (CAM). To achieve high-speed processing, incrementation for voting, which composes the Hough transform, and calculations for coordinate updating are carried out for the every scan line, not every edge pixel, and extracting maxima in Hough space is executed by parallel comparing. Moreover, variously weighted voting achieves more accurate line extraction in spite of the quantization error and noise in the image space. In the implementation, the CAM acts as a PE (processing-element) array that effectively performs highly parallel processing for the Hough transform and also as a memory for two-dimensional Hough space, and both voting and peak extraction are directly executed by the CAM. Evaluations of CAM hardware size, processing time and the accuracy of line extraction show that a real-time and high-resolution Hough transform for a 256256 picture can be achieved using a single CAM chip with current VLSI technology. This CAM-based Hough transform algorithm promises to be an important step towards the realization of a real-time and compact image-understanding system. Received: 15 August 1998 / Accepted: 15 March 2000     

SLIDE: subspace-based line detection

An analogy is made between each straight line in an image and a planar propagating wavefront impinging on an array of sensors so as to obtain a mathematical model exploited in recent high resolution methods for direction-of-arrival estimation in sensor array processing. The new so-called SLIDE (subspace-based line detection) algorithm then exploits the spatial coherence between the contributions of each line in different rows of the image to enhance and distinguish a signal subspace that is defined by the desired line parameters. SLIDE yields closed-form and high resolution estimates for line parameters, and its computational complexity and storage requirements are far less than those of the standard method of the Hough transform. If unknown a priori, the number of lines is also estimated in the proposed technique. The signal representation employed in this formulation is also generalized to handle grey-scale images as well. The technique has also been generalized to fitting planes in 3-D images. Some practical issues of the proposed technique are given     

A system to understand hand-drawn floor plans using subgraph isomorphism and Hough transform

Presently, man-machine interface development is a widespread research activity. A system to understand hand drawn architectural drawings in a CAD environment is presented in this paper. To understand a document, we have to identify its building elements and their structural properties. An attributed graph structure is chosen as a symbolic representation of the input document and the patterns to recognize in it. An inexact subgraph isomorphism procedure using relaxation labeling techniques is performed. In this paper we focus on how to speed up the matching. There is a building element, the walls, characterized by a hatching pattern. Using a straight line Hough transform (SLHT)-based method, we recognize this pattern, characterized by parallel straight lines, and remove from the input graph the edges belonging to this pattern. The isomorphism is then applied to the remainder of the input graph. When all the building elements have been recognized, the document is redrawn, correcting the inaccurate strokes obtained from a hand-drawn input. Received 6 June 1996 / Accepted 4 February 1997     

Intermediate-level feature extraction in novel parallel environments

Abstract. Parallel systems provide an approach to robust computing. The motivation for this work arises from using modern parallel environments in intermediate-level feature extraction. This study presents parallel algorithms for the Hough transform (HT) and the randomized Hough transform (RHT). The algorithms are analyzed in two parallel environments: multiprocessor computers and workstation networks. The results suggest that both environments are suitable for the parallelization of HT. Because scalability of the parallel RHT is weaker than with HT, only the multiprocessor environment is suitable. The limited scalability forces us to use adaptive techniques to obtain good results regardless of the number of processors. Despite the fact that the speedups with HT are greater than with RHT, in terms of total computation time, the new parallel RHT algorithm outperforms the parallel HT. Received: 8 December 2001 / Accepted: 5 June 2002 Correspondence to: V. Kyrki     

Hough Array Processing via Fast Multi-Scale Clustering

The major emphasis in fast Hough transform algorithms has been placed on the transformation involved. Little attention has been paid to fast processing of a Hough array without requiring one to specify a threshold value to determine candidate parameters in the Hough array. This paper gives a comprehensive discussion of Hough array processing as a part of Hough transform, and presents a time efficient clustering algorithm, called Fast Multi-Scale Clustering, to obtain the number of and hence to select the locations of candidate parameters in a Hough array in a threshold independent manner. It is shown that the complexity of this algorithm is O (nd^r) where n is the number of non-zero cells in the Hough array, d is the number of cells used in the discretization of the corresponding parameter space, and r is the dimensionality of the Hough array. Two examples of line and circle detection are provided to illustrate the steps involved in deploying this Hough array processing approach.     

A Robust Hough Transform Technique for Complete Line Segment Description

When the Hough transform is applied to the detection of straight lines in images, it provides the parameters but not the length or the end points of the line. We propose a new algorithm for the determination of the length and the end points of a line in an image. It is very efficient in terms of computing time and does not depend on the sharpness of the peak in the accumulator array.     

基于Hough变换提取直线的改进方法研究

传统的Hough变换用于检测直线时,存在不能确定直线端点、会检测出虚假直线以及对称地额外画出直线的问题,文章针对这些特点对Hough变换加以改进,经过实践检验,提取的特征较完整,改进效果较理想。     

宽线段Hough变换及其在箭靶识别上的应用

Hough变换是用于检测图像中直线段的有力工具。论文提出的宽线段Hough变换针对传统Hough变换进行了改进,使之适用于多条宽线段同时存在的情况,并且解决了端点提取的问题。该方法应用于箭靶识别取得了很好的效果,实验表明对比传统方法具有较大优势。     

基于扫描线处理的指针式仪表快速读数算法

针对光照不均匀、指针检测速度过慢等因素造成指针式仪表读数算法无法快速、准确读取示数的问题,提出一种基于扫描线处理的快速准确读数新算法。新算法首先利用单尺度Retinex提取光照鲁棒性特征图像,然后应用提出的扫描线处理算法快速抽取进行Hough变换的特征像素点,最后用双阈值Hough变换检测直线。实验表明,所提算法创新性地将指针图像细化与双阈值Hough变换等相结合,不仅解决了光照变化的影响以及检测速度慢等问题,而且具有读数精度高、读取速度可调节等特点。     

A protocol for performance evaluation of line detection algorithms

Accurate and efficient vectorization of line drawings is essential for any higher level processing in document analysis and recognition systems. In spite of the prevalence of vectorization and line detection methods, no standard for their performance evaluation protocol exists. We propose a protocol for evaluating both straight and circular line extraction to help compare, select, improve, and even design line detection algorithms to be incorporated into line drawing recognition and understanding systems. The protocol involves both positive and negative sets of indices, at pixel and vector levels. Time efficiency is also included in the protocol. The protocol may be extended to handle lines of any shape as well as other classes of graphic objects.     

基于Hough变换的建筑边缘特征检测的研究及其改进

Hough变换是对二值图像进行直线检测的有效方法,介绍了Hough变换直线检测对房屋边缘特征检测方法及实验结果,并根据其存在的缺点提出了检测矩形的Hough变换的改进算法.     

Finding circular shapes in an image on a pyramid architecture

The problem of finding circular shapes in an image using a pyramid architecture is considered. In this paper we have defined a new transformation that converts circles in an image to a family of straight lines allowing the problem to be converted to line detection which can be solved by Hough transform algorithms. Also, based on this new transformation we have developed two algorithms for circle detection using a pyramid architecture.     

An unconstrained handwriting recognition system

In this paper, an integrated offline recognition system for unconstrained handwriting is presented. The proposed system consists of seven main modules: skew angle estimation and correction, printed-handwritten text discrimination, line segmentation, slant removing, word segmentation, and character segmentation and recognition, stemming from the implementation of already existing algorithms as well as novel algorithms. This system has been tested on the NIST, IAM-DB, and GRUHD databases and has achieved accuracy that varies from 65.6% to 100% depending on the database and the experiment.     

黑白棋盘网格中的直线检测方法研究

黑白棋盘网格的直线检测在摄像机标定中具有重要的应用价值。针对黑白棋盘网格图像的特点及传统Hough变换直线检测方法中参数选择敏感的不足,在Hough变换的基础上进行了后续处理,结合最小二乘法获得黑白棋盘网格图像中的直线信息。最后,通过大量真实图像实验验证了方法的可行性,并与传统Hough变换方法及其改进方法进行了比较。     

Efficient extraction of primitives from line drawings composed of horizontal and vertical lines

The performance of the algorithms for the extraction of primitives for the interpretation of line drawings is usually affected by the degradation of the information contained in the document due to factors such as low print contrast, defocusing, skew, etc. In this paper, we are proposing two algorithms for the extraction of primitives with good performance under degradation. The application of the algorithms is restricted to line drawings composed of horizontal and vertical lines. The performance of the algorithms has been evaluated by using a protocol described in the literature. Received: 6 August 1996 / Accepted: 16 July 1997     

基于分级的快速霍夫变换直线检测

在分析标准霍夫变换、两点表决霍夫变换以及多级霍夫变换直线检测的基础上，针对算法的不足，结合他们的优点，设计并实现了基于分级的快速霍夫变换直线检测方法，对算法进行了详细描述和分析，并通过实验证明了算法的有效性，实验表明：所设计的直线检测运算速度快，检测精度高，鲁棒性强，有一定的应用价值。     

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

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

Extension of the Nicholls-Lee-Nichols algorithm to three dimensions

A new algorithm for clipping a line segment against a pyramid in E ³ is presented. This algorithm avoids computation of intersection points that are not end points of the output line segment. It also solves all cases more effectively. The performance of this algorithm is shown to be consistently better than that of existing algorithms, including the Cohen–Sutherland, Liang–Barsky, and Cyrus–Beck algorithms.     

Hough transform algorithms for mesh-connected SIMD parallel processors

Hough transform techniques for straight line detection play a key role in the road following algorithms developed by the University of Maryland for the DARPA Autonomous Land Vehicle Project. This report compares several methods of Hough transform computation suitable for implementation on a mesh-connected SIMD parallel processor, such as Goddard Space Flight Center's Massively Parallel Processor (MPP) or Martin Marietta Corp.'s Geometric Arithmetic Parallel Processor (GAPP).