Microsoft PowerPoint - CV08.pptx

視覚の幾何学２

参考書

佐藤 淳：

「コンピュータビジョン －視覚の幾何学－」

コロナ社

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

●一台のカメラから得られた一枚の画像のみからでは、 ３Ｄ物体の奥行き・形状を一意に決定できない ●２つ以上の異なる視点で得られた画像からはこのよう な不定性を取り除き、形状を決定できる ●静止シーンの場合、1台のカメラから異なる視点で得られた2枚の画像でもＯＫ ●動く物体の場合、1台のカメラから固定視点で得られた画像系列でOK _baseline optical center (left) optical center (right) Focal lengt h World point Depth of p image point (left) image point (right)

Slide credit: Kristen Grauman

立体視の原理

 Assume parallel optical axes, known camera parameters

(i.e., calibrated cameras). We can triangulate via:

三角計測法

Similar triangles (pl, P, pr)

and (Ol, P, Or):

Geometry for a simple stereo system

Z

T

f

Z

x

x

T

_{l r}









r l

x

x

T

f

Z





視差(disparity)

Slide credit: Kristen Grauman

平行ステレオ視の３

D距離推定



点P(x,y,z)の座標値

R L R L R R L L R L L x x T f z x x T y x x T y y x x T x x             T

左カメラの光学中心がワールド座標の原点とする

（左カメラや、両カメラの真ん中のOK）

Depth from disparity

image I(x,y) Disparity map D(x,y) image I´(x´,y´)

(x´,y´)=(x+D(x,y), y)

Slide credit: Kristen Grauman

立体視の原理

 Algorithm

• Rotate both left and right camera so that they share the same X axis : Or-Ol= T

← カメラ中心の平行移動量

• Define a rotation matrix

Rrectfor the left camera

• Rotation Matrix for the right camera is Rrect・RT • Rotation can be implemented by image transformation p_l p_r P Ol _Or Xl Xr Pl Pr Zl Yl Zr Yr R, t t X’l Xl’ = T, Yl’ = Xl’xZl, Z’l= Xl’xYl’ 光軸は平行ではない場合 変換前座標系:（X,Y,Z） 変換後座標系:(X’,Y’X’)→平行  Algorithm

• Rotate both left and right camera so that they share the same X axis : Or-Ol= T

• Define a rotation matrix

Rrectfor the left camera

• Rotation Matrix for the right camera is Rrect・RT • Rotation can be implemented by image transformation p_l p_r P Ol Or Xl Xr Pl Pr Zl Yl Zr Yr R, t t X’l Xl’ = T, Yl’ = Xl’xZl, Z’l= Xl’xYl’

立体視の原理

光軸は平行になるように変換 （R,tが既知→カメラ校正済み） カメラキャリブレーション済みなら • R,tが既知 • 光軸は平行になるように変換できる p_l p_r P Ol Or Xl Xr Pl Pr Zl Yl Zr Yr R, t t X’l Xl’ = T, Yl’ = Xl’xZl, Z’l= Xl’xYl’

立体視の原理と問題点

Stereo image rectification:

example

Source: Alyosha Efros

カメラキャリブレーション済みなら • R,tが既知 • 光軸は平行になるように変換できる • ２Ｄシーンから３Ｄ復元 p_l p_r P Ol Or Xl Xr Pl Pr Zl Yl Zr Yr R, t t X’l Xl’ = T, Yl’ = Xl’xZl, Z’l= Xl’xYl’

立体視の原理と問題点

一つの問題： 対応点をどう判定するか？

Correlation Approach

For each point ○(x_l, y_l) in the left image, define

a window centered at the point

(xl, yl)

LEFT IMAGE

左画像からある点○の周辺領域をテンプレット□とする

テンプレット

Correlation Approach

… search its corresponding point within a

search region in the right image

(xl, yl)

RIGHT IMAGE

テンプレット

テンプレットを用いて、右画像のある領域から対応点を探す

Correlation Approach

… the disparity (dx, dy) is the displacement

when the correlation is maximum

(xl, yl) dx (xr, yr) RIGHT IMAGE 相関評価で最大類似度を取れた点ペアの視差を求める

特徴に基づいた立体視

特徴検出 • 特徴コーナー、線、エッジ • 対応特徴を見つける （相関評価による） ⇒視差（disparity）より奥行計算 残りの部分は表面内挿 corner line structure

よく用いられる相関評価方法







    W x x d x d 2 ) ( ) ( ) ( I_l I_r  ラスタスキャン 多次元ベクトルと考える 画素毎に差をとって二乗 総和 SSD(Sum of Squared Differences) •最も基本的な誤差評価関数 •画像をベクトルとみなせば、 ベクトル間のユークリッド距離 •外れ値の影響を受けやすい •照明変化の影響を受けやすい Il Ir Image2 Image1

よく用いられる相関評価方法

SAD(Sum of Absolute Differences)

•画素毎の差分の絶対値の和 •SSDに比べて外れ値の影響を受けにくい •照明の影響を受けやすい



    W x x d x d) | ( ) ( )| ( I_r I_l  画像領域をベクトルで表現

region A

Normalized Cross Correlation

region B vector a vector b 領域内の画素値をベクトル化 a b ベクトル間の相関を求める ベクトルの各要素から平均値を引かない

よく用いられる相関評価方法



CC

(

C

ross

C

orrelation) 正規化相互相関

• 領域内の画素値をベクトル化 •ベクトルの各要素から平均値を引く • ベクトル間の内積（角度） • 照明変化に強い SSD,SAD CC ノルムが変化しても 内積CCは変わらない







, 1 ) ( , 1 ) ( | ) ( || ) ( | ) ( ) ( ) (











               W x W x W x W x W x d x x x d x x d x r r l l l l r r l l r r I I I I I I I I I I I I d  明るさの正規化 コントラスト の正規化

Local Features:

Detectors & Descriptors

Detected

Interest Points/Regions Descriptors

<0 12 31 0 0 23 …> <5 0 0 11 37 15 …> <14 21 10 0 3 22 …> 最近の動向：SIFT or SURF特徴量によって2枚画像間の 対応点を探し出す 各点の周辺領域から128次元の 特徴量が得られる

Correspondence

Images from: M. Brown and D. G. Lowe. Recognising Panoramas. In Proceedings of the )

the International Conference on Computer Vision (ICCV2003 Th No d No d v v v v d i I i I i I I   



 2 min 1 min ) ( ) , ( 128 1 2 2 1 2 1

特徴に基づいた立体視

corner 2 x 1 x 2 1 x x fB Z   視差(disparity) 平行ステレオカメラ： 2枚の画像から 3次元情報を復元

Examples

Stereo

ボールの３Ｄ軌跡の計測

平行ステレビデオカメラ エピポーラ平面 エピポーラ線 右画像 左画像

出席チェック

1

１．対応点同士の相関を判定する方法について、 一つの例を挙げて述べなさい（基本考え、式、利 点、欠点を含む） カメラキャリブレーション済みなら • R,tが既知 • 光軸は平行になるように変換できる • ２Ｄシーンから３Ｄ復元 p_l p_r P Ol Or Xl Xr Pl Pr Zl Yl Zr Yr R, t t X’l Xl’ = T, Yl’ = Xl’xZl, Z’l= Xl’xYl’

立体視の原理と問題点

もう一つの問題： 対応点の探索範囲をどう絞るか？

２眼視の幾何: Two-View Geometry

courtesy of F. Dellaert

x

₁

x’

₁

x

₂

x’

2

x

₃

_x’

3 画像間の点（xito x’i）の対応関係は 1)カメラ間の剛体変換（カメラ行列：内部＋外部パラメータ） 2)シーンの構造 により決定 エピポーラ幾何は１）だけに関係がある

エピポーラ幾何

(Epipolar geometry）

複数の視点における相対的なカメラの位置Tや姿勢R の情報をエピポーラ幾何（Epipolar geometry）と呼ば れる画像特有の幾何によって記述できる O O もう一方のカメラでは、 画像上のどこに投影されるのか？ ？

エピポーラ幾何（Epipolar Geometry）

Baseline: カメラ中心

C

と

C’

を繋がる直線

Epipolar plane



: baselineとシーンの中の点

X

より

決定された平面 from Hartley & Zisserman baseline エピポーラ平面

エピポーラライン（

Epipolar Lines）

Epipolar lines l, l’: epipolar plane



と画像面との交線 Epipoles e, e’: baselineと画像面との交点；すべての Epipolar linesはこの点に交わる C _C’ from Hartley & Zisserman エピポーラ平面 ベースライン Epipolar line エピポーラライン _{Epipolar line} Epipole エピポール Epipole http://www.ai.sri.com/~luong/research/Meta3DViewer/EpipolarGeo.html

Epipolar Pencil

 シーンの中の点X の位置を変化すると、

epipolar planes はbaselineの周りに“rotate”

• このような平面集合をepipolar pencilと呼ぶ

Epipolar lines はepipole から“radiate”

• これはpencil of epipolar linesと呼ぶ

from Hartley & Zisserman

epipolar pencil エピポーラペンシール

pencil of epipolar lines

Why is Epipolar Constraint useful?

エピボラ幾何より、片方の画像内の一点は必ずもう一方 の画像内のエピポーラ直線（１Ｄ）上存在 探索は2次元から1次元に絞られる O O エピポール エピポール エピポーラ線

エピポーラ拘束

一点

Epipolar constraint

This is useful because it reduces the correspondence problem to a 1D search along an epipolar line.

Image from Andrew Zisserman Slide credit: Kristen Grauman

Epipolar geometry example I:

parallel cameras

Epipolar geometry depends onlyon the relative pose (position and orientation) and internal parametersof the two cameras, i.e. the position of the camera centres and image planes. It does notdepend on the scene structure(3D points external to the camera).

Cross-correlation of neighbourhood regions

epipolar line

translate so that mean is zero

left image band

right image band

1

0 0.5

x

target region （Good Feature Point）

left image band right image band

cross correlation 1 0 x 0.5 target region

（Bad Feature Point）

Epipolar geometry example II:

converging cameras

Note, epipolar lines are in general notparallel

例：

Epipolar Lines for Converging Cameras

from Hartley & Zisserman

Left view Right view

epipolar linesの交線 = Epipole ! 他方のカメラ中心の位置を表す ロボット・カメラの移動軌跡の推定

特例

: Translation Parallel to Image Plane

カメラの運動が画像面と平行する場合、 ・epipolar linesは平行（エピポールは無限遠）

特例: Translation along Optical Axis

カメラの運動が画像平面と垂直：  Epipolesはfocus延長線上に一致  一般的に、無限遠点と異なる e e’

ステレオから

3眼視へ

エピポーラ幾何より、片方の画像内の一点はかなら ずもう一方の画像内のエピポーラライン（１Ｄ）上存在 C C’ x’ 対応付け： 左側の画像上の1点 右側の画像上の一本の直線

点

直線

曖昧性が残っている 一点

Transfer: epipolar transfer

Using more cameras to remove match ambiguity

点点

点直線 _点直線

3眼視

Multi-Camera Stereo

Multiview geometry

Structure from motion (SfM) Dense multiview stereo

• N. Snavely, S. M. Seitz, R. Szeliski, 2007 • M. Vergauwen, L. Van Gool, 2006 • M. Brown, D. Lowe, 2005 • F. Schaffalitzky, A. Zisserman, 2002

• Y. Furukawa, J. Ponce, 2009 • P. Labatut, J.-P. Pons, R. Keriven, 2009 • M. Goesele, N. Snavely, B. Curless,

Multi-Camera

49

自由視点画像系列

50

透視カメラのエピポーラ幾何

複数のカメラ間の関係や対象物との関係を考える ために、何か基準となる座標系を考えなければな らない（各カメラの座標系を元に考えるのではない） 全てのカメラや対象物に対して共通に決められた 座標のことをワールド座標(world coordinates)と呼 ぶ（ワールド座標を一つ決める） 

ワールド座標を基準に考え

なければならない

出席チェック

2

１．エピポーラ幾何の原理図を描き、その原理に ついて述べなさい

Coordinate Transformations

座標変換

 If we want to measure something (sizeof an object, depthof image points, distancebetween features……), we need to understand the geometry from image to

worldCoordinate system transformations

• Image (i) camera (c) world (w) object (o)

xc zc yc yi xi xw zw yw Oc Oi Oo _Ow

行列・ベクトルの外積

(数学の準備)

 

a b b b a b a                                                      0 0 0 ; 1 2 1 3 2 3 1 2 2 1 3 1 1 3 2 3 3 2 3 2 1 3 2 1 a a a a a a b a b a b a b a b a b a b b b a a a 　

0

0













b)

(a

b

b)

(a

a

b

a

と

は一つの平面をサポー

トしているので

幾何変換

Geometric transformation

　変換あり 　変換なし 同次座標系で表現： ] with ] 0 | with t | [R E' p E' p' [I E Ep p t Rp p'       　変換あり 　変換なし 同次座標系で表現： あるいは ] with ] 0 | with t | [R P' x P' x' [I P Px x t Rx x'      

基本行列

(Essential matrix)

２カメラ間の姿勢と位置： • R : 3*3 rotation matrix • t : 3*1 translation vector pとp’が対応点同士なら： ⇒ 即ち：同一平面内の三つのベクトルから二つのベクトルの外積と 残るもう一つのベクトルの内積は０となる エピポーラ方程式 自由度が５： 基本行列（Ｅ行列） 回転３＋並進３－スケール１ 前提：pとp’は画像座標から計算さ れた物理(カメラ)座標である （カメラの内部パラメータ既知）         T_T y x y x ) 1 , ' , ' ( ' ) 1 , , ( with 0 )] ( [ ' p p Rp t p

 

t R E Ep p'    with 0

基本行列

(Essential matrix)

エピポーラ方程式 自由度が５： 基本行列（Ｅ行列） 回転３＋並進３－スケール１ ★ Ｅはランク落ちが発生！ ★Eが求まれば、tとＲに分解することができる 前提：pとp’は画像座標から計算さ れた物理(カメラ)座標である （カメラの内部パラメータ既知）         T_T y x y x ) 1 , ' , ' ( ' ) 1 , , ( with 0 )] ( [ ' p p Rp t p

 

t R E Ep p'    with 0

 

a b b b a                  0 0 0 1 2 1 3 2 3 a a a a a a 自由度が５： 回転３＋並進３－スケール１

出席チェック3



Ｅ行列の自由度は？理由は？