Fast circle detection algorithm using sequenced Hough transform

YE Feng; CHEN Can-jie; LAI Yi-zong; CHEN Jian-dong

doi:10.3788/OPE.20142204.1105

您当前的位置：

首页 >

文章列表页 >

Fast circle detection algorithm using sequenced Hough transform

Information Sciences | 更新时间：2020-08-13

- Fast circle detection algorithm using sequenced Hough transform
- Optics and Precision Engineering Vol. 22, Issue 4, Pages: 1105-1111(2014)
- 作者机构：
  
  华南理工大学机械与汽车工程学院,广东广州,中国,510640
- 作者简介：
- 基金信息：
- DOI：10.3788/OPE.20142204.1105
  CLC： TP391.41
- Received：15 August 2013，
  
  Revised：22 September 2013，
  
  Published：25 April 2014
- 稿件说明：
移动端阅览
叶峰, 陈灿杰, 赖乙宗等. 基于有序Hough变换的快速圆检测算法[J]. 光学精密工程, 2014,22(4): 1105-1111

YE Feng, CHEN Can-jie, LAI Yi-zong etc. Fast circle detection algorithm using sequenced Hough transform[J]. Editorial Office of Optics and Precision Engineering, 2014,22(4): 1105-1111
叶峰, 陈灿杰, 赖乙宗等. 基于有序Hough变换的快速圆检测算法[J]. 光学精密工程, 2014,22(4): 1105-1111 DOI： 10.3788/OPE.20142204.1105.

YE Feng, CHEN Can-jie, LAI Yi-zong etc. Fast circle detection algorithm using sequenced Hough transform[J]. Editorial Office of Optics and Precision Engineering, 2014,22(4): 1105-1111 DOI： 10.3788/OPE.20142204.1105.

摘要

针对随机Hough变换（RHT）及其改进算法在同一圆边缘点随机抽样时命中率低且投票处理过程复杂，提出了基于有序搜索的广义Hough变换快速圆检测算法（SQHT）。该算法利用圆的几何性质和梯度方向信息来有序搜索圆边缘点集，将Hough变换的基于投票判定基元参数转变为有效确定基元三点的讨论。执行算法时，首先顺序搜寻第一边缘点并根据邻域边缘点集或图像灰度值计算其梯度值；接着在第一点所在行匹配与其梯度信息相符的第二点，根据前两点信息在第一点所在列匹配第三点；最后按照RHT算法流程确定有效基元参数，从而避免了随机抽样带来的时间不确定性。该算法具有计算速度快，检测时间可控，适用范围广泛，抗干扰性强等特点。相比于RHT算法，提出的算法在单目标圆检测情况下检测效率提高了2倍，在多目标圆（5个及以上）且有非目标边缘点情况下检测效率提高了5倍，在多圆检测方面能有效弥补了Hough变换算法的不足。

Abstract

To solve the problem of low hit ratio of random sampling in the same circle and complexity of voting process when Randomized Hough Transform (RHT) or its improved algorithm were used to detect circles

an algorithm for fast circle detection using Sequenced Hough Transform (SQHT) was proposed. It used the geometric features and gradient direction information of a circle to sequentially search the circle edge points sets and turned the acquisition of circle parameters based on vote of RHT to a discussion of locating three points of circle effectively. By using the method

the first edge point was searched sequentially and its gradient was calculated based on the adjacent edge point set or its gray value. The second point was mapped according to gradient of the first point in the row. The third point was mapped according to the information of two points above. The true circle parameters were finally calculated by RHT method

which avoids timing uncertainty caused by randomness of sampling. This method has features of high speed

controllable detection time

wide range of application and strong anti-interference performance. Comparing with the RHTs

experimental results indicate that the proposed algorithm can improve 2 times or more in the image of single circle

and 5 times or more in the image of multi-circles (5 or more). It can efficiently remedy the shortage of RHT in multi-circle detection.

关键词

Keywords

references

XU L, OJA E. A new curve detection method: Randomized Hough Transform(RHT)[J]. Pattern Recognition Letters, 1990, 11(5):331-338.

XU L, OJA E, KULTANEN P. Randomized Hough Transform(RHT): basic mechanisms, algorithms, and computational complexities[J]. Computer Vision Graphics Image Process: Image Understanding, 1993, 57(2):131.

陈燕新, 戚飞虎. 基于随机Hough变换的快速圆检测方法[J]. 上海交通大学学报, 1998, 32(10):17-20. CHEN Y X, QI F H. Fast circle detection using randomized Hough transform[J]. Journal of Shanghai Jiaotong University, 1998, 32(10):17-20. (in Chinese)

束志林, 戚飞虎. 一种新的随机Hough快速圆检测算法[J]. 计算机工程, 2003, 29(6): 87-89. SHU ZH L, QI F H. A novel algorithm for circle detection using randomized Hough transform[J]. Computer Engineering, 2003, 29(6):87-89. (in Chinese)

CHEN T C, CHUNG K L. An efficient randomized algorithm for detecting circles[J]. Computer Vision and Image Understanding, 2001, 83(2):172-191.

IOANNOU D, HUDA W, LAINE A F. Circle recognition through a 2D Hough transform and radius histogramming[J]. Journal of Parallel and Distributed Computing, 1994, 20:256-260.

岳健, 项学智. 一种改进的Hough圆检测算法[J]. 应用科技, 2006, 33(6):74-76. YUE J, XIANG X ZH. An improved algorithm of Hough circle detection[J]. Applied Science and Technology, 2006, 33(6):74-76. (in Chinese)

王强, 胡建平, 胡凯. 一种用于圆检测的快速Hough算法[J]. 小型微型计算机系统, 2000, 21(9):970-973. WANG Q, HU J P, HU K. A high speed Hough transform algorithm for circle detection[J]. Mini-Micro System, 2000, 21(9):970-973. (in Chinese)

贾平, 徐宁, 张叶. 基于局部特征提取的目标自动识别[J]. 光学精密工程, 2013, 21(7):1898-1905. JIA P, XU N, ZHANG Y. Automatic target recognition based on local feature extraction[J]. Opt. Precision Eng., 2013, 21(7):1898-1905.(in Chinese)

陈传虎, 邹德旋, 刘海宽. 应用统计距离实现虹膜定位[J]. 光学精密工程, 2012, 20(11):2516-2522. CHEN CH H, ZOU D X, LIU H K. Iris location algorithm by counting distances[J]. Opt. Precision Eng., 2012, 20(11):2516-2522.(in Chinese)

王平, 张力, 周长其. 基于种子点的粘连巨噬细胞图像的分割方法[J]. 液晶与显示, 2012, 27(6):808-813. WANG P, ZHANG L, ZHOU CH Q. Segmentation method to adhesion macrophage image based on seeding point[J]. Chinese Journal of Crystals and Displays, 2012, 27(6):808-813.(in Chinese)

郑咸义, 姚仰新, 雷秀仁, 等. 应用数值分析[M]. 广州:华南理工大学出版社, 2008:146-148. ZHENG X Y, YAO Y X, LEI X R, et al.. Numerical Analysis[M]. Guangzhou: SCUT Press, 2008:146-148.(in Chinese)

OTSU N. A threshold selection method from gray-level histograms[J]. IEEE Trans. Systems Man Cybernet., 1979, SMC-9:62-66.

Views

374

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Improved fast Image registration algorithm based on ORB and RANSAC fusion

Maker detection and pose measurement using a cooperative target

Fast recognition of aircraft target in complex scenes

Improved fast line detection method in images

Related Author

FAN Yan-guo CHAI Jiang-long XU Ming-ming WANG Bin HOU Qiu-shi

Jiang-long CHAI

Ming-ming XU

Bin WANG

Qiu-shi HOU

Yan-guo FAN

GE Shuang-long

WEN Zhuo-man

Related Institution

School of Geosciences, China University of Petroleum

Department of Criminal Science and Technology, Jilin Police College

Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences

University of the Chinese Academy of Sciences

AI问答

Address：No.3888 Dong Nanhu Road, Changchun, Jilin, China Postal code：130033
Tel：0431-86176855 Email：gxjmgc@ciomp.ac.cn
Technical support is provided by Beijing Founder electronics co., LTD 吉ICP备11002662号-17 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰