metric rectification from circles

The circular points encode the metric structure of the 2D plane. They are invariant to rotation, isotropic scaling and translation. If the plane undergoes a more general (e.g. affine or projective) transformation  they move to some unknown location. Metric rectification can be performed if we find the image of the circular points and move them back to their original location. These points are not directly visible in the image but can be indirectly found using for instance the images of right angles [HZ].

The circular points can also be extracted from the images of two circles [IC]. Any two circles in general position intersect at two possibly complex points. Interestingly, if we allow points at infinity there are two additional intersection points: the circular points (1,i,0) and (1,-i,0), which belong to all circles. If the plane suffers a projective transformation the circles become general conics (in a perspective view with the circles in front of the camera the images are ellipses). Incidence and tangency are preserved by projective transformations, so the images of the circular points are among the intersections of the observed ellipses.

This nice visual geometry result is illustrated by a simple easyVisio demo. I like it because it touches many interesting mathematical themes. I have recently rewritten the code to use higher level combinators.

To achieve metric rectification of a plane containing the image of several circles we must solve the following subproblems. All of them involve interesting mathematical results.

1) Detection of salient regions in the image. We can use fixed gray level thresholding and extraction of connected components, which can be represented by reduced contours:

2) Find elliptical shapes, and estimate the conic parameters:

3) Compute the intersection of two ellipses (e.g. the two bigger ones). We must find the roots of a polynomial of degree 4. It is a good idea to move the problem to a reduced form in which one of the ellipses is the unit circle and the other one has only 4 parameters (center and axes). A polynomial of degree 4 can in principle be solved in closed form, but we can also try simpler numeric methods. We can compute the eigenvalues of the companion matrix or directly use the GSL polynomial solver also available from hmatrix.

We get two pairs or complex conjugate solutions, which define two real lines. We can easily separate the "true" circular points, which define the horizon, from the other "normal" intersections:

intersections of the two bigger ellipses (real part and lines joining them)

The rectification transformation can be easily computed from the imaged circular points:

If the aspect ratio and principal point are known the focal length can be inferred and a full camera can be recovered. Then we can insert virtual objects in the scene

and show the camera position in 3D space:

It is also interesting to show a graphic representation of the projective invariants of two conics. They are closely related to the common tangents, which can be computed as intersections of the corresponding dual conics:

eigenvectors of C1*inv C2 (yellow) and common tangents (orange)

The demo program is just a composition of pure functions for the above steps. We intercalate several monitoring windows in the pipeline. The source code looks simple but it uses many tools from the easyVision packages. Here is a video of the program in action: