画像処理論第5回佐藤洋一生産技術研究所情報理工学系研究科電子情報学専攻／情報学環 http://www.hci.iis.u-tokyo.ac.jp/~ysato/ 前回講義の復習   コーナー特徴  Moravecオペレータ  ZHオペレータ、KRオペレータ  Tomasi-Kanadeオペレータ  Harrisオペレータ  SUSANオペレータ SIFT特徴コーナーとして望ましい性質  輝度変化の大きさとそのパターン  画像フレーム間における対応付けに必要  平坦な領域→対応づけのための手掛かりが無い  一つの方向にのみ輝度変化が見られる領域 →エッジ方向に関して対応付けができない（オプティカルフローにおけるapature problemに相当）コーナーとして望ましい性質  輝度変化の大きさとそのパターン  画像フレーム間における対応付けに必要  平坦な領域→対応づけのための手掛かりが無い  一つの方向にのみ輝度変化が見られる領域 →エッジ方向に関して対応付けができない（オプティカルフローにおけるapature problemに相当） Tomasi-Kanadeオペレータ 1. 領域 W に対して、行列Cの固有値 λ1 , λ2 を計算 2  ∂I  ∑ ∂x C= W  ∂I ∂I ∑ ∂x ∂y W ∂I ∂I   ∑ x y ∂ ∂ W  2 ∂I  ∑  W ∂y  W 2. min(λ1 , λ2 ) が大きい点  領域Ａ内の輝度変化パターンと固有値との関係両方とも小さい → I 片方が小さい → II 両方大きい → III I II III Harrisオペレータ  Tomasi-Kandeオペレータの近似版  min(λ1 , λ2 ) の代わりに以下の評価式を用いる R = λ1λ2 − k (λ1 + λ2 ) 2 = Det(C ) − kTr(C )  2 kは任意の値に設定（通常はk=0.04程度） SIFTアルゴリズム SIFT特徴の例 DoGピラミッドからの極値検出特徴点の絞り込み主曲率にもとづく絞り込み固有値計算を用いない判別低コントラスト点の削除  推定されたサブピクセル位置でのDoG出力値回転に対する正規化特徴ベクトルによる特徴量記述 128次元ベクトルの正規化 → 照明変化の影響の軽減本日の講義の内容  ライン特徴の検出  ハフ変換  一般化ハフ変換  幾何学的ハッシングライン特徴の検出エッジ点からの直線の検出  ハフ変換（Hough transform）が良く用いられる  パラメータ空間への投票により直線を検出ハフ変換による直線の検出  画像空間とパラメタ空間の関係  画像中の直線の表現（傾きmと切片c） y y = mx + c c c = −mx + y (x,y) x エッジ点(x,y)を通る全ての直線 m パラメタ空間(m,c)内の直線パラメタ空間における投票  画像中の各エッジ点ごとにパラメタ空間で直線を追加  画像中の直線に対応するパラメタ(m,c)にピーク →ハフ変換の基本的な考え方 c y c = − xm + y (x,y) c = − x′m + y′ (x’,y’) x m ハフ変換における投票空間  パラメタ空間を離散化して投票→2次元配列P[m,c]  配列Pにおけるピークが直線に対応  ピークの“鋭さ”が直線の強さを示すハフ変換による投票の例ハフ変換の改良（１） y  = mx + c による表現の問題  y軸に平行な直線で傾きmが無限大  パラメタ空間(m,c)にばらつきが存在より偏りのないパラメタ空間 ( ρ , θ ) を利用 x cos θ + y sin θ = ρ 直線を表すパラメタ空間ハフ変換の改良（２）  パラメタ空間への投票のコストの問題   (x,y)を通る全ての直線に対する投票エッジ検出オペレータのgradientを利用  gradient方向を利用して直線の範囲を限定  gradient強度により投票を重み付けハフ変換の改良（３）  精度向上のためにパラメタ値を実数のまま記録  既に記録されているパラメタと同じであれば、そのパラメタの投票数を１増やす  同じものがなければ新しいパラメタを追加ハフ変換による曲線の検出  曲線検出も直線と同様 ( x − a ) 2 + ( y − b) 2 = r 2  エッジ点(x,y)に対して、上式を満たす全パラメタ組(a,b,r)へ投票する  一般に、曲線が次式で与えられれば検出可能  f ( x, y , a ) = 0   a  は曲線を表すパラメタ。直線ならば a = ( ρ , θ ) ランダムハフ変換  ハフ変換を効率的に行うための工夫  各エッジ点ではなく、エッジ点の組による投票  例：直線検出の場合ランダムハフ変換  n点で一意に決定される図形に対し、以下を繰り返す  画像中のエッジ点からn点の組をランダムに選ぶ  n点の組に対応する図形のパラメタを計算  求めたパラメタをパラメタ空間に投票  パラメタ空間にピークが見つかれば終了  RANSAC (Random Sample Consensus)と関係ハフ変換の長所・短所   長所  線の一部欠損に対して頑健  パラメタ空間への投票を並列化が可能  本数に依存せずに一括処理可能短所  パラメタ空間への投票の計算コストが高い  投票空間におけるピーク検出が容易ではない  求められるのは線分ではない（端点は不明）  短い線は検出が困難  パラメタ数の増加とともに急激にコストが増大ハフ変換による直線検出の利用例  J. Xiao and Y. Furukawa, “Reconstructing the world’s museums”, ECCV2012 (Best Student Paper Award) 一般化ハフ変換  ハフ変換を輪郭が定義されている物体全般に拡張  ハフ変換   エッジ点（x,y）が与えられたときに、 f ( x, y, a ) = 0 パラメタを投票  一般化ハフ変換   輪郭形状をもとに、投票するパラメタの表を事前準備最初に、物体の姿勢と大きさが一定の場合を満たすテンプレートと形状定義表  テンプレートの基準点Qを定義  輪郭線上の点Pにおいて、接線方向θごとに基準点Qの位置（距離rと方向α）を記録  xPi Q   ri cos α i     y P Q  =  r sin α  i   i   i パラメタ空間における投票 1. 各エッジ点（x,y）において、gradientからエッジ方向θを計算 2. 形状定義表を参照し、基準点の候補位置Qに投票 3. 全ての投票後に、候補位置Qにピークがあれば、対象物体をその位置に検出 Q xQ = x + r (θ ) cos[α (θ )] Q yQ = y + r (θ ) sin[α (θ )] 回転・スケールの考慮  一般には、対象物体の回転とスケールは未知  基準点位置算出の際に、回転 Φ とスケール S を考慮 Φ Pi ( x, y ) Sri Q  αi + Φ θ = θi + Φ xQ = x + Sri cos(α i + Φ ) yQ = y + Sri sin(α i + Φ ) この場合のパラメタ空間は ( x, y, S , Φ ) の4次元となる  (1) パラメタ空間における投票 1. 各エッジ点（x,y）において、gradientからエッジ方向θを計算 2. 全ての回転Φ・スケール S に対して、式(1)と形状定義表を参照し、基準点の候補位置Qに投票  3. 形状定義表のインデックスとなるエッジ方向は θ − Φ 最後に、パラメタ空間 ( x, y, S , Φ )においてピークを検出する Pi ( x, y ) Sri Q αi + Φ θ = θi + Φ θ −Φ 一般化ハフ変換のまとめ  任意の輪郭形状をもった物体を取扱可能  輪郭がとぎれていたり、一部が遮蔽されているような場合でも検出可能  回転とスケールを考慮した場合のパラメタ空間が4次元となり、計算コストが急激に増大幾何学的ハッシング  一般化ハフ変換と似た物体検出法  モデル準備：  姿勢に対する不変特徴をハッシュテーブルに記録幾何学的ハッシング  モデル検出：  画像中特徴点から2点を基底として選択  各特徴点について、ハッシュテーブルのエントリに投票  最高得点のモデル・基底を検証 y 画像中特徴点 A１，４ A６，５ A１，４ A６，5 ３５１６５ A１，４ A６，５４１１ A１，４ A６，５２３ A１，４ A１，４４２ A６，５５モデルA x ４３２基底1-3の時、（A, 1-4)で最高得点幾何学的ハッシング    特長  モデル数が多くても問題ない  モデルの検出とアラインメントを同時実行  並列処理に向く基底数の違い  2点による基底→スケール・回転・平行移動  3点による基底→アフィン変換（上記＋シアー変形）一般化ハフ変換との違い  一般化ハフ変換→全てのスケールと回転  幾何学的ハッシング→基底の組数だけ本日の講義内容のまとめ  ライン特徴の検出  ハフ変換  一般化ハフ変換  幾何学的ハッシング  参考資料  Ballard&Brown 4.3章  画像処理標準テキスト 3.2章、6.3章  Hartley 4.7.1  Geometric Hashing論文  CVonline