画像処理ソリューション
これを見れば画像処理の入門から基礎~応用まで全てがわかるのを目指して!
   
翻訳(Translate)

プロフィール

Akira

ニックネーム:Akira
東京都の町田事業所に勤務
画像処理ソフトの開発を行っています。リンクフリーです!
詳細プロフィールは こちら
お問い合わせは、こちら↓

【補助HP】
画像処理ソリューションWeb版 【Newブログ】
イメージングソリューション

スポンサーリンク


カテゴリ

最近のコメント

カレンダー

07 | 2017/08 | 09
S M T W T F S
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

趣味のブログ

iPhone萬歳!
iPhoneの情報いろいろ。
ブログ学習帳
ブログ、SEO、アフィリエイト情報など(まだまだこれから)
俺流クラフト日記
ハンドメイド作品の記録(現在、放置中)

スポンサーリンク 最近の記事
(09/18)  計測測定展に光切断のデモを出展しました
(08/17)  ディジタル画像技術事典200に記事が載りました
(06/09)  光切断を画像センシング展で公開
(05/14)  中国(上海)へ行って来ました
(04/12)  韓国へ行って来ました
(03/10)  私の求める新人像
(01/18)  エレクトロテストジャパンにカラー光切断法のデモを出展しました。
(12/23)  ユニークアクセス200万達成!
(12/10)  【カラー光切断法】YouTube動画まとめ
(11/04)  国際画像機器展2014にカラー光切断法を出展します。
(10/05)  第25回コンピュータビジョン勉強会@関東に参加してきました。
(09/08)  フーリエ変換の記事を追加しました。
(08/09)  【画像処理】ランキング低下中
(07/06)  記事の更新が停滞中...
(06/08)  画像センシング展2014でカラー光切断法のデモを行います。
(05/17)  カラー光切断法の動画を公開しました。
(04/30)  ソニーα NEX-5Rで星空撮影
(04/10)  カラー光切断法の取込結果を追加しました
(03/08)  Korea Vision Show 2014へ行ってきました
(02/05)  フーリエ変換シリーズを始めます。
(01/06)  2014年、あけましておめでとうございます。
(12/04)  カラー光切断法を公開(国際画像機器展2013にて)
(11/13)  国際画像機器展2013に出展します
(10/14)  「画像処理のためのC#」はじめます。
(09/16)  【C#,VB.NET】高速描画コントロールをバージョンアップしました。
(09/04)  拡大鏡に輝度値表示、ルーラー機能を追加した個人ツールを公開
(08/05)  7月の拍手Top5
(07/06)  2013年6月人気記事Top5
(05/12)  SONY α NEX-5Rレビュー
(04/24)  SONY α NEX-5RY購入

パターンマッチング(正規化相関など)

メインページ画像処理

画像の中から指定した画像(テンプレート)と似ている位置を探すことを
テンプレートマッチング
(template matching)
と言います。

パターンマッチング(テンプレートマッチング、正規化相関など)パターンマッチング(テンプレートマッチング、正規化相関など)
テンプレート画像

このとき、テンプレートと画像データがどれだけ似ているか?という評価値(類似度または相違度)にはいくつかあり、次に示すような値を用います。

以下の式において、テンプレートの輝度値の値をT(i,j)、画像の輝度値の値を(i,j)とします。
座標の(i,j)はテンプレートの幅をm画素、高さをn画素としたとき、
左上(もしくは左下)を(0,0)、右下(もしくは右上)を(m-1、n-1)とします。

SSD(Sum of Squared Difference)

SSDはテンプレートをラスタスキャンし、同じ位置の画素の輝度値の差の2乗の合計が用いられます。
SSDの値が小さいほど、似ている位置となります。
  SSD

SAD(Sum of Absolute Difference)

SADはテンプレートをラスタスキャンし、同じ位置の画素の輝度値の差の絶対値の合計が用いられます。
SADの値が小さいほど、似ている位置となります。
  SAD

正規化相互相関【NCC:Normalized Cross-Correlation】

テンプレートと画像との類似度として、以下の正規化相互相関を用いられる場合もあります。
類似度が1に近いほど、似ている位置となります。
  正規化相互相関

ちなみに、この計算式は内積の式をCosθ = の式に変形した式と同じ事にお気づきでしょうか?
上式を以下のように変形すると、M×N次元のIのベクトルとTのベクトルの内積に見えてきませんか?

正規化相互相関


正規化相互相関【ZNCC:Zero-mean Normalized Cross-Correlation】

上記NCCの相互相関係数ではテンプレートや画像の明るさが変動すると、NCCの値もふらついてしまうので、テンプレートおよび画像の輝度値の平均値をそれぞれの値から引いて計算することで、明るさの変動があっても安定的に類似度を計算することができます。
 
  正規化相互相関

ここで、この式はテンプレートの領域内の輝度値の平均値を計算してから、さらに輝度値から平均値を引くため、標準偏差の時にも説明したように、この式でそのままプログラミングすると効率の悪いプログラムとなってしまいます。
そのため、今回も同様にRZNCCの式を変形します。

テンプレートの平均輝度値およびテンプレートと同じ領域の画像の輝度値の平均は

 テンプレートの平均輝度値     画像の平均輝度値

で求まることから、この値をRZNCCの式に代入して整理すると、
 正規化相互相関

となります。
この式を用いると、プログラム的には1パスで済むでの計算効率が良くなります。
 

ΣΣ×××の部分がなんだか難しく見える方は、C言語に置き換えて
Sum = 0;
for(j = 0; j < N; j++){
     for(i = 0; i < M; i++){
           Sum += ×××;
     }
}

と置き換えて読んで下さい。


ここで説明しておきながら、最近の工業用途では、この正規化相関の方法よりもパターンの輪郭に基づき、回転やスケール変動などにも対応したマッチング(輪郭サーチ)が一般的になってきています。
最近では、さらにカメラが動いてもマッチングする三次元マッチングなども登場してきています。

正規化相関では明るさの変動にも強く優れたアルゴリズムのように聞こえるかもしれませんが、パターンが重なった場合や欠けた場合に意外と弱かったりもします。

輪郭ベースのマッチングは、ちょっと難しい(というか、理解できていない、ノウハウが無い)もので...
Loading...
スポンサーリンク

この記事に対するコメント
Re: タイトルなし
場合による。
というのが正解な気もしますが、計算の負荷を下げたくて、画像にバラつきが少ない場合にはSSDやSADを使いますが、画像の明暗がバラつく場合はZNCCを使う場合が多いと思います。
もっとも、最近はCPUが速いのでZNCCを普通に使っているように思います。
ただ、実際には画像のスケール変動があったり回転もしたりするので、そう単純ではありません。
OpenCVのようなフリーの画像処理ライブラリがある中、有償の市販のライブラリが生き残れるのも、このマッチングの性能が良いからで、実際にどのような処理をしているかは、私にも良く分かりません。
【2013/12/10 22:49】 URL | Akira #- [ 編集]


SSD SAD NCCの関係はどのような感じでしょうか?
【2013/12/10 16:02】 URL | うほ #- [ 編集]

Re: Re: テンプレートマッチングについて
回答ありがとうございます。
実は現在研究で使用するシステムの画像認識
エンジンにARToolKitが使われていまして、ロボット
の上にマーカーを乗せてロボットが動作するという
ような環境です。
なのでマーカーを真上から撮影すること前提でそこは大丈夫
かと思われます。
しかしながらロボット自体が動くので、モーションブラーが問題なのと、
色々な環境で行うので照明変動に弱い、この2つをどうにしかして
改善しようと思っています。
また、複数のマーカーを使用しますので、輪郭ベースは現状難しいかなと...
【2013/09/23 06:24】 URL | nanasi #- [ 編集]

Re: テンプレートマッチングについて
コメント頂きありがとうございます。
残念ながら、私はARも増分符号相関、統計的リーチ特徴法などを行った事がないので、
推測となってしまうのですが、ARの性格的に、マーカーを動かすでしょうし、カメラは
マーカーの真上から撮影するとは限らないので、明るさの変動よりも、回転や拡大縮小、
カメラの傾きの変動にロバストであった法が良いと思うのですが、
増分符号相関や統計的リーチ特徴法は、回転や拡大縮小、カメラの傾きに対応
できるものでしょうか??
以前、ARToolKitの開発者の加藤博一先生の講演を聞いた事があるのですが、
マーカーの検出精度は、少しいい加減と言っていました。
そのため、検出精度を上げる余地はあると思うのですが、基本的には
輪郭ベースの処理の法が良いような気もするのですが、どうでしょう。。。
【2013/09/19 21:02】 URL | Akira #- [ 編集]

テンプレートマッチングについて
いつも参考にさせて頂いております。
パターンマッチング手法についてですが、
ARToolKitのパターンマッチングについて他の手法を用いて
みたいと思っているのですが、ARToolKitの方は2つの白黒画像
の相関を取っているので明るさに強い増分符号相関や
統計的リーチ特徴法などを採用しても意味はないということ
でしょうか。
【2013/09/19 02:01】 URL | nanasi #- [ 編集]


コメント頂きありがとうございます。
RznccをR,B,Gのどれを使うか?という事ですが、これについては、プログラムを作る人が好きに決めていいと思います。
例えば、
●処理速度優先で、R,G,Bのどれか1つだけを用いる。
●カラーの影響を無視するため、モノクロに変換してから計算する。
など。
ただし、一般的にはR,G,B全てを使う場合が多いと思います。
Rznccの式の輝度値(T,I)にR,G,B,R,G,B・・・と代入していき計算します。
この時、Rznccの値はR,G,Bごとに区別する事はしません。
というのが、あくまでも一般的な話なのですが、この計算でパターンをうまく見つけられない場合は、本当にプログラムを作る人の腕の見せ所となります。
【2011/02/14 19:44】 URL | Akira #- [ 編集]


いつも参考にさせていただいております。
超素人なのですがVB2008でRZNCCの式を作成しました。文中の輝度値とはR、G、Bの値のことなのでしょうか?もし、そうでしたらR、G、Bのどの値を用いるのでしょうか?よろしくお願いします。
【2011/02/14 17:52】 URL | yyyy #- [ 編集]

Re: Re: 輪郭サーチについて
Akira様、回答ありがとうございます。
おかげさまで、概要を掴むことができました。
また質問させていただく機会があるかと思いますがよろしくお願いいたします。
【2010/10/15 12:11】 URL | HACHI #AIlHpmOk [ 編集]

Re: 輪郭サーチについて
HACHI様、コメント頂きありがとうございます。
輪郭サーチ(形状サーチ、幾何学形状サーチ)についてですが、私もあまり詳しくは無いのですが、輪郭サーチについては比較的有名なライブラリに、CognexのPatMaxというのがあります。
このPatMaxの説明なら、このへん↓
http://www.cognex.com/ExploreLearn/default.aspx?id=5728&langtype=1041&rdr=true
http://www.cognexsensors.com/VisionPro/HelpFiles/VisionPro_50/source/extfile/UsersGuide/Search.PMAlign.Theory.PatMax.html
を見て頂くと、どのような事ができるのか?雰囲気がつかめると思いますが、その処理アルゴリズムについては、各社のライブラリによって違うようです。
幾何学形状を見つける手法としては『Geometric Hashing』というのもあるのですが輪郭サーチの全てではありません。
輪郭サーチについては、OpenCVのようなフリーのライブラリがある中、有償のライブラリが存在している命のようなものですので、そう簡単にはマネできないと思います。
【2010/10/09 03:35】 URL | Akira #- [ 編集]

輪郭サーチについて
いつも参考にさせていただいてます。
本記事の最後に記載されております、「輪郭サーチ」に興味がありまして、
この単語で調べたのですが、わかりやすい情報が得られません。
わかりやすいサイト、論文、あるいは別の同意語について
教えていただけるとうれしく思います。
【2010/10/08 23:52】 URL | HACHI #kY2E5Ekw [ 編集]


この記事に対するコメントの投稿














管理者にだけ表示を許可する


この記事に対するトラックバック
トラックバックURL
→http://imagingsolution.blog107.fc2.com/tb.php/186-1716390e
この記事にトラックバックする(FC2ブログユーザー)

現在の閲覧者数: / 合計