Find circles using circular Hough transform

`centers = imfindcircles(A,radius)`

```
[centers,radii]
= imfindcircles(A,radiusRange)
```

```
[centers,radii,metric]
= imfindcircles(A,radiusRange)
```

```
[___]
= imfindcircles(___,Name,Value)
```

`[`

finds
circles with radii in the range specified by `centers`

,`radii`

]
= imfindcircles(`A`

,`radiusRange`

)`radiusRange`

.
The additional output argument, `radii`

, contains
the estimated radii corresponding to each circle center in `centers`

.

`[`

also
returns a column vector, `centers`

,`radii`

,`metric`

]
= imfindcircles(`A`

,`radiusRange`

)`metric`

, containing the
magnitudes of the accumulator array peaks for each circle (in descending
order). The rows of `centers`

and `radii`

correspond
to the rows of `metric`

.

```
[___]
= imfindcircles(___,
```

specifies additional options with one or more `Name,Value`

)`Name,Value`

pair
arguments, using any of the previous syntaxes.

Specify a relatively small

`radiusRange`

for better accuracy. A good rule of thumb is to choose`radiusRange`

such that`rmax < 3*rmin`

and`(rmax-rmin) < 100`

.The accuracy of

`imfindcircles`

is limited when the value of`radius`

(or`rmin`

) is less than or equal to 5.The radius estimation step is typically faster if you use the (default)

`'PhaseCode'`

method instead of`'TwoStage'`

.Both computation methods,

`'PhaseCode'`

and`'TwoStage'`

are limited in their ability to detect concentric circles. The results for concentric circles can vary depending on the input image.`imfindcircles`

does not find circles with centers outside the domain of the image.`imfindcircles`

preprocesses binary (logical) images to improve the accuracy of the result. It converts truecolor images to grayscale using the function`rgb2gray`

before processing them.

`imfindcircles`

uses a Circular Hough Transform (CHT) based algorithm for
finding circles in images. This approach is used because of its robustness in the presence of
noise, occlusion and varying illumination.

The CHT is not a rigorously specified algorithm, rather there are a number of different approaches that can be taken in its implementation. However, by and large, there are three essential steps which are common to all.

**Accumulator Array Computation**Foreground pixels of high gradient are designated as being candidate pixels and are allowed to cast ‘votes’ in the accumulator array. In a classical CHT implementation, the candidate pixels vote in pattern around them that forms a full circle of a fixed radius. Figure 1a shows an example of a candidate pixel lying on an actual circle (solid circle) and the classical CHT voting pattern (dashed circles) for the candidate pixel.

**Classical CHT Voting Pattern****Center Estimation**The votes of candidate pixels belonging to an image circle tend to accumulate at the accumulator array bin corresponding to the circle’s center. Therefore, the circle centers are estimated by detecting the peaks in the accumulator array. Figure 1b shows an example of the candidate pixels (solid dots) lying on an actual circle (solid circle), and their voting patterns (dashed circles) which coincide at the center of the actual circle.

**Radius Estimation**If the same accumulator array is used for more than one radius value, as is commonly done in CHT algorithms, radii of the detected circles have to be estimated as a separate step.

`imfindcircles`

provides two algorithms for finding circles in images:
Phase-Coding (default) and Two-Stage. Both share some common computational steps, but each has
its own unique aspects as well.

The common computational features shared by both algorithms are as follow:

**Use of 2-D Accumulator Array**The classical Hough Transform requires a 3-D array for storing votes for multiple radii, which results in large storage requirements and long processing times. Both the Phase-Coding and Two-Stage methods solve this problem by using a single 2-D accumulator array for all the radii. Although this approach requires an additional step of radius estimation, the overall computational load is typically lower, especially when working over large radius range. This is a widely adopted practice in modern CHT implementations.

**Use of Edge Pixels**Overall memory requirements and speed is strongly governed by the number of candidate pixels. To limit their number, the gradient magnitude of the input image is threshold so that only pixels of high gradient are included in tallying votes.

**Use of Edge Orientation Information**Another way to optimize performance is to restrict the number of bins available to candidate pixels. This is accomplished by utilizing locally available edge information to only permit voting in a limited interval along direction of the gradient (Figure 2).

**Voting Mode: Multiple Radii, Along Direction of Gradient**

r_{min} | Minimum search radius |

r_{max} | Maximum search radius |

r_{actual} | Radius of the circle that the candidate pixel belongs to |

c_{min} | Center of the circle of radius r_{min} |

c_{max} | Center of the circle of radius r_{max} |

c_{actual} | Center of the circle of radius r_{actual} |

The two CHT methods employed by function `imfindcircles`

fundamentally
differ in the manner by which the circle radii are computed.

**Two-Stage**Radii are explicitly estimated utilizing the estimated circle centers along with image information. The technique is based on computing radial histograms [2] [3].

**Phase-Coding**The key idea in Phase Coding [1] is the use of complex values in the accumulator array with the radius information encoded in the phase of the array entries. The votes cast by the edge pixels contain information not only about the possible center locations but also about the radius of the circle associated with the center location. Unlike the Two-Stage method where radius has to be estimated explicitly using radial histograms, in Phase Coding the radius can be estimated by simply decoding the phase information from the estimated center location in the accumulator array.

[1] T.J Atherton, D.J. Kerbyson. "Size
invariant circle detection." *Image and Vision Computing*.
Volume 17, Number 11, 1999, pp. 795-803.

[2] H.K Yuen, .J. Princen, J. Illingworth, and
J. Kittler. "Comparative study of Hough transform methods for circle
finding." *Image and Vision Computing*. Volume
8, Number 1, 1990, pp. 71–77.

[3] E.R. Davies, *Machine Vision:
Theory, Algorithms, Practicalities*. Chapter 10. 3rd Edition.
Morgan Kauffman Publishers, 2005,

`hough`

| `houghlines`

| `houghpeaks`

| `viscircles`