Real-time ellipse detector

The first step in developing an application that works with augmented reality is to select a label with its subsequent recognition in real time. A number of algorithms suggests using specially created tags, a number is trained on a suitable image, we decided to dwell on the fact that almost everyone has at hand - coins. Their choice as labels and led us to the task of finding ellipses. Of course, due to camera distortions and the small cylindrical nature of the coin in the image is not always an ellipse, but rather close in shape to this curve. As a target platform, a modern phone on an ARM processor was chosen. Real-time additions require at least 20 frames per second, so you can spend no more than 50 milliseconds to process each frame.



So, the task is to find ellipses on the image. To begin with, we looked for ready-made implementations and found such a detector . Its algorithm is as follows:

1. Select the contours of the detector Kany
2. We divide the border segments into 2 groups (1, 3 and 2, 4) in the direction of the gradient, then each further by two, depending on the direction of convexity
   ')
   
   
   
3. Select three segments lying close enough from different groups.
4. If these are parts of one ellipse, then straight (black) lines drawn through the centers of the chords (red and blue) will pass through the center of the ellipse. For each pair of adjacent segments, we construct two such straight lines and get the center for each pair. If the centers are close enough, then we found an ellipse:
   
   
5. Calculate the equation of the ellipse in three segments

Unfortunately, in practice, the algorithm gave a lot of lying ellipses, a large error in the parameters of the found ellipses and a lot of false positive detektov. Soon another work was found, the detector of which can be tested online . On the basis of it, in the end, an acceptably working algorithm was created, consisting of the following key stages:

Gaussian Blur, Gradient Acquisition Horizontal, Vertical, and Magnitude by the Pruitt Operator

Repeatedly described step, but it was his modification that significantly increased the performance of the solution. At first they wrote “in the forehead”: they calculated float coefficients, 25 pixels were processed for each pixel (5x5 matrix, because they used a 5-core kernel) - multiplied by coefficients, added and normalized. Then the Pruitt operator was calculated - here, to get the value at each point in one direction, it is necessary to process 6 pixels, but due to the generality of the code to calculate the vertical and horizontal gradients, “ran” 9 (3x3).

As a result, this step alone has already exceeded the required threshold for a picture with a resolution of 320x240. Rewrote the blur from float to uin32_t for 9 (3x3 matrix - reduced the core to 3) pixels, and when calculating the Prewitt operator, they got rid of the generality of the code and also calculated on whole numbers.

At a later stage, it turned out that blurring can be avoided altogether, since, with the resolution chosen by us for processing, it does not significantly affect the final result. The calculation of the magnitude by the operator Pruitt can be accelerated through the use of SIMD instructions (for ARMs - NEON), but this also turned out to be not very necessary - the previous steps for optimization were quite enough.

The pictures below show magnitude, vertical and horizontal gradients:

Building Border Segments

In the algorithm chosen for implementation, the boundaries are searched for by the author's method - the edge drawing method. This step in the work is described extremely vaguely, after several implementations came to the following:

1. choose key points (anchors) - a point with a magnitude, a larger threshold and neighbors;
2. sort them by decreasing magnitude;
3. starting at the next unused point, we assemble the border segment as follows:
   
   • choose one of four directions (right / left / up / down), taking into account the direction of the gradient at the current point and the magnitude of the neighbors;
   • select three points in this direction and go to the unused point with the greatest magnitude, checking at each step whether the gradient direction has changed;
   • if the direction has changed, we analyze 6 points (three neighbors on each side) and again select an unused point with a larger magnitude;
   • stop if there is nowhere else to go.
   
   

Elimination of insignificant segments according to the Helmholtz principle

The filtering of significant segments in the original article is described well, for a complete understanding, you can read the article “Edge Detection by Helmholtz Principle” or the book “From Gestalt Theory to Image Analysis. A Probabilistic Approach . I will give only formulas and sequence of actions:

1. We construct a histogram (H), so that for each value of magnitude we calculate the number of pixels for which the magnitude is greater than or equal to a given one;
2. calculate Np, where l is the segment length;
   
3. The importance of a segment depends on the smallest magnitude of the points in it and the length. Substitute the formula for the length - L and the minimum magnitude - m. If NPA is less than 1, then the segment is left; otherwise, divide by the weakest point by two and repeat the procedure.
   
   
   

This is what we get after filtering:

Linearization of segments

1. We take several points from the previously found boundary segment and believe that they lie approximately on one straight line.
2. We add points while we keep within an error

Arc construction

In the original article it is proposed to build arcs of circles, but here we decided to build arcs of ellipses, since sometimes you can immediately get a large enough part of the ellipse, and this does not have a significant impact on the computation time. To build, we find three or more straight lines located in a row on one segment, with the angles between the straight lines must be in a certain range, and the turn must be in the same direction. We inscribe the resulting arc of the ellipse using the method of least squares (described below) and check the error.

Combining arcs into ellipses

We look for nearby suitable pieces of the ellipse and again use the least squares method, counting the error and discarding candidates that exceed the selected error threshold.

Least square method

Described here . I had to “tie” the Eigen library to calculate the eigenvalues ​​of the matrix, well, to translate the code from MATLAB to C ++ (thanks to Octave ).

Detector demonstration

That's all the steps to find the ellipse in the image, then goes its tracking, stabilization, filtering of embedded ellipses (on a coin of 10 rubles, up to 3 pieces are detected). To complement reality, it remains only to restore the position of the plane and add cool objects.

The result can be viewed here - an application with a detector (caution: the two right buttons write png on / mnt / sdcard / i).

PS In the process, a convenient extension to Visual Studio was found that allows you to view the image in debug mode - Image Watch . Many thanks to Microsoft.