Detection of Circles

A circle in the image can be described by

$$f(x,y,x_0,y_0,r)=(x-x_0)^2+(y-y_0)^2-r^2=0$$

where $x_0$, $y_0$, and $r$ are three parameters which span a 3D Hough space. Any point $(x,y)$ in the image corresponds to a cone shaped surface in the 3D parameter space. To use $\angle G$, consider the derivative

$$\frac{dy}{dx}=-\frac{f'_x(x,y)}{f'_y(x,y)}=-\frac{x-x_0}{y-y_0}$$

Now we only need to increment those elements in the parameter space that satisfy both of the following equations

$$\left\{ \begin{array}{l} (x-x_0)^2+(y-y_0)^2-r^2=0 \\ (x-... ...t\;\angle G=\cos\;\angle G/\sin\;\angle G \end{array} \right.$$

Geometrically these two simultaneous equations represent the intersection of a cone specified by the first equation and a plane specified by the second equation which passes through the axis of the cone, as shown in the figure below.

Solving these equations for $x_0$ and $y_0$, we get

$$\left\{ \begin{array}{l} x_0=x \pm r\;cos\;\angle G \\ y_0=y \pm r\;sin\;\angle G \end{array} \right.$$

and the algorithm for detecting circles:

• For any pixel satisfying $\vert G(x,y)\vert > T_s$, increment all elements satisfying the two simultaneous equations above;

  for all $r$

  {

  
  
  $$\left\{ \begin{array}{l} x_0=x \pm r\;cos\;\angle G \\ y_0=y \pm r\;sin\;\angle G \end{array} \right.$$
  
  
  
  
  $$H(x_0,y_0,r)=H(x_0,y_0,r)+1;$$
  
  

  }

• In the parameter space, any element $H(x_0,y_0,r) > T_h$ represents a circle with radius $r$ located at $(x_0,y_0)$ in the image.