All images are compressed.

Presentation on theme: "All images are compressed."— Presentation transcript:

1 All images are compressed.
1st U30 Workshop, 2006 Sep, Tokyo 宮崎大輔：コンピュータビジョンにおける最適化手法 All images are compressed.

2 宮崎大輔：コンピュータビジョンにおける最適化手法
1st U30 Workshop, 2006 Sep, Tokyo 宮崎大輔：コンピュータビジョンにおける最適化手法 コンピュータビジョンにおける最適化手法 池内研ポスドク２年目 宮崎大輔

3 本日の内容 松山隆司，久野義徳，井宮淳 「コンピュータビジョン 技術評論と将来展望」 第11章 コンピュータビジョンにおける最適化手法 －モデルの妥当性と解の安定性－ 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

4 予備知識：誤差関数 データ を一つの数値 y=aで表したい いまいち いまいち ピッタリ合う！ 15 10 5
いまいち いまいち ピッタリ合う！ 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

5 予備知識：誤差関数 データ と の差 y=4だと差が大きい y=10だと差が小さい 宮崎大輔：コンピュータビジョンにおける最適化手法
1st U30 Workshop, 2006 Sep, Tokyo

6 予備知識：誤差関数 差 が最小となるときのaが データ を で最も良く表すことができる
この差を誤差関数・コスト関数・目的関数・ペナルティ関数という 関数の最小化方法は様々な方法があるが，ここでは述べない 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

7 予備知識：誤差関数 ちなみに，この例での解答は は下に凸の２次関数なので 最小値の点では微分の値が0 これを とすると をaで微分すると
6 は下に凸の２次関数なので 10 最小値の点では微分の値が0 これを とすると をaで微分すると よって つまり， つまりaはyiの平均： 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

8 二階微分を小さくする→曲線が滑らかになる
予備知識：微分と滑らかさ 二階微分を小さくする→曲線が滑らかになる 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

9 関数当てはめ問題 データ←多項式やスプライン関数のパラメータ推定 関数を人間が与える 関数の自由度を上げる→うまく当てはまる
弛緩法・正則化法・最適化法 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

10 これを解く→ill-posedな問題：解が一意に定まらない
正則化手法 ２次元画像から３次元復元 解は無数にある 正則化手法：数学的に「安定」な解 これを解く→ill-posedな問題：解が一意に定まらない 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

11 サンプリング点に滑らかな関数を当てはめる
点の数：N 当てはめる関数:f 各点のデータ:(xi,yi) データが関数にどれだけ近いかを表す ２階微分が小さい→滑らか 曲率が小さい（＝曲率半径が大きい） 曲率大 曲率小 これを最小化すれば 滑らかな関数でデータを表せる これが正則化の基本的な考え方 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

12 別の例：線形関係Az=uで，uからzを求める
正則化手法 別の例：線形関係Az=uで，uからzを求める を最小化する方法 正則化項 ペナルティ項 Azとuがどれだけ近いかを表す 先程の例だと 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

13 滑らかな関数 解空間が巨大なill-posedな問題 解が安定になる物を選ぶ 解が滑らかな関数となる物を選ぶ
宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

14 正則化パラメータの決定法 誤差が分かっている場合は誤差に応じて決める 学習により誤差を計算する など このλをどうやって決めるか？
宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

15 計算方法 確率的な手法 決定的な手法 シミュレーテッドアニーリングなど 最急降下法など 確率的な手法は計算時間がかかる しかし
確率的な手法は扱える問題の範囲が広い 決定的な手法で解ける問題であれば， 能力でも計算時間でも決定的な手法が有利 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

16 コンピュータビジョンの問題と正則化 ノイズ除去 形状復元 エッジ検出 領域分割 オプティカルフロー ステレオ視 動的輪郭モデル
宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

17 ノイズ除去 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

18 ノイズ除去：スプライン関数 観測データに対するスプライン関数の当てはめ 重みの計算 安定化汎関数（正則化項）は 観測データ 重み
微分による滑らかさ 観測データに対するスプライン関数の当てはめ 重みの計算 この２つを交互に繰り返して計算する 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

19 ほとんど滑らかだが，いくつか不連続点がある場合
ノイズ除去：不連続点 ほとんど滑らかだが，いくつか不連続点がある場合 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

20 にはノイズが載っているので，それをキレイにして
ノイズ除去：GNC法 データ にはノイズが載っているので，それをキレイにして にする 最小化： ペナルティ項 正則化項 データuが当てはめる値yに どれだけ近いかを表す シャープになって欲しい部分は： 滑らかになって欲しい部分は： （一次微分） 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

21 ノイズ除去：GNC法 反復回数を増やすごとにrとqを近づけて，最終的にr=qとすれば， 連続部分と不連続部分がはっきりと検出できる 一次微分
を使う （微分が小さい→変化が小さい→滑らかな部分） 一次微分 がしきい値rより大きいとき を使う （微分が大きい→変化が大きい→不連続部分） 一次微分 がしきい値rとqの間のとき を使う 反復回数を増やすごとにrとqを近づけて，最終的にr=qとすれば， 連続部分と不連続部分がはっきりと検出できる 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

22 ノイズ除去：多価関数 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

23 ノイズ除去：多価関数 データ点yは関数f1かf2のどちらかに属する
yがf1に一致すればy-f1が0になり，(y-f1)(y-f2)も0になる yがf2に一致すればy-f2が0になり，(y-f1)(y-f2)も0になる ペナルティ項 正則化項 これを最小化→観測データがどっちの 曲線・曲面に属するかを指定する必要がない 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

24 コンピュータビジョンの問題 ２次元の情報から３次元の情報を復元する ill-posedな問題 （ペナルティ項）＋λ（正則化項）
滑らかさを表す ステレオやオプティカルフローなどのコスト関数 これまでのスライドでは正則化項の説明ばかりしてきたが これ以降のスライドでも正則化項の説明をメインに行う 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

25 形状復元 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

26 ２次元画像の格子(x,y)に復元したい３次元情報fがある
形状復元：Sobolev半ノルム 安定化汎関数（正則化項）としてソボレフ半ノルムを使用 ２次元画像の格子(x,y)に復元したい３次元情報fがある fのx軸方向とy軸方向の微分→滑らかさ 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

27 形状復元：Controlled continuity stabilizer
安定化汎関数（正則化項）として以下を使う ρ→0：正則化項が使われず，不連続になる ρ→大：正則化項が効いてきて，滑らかになる τ→0：１次微分を最小化→連続な直線に近くなる τ→1：２次微分を最小化→滑らかな曲線に近くなる τとρの値を各点ごとに適切に変えることにより 不連続部分も滑らか部分もうまく表現できる vとτとρは交互に推定する反復計算 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

28 エッジ検出 エッジ検出にも利用される（詳細は省略） 宮崎大輔：コンピュータビジョンにおける最適化手法
1st U30 Workshop, 2006 Sep, Tokyo

29 領域分割 領域分割（詳細は省略） （概念図） 宮崎大輔：コンピュータビジョンにおける最適化手法
1st U30 Workshop, 2006 Sep, Tokyo

30 この明るさの変化を利用して物体の動きを計算する
オプティカルフロー 物体が動くと，ある点の明るさが変化する この明るさの変化を利用して物体の動きを計算する 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

31 （注：オプティカルフローは物体の動きを表さない状況もある）
宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

32 実感が沸かないと思うので次のスライドで具体例で説明する
オプティカルフロー オプティカルフロー方程式 画素の濃淡の変化に対する拘束 物体表面の輝度 物体の速度 実感が沸かないと思うので次のスライドで具体例で説明する 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

33 具体例 輝度の傾き x軸だけの例で説明する 輝度の傾き この点に着目 時刻t 時刻t+1 t-1 t t+1 時刻t-1 物体の速度
オプティカルフロー方程式が成り立つ 大きな変化がなく，小さな変化がある場合 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

34 オプティカルフローを解こう 輝度 は分かっており，そこから 物体の速度 を求めたい
未知数は２つで，方程式は１つなので，ill-posedな問題 正則化手法で解く 正則化項 物体速度の微分を最小化 →隣り合った点の速度は大体同じ 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

35 ステレオ視 「形状復元」の項で説明した正則化項が利用できる 宮崎大輔：コンピュータビジョンにおける最適化手法
1st U30 Workshop, 2006 Sep, Tokyo

36 Snakes (Active Contour)
宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

37 Snakes (動的輪郭検出法） 初期輪郭を設定 エネルギー関数を最小化するにつれて， 輪郭は滑らかな曲線を描きつつ，エッジに近づいていく
最終的に，エッジの場所で収束する 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

38 エネルギー関数 輪郭の滑らかさ 一次微分 二次微分 円に近づける 宮崎大輔：コンピュータビジョンにおける最適化手法
1st U30 Workshop, 2006 Sep, Tokyo

39 エネルギー関数 エッジの強さ 画像の一次微分→エッジ エッジに近づける 宮崎大輔：コンピュータビジョンにおける最適化手法
1st U30 Workshop, 2006 Sep, Tokyo

40 Snakesの問題点 初期輪郭の位置によって解が変化する 事前知識を導入することがむずかしい 計算時間がかかる
パラメータα，βによって解が変化する トポロジの変化に対応できない 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

41 様々な改良（詳細は省略） 解空間の解析 事前知識の導入 高速計算法
初期値にあまり依存せずに解を求めるためには，最小化を行う関数がどのような性質を持っていればいいかを解析 事前知識の導入 輪郭をある曲率に近づくようにする 物理モデルを導入 形状を文法規則で記述 トポロジの変化に対応 高速計算法 動的計画法 Greedy Algorithm 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

42 幾何モデルに基づくSnakes Snakesをこの方向に動かす： 法線 曲線 宮崎大輔：コンピュータビジョンにおける最適化手法
1st U30 Workshop, 2006 Sep, Tokyo

43 幾何モデルに基づくSnakes この部分の意味→曲線の滑らかさ まずは の意味 曲率が小さい （曲がっている率が小さい
→あまり曲がっていない） 曲率が大きい （曲がっている率が大きい →かなり曲がっている） 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

44 幾何モデルに基づくSnakes この部分の意味→曲線の滑らかさ まずは の意味 法線 凸：曲率が正 凹：曲率が負
宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

45 幾何モデルに基づくSnakes この部分の意味→曲線の滑らかさ 次に の意味 エッジ 0: エッジに近い 1: エッジから遠い
gは0～1の関数 g=1 g=0 g=1 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

46 幾何モデルに基づくSnakes この部分の意味→曲線の滑らかさ 最後に の意味 曲線 曲線 エッジ エッジ 曲線がエッジに近いと
gは0に近い 曲線がエッジから遠い gは1に近い 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

47 幾何モデルに基づくSnakes この部分の意味→エッジに向かう動き まずは の意味 エッジ エッジ g=1 （説明の都合上
横方向の位置 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

48 幾何モデルに基づくSnakes この部分の意味→エッジに向かう動き まずは の意味 gの一次微分→gの傾き（接ベクトル） g
宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

49 幾何モデルに基づくSnakes この部分の意味→エッジに向かう動き まずは の意味 一次元の場合は 法線が右向きだった場合 はただのかけ算
二次元の場合は これが内積に 変わるだけ g 宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

50 幾何モデルに基づくSnakes この部分の意味→エッジに向かう動き 最後に の意味 法線が右向きだった場合 g g
宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

51 まとめ 解空間が大きすぎて，解が見つからない問題 正規化項を付ける 解空間をせばめて，それらしい解を見つける
宮崎大輔：コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo

52 宮崎大輔：コンピュータビジョンにおける最適化手法
1st U30 Workshop, 2006 Sep, Tokyo 宮崎大輔：コンピュータビジョンにおける最適化手法 Daisuke Miyazaki 2006 Creative Commons Attribution 4.0 International License. 宮崎大輔, "コンピュータビジョンにおける最適化手法," U30ワークショップ, 東京, 2006年9月