Stereopsis

Prévia do material em texto

6/4/2013 Stereopsis 1 
Stereopsis 
Raul Queiroz Feitosa 
6/4/2013 Stereopsis 2 
Objetive 
 
 
 This chapter introduces the basic techniques for a 3 
dimensional scene reconstruction based on a set of projections 
of individual points on two calibrated cameras. 
6/4/2013 Stereopsis 3 
Content 
 Introduction 
 Reconstruction 
 The Correspondence Problem 
 Rectification 
6/4/2013 Stereopsis 4 
Introduction 
Correspondence 
 Detection of corresponding points in a pair of stereo 
images. 
 
Reconstruction 
 Based on a set of corresponding points, compute its 3D 
position in the world. 
 
6/4/2013 Stereopsis 5 
Content 
 Introduction 
 Reconstruction 
 The Correspondence Problem 
 Rectification 
6/4/2013 Stereopsis 6 
Midpoint Triangulation 
R 
OP1 P1P2 P2O´ OO´ + = + + = 
O 
 ´ 
R´ P1 
P2 
P 
O´ 
 p ^ 
 p´ 
normalized 
frames 
^ 
OP1 
P1P2 
P2O´ 
OO´ 
6/4/2013 Stereopsis 7 
Midpoint Triangulation 
OP1 P1P2 P2O´ OO´ + = + + (a,b and c can be computed) = a p 
^ b (p Rp´) ^ ^ 
where R is the rotation matrix of the right camera frame and t is the vector 
connecting the principal points, both in relation to the left camera frame. 
Expressing the equation in the normalized left camera frame, yields: 
OP1 
P1P2 
P2O’ 
OO’ 
t 
a p ^ 
b (p  Rp´) ^ ^ 
 cRp´ ^ 
O 
 ´ 
R´ P1 
P2 
P 
O´ 
 p ^ 
 p´ 
normalized 
frames 
^ 
c Rp´ ^ 
t 
R 
6/4/2013 Stereopsis 8 
Midpoint Triangulation 
Algorithm 
 Given p, p´, K, R, t, K´, R´ and t´ 
1. Compute 
p= K -1 p 
p´=K´ -1 p´ 
R=RR´-1 (→ rotation relative to the left camera frame) 
t=-RR´-1 t´+t (→ translation relative to the left camera frame) 
^ 
^ 
6/4/2013 Stereopsis 9 
Midpoint Triangulation 
Algorithm (cont.) 
2. Compute a, b and c such that 
a p + b (p  Rp´)+ c Rp´=t 
3. Compute CP in the left camera frame with 
CP= a p + b (p  Rp´)/2 
4. If you wish, transform CP to the world frame, 
 
WP= R-1 (CP – t) 
^ ^ ^ ^ 
^ ^ ^ 
t ≠ t 
6/4/2013 Stereopsis 10 
Linear Reconstruction 
 
 
 
 
 
 It is a system with 4 independent linear equations 
([p] e [p´] have rank 2). 
 It can be applied for more than 2 cameras. 
 
z p = M P 
z´ p´ = M´ P 
 
 
p  M P = 0 
p´  M ´ P = 0 
 
 [p] M 
 
[p´] M´ 
P = 0 
6/4/2013 Stereopsis 11 
Geometric Reconstruction 
 
 
 
 
 
 
 
 
 
 
The point Q with images q e q’ where the rays do intercept are such that 
d2(p,q) + d2(p´,q´) under qTF q´ =0 is minimum  a non linear system. 
O 
 ’ 
R 
R’ P1 
P2 
P 
O’ 
 p ^ 
 p’ ^ 
 q q’ ^ quadros 
normalizados 
^ 
Q 
6/4/2013 Stereopsis 12 
Geometric Reconstruction 
Algorithm – geometric interpretation 
 The noise free projections lie on a pair of corresponding 
epipolar lines 
θ(t) 
p 
q 
l=FTq΄ 
e 
left image 
θ΄(t) 
p΄ 
q΄ 
l΄=Fq 
e΄ 
right image 
measured 
points 
optimal 
points 
epipolar 
line 
epipolar 
line 
6/4/2013 Stereopsis 13 
Geometric Reconstruction 
Algorithm outline 
1. Parameterize the pencil of epipolar lines in the left image by a 
parameter t  l(t ) 
2. Using the fundamental matrix F, compute the corresponding epipolar 
line in the right image  l´(t ) 
3. Express the distance d2(p,l(t )) + d2(p´,l´(t )) explicitly as function of t 
 a polynomial of degree 6. 
4. Find the value of t that minimizes this distance. 
5. Compute q and q’ and from them Q. 
 
Details can be found in 
Multiple View Geometry in computer Vision, Hartley,R. and Zisserman, A., pp 315… 
6/4/2013 Stereopsis 14 
Evaluation on Real Images 
From 
Multiple View Geometry in computer Vision, Hartley,R. and Zisserman, A., pp 315… 
0.6 
0.5 
0.4 
0.3 
0.2 
0.1 
0 
R
ec
o
n
st
ru
ct
io
n
 E
rr
o
r 
0 0.05 0.1 0.15 
Standard Deviation of Gaussian noise 
Midpoint 
Geometric 
6/4/2013 Stereopsis 15 
Evaluation on Real Images 
 Points are less precisely located along the rays as the 
rays become more parallel 
uncertainty regions 
Texturing 3D Models 
watch 
6/4/2013 Stereopsis 17 
Content 
 Introduction 
 Reconstruction 
 The Correspondence Problem 
 Rectification 
6/4/2013 Stereopsis 18 
The Correspondence Problem 
Introduction 
 Assume the point P in space emits light with the same energy in all 
directions (i.e. the surface around P is Lambertian) 
 
 
 
 
 then 
 I(p) =I´(p´) (brightness constancy constraint) 
 where p and p´ are the images of P in the views I and I´. 
 The correspondence problem consists of establishing relationships 
between p and p´, i.e. 
 I(p) =I´( h(p) ) ( h → deformation) 
P 
I1 I’ 
O O’ 
p p’ 
6/4/2013 Stereopsis 19 
The Correspondence Problem 
Introduction 
 It is difficult to locate an accurate match for points lying 
in uniform neighborhoods. 
 Also difficult is the location of points close to edges. 
 Therefore, before we start searching for pairs of 
corresponding points, it is convenient to establish which 
points in one image have good characteristics for an 
accurate match. 
 They must be in neighborhoods with high dynamics. 
6/4/2013 Stereopsis 20 
The Correspondence Problem 
Local deformation models 
 We look for transformations h that model the deformation 
on a domain W(p) around p=[u v]T. 
 Translational model 
h(p) = p +Δp 
 
 Affine model 
h(p) = A p + Δp, 
 where A  R2×2 
 
 Transformation in intensity values 
I(p) =I’( h(p) ) + η( h(p) ) 
W(p) 
Δp 
W(p) 
(A,Δp) 
6/4/2013 Stereopsis 21 
The Correspondence Problem 
Matching by Sum of Squared Differences (SSD) 
 We choose a class of transformation and look for the 
particular transformation h that minimizes the effects of 
noise integrated over a window W(p), i. e., 
 
 
 
 If I(p)=constant, for p  W(p), the same happens for I´, and 
the norm being minimized does not depend on h!!!! 
(blank wall effect) 
    
 



pp
pp
Wh
hIIh
~
2~~
minargˆ
6/4/2013 Stereopsis 22 
The Correspondence Problem 
Matching by Normalized Cross-Correlation (NCC) 
 SSD is not invariant to scaling and shifts in image intensities 
(deviation from the Lambertian assumptions). 
 The Normalized Cross-Correlation (NCC) 
 
 
 
 
 where and are the mean intensities of I and I’ on W(p). 
 -1 ≤ NCC ≤ 1. If =1, I(p) and I’( h(p) ) match perfectly. 
 
 
      
 
  
 
   
 




pp
p
pp
pp
WW
W
IhIII
IhIII
hNCC
22 ~~
~~
I I 
6/4/2013 Stereopsis 23 
The Correspondence Problem 
Matching by NCC 
 For the translational model → h(p) = p +Δp. 
 
 
 
 
W(p) 
→ - = 
I(p) 
I 
_ 
I(p)- I 
_ 
→ - = 
I’(p+Δp) 
I’ 
_ 
I’(p+Δp) -I’ 
_ 
→ v1 
→ v2 
NCC= 
_______ 
||v1|| ||v2|| 
 v1 ·v2 
NCC is equal to the 
cosine 
between v1 and v2 
W(p) 
6/4/2013 Stereopsis 24 
The Correspondence Problem 
Matching by NCC (example) 
6/4/2013 Stereopsis 25 
Least Square Matching 
Affine model → p´ = h(p) = A p +Δp 
 Let’s assumethat 
 
 
 
 
 Thus 
u´=a11u+ a12v+b1 
 and 
v´=a21u+ a22v+b2 
 



























2
1
2221
1211
 , , , 
b
b
aa
aa
A
v
u
v
u
ppp
6/4/2013 Stereopsis 26 
Least Square Matching 
Affine model → p´ = h(p) = A p +Δp 
 Matching is established if (SSD) 
 
 → 
 
 
 
 
 
 that can be written in more compact form as … 
 
      vd
v
I
ud
u
I
vuIvuIvuI 





 , ,,
00
     
 
2220210
112011000
 
 ,-,
dbdavdaug
dbdavdaugvuIvuI
v
u




6/4/2013 Stereopsis 27 
Least Square Matching 
Affine model → p’ = h(p) = A p +Δp 
 Matching is established if (SSD) 
 
 
 
 where 
 
 
 
 
    x ,,
00
 vuIvuI
 
2222111211
 dbdadadbdada
T
x
 
vvvuuu
gvguggvgug

 
0000

6/4/2013 Stereopsis 28 
Least Square Matching 
Affine model → p’ = h(p) = A p +Δp 
 Stacking the equation generated by each point in W(p) yields 
 
 
 
 
 
 It is a over determined system whose solution is given by 
 
x = W† y 
 
   
   
x



























vnvnvununu
vvvuuu
nnnn
gvguggvgug
gvguggvgug
vuIvuI
vuIvuI
 
 
,,
,,
0000
01010101
00
010111

y W 
6/4/2013 Stereopsis 29 
Least Square Matching 
Affine model → p’ = h(p) = A p +Δp 
1. Start with, k=0 and 
 
 
2. k=k+1; for each (u,v) in W(p) apply the transformation to 
compute I’ (u’,v’), gu’ and gv’ . 
3. Build the equation (previous slide) and compute x 
4. Update the parameters 
 
 
 
5. Repeat steps 2 to 4 till ||x|| goes below a certain limit. 













0
2
0
100
 ,
10
01
b
b
A p














k
k
kk
kk
kk
kk
db
db
dada
dada
AA
2
11
2221
12111
 , pp
6/4/2013 Stereopsis 30 
 Building a dense correspondence 
new seed 
N 
new seed 
W 
good 
match 
new seed 
E 
new seed 
S 
Region Growing right image 
refine location 
select a seed 
good 
match? 
 
save match 
create new 
seeds (NSEW) 
 seeds? 
save 
matches 
left 
image 
seed 
repository 
match 
repository 
START 
END 
yes 
yes 
no 
no 
6/4/2013 Stereopsis 31 
Region Growing 
 Building a dense correspondence map with Region 
Growing 
1. Select a seed of corresponding points manually, and add it in 
To_Check_List . 
2. Take the first pair, delete it in To_Check_List and add it to 
Checked_List . 
3. Refine location in right image using a correlation based method 
4. If constrast > min_contrast AND correlation > min_correlation, 
 Put pair in the Match_List. 
 Add to the To_Check_List its neighbors d pixels to the North, to the 
South, to the East and to the West, as long as they belong neither to 
Checked_List nor to To_Check_List . 
5. Do steps 2 to 4 till To_Check_List is empty. 
6/4/2013 Stereopsis 32 
Region Growing 
Example 
left image right image 
watch 
6/4/2013 Stereopsis 33 
Content 
 Introduction 
 Reconstruction 
 The Correspondence Problem 
 Rectification 
6/4/2013 Stereopsis 34 
Rectification 
Transforms a pair of stereo images in such a way that 
 both images stay on a single plane parallel to the baseline, and 
 conjugate epipolar lines are collinear with the x axis. 
O O’ 
P 
linha de base 
 
 The search for corresponding points becomes 1D. 
6/4/2013 Stereopsis 35 
Rectification 
Example: 
 original 
 images 
 
 
 rectified 
 images 
6/4/2013 Stereopsis 36 
Rectification 
Algorithm1 
Recalling the camera model 
 
 
for P non homogeneous 
 
 
1 A. Fusiello, E. Trucco, and A. Verri. A compact algorithm for rectification of 
stereo pairs. Machine Vision and Applications, 12(1):16-22, 2000 
   bPz where RK  tp bPPz  KKR tp






tK
KR
b
6/4/2013 Stereopsis 37 
Rectification 
Algorithm (cont.) 
 Recalling the camera model 
 The non homogeneous coordinates O of the optical center in 
the world frame is given by 
 
 
 
 which implies 
 
 
  0 0 0 11
 
bOOO
T 
 RR tt
     OO RRKRK -  t
Algorithm (cont.) 
 Recalling the camera model 
 
 
 
 
 
 
 Thus, if then ri are the base vectors of the 
camera frame expressed in the world frame. 
 
 
6/4/2013 Stereopsis 38 
Rectification 











333231
232221
131211
rrr
rrr
rrr
R
 
TTTT
1
 
32
 rrrR
base vectors of the camera frame 
expressed in the world frame 
base vectors of the world frame 
expressed in the camera frame 
Algorihm (cont.) 
Recalling the camera model 
 Let W be the vector (non homogeneous) 
 defined by the optical center O and a point P in the world 
coordinate frame which project on p (homogeneous). 
 
 
Thus, points along the ray back-projected on p have world non 
homogeneous coordenates 
6/4/2013 Stereopsis 39 
Rectification 
 
1
 pOw

 
P 
p 
O 
W 
pzWOpzPPp
11
 

  Oz
6/4/2013 Stereopsis 40 
Rectification 
Algorithm (cont.) 
Problem formulation: 
 Given Mo, M´o, the known perspective projection matrices. 
 compute the geometric transformations T and T ´ that applied 
to the left and right images, i.é., 
 
 
pn= T po and p´n= T ´ p´o 
 
 will produce the rectified images. 
new image coordinates 
original image coordinates 
6/4/2013 Stereopsis 41 
Rectification 
Algorithm (cont.) 
 The perspective projection matrices relative to the 
rectified images will be 
n= T o and ´n= T´ ´o 
 The sought new cameras have the same 
 intrinsic parameters (arbitrary), and 
 rotation matrices. 
 Thus 
 
 and 
   OO
nnnnnnnn
 RRKRRK

- -
6/4/2013 Stereopsis 42 
Rectification 
Algorithm (cont.) 
Rectification itself 
The rotation matrix is built in the following way: 
 
 
 
 
T
T
n
T
n
T
n1n
 
32
 rrrR
OO
OO
n



1
r
13
13
2
no
no
n
rr
rr
r



213 nnn
rrr 
x axis of the camera frame in the 
world frame parallel to the base line 
y axis of the camera frame in the world 
frame perpendicular to x and to old z 
axes form an orthonormal basis 
6/4/2013 Stereopsis 43 
Rectification 
Algorithm (cont.) 
 The equation derived in a previous slide holds for the 
original as well as for the new camera, i.é., 
 
 and 
 yielding 
 
 Thus 
 and similarly 
 
o
1
onn
pp

 
 
n
1
nn
O pw

  
o
1
oo
O pw
 
 
1
on

 T 
' 1
o
'
n

 T
6/4/2013 Stereopsis 44 
Rectification 
Algorithm steps 1 to 3: 
1. Factorize the original projection matrices 
 and 
 
2. Compute the optical centers in the world frame 
 and 
 
3. Compute the new rotation matrix 
 
 
 
0000
t,, M   
0000
t  ,, M
0
1
00
t

 O
0
1
00
t 

O
OO
OO
n



1
r
13
13
2
no
no
n
rr
rr
r


 213 nnn rrr 
 
T
T
n
T
n
T
nn 321
rrr
6/4/2013 Stereopsis 45 
Rectification 
Algorithm steps 4 to 6: : 
4. Compute the new Projection Matrices with n arbitrary 
 
 
5. Compute the rectifying transformations 
 
 
6. Warp the input images 
   OO
nnnnnnnn
 RRKRRK

- -
1
0
1
0nn
1
on

 KRRKT 
' 1
0
1
0nn
1
o
'
n

 KRRKT
and 
and 
pn= T p0 and p´n= T ´p´0 
6/4/2013 Stereopsis 46 
Rectification 
 Example: 
original left image original right image 
rectified left image rectified right image 
Images from INRIA Syntim database: http://perso.lcpc.fr/tarel.jean-philippe/syntim/paires/syntim_stereo.tgz 
6/4/2013 Stereopsis 47 
Rectification 
Remarks: 
 The search for corresponding points becomes 1D. 
 It is possible to find a match for almost every pixel → 
dense match map. 
 Compensates rotation over the image plane, which 
improves cross correlation. 
 Reconstruction can be done from rectified images. 
 
6/4/2013 Stereopsis 48 
Next Topic 
More on 
Calibration and 
Reconstruction