Calculate centers of circles from their ellipse perspective.

Question

Originally there are 4 circles in a plane and after perspective transform we get four conics. Now I know the equation of those ellipses. How could I get the origin of those four circles ?

I know it's impossible to get the center just by one circle, but they are four of them, and the relationship between the original circles is known. How could I use this prior information to do the calculation ?

Thanks!

Answer 1

One approach can be: from at least 4 point correspondences a perspective transformation matrix (plane -> plane) can be computed, which you can apply to the circle centers.

Now how to establish point correspondences? At first we only have corresponding point sets:

• circles corresponding to ellipses
• in most cases also tangents touching two circles corresponding to tangents touching two ellipses

Point correspondences can be established from intersections of corresponding point sets:

• circle intersections corresponding to ellipse intersections
• intersections of common circle tangents corresponding to intersections of common ellipse tangents
• circle-with-tangent intersections corresponding to ellipse-with-tangent intersections

When will this approach not work? If for each pair one of the circles contains the other.

As soon as two circles do not contain each other, this approach should work.

From the above image it may seem that only two circles suffice, but at least a third circle is needed to uniquely establish the correspondences.

Answer 2

If the horizon line is known, then you can find the center even with one circle only. Just find the two lines parallel to the horizon and touching the ellipse and let $A$, $B$ be the points of tangency. Line $AB$ intersects the horizon at $P$, which is the vanishing point for two sides of a square circumscribed to the circle and having the other two sides parallel to the horizon. Two lines through $P$ are tangent to the ellipse: together with the two parallels they form a trapezoid which is the transformed of the square. The point of intersection of its two diagonals is then the transformed of the center.

Line $AB$ is a diametral line of the ellipse, conjugated to the diameter parallel to the horizon line. If you draw another chord of the ellipse parallel to the horizon line and find its midpoint $M$, the line passing through $M$ and the center $O$ of the ellipse is precisely $AB$: this suggests a fast way to find that line.

If the horizon line is not known, then you need at least three ellipses. For every direction $m$ of the horizon line and for each ellipse one can find, as described above, the diametral line conjugated to direction $m$. For a certain $m$ those three lines will meet at the same point $P$, which is the vanishing point described above. Once you have found $P$, you can proceed as explained above to find the centers of the original circles.

Answer 3

One can also use the cross-ratio, which is invariant under perspective transformation, for finding the transformed circle centers. For four different points $A,B,S,T$ on a line the cross-ratio is defined as $$(A,B;S,T) := \frac{|AS|}{|SB|} : \frac{|AT|}{|TB|}$$

For a configuration of two circles like in the image below I could prove that the cross-ratio (A,B;S,T) reaches its maximum for the line through the two centers: $$(A_0,B_0;S_0,T_0) > (A,B;S,T)$$ So when maximizing the corresponding cross-ratio for the intersection points of the corresponding ellipses with a line (two parameter, well conditioned optimization problem), one will get the same maximal value and a line through the transformed circle centers.

Doing this pairwise with 3 circles (that do not contain each other and who's centers are not on a line) will give three lines intersecting each other at the transformed circle centers.

For other circle configurations (intersecting circles or one circle containing the other) it still remains to check, if the cross-ratio reaches an extreme value when the line generating the intersection points runs through both centers (left as an exercise to the reader :-) ).

Note that for two touching circles the line through both circle centers generates only 3 intersection points, so if there are too many pairs of touching circles this method fails (at least I have not found a way to deal with it using cross ratios).