Detection of Ellipses

Here we assume the axes of the ellipses are in parallel with the coordinates of the image space, i.e., the equations specifying the ellipses are in the following standard form

$$f(x,y,x_0,y_0,a,b)=\frac{(x-x_0)^2}{a^2}+\frac{(y-y_0)^2}{b^2}-1=0$$

where $x_0$, $y_0$, $a$ and $b$ are four parameters which span a 4D parameter Hough space. To use $\angle G$, consider

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

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/a^2+(y-y_0)^2/b^2-1=0 \\ (x-x_0)b/(y-y_0)a=cot\;\angle G \end{array} \right.$$

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

$$\left\{ \begin{array}{l} x_0=x \pm a\;cos\;\angle G \\ y_0=y \pm b\;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 $a$ and all $b$

  {

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

  }

• In the parameter space, any element $H(x_0,y_0,a,b) > T_h$ represents an ellipse detected in the image.