Introduction to homography

1. IntroductionIntroduction
toto
HomographyHomography
2010.01.19

2. Coordinate System
view coordinate
system
object coordinate
system
x
y
z
world coordinate system

3. History
P->G:
以
E 為眼點從平面
G到平面W的透視對應

4. Outline
•Projective Geometry
•Projective Transformation
•Estimation
•Document Perspective Distortion
•Direct Linear Transform (DLT) Algorithm
•OpenCV Implementation

5. Homo. representation (1)
•Lines
•This equivalence relationship is known as a
homogeneous vector
0ax by c+ + = ( , , )
T
abc
( ) ( ) ( ) 0ka x kb y kc+ + = ( , , )
T
k abc
representative

6. Homo. representation (2)
•Points
0ax by c+ + =( , )
T
x y on
[ ]( , ,1)( , , ) 1 0
T
a
x y abc x y b
c
é ù
ê ú
= =
ê ú
ê ú
ë û
1 2 3
( , , )
T
x x x
2
1 3 2 3
( / , / ,1) in
T
x x x x R
Homo. representation

7. Degree of freedom (DoF)
•Point
•Line
( , ) :2
T
xy DoF
{ }( , , ) : : :2
T
abc a b c DoF

8. •2 lines
•Assume
Intersection of lines (1)
( , , ) ( , , )
T T
l abc l a b c¢ ¢ ¢ ¢= =
( ) ( )0 0
x l l
l l l l l l l x l x
¢= ´
¢ ¢ ¢ ¢× ´ = × ´ = Þ × = × =
The intersection of two lines and ' is the pointl l x

9. Intersection of lines (2)
•Ex: determining the intersection of the
lines x = 1 and y = 1
( )
( )
( )
: 1 1 0 1,0,1
: 1 1 0 0, 1,1
0 1 1 1 1 0
1 0 1
1 1 0 1 0 1
0 1 1
1,1,1
T
T
T
l x x
l y y
i j k
x l l i j k
= - + = -
¢= - + = -
- -
¢= ´ = - = - +
- -
-
=
y = 1
x = 1

10. Line joining points
•The line passing through two points x and
x’
•Assume
The line through two points and 'is 'x x l x x= ´
( ) ( )0 0
l x x
x x x x x x x l x l
¢= ´
¢ ¢ ¢ ¢× ´ = × ´ = Þ × = × =

11. Line at infinity (1)
•Consider 2 lines
•Intersection
: 0 : 0
( , , ) ( , , )
T T
l ax by c l ax by c
l abc l abc
¢ ¢+ + = + + =
¢ ¢= =
( ) ( ) ( )( ), ,0
T
b c c a c c
i j k
b c a c a b
x l l a b c i j k
b c a c a b
a b c
i j c c b a
¢= ´ = = - +
¢ ¢-
¢ ¢
¢
¢= - = - - -

12. Line at infinity (2)
•Inhomogeneous representation
•No sense! Suggest the point has infinitely
large coordinates
( )( ), ,0 ,
0 0
T
T b a
c c b a
-æ ö
¢- - Þ
ç ÷
è ø
Homogeneous coordinates (x, y, 0)
T
do not
correspond to any finite point in R
2

13. Line at infinity (3)
•Ex: intersection point of 2 lines x=1 and
x=2
( )1 0 1 0,1,0
1 0 2
T
i j k
x l l¢= ´ = - =
-
The point at infinity in the direction of the y-
axis

14. Line at infinity (4)
•Projective Space P
2
: augment R
2
by
adding points with last coordinate x
3
= 0 to
all homogeneous 3-vectors
•The points with last coordinate x
3
= 0 are
known as ideal points, or points at infinity
•The set of all ideal points may be written
(x
1
,x
2
, 0)
T
. The set lies on a single line, the
line at infinity, denoted by the vector
(0,0,1)
T
=> (x
1
,x
2
,0)(0,0,1)
T
=0

15. Concept of points at infinity
•Simplify the intersection properties of
points and lines
•In P
2
, one may state without qualification
(not true in the R
2
)
•2 distinct lines meet in a single point
•2 distinct points lie on a single line

16. A model for the projective
plane
Points and Lines of P
2
are
represented by Rays and Planes,
respectively, through the origin in R
3
Lines lying in the x
1
x
2
-plane
represent ideal points, and the
x
1
x
2
-plane represents l
∞

17. Outline
•Projective Geometry
•Projective Transformation
•Estimation
•Document Perspective Distortion
•Direct Linear Transform (DLT) Algorithm
•OpenCV Implementation

18. Mapping between planes

19. Definition (1)
•A projectivity is an invertible mapping h
from P
2
to itself such that 3 points x
1
, x
2

and x
3
lie on the same line if and only if
h(x
1
), h(x
2
) and h(x
3
) do
•Synonymous
•Collineation
•Homography

20. Definition (2)
•A mapping h from P
2
to P
2
•There exists a non-singular 3 x 3 matrix H
such that for any point in P
2
represented
by a vector x it is true that
1 11 12 13 1
2 21 22 23 2
3 31 32 33 3
x h h h x
x h h h x
x h h h x
¢æ ö é ùæ ö
ç ÷ ç ÷ê ú
¢=
ç ÷ ç ÷ê ú
ç ÷ ç ÷
¢ê ú
è ø ë ûè ø
( )x H x¢=

21. Definition (3)
•H is a homogeneous matrix, since as in
the homogeneous representation of a
point, only the ratio of the matrix
elements is significant (Dof = 8)

22. A hierarchy of
transformations (1)

23. A hierarchy of
transformations (2)
0 0
0 1 0 1
T
s A P T T T T
sR t K I sRK tv t
H H H H
v v v v
é ù+é ùé ùé ù
= = = ê úê úê úê ú
ë ûë ûë û ë û

24. Outline
•Projective Geometry
•Projective Transformation
•Estimation
•Document Perspective Distortion
•Direct Linear Transform (DLT) Algorithm
•OpenCV Implementation

25. Document Distortion

26. Correction

27. 2D Homography
•x
i
in P
2
x
j
in P
2
•In a practical situation, the points x
i
and x
j

are points in 2 images (or the same
image), each image being considered as a
projective plane P
2

28. DLT Algorithm (1)
1 2 3
4 5 6
7 8 9
,
1 1
u x h h h
cx Hx x v x y H h h h
h h h
é ù é ù é ù
ê ú ê ú ê ú
¢ ¢= = = =
ê ú ê ú ê ú
ê ú ê ú ê ú
ë û ë û ë û
1 2 3
4 5 6
7 8 9
1 1
u h h h x
c v h h h y
h h h
é ù é ùé ù
ê ú ê úê ú
=
ê ú ê úê ú
ê ú ê úê ú
ë û ë ûë û
1 2 3
4 5 6
7 8 9
cu hx h y h
cv h x h y h
c h h h
= + +
= + +
= + +
( )
( )
1 2 3 7 8 9
4 5 6 7 8 9
0
0
hx h y h h h h u
h x h y h h h h v
- - - + + + =
- - - + + + =

29. DLT Algorithm (2)
•Since each point correspondence provides
2 equations, 4 correspondences are
sufficient to solve for the 8 degrees of
freedom of H
•Use more than 4 correspondences to
ensure a more robust solution (The
problem then becomes to solve for a
vector h that minimizes a suitable cost
function)

30. Outline
•Projective Geometry
•Projective Transformation
•Estimation
•Document Perspective Distortion
•Direct Linear Transform (DLT) Algorithm
•OpenCV Implementation

31. OpenCV Implementation
•Mat findHomography(
const Mat& srcPoints,
const Mat& dstPoints,
int method=0,
double ransacReprojThreshold=3);
•void warpPerspective(
const Mat& src,
CV_OUT Mat& dst,
const Mat& M,
Size dsize,
int flags=INTER_LINEAR,
int borderMode=BORDER_CONSTANT,
const Scalar& borderValue=Scalar());
Homography Estimation
Projective Transform

32. Reference
•Multiple View Geometry in Computer Vision, Cambridge
University Press, 2000.
•Projective geometry and homogeneous coordinates
[Video] -
http://www.youtube.com/watch?v=q3turHmOWq4