Hough circles detection

HoughCircles2dPpties =	houghCircles2d (inImg,radiusRange)
HoughCircles2dPpties =	houghCircles2d (inImg,radiusRange,eCircleIntensityType,nbMaxPtsPerCircle,accumIntensityThreshold,removeTooCloseCirclesParams)
HoughCircles2dPpties =	houghCircles2d (inGxImg,inGyImg,radiusRange)
HoughCircles2dPpties =	houghCircles2d (inGxImg,inGyImg,radiusRange,method,eCircleIntensityType,maxAngleWithGradDir,nbMaxPtsPerCircle,accumIntensityThreshold,removeTooCloseCirclesParams,outImg1,outImg2)

Detailed Description

detects circles in image using Hough algorithm

This algorithm uses a variant of the Standard Circle Hough Transform to detect circles in a 2d grey levels image (or in a sequence of 2d grey levels images). Below is shown an example of application of Hough circles detector on an image of coins (circles detected by the algorithm are drawn in red on the right image; used range of radii equals to [10, 20]; all other input parameters are left to their default values):

1- Background: the Standard Circle Hough Transform

Standard Circle Hough Transform was inspired from Standard Line Hough Transform ([1]). Considering the user wants to detect circles with radii between minRadius and maxRadius, it works as follows:

a- pre-process the image by applying an edge extraction (Canny edge extraction, for instance)

b- create a 3D parameter space (also called accumulator matrix, or Hough space, or voting space). The 2 first dimensions correspond to the positions of the centers of the circles, and the 3rd dimension corresponds to the radii of the circles. Initialize the content of this 3D image with zeros.

c- for each pixel of the edge(s) detected in the input image in a), and for each radius in , increment pixels of coordinates in the 3D parameter space that satisfy the equation .

d- extract local maxima in the 3D parameter space; they should correspond to the circles present in the original image

This algorithm has several limitations; in particular:

• it requires a lot of memory space: the allocation of the 3D parameter space is important, especially if the range of radii is great.
• a pre-process step of edge-extraction is required, implying a thresholding of the input image

2- Modifications of the Standard Circle Hough Transform for our implementation

The current implementation makes use of modifications described in [2]. Here is a recall of the main modifications from the standard version:

• gradient orientation is used; Kimme et al. [3] took advantage of the following property: the normals to the points of a circle pointed to its center. So for each accumulation pixel, by considering only points whose gradient direction points to the processed pixel (within an angle tolerance specified by the user), the risk to pollute the vote with "bad" edges is greatly reduced.
• no "edge extraction" step (and so no implicit thresholding) is needed; all points take part to the vote, with a weight that equals to the modulus of their gradient
• only one plan is used for the whole range of radii, reducing the required memory space (the parameter space is in 2 dimensions, only)
• the transform is implemented as a convolution operator, with an annulus kernel
• in the case of the "phase-coded" method, a complex image (2 images, one for the real part, the other for the imaginary part) is used, so that the radius of the circle can be encoded in the phase (the linear coding has been retained for the current implentation).

3- Steps of the current implementation:

The current implementation executes the following steps:

a- compute the gradient images if necessary, respectively along x and y axis

b- compute the Hough image (or images, if the "phase coded" method has been chosen)

c- extract the circles centers from the Hough image(s). The way to proceed depends on the selected method:

• for the "gradient" method, it simply extracts the local maxima in the Hough image, beyond a threshold specified by the user
• for the "gradient phase-coded" method, it computes a magnitude image from the 2 Hough images (real+imaginary) and extracts the local maxima from this magnitude image

d- compute the radius associated to each detected circle:

• if the "gradient" method has been selected, it computes a histogram of radii for each circle and associates to the circle the radius for which the frequency is the greatest
• otherwise, in the case of "gradient phase-coded" method, the radius is simply decoded from the phase of the complex image

e- for each couple of too close circles, remove the one with the lower accumulation intensity in Hough image

4- How to use the input parameters of the algorithm

As a general rule, more the user will restrict the search parameters, the faster the algorithm will execute and the more accurate the result will be. Here are some details for each parameter:

• input image ( or the couple ): the user can choose between specifying directly the image in which he wants the circles to be detected (it has to be a grey-level 2d image, or a sequence of grey-level 2d images; if the user wants to detect circles in a color image, he can first convert it to a lightness image using ipsdk::imaproc::color::lightnessImg function, for instance) or entering the gradients images, respectively along the x and y axis. In the first case, the algorithm will first compute internally the gradient images, necessary for the next processing steps.
• range of radii ( ): specify the minimal and maximal radii of the set of circles to detect. Remember the general rule: the smaller the range will be, the faster the algorithm will execute and the more accurate the result will be.
• method ( ): choose between "gradient" and "gradient phase-coded" methods. Default method is set to "gradient"
• circles intensity type ( ): 3 values are possible for this parameter:
  • bright circles: asks the algorithm to detect bright circles on dark background only
  • dark circles: asks the algorithm to detect dark circles on bright background only
  • both: asks the algorithm to detect bright circles on dark background AND dark circles on bright background. When it's possible, the user should choose between the 2 first values, to reduce the detection of false circles. Default value for this parameter is set to "both"
• gradient orientation maximal angle tolerance ( , expressed in radians): on clean (ie. without noise) images, a small tolerance (a few degrees) should be used, so that edge points with wrong gradient orientation do not take part to the vote in the Hough image. On the other hand, when the image is noisy, the user should increase the value of this parameter, because the gradient orientation is very sensitive to noise. Default value of this parameter is set to 5 degrees
• maximal number of points per circle ( ): this parameter determines the number of points per circle in the annulus kernel that will take part to the vote in the Hough image. The smaller this parameter is, the faster the computation is. Nevertheless, it is advised not to set this parameter to a too small value (< 50), especially on noisy images, or on images where circles are too close from each other, otherwise the accuracy of the results will be dramatically reduced. To determine the points for each circle in the kernel that take part to the vote, each circle is subsampled by keeping only one point every radians. Here are some examples of kernels associated to a range of radii [10; 100], with different values for parameter (pixels belonging to the kernel are colored in white, in a square window of size ):

• thresholds on values of accumulator matrix ( ): there are 2 thresholds for this parameter: an absolute one (default value: 1.0) and a relative one (default value: 0.3). Extraction of local maxima in the parameter space will only be applied on pixels whose value is greater than the absolute one AND greater than the relative one multiplied by the global maximum of the parameter space. Default values have been set to satisfy most of the use cases, but the user can adjust these 2 parameters if the number of circles detected in his input image is too low or too great.

• minimum ratio of distances between two circles ( ): if this parameter is enabled, after the step of local maxima extraction in the parameter space, any circle , of parameters verifying the following condition: , a circle of parameters , so that:

  • accumulation intensity of pixel in parameter space associated to < accumulation intensity of pixel in parameter space associated to
  • distance between centers of and is lower than

  is removed from the collection of detected circles returned to the user.

5- Limitations of the current implementation:

As only one radius is associated to each circle center position, the current implementation does not allow to detect concentric circles.

References

[1] Hough transform. (2015, June 17). In Wikipedia, The Free Encyclopedia. Retrieved 15:42, June 29, 2015, from https://en.wikipedia.org/w/index.php?title=Hough_transform&oldid=667291656
[2] T.J. Atherton and D.J. Kerbyson, Size invariant circle detection, Image and Vision Computing 17 (1999) 795–803
[3] C. Kimme, D. Ballard, J. Sklansky, Finding circles by an array of accumulators, Proc. ACM 18 (1975) 120–122

Example of Python code :

Example imports

import PyIPSDK
import PyIPSDK.IPSDKIPLFeatureDetection as fd

Code Example

    # opening of input image
    inImg = PyIPSDK.loadTiffImageFile(inputImgPath)
    
    # radius range detection definition
    radiusRange = PyIPSDK.createHoughCirclesRadiusRange(15,  20)
    
    # hough circle detection computation
    outHoughCircles2dPpties = fd.houghCircles2d(inImg,  radiusRange)
    
    # retrieve coordinates of first detected circle (associated to maximum intensity)
    maxHoughCircles2dPpty = PyIPSDK.toPyDict(outHoughCircles2dPpties)['Coll'][0]
    print("Circle with maximum accumulated intensity " + str(maxHoughCircles2dPpty['AccumIntensity'] ) + " found on coordinates x=" + str(maxHoughCircles2dPpty['X'] ) + " and y=" + str(maxHoughCircles2dPpty['Y'] ) + " and with radius=" + str(maxHoughCircles2dPpty['Radius'] ))

Example of C++ code :

Example informations

Header file

#include <IPSDKIPL/IPSDKIPLFeatureDetection/Processor/HoughCircles2d/HoughCircles2d.h>

Code Example

#include <IPSDKImageFile/Tiff/TiffImageFileUtils.h>
#include <IPSDKIPL/IPSDKIPLFeatureDetection/Processor/HoughCircles2d/HoughCircles2d.h>

// function returning the collection of circles with radii in a given range
// detected by Hough algorithm in the image loaded from a given TIFF file
boost::shared_ptr<imaproc::attr::HoughCircles2dPpties>
detectCircles(
    const std::string& inImgFilePath,
    ipUInt64 nMinRadius,
    ipUInt64 nMaxRadius)
{
    // load input image from file specified by the user
    ipsdk::image::ImagePtr pInImg =
        ipsdk::image::file::loadTiffImageFile(inImgFilePath);

    // apply Hough circles detection
    const boost::shared_ptr<imaproc::attr::HoughCircles2dPpties> pCircles =
        ipsdk::imaproc::fd::houghCircles2d(
            pInImg,
            ipsdk::imaproc::attr::createHoughCirclesRadiusRange(nMinRadius, nMaxRadius));

    // return the collection of detected circles
    return pCircles;
}