Efficient sampling strategy and refinement strategy for randomized circle detection

Abstract

Circle detection is fundamental in pattern recognition and computer vision. The randomized approach has received much attention for its computational benefit when compared with the Hough transform. In this paper, a multiple-evidence-based sampling strategy is proposed to speed up the randomized approach. Next, an efficient refinement strategy is proposed to improve the accuracy. Based on different kinds of ten test images, experimental results demonstrate the computation-saving and accuracy effects when plugging the proposed strategies into three existing circle detection methods.

Introduction

Circle detection is important and fundamental in pattern recognition and computer vision [8], [10], [11], [14], [19]. In the past two decades, the detection accuracy and computation performance are two main concerned issues and many circle detection methods have been developed. The Hough transform-based (HT-based) approach for recognizing complex patterns is first presented by Hough [13]. Later Duda and Hart [9] use the HT to detect curves. Because of the adaption of voting strategy allowable in the accumulator array, the HT-based approach has the accuracy advantage. To reduce the computing time and memory space requirements, several improved HT-based methods [4], [7], [12], [16], [17], [18], [20], [21], [27] have been developed by using either geometrical properties or the decomposition of the parameter space. However, the computing time required in these methods is difficult to be reduced significantly.

To improve the computation performance significantly, several randomized circle detection methods [3], [5], [6], [22], [23], [24], [25], [26], [28] have been developed. In the randomized HT (RHT) method proposed by Xu et al. [25], [26], each time it randomly selects three edge pixels, and then the corresponding mapped points in the parameter space are collected by voting on a 3-D accumulator array or a link-list data structure. Based on the RHT, Lu and Tan [24] presented an iterative RHT (IRHT) to detect circles, lines, and ellipses. Combining the sampling strategy in the RHT and particle swarm optimization technique, Cheng et al. [5] proposed an efficient method for circle detection. Based on a parameter-free approach without using any accumulator arrays, the RCD method proposed by Chen and Chung [3] first randomly samples four edge pixels in which three selected edge pixels are used to construct a possible circle, and the remaining edge pixel is used to confirm whether the possible circle can be promoted to a candidate circle or not. If yes, the RCD performs a voting process to determine whether the candidate circle is a true circle or not. Experimental results show that the RCD is faster than the RHT when the noise level is ranged from light level to modest level. Here the range between two levels means that the number of noisy pixels over the number of true circle pixels is at most 170%. Later, one improved lookup-table based method was presented in [6] to speed up the computation performance. To improving the accuracy of the RCD, Lee et al. [23] proposed an $O(|V{|}^2)\text{-}\mathrm{time}$ refinement strategy where $\left|V\right|$ denotes the number of edge pixels in the edge map. The motivations of our research are twofold: (1) presenting a new multiple-evidence-based efficient sampling strategy to significantly reduce the computation performance and (2) presenting a new linear-time, i.e. $O(|V|)\text{-}\mathrm{time}$, refinement strategy to improve the accuracy.

In this paper, two novel strategies are presented to improve the computation and accuracy performance of some existing randomized circle detection methods. We first present a multiple-evidence-based sampling strategy which uses three evidences to discard a large amount of invalid possible circles and candidate circles, and this strategy leads to a significant computation-saving effect. For enhancing accuracy, we present a new $O(|V|)\text{-}\mathrm{time}$ refinement strategy, which is quite different from Lee et al.'s method, to refine the parameters of the detected true circle. Based on ten images, experimental results illustrate the computation and accuracy advantages of our proposed two strategies.

The rest of this paper is organized as follows. Section 2 revisits the sampling strategy of the RCD and the refinement strategy by Lee et al.'s. In addition, Section 2 points out the related accuracy and computation overhead problems. In Section 3, the proposed multiple-evidence-based sampling strategy is presented. In Section 4, the proposed refinement strategy is presented. Section 5 demonstrates the computation and accuracy performance improvement. Finally, some concluding remarks are drawn in Section 6.