Circular Hough Transform

Enhanced (Circular) Hough Transform

Actually, this method should not be called a "Hough Transform" at all, since it operates on quite different, almost exactly opposite principles compared to the other two methods.

In fact, the CHT and GHT both produce the same spectrum in the (x,y,ρ) space when searching for circular diameters, where high values of a certain (x,y,ρ) point indicate the possible presence of a circle's center at (x,y) with a given diameter ρ, something which can be (and is) used for circle detection.

However, the latter method, while not wrong on a principle basis, consumes enormous amounts of memory, processing power and has (especially the GHT method) to search for circles of strictly predefined diameters, as we need a table with a spatial resolution at least as big as our image (e.g. 500 per 500 pixels) and a "diameter resolution" at least as wide as the difference between the smallest and biggest diameter we are looking for.

This is also another serious drawback of the CHT and GHT methods, since even without specific diameter constraints, due to memory, we still have to explicitly check for a precise diameter each time. While doing that, all other diameters simply get ignored, from a purely mathematical/geometrical point of view. From a signal processing point of view, that would equate to viewing our image through a very narrow-banded "notch" filter only able to see one "frequency" (circle diameter) at a time, and thus we have to perform multiple "passes" each time.

The so called "EHT" method, which in this context we use for "Extended/Enhanced (Circle detection optimized) Hough Transform", can at least in part overcome those limitations, and deliver a much faster and reliable circle detection mechanism. Furthermore, the final "spectrum" is much sharper and defined compared to the CHT/GHT method.

The fundamentals behind this method are described in a scientific paper by Shih-Hsuan Chiu and Jiun-Jian Liaw, quite unoriginally called "An effective voting method for circle detection". The paper describes the basic theory behind the method but doesn't give it a specific name, and neither does it dwell on implementation details, despite the paper showing the results of an allegged implementation by part of the authors.

In our implementation, we followed part of the paper's suggestions, while improvising others, not better specified details, and tried to "blend it in" with the rest of the program (see end of this section for details and limitations).

How it works

First of all, you must enable the EHT controls by checking the "Enable" box under the "Binary" tab, after having a valid binary image.

The first step, according to the original paper, is subsampling the original image without destroying it. This means that we create a subsampled copy of our original image in memory, and work on that. Subsampling can be done in either the X or Y direction, and can be set by the "StepX" and "StepY" controls.

The result of the subsampling can be seen after the "Use EHT" button has been hit.

Choosing the subsampling factor is a kind of art:

Values of X:1, Y:1 mean no subsampling, and will lead to longer calculation times. Also, the EHT will actually perform worse with no subsampling at all.
Values of X:1, Y:2 are the default settings, and tend to work very well with most images.

Occassoinally, setting X:2, Y:2 or X:2, Y:1 may help on certain images, if important details are lost.

In general, use small subsampling values when searching for small circles, and bigger ones when searching for bigger. For a mixed situation, try an "in medio stat virtus" approach.

For each point P1 in our subsampled image, which we hope is part of a circle (here shown in blue, and just hypothetical, for now)....

...we try to "pick" a second point P2. The original paper doesn't say HOW or WHERE we should look for this point, but it's reasonable to assume that we should look "around" our original P1 point, up to a distance equal to the maximum diameter we're looking for (Note: on a "perfect" implementation this means the ENTIRE IMAGE!).

For our purposes, we search each circular radius from 0 to the Maximum Seached Diameter, lower radii first. This can, however, lead to "vote stealing" errors on certain images.

The image shows the search radius progression and direction.

Let's say we found a point P2 that belongs to our subsampled image, and is within a "maximum diameter"'s length from P1.

With a similar method, we now seach for a third point P3 , which has to be on a circular arc between P1 and P2. Ideally, P1 and P2 should belong to the same circular arc.

And, P3 must be "between" P1 and P2 on said circular arc. For that reason, each candidate Pi point is checked this way: if the absolute difference between the P2-P1 and the P3-P2 distance is less than a certain tolerance value εr , then we accept it as our third point.

This parameter can be set from within the program, from the "Third point distance" slidebar. A distance of 0 means P3 is exactly halfway between P1 and P2, something very restrictive. The image shows approximately where distances of 0, 1, 2 and 3 would lie on our supposed circle.

Up to a certain point, bigger values of εr give better detection results, but values in excess of the actual P1-P2 distance (which is, unluckily, variable with each pair of P1,P2 in the image) will lead to false detections or "lost votes", so this parameter must be set carefully or should be dynamically optimized during runtime (we're working on this).

Let's say that, due to our tolerance settings and search methods, we picked the P3 pixel, which also belongs to our subsampled image, but we don't know if it's actually part of a circle along with P1 and P2.

We now determine the equations for the mid-perpendiculars lines of the P1-P3 and P2-P3 segments. These are in the form of y=ax+b equations, which for two lines form a 2-variable (x and y) simultaneous linear equations system.

By solving this system, we found the coordinates x and y where those mid-perpendiculars intersect. If that (x,y) point is outside the boundaries of our image, coincides with either P1,P2 or P3, or the system cannot be solved, we ignore the result and that causes a "vote failure" for P1, at least for now.

If the solution exists and is acceptable, then the solution could be the possible center of a circle, and the radius of that circle is of course the distance between the center and P1 or P2 or P3.

To verify that this is indeed the center of a circle, we check how many pixels there actually are on our ORIGINAL IMAGE (NOT THE SUBSAMPLED ONE!), around this "center" and at the specified radius. This is done by "counting" them, and allowing for some errors (e.g. slightly bigger or smaller radius at some points, missing pixels).

The amount of RADIUS TOLERANCE can be set by the EHT Radius Tolerance slidebar, and only affects this phase of detection.

The effective pixel count is then stored at a special data structure (for now, we use the same (x,y,ρ) table as the GHT and CHT).

If a same center and radius is picked more than one, the best (biggest) occurring pixel count gets stored.

The process is repeated for each pixel P1 in the subsampled image. No pixel gets to be "P1" for a second time, unless it fails to vote the first time and "refinement" is on. In that case, the whole image can be "scanned" several times, by restricting the search radius (e.g. focusing on larger radii to combat "vote stealing").

Our original Image.

Spectrum for CHT, diameter 25.

Spectrum for GHT, diameter 25.

It is similar,save for a shifting of 12.5 pixels in the centers of the spectrum circles, due to the way our R-Tables are constructed.

Spectrum for EHT, diameter 25.

Notice how "cleaner" the spectrum is. Even the nasty white "glob" on the lower right has been reasonaby suppressed.

Some immediate advantages of this method:

In theory, unlike the CHT and GHT methods, the definition of EHT by itself doesn't impose a specific strict limit over what diameters/radii should be/can be detected, and the formulas behind it allow for any radius to be accounted for at any time (however, see the notes below).

It can work with much less memory compared to the other two methods, or to most other similar circle detection schemes (however, see the notes below).

It is much faster than the other two methods, provided it has been correctly set up in order to perform a "perfect" detection cycle with little or even no "refinement" passes.

Drawbacks/Notes:

It is much more complicated to implement, and many phases are not standarized or well documented.It has many parameters to take into account, compared to the CHT and GHT methods, and hiding them from the final user might not be a good idea. It is highly specialized for circle detection, cannot easily be extended to other shapes. Memory or implementation limitations might make it necessary (or a side effect) to restrict the acceptable diameter ranges within certain boundaries, like with the CHT and GHT methods.The exact detection methods used to pick the second and third points (P2,P3), as well as their tolerance, can make a difference in the final results, as well as to how "free" and "without limits" our detection will be. As a note, in our implementation lower radii get "priority" over the larger ones, so trying an excessively "broad band" detection on an image can be counterproductive or ineffective.

It needs a different data structure compared to CHT/GHT, to be used to its full potential. This might be implemented in a next version of the program.