The COTBLEDTCID approach to object detection and pose estimation, Part V – Circles detection

Introduction

Let’s do a summary of what we have done so far:

  • COT: colour thresholding. We separated yellow objects from the rest.
  • BLED: blob edge detection. We retrieved the bottom edges of blobs (pawns).
  • T: transformation. We transformed the image’s pixels into game field points (aka. pixels to meters).

And the last step CID: Circles Detection.

As you may have already noticed, pawns and tower of pawns are in fact circles when viewed from above. Therefore, the bottom edges we found with BLED are also circles’ segments when transformed into game field coordinates (step T). This is the property we’re exploiting below.

Algorithm

The secret here is to find the centre of the circles defined by the transformed edges. Then, we need to remove those which lay outside the game field, and finally we should merge those circles which are too close to each other.

Transform the bottom edges to field coordinates.
For each bottom edge
  Retrieve the 2 points that are the farthest from each other (The longer the edge, the more precise the centre is likely to be) :
    pLeft  = beginning of the bottom edge
    pRight = end of the bottom edge
  Given two points and the circle's radius (pLeft, pRight, r), find the circle's centre c

Remove any circle placed outside the game field

If any circle c overlaps any other circle c' then
  merge the circles' centre by averaging their positions with the means of a weighted mean to increase precision. The weight being the length of the edge.

Finding a circle’s centre is just a matter of solving (x - h)^2 + (y - k)^2 = r^2 for c=\begin{pmatrix} h \\ k \end{pmatrix} given 2 points p_1=\begin{pmatrix} x_1 \\ y_1 \end{pmatrix}, p_2 = \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} and the radius r.

It can be shown that the centre of the circle is given by:
c = \frac{1}{2}(p_1+p2 )\pm \sqrt{(\frac{r}{d})^2-\frac{1}{4}} \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} (p_2-p_1) where d = ||p_2 - p_1||

This equation has 2 solutions but only one gives the expected result. To choose the right sign, check whether p_1 and p_2 go counter-clockwise if yes the the sign should be +. In our case we go counter-clockwise because the points are always given from left to right.

Results

The original image:

Original image

The binary thresholded image:

Binary image

The bottom edges:Bottom edgesThe transformed bottom edges with the circles rendered on top of them:

Bottom Edges + CirclesThe final render :

Terrain rendered with circles and camera view

Discussion

We presented a simple yet effective method for finding circles’ centres. This is evidently not the only way of finding them, the more usual approach is by using Hough Cirlce Transforms. However, our method is much faster and does not have any special memory requirements as it is not probabilistic and requires only two points, and because the radius is known, high precision is achieved.

Another method we tried was the Least-Squares fit by R. Bullock, which gave pretty much the same results with a sightly heavier computational approach. The advantage of this last method is it uses all points from the edge to compute the circles’ centre, this may give better results when the first or the last points of the edge are not correctly found and have an offset. Practically this case rarely happened because pawns, which are yellow, have a very different colour from their entourage which is usually red, blue, green or black, and therefore pawns’ bottom edges are usually correctly determined.

What’s next

The fancy algorithms end here. Yeap, sorry about that. No more maths for today. 🙂

A conclusion and a summary of what has been done, what could be improved and what I have learned on the next post.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s