An Effective Rigidity Constraint for Improving RANSAC in Homography Estimation - Advanced Concepts for Intelligent Vision Systems - page 209

a) cross product when “turning left” a) cross product when “turning right”

Fig. 4. Sign of the cross product as a function of the kind of “turn” in an oriented path

fully convex shapes and the shapes with one concavity, any possible closed path
linking their four points and oriented in such a way as to reflect the order of
the points. There are exactly fourteen possibilities represented in figure 3. Let
us now consider the different direction turns necessary to follow the paths and
code each path in a sequence of “ ” corresponding to “turn left” and

“turn right”, respectively. It is obvious, from the four-digit chain codes reported
in figure 3, that the codes formed in this way are unique and that each of them
represents a different path. In the context of image registration, it means that
if the chain code formed from the four points of a first image is the same as
the one obtained from the corresponding points in a second image, the shapes
they constitute are the same in both images and the point correspondences are
ordered in the same way. Hence, this condition is sucient and necessary for the
homography estimation based on these four point correspondences to produce a
rigid-body transformation.

1 ”and“ − 1

3.3 Mathematical Expression of the Rigidity Constraint
The expression of the chain code introduced in the previous section does not
necessitate processing the value of the angle formed by the three consecutive
points of an oriented path. Indeed, as it is only important to identify the direction
of the turns, let us simply consider the cross product V n ×

V n +1 of the vectors
V n and V n +1 which are respectively defined from point n to point n +1 and from

point n . Figure 4 highlights that the direction turns are simply

given by the direction, i.e. the sign, of the cross product V n ×

+1 to point n +2

V n +1 . The rigidity

constraint can then be expressed as:

sign V n × V n +1 ∀n =1 .. 4 , with V 5 = V 1 and V 5 = V 1 ,

(8)

sign ( V n × V n +1 )=

where vectors V n and V n +1 are formed from points of a first image, while V n and

0) , V n +1 are formed from their correspondents in a second image. Given

( x n ,y n ,

the Euclidean coordinates of a pixel p n , a vector V n can be written:

0) =( 0) . V n =( V x n ,V y n , x n +1 − x n ,y n +1 − y n , (9)