1st U30 Workshop, 2006 Sep, Tokyo 宮崎大輔:コンピュータビジョンにおける最適化手法 All images are compressed. Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 1 1st U30 Workshop, 2006 Sep, Tokyo 宮崎大輔:コンピュータビジョンにおける最適化手法 コンピュータビジョンにおける最適化手法 池内研ポスドク2年目 宮崎大輔 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 2 本日の内容 • 松山隆司,久野義徳,井宮淳 「コンピュータビジョン 技術評論と将来展望」 第11章 コンピュータビジョンにおける最適化手法 -モデルの妥当性と解の安定性- 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 3 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 予備知識:誤差関数 y データ ( x1 , y1 ) (2,10) 15 ( x2 , y2 ) (4,9) 10 を一つの数値 y=aで表したい ( x10 , y10 ) (20,11) 5 0 x いまいち y4 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo y 14 いまいち 4 y 10 ピッタリ合う! Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 予備知識:誤差関数 データ ( x1 , y1 ) (2,10) y と y ya 10 の差 x 2 y a i i 1 y=4だと差が大きい 10 yi 4 2 y=10だと差が小さい 10 2 y 10 6 i 366 i 1 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo x i 1 5 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 予備知識:誤差関数 10 差 2 y a i が最小となるときのaが i 1 ( x10 , y10 ) (20,11) データ ( x1 , y1 ) (2,10) を y a で最も良く表すことができる この差を誤差関数・コスト関数・目的関数・ペナルティ関数という 関数の最小化方法は様々な方法があるが,ここでは述べない 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 6 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 予備知識:誤差関数 10 2 y a i ちなみに,この例での解答は i 1 10 2 y a i は下に凸の2次関数なので 6 i 1 10 a 最小値の点では微分の値が0 10 10 i 1 i 1 2 をaで微分すると 2 yi a y a i 10 yi a 0 i 1 これを 0 とすると 10 yi つまり, yi a1 0 よって a i 1 10 10 i 1 i 1 10 1 i 1 y1 y2 y10 10 9 11 つまりaはyiの平均: a 10 10 10 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 7 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 予備知識:微分と滑らかさ y 4 y 2 y 1 y 4 x y 2 x y x y 2x yx 1 2 y x 2 2 2 二階微分を小さくする→曲線が滑らかになる 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 8 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 関数当てはめ問題 • データ←多項式やスプライン関数のパラメータ推定 • 関数を人間が与える • 関数の自由度を上げる→うまく当てはまる • 弛緩法・正則化法・最適化法 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 9 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 正則化手法 • 2次元画像から3次元復元 • 解は無数にある • 正則化手法:数学的に「安定」な解 これを解く→ill-posedな問題:解が一意に定まらない 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 10 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ サンプリング点に滑らかな関数を当てはめる N 2 f ( xi ) yi 2 i 1 点の数:N 当てはめる関数:f 各点のデータ:(xi,yi) データが関数にどれだけ近いかを表す xN f 2 x 2 2階微分が小さい→滑らか dx x1 曲率が小さい(=曲率半径が大きい) 曲率大 曲率小 2 2 これを最小化すれば E 滑らかな関数でデータを表せる 2 2 これが正則化の基本的な考え方 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 11 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 正則化手法 別の例:線形関係Az=uで,uからzを求める Az u Pz を最小化する方法 正則化項 ペナルティ項 r 2 f 2 x 2 d z Pz qr ( x) r dx r 0 dx p Azとuがどれだけ近いかを表す 先程の例だと E N f (x ) y 2 i i 1 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 12 i xN x1 2 dx Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 滑らかな関数 • 解空間が巨大なill-posedな問題 • 解が安定になる物を選ぶ • 解が滑らかな関数となる物を選ぶ 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 13 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 正則化パラメータの決定法 Az u Pz このλをどうやって決めるか? • 誤差が分かっている場合は誤差に応じて決める • 学習により誤差を計算する • など 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 14 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 計算方法 • 確率的な手法 – シミュレーテッドアニーリングなど • 決定的な手法 – 最急降下法など 確率的な手法は計算時間がかかる しかし 確率的な手法は扱える問題の範囲が広い 決定的な手法で解ける問題であれば, 能力でも計算時間でも決定的な手法が有利 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 15 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ コンピュータビジョンの問題と正則化 • • • • • • • ノイズ除去 形状復元 エッジ検出 領域分割 オプティカルフロー ステレオ視 動的輪郭モデル 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 16 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ ノイズ除去 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 17 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ ノイズ除去:スプライン関数 安定化汎関数(正則化項)は p m 0 R d wm ( x) j1 jd m 観測データ m! v( x) j j1! jd ! x1 1 xdjd m 重み 2 dx 微分による滑らかさ • 観測データに対するスプライン関数の当てはめ • 重みの計算 この2つを交互に繰り返して計算する 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 18 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ ノイズ除去:不連続点 ほとんど滑らかだが,いくつか不連続点がある場合 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 19 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ ノイズ除去:GNC法 データ u i にはノイズが載っているので,それをキレイにして yi にする 最小化: F yi ui 2 g yi yi 1 i ペナルティ項 正則化項 データuが当てはめる値yに どれだけ近いかを表す シャープになって欲しい部分は: g 定数 滑らかになって欲しい部分は: g yi yi 1 2 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 20 2 (一次微分) Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ ノイズ除去:GNC法 F yi ui g yi yi 1 一次微分 yi yi 1 2 i 2 g g yi yi 1 を使う 1 がしきい値qより小さいとき 2 (微分が小さい→変化が小さい→滑らかな部分) 一次微分 yi yi 1 がしきい値rより大きいとき g g 2 定数 を使う (微分が大きい→変化が大きい→不連続部分) 一次微分 yi yi 1 がしきい値rとqの間のとき g g1と g2をうまくつなげたよう な関数 を使う 反復回数を増やすごとにrとqを近づけて,最終的にr=qとすれば, 連続部分と不連続部分がはっきりと検出できる 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 21 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ ノイズ除去:多価関数 y y f1 ( x) y f 2 ( x) x 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 22 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ ノイズ除去:多価関数 データ点yは関数f1かf2のどちらかに属する yがf1に一致すればy-f1が0になり,(y-f1)(y-f2)も0になる yがf2に一致すればy-f2が0になり,(y-f1)(y-f2)も0になる y f1 ( x) y f 2 ( x) y 2 f1 ( x) f 2 ( x)y f1 ( x) f 2 ( x) 0 F ( x) f1 ( x) f 2 ( x) G( x) f1 ( x) f 2 ( x) N E y G( xi ) yi F ( xi ) F F ( x) G G( x) i 1 2 2 i ペナルティ項 2 2 正則化項 これを最小化→観測データがどっちの 曲線・曲面に属するかを指定する必要がない 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 23 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ コンピュータビジョンの問題 • 2次元の情報から3次元の情報を復元する • ill-posedな問題 (ペナルティ項)+λ(正則化項) 滑らかさを表す ステレオやオプティカルフローなどのコスト関数 これまでのスライドでは正則化項の説明ばかりしてきたが これ以降のスライドでも正則化項の説明をメインに行う 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 24 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 形状復元 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 25 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 形状復元:Sobolev半ノルム • 安定化汎関数(正則化項)としてソボレフ半ノルムを使用 12 i j f R 2 x y i j m 2 2次元画像の格子(x,y)に復元したい3次元情報fがある fのx軸方向とy軸方向の微分→滑らかさ 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 26 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 形状復元:Controlled continuity stabilizer 安定化汎関数(正則化項)として以下を使う P (v ) 1 2 2 2 2 2 ( x , y ) ( x , y ) v 2 v v 1 ( x , y ) v v xx xy yy x y dxdy 2 ρ→0:正則化項が使われず,不連続になる ρ→大:正則化項が効いてきて,滑らかになる τ→0:1次微分を最小化→連続な直線に近くなる τ→1:2次微分を最小化→滑らかな曲線に近くなる τとρの値を各点ごとに適切に変えることにより 不連続部分も滑らか部分もうまく表現できる vとτとρは交互に推定する反復計算 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 27 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ エッジ検出 • エッジ検出にも利用される(詳細は省略) 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 28 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 領域分割 • 領域分割(詳細は省略) (概念図) 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 29 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ オプティカルフロー 物体が動くと,ある点の明るさが変化する この明るさの変化を利用して物体の動きを計算する 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 30 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ オプティカルフロー (注:オプティカルフローは物体の動きを表さない状況もある) 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 31 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ オプティカルフロー オプティカルフロー方程式 Eb I xu I y v It 0 画素の濃淡の変化に対する拘束 物体表面の輝度 物体の速度 I (u , v ) 実感が沸かないと思うので次のスライドで具体例で説明する 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 32 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 具体例 I xu I t 0 x軸だけの例で説明する I 輝度の傾き I x 2 輝度の傾き I It 2 x この点に着目 時刻t-1 物体の速度 u 1 t 時刻t 時刻t+1 t-1 t t+1 I xu I t 2 1 2 0 オプティカルフロー方程式が成り立つ 大きな変化がなく,小さな変化がある場合 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 33 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ オプティカルフローを解こう 輝度 Eb I xu I y v It 0 I は分かっており,そこから 物体の速度 (u , v ) を求めたい 未知数は2つで,方程式は1つなので,ill-posedな問題 正則化手法で解く 正則化項 Ec ux2 u y2 vx2 vy2 物体速度の微分を最小化 →隣り合った点の速度は大体同じ 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 34 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ ステレオ視 • 「形状復元」の項で説明した正則化項が利用できる 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 35 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ Snakes (Active Contour) 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 36 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ Snakes (動的輪郭検出法) 1. 初期輪郭を設定 2. エネルギー関数を最小化するにつれて, 輪郭は滑らかな曲線を描きつつ,エッジに近づいていく 3. 最終的に,エッジの場所で収束する 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 37 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ エネルギー関数 Esnakes (v( s )) Eint (v( s )) wimageEimage (v( s ))ds 輪郭の滑らかさ 1 2 2 Eint (v( s )) vs ( s ) vss ( s) 2 一次微分 二次微分 円に近づける 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 38 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ エネルギー関数 Esnakes (v( s )) Eint (v( s )) wimageEimage (v( s ))ds エッジの強さ Eimage (v( s )) I (v( s )) 2 画像の一次微分→エッジ エッジに近づける 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 39 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ Snakesの問題点 • • • • • 初期輪郭の位置によって解が変化する 事前知識を導入することがむずかしい 計算時間がかかる パラメータα,βによって解が変化する トポロジの変化に対応できない 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 40 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 様々な改良(詳細は省略) • 解空間の解析 – 初期値にあまり依存せずに解を求めるためには,最小化を 行う関数がどのような性質を持っていればいいかを解析 • 事前知識の導入 – – – – 輪郭をある曲率に近づくようにする 物理モデルを導入 形状を文法規則で記述 トポロジの変化に対応 • 高速計算法 – 動的計画法 – Greedy Algorithm 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 41 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 幾何モデルに基づくSnakes Snakesをこの方向に動かす: C (t ) gN g N N t N 法線 C (t ) t 曲線 C (t ) 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo C (t 1) C (t ) 42 C (t ) t Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 幾何モデルに基づくSnakes C (t ) gN g N N t この部分の意味→曲線の滑らかさ まずは N の意味 N N N 曲率が小さい (曲がっている率が小さい 宮崎大輔:コンピュータビジョンにおける最適化手法 →あまり曲がっていない) 1st U30 Workshop, 2006 Sep, Tokyo N 曲率が大きい (曲がっている率が大きい Ikeuchi Lab, The University of Tokyo 43 →かなり曲がっている) http://www.cvl.iis.u-tokyo.ac.jp/ 幾何モデルに基づくSnakes C (t ) gN g N N t この部分の意味→曲線の滑らかさ まずは N の意味 N 法線 N N N 凸:曲率が正 0 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 凹:曲率が負 0 44 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 幾何モデルに基づくSnakes C (t ) gN g N N t この部分の意味→曲線の滑らかさ g の意味 次に エッジ gは0~1の関数 0: エッジに近い 1: エッジから遠い g=1 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 45 g=0 g=1 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 幾何モデルに基づくSnakes C (t ) gN g N N t この部分の意味→曲線の滑らかさ 最後に gN の意味 曲線 N 曲線 エッジ エッジ gN gN 曲線がエッジに近いと gは0に近い 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo N 曲線がエッジから遠い gは1に近い 46 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 幾何モデルに基づくSnakes C (t ) gN g N N t この部分の意味→エッジに向かう動き g まずは の意味 エッジ g=1 エッジ (説明の都合上 gを1次元で描く) g=1 g=0 g=0 g=1 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 47 横方向の位置 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 幾何モデルに基づくSnakes C (t ) gN g N N t この部分の意味→エッジに向かう動き g まずは の意味 gの一次微分→gの傾き(接ベクトル) g 0 g 0 g 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 48 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 幾何モデルに基づくSnakes C (t ) gN g N N t この部分の意味→エッジに向かう動き まずは g N の意味 一次元の場合は g N はただのかけ算 二次元の場合は これが内積に 変わるだけ 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 法線が右向きだった場合 N 1 N N g N 0 g N 0 g 0 g 0 g 49 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 幾何モデルに基づくSnakes C (t ) gN g N N t この部分の意味→エッジに向かう動き 最後に g NN の意味 法線が右向きだった場合 N 1 g N 0 g N 0 g NN 0 g 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo g NN 0 g 50 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ まとめ • 解空間が大きすぎて,解が見つからない問題 • 正規化項を付ける • 解空間をせばめて,それらしい解を見つける 宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 51 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 1st U30 Workshop, 2006 Sep, Tokyo 宮崎大輔:コンピュータビジョンにおける最適化手法 (c) Daisuke Miyazaki 2006 All rights reserved. http://www.cvl.iis.u-tokyo.ac.jp/ 宮崎大輔, "コンピュータビジョンにおける最適化 手法," U30ワークショップ, 東京, 2006年9月 Ikeuchi Lab, The University of Tokyo http://www.cvl.iis.u-tokyo.ac.jp/ 52
© Copyright 2024 ExpyDoc