A Fast Hough Transform for the Parametrisation of Straight Lines using Fourier Methods

The Hough transform is a useful technique in the detection of straight lines and curves in an image. Due to the mathematical similarity of the Hough transform and the forward Radon transform, the Hough transform can be computed using the Radon transform which, in turn, can be evaluated using the central slice theorem. This involves a two-dimensional Fourier transform, an x-y to r-θ mapping and a 1D Fourier transform. This can be implemented in specialized hardware to take advantage of the computational savings of the fast Fourier transform. In this paper, we outline a fast and efficient method for the computation of the Hough transform using Fourier methods. The maxima points generated in the Radon space, corresponding to the parametrisation of straight lines, can be enhanced with a post transform convolutional filter. This can be applied as a 1D filtering operation on the resampled data whilst in the Fourier space, so further speeding the computation. Additionally, any edge enhancement or smoothing operations on the input function can be combined into the filter and applied as a net filter function.     

An O(log n) pyramid hough transform

This paper describes a divide-and-conquer Hough transform technique for detecting a given number of straight edges or lines in an image. This technique is designed for implementation on a pyramid of processors, and requires only O(log n) computational steps for an image of size n × n.     

基于数学形态学与Hough变换的乐谱谱线探测算法研究

数学形态学是综合了多学科知识的交叉学科,是一种非线性的图像分析理论,己成为图像处理的重要工具之一。文章简单介绍了数学形态学和二值形态学的基本运算—腐蚀和膨胀,并提出了基于数学形态学的乐谱谱线探测算法。实验结果证明,与Hough变换探测直线算法相比,该乐谱谱线探测算法具有运算速度快、效率高、抗噪声能力强等优点。     

基于归一化灰度Hough变换的SAR图像舰船尾迹检测算法

舰船尾迹检测作为近年来SAR图像海洋应用的一个重要方面而受到关注。目前大多数研究都是利用Radon变换作为数学工具，结果得到增强的是尾迹特征，而不是尾迹的端点。从提取尾迹的端点坐标出发，在传统Hough变换算法基础上进行改进，提出了基于归一化灰度Hough变换的SAR图像舰船尾迹检测算法，并推导出尾迹端点反演算法，同时自动提取舰船的航速，取得了较好的实验结果。     

基于RAPWBN模型的快速高效Hough变换并行算法

提出了RAPWBN模型上的整数前缀和与抽取压缩操作算法，并由此得到了RAPWBN模型上的快速高效Hough变换并行算法，对于大小为n×n的二值数字图像，p个θ参数值。可以使用pn2个处理器在O(1)时间完成。使算法的速度和效率达到了最优。     

Improvements and systolic implementation of the hough transformation for straight line detection

Hough Transformation (HT) is an efficient method to detect straight lines in digital pictures. In the conventional HT, pixel contiguity is not taken into account, and this leads to the following drawbacks: (1) actual length of line segments cannot be computed; (2) colinear line segments cannot be distinguished; and (3) very often, false lines are detected and short lines go undetected. This paper proposes a modified Hough Transformation which performs contiguity check in a simple and efficient way. A systolic architecture that implements this modified transform is presented. The systolic array takes the bit-map of the binary picture as input and processes one row/column of pixels concurrently. The area-time complexity of the proposed architecture is shown to be superior to the conventional sequential algorithm. Preliminary simulation results are presented.     

水下人造目标线特征快速检测算法

为了从水下复杂场景中快速检测人造目标,提出了一种在图像小波变换低频子带上进行直线实时检测的算法。首先,利用小波变换确定显著线特征检测的合适尺度;然后在确定的低频子带小图像上进行边缘检测,利用梯度直方图和迭代法相结合自适应确定边缘检测的分割阈值,得到显著特征的边缘点;再利用改进的Hough变换检测人造目标的直线特征;最后在原始图像上标记出直线检测的结果。实验结果表明:提出的算法可以准确检测出水下复杂背景中人造目标的直线特征,并且具有良好的实时性,满足水下人造目标视频检测的应用要求。     

基于Finite Ridgelet变换的图像线性特征提取

线性特征是图像的一种重要局部特征,它常常决定图像中目标的形状。线性特征的提取在图像匹配、目标描述与识别以及运动估计、目标跟踪等领域具有十分重要的意义。常用的线性特征检测方法有Radon变换和Hough变换,但检测曲线复杂度会很高。本文提出一种多尺度几何分析的线性特征检测方法,该方法以finite ridgelet理论为基础,结合正交小波变换对线性特征进行提取。Finite ridgelet变换对于含有直线奇异的多变量函数具有良好的逼近特性,能够获得连续空间函数的稀疏表达,同时具有区域平滑性、很好的可逆性和去冗余性。实验结果表明,本方法即使在背景复杂的环境下也具有良好的检测效果。     

The generalized Radon transform: Sampling, accuracy and memory considerations

The generalized Radon (or Hough) transform is a well-known tool for detecting parameterized shapes in an image. The Radon transform is a mapping between the image space and a parameter space. The coordinates of a point in the latter correspond to the parameters of a shape in the image. The amplitude at that point corresponds to the amount of evidence for that shape. In this paper we discuss three important aspects of the Radon transform. The first aspect is discretization. Using concepts from sampling theory we derive a set of sampling criteria for the generalized Radon transform. The second aspect is accuracy. For the specific case of the Radon transform for spheres, we examine how well the location of the maxima matches the true parameters. We derive a correction term to reduce the bias in the estimated radii. The third aspect concerns a projection-based algorithm to reduce memory requirements.     

适用于机场跑道识别的改进Hough变换

机场跑道的卫星图片经过处理后表现出来的骨架特征为边缘直线,在边缘图像中检测直线通常使用的方法是Hough变换（HT）.由于（HT）是一种穷举式的搜索,在处理复杂图像时存在大量无效计算,实时性较差.针对机场跑道识别的实时性要求,提出一种改进的用于在二值图像中检测直线的快速Hough变换算法,此算法克服了标准Hough变换以图像边界点为扫描边界的缺点,并且能及时中断无谓的扫描,较好地解决了无效累积问题,实验证明,与标准Hough变换相比,它不仅具备Hough变换原有的高可靠性和抗干扰能力,而且具备Hough变换所不具备的高效性和低存储,克服了标准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     

Hough transform from the radon transform

An appropriate special case of a transform developed by J. Radon in 1917 is shown to have the major properties of the Hough transform which is useful for finding line segments in digital pictures. Such an observation may be useful in further efforts to generalize the Hough transform. Techniques for applying the Radon transform to lines and pixels are developed through examples, and the appropriate generalization to arbitrary curves is discussed.     

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

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

An improved constant-time algorithm for computing the Radon andHough transforms on a reconfigurable mesh

The Hough transform is an important problem in image processing and computer vision. An efficient algorithm for computing the Hough transform has been proposed on a reconfigurable array by Kao et al. (1995). For a problem with an √N×√N image and an n×n parameter space, the algorithm runs in a constant time on a three-dimensional (3-D) n×n×N reconfigurable mesh where the data bus is N¹c/-bit wide. To our best knowledge, this is the most efficient constant-time algorithm for computing the Hough transform on a reconfigurable mesh. In this paper, an improved Hough transform algorithm on a reconfigurable mesh is proposed. For the same problem, our algorithm runs in constant time on a 3-D n*n×n×√n√n reconfigurable mesh, where the data bus is only log N-bit wide. In most practical situations, n=O(√N). Hence, our algorithm requires much less VLSI area to accomplish the same task. In addition, our algorithm can compute the Radon transform (a generalized Hough transform) in O(1) time on the same model, whereas the algorithm in the above paper cannot be adapted to computing Radon transform easily     

A fast Hough Transform algorithm for straight lines detection in an image using GPU parallel computing with CUDA-C

The Hough Transform (HT) is a digital image processing method for the detection of shapes which has multiple uses today. A disadvantage of this method is its sequential computational complexity, particularly when a single processor is used. An optimized algorithm of HT for straight lines detection in an image is presented in this article. Optimization is realized by using a decomposition of the input image recently proposed via central processing unit (CPU), and the technique known as segment decomposition. Optimized algorithms improve execution times significantly. In this paper, the optimization is implemented in parallel using graphics processing unit (GPU) programming, allowing a reduction of total run time and achieving a performance more than 20 times better than the sequential method and up to 10 times better than the implementation recently proposed. Additionally, we introduce the concept of Performance Ratio, to emphasize the outperforming of the GPU over the CPUs.     

改进随机Hough变换在心肌纤维图像直线检测中的应用

利用改进的随机Hough变换被用来对心肌纤维方向进行了检测。针对心肌纤维边缘的特点,采用窗口对投票点对加以筛选,同时利用模糊映射对Hough变换投票在变换空间加以修正,使随机Hough变换能够较好的用于复杂非规则直线段的检测,提高了利用Hough变换检测心肌纤维方向的正确率。     

Generalized Fuzzy Hough Transform for Detecting Arbitrary Shapes in a Vague and Noisy Image

A generalized Hough transform is an effective method for an arbitrary shape detection in a contour image. However, the conventional generalized Hough transform is not suitable for a noisy and blurred image. This paper describes a generalized fuzzy Hough transform which is derived by fuzzifying the vote process in the Hough transform. The present generalized fuzzy Hough transform enables a detection of an arbitrary shape in a very noisy, blurred, and even distorted image. The effectiveness of the present method has been confirmed by some preliminary experiments for artificially produced images and for actual digital images taken by an ordinary digital camera     

A convolution approach to the circle Hough transform for arbitrary radius

The Hough transform is a well-established family of algorithms for locating and describing geometric figures in an image. However, the computational complexity of the algorithm used to calculate the transform is high when used to target complex objects. As a result, the use of the Hough transform to find objects more complex than lines is uncommon in real-time applications. We describe a convolution method for calculating the Hough transform for finding circles of arbitrary radius. The algorithm operates by performing a three-dimensional convolution of the input image with an appropriate Hough kernel. The use of the fast Fourier transform to calculate the convolution results in a Hough transform algorithm with reduced computational complexity and thus increased speed. Edge detection and other convolution-based image processing operations can be incorporated as part of the transform, which removes the need to perform them with a separate pre-processing or post-processing step. As the Discrete Fourier Transform implements circular convolution rather than linear convolution, consideration must be given to padding the input image before forming the Hough transform.     

Parallel processing approaches to edge relaxation

This paper describes several parallel algorithms for image edge relaxation on array processors with different numbers of processing elements (PEs) connected by a mesh or hypercube network. The time complexity of Prager's original edge relaxation scheme is O(N²) per iteration using floating-point operations on a sequential machine, where N² is the number of pixels in the image. Modifications to the scheme are made so that no multiplications are employed and only integer operations are required. Moreover, with parallel processing, the time complexity per iteration is reduced to some constant value. A time complexity analysis on two parallel algorithms is performed. Although the algorithm on an array processor with 4N² PEs achieved higher degree of parallelism, the algorithm with N² PEs is preferred. Further modifications on the latter algorithm are made to accommodate to fewer PEs.