パターンと図形の検出 画像処理 z パターンの検出 テンプレートマッチング，類似度 サブピクセル位置推定 2015年度 （第11回） 高速探索法 z エッジ情報とヒストグラムによるパターン検出 チャンファーマッチング ヒストグラム情報を用いたアクティブ探索 z 特徴点検出 コーナー検出 中島 克人 DoG画像を用いた特徴点とスケールの検出 情報メディア学科 輪郭線検出 [email protected] z 図形要素検出 ハフ変換，一般化ハフ変換，ランダム化ハフ変換 2 パターンの検出 パターンの検出 テンプレートマッチング 類似度 z サブピクセル位置推定 z 高速探索法 z z パターン（pattern） z テンプレート（template） z テンプレートマッチング（template matching） 画像においては，その視覚的特徴や画素値そのもの z 比較・探索対象の標準パターン 被探索対象画像（の一部）がテンプレートと同じかどうかを判 断（＝検出）し，検出できた場合はその位置を求める事 同じかどうかは類似度によって判断する z テンプレートマッチングの応用 半導体上の回路やプリント基板上の部品の配置検査 ロボットビジョン その他，多数 3 パターンの検出 z パターンの検出 z テンプレートマッチング（続） テンプレート画像の走査（raster z z z 4 類似度（similarity measure） ⇔相違度（dissimilarity scan） measure） テンプレートと画像の一部が『同じ』かどうかの尺度 被探索対象画像上をテンプレート画像を少しずつ移動しながら順に 比較していく（通常，画像の左上から右下に横優先にて） 移動量（例えば，テンプレートの幅の0.2倍）とテンプレートサイズの 拡大量（例えば，1回の走査が終わる度に1.2倍）により，マッチング の回数が異なる 検出対象が回転している場合は，回転したテンプレートも必要 SSD（Sum z of Squared Difference／差の2乗和） ユークリッド距離の2乗 探索窓内の 画像（被探索画像） テンプレート z式12.1 I（i,j） M，N：テンプレートの幅と高さ， I（i,j）：被探索画像の画素値，T（i,j）：テンプレートの画素値 探索窓 ＝テンプレートと の比較領域 探索窓を走査 SAD（Sum z （sub-window） z図12.1 テンプレートマッチングにおけるテンプレートの移動（走査） T（i,j） of Absolute Difference／差の絶対値和） マンハッタン距離 z式12.2 5 6 画像処理 1 パターンの検出 z パターンの検出 類似度（続） NCC（Normalized z z z Cross-Correlation／正規化相互相関） NCC（正規化相互相関）の補足説明 T（i,j）をM×N次元のベクトルと見なす I（i,j）,T（i,j）をそれぞれM×N次元のベクトルと見た際の余弦（cosθ） 画素値の絶対値を無視し，画素値の相対的な比率を比較する z z ベクトルA＝{a1,a2},B＝{b1,b2}の内積A・Bの定義と余弦 z式12.3 z z A・B＝|A| |B| cosθ → cosθ＝A・B／|A| |B| cosθ＝（a1×b1＋a2×b2）／ （a12＋a22）×（b12＋ｂ22） M×N＝K次元ベクトルI,T ZNCC（相互相関係数） z M×N＝2×2＝4 のとき，テンプレート画像は4要素のベクトル { T（0,0）,T（1,0）,T（0,1）,T（1,1）} ＝{T（0）,T（1）,T（2）,T（3）} 比較対象の部分画像 I（i,j）も同様に4要素のベクトル z I（i,j）,T（i,j）のそれぞれの平均からの偏差のNCC の余弦 cosθ＝（I（0）×T（0）＋ ・・ ＋I（K-1）×T（K-1））／ （I（0）2＋ ・・ ＋I（K-1）2）×（T（0）2＋T（K-1）2） z式12.4 z式12.3 7 演習（類似度・相違度） パターンの検出 z 8 類似度（続） z SSD,SADは小さいほど類似度が高い（完全一致時0） z SSD,SADは相違度の尺度 入力画像（5×5画素）に対して，3×3画素のテンプレートマッ チングを行なう際の以下の類似度（相違度）を計算せよ 検索窓位置A 検索窓位置B NCC,ZNCCは大きいほど類似度が高い（完全一致時1） パターンマッチングとは z z 類似度の一番大きい（相違度の一番小さい）位置を2次元的に探索 I,Tをベクトルと見たとき，SSD,SAD,NCCの関係は図12.3の通り 1 2 0 3 3 2 3 5 2 2 0 4 7 3 0 2 2 0 4 3 1 5 2 1 2 1）検索窓位置A, BにおけるそれぞれのSAD 解答） 位置AのSAD＝ 位置BのSAD＝ 2）検索窓位置A, BにおけるそれぞれのSSD 解答） 位置AのSSD＝ 位置BのSSD＝ 入力画像 z図12.2 SSD相違度の例 z図12.3 SAD，SSD, NCCの関係 z サブピクセル／サブピクセル位置 z 1 0 4 3）検索窓位置A, BにおけるそれぞれのNCC （少数点第2位まで） 解答） 位置AのNCC＝ 位置BのNCC＝ 10 サブピクセル位置推定（sub-pixel position estimation） R（－1）, 画素単位で得られた類似度（相違 度）を連続なフィッティング関数で 補間し，フィッティング関数の最大 値（最小値）を求めること フィッティング関数 z 0 R（0）：相違度が最小の位置における相違度の値 サブピクセル位置推定 z 1 7 パターンの検出 画素より細かい単位／位置 z 4 3 テンプレート 9 パターンの検出 2 R（1）：両隣の位置の相違度の値 ：等角直線フィッティングの結果 R（－1） R（1） R（0） z式12.5 離散的な位置の値を通る，または， 近似する連続関数 等角直線フィッティング（SAD向き）， パラボラフィッティング（SSD向き） 等 （傾きが対称な2本の直線の交点のx座標から求まる） R（－1） R（1） R（0） ：パラボラフィッティングの結果 z式12.6 （3点を通る2次曲線の最下点のx座標から求まる筈） z図12.4 サブピクセル位置推定 11 z図12.4 12 画像処理 2 パターンの検出 パターンの検出 z 高速探索法（1） z 疎密探索法（coarse-to-fine 残差逐次検定法（Sequential Similarity Detection Algorithm／ SSDA） z SADを計算する際，領域内の差の絶対値（残差）を加算（Σ）している z z z式12.2 z 画像間の重ね合せがずれる（検出位置でない）と急激に残差が増大 する z の時は RSAD≒0 に対して T（i,j） I（i,j） の時は RSAD >> 0 I（i,j） z z 加算の途中で残差がある閾値を超えたら，検出位置ではないと判断 し，加算を打ち切り，次の位置の検査に進む（大幅な高速化が期待） z 閾値はそれまでの最小値とする（初期値は最初に求まるSAD値） ある位置で最小値を超えなければ，そこで求まったSADが新最小値 13 エッジ情報とヒストグラムによる パターン検出 多重解像度法，階層的探索 などとも称する 高速探索法（2） search） 被探索対象画像を何段階かの解像度で表現し，解像度の粗い画像 で検出位置の大まかな狙いを定め，徐々に詳細な検出位置を求める 探索開始前にイメージピラミッド （解像度を4倍ずつ落とした画像 群）を作成（テンプレートも同様に イメージピラミッドを作成） 探索は低解像度画像から行い， 類似度の高い領域（とその周辺） のみで高解像度画像での探索を 行う イメージピラミッド作成のための z図12.5 イメージピラミッド 画像データ量の増大はわずか z式12.7 14 エッジ情報によるパターン検出 z チャンファーマッチングの概要 エッジ画像のパターン検出手法 チャンファーマッチング z ヒストグラム情報を用いたアクティブ探索 z 全画面操作は低速なため，相違度の低い方向に検索窓を 移動させて検索（局所解に陥る可能性有り） 15 エッジ情報によるパターン検出 z 16 ヒストグラムによるパターン検出 チャンファーマッチングの手順 z エッジ画像から距離変換（エッジからの距離）画像を生成 ヒストグラム情報を用いた探索 検索窓内のカラーヒストグラム（色ヒストグラム）で 類似度を検索 検索窓のある位置での相違度とその勾配から相違度が低く なる方向を微分で求め，その方向に検索窓を移動する z z 移動できなくなれば，そこが相違度の極小点 形状は検査しないため計算が速い 形状等の詳細な検査の前段階に利用可 ヒストグラムの類似度算出法 最小点を求めるためには別途方策が必要 z テンプレート ヒストグラムインタセクション （histogram intersection） n ρ（p,q）＝Σ min（pi,qi） i =1 z バタチャリア係数 （Bhattacharyya coefficient） テンプレートの色分布 p p （正規化ヒストグラム） 探索窓内の 画像（被探索画像） n ρ（p,q）＝Σ pi ×qi i =1 17 問題：それぞれの値域は？ q 探索窓内の色分布 q 18 画像処理 3 ヒストグラムによるパターン検出 z 特徴点検出 テンプレート アクティブ探索 z 探索窓の全走査を高速化 ハリスのコーナー検出 コンセプト z z コーナー検出 FASTによるコーナー検出 探索窓のある位置で類似度がかなり 小さければ，探索窓を少しずらしても， 類似度はそれ程大きくならない 探索窓の移動により増加する 類似度の最大値を加えても， 全体である閾値以上にならない ならば，その移動位置での類似度 計算はスキップ DoG画像を用いた特徴点とスケールの検出 z 輪郭線検出 z Canny（キャニー／ケニー）のエッジ検出アルゴリズム 出る領域 入る領域 類似度増加の見積りと探索窓のスキップ z z 新位置の類似度 S≦ の類似度＋ が類似度満点 Sが閾値以上となる位置まで探索窓をスキップできる ヒストグラムによる類似度判定以外でも （画素数に応じて最大類似度増が計算可なら）使える高速化手法 19 特徴点検出 z 20 特徴点検出 特徴点 z コーナー検出 エッジ，コーナー（＝2つのエッジの交点），孤立点など z コーナー検出 FAST（Features from Accelerated Segment Test）による 画像中の物体検出やパノラマ画像生成などの際の手がかり z コーナー検出 画像間の対応位置を求めるには，特徴点を如何に正確かつ 注目画素pを中心とする周囲16画素が中心より明るいか類似か暗 いかを見て，16ビットの特徴ベクトルを構成し，この値でエッジかどう かを判定 効率よく検出するかが重要 z ハリスのコーナー検出（Harris corner detector） ヘッセ行列Mの固有値が大きい時，その位置にコーナーが存在すると考 える → 固有値分解の計算を省くために関数Rが代用される z式12.8 z式12.9 I：位置（x,y）の画素値 detM：Mの行列式 trM：Mのtrace（固有和） k：経験定数（0.04～0.15） 21 特徴点検出 特徴点検出 FASTによるコーナー検出（続） z 22 z 実際には16ビットを一度に検査せず，決定木を用いて，1ビットずつ の検査結果で場合分けして，次に検査すべきビットを順次決めていく ため，少ない検査でエッジかどうかが判定できる DoG画像を用いた特徴点とスケールの検出 DoG（Difference z of Gaussian） スケール（偏差値σ）の異なるガウスフィルタG（σ）を入力画像I に 畳み込んだ平滑化画像の差を取った画像 スケール検出 z z スケールが隣接する3枚のDoG画像上の注目画素とその26近傍を 比較し，注目画素が極値ならば特徴点とする その時のスケールが特徴点の細かさ（特徴点の局所性）を示す ：近傍画素 ：注目画素 23 24 画像処理 4 特徴点検出 z 特徴点検出 特徴点の検出例（原画への重ね合わせの結果） z 輪郭線検出 多くの場合「画素値のエッジ」を輪郭線とするが，エッジは不 連続で，ノイズ（誤検出エッジ）も含む． z キャニー（ケニー）のアルゴリズム（Canny edge detector） ラプラシアンやソーベルのエッジ画像はグレースケールだが， キャニーの結果は2値画像 原画（チューリップ） ソーベルによるエッジ画像 キャニーによるエッジ画像 25 特徴点検出 z 26 特徴点検出 キャニー（ケニー）のアルゴリズム（Canny edge detector） z z z キャニー（ケニー）のアルゴリズム（続） 第2段階（勾配の最大位置の検出＝細線化） 第1段階（ノイズ低減と微分） z x方向に1次微分した2次元ガウス関数を畳み込み，x方向微分値を 求め，次に同様に，y方向の微分値を求める． （この時のガウス関数の標準偏差σは用途に応じて適当に設定） 位置（x,y）の勾配の大きさ と勾配方向 は下式 z z式12.13 最大位置以外を破棄する事から，非最大抑制（Non-maximum suppression）とも呼ばれる 位置（x,y）の8近傍の内，勾配方向 に沿った勾配方向に 隣接する2つの画素の勾配の大きさと を比較し，いずれより も大きい場合は残し，そうでなければ 0 とする事により，細線化を行 なう． 第3段階（閾値処理による2値化） z z式12.14 z z 得られる画像（データ）は勾配強度と らなる多値画像（データ） と勾配方向 か 27 特徴点検出 z 28 特徴点検出 輪郭線検出結果の例 パラメータの変化に 対するエッジ検出結果の例 第2段階で求めた勾配の最大位置での勾配の大きさ g を使って 最終的な輪郭検出を行う 2つの閾値 THhigh と THlow を用いて2値化を行なう g < THlow ．．．輪郭画素としない g > THhigh ．．．輪郭画素とする THlow ≦ g ≦ THhigh ．．．輪郭画素に隣接している場合のみ輪 郭とする z 特徴点検出の 結果例 （原画への重ね合わ せの結果） z図12.7 z図12.6 29 特徴点検出 結果の例 30 画像処理 5 演習（輝度勾配） z 演習（輝度勾配） グレースケール画像（256階調）のある注目画素とその8近傍 が下記の画素値である （1） 注目画素から各方向への輝度勾配を求めよ （ ：注目画素） ただし，上下左右の画素への距離を1，斜め方向の画素への距離を1.4 とし，計算は小数点第1位を四捨五入せよ z （ 1 2 1 0 0 0 ：注目画素） グレースケール画像（256階調）のある注目 画素とその8近傍が下記の画素値である －1 －2 －1 ソーベルフィルタ（縦方向） （1） 注目画素の輝度勾配（勾配強度）を求めよ ただし，勾配は縦方向および横方向のソーベルフィルタで求め， 勾配強度は式12.13を用い，計算は小数点第1位を四捨五入で求めよ fx＝95, fy＝－17 （2） 勾配の最大方向は (1)～(8) の内，どれか？ ∴ g＝√｛952＋（－17）2 ｝＝ （2） 勾配の最大方向は式12.14で求めると (1)～(8) の内どれ（に近い）か？ 32 65 151 55 130 85 137 70 53 グレースケール画像 の注目画素と8近傍 注目 －45 画素 5 （1） 注目画素から各方向 への輝度勾配 (1) (2) (3) (4) 注目 画素 (5) (6) (7) d＝tan－1（fy／fx）＝tan－1（－17／95）＝－10.3度 ∴ 32 (8) （2） 勾配の最大方向 31 65 151 55 130 85 137 70 53 グレースケール画像 の注目画素と8近傍 ？ （1） 注目画素の 勾配強度 (1) (2) (3) (4) 注目 画素 (5) (6) (7) (8) （2） 勾配の最大方向 32 画像処理 6
© Copyright 2024 ExpyDoc
