[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Circular hole detection algorithm based on image block

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

Circular hole detection is a common problem in computer vision and pattern recognition. Randomized Hough transform and randomized circle detection algorithm are commonly used in circle detection, with good detection robustness and accuracy. But for circular holes with smaller radius, the two algorithms will be too slow because of a large number of invalid sampling. Thus the circular hole detection algorithm based on image block is proposed in order to improve the speed of circular hole detection. The algorithm divides the image into several small blocks and 3 points from the same block are randomly selected for sampling each time. If a candidate circular hole can be obtained by calculating these 3 points, then the points in the 4 blocks (or less) closest to the center of the candidate hole will be used for evidence-collecting to determine whether the candidate circular hole is true. Experimental results on a large number of synthetic images and real images show that the detection speed of circular hole detection algorithm proposed is much faster than the speed of randomized Hough transform and randomized circle detection algorithm. In addition, the proposed algorithm has the same detection robustness and accuracy as the randomized circle detection algorithm. The block strategy proposed in this paper is also applicable to the detection of elliptical holes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

References

  1. Ayala-Ramirez V, Garcia-Capulin CH, Perez-Garcia A, Sanchez-Yanez RE (2006) Circle detection on images using genetic algorithms. Pattern Recogn Lett 27(6):652–657

    Article  Google Scholar 

  2. Chen TC, Chung KL (2001) An efficient randomized algorithm for detecting circles. Comput Vis Image Underst 83(2):172–191

    Article  MathSciNet  Google Scholar 

  3. M. Chen, F. Zhang, Z.H. Du, R.Y. Liu. Circle detection using scan lines and histograms. Opt Rev, 2013, 20(6): 484–490

    Article  Google Scholar 

  4. Cheng HD, Guo YH, Zhang YT (2009) A novel Hough transform based on eliminating particle swarm optimization and its applications. Pattern Recogn 42(9):1959–1969

    Article  Google Scholar 

  5. Chiu SH, Lin KH, Wen CY, Lee JH, Chen HM (2012) A fast randomized method for efficient circle/arc detection. International Journal of Innovative Computing, Information and Control 8(1A):151–166

    Google Scholar 

  6. Chung KL, Huang YH (2008) A pruning-and-voting strategy to speed up the detection for lines, circles, and ellipses. J Inf Sci Eng 24(2):503–520

    MathSciNet  Google Scholar 

  7. Chung KL, Huang YH, Shen SM, Krylov AS, Yurin DV, Semeikina EV (2012) Efficient sampling strategy and refinement strategy for randomized circle detection. Pattern Recogn 45(1):252–263

    Article  Google Scholar 

  8. Cuevas E, González M (2013) Multi-circle detection on images inspired by collective animal behavior. Appl Intell 39(1):101–120

    Article  Google Scholar 

  9. Cuevas E, Zaldivar D, Pérez-Cisneros M, Ramírez-Ortegón M (2011) Circle detection using discrete differential evolution optimization. Pattern Anal Applic 14(1):93–107

    Article  MathSciNet  Google Scholar 

  10. Cuevas E, Osuna-Enciso V, Wario F, Zaldívar D, Pérez-Cisneros M (2012) Automatic multiple circle detection based on artificial immune systems. Expert Syst Appl 39(1):713–722

    Article  Google Scholar 

  11. Cuevas E, Sención-Echauri F, Zaldivar D, Pérez-Cisneros M (2012) Multi-circle detection on images using artificial bee colony (ABC) optimization. Soft Comput 16(2):281–296

    Article  Google Scholar 

  12. Cuevas E, Osuna-Enciso V, Oliva D (2015) Circle detection on images based on the clonal selection algorithm (CSA). The Imaging Science Journal 63(1):34–44

    Article  Google Scholar 

  13. Dasgupta S, Das S, Biswas A, Abraham A (2010) Automatic circle detection on digital images with an adaptive bacterial foraging algorithm. Soft Comput 14(11):1151–1164

    Article  Google Scholar 

  14. De Marco T, Cazzato D, Leo M, Distante C (2015) Randomized circle detection with isophotes curvature analysis. Pattern Recogn 48(2):411–421

    Article  Google Scholar 

  15. Djekoune AO, Messaoudi K, Amara K (2017) Incremental circle hough transform: an improved method for circle detection. Optik 133:17–31

    Article  Google Scholar 

  16. N. Dong, C.H. Wu, W.H. Ip, Z.Q. Chen, C.Y. Chan, K.L. Yung. An opposition-based chaotic GA/PSO hybrid algorithm and its application in circle detection. Computers and Mathematics with Applications, 2012, 64(6): 1886–1902

    Article  MathSciNet  Google Scholar 

  17. Huang YH, Chung KL, Yang WN, Chiu SH (2012) Efficient symmetry-based screening strategy to speed up randomized circle-detection. Pattern Recogn Lett 33(16):2071–2076

    Article  Google Scholar 

  18. Jiang LY (2009) Fast detection of multi-circle with randomized Hough transform. Optoelectron Lett 5(5):397–400

    Article  Google Scholar 

  19. Jiang LY (2012) Efficient randomized Hough transform for circle detection using novel probability sampling and feature points. Optik 123(20):1834–1840

    Article  Google Scholar 

  20. Jiang LY, Ye YQ, Xu GL (2016) An efficient curve detection algorithm. Optik 127(1):232–238

    Article  Google Scholar 

  21. Jiang LY, Wang ZW, Ye YQ, Jiang JB (2018) Fast circle detection algorithm based on sampling from difference area. Optik 158:424–433

    Article  Google Scholar 

  22. Liu D, Wang YT, Tang Z, Lu XQ (2014) A robust circle detection algorithm based on top-down least-square fitting analysis. Computers & Electrical Engineering 40(4):1415–1428

    Article  Google Scholar 

  23. Liu WF, Zhang ZQ, Li SY, Tao DP (2017) Road detection by using a generalized Hough transform. Remote Sens 9(6):590

    Article  Google Scholar 

  24. Manzanera A, Nguyen TP, Xu XL (2016) Line and circle detection using dense one-to-one Hough transforms on greyscale images. EURASIP Journal on Image and Video Processing 2016(1):46

    Article  Google Scholar 

  25. Mukhopadhyay P, Chaudhuri BB (2015) A survey of Hough transform. Pattern Recogn 48(3):993–1010

    Article  Google Scholar 

  26. Ok AO (2014) A new approach for the extraction of aboveground circular structures from near-nadir VHR satellite imagery. IEEE Trans Geosci Remote Sens 52(6):3125–3140

    Article  Google Scholar 

  27. Ok AO, Başeski E (2015) Circular oil tank detection from panchromatic satellite images: a new automated approach. IEEE Geosci Remote Sens Lett 12(6):1347–1351

    Article  Google Scholar 

  28. Scitovski R, Marošević T (2015) Multiple circle detection based on center-based clustering. Pattern Recogn Lett 52:9–16

    Article  Google Scholar 

  29. Tang ZJ, Zhang XQ, Zhang SC (2014) Robust perceptual image hashing based on ring partition and NMF. IEEE Trans Knowl Data Eng 26(3):711–724

    Article  Google Scholar 

  30. Xu L (2007) A unified perspective and new results on RHT computing, mixture based learning, and multi-learner based problem solving. Pattern Recogn 40(8):2129–2153

    Article  Google Scholar 

  31. Xu L, Oja E, Kultanen P (1990) A new curve detection method: randomized Hough transform (RHT). Pattern Recogn Lett 11(5):331–338

    Article  Google Scholar 

  32. Yao ZJ, Yi WD (2016) Curvature aided Hough transform for circle detection. Expert Syst Appl 51:26–33

    Article  Google Scholar 

  33. Yuan BD, Liu M (2015) Power histogram for circle detection on images. Pattern Recogn 48(10):3268–3280

    Article  Google Scholar 

  34. Zhang HQ, Wiklund K, Andersson M (2016) A fast and robust circle detection method using isosceles triangles sampling. Pattern Recogn 54:218–228

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported by the Natural Science Foundation of Guangxi (2016GXNSFBA380081), the National Natural Science Foundation of China (61751213, 61462008), the Program of Guangxi Education Department (KY2016YB256, KY2016YB249), the Research Fund of Guangxi Key Lab of Multi-source Information Mining & Security (MIMS17-04), the Key Laboratory of Industrial Process Intelligent Control Technology of Guangxi Higher Education Institutes (IPICT-2016-03), Liuzhou Scientific Research and Technology Development Project (2016C050205), and the Innovation Team Project of Guangxi University of Science and Technology.

Author information

Authors and Affiliations

  1. College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing, 210016, China

    Lianyuan Jiang

  2. College of Computer Science and Communication Engineering, Guangxi University of Science and Technology, Liuzhou, 545006, China

    Lianyuan Jiang, Haohao Yuan & Chungui Li

  3. Guangxi Key Lab of Multi-source Information Mining & Security, Guangxi Normal University, Guilin, 541004, China

    Haohao Yuan

Authors
  1. Lianyuan Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Haohao Yuan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chungui Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lianyuan Jiang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jiang, L., Yuan, H. & Li, C. Circular hole detection algorithm based on image block. Multimed Tools Appl 78, 29659–29679 (2019). https://doi.org/10.1007/s11042-018-6135-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-018-6135-x

Keywords

Search

Navigation