パターン検出とマッチングのお勉強（１０）

参考：Archives

やりたいこと

パターン検出とマッチングについて学ぶ

教科書

CG-ARTS | 書籍・教材

テンプレートマッチング

テンプレートマッチング：予め標準パターンをテンプレートとして用意しておき、このテンプレートを用いて入力画像とのマッチングを行う

位置を検出することもでき、探索範囲に対して類似度を調べ、その中から最も類似する位置を検出する

類似度

類似度を調べるには以下の２つがよく利用される

1. SSD: 差の二乗和。ユークリッド距離の二乗。

2. SAD: 差の絶対値和。市街地距離。

また、以下が使われることもある。

1. NCC: 正規化相互相関。ベクトルのなす角の余弦。

2. ZNCC: 相互相関係数。

サブピクセル位置推定

サブピクセル位置推定：対応点の座標の小数値を推定する技術(サブピクセル推定)

参考： 機械の目が見たセカイ -コンピュータビジョンがつくるミライ(9) カメラを用いた3次元計測(3) - サブピクセル推定 | マイナビニュース

高速探索法

探索範囲すべての位置での類似度の計算（全探索）は計算時間が多くかかることがある。

以下に効率化手法を示す。

残差逐次検定法

残差があるしきい値を超えたら、検出位置ではないとし、次の位置での計算にうつる方法

しきい値は自動的に決める方法があり、最初はしきい値を決めず計算し、それを最初のしきい値とし、次々計算していく中でそのしきい値を超えない場合、その値をしきい値に変更する。

こうすることで、常に真の最小値に到達することが保証されている。

疎密探索法

画像情報を何段階化の解像度で表現し、解像度の疎密性を利用することで、類似度や相違度の最大値位置や最小値位置を効率的に探索することができる。

イメージピラミッドを作り、低解像度から探索を行い、探索された位置に対して高解像度画像に上げていき探索を行う。こうすることで高速に探索できる。

参考：画像認識 第４章-物体追跡:Object Tracking- - とある学生のお勉強日記

参照画素の選択による高速化

同時生起行列の確率を計算し、確率が低い（独自性が高い）画素を類似度計算に用いる参照画素とする。

こうすることで、もし選択された画素が1%であれば、100倍高速化される。

エッジ情報を用いたチャンファーマッチング

テンプレートマッチングの一種であり、入力画像とテンプレート画像間のエッジ相違度に基づいて探索を行う手法

参考： Archives

ヒスログラム情報を用いたアクティブ探索

カラーヒストグラム

カラー空間を量子化した際の各色番号に対する類度を表したもの

類似度の算出は以下の２つがある。

1. ヒストグラムインタセクション

   

   参考：http://web.tuat.ac.jp/~s-hotta/gke/ch4/index.html

2. バタチャリヤ係数

   

   参考：

   局所特徴量と統計学習手法による物体検出 from MPRG_Chubu_University
   www.slideshare.net

アクティブ探索

テンプレートと入力画像上のある領域のカラーヒストグラムの類似度が低ければ、周辺の重なりを持つ領域の類似度も低いという考え方を利用して、周辺領域の類似度計算を省く

コーナー検出全体まとめ

参考： qiita.com

ハリスのコーナー検出

参考：

• MIRU2013チュートリアル：SIFTとそれ以降のアプローチ from Hironobu Fujiyoshi
  www.slideshare.net

• Harrisコーナー検出 — OpenCV-Python Tutorials 1 documentation

FASTによるコーナー検出

決定木をトラバーサル（横切る）するだけでコーナーを検出できる

参考：

• MIRU2013チュートリアル：SIFTとそれ以降のアプローチ from Hironobu Fujiyoshi
  www.slideshare.net

• コーナー検出のためのFASTアルゴリズム — OpenCV-Python Tutorials

DoG画像を用いた特徴点とスケールの検出

画像間の拡大縮小に関係なく、対応点を決めることができる

参考：

• MIRU2013チュートリアル：SIFTとそれ以降のアプローチ from Hironobu Fujiyoshi
  www.slideshare.net

• コンピュータビジョンのセカイ - 今そこにあるミライ(40) iPhoneアプリ「漫画カメラ」で使われている画像処理手法その1 | マイナビニュース

Cannyのエッジ検出アルゴリズム

アルゴリズム：Canny法によるエッジ検出 — OpenCV-Python Tutorials 1 documentation

参考：

• Canny法によるエッジ検出 — OpenCV-Python Tutorials 1 documentation

• 【画像処理】Cannyエッジ検出器の原理・特徴・計算式 | アルゴリズム雑記

SIFT

スケールと回転に不変な特徴記述

参考：

• MIRU2013チュートリアル：SIFTとそれ以降のアプローチ

• SIFT (Scale-Invariant Feature Transform, スケール不変の特徴変換)の紹介 — OpenCV-Python Tutorials

• https://www.codeproject.com/Articles/619039/Bag-of-Features-Descriptor-on-SIFT-Features-with-O

２値特徴量

BRIEF: BRIEF (Binary Robust Independent Elementary Features, 二値頑健独立基本特徴) — OpenCV-Python Tutorials

ORB: ORB (Oriented FAST and Rotated BRIEF, 方向付きFASTと回転BRIEF) — OpenCV-Python Tutorials 1 documentation

対応点マッチング

参考： MIRU2013チュートリアル：SIFTとそれ以降のアプローチ

図形要素検出

ハフ変換

参考：

• Hough変換による画像からの直線や円の検出：CodeZine（コードジン）

• ハフ変換による直線検出 — OpenCV-Python Tutorials 1 documentation

一般化ハフ変換

• http://www.wakayama-u.ac.jp/~wuhy/CV/CV2011/CV06.pdf

ランダム化ハフ変換

• Randomized Hough Transform (Artificial Intelligence)

特徴統合性理論

• 特徴統合理論とは - Weblio辞書

顕著性マップ

参考： コンピュータビジョンのセカイ - 今そこにあるミライ(44) 自動作成を行うために用いられることの多い3つの重要度マップ手法 | マイナビニュース

所感

ロボットの認識器を作る上でとても大事な章だと思う。なかなか難しいところもある。。。

顕著性マップなど人間の視覚システムに基づいて考えられている理論は面白い。