All images are compressed.

Slides:



Advertisements
Similar presentations
Absolute Orientation. Absolute Orientation の問題 二つの座標系の間における剛体 (rigid body) 変換を復元す る問題である。 例えば: 2 台のステレオカメラから得られた3次元情報の間の関 係を推定する問題。 2 台のステレオカメラから得られた3次元情報の間の関.
Advertisements

22 ・ 3 積分形速度式 ◎ 速度式: 微分方程式 ⇒ 濃度を時間の関数として得るためには積分が必要 # 複雑な速度式 数値積分 (コンピューターシミュ レーション) # 単純な場合 解析的な解(積分形速度式) (a)1 次反応 1次の速度式 の積分形 [A] 0 は A の初濃度 (t = 0 の濃度.
池内研究室 Computer Vision Laboratory 東京大学 The University of Tokyo 偏光レイトレーシング 宮崎大輔 2004 年 6 月 22 日(火) CVL セミナー.
Determining Optical Flow. はじめに オプティカルフローとは画像内の明る さのパターンの動きの見かけの速さの 分布 オプティカルフローは物体の動きの よって変化するため、オプティカルフ ローより速度に関する情報を得ること ができる.
Ruth Onn, Alfred Bruckstein (Int J Comp Vision 1990)
テンソル積展開 宮崎大輔.
コンピュータビジョン特論 OpenCVについて
コンピュータビジョン特論 第8回対象追跡 2006年11月22日 加藤丈和.
HOG特徴に基づく 単眼画像からの人体3次元姿勢推定
高度情報演習1A “テーマC” 実践 画像処理プログラミング 〜画像認識とCGによる画像生成〜 第四回 演習課題 画像中からの物体抽出処理(背景情報を手がかりとして) 芝浦工業大学 工学部 情報工学科 青木 義満 2006/05/15.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
ウェーブレットによる 信号処理と画像処理 宮崎大輔 2004年11月24日(水) PBVセミナー.
Pattern Recognition and Machine Learning 1.5 決定理論
「Self-Organizing Map 自己組織化マップ」 を説明するスライド
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
「データ学習アルゴリズム」 第3章 複雑な学習モデル 3.1 関数近似モデル ….. … 3層パーセプトロン
エッジの検出 画像中に表示された物理の輪郭(エッジ(edge))や線では、一般的に濃淡が急激に変化しており、これらは画像中のなんらかの構造を反映していることが多い このようなエッジや線の検出処理は、画像理解や認識のための前処理として重要である   差分型によるエッジ検出   零交差法によるエッジ検出.
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
形状モデリングにおいて,任意の自由曲面を定義する必要のある場合がある.自由曲面の表現法について説明する.
第3章 重回帰分析 ー 計量経済学 ー.
第3章 重回帰分析 ー 計量経済学 ー.
SURF: Speeded Up Robust Features
DARTs: Efficient scale-space extraction of DAISY keypoints
「データ学習アルゴリズム」 第2章 学習と統計的推測 報告者 佐々木 稔 2003年5月21日 2.1 データと学習
確率・統計輪講資料 6-5 適合度と独立性の検定 6-6 最小2乗法と相関係数の推定・検定 M1 西澤.
非線形方程式の近似解 (2分法,はさみうち法,Newton-Raphson法)
誤差の二乗和の一次導関数 偏微分.
第3章 補足:パラメータが極小値に収束する例
3次元剛体運動の理論と シミュレーション技法
Yuri Y. Boykov Marie-Pierre Jolly
スペクトル・時系列データの前処理方法 ~平滑化 (スムージング) と微分~
第6章 カーネル法 修士2年 藤井 敬士.
線形フィルタと畳み込み積分 マスクによる画像のフィルタリング 1.入力画像中の関心の画素のまわりの画素値
データ解析 静岡大学工学部 安藤和敏
エッジの検出 画像中に表示された物理の輪郭(エッジ(edge))や線では、一般的に濃淡が急激に変化しており、これらは画像中のなんらかの構造を反映していることが多い このようなエッジや線の検出処理は、画像理解や認識のための前処理として重要である   差分型によるエッジ検出   零交差法によるエッジ検出.
Bottom-UpとTop-Down アプローチの統合による 単眼画像からの人体3次元姿勢推定
第11回   ディジタル画像(2) ディジタル画像処理(2)
情報理工学系研究科 数理情報学専攻 数理第四研究室 博士三年 指導教員: 駒木 文保 准教授 鈴木 大慈 2008年8月14日
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
構造情報に基づく特徴量を用いた グラフマッチングによる物体識別 情報工学科 藤吉研究室  EP02086 永橋知行.
ルンゲクッタ法 となる微分方程式の解を数値的に解く方法.
東京農業大学 東京情報大学 附属第一高等学校・中等部 附属第二高等学校 附属第三高等学校・中等部
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
Data Clustering: A Review
Thesis Supervisor: Katsushi Ikeuchi 池内克史
パターン認識特論 担当:和田 俊和 部屋 A513 主成分分析
知識科学研究科 知識システム構築論講座 林研究室 佛明 智
文化財のデジタル保存のための 偏光を用いた透明物体形状計測手法
4. システムの安定性.
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
Bottom-UpとTop-Down アプローチの組み合わせによる 単眼画像からの人体3次元姿勢推定
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
第3章 線形回帰モデル 修士1年 山田 孝太郎.
データ解析 静岡大学工学部 安藤和敏
サポートベクターマシン Support Vector Machine SVM
22・3 積分形速度式 ◎ 速度式: 微分方程式 ⇒ 濃度を時間の関数として得るためには積分が必要
第16章 動的計画法 アルゴリズムイントロダクション.
22・3 積分形速度式 ◎ 速度式: 微分方程式 ⇒ 濃度を時間の関数として得るためには積分が必要
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
ポッツスピン型隠れ変数による画像領域分割
All images are compressed.
2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法)
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年8月1日 3.2 競合学習
シミュレーション演習 G. 総合演習 (Mathematica演習) システム創成情報工学科
回帰分析入門 経済データ解析 2011年度.
Cプログラミング演習 ニュートン法による方程式の求解.
コンピュータの高速化により, 即座に計算できるようになってきたが, 手法的にはコンピュータ出現以前に考え出された 方法が数多く使われている。
各種荷重を受ける 中空押出形成材の構造最適化
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ノイズ除去:多価関数 データ点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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

宮崎大輔:コンピュータビジョンにおける最適化手法 1st U30 Workshop, 2006 Sep, Tokyo 宮崎大輔:コンピュータビジョンにおける最適化手法 Daisuke Miyazaki 2006 Creative Commons Attribution 4.0 International License. http://www.cvl.iis.u-tokyo.ac.jp/ 宮崎大輔, "コンピュータビジョンにおける最適化手法," U30ワークショップ, 東京, 2006年9月