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     

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变换的椭圆检测算法(如RHT算法)存在着占用大量存储空间及计算耗时等缺点。本文提出一种高效随机的椭圆检测算法(RED)。该算法不基于Hough变换,其原理是:首先从一幅图像中随机地挑选出6个点,并定义一个约束距离以确定在此图像中是否存在一个可能的椭圆;当可能椭圆确定之后,引入椭圆点收集过程以进一步确定可能椭圆是否是待检测的真实椭圆。通过对具有不同噪声的合成图像以及真实图像进行测试,结果表明RED算法在低噪声与适度噪声的情况下,速度明显快于RHT算法。     

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.     

New shape-based auroral oval segmentation driven by LLS-RHT

A new method that exploits shape to localize the auroral oval in satellite imagery is introduced. The core of the method is driven by the linear least-squares (LLS) randomized Hough transform (RHT). The LLS-RHT is a new fast variant of the RHT suitable when not all necessary conditions of the RHT can be satisfied. The method is also compared with the three existing methods for aurora localization, namely the histogram-based k-means [C.C. Hung, G. Germany, K-means and iterative selection algorithms in image segmentation, IEEE Southeastcon 2003 (Session 1: Software Development)], adaptive thresholding [X. Li, R. Ramachandran, M. He, S. Movva, J.A. Rushing, S.J. Graves, W. Lyatsky, A. Tan, G.A. Germany, Comparing different thresholding algorithms for segmenting auroras, in: Proceedings of the International Conference on Information Technology: Coding and Computing, vol. 6, 2004, pp. 594-601], and pulse-coupled neural network-based [G.A. Germany, G.K. Parks, H. Ranganath, R. Elsen, P.G. Richards, W. Swift, J.F. Spann, M. Brittnacher, Analysis of auroral morphology: substorm precursor and onset on January 10, 1997, Geophys. Res. Lett. 25 (15) (1998) 3042-3046] methods. The methodologies and their performance on real image data are both considered in the comparison. These images include complications such as random noise, low contrast, and moderate levels of key obscuring phenomena.     

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

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

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

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

基于梯度的随机Hough快速圆检测方法

针对随机Hough变换(RHT)在复杂图像中检测圆时产生随机采样的大量无效累积,提出了一种改进的RHT用于圆检测,方法利用梯度方向信息来判定是否对采样到的三点进行参数累积,从而较好地解决了无效累积问题。实验表明改进后的算法比原算法计算速度快,占用的内存小,检测性能有较大提高。     

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     

基于相位编组图像分块的快速Hough变换直线检测

在分析Hough变换直线检测算法和相位编组法直线检测算法的基础上,针对这两个直线检测算法的不足,结合它们的优点,设计并实现了基于相位编组图像分块的快速Hough变换直线检测算法,对算法进行了详细描述和算法优点分析,并通过实验验证了算法的有效性,实验表明所设计的直线检测算法运算速度快,参数易于选择,鲁棒性强,有一定的应用价值。     

基于中心提取的RHT在椭圆检测中的应用

充分利用椭圆的几何性质,借助椭圆的形状控制点约束和弦端点法向约束,大幅降低随机Hough变换(RHT)的无效采样和累积次数,并采用基于视觉感知聚类的模糊置信度对由同一个形变椭圆引入的多个虚假候选椭圆进行有效去除.实验结果表明:该算法与基于RHT的其他椭圆检测方法相比,具有检测速度快、精度高、抵抗椭圆的部分缺失和形变能力强等优点.     

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

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

基于随机Hough变换的深度图像分割

提出了基于随机Hough变换的深度图像分割算法,该算法采用随机Hough变换在深度图像中寻找平面,具有对噪声不敏感的优点．通过对一常用深度图像数据库(ABW图像库)的分割实验,并将实验结果同4种经典的深度图像分割算法在同一数据库中的分割结果作了比较分析,表明该算法对噪声不敏感,分割性能优于4种经典算法。     

一种基于随机Hough变换圆检测的改进算法

介绍了一种基于随机Hough变换(RHT)的圆检测的改进算法。该算法利用梯度方向信息来确定采样的三点是否进行累积,然后再利用确定候选圆范围的方法来缩小所要搜索的像素点的范围。此方法较好地解决了传统RHT中由于随机采样而造成的大量无效累积问题,并且改进后的算法使运行速度得到进一步的提高,检测性能也有较大的改善。该算法分别在加噪和不加噪的人工图像上做了实验,检测性能和处理速度方面都比传统的RHT有明显的改善和提高。     

基于FPGA的实时Hough变换

为解决Hough变换实时性差的问题,提出一种基于现场可编程门阵列的实时Hough变换方法。采用分角度映射方法使Hough变换在空间上并行运算。设计一种基于流水线的计算结构,实现Hough空间参数计算与存储的时间并行性。通过双口RAM,在单个时钟内完成参数空间的一次投票操作,提出一种适合在FPGA中实现的快速寻找极值的二次搜索算法。与DSP进行效率对比实验,结果表明该方法效率较高,能满足实时性处理要求。     

A circle-detection algorithm simulating wave propagation

Based on the analogy of the Hough transform and Huygens's principle, we present a circle-detection algorithm that numerically solves a two-dimensional wave equation using neighbor-based operations only, that is, Laplacian, frame addition, and multiplication of constants with frame contents, all basic functions of standard image processors. Because it does not use edge extraction, the algorithm detects circles even from low-contrast and blurred images. A comparison of point spread functions shows the algorithm to be equivalent to the weighted Hough transform but requiring much less computation. We applied the algorithm to disk-surface inspection of low-contrast and blurred microscopic images.     

Accurate and efficient curve detection in images: the importance sampling Hough transform

The Hough transform is a well known technique for detecting parametric curves in images. We place a particular group of Hough transforms, the probabilistic Hough transforms, in the framework of importance sampling. This framework suggests a way in which probabilistic Hough transforms can be improved: by specifying a target distribution and weighting the sampled parameters accordingly to make identification of curves easier. We investigate the use of clustering techniques to simultaneously identify multiple curves in the image. We also use probabilistic arguments to develop stopping conditions for the algorithm. Results from applying our method and two popular versions of the Hough transform to both simulated and real data are shown.     

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

圆形(包括弧线)检测是数字图像处理过程中的经典问题之一,有着广泛的应用背景。基本的Hough变换方法是将图像中的每一边缘点映射到参数空间的一个区域,选取累积最多的参数。在现实生活中,由于噪音、数字化错误和图形变异等因素真实的图形经常被曲解,因此,图像在应用Hough变换后,很难找到单一的峰值,这也就造成了检测的难度。在Hough变换的原理基础上利用圆的几何特征提出了改进算法。理论和实验证明能获得较好的检测结果。     

Computing Hough transforms on hypercube multicomputers

Efficient algorithms to compute the Hough transform on MIMD and SIMD hypercube multicomputer are developed. Our algorithms can compute p angles of the Hough transform of an N × N image, p N, in 0(p + log N) time on both MIMD and SIMD hypercubes. These algorithms require 0(N ²) processors. We also consider the computation of the Hough transform on MIMD hypercubes with a fixed number of processors. Experimental results on an NCUBE/7 hypercube are presented.This research was supported by the National Science Foundation under grants DCR84-20935 and 86-17374. All correspondence should be mailed to Sanjay Ranka.