Computer Vision: Motion

運動の推定
なぜ運動を推定しますか?
たくさんの使い道があるからです。
•
•
•
•
•
•
運動の検出
物体の行動の追跡
カメラの手ぶれの補正
複数の画像合わせ (mosaics)
3次元形状復元
ビデオの圧縮
Optical flowの推定
画素ごとに運動を推定する
画像1
画像2
Optical Flowの例
平行移動
回転
拡大・縮小
Optical flowの例
Optical flowの推定
画素ごとに運動を推定する
画像1
画像2
問題の定義: optical flow
画像 H から画像 I までの画素の運動を推定する方法は?
• 画素の対応付け問題を解決する
– Hにある画素を与え、Iにおいて、その画素の近くから同じ色の画素を探す
重要な仮定
• 色の定常性: Hにある点はIにも同じ色に見える
– グレイ画像の場合、それは明るさ定常性になる
• 微小運動: 点の移動量は小さい
これはoptical flow問題という
Optical flowの拘束 (grayscale images)
それらの拘束について詳しく見てみよう
• 明るさ定常性: Q: 方程式は?
I ( x  u, y  v)  H ( x, y)  0
• 微小運動: (u と v は1画素以下)
– I についテーラー（Taylor）展開する:
I
I
u  v ２次以上の高次項
x
y
I
I
 I ( x, y )  u  v
x
y
I ( x  u , y  v )  I ( x, y ) 
Optical flow方程式
二つの方程式を合併すると
0  I ( x  u , y  v )  H ( x, y )
I
I
 I ( x, y )  u  v  H ( x, y )
x
y
I
I
 I ( x, y )  H ( x, y )   u  v
x
y
I
I
 I ( x, y )  H ( x, y )   u  v
x
y
I
I
 I  u  v
x
y
Optical flow方程式
式の両側をΔtで割ると
I u I v I


0
x t y t t
Δtに関する極限をとると
 I u I v I  I x I x I
lim

  

 0
t 0 x t
y t t  x t y t t

 x y 
I     I t  0
 t t 
ここで、
 
 
 t t 
I
It 
t
Optical flowの方程式
 x y 
I     I t  0
 t t 
Q: 画素あたりに、未知数、方程式はいくつ？
方程式＝１未知数＝２
この方程式の本当の意味は？
• エッジの勾配方向の速度成分は計算できる
• エッジと並行する速度成分は決定できない
これは、Aperture problemという
Aperture problem （このように見えるが）
Aperture problem （本当は．．．）
Aperture problem （本当は．．．）
エッジ勾配
 x y 
I   t t   I t  0


内積
すなわち
移動ベクトル
I  垂直成分 I t  0
エッジ勾配
垂直成分
移動ベクトル
平行成分
Aperture problemを解決しよう
画素あたりの方程式の数を増やすには？
• 基本アイディア: 拘束条件を追加する
– 最も一般的なのは：
速度場は局所的に滑らかの仮定、つまり、画面上の
画素の移動速度は、場所によって急激に変化しない
こと
– ひとつの方法:
隣接する画素の速度も同じとする
Aperture problemを解決しよう
5x5の窓を用いると、画素あたりに25個の方程式が得られる
RGB version
How to get more equations for a pixel?
• Basic idea: impose additional constraints
– most common is to assume that the flow field is smooth locally
– one method: pretend the pixel’s neighbors have the same (u,v)
» If we use a 5x5 window, that gives us 25*3 equations per pixel!
Lukas-Kanade flow
問題: 未知数より、方程式の方の数が多い
解方: 最小２乗問題を解く
• 最小２乗誤差を持つ解を求める方法:
• K x K のwindow内の全画素に対する累積を計算する
• この方法は Lukas & Kanade (1981) によって最初に提案された
問題を解ける条件
• 下記のLucas-Kanade方程式に最適な(u, v)を求める
解ける場合
• ATA の逆行列は存在する
• |ATA| はある程度大きい
– ATA の二つの固有値 l1と l2 微小ではない
• ATA 良い状態である
– l1/ l2 は極端に大きくない（l1 は大きいほうの固有値)
ATAの固有ベクトル
(x,y) がエッジ上にあるとすると、ATAは?
• エッジ上の点に勾配は強くて、方向も揃っている
• エッジから離れる勾配は弱い
•
は固有値
と対応している固有ベクトルである
• ATAのもう一個の固有ベクトルは?
– Nは
と垂直のベクトルとする
– N は0の固有値と対応する固有ベクトルである。
– ATAの固有ベクトルはエッジの方向と強度に依存する
Edge
– large gradients, all the same
– large l1, small l2
Low texture region
– gradients have small magnitude
– small l1, small l2
High textured region
– gradients are different, large magnitudes
– large l1, large l2
考察
これは二つの画像間の問題ですが、しかし
• 一枚の画像を見るだけで、解の安定性がわかる!
• それはどの画素が追跡しやすく、どの画素が追跡しにくいかを教えてく
れる
– 特徴追跡を行うときに大変役立つ...
Lukas-Kanadeにおけるエラー
この方法における誤りの潜在原因は?
• ATA の逆行列が容易に求められ、
• 画像にノイズはそうたくさん存在しない
と仮定していること
仮定が崩れたとき
• 明るさ定常性は満たされていない
• 移動は小さくない
• 点はその隣と同じように移動していない
– window sizeは大きすぎる
– 理想のwindow sizeは?
精度の改善
微小運動の仮定を思い出して
この近似は粗すぎる
• 良くするために、省略した高次項を元のように書き加える:
それは、多項式の解を求める問題となる
• ニュートン法（Newton’s method）を用いて解ける
– Also known as Newton-Raphson method
• Lukas-Kanade 法はニュートン法を用いて一回の繰り返しを行う
– 繰り返し回数を増やすことにより更に良い結果が得られる
繰り返し改善
繰り返しLukas-Kanade アルゴリズム
各画素の速度をLucas-Kanade方程式を解くことにより求める
1. 求まった速度場を用いて、移動後の画像をimage warping技術で画像H
から再構成して、画像Iとの間の速度を計算する
2. 速度場の解が安定する（変化が少なくなる）まで繰り返す
Revisiting the small motion assumption
Is this motion small enough?
• Probably not—it’s much larger than one pixel (2nd order terms dominate)
• How might we solve this problem?
Reduce the resolution!
Coarse-to-fine optical flow estimation
u=1.25 pixels
u=2.5 pixels
u=5 pixels
image H
Gaussian pyramid of image H
u=10 pixels
image I
Gaussian pyramid of image I
Coarse-to-fine optical flow estimation
run iterative L-K
warp & upsample
run iterative L-K
.
.
.
image H
J
Gaussian pyramid of image H
image I
Gaussian pyramid of image I
Multi-resolution Lucas Kanade Algorithm
Optical Flow Results
Optical Flow Results

Download Report