15

基本的にJavaでテンプレートマッチングを行おうとしています。一致するものを見つけるために簡単なアルゴリズムを使用しました。コードは次のとおりです。

minSAD = VALUE_MAX;
// loop through the search image
for ( int x = 0; x <= S_rows - T_rows; x++ ) {
    for ( int y = 0; y <= S_cols - T_cols; y++ ) {
        SAD = 0.0;

        // loop through the template image
        for ( int i = 0; i < T_rows; i++ )
            for ( int j = 0; j < T_cols; j++ ) {

                pixel p_SearchIMG = S[x+i][y+j];

                pixel p_TemplateIMG = T[i][j];

                SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
            }
    }

    // save the best found position 
    if ( minSAD > SAD ) {
        minSAD = SAD;
        // give me VALUE_MAX
        position.bestRow = x;
        position.bestCol = y;
        position.bestSAD = SAD;
    }
}

しかし、これは非常に遅いアプローチです。2つの画像（768×1280）とサブ画像（384 x 640）をテストしました。これは何年も続きます。openCVは、ready関数cvMatchTemplate（）を使用して、テンプレートマッチングをはるかに高速に実行しますか、それとも実行しませんか？

4

1 に答える 1

45

openCV cvMatchTemplate（）は、実装したメソッドよりもはるかに高速です。作成したのは、統計的なテンプレートマッチングメソッドです。これは最も一般的で実装が最も簡単ですが、大きな画像では非常に遅くなります。基本的な計算を見てみましょう。768x1280の画像は、これらの各ピクセルからエッジを引いたものをループします。これは、テンプレートの制限であるため、（768-384）x（1280-640）であり、384 x 640 = 245 'テンプレートの各ピクセルをループする760の操作（別の245'760の操作）。したがって、ループに数学を追加する前に、すでに（245'760 x 245'760）60'397'977'600の操作があります。画像をループするためだけに600億を超える操作が行われるマシンがこれをどれほど迅速に実行できるかは、さらに驚くべきことです。

ただし、その245'760 x（245'760 x数学演算）を覚えておいてください。そのため、さらに多くの演算があります。

これで、cvMatchTemplate（）は実際にフーリエ解析テンプレートマッチング操作を使用します。これは、強度のピクセル変化を構成する信号が対応する各波形にセグメント化されている画像に高速フーリエ変換（FFT ）を適用することによって機能します。この方法をうまく説明するのは難しいですが、画像は複素数の信号表現に変換されます。詳細を理解したい場合は、ゴーグルで高速フーリエ変換を検索してください。これで、同じ操作がテンプレートで実行されます。テンプレートを形成する信号は、画像から他の信号を除外するために使用されます。

単純に、テンプレートと同じ機能を持たない画像内のすべての機能を抑制します。次に、画像は逆高速フーリエ変換を使用して変換され、高い値は一致を意味し、低い値は反対を意味する画像を生成します。この画像は正規化されていることが多いため、1は一致を表し、0またはそこはオブジェクトが近くにないことを意味します。

ただし、オブジェクトが画像になく、正規化されている場合は、計算された最大値が一致として扱われるため、誤検出が発生することに注意してください。私はこの方法がどのように機能するか、そしてその利点や起こりうる問題について何年も続けることができましたが...

このメソッドが非常に高速である理由は次のとおりです。1）opencvは高度に最適化されたc++コードです。2）fft関数は、大多数がハードウェアでこの操作を実行する機能を備えているため、プロセッサが簡単に処理できます。GPUグラフィックカードは、毎秒数百万のfft操作を実行するように設計されています。これらの計算は、高性能のゲームグラフィックスやビデオエンコーディングでも同様に重要です。3）必要な操作の量ははるかに少ないです。

夏季の統計テンプレートマッチング方法は遅く、時間がかかりますが、opencv FFTまたはcvMatchTemplate（）は高速で、高度に最適化されています。

オブジェクトが存在しない場合、統計的テンプレートマッチングはエラーを生成しませんが、opencv FFTは、そのアプリケーションに注意が払われない限りエラーを生成します。

これがあなたに基本的な理解を与え、あなたの質問に答えることを願っています。

乾杯

クリス

[編集]

あなたの質問にさらに答えるには：

やあ、

cvMatchTemplateは、CCOEFF_NORMED、CCORR_NORMED、およびこれらの非正規化バージョンを含むSQDIFF_NORMEDで動作します。ここに、期待できる結果の種類を示し、操作するコードを示します。

http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html#Step%202

3つの方法はよく引用されており、多くの論文がGoogleの学者から入手できます。以下にいくつかの論文を提供しました。それぞれが異なる方程式を使用して、テンプレートを形成するFFT信号と、画像内に存在するFFT信号との間の相関を見つけます。相関係数は、私の経験でより良い結果をもたらす傾向があり、参照を見つけるのが簡単です。二乗の差の合計は、同等の結果で使用できるもう1つの方法です。私はこれらの助けのいくつかを願っています：

欠陥検出のための高速正規化相互相関 Du-MingTsai; Chien-Ta Lin; パターン認識レター第24巻、第15号、2003年11月、2625-2631ページ

高速正規化相互相関KaiBriechleを使用したテンプレートマッチング。Uwe D. Hanebeck;

2次元スペックルトラッキング手法の相対的なパフォーマンス：正規化された相関、正規化されていない相関、および絶対差の合計 Friemel、BH; ボヘミアン、LN; トラヘイ、GE; 超音波シンポジウム、1995年。議事録、1995年IEEE

高速デジタル画像レジストレーションのためのアルゴリズムのクラス Barnea、Daniel I .; シルバーマン、ハーベイF .;
コンピュータ、1972年2月のIEEEトランザクション

1に等しいものはすべて一致するため、これらのメソッドの正規化バージョンを使用することをお勧めしますが、オブジェクトが存在しない場合は誤検知が発生する可能性があります。この方法は、コンピューター言語で開始される方法のために、高速に機能します。関連する操作は、プロセッサアーキテクチャにとって理想的です。つまり、メモリと情報を数クロックサイクルにわたってシフトするのではなく、数クロックサイクルで各操作を完了することができます。プロセッサは長年にわたってFFTの問題を解決してきましたが、私が言ったように、そうするためのハードウェアが組み込まれています。ハードウェアベースは常にソフトウェアよりも高速であり、テンプレートマッチングの統計的手法は基本的なソフトウェアベースです。ハードウェアの良い読み物はここで見つけることができます：

デジタルシグナルプロセッサ Wikiページは一見の価値がありますが、これはFFT計算を実行するハードウェアです。

パイプラインFFTプロセッサへの新しいアプローチ ShoushengHe; マット・トーケルソン; プロセッサ内で何が起こっているかを示しているので、私のお気に入り

効率的なローカルパイプライン化されたFFTプロセッサ LiangYang; Kewei Zhang; Hongxia Liu; ジンファン; Shitan Huang;

これらの論文は、FFTを実装した場合の複雑さを実際に示していますが、プロセスのパイプライニングにより、数クロックサイクルで操作を実行できます。これが、リアルタイムビジョンベースのシステムがFPGA（特に、設定されたタスクを実装するために設計できる設計プロセッサ）を利用する理由です。これは、アーキテクチャ内で非常に並列に設計でき、パイプライニングの実装が容易だからです。

画像のFFTには、実際には水平プレーンのFFTと垂直プレーンのFFTであるFFT2を使用しているため、参照時に混乱が生じることはありません。方程式の実装方法とFFTの実装方法について専門知識があるとは言えませんが、良いガイドを見つけようとしましたが、良いガイドを見つけるのは非常に難しいので、まだ見つけていません（少しでも）。いつか私はそれらを理解するかもしれませんが、私はそれらがどのように機能するか、そして期待できる結果の種類をよく理解しています。

これ以外に、独自のバージョンを実装したり、それがどのように機能するかを理解したい場合は、これ以上お役に立てませんが、opencvコードは非常に最適化されているため、パフォーマンスを向上させるのに苦労します。あなたがより良い結果を得る方法を見つけ出すかもしれないことを知っています

クリス

于 2011-08-31T08:43:17.373 に答える