Microsoft PowerPoint - CV06Cut.ppt [互換モード]

Transcription

1 画像特徴 ( 点 直線 領域 ) の検出と識別 -3 Hough 変換 投票と多数決原理に基づく幾何学的対象の検出と識別 参考書 : 松山隆司 久野義徳 井宮淳 コンピュータビジョンー技術評論と将来展望ー新技術コミュニケーションズ酒井幸市デジタル画像処理入門コロナ 結果として ( エッジ点 ) 例えば : 欠落のある情報 投票 多数決 図形検出 何の図形? 結果として 投票と多数決原理に基づく図形の検出 識別法 例えば : 欠落のある情報 投票 多数決 図形検出 Hough 変換 (P.V.C.Hough 196): 値画像から 直線の検出 Hough 変換 (R.O.Duda and P.E.Hart 197): 値画像から 円 楕円の検出 一般化 Hough 変換 (D.H.Ballard 1981): 値画像から 平行移動 回転 ズームなどの変換を受けた任意形状の図形の検出 Geometrc Hashng(Y.Lamdan et al. 1988): 値画像から 予め与えた複数の図形集合の検出 識別 1

2 (X1, Y1) (X, Y) (Xn, Yn) 画像空間 パラメータ空間 b y 1 3 (A,B) 3 a 1 x パラメータ (a-b) 空間の問題点 入力画像から抽出された図形の x, y から パラメータ a, b を決定すればよいが 傾きが垂直に近くなると a の絶対値が無限大に近く (b もその可能性がある 考えること : どんな場合?) y = ax + b ハフ変換では a-b パラメータ平面上の各点の累積度数を格納するために 次元配列が用いられるこのままでは大きなメモリ容量を必要とするため コンピュータ処理には不都合 o 空間 直線の方程式 : y = ax + b = xcos + ysn : 原点から直線に垂線を引いたときの長さ :x 軸とのなす角 ; 範囲は 0 垂線がy < 0の領域にあるときは < 0 一本の直線に対し が唯一に決まる ある1 点 (x, y) を通る直線群は無限に存在 が無数その中ある一本の直線に対し が唯一に決まる 空間 xcos ysn では 角度 は有界 で 画像の大きさが有限であるため も有界となる ほとんどの直線検出用ハフ変換では パラメータ空間が用いられている

3 xcos ysn を用いて計算すれば 直線上の1 点 (X, Y) に対する パラメータ空間の一本の曲線が求まる 直線上の点 1と点 に対する二本の曲線が求まる曲線はある点 ( 0) で交差この ( 0) が点 1, 点 を共通に通る直線を表す ( 0, 0) Hough 変換の処理の流れ 1. 初期化 : パラメータ空間を セル と呼ばれる要素に分解 全てのセルの投票度数を0にリセット. 投票 : 各特徴点について軌跡を計算 軌跡が通過するセルの度数をプラス1 3. ピーク検出 : 全ての特徴点からの投票を終了した後 投票度数が閾値以上の極大値を持つセルを抽出 4. 検証 : 真のピークかどうかをチェック 入力画像 ( 一直線 ) tokens 投票数を濃度で表す Votes Horzontal axs s θ, vertcal ピークが一点だけ s. 入力画像 ( ノイズある直線 ) 投票数を濃度で表す 入力画像 ( ランダムの点 ) 投票数を濃度で表す tokens votes ピークがある点付近に複数あり tokens votes 閾値以上のピークがない 3

4 Real World Example 入力画像 ( 研究例 ) Orgnal Edge Detecton Found Lnes Parameter Space 複数個ピークがあり 複数本の直線を抽出 ハフ変換で抽出された黄色両側の直線 全体として 安定な結果が得られた 3 次元 Hough 変換より眼鏡の抽出 次元空間内の直線 3 次元空間内の平面 眼鏡の平均的な形状 フレーム部分 同一平面への近似 対称性 眼鏡が除去された結果例 眼鏡の抽出 頭部の姿勢推定 4

5 応用 ρ=xcosθ + ysnθ edge detecton mage segmentaton 特長 smple algorthm nose tolerance 問題点 The Hough transform unable to detect the exact poston of the lne pxels hgh memory reuqrements - hgh computatonal cost Hough 変換の曲線への応用 今まで説明したHough 変換は直線を検出するためにしか役立たないが 一組のパラメータで表現しうる形状については全て 類似の変換法が応用できる 例えば ( 平面上の ) 円は中心 (x0,y0) と半径 r を表す三つのパラメータに変換できるので 3 次元 Hough 空間を用いることになる 楕円も中心(x0,y0) 長軸 a 短軸 b 傾き を表す5つのパラメータで表現できるので 5 次元 Hough 空間を用いることになる 更に複雑な図形には一般化 Hough 変換が用いられる Hough 変換 : 円検出 ( 半径既知 ) Hough 変換 : 円検出 ( 半径未知 ) 円の方程式 : ( x a) ( y b) r 半径が既知 ( 固定 ) の場合 : 次元 Hough 空間に投票 A( a, b) パラメータ式 : a x r cos ; b y r sn b a 半径が未知の場合 求める円周上にある ( はずの ) 一点 X, Y について それを通る無限に多くの円を考えることができる それらの円の中心座標 半径をパラメータとして 3 次元 Hough 空間 (CenterX,CenterY,r) 内にプロットすると 一つの曲面が形成される ( 投票 ) パラメータ式 : CenterX x r cos ; CenterY y r sn Hough 変換 : 円検出 ( 半径未知 ) もう一つのアルゴリズム : 次元 Hough 空間 (a, b) 内で 半径を変化しながら投票 パラメータ式 : b a tan x tan y 直線円楕円双曲線 曲線フィット 1 頭の抽出例 放物線 一般的な 次曲線 5

6 曲線フィット 出席チェック 6 直線を検出する Hough の基本原理と処理の流れを記入してください 学籍番号と名前 今日の日付を記入してください レポート 3 廊下を撮影した画像 値化して その画像に対して -Hough 変換を行うことによって 消失点の位置をもとめてください ニュートン (I.Newton) が音速実験を行った回廊ーケンブリッジ大学内ー 004 年 5 月 ECCV 消失点 (Vanshng pont): 空間中の平行線は画像面上では一点 ( 消失点 ) で交わる u 0 u 1 u レポート 3 の提出要求 : 1) 廊下の画像を一枚選んで 原画像と処理した結果画像を提出してください 注 1: エッジ検出や 値化処理などはプログラムを作るか OpenCV の関数を利用するかどっちでも OK です 注 : 標準的ハフ変換による線の検出例 : cvhoughlnes (src_mg_gray, gray storage, CV_HOUGH_STANDARD, 1, CV_PI / 180, 50, 0, 0); ) プログラムも提出してください ( 説明を含む ) 提出期限 : 3 週間以内 ( 講義時間 or 私の居室 A61) 6

7 形状とポーズ一緒に投票 形状が固定 座標変換パラメータ投票と多数決 Generalzed Hough Transform Correlaton For each translaton, compute the correlaton between the target and the translated query: f, T ( g ) f ( x ) g T ( x ) dx Hough 変換 一般化 Hough 変換 Hough 変換と一般化 Hough 変換における投票空間 Generalzed Hough Transform Correlaton For each translaton, compute the correlaton between the target and the translated query: f, T ( g ) f ( x ) g T ( x ) dx 一般的に形状モデルは関数で表現できない (4 次元 ) 基準点 一般化 Hough 変換の投票方法 x(x, (, Y) 1. 画像上の特徴点 (X,Y) と 勾配方向 を求める. 回転角 拡大率 sのパラメータ空間中の全ての s) の組合せに対して - に対応するRテーブル中のエントリから 平行移動ベクトル (u, v) ) を以下の式によって求め 投票を行うし u X v Y r( r( ) s cos( ( ) s sn( ( ) ) ) ) 7

8 ポーズが固定 ( 位置 大きさ 回転の正規化より ) 形状に投票 / 多数決 Geometrc Hashng Feature Extracton Compute nvarants 不変特徴を計算 Hash-table Lst of obects Hash Table 中の対応要素に モデル 記述に用いた基底 の組を登録 Verfy Bass Geometrc Hashng 拡大縮小 回転平行移動 点 4 と点 1 から生成された基底に基づいて Hash Table にモデルを登録するイメージ Wolfson and Rgoutsos, Geometrc Hashng, an Overvew, 1997 点, を基底とする場合 モデルの登録 X P P 点,kを基底とする場合 P P N 個の点によって表されたモデル M { P, P, P ) から 点 P,Pを選択 1 する これらの 点から N ( x, y ), Y ( y, x ) となる直交基底を生成する この基底で表された各特徴点の座標値を求めることにより 図に示す不変特徴の集合 {( x, y )} {( X ( P P ), Y ( P P )} f f が得られる この{( x, y )} はもとの点 集合 { P } が平行移動や回転 拡大など の座標変換を受けても変化しないという性質を持っている k f f k 8

9 投票数011/5/16 Bass Geometrc Hashng 全ての 点の組合せから生成される基底に対してそれぞれ不変特徴を求め それらを全て Hash Table に登録しておく Wolfson and Rgoutsos, Geometrc Hashng, an Overvew, 1997 Wolfson and Rgoutsos, Geometrc Hashng, an Overvew, 1997 Bass Geometrc Hashng Recognton of Obects Fnd Features Select Bass Parameterze Features Do hash table lookup Hstogram number of matches per model モデルの多重記述により モデルと相似な図形が与えられたとき この図形に含まれる任意の 点から求められる不変特徴と Hash Table 上に記録された ( モデル 基底 ) の組のどれかが一致することが保証 Wolfson and Rgoutsos, Geometrc Hashng, an Overvew, 1997 道路車家トラ草原 (3,) (4,1) (1,4) Recognton of Obects Verfcaton 確認 Least Square Transform Recovery (fnd the rotaton, and translaton of the bass) Geometrc Hashng の投票と識別 1 1.Hash Table の各要素に対する投票数を 0 にする. 画像からまだ選択されていない任意の 点を選択し 基底を求める 3. この基底に対して画像上の全ての点の不変特徴を計算し 対応する Hash Table 中の要素の投票度数を各々 1 増加させる 4. 投票終了後 ( モデル 基底 ) の組ごとに投票度数を集計し 予め与えた閾値を越えるものがあるかどうかを調べる 閾値を越えた投票が得られたものがなければ 1. の処理に戻る 9

10 Geometrc Hashng の投票と識別 5. 高い投票が得られた ( モデル 基底 ) 組の基底と 画像から求められた基底を対応付ける座標変換を求める 6. 求められた変換を用いてモデルを画像上に写像し モデルにマッチする特徴点が十分存在することを確認する 特徴点が十分存在すれば終了し そうでなければ1. の処理に戻る 画像中に存在する複数の対象を識別 検出する場合には モデルにマッチする特徴点集合を取り除きながら 上記の手続きを繰り返し行う Geometrc Hashng の意味 対象とするモデルの全てに関して同様に記述を行っておくことにより 複数のモデルを同時に扱うことが可能となる 1. Hash Table に登録された形状モデルは 不変特徴によって記述された形状の テンプレート と見なすことができる. Geometrc Hashng において ポーズを固定する ということは 画像から不変特徴を求める際に 1 つの基底を用いることを意味 10