Checker Detection/Localization

In this article I’ll discuss multiple ways to localize a checker in an image.

“opencv” method

The opencv method is the defacto standard for checker localization. It’s fast, robust, accurate and is the checker localization algorithm used in Bouguet’s camera calibration toolbox. It is based on the observation that a vector with its tail at the center of a checker and the tip in a region around a checker should always have a zero dot product with the intensity gradient located at the tip of the vector:

Note that the example figures in this section are for a corner, but the same holds for a checker. Anyway:

in “flat” regions: $<\nabla I(\vec{p}),\vec{p}-\vec{q}> = 0$
in edge regions: $<\nabla I(\vec{p}),\vec{p}-\vec{q}> = 0$

The dot product is zero in “flat” regions because the image gradient is zero there. In edge regions, it’s zero because $\nabla I(\vec{p})$ and $\vec{p}-\vec{q}$ are orthogonal:

You can use this constraint to set up a linear set of equations to solve for $\vec{q}$ by sampling points (usually at integer pixel locations) around an initial guess of $\vec{q}$ :

Here’s the math:

$\nabla I_x (p_x-q_x) + \nabla I_y (p_y - q_y) = 0$

$\nabla I_x p_x- \nabla I_x q_x + \nabla I_y p_y - \nabla I_y q_y = 0$

$\nabla I_x q_x + \nabla I_y q_y = \nabla I_x p_x + \nabla I_y p_y$

Reformed as matrices:

$\begin{bmatrix}\nabla I_{x_1} & \nabla I_{y_1} \\ \vdots & \vdots \\ \nabla I_{x_N} & \nabla I_{y_N} \end{bmatrix}\begin{bmatrix} q_x \\ q_y\end{bmatrix}=\begin{bmatrix} \nabla I_{x_1} p_{x_1} + \nabla I_{y_1} p_{y_1} \\ \vdots \\ \nabla I_{x_N} p_{x_N} + \nabla I_{y_N} p_{y_N} \end{bmatrix}$

So now $\vec{q}$ can be solved for using a linear solver.

Some things you can do to improve this algorithm:

Apply a Gaussian kernel to the sampling points around $\vec{q}$ to give less weight to points further away from the checker center.
Apply multiple iterations until convergence is reached (i.e. the position of $\vec{q}$ moves less than a certain threshold)

If you’d like to see an example in action, you can download my camera calibration toolbox. The function which implements it is alg.refine_checker_opencv() and an example can be found in the unit tests folder.

“Edges” method

This is a cool method discussed in Mallon07. It tries to model the gradient magnitude of a checker with the following equation (note that I think the publication mistakenly switched $cos$ and $sin$ in the first term):

$\begin{gathered}{h_1}e^{-h_2^2((x-h_5)sin(h_3)-(y-h_6)cos(h_3))^2} + {h_1}e^{-h_2^2((x-h_5)sin(h_4)-(y-h_6)cos(h_4))^2} \\ - 2{h_1}e^{-h_2^2((x-h_5)^2+(y-h_6)^2)}\end{gathered}$

This equation is actually pretty cool. The first two terms are essentially Gaussian distributions along lines, added together. Where the lines intersect, the Gaussian’s are added twice, and because the gradient magnitude is zero in that region for a checker, these values must be subtracted, hence the “-2” coefficient on the third term. The “h” coefficients are described below:

$h_1$ – magnitude of the gradient peak
$h_2$ – variance (i.e. width) of the gaussian distribution
$h_3$ – angle of first line
$h_4$ – angle of second line
$h_5$ – x component of line-line intersection
$h_6$ – y component of line-line intersection

Since this equation is differentiable with respect to the “h” parameters, you can apply non-linear optimization to optimize them, and then get the center point from ( $h_5$ , $h_6$ ). I personally used matlab’s symbolic toolbox to do the symbolic differentiation since it helps prevent mistakes and is easier. I implemented the optimization with a simple Gauss Newton optimizer. One downside to this approach is you need to obtain initial guesses for the lines (even more difficult than an initial guess of a point needed for the opencv method). I did this by using a hough transform of the sub array containing the checker.

Below is an example of the optimization process:

Note that the final optimized edge function actually matches the array gradient for a checker very well.

If you’d like to see an example in action, you can download my camera calibration toolbox. The functions which implement it are alg.dominant_grad_angles() and alg.refine_checker_edges() and an example can be found in the unit tests folder.

“opencv” method

“Edges” method

Leave a Reply Cancel reply