In this project you will apply 2D projective geometry and math we learned in Chapter 1.
Suppose we have a planar tabletop in 'world space', and we have drawn some lines, points, and circles on that tabletop. The tabletop also contains a photograph of Leonardo DaVinci's 'Mona Lisa'. Next, we made a series of photograph of the tabletop as we walked around it with a camera, creating 2D images in 'image space'. We don't know the camera position or dimensions, and we don't even know if the camera's image plane is skewed or not (it might have affine distortions). However, we DO know something about the tabletop: some pairs of lines on it are parallel, some are perpendicular, and we know the exact position (in tabletop x,y) of the centerpoints of 4 circles. Also, we have some measurements taken from the photographs, giving the exact positions of the some of the lines and centerpoints.
Your mission is 'rectify' the image, to find out how to warp each photograph so that tabletop x,y corresponds to warped photo x,y. To do this, you must find the point mapping from 'world space' to 'image space' that is defined by the 3x3 projective 2D matrix H; the inverse of this mapping will rectify the image. You will write a program that reads in a file describing points or lines measured from an image. You program will then work backwards compute the H matrix that transforms world space to image space.
You can verify your work by using the H you
find to transform world space points, lines, and conics to image space.
Also note that you can make up your own examples to test your program:
--choose some convenient 'world space' points and lines, such
as points on a unit square, triangle or circle
--choose an arbitrary H matrix (be sure it has full rank,
though (use SVD)).
--Transform them to make corresponding 'image space' points
and lines using the H matrix you chose,
--Run your code using only the image space and world space
data: see if you can reconstruct H matrix.
Your program should do each one of these things:
1) Read a text only 'hint' file (defined below) to get measurements and determine the task.
2) If the file describes two groups of 4 points each, then solve for point transform H using 4-point correspondence. The first group are world-space points and the second group are image space points, both given in the same ordering:1st point in first group corresponds to 1st point in second group, etc. Note that this method rectifies completely--x,y of the rectified image matches x,y of the tabletop.
3) If the file describes two groups of 2 lines each, then solve for point transform H using the vanishing-point method. Each pair of lines were measured in image space (from the photograph), but we also know that in world space they are parallel lines. Assume all 4 lines are non-collinear. Note that this method rectifies only up to an affinity--there may still be some affine distortion if we apply H^-1 to the photograph.
4) If the file describes five groups of 2 lines each, then solve for point transform H using the C*_infinity conic method. Each pair of lines were measured in image space (from the photograph), but we also know that in world space they are perpendicular lines. Note that this method rectifies up to a similarity--there may still be residual rotation and scale distortion if we apply H^1 to the photograph.
5) Make an output file: copy the entire input 'hint' file,
then append your 'H' matrix in two forms:
--Human-readable: use the
Matrx::prnt() routine or something similar, then
--Machine-readable: write out your
matrix using the 'hint file' format.
To help you avoid matrix programming tedium, I have attached source code for C++ vector/matrix classes that I wrote and have used extensively: IBMRvecmat.cpp IBMRvecmat.h (if you use them in a non-MFC program, comment out the line #include "stdafx.h" at the top of IBMRvecmat.c). This gives you classes for 2,3,4 vectors, 2x2,3x3,4x4 matrices, vectors/matrices of arbitrary and changeable size (Matrx class), and integer-only vectors and matrices. For simplicity, you should probably use 'Matrx' class for everything, and you'll find member function SVD_full() to perform singular value decomposition for you.
Though I encourage you to
incorporate your work into the 3D viewer you made in Project 1, it is not
required.
You will not be penalized in any way if you choose instead to write a
stand-alone, command-line driven program invoked
by:
proj2 infile.hint outfile.hint
If MFC is your friend, then you may prefer to incorporate a file reader and writer for these 'hint' files into your viewer so you can see their results on-screen. Either way, don't let the vagaries of Windows MFC programming frustrate you or eat up too much of your time; it's the projective geometry that matters here.
1) Your program should read and write geometry data in a very simple ASCII text-only format I will call a 'hintfile', intended to be very easy to parse.
Hintfiles hold text that describes points, lines, conics, transform matrices
(H), and IBMR operations on all of them.
--A hintfile holds nothing but lines of case-sensitive text, and each line is
separated by a newline character(\n).
--Each line of text can be parsed separately and independently.
--Every line is either:
---a command line, which begins with the $ character, or
---a comment line, which begins with the # character(ignore
these lines), or
---blank, empty, or begins with whitespace (ignore these
lines), or
---something after the $EndHints command line; ignore it.
(Thus your program ignores everything except command lines, which always begin
with $ character.)
--Command lines all have the same syntax:
$<TextKeyword> (<whitespace>
<FloatEntry>)*
---<TextKeyword> is a single text string that contains
no whitespace chars.
---<whitespace> is any nonzero number of space or tab
characters. More formally: (space|tab)(space* | tab*)*
---<FloatEntry> is a single number that can be read by
scanf() as a valid floating-point number (float or double).
this includes all signed and unsigned integers, real numbers with a decimal
point, or numbers written in scientific notation, such as -1.234E-5 for
(1.234 x 10^-5).
---Note that there may be any number of <FloatEntry>
items on the line, but assume that the TextKeyWord will determine the number of
<FloatEntry> to read.
---Remember, some text editors balk at lines longer than 256
characters!
---The list of keywords may grow as the quarter progresses, but for
this assignment the only keywords are:
BeginHints
--the first line of any valid 'hintfile'. All files must begin with this
line.
EndHints
--the last usable line of a valid 'hintfile'. Your parser should ignore
any text after this line.
point_3 -- a 3-element point vector (x1,x2,x3),
line_3 -- a 3-element line
vector (l_1, l_2, l_3)
H_point_3 -- a 3x3 H matrix for point transformations, with all 9
elements
listed in row-major order: (h11, h12, h13, h21, h22,h23,
h31,h32,h33).
H_line_3 -- a 3x3 H matrix for line transformations with all 9
elements listed in row-major order.
C_point_3 --
a 3x3 C matrix for point conics,with all 9 elements listed in row-major order
C_line_3 -- a 3x3 C matrix for line conics, with all 9
elements listed in row-major order
group_point_3
-- a group of 1 or more 3-element point vectors. First <floatEntry>
specifies how many points,
followed by <floatEntry> values for each successive point (e.g. x11
x12 x13 x21 x22 x23)
group_line_3 -- a group of 1 or more 3-element line vectors. First <floatEntry>
specifies how many lines,
followed by <floatEntry> values for each successive line (e.g. l_11
l_1_2 l_13 l_21 l_22 l_23)
NEW COMMANDS added 4/30/2002
(to simplify your program)
do_4ptcorr_3 -- do 4-point correspondence in 2D projective
space to find H
do_vanish_3 -- do vanishing-point estimates from
parallel lines to find H
do_C*inf_3
-- use perpendicular lines and the C*_infinity conic to find H
(to help with memory
allocation).
max_point_3
--the number of 'point_3' items contained this file
This command must appear before any other 'point_3' related commands in
the file.
max_line_3 --
the number of 'line_3' items contained in this file.
This command must appear before any other 'line_3' related commands in the file.
max_H_point_3
--the number of 'H_point_3' items contained in this file.
This command must appear before any other 'H_point_3' related commands in the
file.
max_H_line_3
-- the number of 'H_line_3' items contained in this file.
This command must appear before any other 'H_line_3' related commands in the
file.
max_C_point_3 --
the number of 'C_point_3' items contained in this file.
This command must appear before any other 'C_point_3' related commands in the
file.
max_C_line_3 -- the
number of 'C_line_3' items contained in this file.
This command must appear before any other 'C_line_3' related commands in the
file.
max_group_point_3
-- the number of 'group_point_3' items contained in this file.
This command must appear before any other 'group_point_3' related commands in
the file.
max_group_line_3 --
the number of 'group_line_3' items contained in this file.
This command must appear before any other 'group_line_3' related commands in the
file.
Example HintFile: ______________________________________________________________ $BeginHints
#(first line of file must always begin hintfile\n )
# comments lines always begin with # sign # Blank lines are ignored
max_line_3 10 # no more than 10 line_3 items will be found in the file below # (actually there are only 3 line_3 items, and 1 point_3 item max_point_3 10
$line_3 3 0 1E-7
# Comment lines can be placed anywhere except 1st line of file
$point_3 21.2345352342342 -3.14156E-03 .12
$H_point_3 1.0 -0.0 2.0 0.0 1.0 1.0 0.0 0.0 2.0
# and now, the world-space C*_{infinity} conic:
$C_line_3 1.0 0.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0
# now a group of two points (one is an ideal point)
$group_line_3 2 0.0 0.0 1.0 1.0 1.0 0.0
# your parser should stop reading the file after a line that begins $EndHints # like this one:
$EndHints
The $EndHint line allows you to append plain text of any sort,
including printouts of the matrices you compute. The matrices below
were prettyprinted by Matrx::prnt("title string") function.
-----------A matrix: 3 rows, 4 cols----------
88.656270 653.798029 -451.094089 614.551225
596.850490 814.874722 -440.290536 447.248756
-539.658803 -731.803339 681.020539 799.798578
-----------USVT matrix: 3 rows, 4 cols----------
88.656270 653.798029 -451.094089 614.551225
596.850490 814.874722 -440.290536 447.248756
-539.658803 -731.803339 681.020539 799.798578
-----------Error: USVT-A: 3 rows, 4 cols----------
-0.000000 -0.000000 0.000000 -0.000000
-0.000000 -0.000000 -0.000000 0.000000
0.000000 0.000000 -0.000000 -0.000000
$BeginHints
$do_4ptcorr_3
# Test for 4-point correspondence. Output points were made by # transforming input points to output points using this (point) H matrix: # H = [ 1 3 0] # [-1 2 4] # [ 2 1 1] # File contains 4 groups of 2 points each. $max_group_point_3 4 $max_point_3 8 # Each point group holds an input (x,y), output (x',y') pair # NOTE!! the third number (x3) in each point is MEANINGLESS!! # The 1st and 2nd entries for the point hold (x,y) values # DO NOT use x3=1 for your output: it won't work! $group_point_3 2 0 0 1 0.0 4.0 1 $group_point_3 2 1 0 1 0.333333333 1.0 1 $group_point_3 2 1 1 1 1.0 1.25 1 $group_point_3 2 0 1 1 1.5 3.0 1 $EndHints ______________________________________________________________ $BeginHints $do_vanish_3 # Test for vanishing-point method. Remember, this only finds the # projective part of the H matrix; it 'rectifies up to an affinity'. # Thus the H matrix you'll find is Hp, whose only free variables are # on the bottom row; the rest is identity matrix. # transforming input lines to output lines using this (point)Hp matrix: # (Hp^-T * Lin = Lout) where # Hp = [ 1 0 0] so Hp^-T= [1 0 -3] # [ 0 1 0] [0 1 -4] # [ 3 4 1] [0 0 1] # I computed output lines La,Lb,Lc,Lc by Hp^-T $max_group_line_3 2 $max_line_3 4 # File contains two pairs of parallel lines. In world space these # lines are ax +by +c = 0, or in another form, (a/c)x+(b/c)y +1 = 0. # La = 1 $group_line_3 2 -1 -5 1 -2 -4.5 1 $group_line_3 2 -2 -2 1 -2.75 -3.5 1 $EndHints ______________________________________________________________ $BeginHints do_C*inf_3 # Test for C*_infinity method. This find the projective and affine # part of the H matrix: it 'rectifies up to a similarity'. # Requires 5 perpendicular lines pairs in image space, (finish later!) #5 groups of 2 lines each $max_group_line_3 5 $max_line_3 10
$EndHints ______________________________________________________________