Fast Circle Detection Using Spatial Decomposition of Hough Transform

Circles are important patterns in many automatic image inspection applications. The Hough Transform (HT) is a popular method for extracting shapes from original images. It was first introduced for the recognition of straight lines, and later extended to circles. The drawbacks of standard Hough Transform (SHT) for circle detection are the large computational and storage requirements. In this paper, we propose a modified HT called Vector Quantization of Hough Transform (VQHT) to detect circles more efficiently. The basic idea is to first decompose the edge image into many subimages by using Vector Quantization (VQ) algorithm based on their natural spatial relationships. The edge points resided in each subimage are considered as one circle candidate group. Then the VQHT algorithm is applied for fast circle detection. A new paradigm to store potential curve parameters is also proposed, which can exponentially reduce the storage space for HT algorithm. Experimental results show that the proposed algorithm can quickly and accurately detect multiple circles from the noisy background.