Performance Prediction of the Hough Transform

Based on hree different implementation schemes,this paper strongly demonstrates that the performance of the Hough transform depends crucially on its implementation sceme when it is used for line detection.Moreover,the obtained results can be used as a theoretical basis to predict the performance of the Hough transform as well as to eliminate the noise in Hough space coming from image noise.     

Geometric constructions for predicting hough transform performance

Graphical techniques are presented for estimating Hough transform performance for detecting straight lines in noisy digital pictures. The methods show explicitly the influence of noise due, for example, to quantizing errors on the accuracy of estimating the underlying sets of collinear points. Exact bounds are obtained for sets of collinear points showing that under quite general conditions only the endpoints are of significance. Theorems governing grid size for the accumulator method are given.     

改进随机Hough变换在虹膜定位中的应用

针对随机Hough变换(RHT)中随机采样造成的大量无效采样和无效积累问题，提出了基于连续曲线段检测的RHT(CRHT)算法并应用于虹膜定位中，它利用了边缘图像的连续特性来减少无效采样的数量。实验结果证明，改进的CRHT变换提高了虹膜定位速度。     

基于Hough变换的圆形物体的检测

Hough变换在图像处理中占有重要地位,但本身具有存储空间大、计算时间长的缺点。利用圆的几何特性,针对Hough变换的缺点进行改进,并将其应用到图像中存在多个圆的情况。实验表明:该算法能较好地减少存储空间,并降低计算时间,同时,能很好地对图像中多个圆进行检测。     

A hough transform technique for subgraph isomorphism

The Generalized Hough Transform is an established technique for geometric shape matching. An analogous technique is presented here for approximate solution of subgraph isomorphism problems. Its chief advantages are that it can also be used to find partial isomorphisms and that it can be readily implemented in parallel on a network of simple processors.     

Inherent bias and noise in the hough transform

Considering the Hough transformation as a linear imaging process recasts certain well-known problems, provides a useful vocab-ulary, and possibly indicates a source of applicable literature on the behavior of the Hough transformation in various forms of noise. A consideration of the analytic form of peaks in parameter space sets the stage for the idea of using complementary (negative) votes to cancel off-peak positive votes in parameter space, thus sharpening peaks and reducing bias.     

快速随机Hough变换多圆检测算法

随机Hough变换是检测圆的一种有效方法,但在处理多圆复杂图像时随机采样带来的大量无效累积会导致计算量过大。文中提出一种基于随机Hough变换的快速多圆检测算法,除去三类噪声点,通过随机采样到的一点按照一定规则搜索另外两点来确定候选圆,用原始图像对候选圆进行证据积累以判断是否为真圆。理论分析和实验结果表明：该算法较其他算法能更快地检测出图像中的多个圆,具有较好的应用价值。     

基于Hough变换的地形图自动校正

利用Hough变换检测地形图中的方里网网点坐标,并由地形图图幅编号计算得到方里网网点的理论坐标,再把方里网网点的理论坐标与相应Hough变换搜索得到的方里网网点图像坐标进行最小二乘拟合,以纠正扫描地形图的误差得到精确的方里网网点坐标。结合该技术形成了自动扫描生成DRG的软件系统。     

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.     

New memory- and computation-efficient hough transform for detecting lines

The slope-intercept Hough transform (SIHT) is one of the two types of line-detection methods. However, the disadvantage of the SIHT is its low memory utilization, say 50%. Based on the affine transformation, this paper presents a new method to improve the memory utilization of the SIHT from 50% to 100%. According to the proposed affine transformation, we first present a basic SIHT-based algorithm for detecting lines. Instead of concerning floating-point operations in the basic SIHT-based algorithm, an improved SIHT-based algorithm, which mainly concerns integer operations, is presented. Besides the memory utilization advantage, experimental results reveal that the improved SIHT-based algorithm has more than 60% execution time improvement ratio when compared to the basic SIHT-based algorithm and has more than 33% execution time improvement ratio when compared to another type of line-detection methods, such as the (r,θ)-based HT algorithm and its variant. The detailed complexity analyses for all the related algorithms are also investigated and we show that the time complexity required in the improved SIHT-based algorithm is the least.     

Contribution to the prediction of performances of the hough transform

Exact predictions of the performances of the Hough detection of straight lines in two-dimensional images are presented for rectangular and circular retinas, in Cartesian and normal parameterization, in the case of noisy signals. Detection of circles, under the same assumptions, is discussed. The limits of adaptive quantization to reduce intrinsic noise are presented, and it is shown that a signal processing approach is especially convenient to measure the performances of a detector based on the Hough transform.     

Fourier extension and hough transform for multiple component FM signal analysis

Conventional representations in the time or frequency domain are inadequate for non-stationary signals which have statistical properties varying with time. In particular the advent of pulse compression techniques and the use of time varying chirp-type signals widespread in radar, sonar and seismic technologies means there is a need for time-frequency representation. We present a technique which extends the Fourier transform to non-stationary signals. We call the technique Fourier Extension analysis. We show that the analysis extends naturally to a time-frequency representation using the Hough transform projection, and investigate the resolutions obtainable with regard to separation of chirp signals compared with the usual matched filter approach common in radar processing. A visual interpretation of the magnitude and phase of the analytic results is introduced allowing a range of transform orders to be viewed simultaneously. Using frequency modulated signals, we demonstrate significantly higher resolution both in rate and time separation. Examples are given using synthetic and real world chirp signals illustrating improvements in time-frequency resolution using the new approach compared to the commonly used quadratic transforms.     

Randomised hough transform with error propagation for line and circle detection

In this paper, we introduce a new Randomised Hough Transform aimed at improving curve detection accuracy and robustness, as well as computational efficiency. Robustness and accuracy improvement is achieved by analytically propagating the errors with image pixels to the estimated curve parameters. The errors with the curve parameters are then used to determine the contribution of pixels to the accumulator array. The computational efficiency is achieved by mapping a set of points near certain selected seed points to the parameter space at a time. Statistically determined, the seed points are points that are most likely located on the curves and that produce the most accurate curve estimation. Further computational advantage is achieved by performing progressive detection. Examples of detection of lines using the proposed technique are given in the paper. The concept can be extended to non-linear curves such as circles and ellipses. ID="A1"Correspondance and offprint requests to: Q. Ji, Department of Electrical, Computer and Systems Engineering, Rensselaer Polytechnic Institute, Troy, NY 12180, USA. E-mail: qji@ecse.rpi.edu     

Generalized double hough transform in the problem of estimating shape symmetries

A sequential approach to estimating approximate symmetries of two-and three-dimensional shapes is proposed. A shape is described using a set of base k-point configurations such that the orbits of significant symmetries for each of them are found using Hough transforms fine-tuned to certain types of adjacent classes in the SO₃ manifold. Optimal solutions are found taking into account the ergodic property of the sequential random choice. Alexander P. Vinogradov. Born 1951. Graduated from the Moscow Institute of Physics and Technology in 1974. Received candidate’s degree in mathematical cybernetics in 1978. Scientific interests: geometric and algebraic methods in data analysis and image processing. Author of about 50 papers.     

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.     

Constant-time hough transform on the processor arrays with reconfigurable bus systems

We develop constant-time algorithms to compute the Hough transform on a processor array with a reconfigurable bus system (abbreviated to PARBS). The PARBS is a comptuation model which consists of a processor array and a reconfigurable bus system. It is a very powerful computation model in that many problems can be solved efficiently. In this paper, we introduce the concept of iterative-PARBS which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block in which the processing data can be routed through it several times. We can think it as a “hardware subroutine”. Based on this scheme, we are able to explore constant-time Hough transform algorithms on PARBS. The following new results are derived in this study:

1. The sum ofn bits can be computed in O(1) times on a PARBS with O(n ^1+?) processors for any fixed ?>0.
2. The weights of each simple path of ann*n image can be computed in O(1) time on a 3-D PARBS with O(n ^2+?) processors for any fixed ?>0.
3. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ^2+?) processors for any fixed ?>0 withp copies of the image pretiled.
4. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ³) processors.

     

An application of the hough transform to the recognition of printed hebrew characters

This paper describes computer recognition of printed Hebrew characters, in which the Hough Transform space is used as the feature domain. The sequentially built recognition scheme has a first stage coarse classification by end points of strokes and a second stage classifier divided into two parts: in one part the decision is based on matching features in the transform space and in the other part a structural classification is applied. The method was tested on a sample set of eighteen print-simulated alphabets and a recognition rate of 99.6% was achieved. A performance comparison with two other recognition methods is also given.     

The adaptive modulated wavelet transform image representation

In this paper, a new, called the adaptive modulated wavelet transform (AMWT) image representation is presented. One of the attractive features is that the informative instantaneous frequencies of images can be taken into account to improve the representation performance via adaptation of the modulating frequencies involved. The transform coefficients in both wavelet and modulated wavelet domains are uniformly quantized with several quantization levels. The computed peak signal-to-noise ratio values and entropies are used as rate distortion curves for performance comparison. Experimental results show that AMWT out performs wavelet transform for representing images containing textures with rapid variation in grays.     

The modified adaptive Hough transform (MAHT)

A fast and robust algorithm for extracting line segments from an image through use of the Hough Transform is presented. The framework for our algorithm comes from the work of Illingworth and Kittler. We have extended their Adaptive Hough Transform algorithm to handle lines of arbitrary slope, multiple lines, and lines in very low signal to noise environments. We present our Modified Adaptive Hough Transform along with experimental results obtained with data from a tactile sensor.     

Adaptive hough transform with optimized deep learning followed by dynamic time warping for hand gesture recognition

Multimedia Tools and Applications - Hand gesture is a natural interaction method, and hand gesture recognition is familiar in human–computer interaction. Yet, the variations, as well as the...