スライド 1 - 和歌山大学

視覚の幾何学１
呉海元＠和歌山大学
参考書
佐藤淳：
「コンピュータビジョン－視覚の幾何学－」
コロナ社
Single view geometry
Camera model
Single view geom.
カメラモデル（Camera model）
画像内の一点と3次元空間中の光線の関係
?
投影・射影関係によって決定
投影（ Projections ）

投影：m次元からn次元への変換 (m>n)
• CV： 3D to 2D
平行投影・正射影
透視投影
理想的なカメラ
●3次元空間のある点から発せられた光はレ
ンズによって一点に集光される
●光がレンズに入射する角度に応じて集光さ
れる位置が変わる
●どのような角度で入射した平行な光もすべ
てある一つの平面上に集光される
☆この平面上に撮像素子を置いておけば，ピントの合った画像が得られる
ピンホール･カメラ(pinhole camera)
●視覚を情報処理として考える場合には必ずし
も実際のカメラの物理的な投影をそのまま考え
る必要はない
●カメラの幾何学的な性質のみを考えるのであ
れば、レンズの中心の一点のみに注目し、撮像
素子に至る光はすべてこの一点を通過してくる
ものと考えるほうが扱いやすい
●このようなカメラをピンホール･カメラと呼ぶ
ピンホール･カメラ
f
Pinhole
Object
Image plane
●撮像素子が置かれる面を画像面(image plane)
●すべての光が通過する点(pinhole)を光学中心
(optical center)
●光学中心と画像面との間の距離を焦点距離ｆ(focal
length)
ピンホール･カメラ
Pinhole
Object
Image plane
●ピント合わせの必要がない
●投影の幾何学的な性質がそのまま保存されている
●視覚の幾何を考えるうえで理想的な性質を持つ
ピンホール･カメラ
●仮想的に画像面(Virtual image plane)を光学中心
の前(対象物側)に置くと、まったく同じ像が上下逆転せ
ずに投影される
●画像面を光学中心の前に出すことによって投影がよ
り扱いやすくなる
●普通、画像面を対象物側に置いて考える
Pinhole
Image plane
Virtual
Object
image plane
Pinhole camera image
Amsterdam : what do you see in this picture?
straight
line
size
parallelism/angle
shape
shape
of planes
depth
Photo by Robert Kosara, [email protected]
http://www.kosara.net/gallery/pinholeamsterda
m/pic01.html
Pinhole camera image
Amsterdam
straight line
size
parallelism/angle
shape
shape
of planes
depth
Photo by Robert Kosara, [email protected]
http://www.kosara.net/gallery/pinholeamsterda
m/pic01.html
Pinhole camera image
Amsterdam
straight line
size
parallelism/angle
shape
shape
of planes
depth
Photo by Robert Kosara, [email protected]
http://www.kosara.net/gallery/pinholeamsterda
m/pic01.html
Pinhole camera image
Amsterdam
straight line
size
parallelism/angle
shape
shape
of planes
depth
Photo by Robert Kosara, [email protected]
http://www.kosara.net/gallery/pinholeamsterda
m/pic01.html
Pinhole camera image
Amsterdam
straight line
size
parallelism/angle
shape
shape
of planes
depth
Photo by Robert Kosara, [email protected]
http://www.kosara.net/gallery/pinholeamsterda
m/pic01.html
Pinhole camera image
Amsterdam
straight line
size
parallelism/angle
shape
shape

of planes
parallel to image
depth
Photo by Robert Kosara, [email protected]
http://www.kosara.net/gallery/pinholeamsterda
m/pic01.html
Pinhole camera image
Amsterdam: what do you see?
straight line
size
parallelism/angle
shape
shape

of planes
parallel to image
Depth
?
stereo
- We see spatial shapes rather than individual pixels
motion
size
structure
…
- Knowledge: top-down vision belongs to human
- Stereo &Motion most successful in 3D CV &
application
- You can see it but you don't know how…
透視投影 (Perspective Projection)
Pinhole
Virtual
image plane
Image plane
簡略されたモデル：
z
y’
y
O
x
x’
Object
透視投影 (Perspective Projection)


消失点




点⇒点
線⇒線
面⇒面
ポリゴン⇒ポリゴン
遠い物体が小さい
奥行き情報が得られない
透視投影モデル
y’
y
(x’, y’, z’)
(x, y, z)
(x,y,z)から(x’,y’,z’)へ投影:
（相似三角関係より）
z
z’
z
x’
O
x
x’
仮定：
原点をレンズの中心に
Z軸と光軸と同じ
x
z
y
y  z
z
z  z
x  z 
（f = Z’）
●透視投影はZに関し非線形である
★幾何関係だけ考える理論系の人はよくｆ＝１とする
x
同次座標系
Homogenous Coordinates
cartesianworld
coordinates
homogenous world
corrdinates


 

( X , Y , Z )  (kX , kY , kZ , k )
cartesian world
coordinates





C1 C2 C3
(C1 , C2 , C3 , C4 )  ( , , )
C4 C4 C4
homogenous world
corrdinates
カメラのパラメータ
Camera Parameters

画像座標系Image coordinates

画素の有効サイズEffective size of pixel in millimeter
(ximage, yimage)
 画像中心Image center
(ox, oy)
 カメラ座標系Camera coordinates
(xcamera, ycamera)
 ワールド座標系Real world coordinates (X, Y, Z)
 焦点距離Focal length
f
(kx, ky)
カメラのパラメータ
ximage  k x xcamera  ox
yimage  k y ycamera  o y
 ximage  k x
y
0
 image  
 1   0
U image  k x
V
0
 image  
 S   0
U image  k x
V
0
 image  
 S   0
0
ky
0
ox   f
o y   0
1   0
0
f
0
0
ky
0
0
ky
0
X 
0 0  
Y


0 0
Z 
1 0  
1
ox   xcamera 
o y   ycamera 
1   1 
ox  U camera 
o y   Vcamera 
1   S 
fX
fY
Z
カメラのパラメータ
U image  k x
V
0
 image  
 S   0
U image   fk x
V
 0
 image  
 S   0
0
ky
0
0
fk y
0
X 
0 0  
Y


0 0
Z 
1 0  
1
ox   f
o y   0
1   0
0
f
0
ox
oy
1
X 
0  
Y


0
Z 
0  
1
f x  fk x
f y  fk y
カメラの内部パラメータ
Intrinsic Camera Parameters
y
 fx
x
 fy



ox
oy
p (x,y,f)
O
Size:
(x,sy)
ox
(0,0)
xim
o
Pixel
(xim,yim)
y
yim
内部パラメータはワールド座標系内のカメラの位
置と姿勢と依存しない
X 
U image   f x
V
0
 image  
 S   0
0
fy
0
ox
oy
1
0  
Y


0
Z 
0  
1
カメラの内部パラメータＩＩ
(x, y)

レンズのひずみ
Lens Distortions
k1 , k2
(xd, yd)
カメラの内部パラメータＩＩ
(x, y)


レンズのひずみ
Lens Distortions
(xd, yd)
k1 , k2
Modeled as simple radial distortions
• r2 = xd2+yd2
x  xd (1  k1r 2  k2r 4 )
• (xd , yd) distorted points
y  yd (1  k1r 2  k2r 4 )
• k1 , k2: distortion coefficients
• A model with k2 =0 is still accurate for
a CCD sensor of 500x500 with ~5
pixels distortion on the outer boundary
カメラの外部パラメータ
Extrinsic Camera Parameters

外部パラメータはワールド座標系内のカメラの位置
と姿勢によって決定される
• 平行移動Translation (3x1ベクトル)
• 回転Rotation (3x3行列)
xim
(xim,yim)
yim
O
y
x
p
R
t
P
Zw
Pw
Xw
O
Yw
平行移動（Translation）

(tx, ty, tz) Translation vector
 X camera   X world  t x 
Y
  Y
  t 
 camera   world   y 
 Z camera   Z world  t z 
 X camera  1 0 0 t x   X world 
Y
 0 1 0 t   Y

y   world 
 camera   
 Z camera  0 0 1 t z   Z world 

 


1
0
0
0
1
1

 

 
Translation Matrix
 X camera   X world 
Y
 Y

camera
world

  t

 Z camera   Z world 

 

1
1

 

平行移動（Translation）

Inverse translation
1
0
t
0

0
0
1
0
0
0 tx 
0 t y 
1 tz 

0 1
1
0
t 1  
0

0
1
0
tt1  
0

0
0
1
0
0
0 t x  1 0 0  t x  1
0 t y  0 1 0  t y  0

1 t z  0 0 1  t z  0

 
0 1  0 0 0 1  0
0  tx 
0  t y 
1  tz 

0 1 
0
1
0
0
0
1
0
0
0
0
1
0
0
0
I
0

1
回転（Rotation）
Y

R
Z-軸周り
X  R cos
Y  R sin 

(X’,Y’,Z’)
R

X
Z
X
Y




X   R cos     R cos cos  R sin  sin 
X
Y




Y   R sin     R cos sin   R sin  cos
X   X cos   Y sin 
Y   X sin   Y cos 
(X,Y,Z)
 X  cos
 Y     sin 
  
 Z   0
 sin 
cos
0
0  X 
0  Y 
1  Z 
回転（Rotation）




X-軸周り
Y-軸周り
Z-軸周り
回転なし
0
1
R X  0 cos
0 sin 

 sin  
cos 
0
cos
R Y   0
 sin 
0  sin  
1
0 
0 cos 
cos
R Z   sin 
 0
 sin 
cos
0
1 0 0 
R  0 1 0
0 0 1
0
0
1
回転（Rotation）

Inverse rotation
Z
 
R .R
cos
 sin 

 0

Z T
I
 sin 
cos
0
0  cos
0  sin 
1  0
sin 
cos
0
0 1 0 0
0  0 1 0
1 0 0 1
回転行列は直交行列!! R 1  RT , i.e. RRT  RT R  I
1 i  j
Ri  R j  
0 otherwise
T
回転行列とEuler角

回転行列: 3x3
• 直交行列Orthogonal :
R 1  RT , i.e. RRT  RT R  I
T
 r11 r12 r13  R1 
 
R  rij
 r21 r22 r23   RT2 
33
 r31 r32 r33  RT3 
 
 
• 9 elements => 3+3 constraints (orthogonal) => 2+2 constraints
(unit vectors) => 3 DOF 自由度 (degrees of freedom)

, ,  はX, Y, Z軸周りの回転角



R  R Z RY R X

O
注意：

• 一回一つの角度しか回転できない
• 順番と関係がある
Zw
Xw

Yw

回転行列とEuler角
R  RZ RY RX
cos  cos

R   sin  sin  cos  cos sin 
 cos sin  cos  sin  sin 

 cos  sin 
sin 
 sin  sin  sin   cos cos
cos sin  sin   sin  cos
If angle  is small, then cos =1
and sin =
 1   
R   
1   
  
1 

 sin  cos  
cos cos 
O

Zw
Xw

Yw

カメラのパラメータ


ワールド座標系とカメラ座標系の下
tx, ty, tz と r1,1…r3,3 はカメラ外部パラメータ
Xcamera  RXworld  T
 X camera   r1,1 r1, 2
Y
 r
r
camera
2
,
1
2, 2


 Z camera   r3,1 r3, 2

 
0
 1  0
r1,3 t x   X world 



r2,3 t y   Yworld 
r3,3 t z   Z world 


0 1  1 
カメラのパラメータ

ワールド座標系と画像座標系の下で
U image   fk x
V
 0
 image  
 S   0
U image   fk x
V
 0
 image  
 S   0
0
fk y
0
0
fk y
0
ox
oy
1
 X camera 
0 

Y
0  camera 
 Z camera 
0 

1


ox
oy
1
 r1,1 r1, 2
0 
r2,1 r2, 2


0
 r3,1 r3, 2
0 
0
0
r1,3 t x   X world 
r2,3 t y   Yworld 
r3,3 t z   Z world 


0 1  1 
ピンホールカメラモデル
ximage  ox   f x
yimage  oy   f y
r1,1 X world  r1, 2Yworld  r1,3 Z world  t x
r3,1 X world  r3, 2Yworld  r3,3 Z world  t z
r2,1 X world  r2, 2Yworld  r2,3 Z world  t y
r3,1 X world  r3, 2Yworld  r3,3 Z world  t z
透視投影モデル
y’
y
(x’, y’, z’)
(x, y, z)
(x,y,z)から(x’,y’,z’)へ投影:
（相似三角関係より）
z
z’
z
x’
O
x
x’
仮定：
原点をレンズの中心に
Z軸と光軸と同じ
x
z
y
y  z
z
z  z
x  z 
（f = Z’）
●透視投影はZに関し非線形である
★幾何関係だけ考える理論系の人はよくｆ＝１とする
x
正射影 (orthographic projection)
●正射影画像面に垂直な軸に沿って投影するもの
●Z軸方向の情報が失われ, X軸とY軸方向の座標は
そのまま保存される
●正射影はZに関し線形であり数学
的にははるかに扱いやすい
●正射影は実際のカメラによる投影
とは掛け離れたものであり,この投影
モデルがＣＶの分野に応用できる場
合は稀である
正射影モデル
y
(x’, y’, z’)
(x, y, z)
z
O
x
Projection from (x,y,z) to (x’,y’,z’):
x  x
y  y
or
z   z  const
x  kx
y   ky
z   const
弱透視投影(weak perspective projection)
●透視投影は現実のカメラによる投影にきわめて近いが、非線形
であり数学的には扱いにくい
●正射影は線形であるが、実際のカメラによる投影とは程遠い
●弱透視投影はこれら二の投影の中間的なものであり、正射影と
透視投影を組み合わせた投影である
弱透視投影
1) 対象物を画像面pに平行な平面Pに正射影する
この投影は正射影 => 線形
2) その投影像をさらに画像面pへ透視投影する
この投影は平面Pから平行な平面pへの投影
=> 均一に拡大或は縮小を行っている => 線形
★弱透視投影は線形
弱透視投影の式
●対象物を画像面pに平行な平面Pに正射影すること
は、対象物上の各点のX座標とY座標を保存したままZ
座標のみ一定の値
即ち、平面PのZ座標であるZ°に変更することに等しい
●この投影は次のように表せる：
X’=X
Y’=Y
Z' =Z°
(5.3)
弱透視投影の式
●正射影されたものをさらに透視投影される
=> 弱透視投影は次のように表せる
x = X’/Z’ = X/Z°
y = Y’/Z’ = Y/Z°
(5.4)
Z°は定数である
●これらの式はXとYに関して線形である
=> 投影が線形化された
弱透視投影が成り立つ条件
●弱透視投影は透視投影の近似である
●この近似の有効範囲は限られている
●弱透視投影では対象物上の各点までの距離Zが
一定値Z°で近似できることを前提としている
●対象物のZ軸方向の厚みDがカメラから対象物ま
での距離Zと比較して十分小さければよい
●D:Zが1:10以上であればこの近似が有効であると
考えてよい
平行透視投影(paraperspective projection)
●透視投影を線形近似するもう一つの方法
●弱透視投影では透視投影の前に画像面pに平行な
平面Pへの正射影を行った
●これを一般化し透視投影の前にPへ平行投影を行う
=> 正射影のように各点をある直線Lに平行に投影する
が、この直線Lが必ずしもPに垂直ではない
弱透視投影
平行透視投影
平行透視投影
●平行投影の方向 = 対象物の平均的な方向
●平行投影は線形な投影であり、平行な平面間の透
視投影も線形な投影であるから、これらを組み合わせ
た平行透視投影も線形な投影となる
平行透視投影の式
●対象物の平均的な方向を(△X, △Y, 1)とし
この方向に平行投影する：
X’ = X + ( Z°- Z)△X
Y’ = Y + ( Z°- Z)△Y
Z’ = Z°
●さらに透視投影する
平行透視投影は以下のように表せる：
x = X’/Z’ = 1/Z°・X - △X/Z°・ Z + △X
y = Y’/Z’ = 1/Z°・Y - △Y/ Z°・Z + △Y
平行透視投影
●前式のX, Y, Zにかかる1/ Z°, △x/ Z°, △Y/ Z°,
△x, △Yなどはいずれも定数 => X, Y, Zに関して線形
●平行透視投影も透視投影の線形近似
●対象物の平均方向が光軸に一致する場合には平行
透視投影は弱透視投影となる
弱透視投影と平行透視投影
●弱透視投影も平行透視投影も画像面pに平行な平
面Pに平行投影した後、透視投影する
●弱透視投影は平面Pに垂直に平行投影する
●平行透視投影は対象物の平均的な方向に向けて
平行投影する
●平行透視投影の方がより透視投影に近い
E.g., Shape Reconstruction
Left
Right
★射影モデルが異なる→同じ画像から復元された３D情報が異なる
Affine cameras
焦点距離ｆを増加
物体とカメラの距離を増加
実際のカメラ
●実際に使用するテレビカメラは対象物からの光を受ける受光部
(撮像素子)と、受光により発生する微弱な電気信号を処理する信
号処理部からなっている
★イメージセンサーに受光部と信号処理部を含まれる
●受光部の前にはレンズが置かれ、光はこのレンズによって集光
され、絞りを通して撮像素子(イメージセンサー）に至る
●レンズ系と撮像素子によって、3D空間から2D画像への投影が
起こる
実際のカメラ
●実際のカメラではレンズ収差や歪みが生じるため、複
数のレンズを組み合わせて、レンズ収差や歪みなどを
取り除く
ズームレンズの
内部構造
・レンズの配置を変わると
焦点距離を変わる
出席チェック
１．弱透視投影の原理図を描き、その原理と成り
立つ条件について述べなさい
平行移動
拡大・縮小
回転（原点中心）
2次元アフィン変換
平行移動  x' 
 x   a
       
 y'   y   b 
拡大・縮小  x' 
a
   
 y'  0
回転  x'    cos
 y '   sin 
  
 x'   a b  x   e 
0  x 
   
    
 一般化！  y'  c d  y   f 
b y
 
 sin   x 
 
cos  y 
せん断
アフィン変換
アフィン変換をもっと簡単な形に~
同次座標
(homogeneous coordinates)
 x'   a b
  
 x'   a b  x   e 
 y'   c d
   
    
 y'   c d  y   f  １つ次元を  1   0 0
上げると・・・
積


和
e  x 
 
f  y 
1  1 
積のみ！
図形の変換を全て行列の乗算1回で処理可能
複雑な座標変換がすべて行列の形で処理できる
同次座標の基本２Ｄ変換

Basic 2D transformations as 3x3 matrices
 x '  1 0 t x   x 
 y '  0 1 t   y 
y  
  
 1  0 0 1   1 
Translate
 x' cos 
 y '   sin 
  
 1   0
 sin 
cos
0
Rotate
 x '  s x
 y '   0
  
 1   0
0
sy
0
0  x 
0  y 
1   1 
Scale
0  x 
0  y 
1  1 
 x '  1 shx 0  x 
 y '   sh
 y
1
0
   y
 
 1   0
0 1  1 
Shear
行列の合成

複雑な座標変換の行列は各処理の行列の掛け算
から合成
 x'   1 0 tx  cos  sin  0  sx 0 0   x 
 y '    0 1 ty   sin  cos 0  0 sy 0   y 
  
 w'  0 0 1   0



0
1
  0 0 1    w

p’ =
T(tx,ty)
R()
S(sx,sy)
p
同次座標（3次元）

3次元座標値を，一つ次元を上げて4次元空間の
中で処理
( x, y, z )


( x, y, z, f )
(x/f, y/f, z/f) が三次元座標値となる
f=1のときはそのまま(x, y, z)が座標値
2次元アフィン変換と同じく、
座標変換をまとめて表記できる！
3次元アフィン変換
 x'   a
  
 y'   c
 1  0
  
b
d
0
 x'   a11
  
 y '   a21
 z'    a
   31
1  0
  
e  x 
 
f  y 
1  1 
2次元
a12
a22
a32
0
a13
a23
a33
0
３次元
bx  x 
 
by  y 
bz  z 
 
1  1 
P(x, y, z) からP(x’, y’, z’) へのアフィン変換（同次座標による表現）
P  AP
'
（A：アフィン変換行列）
同次座標導入の利点

同次座標を使わない場合
• 一回目のアフィン変換 P '  M1 P  b1
• 二回目のアフィン変換 P''  M2 P'  b2
P ''  M 2 ( M 1 P  b 1 )  b 2
P ''  M 2 M 1 P  M 2 b 1  b 2

同次座標を導入した場合
P '  H1 P
P ''  H 2 H 1 P
H1,H2： 2D -> 3 x 3 のアフィン変換行列
H1,H2： 3D -> 4 x 4 のアフィン変換行列
同次座標系導入の利点
f=w=1
直線上の点はすべて同じ座標を持つものとする
(点と線が同一視される)
無限遠点は？
無限遠要素
無限遠点
無限遠直線
無限遠平面
Two-view geometry
3D reconstruction
Epipolar geometry
E-matrix comp.
F-matrix comp.
H-matrix comp.
Structure comp.
立体視Stereo Vision (Stereopsis)

Main problem – recover 3D depth from two
(or more) image views
●一台のカメラから得られた画像のみからでは、３Ｄ
物体の形状を一意に決定することができない
●２つ以上の異なる視点で得られた画像からはこの
ような不定性を取り除き、形状を決定することができる
●静止シーンの場合、一台のカメラから異なる視点で
得られた2枚の画像でもＯＫ
立体視の原理
三角計測法に基づいて、
視線の交点が注視点の空間位置
x1
fB
Z
x1  x2
x2
平行ステレオ
差(disparity)
立体視の原理

Algorithm
• Rotate both left and
right camera so that
they share the same X
axis : Or-Ol = T
• Define a rotation matrix
Rrect for the left camera
• Rotation Matrix for the
right camera is RrectRT
Xl
• Rotation can be
implemented by image
X’l
transformation
P
Pl
p
Yl
Pr
p
l
Zl
Or
R, t
Xl’ = T,
Yr
Zr
Ol t
光軸は平行ではない場合
r
Yl’ = Xl’xZl,
Xr
Z’l = Xl’xYl’
立体視の原理

Algorithm
• Rotate both left and
right camera so that
they share the same X
axis : Or-Ol = T
• Define a rotation matrix
Rrect for the left camera
• Rotation Matrix for the
right camera is RrectRT
Xl
• Rotation can be
implemented by image
X’l
transformation
光軸は平行になるように
変換（R,tが既知）
P
Pl
p
Yl
Pr
p
l
Zl
Yr
Zr
Ol t
Or
R, t
Xl’ = T,
r
Yl’ = Xl’xZl,
Xr
Z’l = Xl’xYl’
Correlation Approach
LEFT IMAGE

(xl, yl)
For each point (xl, yl) in the left image, define
a window centered at the point
Correlation Approach
RIGHT IMAGE

(xl, yl)
… search its corresponding point within a
search region in the right image
Correlation Approach
RIGHT IMAGE

(xr, yr)
dx
(xl, yl)
… the disparity (dx, dy) is the displacement
when the correlation is maximum
特徴に基づいた立体視

特徴検出
• 特徴コーナー、点、エッジ
• 対応を見つける
（相関評価による）
⇒奥行き計算

残りの部分は表面内挿
corner
line
structure
相関評価のアルゴリズム
距離マップは特徴間の相関評価によって構成
伝統的な方法


SSD   I t 1  I t 
2
AD  | I t 1  I t  |
CC   I t 1I t

 I .I 

NC 
 I .I
MC 
t 1
t
t
t
1
64 t 1 t
 I
t 1
 t 1 I t  t 
更に距離マップの連続性を考慮すると
1
1
E    I left ( x  i, y  j )  I right ( x  i  Dx ( x, y), y  j  Dx ( x, y))   D( x, y)
i  1 j  1
1
1
D( x, y)    D( x  i, y  j )  D( x, y)
i  1 j  1
Examples
Left Image
Right Image
Depth Map
２眼視の幾何: Two-View Geometry
x3
x2
x’3
x1
x’2
x’1
courtesy of F. Dellaert
画像間の点（xi to x’i ）の対応関係は
・カメラ間の剛体変換（カメラ行列）
・シーンの構造
により決定 ⇒ 対応点の探索を絞ることができるか
エピボラ幾何(Epipolar geometry）
複数の視点における相対的なカメラの位置や姿勢の情報を
エピポーラ幾何（Epipolar geometry）と呼ばれる画像特
有の幾何によって記述できる
O
O’
エピボラ幾何（Epipolar Geometry）

Baseline: カメラ中心C, C’を繋がる直線

Epipolar plane p: baselineとシーンの中の点 Xより
決定された平面
baseline
from Hartley
& Zisserman
Epipolar Lines


Epipolar lines l, l’: epipolar plane p と画像面
との交線
Epipoles e, e’: baselineと画像面との交点
C
C’
from Hartley
& Zisserman
Epipolar Pencil

X の位置を変化すると、epipolar planes はbaseline
の周りに“rotate”
• このような平面集合を epipolar pencilとよぶ

Epipolar lines はepipole から“radiate”
• これは pencil of epipolar lines
from Hartley
& Zisserman
エピボラ制約（Epipolar Constraint）

エピボラ幾何より、片方の画像内の一点はかならずも
う一方の画像内のエピボラ直線（１Ｄ）上存在
x’
C
C’
from Hartley
& Zisserman
例：Epipolar Lines for Converging Cameras
Left view
epipolar linesの交線 = Epipole !
他方のカメラ中心の位置を表す
Right view
from Hartley
& Zisserman
特例: Translation Parallel to Image Plane
カメラの運動が画像面と平行する場合、
・epipolar linesは平行
・対応点は対応 epipolar line上に存在 (全種類のカメラ運動)
特例: Translation along Optical Axis
カメラの運動が画像平面と垂直する場合
 Epipolesはfocus延長線上に一致
 一般的に、無限遠点と異なる
e’
e
透視カメラのエピポーラ幾何



複数のカメラの関係や対象物との関係を考える
ために、何か基準となる座標系を考えなければ
ならない（各のカメラのカメラ座標系を元に考える
のではない）
すべてのカメラや対象物に対して共通に決めら
れた座標のことをワールド座標(world
coordinates)と呼ぶ（ワールド座標を一つ決める）
ワールド座標を基準に考えなければならない
Transfer: epipolar transfer
Using more cameras to remove match ambiguity
3眼視
Coordinate Transformations
座標変換


If we want to measure something (size of an object,
depth of image points, distance between features……),
we need to understand the geometry from image to world
Coordinate system transformations
• Image (i) camera (c) world (w) object (o)
yc
yi
yw
zc
zw
xc
xi
xw
行列・ベクトルの外積
a2b3  a3b2   0
a  b   a3b1  a1b3    a3
 a1b2  a2b1   a2
a  (a  b)  0
b  (a  b)  0
 a3
0
a1
a2 
 a1 b 
0 
a b
幾何変換
Geometric transformation
P'  RP  t
p  KP with K  [ I | 0]
p'  K ' P with K '  [ R | t ]
基本行列 (Essential matrix)


⇒
２カメラ間の姿勢と位置：
• R : 3*3 rotation matrix
• t : 3*1 translation vector
pとp’が対応点同士なら：
 p  (u, v,1)T
p'[t  ( Rp)]  0 with 
T
 p'  (u ' , v' ,1)
前提： pとp’は画像座標から計算
された物理(カメラ)座標である
（カメラの内部パラメータ既知）
即ち：同一平面内の三つのベクトルから二つのベクトルの外積と
残るもう一つのベクトルの内積は０となる
エピボラ方程式
p' Ep  0
基本行列（Ｅ行列） with E  t R
★ Ｅが求まれば、tとＲに分解することができる
基礎行列（Fundamental matrix）

内部パラメータが未知、画像座標xしか分からない
• 画像座標xと物理（カメラ）座標pの関係：
x=Kp , x’=K’p’ ⇒ p=K-1x, p’=K’-1x’
(K,K’ are the camera calibration matrix)

基本行列から : p’TEp=0
⇒ x’TK’-TEK-1x=0
⇒ x’TFx=0
F= K’-TEK-1 基礎行列（Ｆ行列）
●基礎行列はカメラの内部パラメータと外部パラメー
タの双方を含んでいる
基礎行列Fの性質
x’TFx=0
 x=eの場合 (e is epipole) : x’TFe=0,∀x’
(∵全てのepipolar linesはepipoleの所に交叉)
⇒ Fe = 0
 x’=e’の場合(e’ is epipole) : e’TFx =0,∀x
⇒ e’TF = 0 ⇒ FTe’ = 0

●Ｆ行列が与えられれば、eとe’はそれぞれＦTFと
ＦＦTの最も小さい固有値に対応する固有ベクト
ルとして求められる
The Fundamental Matrix F

片方の画像内の点xがもう一方の画像内epipolar
line l’ 上に対応付けることは：
line
point
l’ = Fx

このpoint-on-lineの関係は l’TFx
れ、l’T Fx
= 0より決定さ
= (Fx)T l’ = 0の関係も成り立つ
 F is 3 x 3, rank 2 (逆行列が求められない）
Homography
空間中の対象点がすべてある平面内の上にある場合
Homography
空間中の対象点がすべてある平面内の上にある場合

x’=Hx 空間内平面と画像間の投影
ximage  ox   f x
yimage  oy   f y

r1,1 X world  r1, 2Yworld  r1,3 Z world  t x
r3,1 X world  r3, 2Yworld  r3,3 Z world  t z
r2,1 X world  r2, 2Yworld  r2,3 Z world  t y
r3,1 X world  r3, 2Yworld  r3,3 Z world  t z
ホモグラフィ行列Hの自由度： 8
特例として
Z world  0
Compute H

一対の対応点 ((x,y,1)⇔(x’,y’,1))が分かれば、二つ
の方程式が得られる
x'1 h11 x  h12 y  h13
x' 

x'3 h31 x  h32 y  h33
x'2 h21 x  h22 y  h23
y' 

x'3 h31 x  h32 y  h33
x' h31 x  h32 y  h33   h11 x  h12 y  h13
y' h31 x  h32 y  h33   h21 x  h22 y  h23

(linear in hij)
4組み以上の対応点(n>=4)が分かれば、Ｈが唯一
に決定できる
Applying Homographies to Removing
projective distortion
select four points in a plane with know coordinates
x' 
x'1 h11 x  h12 y  h13

x'3 h31 x  h32 y  h33
y' 
x'2 h21 x  h22 y  h23

x'3 h31 x  h32 y  h33
x' h31 x  h32 y  h33   h11 x  h12 y  h13
(linear in hij)
y' h31 x  h32 y  h33   h21 x  h22 y  h23
Homographies for
Bird’s-eye Views
from Hartley & Zisserman
Homography between images of planes



x=H1xπ , x’=H2xπ
x’=H2xπ=H2H1-1x=Hx
4組み以上の対応点(n>=4)が分かれば、Ｈが唯一に
決定できる
Homographies for Mosaicing
from Hartley & Zisserman
Stereo
Wider Baseline
Multi-Camera Stereo
Stereo
Multi-Camera Stereo
Object Detection and
Recognition
Model, detect, and recognize objects in
images
 Main issues

• Object representation, feature extraction,
matching, learning from data
Optical Flow and Motion
Compute local image motion
(optical flow field) and then
estimate object/scene/camera
motion (motion field)
 Problems with local flow
computation

Aperture problem
Aperture Problem Example
Examples of Commercial Vision
Systems
Toshiba Hand Motion Processor
Point Gray Research
Eyematic Interfaces
Viisage
JLI Vision
Aluminum foil container inspection
LC Technologies
Eye tracking
The Cup is Half Full…

Vision is a hard problem!
• It is an inverse, ill-posed problem
• Much of your very complex brain is devoted to
doing vision
• It involves cognition, navigation, manuiplation
and learning
• Not just simple “match a feature vector to a
database” tasks

However…
• Some commercial successes
Vision Based Interaction (VBI)
Hand tracking
Hand gestures
Arm gestures
Body tracking
Activity analysis
Head tracking
Gaze tracking
Lip reading
Face recognition
Facial expression
VBI applications can enable:

3D interaction

Accessibility, hands-free computing

Game input

Social interfaces

Teleconferencing

Improved speech recognition
(speechreading)

User-aware applications
What makes VBI hard?

User appearance
• size, sex, race, hair,
skin, make-up,
fatigue, clothing
color & fit, facial
hair, eyeglasses,
aging….

Environment
• lighting,
background,
movement, camera

Multiple people

Intention of actions

Speed and latency

Calibration, FOV,
camera control, image
quality
 Robustness
 Real
time
Real-Time Vision Processing
Needs

Algorithms typically require generalpurpose computing

Low resolution/quality: 300 MHz
• 15 fps * 20K pix/frm * 1000 ops/pix

Fair resolution/quality: 75 GHz
• 30 fps * 200K pix/frm * 10K ops/pix

High resolution/quality: 8 THz
• 100 fps * 2M pix/frm * 40K ops/pix
Some VBI Examples
Myron
Krueger
MIT Media
Lab
Videos










Color tracking
Hand tracking 1
Hand tracking 2
Hand tracking 3
Magicboard 1
Magicboard 2
DrawBoard
Segen 1
Segen 2
Segen 3









Face tracking 1
Face tracking 2
Dyna 1
Dyna 2
Davis 1
Davis 2
Davis 3
ALIVE / Silas
V-TOYS
The KidsRoom
A fully-automated, interactive narrative
playspace for children
 The room itself actively participated in the
story, guiding and reacting to the children's
choices and actions
 Used images, lighting, sound, and
computer vision action recognition
technology
 Hardware:

• Six computers, 2 high-res video projectors
KidsRoom
Interactive, engaging, social, and fun
 Worlds: bedroom, forest, river, monster
 Input: vision, sound
 Output: images, animations, sound,
narrative, music, lighting

Homography given plane
P  [I | 0] P'  [A | a]
π X0
T


π  v ,1
T
T
point on plane
x  PX  [I | 0]X

 
T
X  x , ρ  x T ,-vT x
T

T
project in second view


x'  A  avT x
x'  Hx
H  A  avT
Homography given plane and viceversa
H  A  avT
A  H  av T  u1σ1v1
T
T


σ
v
T
T
1
1
A  H  av  a u1u1  T 
 a u1 


Calibrated stereo rig
PE  K[I | 0]
P'E  K'[R | t]
π  (n T d ) T
v  n/ d


H  K' R  tn T /d K -1
homographies and epipolar
geometry
points on plane also have to satisfy epipolar geometry!
Hx T Fx  x T HT Fx  0, x
HTF has to be skew-symmetric
H T F  FT H  0
x H e'x'  0, x  x'
T
T
F  e'H
Fx  e'x' , x
homographies and epipolar
geometry
x
l  Fx
lπ
e'
e
l l π
x'  l π  Fx
(pick lp =e’, since e’Te’≠0)
H π  e'F
compare with F  e'H
Homography also maps epipole
e'  He
Homography also maps epipolar
lines
le  H l'e
T
Compatibility constraint
l'e  Fx  x'Hx
plane homography
given F and 3 points
correspondences
Method 1: reconstruct explicitly,
compute plane through 3 points
derive homography
Method 2: use epipoles as 4th correspondence
to compute homography
degenerate geometry for an
implicit computation of the
homography
Estimastion from 3 noisy points
(+F)
Consistency constraint:
points have to be in exact epipolar correspodence
Determine MLE points given F and x↔x’
Use implicit 3D approach (no derivation here)

1
H  A  e' M b
A  e' F

T
bi  x 'i Ax i  x'i e'  / x'i e'
T
2
plane homography
given F, a point and a line
H  l' F  μe'lT
T

x'e' x'Fx  l'
μ
 
x'e' l T x
2
application: matching lines
(Schmid and Zisserman, CVPR’97)
epipolar geometry
induces point homography on lines
Degenerate homographies
x '  l'Fx
plane induced parallax
l  x 'Hx
6-point algorithm
x1,x2,x3,x4 in plane, x5,x6 out of plane
Compute H from x1,x2,x3,x4
e'  x 5 'Hx 5  x 6 'Hx 6 
F  e' H
Projective depth

X  xT , ρ

T
x'  Hx  ρe'
r=0 on plane
sign of r determines on which side of plane
Binary space partition
Two planes
H  H -12H1
He  e
H has fixed point and fixed line
F  [e] Hi
Narrow Baseline
Wider Baseline
Multi-Camera Stereo
Stereo
Multi-Camera Stereo
コンピュータビジョン特論
の復習
●画像・映像の処理、認識、理解研究の歴史と現状
●デジタル濃淡画像と画質改善
●エッジの検出
●投票と多数決原理に基づく幾何学的対象の検出と識別
●色彩工学とカラービジョン
●視覚の幾何学
画像・映像の処理、認識、理解研究
の歴史と現状
●コンピュータビジョンの歴史
●「コンピュータビジョン」と「画像処理」の区別
デジタル濃淡画像と画質改善
●画質に影響を与える情報の計算
諧調性、コントラスト、雑音（S/N、ｄB）
●画質の改善
濃度変換、平滑化、鮮鋭化
それぞれどんな方法があるか、特徴、利点、欠点
●ヒストグラム
● ヒストグラムとは
● ヒストグラムの求め方
● ヒストグラムの応用
エッジの検出
●差分型エッジ検出オペレータ
●零交差法
●テンプレート型エッジ検出オペレータ
・それぞれのオペレータの代表名、
・あるオペレータを用いて、画像上のエッジの大きさ、
方向の計算
・なぜ(2n+1)*(2n+1)画素のフィルタを使うか
投票と多数決原理に基づく
幾何学的対象の検出と識別
●直線検出用Hough変換の基本原理
と簡単なアルゴリズム
色彩工学の基礎
●顕色系と混色系
●マンセル表色系
色相、彩度、明度
●RGB表色系とXYZ表色系
●均等色度図
MacAdamの色弁別楕円より説明
投影とカメラモデル
●ピンホール・カメラ
●透視投影
●正射影
●弱透視投影
●平行透視投影
それぞれのイメージ図と投影方程式
エピボラ幾何
・エピポーラ線
・エピポーラ平面
・ペンシル
試験
日時：2月４日 10:50～
場所：A20４
質問時間
カメラ座標系(camera coordinate system)
●カメラ座標系はカメラを中心として定義した座標系
●光軸(optical axis)：光学中心から画像面に垂直に引いた直線l｡
●画像中心(principal point)：光軸と画像面との交点xc
●ピンホール･カメラ：
・X軸とY軸を画像面上のx軸とy軸に平行
・Z軸を光軸l｡に対し平行
・光学中心を座標原点Cにとる
Coordinate Transformations
座標変換


If we want to measure something (size of an object,
depth of image points, distance between features……),
we need to understand the geometry from image to world
Coordinate system transformations
• Image (i) camera (c) world (w) object (o)
yc
yi
yw
zc
zw
xc
xi
xw
透視投影
（Perspective projection）
 x  f
  
s y    0
1 0
  

0
f
0
 
0 0  X 
 

0 0  Y 
Z


1 0
1 
 
3*4の透視投影行列より３Ｄ→２Ｄの変換を表現
Concatenating the three matrix
 x
f
 
x   y   K  0
1
 0
 


0
f
0
0 0
R

0 0  T
0

1 0
X
X
 
 
t  Y 
Y 
 K R | t  



1 Z
Z
 
 
1
1
 
 
三つの行列を繋がると、新しい3*4 投影行列を定義
⇒ x=PX
P=K[R| t]
ワールド座標系における3次元空間の点Xは2次元画
像上の点xに投影される
Perspective Projection (透視投影)
x
x  z  ,
z

y
y  z  , z   z
z
use homogeneous coordinates（同次座標系）
 x'  1
 y '  0
 
 z '  0
  
 w' 0
and
0  x 
0  y 
0 1 0  z 
 
0 1 / z ' 0  1 
0
1
 x'  x' / w'
 y '   y ' / w'
  

 z '   z ' / w' 
0
0
Goals of Computer Vision
CVの目標

Computer vision aims to
• Automate visual perception
視知覚の自動化
• Construct scene descriptions from images
画像からシーンの記述を構築
• Interpret the content of images
画像の中身を解釈
• Support tasks that require visual information
視覚情報を必要なタスクを提供
• ……
Goals of Computer Vision

Computer vision aims to
• Automate visual perception
• Construct scene descriptions from images
• Make useful decisions about real physical objects
and scenes based on sensed images
• Produce symbolic (perhaps task-dependent)
descriptions from images
• Produce from images of the external world a useful
description that is not cluttered with irrelevant
information
• Interpret the content of images
• Support tasks that require visual information
透視投影
●3次元空間中で(X,Y,Z)の座標を持つ点X= [X, Y,
Z]^Tが, 2次元画像上で(x, y)の位置の点x= [x,y]^Tに
投影されている
●この画像上の点を3次元空間中の点と考えるとその
位置は(x, y, ｆ)である
●ピンホール･カメラによる投影では、画像上の点のx
とfの比が3次元空間中の点のXとZの比に等しく、また
yとfの比がYとZの比に等しい
透視投影
(perspective projection)
●3次元空間中の点と
その投影像との間：
x = f * X/Z
y = f * Y/Z
の関係が成り立つ
●透視投影はZに
関し非線形である
Perspective Projection (透視投影)


x
y
x  z  , y   z  , z   z 
z
z
Can we compute this in a 3x3 matrix?
• No, it’s not linear (透視投影はZに関し非線形である)
Instead, use homogeneous coordinates（同次座標系）
 x'  1
 y '  0
 
 z '  0
  
 w' 0
and
0  x 
0  y 
0 1 0  z 
 
0 1 / z ' 0  1 
0
1
 x'  x' / w'
 y '   y ' / w'
  

 z '   z ' / w' 
0
0
Calculating Camera Calibration
Original planar pattern
Corrected for radial
lens distortion
Edges
Zhang method:
• Grab images of this pattern at at least two random orientations
• Closed-form solution then non-linear refinement
• Result: Camera extrinsic and intrinsic parameters
The fundamental matrix F
algebraic representation of epipolar geometry
x  l'
we will see that mapping is (singular) correlation
(i.e. projective mapping from points to lines)
represented by the fundamental matrix F
The fundamental matrix F
geometric derivation
x' H π x
l'  e'x'  e' H π x  Fx
mapping from 2-D to 1-D family (rank 2)
The fundamental matrix F
algebraic derivation
Xλ  P x  λC

l  P'C  P'P x
F  e' P'P 
(note: doesn’t work for C=C’  F=0)
P P  I

P x
Xλ 
The fundamental matrix F
correspondence condition
The fundamental matrix satisfies the condition
that for any pair of corresponding points x↔x’ in
the two images
T
T
x' Fx  0
x'

l'  0
The fundamental matrix F
F is the unique 3x3 rank 2 matrix that
satisfies x’TFx=0 for all x↔x’
(i)
(ii)
(iii)
(iv)
(v)
Transpose: if F is fundamental matrix for (P,P’), then
FT is fundamental matrix for (P’,P)
Epipolar lines: l’=Fx & l=FTx’
Epipoles: on all epipolar lines, thus e’TFx=0, x
e’TF=0, similarly Fe=0
F has 7 d.o.f. , i.e. 3x3-1(homogeneous)-1(rank2)
F is a correlation, projective mapping from a point x to
a line l’=Fx (not a proper correlation, i.e. not invertible)
The epipolar line geometry
l,l’ epipolar lines, k line not through e
 l’=F[k]xl and symmetrically l=FT[k’]xl’
k
l
k l
e
Fkl
e'
(pick k=e, since eTe≠0)
l'  Fe l
l  FT e' l'
Fundamental matrix for pure translation
Fundamental matrix for pure translation
Fundamental matrix for pure translation
F  e' H  e'
example:
e' 1,0,0
T
H

 K 1RK

0 0 0 
F  0 0 - 1
0 1 0  
x'T Fx  0  y  y'
x  PX  K[I | 0]X
-1

K
x'  P'X  K[I | t] x 
 Z 
( X,Y,Z)T  K-1x/Z
x'  x  Kt/ Z
motion starts at x and moves towards e, faster depending on Z
pure translation: F only 2 d.o.f., xT[e]xx=0  auto-epipolar
General motion
x'T e' Hx  0
x'T e' xˆ  0
x' K' RK -1x  K' t/Z
Geometric representation of F
FS  F  FT / 2
x x


FA  F  FT / 2
x Fx  0
x T FSx  0
T
Fs: Steiner conic, 5 d.o.f.
Fa=[xa]x: pole of line ee’ w.r.t. Fs, 2 d.o.f.
F  FS  FA 
x F x  0
T
A
Geometric representation of F
Pure planar motion
Steiner conic Fs is degenerate (two lines)
Projective transformation and invariance
Derivation based purely on projective concepts
ˆx  Hx, xˆ '  H' x'  Fˆ  H'-T FH-1
F invariant to transformations of projective 3-space


ˆ
x  PX  PH H-1X  Pˆ X
ˆ
x' P'X  P'H H-1X  Pˆ ' X
P,P'  F
F  P,P'


unique
not unique
canonical form
P  [I | 0]
P' [M | m]
F  m M
Projective ambiguity of cameras given F
previous slide: at least projective ambiguity
this slide: not more!
~~
Show that if F is same for (P,P’) and (P,P’),
there exists a projective transformation H so that
~
~
P=HP and P’=HP’
~
~ ~
P  [I | 0] P' [A | a] P  [I | 0] P'  [A | ~
a]
~
~
F  a  A  a  A
~
lemma: ~
a  ka A  k 1 A  avT


rank 2
aF  aa  A  0  ~
aF  ~
a  ka
~
~
~
~
a A  a  A  a kA - A  0  kA - A  avT

 k 1I
H   1 T
k v
0
k 
 k 1I
P'H  [A | a] 1 T
k v





0  [k 1 A - avT | ka ]  ~
P'
k 
(22-15=7, ok)
Canonical cameras given F
F matrix corresponds to P,P’ iff P’TFP is skew-symmetric
X P'
T
T
FPX  0,X

F matrix, S skew-symmetric matrix
P  [I | 0] P' [SF | e' ]
(fund.matrix=F)

FTST F 0 FTST F 0 
T

[SF | e' ] F[I | 0]   T



0
0
e'
F
0


 

Possible choice:
P  [I | 0] P' [[e'] F | e' ]
Canonical representation:
P  [I | 0] P' [[e'] F  e' vT | λe' ]
The essential matrix
~fundamental matrix for calibrated cameras (remove K)
E  t  R  R[RT t]
xˆ 'T Exˆ  0
xˆ  K
E  K' T FK
5 d.o.f. (3 for R; 2 for t up to scale)
E is essential matrix if and only if
two singularvalues are equal (and third=0)
E  Udiag(1,1,0)VT

x; xˆ '  K-1x'
-1
Four possible reconstructions from E
(only one solution where points is in front of both cameras)
試験
日時：2月４日 10:50～
場所：A20４

Download Report