Sonar Echoesを見つけるための相互相関

Question

私のサウンドの私のサウンド Chirp のエコーをAndroidののエコーを検出しようとしています。相互相関が最も適切な方法であるようです。 2つの信号は類似しており、そこから、距離に対応する相関相関アレイ内のピークを識別することができる。

私の理解から、私は以下の相互相関関数を思い付きました。これは正しいです？私はゼロを始めに追加するかどうかを確信していませんでしたか？

public double[] xcorr1(double[] recording, double[] chirp) {        
    double[] recordingZeroPadded = new double[recording.length + chirp.length];

    for (int i = recording.length; i < recording.length + chirp.length; ++i)
            recordingZeroPadded[i] = 0;

    for (int i = 0; i < recording.length; ++i)
            recordingZeroPadded[i] = recording[i];

    double[] result = new double[recording.length + chirp.length - 1];

    for (int offset = 0; offset < recordingZeroPadded.length - chirp.length; ++offset)
        for (int i = 0; i < chirp.length; ++i)
            result[offset] += chirp[i] * recordingZeroPadded[offset + i];
    return result;
}

.

二次質問：

この答え、

のように計算することもできます。

corr(a, b) = ifft(fft(a_and_zeros) * fft(b_and_zeros[reversed]))

.

私は全く理解していないが実装するのに十分な容易に思われる。私が失敗したと言ったことは（私の xcorr1 が正しいと仮定して）。私はこれを完全に誤解したような気がしますか？

public double[] xcorr2(double[] recording, double[] chirp) {
    // assume same length arguments for now
    DoubleFFT_1D fft = new DoubleFFT_1D(recording.length);
    fft.realForward(recording);
    reverse(chirp);
    fft.realForward(chirp);
    double[] result = new double[recording.length];

    for (int i = 0; i < result.length; ++i)
        result [i] = recording[i] * chirp[i];

    fft.realInverse(result, true);
    return result;
}

.

アレイに数千の要素が含まれていることを考えると、どちらの機能が最も適していますか？

編集：BTW、私はFFTバージョンの両方のアレイの両端にゼロを追加しようとしました。

---

Sleutheyeの応答後の編集：

私は「実際の」データを扱っているので、実際の変換を行うことによって計算の半分だけをする必要があることを確認するだけです。

あなたのコードから、実変換によって返された配列内の奇数番号の要素が想像上のように見えます。ここで何が起こっているの？

私はどのように私は実数の配列から複雑になるのですか？またはこれは変換の目的です。実数を複雑なドメインに移動するには？ （しかし、実数は複雑な数字のサブセットだけであり、彼らはすでにこのドメインにいませんか？）

実際に想像上/複雑な数字を返すのである場合、それは複雑な方法とどのように異なりますか？そしてどのように結果を解釈するのですか？複素数の大きさは？

私は変革に関して私の理解の欠如をお詫び申し上げます、私はこれまでのフーリエシリーズを研究しただけです。

コードをありがとう。これが「私の」作業実装です：

public double[] xcorr2(double[] recording, double[] chirp) {
    // pad to power of 2 for optimisation
    int y = 1;
    while (Math.pow(2,y) < recording.length + chirp.length)
        ++y;
    int paddedLength = (int)Math.pow(2,y);

    double[] paddedRecording = new double[paddedLength];
    double[] paddedChirp = new double[paddedLength];

    for (int i = 0; i < recording.length; ++i)
            paddedRecording[i] = recording[i];

    for (int i = recording.length; i < paddedLength; ++i)
            paddedRecording[i] = 0;

    for (int i = 0; i < chirp.length; ++i)
            paddedChirp[i] = chirp[i];

    for (int i = chirp.length; i < paddedLength; ++i)
            paddedChirp[i] = 0;

    reverse(chirp);
    DoubleFFT_1D fft = new DoubleFFT_1D(paddedLength);
    fft.realForward(paddedRecording);
    fft.realForward(paddedChirp);
    double[] result = new double[paddedLength];

    result[0] = paddedRecording[0] * paddedChirp[0]; // value at f=0Hz is real-valued
    result[1] = paddedRecording[1] * paddedChirp[1]; // value at f=fs/2 is real-valued and packed at index 1
    for (int i = 1; i < result.length / 2; ++i) {
        double a = paddedRecording[2*i];
        double b = paddedRecording[2*i + 1];
        double c = paddedChirp[2*i];
        double d = paddedChirp[2*i + 1];

        // (a+b*j)*(c-d*j) = (a*c+b*d) + (b*c-a*d)*j
        result[2*i]     = a*c + b*d;
        result[2*i + 1] = b*c - a*d;
    }

    fft.realInverse(result, true);

    // discard trailing zeros
    double[] result2 = new double[recording.length + chirp.length - 1];
    for (int i = 0; i < result2.length; ++i)
        result2[i] = result[i];

    return result2;
}

.

しかし、それぞれ約5000個の要素まで、XCORR1が速いようです。私は特に遅いものをやっていますか（おそらく、記憶の絶え間ない新しい '新たなもの - 私はアレイリストにキャストする必要があります）？または私がそれらをテストするためにアレイを生成した任意の方法？またはそれを逆にする代わりに共役をするべきですか？そうは言っても、パフォーマンスは実際には問題ではありませんので、あなたが指摘した最適化を妨げるものがない限り、あなたが最適化を妨げる必要がない限り、

Answer 1

xcorr1の実装は、相互相関の標準信号処理定義に対応しています。

始めにゼロの追加に関する質問に対する尋問：chirp.length-1ゼロの追加結果の索引0は送信開始に対応します。ただし、相関出力のピークは、エコーの開始後にchirp.length-1サンプルを発生します（Chirpはフルレジエコーと整列している必要があります）。ピークインデックスを使用してエコー遅延を取得するには、遅延を差し引くことによって、または最初のchirp.length-1出力結果を破棄することによって、その相関器遅延に対して調整する必要があります。追加のゼロが最初に多くの余分な出力に対応することに注目して、あなたはおそらく最初の場所でこれらのゼロを追加しないのではないでしょう。

xcorr2の場合、いくつかのことを対処する必要があります。まず、recordingおよびchirp入力がまだ少なくともCHIRP +記録データ長さにゼロパッドされていない場合は、（パフォーマンス上の理由から2つの長さの2つの長さまで）などを実行する必要があります。あなたが知っているように、それらは両方とも同じ長さに埋められる必要があります。

秒、に示されている乗算が登録されていないことを考慮に入れなかった。複雑な乗算への事実（DoubleFFT_1D.realForward APIは2倍を使用します）。 ChirpのFFTとの複雑な乗算などの何かを実装する場合は、実際にChirpのFFTの複素共役（ reference応答）、時間領域値を逆にする必要がなくなります。

DoubleFFT_1D.realForwardの梱包注文についても、偶数の変換のための注文になります。

// [...]
fft.realForward(paddedRecording);
fft.realForward(paddedChirp);

result[0] = paddedRecording[0]*paddedChirp[0]; // value at f=0Hz is real-valued
result[1] = paddedRecording[1]*paddedChirp[1]; // value at f=fs/2 is real-valued and packed at index 1
for (int i = 1; i < result.length/2; ++i) {
    double a = paddedRecording[2*i];
    double b = paddedRecording[2*i+1];
    double c = paddedChirp[2*i];
    double d = paddedChirp[2*i+1];

    // (a+b*j)*(c-d*j) = (a*c+b*d) + (b*c-a*d)*j
    result[2*i]   = a*c + b*d;
    result[2*i+1] = b*c - a*d;
}
fft.realInverse(result, true);
// [...]

.

resultアレイは、paddedRecordingとpaddedChirpと同じサイズであるため、最初のrecording.length+chirp.length-1だけを保持する必要があります。

最後に、どの関数が数千の要素の配列に最も適しているかと比較して、FFTバージョンのxcorr2ははるかに速くなる可能性があります（配列の長さを2の電力に制限すると）。

Answer 2

直接バージョンは最初にゼロパディングを必要としません。長さMの長さNとChirpを録音し、長さN+M-1の結果を計算します。手で小さな例を使って手順をつかむ：

recording = [1, 2, 3]
chirp = [4, 5]

  1 2 3
4 5

  1 2 3
  4 5

  1 2 3
    4 5

  1 2 3
      4 5


result = [1*5, 1*4 + 2*5, 2*4 + 3*5, 3*4] = [5, 14, 23, 4]

.

長いアレイがある場合、FFT方式ははるかに高速です。この場合、両方の入力アレイがFFTを取得する前に同じサイズであるように、サイズM + N-1への各入力をゼロパッドする必要があります。

また、FFT出力は複素数であるため、複素乗算を使用する必要があります。 。 （1 + 2J）*（3 + 4J）は-5 + 10J、3 + 8Jです。私はあなたの複雑な数字がどのように手配されるかまたは処理されるのかわかりませんが、これが正しいことを確認してください。

またはこれは変換の目的です。実数を複雑なドメインに移動するには？

いいえ、フーリエ変換は時間領域から周波数領域へ変換されます。時間領域データは、実数または複素数のいずれかであり、周波数領域データは実数または複雑であり得る。ほとんどの場合、複雑なスペクトルの実際のデータがあります。あなたはフーリエ変換を読む必要があります。

実際に想像上/複雑な数字を返すのである場合、それは複雑な方法とどのように異なりますか？

実際のFFTは、複雑なFFTが複素入力を取ります。どちらの変換も、複素数を出力として生成します。それがDFTのことです。 DFTが実際の出力を生成する唯一の時間は、入力データが対称的な場合（その場合はDCTを使用してさらに時間を節約できます）。