ディジタル信号処理において相互相関関数を利用して二つの信号の類似度を測定する方法があると思うのですが、相関関数の数学的原理や基本などが参照できる文献、書籍、URLを提示していただけると助かります。特にディジタル画像処理の分野と関連した内容を希望しています。二つの画像の類似度を測定するのに使用されていると思うのですが、相互相関関数とはどの様な計算なのか、計算する事によってどの様に値が得られるのか、また得られた値は何を意味するのか、このへんの事が詳しく参照できると助かります。また高速フーリエ変換を使用する方法もあると思うのでそちらも合わせてお願いいたします。よろしくお願いいたします。

回答の条件
  • 1人3回まで
  • 登録:2007/11/26 13:23:31
  • 終了:2007/11/29 20:31:06

ベストアンサー

id:ita No.1

ita回答回数204ベストアンサー獲得回数482007/11/26 22:16:40

ポイント100pt

あまり入門的な記事を見つけられなかったんで1から書いてみます。

同じ歌を録音した二つの音声ファイルがあり、中身が同じ歌だと示したいとします。

単に波形を比べるだけだと、ボリュームが違ったり録音開始時刻が違ったりするので同じかどうか分かりません。ボリュームについては最大値と最小値が同じ程度になるように一方を何倍かすればいいですが、時刻のずれはどうすればいいでしょうか。

一つの方法として、データをm個だけずらして比較してみて、あらゆるmについて手当たり次第に調べれば、どれか一つでよく一致するはずです。

似ている度合いを調べるには、データをずらして平均を0にするといいです。そうしてずらしたデータ列をA0,A1,A2,...とB0,B1,B2,...とします。似ている度合いは

S0=A0*B0+A1*B1+A2*B2+...で評価できます。Aが大きい値のときBも同じ符号で大きい値であればS0は大きくなり、無関係ならば0になります。m個ずらした場合は、

Sm=A0*Bm+A1*B(m+1)+...となります。

さて、いろんなmについてしらみつぶしに調べるのが面倒だ、という場合、簡単に計算する方法もあります。それはSmの二乗を全てのmについて合計したもの

X=\sum_m S_m^2を計算すると、どれかのmで「当たり」がある場合、この合計も大きくなることから判別できます。この合計XはSmより一見計算が大変そうに見えますが、FFTを使うと簡単に計算できます。AとBをFFTを使って変換したものをC(k), D(k)とおきます。するとX=\sum_k C(k)D(-k)と、一重ループで計算できます。

以上は音声データの場合ですが、画像の場合は同様に原点を左右と上下方向にズラして一致を探すことになります。基本的には同じ計算です。

id:jsakato

ご回答ありがとうございます。1次元信号をわかりやすく説明していただいたため、2次元信号である画像においてもイメージできました。相関関数の計算にFFTを使用する場合はサンプルとするデータ数がやはり2の累乗である事が前提なのでしょうか?画像で言うと128*128や256*256の様に縦横同じ画素数(データ数)でかつ2の累乗で無いとFFTでは計算できないと言うことになりますか?

2007/11/27 17:00:59

その他の回答(3件)

id:ita No.1

ita回答回数204ベストアンサー獲得回数482007/11/26 22:16:40ここでベストアンサー

ポイント100pt

あまり入門的な記事を見つけられなかったんで1から書いてみます。

同じ歌を録音した二つの音声ファイルがあり、中身が同じ歌だと示したいとします。

単に波形を比べるだけだと、ボリュームが違ったり録音開始時刻が違ったりするので同じかどうか分かりません。ボリュームについては最大値と最小値が同じ程度になるように一方を何倍かすればいいですが、時刻のずれはどうすればいいでしょうか。

一つの方法として、データをm個だけずらして比較してみて、あらゆるmについて手当たり次第に調べれば、どれか一つでよく一致するはずです。

似ている度合いを調べるには、データをずらして平均を0にするといいです。そうしてずらしたデータ列をA0,A1,A2,...とB0,B1,B2,...とします。似ている度合いは

S0=A0*B0+A1*B1+A2*B2+...で評価できます。Aが大きい値のときBも同じ符号で大きい値であればS0は大きくなり、無関係ならば0になります。m個ずらした場合は、

Sm=A0*Bm+A1*B(m+1)+...となります。

さて、いろんなmについてしらみつぶしに調べるのが面倒だ、という場合、簡単に計算する方法もあります。それはSmの二乗を全てのmについて合計したもの

X=\sum_m S_m^2を計算すると、どれかのmで「当たり」がある場合、この合計も大きくなることから判別できます。この合計XはSmより一見計算が大変そうに見えますが、FFTを使うと簡単に計算できます。AとBをFFTを使って変換したものをC(k), D(k)とおきます。するとX=\sum_k C(k)D(-k)と、一重ループで計算できます。

以上は音声データの場合ですが、画像の場合は同様に原点を左右と上下方向にズラして一致を探すことになります。基本的には同じ計算です。

id:jsakato

ご回答ありがとうございます。1次元信号をわかりやすく説明していただいたため、2次元信号である画像においてもイメージできました。相関関数の計算にFFTを使用する場合はサンプルとするデータ数がやはり2の累乗である事が前提なのでしょうか?画像で言うと128*128や256*256の様に縦横同じ画素数(データ数)でかつ2の累乗で無いとFFTでは計算できないと言うことになりますか?

2007/11/27 17:00:59
id:saulavion No.2

saulavion回答回数2ベストアンサー獲得回数02007/11/26 22:06:21

ポイント40pt

相関関数に関する基本原理が物理のかぎしっぽに載っていますので参考になるかと思います。

id:ita No.4

ita回答回数204ベストアンサー獲得回数482007/11/27 17:25:20

できれば回答中もコメント書き込み可にしていただけるといいんですが、、、

1への補足です。この解答にポイントはいりません。

X=\sum_k C(k)D(-k)と書きましたが間違いでX=\sum_k C(k)D(k)C(-k)D(-k)でした。

それと、FFTは二べきでなくても使えるはずです。二べきの方が速いですが。多くの数に素因数分解できるほうが速いです。なので256*3とかでも十分速いはずです。

また縦横のサイズは違ってもかまいません。横をLx,縦をLyとすると計算すべき量は

C(k_x,k_y)=\frac{1}{L_x L_y}\sum_{x,y}A(x,y)\exp(2\pi k_x x/L_x +2\pi k_y y/L_y), |kx|<=Lx/2, |ky|<=Ly/2 となります。

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません