Elsevier

Image and Vision Computing

Volume 17, Issue 11, September 1999, Pages 795-803
Image and Vision Computing

Size invariant circle detection

https://doi.org/10.1016/S0262-8856(98)00160-7Get rights and content

Abstract

The Circle Hough Transform (CHT) has become a common method for circle detection in numerous image processing applications. Various modifications to the basic CHT operation have been suggested which include: the inclusion of edge orientation, simultaneous consideration of a range of circle radii, use of a complex accumulator array with the phase proportional to the log of radius, and the implementation of the CHT as filter operations. However, there has also been much work recently on the definition and use of invariance filters for object detection including circles. The contribution of the work presented here is to show that a specific combination of modifications to the CHT is formally equivalent to applying a scale invariant kernel operator. This work brings together these two themes in image processing which have herewith been quite separate. Performance results for applying various forms of CHT filters incorporating some or all of the available modifications, along with results from the invariance kernel, are included. These are in terms of an analysis of the peak width in the output detection array (with and without the presence of noise), and also an analysis of the peak position in terms of increasing noise levels. The results support the equivalence between the specific form of the CHT developed in this work and the invariance kernel.

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 E=(Ex,Ey)T, 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.QSC=‖E‖⊗1rOSCQA=‖E‖⊗1rOAQPCA=‖E‖⊗1rOPCAwhere 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)

There are more references available in the full text version of this article.

Cited by (0)

View full text