2D相関マッチング

正規化相互相関マッチング:Normalized Cross Correlation

定義式は以下です。

例によって、実際には以下の離散バージョンで計算します。

相互相関に比べてややこしくなりました。
また、アレ?平均値で引くんじゃなかったっけ、自分が知っている式とちょっと違う、と思われるかもしれません。
それは次節で紹介するゼロ平均正規化相互相関となります。
ここでは、とりあえず正規化相互相関を説明します。

メリット

  • マッチング値が-1.0から1.0に収まる
    単純な相互相関だと、やたら大きな値になったり、画像が変わるとオーダが変わったり
    して困ります。しきい値処理をしないなら、問題ないのですが、通常はマッチング後に
    信頼性を評価するためにしきい値処理を行います。
    しきい値設定がしやすい、ということは実応用上重要です。
  • 画像の明るさがα倍になっても、同じようなマッチング結果になる
    入力画像の明るさの変動に強くなります。NCCの場合は定数倍の変動に不変です。
    オフセットの変化には不変ではありません(後述するZNCCはオフセット変化に不変)

デメリット

相互相関のように、FFTで一撃で計算、という訳にはいきません。
そこで仕方なく、実空間で計算することになりますが、かなり遅いです。
なお、FFTをうまく利用して高速化する方法は後述します。

どうして、明るさの定数倍に強いのか?

まず、画像の類似度Dを二乗誤差で考えます。これは異論がないでしょう。

ここで、入力画像をα倍してマッチングすることを考えます。

以降、簡単のためとします。

αを色々変化させて、Dが最も小さくなる時の結果を採用することにしましょう。
これは最小二乗法で求まります。その停留条件を求めます。

これより、

これを上式に代入すると、

ここではテンプレートは固定なので定数となるので、両辺をで割ります。

2項目にどこかで見た式が出てきました。これのルートを取った式が正規化相関関数となっています。
まだ、という条件より、2項目は1を超えることがありません。
(これより、2項目のルート(正規化相関)の範囲は[-1,1]となる)

マッチング例

入力画像の明るさを半分にしてマッチングを行った結果。

CC.pngNCC.png
CCNCC

検出した位置と(相関値/最大相関値との比)です。
NCCは[0.0, 1.0]の範囲にあります。
また、入力画像の明るさを変化させたのにも関わらず
相関値が最大の1.0となっています。
上の相関マップでは違いが分かりませんが
NCCの方が最大とセカンドピークの差が大きなことも分かります。

  • CC
    0:(64, 128) = 4283.7302/1.0000
    1:(64, 54) = 3769.6825/0.8800
    2:(195, 54) = 3455.5423/0.8067
  • NCC
    0:(64, 128) = 1.0000/1.0000
    1:(64, 54) = 0.8390/0.8390
    2:(37, 128) = 0.8212/0.8212

コード例

  • 例によって境界処理はしていません。
すべて開くすべて閉じる
  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
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
-
|
|
|
!
 
 
 
 
 
 
 
 
 
 
-
|
|
|
-
!
|
|
|
|
-
|
-
|
!
!
|
-
!
-
|
-
-
!
|
|
-
|
|
-
|
|
!
!
|
|
|
|
-
!
-
!
-
|
|
|
!
!
!
|
|
!
//*********************************************
// 2枚の画像間の正規化相関計算
// 戻値:最大相関値
//*********************************************
double calc_NCC(
    unsigned char *in,        //入力画像
    int w,                    //入力画像幅
    int h,                    //入力画像高
    unsigned char *tmp,        //テンプレート画像
    int tw,                    //テンプレート幅
    int th,                    //テンプレート高
    double *map,            //出力相関マップ
    int *ret_x,                //最大相関位置X
    int *ret_y                //最大相関位置Y
    )
{
    int x, y, ptr, pw, ph, sx, sy, sptr;
    double max_v = -DBL_MAX;
    double II, TT;
    // 処理範囲[0, pw]x[0, ph]
    pw = w - tw;
    ph = h - th;
 
    TT = 0.0;
    for(sptr = sy = 0; sy < th;sy++)
    {
        for(sx = 0; sx < tw;sx++, sptr++)
        {
            TT += tmp[sptr] * tmp[sptr];
        };//sx
    };//sy
 
    // (x, y)での相関値計算
    for(y = 0;y < ph;y++)
    {
        for(x = 0;x < pw;x++)
        {
            // テンプレートとの相関
            double TI = 0.0;
            II = 0.0;
            for(sptr = sy = 0; sy < th;sy++)
            {
                ptr = x + (y + sy) * w;
                for(sx = 0; sx < tw;sx++, sptr++, ptr++)
                {
                    TI += tmp[sptr] * in[ptr];
                    II += in[ptr]   * in[ptr];
                };//sx
            };//sy
            double f = II * TT;
            double v = 0.0;
            if(f != 0)
                v = (TI) / sqrt( f );
            // 相関マップ更新
            map[x + y * w] = v;
            // 最大位置を保存
            if(max_v < v)
            {
                 max_v = v;
                *ret_x = x;
                *ret_y = y;
            };
        };//x
    };//y
 
    return max_v;
};

ゼロ平均正規化相互相関マッチング:Zero-mean Normalized Cross Correlation


添付ファイル: fileNCC.png 137件 [詳細] fileCC.png 139件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-09-04 (火) 17:03:25 (716d)