عبر ارتباط تجد أصداء السونار

Question

أحاول الكشف عن أصداء من غرد في الصوت تسجيل على الروبوت ويبدو عبر الارتباط هو أنسب طريقة لإيجاد حيث FFTs من اثنين من إشارات متشابهة و من هناك أنا يمكن تحديد القمم في الصليب ترتبط مجموعة والتي سوف تتوافق مع المسافات.

من فهمي ، وقد تأتي مع التالية عبر ارتباط وظيفة.هل هذا صحيح ؟ لم أكن متأكدا ما إذا كنت تريد إضافة أصفار إلى البداية كما والبدء في عدد قليل من العناصر مرة أخرى ؟

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;
}

على افتراض حصلت كل من العامل ، والتي تعمل سيكون أنسب بالنظر إلى أن المصفوفات سوف تحتوي على بضعة آلاف من العناصر ؟

تحرير:راجع للشغل, لقد حاولت إضافة أصفار إلى طرفي كل من المصفوفات الاتحاد الفرنسي للتنس الإصدار.

---

تحرير بعد SleuthEye رد:

يمكنك فقط التحقق من ذلك, لأنني التعامل مع "الحقيقة" البيانات, أريد فقط نصف الحسابية (الحقيقي أجزاء) بفعل حقيقي تحويل ؟

من التعليمات البرمجية الخاصة بك ، يبدو كما لو الغريب المرقمة العناصر في الصفيف عاد الحقيقية تحويل وهمية.ما الذي يجري هنا ؟

كيف أنا ذاهب من مجموعة من الأعداد الحقيقية إلى المجمع ؟ أو هل هذا هو الغرض من تحويل ؛ لنقل الأرقام الحقيقية في مجمع المجال ؟ (ولكن الأعداد الحقيقية هي مجموعة فرعية فقط من أرقام معقدة و حتى لا يكون بالفعل في هذا المجال؟)

إذا realForward هو في الواقع العودة وهمي/الأرقام المعقدة ، كيف تختلف إلى complexForward?و كيف تفسر النتائج ؟ حجم المعقدة ؟

أعتذر عن قلة فهم فيما يتعلق يحول لدي فقط حتى الآن درس سلسلة فوريير.

شكرا على المدونة.هنا هو بلدي' العامل التنفيذ:

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 يبدو أن تكون أسرع.أفعل أي شيء بطيئة خاصة (ربما ثابت 'الجديدة التعرف من الذاكرة-ربما يجب أن يلقي إلى ArrayList)?أو التعسفي الطريقة التي ولدت المصفوفات لاختبار لهم ؟ أو هل تقارن بدلا من عكس ذلك ؟ وقال أن الأداء ليس حقا مشكلة بذلك ما لم يكن هناك شيء واضح انك لا تحتاج الى عناء مشيرا إلى أمثلية.

Answer 1

الخاص بك تنفيذ xcorr1 لا تتوافق مع معيار إشارة تجهيز تعريف عبر الارتباط.

نسبة إلى التحقيق فيما يتعلق إضافة الأصفار في البداية:إضافة chirp.length-1 الأصفار من شأنه أن يجعل مؤشر 0 النتيجة تتوافق مع بدء الإرسال.نلاحظ أن ذروة العلاقة يحدث الانتاج chirp.length-1 عينات بعد بدء يردد (غرد يجب أن تكون متوائمة مع كامل تلقى صدى).باستخدام ذروة مؤشر للحصول على صدى التأخير ، ثم سيكون لديك لضبط أن الترابطات التأخير إما من خلال طرح التأخير أو عن طريق التخلص من أول chirp.length-1 إخراج النتائج.مشيرا إلى أن أصفار إضافية تتوافق مع العديد من نواتج إضافية في البداية كنت ربما يكون من الأفضل عدم إضافة تلك الأصفار في البداية في المقام الأول.

بالنسبة xcorr2 ولكن عدد قليل من الأشياء التي تحتاج إلى معالجة.أولا إذا كان recording و chirp المدخلات هي بالفعل صفر-مبطن على الأقل غرد+تسجيل البيانات طول كنت بحاجة إلى القيام بذلك (ويفضل أن قوة 2 طول لأسباب الأداء).كما تعلمون أنها سوف تحتاج إلى أن تكون مبطنة إلى طول نفس.

ثانيا ، لم تأخذ في الاعتبار أن الضرب هو مبين في نشر الجواب إشارة, تتوافق في الواقع معقدة الضرب (في حين DoubleFFT_1D.realForward API يستخدم الزوجي).الآن إذا كنت تنوي تنفيذ شيء مثل مجمع الضرب مع غرد هذا الاتحاد الفرنسي للتنس, ربما كنت كذلك في الواقع تنفيذ الضرب المعقدة المتقارن من غرد هذا الاتحاد الفرنسي للتنس (البديل التنفيذ المبينة في الجواب إشارة) ، وإزالة الحاجة إلى عكس ذلك الوقت-مجال القيم.

كما يمثل 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 وحساب نتيجة طول 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]

الاتحاد الفرنسي للتنس طريقة أسرع بكثير إذا كان لديك طويلة المصفوفات.في هذه الحالة عليك أن صفر-pad كل المدخلات إلى حجم M+N-1 حيث أن كل من المدخلات المصفوفات هي نفس الحجم قبل أخذ الاتحاد الفرنسي للتنس.

أيضا, الاتحاد الفرنسي للتنس إخراج الأعداد المركبة ، لذلك تحتاج إلى استخدام مجمع الضرب.(1+2j)*(3+4j) هو -5+10j ، وليس 3+8ي.أنا لا أعرف كيف الأعداد المركبة يتم ترتيب أو التعامل معها ، ولكن تأكد من أن هذا هو الحق.

أو هل هذا هو الغرض من تحويل ؛ لنقل الأرقام الحقيقية في مجمع المجال ؟

لا, تحويل فورييه تحول من مجال إلى مجال التردد.المجال الزمني البيانات يمكن أن تكون إما حقيقية أو معقدة ، و تردد المجال البيانات يمكن أن تكون إما حقيقية أو معقدة.في معظم الحالات يكون لديك بيانات حقيقية مع مجمع الطيف.تحتاج إلى قراءة على تحويل فورييه.

إذا realForward هو في الواقع العودة وهمي/الأرقام المعقدة ، كيف تختلف إلى complexForward?

الحقيقية الاتحاد الفرنسي للتنس يأخذ الحقيقي المدخلات, في حين مجمع الاتحاد الفرنسي للتنس يأخذ معقدة المدخلات.كل من يحول إنتاج مجمع الأرقام كما الانتاج.هذا ما DFT لا.المرة الوحيدة DFT تنتج الناتج الحقيقي هو إذا كان إدخال البيانات متناظرة (في هذه الحالة يمكنك استخدام DCT لتوفير المزيد من الوقت).