Alleviating the computational load of the probabilistic algorithms for circles detection using the connectivity represented by graph

摘要

The probabilistic algorithms are effective and widely used to recognize the curves in machine vision and image processing. In this paper, a novel algorithm for detecting circles is presented. It is based on the observation that the connectivity can help to alleviate the computational load of the probabilistic algorithm. A graph model is introduced to express connectivity in the detected edges, and a modified depth-first-search algorithm is developed to segment the whole graph into connected subgraphs and then partition the complex subgraph into simple paths. Then, four pixels are randomly selected from the sampling set, consisting of one proper path or several consecutive paths, to detect circles. The connectivity constraint is further employed to verify the candidates of circles to eliminate the pseudo ones. The experiments, comparing the proposed algorithm with the randomized Hough transform and the efficient randomized circle detection algorithm, show that it has the advantages of computational efficiency and robustness. 【keyworks】 Circles detection; Random sampling;Connectivity;Graph