Ist Upsampling vor Kreuzkorrelation nutzlos?

12

Man betrachte einen einfachen Fall, in dem zwei Signale von zwei verschiedenen Sensoren kreuzkorreliert werden und die Ankunftszeit aus der Absisse des Peaks ihrer Kreuzkorrelationsfunktion berechnet wird.

Nehmen wir nun weiter an, dass aufgrund der Dimensionalitätsbeschränkungen beider Antennen und der Beschränkungen der maximal möglichen Abtastrate die maximal erreichbare Verzögerung , was 10 Abtastungen entspricht.D

Das Problem:

Aufgrund dieser Einschränkungen kann Ihre berechnete Verzögerung von einem beliebigen ganzzahligen Wert zwischen 0 und 10 Samples abweichen, dh : . Dies ist problematisch, da ich wirklich eine Teilverzögerungsdiskriminierung der Verzögerung zwischen den beiden auf meine Antennen auftreffenden Signalen möchte und eine Änderung der Abmessungen oder der Abtastrate keine Option ist.0D10

Einige Gedanken:

  • In diesem Fall denke ich zunächst an ein Upsampling der Signale, bevor eine Kreuzkorrelation durchgeführt wird. Allerdings denke ich, dass dies irgendwie "betrügt", weil ich dem System keine neuen Informationen hinzufüge.

  • Ich verstehe nicht, wie Upsampling in gewissem Sinne nicht "betrügt". Ja, wir rekonstruieren unser Signal auf der Grundlage der aktuell beobachteten Frequenzinformationen. Wie lässt sich jedoch feststellen, wo ein Signal tatsächlich zwischen und D = 8 begonnen hat ? Wo war diese Information im ursprünglichen Signal enthalten, die feststellte, dass der wahre Bruchverzögerungsstart des Signals tatsächlich bei D = 7,751 lag ?D=7D=8D=7.751

Die Fragen):

  • Betrügt das wirklich?

    • Wenn nicht, woher kommt diese neue 'Information'?
    • Wenn ja, welche anderen Optionen stehen zur Schätzung von Teilverzögerungszeiten zur Verfügung?
  • Ich bin mir bewusst, dass ich das Ergebnis der Kreuzkorrelation hochsampel, um Antworten auf die Verzögerung zu erhalten, aber ist das nicht auch eine Form des "Betrügens"? Warum unterscheidet es sich vom Upsampling vor der Kreuzkorrelation?

Wenn es tatsächlich so ist, dass das Upsampling nicht „schummelt“, warum sollten wir dann jemals unsere Abtastrate erhöhen müssen? (Ist eine höhere Abtastrate in gewisser Hinsicht nicht immer besser als die Interpolation eines Signals mit niedriger Abtastrate?)

Es scheint dann, als könnten wir nur mit einer sehr geringen Rate abtasten und so viel interpolieren, wie wir wollen. Würde dies die Erhöhung der Samplerate nicht angesichts der einfachen Interpolation eines Signals nach Herzenswunsch „unbrauchbar“ machen? Mir ist klar, dass die Interpolation Rechenzeit benötigt und einfach mit einer höheren Abtastrate beginnen würde, aber ist das dann der einzige Grund?

Vielen Dank.

Spacey
quelle
3
Ich bezweifle, dass es einen Unterschied in der Genauigkeit gibt, da die Informationsmenge in beiden Fällen dieselbe ist, aber es ist sicherlich billiger, nach der Kreuzkorrelation nur in dem interessierenden Bereich zu interpolieren, als zuerst alles zu upsamplizieren und dann alle diese zusätzlichen Multiplikationen durchzuführen.
Endolith
@ endolith Gute Punkte. Ich bin mir jetzt klarer darüber, warum / wie das funktioniert, und ja, ein Upsampling des Ergebnisses wäre in diesem Fall der richtige Weg.
Spacey

Antworten:

12

Es betrügt nicht und fügt auch keine neuen Informationen hinzu. Was Sie tun, ist dasselbe, was ein Upsampling-LPF tut - es werden Nullen hinzugefügt und dann die Wellenform mit den bereits bekannten Frequenzinformationen rekonstruiert. Somit gibt es keine neuen Informationen, aber es gibt immer noch eine feinere Zeitauflösung.

Beim Upsampling ist das Ergebnis ähnlich - keine neuen Informationen, aber eine feinere Zeitauflösung. Sie können durch etwas sehr ähnliches tun quadratische Interpolation .

Alle diese Methoden - Upsampling und Polynominterpolation - erhalten Informationen darüber, wo sich der gebrochene Peak sowohl vom Peak selbst als auch von seinen Nachbarn befindet. Ein kurzes Bildbeispiel. Ausgeglichener Peak

Die blaue Linie im Bild oben zeigt meine simulierten Kreuzkorrelationsdaten (obwohl dies jedes Ergebnis sein kann, nicht nur eine Kreuzkorrelation). Ich nenne es einen "ausgeglichenen" Peak, weil die Nachbarn symmetrisch sind. Wie zu erwarten ist, zeigt die resultierende quadratische Interpolation (rote Linie) an, dass der wahre Peak bei Null liegt.

Das Bild unten zeigt dagegen einen unausgeglichenen Peak. Bitte beachten Sie, dass sich bis auf die Werte der beiden nächsten Nachbarn nichts am Ergebnis geändert hat. Dies veranlasst den Interpolator jedoch, seine Schätzung des gebrochenen Peaks zu verschieben. Bildbeschreibung hier eingeben

Ein nützlicher Nebeneffekt dieser Methoden (Polynominterpolation und Upsampling) ist, dass Sie auch eine Schätzung des tatsächlichen Spitzenwerts erhalten, obwohl wir uns normalerweise mehr für den Ort interessieren.

Wenn es tatsächlich so ist, dass das Upsampling nicht „schummelt“, warum sollten wir dann jemals unsere Abtastrate erhöhen müssen?

Das Nyquist-Kriterium erfüllen.

Ist eine höhere Abtastrate nicht in gewisser Hinsicht immer besser als die Interpolation eines Signals mit niedriger Abtastrate?

Nein. Aus theoretischer Sicht spielt es keine Rolle, wie hoch die Abtastrate ist, solange das Nyquist-Kriterium erfüllt ist. Aus praktischer Sicht wird im Allgemeinen eine möglichst niedrige Abtastrate gewählt, um den Speicherbedarf und die Rechenlast zu verringern, was wiederum den Ressourcenbedarf und den Stromverbrauch senkt.

Jim Clay
quelle
1
Fs
1
@ Mohammad Ja und nein. Das Rauschen - entweder aus den Ergebnissen selbst oder aus dem Quantisierungsrauschen - macht die Erhöhung der Zeitauflösung letztendlich bedeutungslos. Bis zu diesem Zeitpunkt sollte jedoch ein größeres Upsampling die Genauigkeit der Schätzung verbessern.
Jim Clay
1
Anmerkungen und Beispielcode für die quadratische / parabolische Interpolation: gist.github.com/255291#file_parabolic.md und einige alternative Interpolationsmethoden: dspguru.com/dsp/howtos/how-to-interpolate-fft-peak
endolith
2
@JimClay Habe eine Chance drauf zu schlafen. Es ist jetzt klar - die Informationen sind immer da - es ist sozusagen nur in der Beziehung zwischen den Proben verschlüsselt. Und das ist es, was die Poly-Anpassung tatsächlich bei ihrer Interpolation verwendet. Und da das Signal bandbegrenzt ist (dh sich innerhalb einer Zeitspanne nur so schnell ändern kann), gibt es nur so viele Möglichkeiten, wie es zwischen Samples existieren kann.
Spacey
8

Jedes bandbegrenzte Signal kann interpoliert werden. Die zusätzliche Information "zwischen den Abtastwerten" ist in den benachbarten Abtastwerten enthalten, plus der Tatsache, dass das Signal vor dem Abtasten bandbegrenzt war (was dazu neigt, Information unter benachbarten Abtastwerten zu verbreiten). Wenn zwei Signale bandbegrenzt sind, ist dies die Kreuzkorrelation, so dass die Kreuzkorrelation auch interpoliert werden kann. Upsampling ist nur eine andere Form der Interpolation, eine sehr genaue Form der Interpolation für bandbegrenzte Signale. Sie können aber auch die Sinc-Interpolation verwenden (beides kann genauer sein als die quadratische oder parabolische Interpolation).

Bei der Interpolation kann ein Peak zwischen den Abtastwerten auftreten. Also vielleicht nicht unbrauchbar.

Wenn Sie ein Signal haben, das ein breiteres Spektrum enthält, kann es mehr Informationen enthalten. Das Abtasten mit einer höheren Rate liefert somit mehr Informationen, jedoch nur bis knapp unter die Hälfte der neuen Bandgrenzfrequenz und nur dann, wenn das Signal tatsächlich einen nützlichen Spektralfrequenzgehalt oberhalb der alten Bandgrenze enthielt und Sie diese nun zusätzlich erhalten können Spektrum durch Verwendung eines neuen, breitbandigeren bandbegrenzenden Verfahrens oder Filters anstelle des alten, verlustbehafteten. Durch das Abtasten von Daten mit einer viel höheren Frequenz eines Signals, das bereits auf eine viel niedrigere Frequenz unterhalb von Fs / 2 begrenzt war, erhalten Sie nur eine Interpolation und keinen weiteren Informationsgehalt.

Wenn die Abtastung quantisiert wird, kann eine Abtastung mit einer höheren Rate aufgrund von Dithering oder Rauschformung des Quantisierungsfehlers zu einem Bruchteil eines LSB mit mehr Informationen führen. Dies hängt jedoch vom Rauschabstand und der Genauigkeit des Abtasters sowie vom genauen Quantisierungsprozess ab, der bei der Abtastung verwendet wird.

Wenn zwei Signale vor dem Abtasten und der Kreuzkorrelation nicht richtig bandbegrenzt sind, können Sie mit dem Upsampling oder der Interpolation nicht nur ein mangelhaftes Ergebnis erzielen, sondern auch die ursprüngliche nicht interpolierte Kreuzkorrelation.

hotpaw2
quelle
1
Vielen Dank, hotpaw2. Es ist also richtig zu sagen, dass es nicht wirklich wichtig ist, wenn Sie beide Signale upsamplen und dann korrelieren oder das Ergebnis korrelieren und dann upsamplen? Wegen der Bandbegrenzung sollten die beiden Methoden zu den gleichen Ergebnissen führen?
Spacey
@Mohammad: Ich denke, es enthält in beiden Fällen die gleichen Informationen, aber da die Interpolation nicht perfekt ist, werden die Ergebnisse je nach Implementierung geringfügig abweichen.
Endolith
3

Ich denke, die beste Antwort, die ich Ihnen geben kann, ist: Sie haben alle Mittel, um es selbst herauszufinden. Bauen Sie ein Beispiel "rückwärts". Beginnen Sie mit Matlab mit zwei Signalen, die mit sehr kleinen Abtastperioden abgetastet wurden (so dass es sich fast um zeitkontinuierliche Signale handelt). Berechnen Sie die Kreuzkorrelation und finden Sie den Peak (falls gewünscht), den Sie mit hoher Präzision erstellen können. Dann beide Signale herunterrechnen und den Vorgang wiederholen. Vergleichen Sie die Position und Höhe des zweiten Peaks mit der ersten. Ich bin sicher, der zweite wird schlimmer sein. Die Verbesserung von der zweiten zur ersten ist das, was Sie gewinnen, wenn Sie vor der Kreuzkorrelation eine Stichprobe machen.

Um den richtigen Weg zu finden, müssen beide Signale bandbegrenzt sein und Sie müssen diese Bandbreiten kennen. Die "neuen" Informationen, die Sie in Ihrer Frage erwähnen, stammen aus den nebenstehenden Beispielen und der Tatsache, dass die Signale bandbegrenzt sind.

Telaclavo
quelle
Vielen Dank, Telaclavo. Eine Sache, die mir wirklich nicht klar ist, ist die Terminologie, bandbegrenzt zu sein. Ich weiß, was bedeutet, aber ich verstehe nicht, warum es hier erwähnt wird. JEDES System, außer möglicherweise Rauschen, ist "bandbegrenzt". Warum wird es in diesem Sinne immer wieder erwähnt?
Spacey
3

Um die vorherigen Antworten ein wenig zu ergänzen, können Sie das Äquivalent einer aufwärtsgetasteten bandbegrenzten Kreuzkorrelation erhalten, indem Sie Ihre Korrelationsvariable zu einer nicht ganzzahligen Variable machen.

τ

τ=argmaxτn=0N-1f(n)G(n+τ)

Das heißt, es wird das Maximum der Kreuzkorrelation gefunden.

abf(n)G(n)n={0,1,...,N-1}Nτ[-N+1,N-1] .

τcorrelate_pointomegaτ=1τ-1 mal die Rotationen der positiven Frequenzen sind (für entsprechende Frequenzpaare).

Die eine Subtilität liegt darin, wie Sie das behandelnN2piomega

ττ

import numpy
from numpy import fft
from scipy import optimize

def arg_max_corr(a, b):

    if len(a.shape) > 1:
        raise ValueError('Needs a 1-dimensional array.')

    length = len(a)
    if not length % 2 == 0:
        raise ValueError('Needs an even length array.')

    if not a.shape == b.shape:
        raise ValueError('The 2 arrays need to be the same shape')

    # Start by finding the coarse discretised arg_max
    coarse_max = numpy.argmax(numpy.correlate(a, b, mode='full')) - length+1

    omega = numpy.zeros(length)
    omega[0:length/2] = (2*numpy.pi*numpy.arange(length/2))/length
    omega[length/2+1:] = (2*numpy.pi*
            (numpy.arange(length/2+1, length)-length))/length

    fft_a = fft.fft(a)

    def correlate_point(tau):
        rotate_vec = numpy.exp(1j*tau*omega)
        rotate_vec[length/2] = numpy.cos(numpy.pi*tau)

        return numpy.sum((fft.ifft(fft_a*rotate_vec)).real*b)

    start_arg, end_arg = (float(coarse_max)-1, float(coarse_max)+1)

    max_arg = optimize.fminbound(lambda tau: -correlate_point(tau), 
            start_arg, end_arg)

    return max_arg
Henry Gomersall
quelle
1
τττ1
Oh, deine Frage ist verschwunden! Trotzdem lasse ich die Antwort dort.
Henry Gomersall
teinu
N2N(LogN+1)
Auch finde ich das Denken im Fourier-Bereich eigentlich viel einfacher. Aber vielleicht ist das nicht normal!
Henry Gomersall
2

Es gibt einen intuitiven Beweis, dass das Upsampling vor der Kreuzkorrelation gleichbedeutend mit dem anschließenden Ausführen ist:

Kreuzkorrelation ist Faltung mit dem anderen Signal zeitumgekehrt. Die Zeitumkehr wirkt sich nicht auf die Bandbreite aus. Faltung ist eine Multiplikation im Frequenzbereich, die die Bandbreite ebenfalls nicht erhöht. Wenn die ursprünglichen Signale richtig bandbegrenzt sind, auf die Hälfte der Abtastfrequenz, wird das Kreuzkorrelationsergebnis so sein. Es wird kein Aliasing eingeführt, um das Ergebnis zu ruinieren. Die anschließende Interpolation spart Arbeit.

Olli Niemitalo
quelle