ベクトルサーチ
パターンマッチング
By PipeKatoo! 2014.1.2
SURFの26近傍探索では
エッジ部ジャストの位置には来ないので
形状マッチングに使いにくく、断念しました。(私のやり方が間違っていた可能性もあるけど・・)
1.エッジ抽出の流れ
・方向 Harr-Waveret応答値
・周囲4画素
と輝度比較
・グレースケール
(カラー無効化)
・メジャー2値化
(縁取り無効化)
dx=
×
dy=
×
・パワー(=エッジ判定の行列式そのもの)
・ぼかし
(エイリアシング影響無効化)
BMP画像
エッジ候補
探索
プリフィルタ
エッジスケールS=1~(整数)・・ユーザーが指定
2S+1
2S+1
9×9pix画像圧縮 ボックスフィルタ(SURFと同じ)
×
Dyy
Dxx
Dxy
Dxx×Dyy-(0.9Dxy)2 > エッジ強度制限値 であればエッジ認定
エッジ判定
エッジ特徴
計算
エッジ集約
半径2S以内 かつ 角度90°以内
のエッジを集約
位置・向き・パワー → パワーに応じて平均化
2.モデル画像のベクトル化
無作為研究所 さんを参考 http://www.faicha.com/vision/
a~gがエッジ抽出により抽出されたエッジとすると・・
c
一番長い距離のエッジのペアは d-g
二番目は
c-e
三番目は
a-f
a
g
それぞれを基準軸として合計3個のモデルを作成する
緑点・・エッジ
赤線・・エッジの方向
オレンジが角度
青線・・基準軸
b
d
f
e
ThirdVectorModel
基準軸
SecondVectorModel
基準軸
スタートエッジ
FirstVectorModel
基準軸
スタートエッジ
エッジポイント(x,y)
スタートエッジ
エッジポイント(x,y)
向きθ
エッジポイント(xs,ys)
向きθ
エンドエッジ
向きθs
エンドエッジ
エッジポイント(x,y)
エンドエッジ
エッジポイント(x,y)
エッジポイント(xe,ye)
その他のポイントのリスト
向きθe
その他のポイントのリスト
ポイント1
その他のポイントのリスト
ポイント1
スタートエッジからの距離比
ポイント1
スタートエッジからの距離比
スタートエッジからの方向
スタートエッジからの方向
ポイント2 スタートエッジからの距離比 Dp1
スタートエッジからの方向 Ap1
ポイント2
・(上記と同じ内容)
ポイント2
ポイント3 ・(上記と同じ内容)
ポイント3
・ スタートエッジからの距離比 Dp2
・ スタートエッジからの方向 Ap2
・
・
その他のエッジの1つ
l
スタートエッジ
A
基準軸
L
エンドエッジ
距離比D=l/L
方向=A
この2つの特徴はターゲット画像が回転・縮小しても
変化しない特徴=回転・縮小にめげないマッチングに使える
2.モデル画像のベクトル化(補足)
基準軸両端エッジの画像
□4S+1の範囲の画像を保存
向きはエッジ方向が右となる向き
基準軸はマッチングにおいて間違えてはいけない重要な
ポイントなので、周囲の画像も情報として保存しておきます。
矢印はそれぞれのエッジの向き(前のページの赤線の向き)
エンドエッジ
スタートエッジ
エッジのスケールS(=1~整数)ユーザーが指定
エッジ判定は2S+1範囲の正方形にボックスフィルタを適用したが・・今回はちょっと大きめに4S+1
4S+1
基準軸
スタートエッジ
エッジポイント(xs,ys)
向きθs
画像Bs
エンドエッジ
エッジポイント(xe,ye)
向きθe
画像Be
その他のエッジのリスト
ポイント1
スタートエッジからの距離比 Dp1
スタートエッジからの方向 Ap1
ポイント2
スタートエッジからの距離比 Dp2
スタートエッジからの方向 Ap2
・
・
4S+1
ターゲットが回転してもエッジ向きをそろえて比較すれば影響なし。
比較予定のターゲットのスタートエッジ・エンドエッジ候補の画像はその時の
基準軸候補の長さ/モデルの基準軸長さ×(4S+1) で可変にすることで縮尺の影響も取り払う。
モデルサイズ×ユーザー指定の集約制限範囲内
のマッチ結果はベストスコアのみを残して、
無駄な結果を消す
3.いざパターンマッチング
可能性あり
ターゲット
BMP画像
エッジ抽出
(1P目の流れ)
全エッジペア
基準軸の
可能性調査
エッジリスト
エッジリスト抽出まではモデル画像と処理は同じ。
ターゲットに1~Nのエッジが見つかったとすると・・
基準軸候補は N×(N-1) ある。
めんどうだが・・全部調べる。
残りエッジの
マッチ調査
近隣の
マッチアイテム
集約
マッチリスト
(無駄有り)
マッチリスト
前段の基準軸チェックを見事パスしたら
残りのエッジが予測通りあるかチェックする。
もともとモデルにm個のエッジがあったとすると
すでに基準軸で2個はチェック完了してるので
残り m-2 このエッジをチェック。
L'×ユーザー指定のエッジ歪み制限の範囲
L'
S’
条件1
条件2
条件3
条件4
候補
E’
L
S
E’
モデル
E
L'/Lがユーザー指定の倍率制限以内
ベクトルS'→E'のS→Eに対するなす角がユーザー指定の検出角度制限以内
基準軸から見た両端のエッジの方向がユーザー指定のエッジ角度制限以内
両端のエッジ画像の正規化相関マッチスコアがユーザー指定のスコア閾値以上
S’
L'
条件1 モデルのエッジ情報から予期した理論的中心(黒丸)x,y から
L'×ユーザー指定のエッジ歪み制限 の範囲内にエッジがあること(赤丸)
条件2 モデルのエッジ情報から予期した理論エッジ方向(黒矢印)に対して
ユーザーが指定したエッジ角度制限以内のエッジ方向であること
条件3 現時点でのミスマッチしたエッジの個数が
(m-2)×ユーザーが指定したミスマッチ制限 以上になったら
パターンマッチ失敗として残りのエッジを調べるの中止。
スコア=マッチしたエッジ数/(m-2) × (1-マッチしたエッジの平均 ブレ/L')
4.トライ結果
・モデルは縁取りあり画像だがプリフィルタ効果により安定したエッジ検出結果
・回転、拡大、縮小されたターゲット画像中からモデルと同形状の絵を検出
・対象なモデル画像は90°や180°違いで何個か検出される
(重なって見えるが対応するポイント同士は角度分ずれたところにいるので
集約させるためには大きな集約制限値を入れる必要有り)
・複雑な写真画像とかはSURFとか他の手法に任せるとして、
エッジがはっきりしたマッチングには使えそうである(パラメータを旨く調整すれば・・だが)。
・処理時間は上記例で400ms程度・・・
(お・・遅い。動画系には使えませんね・・設備とかで1回/1サイクルならゆるされるか・・?)
ダウンロード

このパワポ