Size invariant circle detection
Section snippets
Background
The Circle Hough Transform (CHT) [1], aims to find circular formations, of a given radius R, within an image. An example of the conventional CHT is shown in Fig. 1. A set of edge points, within the original image, is indicated by the black circle. Each edge point contributes a circle of radius R to an output accumulator space, shown by the grey circles. The output accumulator space has a peak where these contributed circles overlap at the centre of the original circle.
The CHT can be formulated
Filters for circle detection
CHT techniques for the detection of a circle of single radius, the detection of a range of circle sizes, the use of orientation information, and the complex coding of size in terms of phase, can each be expressed in terms of a convolution operator or set thereof. Each of which are defined below.
It is assumed that the convolution operator size is (2Rmax+1) by (2Rmax+1), where Rmax is the radius of the largest circle being considered, and that the centre of the operator is indexed (0,0). The
Applying the circle detection filters
The convolution operators introduced in the previous section are applied to either an edge magnitude image, ‖E‖, where , or the partial gradient image in x and y (Ex and Ey, respectively). No edge thresholding operation is required in this work.
The operators for a single circle, an annulus, and a phase coded annulus can each be convolved with the edge magnitude image to give the following results, i.e.where QSC, QA, QPCA are the outputs from the
Circle detection using invariance kernels
In this section we show that the Hough transform filters, that we and others have been using are either equivalent to, or closely related to, kernels derived from considering invariant transformations of patterns [12]. Such transformations, or deformations, include scaling, rotation, and translation. For circle detection the deformations of interest are rotation and scaling. Patterns that are circularly symmetric are inherently invariant to rotation. A kernel invariant to rotation and scaling
Comparative results
A number of experiments have been performed to investigate the behaviour of the techniques in terms of the width of the peak in the accumulator array, the height of the peak above the surrounding pedestal, and the accuracy of detecting the centre of the circle [16]. We report:
- 1.
Cross-sections of the responses of the convolution operations to ideal circle images (with no added noise).
- 2.
Output arrays for noisy test images.
- 3.
The positional accuracy of circle centre detection in the presence of additive
Discussion
We have reviewed a series of modifications to the CHT and shown that a combination of four of these, the inclusion of edge direction, simultaneously considering a range of radii, using a complex accumulator array with phase proportional to the log of radius, and implementation as a filter, is formally equivalent to applying a scale invariant kernel operator. The results presented provide qualitative support for this.
The inclusion of edge direction in a circle detector (sensitive to a range of
References (19)
A Modified Hough Scheme for General Circle Location
Pattern Recognition Letters
(1988)The Lie algebra of visual perception
J. Mathematical Psychology
(1966)Invariant pattern recognition: a review
Pattern Recognition
(1996)- et al.
Transformational invariance—a primer
Image and Vision Computing
(1992) - et al.
Recognition of distorted patterns by invariance kernels
Pattern Recognition
(1991) - et al.
Use of the Hough Transform to Detect Lines and Curves in Pictures
Communications of the ACM
(1972) A Method for Detection of Circular Arcs Based on the Hough Transform
Machine Vision Applications
(1992)- H.K. Yuen, et al., A comparative study of Hough transform methods for circle finding, in: Proc. Alvey Vision...
- et al.
Detection and segmentation of blobs in infrared images
IEEE Trans. SMC
(1981)