Czy próbkowanie wstępne przed korelacją krzyżową jest bezużyteczne?

12

Rozważ prosty przypadek, w którym dwa sygnały z dwóch różnych czujników są skorelowane krzyżowo, a opóźnienie czasowe nadejścia jest obliczane na podstawie odciętej wartości szczytowej ich funkcji korelacji krzyżowej.

Przyjmijmy teraz, że ze względu na ograniczenia wymiarowe obu anten oraz ograniczenia maksymalnej możliwej częstotliwości próbkowania maksymalne możliwe opóźnienie wynosi , co odpowiada 10 próbkom. $D$

Problem:

Z powodu tych ograniczeń obliczone opóźnienie może różnić się od dowolnej liczby całkowitej od 0 do 10 próbek, to znaczy: . Jest to problematyczne, ponieważ tak naprawdę chcę rozróżnić opóźnienie ułamkowe opóźnienia między dwoma sygnałami uderzającymi w moje anteny, a zmiana wymiarów lub częstotliwości próbkowania nie wchodzi w grę. $0 \le D \le 10$

Kilka myśli:

Oczywiście pierwszą rzeczą, o której myślę w tym przypadku, jest próbkowanie sygnałów przed wykonaniem korelacji krzyżowej. Myślę jednak, że to w jakiś sposób „oszukuje”, ponieważ tak naprawdę nie dodam żadnych nowych informacji do systemu.
Nie rozumiem, w jaki sposób upsampling nie jest w pewnym sensie „oszustwem”. Tak, rekonstruujemy nasz sygnał na podstawie obecnie obserwowanej informacji o częstotliwości, ale w jaki sposób daje to wiedzę o tym, gdzie sygnał naprawdę zaczął się między, powiedzmy, i ? Gdzie ta informacja była zawarta w oryginalnym sygnale, który określał, że prawdziwy początek sygnału z ułamkowym opóźnieniem faktycznie miał ? $D=7$ $D=8$ $D=7.751$

Pytania):

Czy to naprawdę „oszustwo”?
- Jeśli nie, to skąd ta nowa „informacja” pochodzi?
- Jeśli tak, to jakie inne opcje są dostępne do szacowania czasów ułamkowych?
Jestem świadomy próbkowania w górę wyniku korelacji krzyżowej, próbując uzyskać odpowiedzi podpróbki na opóźnienie, ale czy to też nie jest formą „oszukiwania”? Dlaczego różni się od upsamplingu przed korelacją krzyżową?

Jeśli rzeczywiście jest tak, że upsampling nie oznacza „oszukiwania”, to dlaczego mielibyśmy kiedykolwiek zwiększać częstotliwość próbkowania? (Czy uzyskanie wyższej częstotliwości próbkowania nie zawsze jest lepsze w pewnym sensie niż interpolacja niskiego próbkowanego sygnału?)

Wydawałoby się wtedy, że moglibyśmy po prostu pobierać próbki w bardzo niskim tempie i interpolować tyle, ile chcemy. Czy nie spowodowałoby to, że zwiększenie częstotliwości próbkowania byłoby „bezużyteczne” w świetle zwykłej interpolacji sygnału do pragnienia naszego serca? Zdaję sobie sprawę, że interpolacja wymaga czasu obliczeniowego, a po prostu rozpoczęcie od wyższej częstotliwości próbkowania nie, ale czy to jedyny powód?

Dzięki.

filters cross-correlation peak-detection

— Spacey
źródło

3

Wątpię, czy istnieje jakakolwiek różnica w dokładności, ponieważ ilość informacji jest taka sama w obu kierunkach, ale z pewnością tańsza jest interpolacja po korelacji krzyżowej tylko w obszarze zainteresowania, niż najpierw próbkowanie wszystkiego, a następnie wykonanie wszystkich tych dodatkowych multiplikacji.

— endolith

@endolith Good point (s). Teraz jaśniej wyjaśniam, dlaczego / jak to działa, i tak, upsampling wyniku byłby dobrym rozwiązaniem w tym przypadku.

— Spacey

12

Nie oszukuje, nie dodaje też żadnych nowych informacji. To, co robisz, jest tym samym, co robi każdy LPF o zwiększonym próbkowaniu - dodawanie zer, a następnie rekonstruowanie kształtu fali z już znaną informacją o częstotliwości. Dlatego nie ma żadnych nowych informacji, ale nadal istnieje lepsza rozdzielczość czasu.

Upsampling wyniku jest podobny - brak nowych informacji, ale lepsza rozdzielczość czasowa. Możesz zrobić coś bardzo podobnego poprzez interpolację kwadratową .

Wszystkie te metody - upsampling i interpolacja wielomianowa - uzyskują informacje o tym, gdzie pik ułamkowy pochodzi zarówno od samego piku, jak i od jego sąsiadów. Szybki przykład obrazkowy. Zrównoważony szczyt

Niebieska linia na powyższym obrazku to moje symulowane dane korelacji krzyżowej (choć może to być dowolny wynik, a nie tylko korelacja krzyżowa). To właśnie nazywam szczytem „zrównoważonym”, ponieważ sąsiedzi są symetryczni. Jak można się spodziewać, wynikowa interpolacja kwadratowa (czerwona linia) wskazuje, że prawdziwy pik ma zero.

Z drugiej strony obraz poniżej pokazuje niezrównoważony szczyt. Należy pamiętać, że w wyniku nic się nie zmieniło oprócz wartości dwóch najbliższych sąsiadów. Powoduje to jednak, że interpolator przesuwa swoją ocenę piku ułamkowego. wprowadź opis zdjęcia tutaj

Sporą zaletą tych metod (interpolacja wielomianowa i upsampling) jest to, że daje również oszacowanie prawdziwej wartości szczytowej, chociaż zazwyczaj jesteśmy bardziej zainteresowani lokalizacją.

Jeśli rzeczywiście jest tak, że upsampling nie oznacza „oszukiwania”, to dlaczego mielibyśmy kiedykolwiek zwiększać częstotliwość próbkowania?

Aby spełnić kryterium Nyquista.

Czy posiadanie wyższej częstotliwości próbkowania nie zawsze jest lepsze w pewnym sensie niż interpolacja niskiego próbkowanego sygnału?

Nie. Z teoretycznego punktu widzenia, o ile spełnione jest kryterium Nyquista, nie ma znaczenia, jaka jest częstotliwość próbkowania. Z praktycznego punktu widzenia generalnie stosuje się tak niską częstotliwość próbkowania, jak to możliwe, aby zmniejszyć wymagania dotyczące pamięci i obciążenia obliczeniowego, co z kolei zmniejsza potrzebne zasoby i zużycie energii.

— Jim Clay
źródło

1

@Jim, znam Kryterium Nyquista. :-) To, co miałem na myśli, było w kontekście zwiększania , czy nie byłoby lepiej mieć wyższą częstotliwość próbkowania na początku, aby nie musieć zwiększać częstotliwości próbkowania, i z tego, co słyszę, to prawda. Wygląda na to, że gdy Nyquist będzie usatysfakcjonowany, wszystkie informacje, które kiedykolwiek dostaniesz, są już „dostępne”, a próbkowanie do pewnego poziomu da ci dowolną rozdzielczość czasową, jakiej chcesz. W tym sensie, czy to sprawia, że jest otwarty? Im wyżej możesz sobie pozwolić na próbkowanie, tym lepiej?

F_{s}

$F_s$

— Spacey

1

@Mohammad Tak i nie. Szum - albo z samych wyników, albo z szumu kwantyzacji - w końcu sprawi, że zwiększenie rozdzielczości czasowej nie będzie miało znaczenia. Do tego momentu jednak tak, zwiększenie częstotliwości próbkowania powinno poprawić dokładność oszacowania.

— Jim Clay

1

noty oraz przykładowy kod dla kwadratowej / paraboliczne interpolacji: gist.github.com/255291#file_parabolic.md i niektórych alternatywnych metod interpolacji: dspguru.com/dsp/howtos/how-to-interpolate-fft-peak

— endolit

2

@JimClay Miałem okazję się przespać. Teraz jest jasne - informacja zawsze tam jest - jest niejako zakodowana w relacji między próbkami. I tego właśnie używa poli-kształtka do interpolacji. A ponieważ sygnał jest ograniczony pasmem (tzn. Może zmieniać się tak szybko w określonym przedziale czasu), istnieje tylko tyle sposobów, w jaki może istnieć między próbkami.

— Spacey

8

Dowolny sygnał pasma może być interpolowany. Dodatkowe informacje „między próbkami” są zawarte w sąsiednich próbkach oraz fakt, że przed próbkowaniem sygnał był ograniczony pasmem (co ma tendencję do rozprzestrzeniania informacji między sąsiednimi próbkami). Jeśli dwa sygnały są ograniczone pasmem, wówczas korelacja krzyżowa będzie możliwa, więc korelację krzyżową można również interpolować. Upsampling jest tylko inną formą interpolacji, bardzo dokładną formą interpolacji dla sygnałów o ograniczonym paśmie; ale możesz również użyć interpolacji Sinc'a (oba mogą być dokładniejsze niż interpolacja kwadratowa lub paraboliczna).

Interpolacja może wykazywać pik między próbkami. Może więc nie bezużyteczne.

Jeśli masz sygnał zawierający szersze spektrum, może on zawierać więcej informacji. Próbkowanie go z większą częstotliwością zapewni zatem więcej informacji, ale tylko do nieco poniżej połowy nowej częstotliwości granicznej pasma i tylko wtedy, gdy sygnał zawiera rzeczywistą użyteczną zawartość częstotliwości widmowej powyżej starej granicy pasma, i jeśli można teraz uzyskać tę dodatkową spektrum przy użyciu nowego, bardziej szerokopasmowego procesu ograniczania pasma lub filtra, zamiast starego bardziej stratnego. Próbkowanie danych przy znacznie wyższej częstotliwości sygnału, który był już ograniczony pasmem do znacznie niższej częstotliwości poniżej Fs / 2, spowoduje jedynie zakup interpolacji, a nie więcej informacji.

Jeśli próbkowanie jest kwantowane, wówczas próbkowanie z wyższą częstotliwością może dać ci ułamek LSB więcej informacji, z powodu ditheringu lub kształtowania szumu błędu kwantyzacji. Zależy to jednak od stosunku S / N i dokładności próbnika oraz dokładnego procesu kwantyzacji zastosowanego w próbkowaniu.

Jeśli dwa sygnały nie są właściwie ograniczone pasmem przed próbkowaniem i korelacją krzyżową, to nie tylko może zarówno próbkowanie w górę, jak i interpolacja może przynieść śmieciowy wynik, ale może to być oryginalna nieinterpolowana korelacja krzyżowa.

— hotpaw2
źródło

1

Dzięki hotpaw2. Zatem poprawne jest stwierdzenie, że nie ma znaczenia, czy próbkujesz oba sygnały, a następnie korelujesz, czy korelujesz, a następnie próbkujesz wynik? Ze względu na ograniczenie pasma dwie metody powinny dać te same wyniki?

— Spacey

@Mohammad: Myślę, że i tak zawiera te same informacje, ale ponieważ interpolacja nie jest idealna, wyniki będą się nieco różnić w zależności od implementacji.

— endolith

3

Myślę, że najlepszą odpowiedzią, jaką mogę ci dać, jest: masz wszelkie środki, by się przekonać. Zbuduj przykład „wstecz”. Korzystając z Matlaba, zacznij od dwóch sygnałów próbkowanych z bardzo małymi okresami próbkowania (tak aby były to sygnały prawie ciągłe). Oblicz korelację krzyżową i znajdź szczyt (jeśli tego chcesz), co będziesz w stanie zrobić z dużą precyzją. Następnie zmniejsz próbkowanie obu sygnałów i powtórz proces. Porównaj położenie i wysokość drugiego szczytu z pierwszym. Jestem pewien, że drugi będzie gorszy. Ulepszenie od drugiego do pierwszego jest tym, co zyskujesz, jeśli próbkujesz przed korelacją krzyżową.

Aby uzyskać próbkę we właściwy sposób, oba sygnały muszą być ograniczone pasmem i musisz znać te pasma. „Nowa” informacja, o której wspominasz w swoim pytaniu, pochodzi z sąsiednich próbek i fakt, że sygnały są ograniczone w paśmie.

— Telaclavo
źródło

Dzięki Telaclavo. Jedną rzeczą, która tak naprawdę nie jest dla mnie jasna, jest terminologia „ograniczonego pasma”. Wiem, co to znaczy, ale nie rozumiem, dlaczego wspomniano tutaj. JAKIEKOLWIEK systemy, poza możliwym szumem, są „ograniczone w paśmie”, więc dlaczego jest wymieniany w tym sensie w kółko?

— Spacey

3

Aby dodać nieco do poprzednich odpowiedzi, można uzyskać ekwiwalent korelacji krzyżowej ograniczonej przez próbkowanie w górę, zmieniając zmienną korelacji na wartość niecałkowitą.

Poniższy kod (python) oblicza , gdzie $\tau$

τ = \arg max_{τ} \sum_{n = 0}^{N - 1} f (n) g (n + τ)

$\tau = \arg \max_{\tau}\sum_{n=0}^{N-1}f\left(n\right)g\left(n+\tau\right)$

Oznacza to, że znajduje maksimum korelacji krzyżowej.

Zmienne wejściowe ai bopisania i dla i oba zakłada się, że ograniczony pasmem i okresowe z okresem (przesunięcie jest realizowane w dyskretnej domenie Fouriera). jest w zakresie . $f\left(n\right)$ $g\left(n\right)$ $n = \{0, 1, ... , N-1\}$ $N$ $\tau$ $[-N+1, N-1]$

Celem jest pokazanie, w jaki sposób można wykonać korelację krzyżową dla wartości niecałkowitych , która jest zdefiniowana przez zamknięcie . Wykorzystuje to tablicę, która opisuje obrót zespolonego fazora przy każdej dyskretnej częstotliwości odpowiadającej przesunięciu . następnie skaluje to dla każdej zmiany. Powinno być oczywiste, że aby utrzymać sygnał w czasie rzeczywistym, obroty częstotliwości ujemnych są zaledwie razy większe niż obroty częstotliwości dodatnich (dla odpowiednich par częstotliwości). $\tau$ correlate_pointomega $\tau=1$ $\tau$ $-1$

Jedyną subtelnością jest to, jak traktujesz próbkę (częstotliwość nyquista), ponieważ jest ona dzielona między pasmami dodatnimi i ujemnymi. Rozwiązaniem zastosowanym w tym przypadku jest interpolacja między fazorem rotacji dodatniej i fazorem rotacji ujemnej (które są odbiciami na osi rzeczywistej), która polega na rzutowaniu fazora rotacji jednostkowej na rzeczywistą oś, która jest funkcją cos ( ponieważ jest to, że to wartość odpowiadająca częstotliwości NYYQUIST). Oczywiście ta wartość musi być rzeczywista, aby utrzymać sygnał w domenie w czasie rzeczywistym. $\frac{N}{2}$ piomega

Możesz użyć tego do obliczenia korelacji krzyżowej dla dowolnej arbitralnie precyzyjnej wartości . Po prostu wywołaj zamknięcie (które można zwrócić jako wywołanie) z dowolną wartością którą sobie wyobrażasz. $\tau$ $\tau$

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
źródło

1

Muszę się zastanowić, czy twoje pytanie jest prawidłowe (i nie mam teraz czasu). Myślę, że przesuwasz grupowe opóźnienie swojego sygnału, co możesz zrobić o dowolną kwotę. Jest to dokładnie równoważne zwojowi kołowemu z funkcją sinc w dziedzinie czasu, z przesunięciem sinc o (ale nadal próbkowanym w tych samych miejscach, co oryginalny sygnał). Warto zauważyć, że przy liczbie całkowitej wszystkie przejścia przez zero sinc są zgodne z czasami próbkowania, z wyjątkiem at (gdzie jest to ), dlatego sygnał jest trywialnie przesunięty.

τ

$\tau$

τ

$\tau$

τ

$\tau$

1

$1$

— Henry Gomersall

Och, twoje pytanie zniknęło! Mimo to zostawię tam odpowiedź.

— Henry Gomersall

Dzięki Henry - (Przepraszam, że usunąłem moje pytanie, próbowałem to wyjaśnić! :-)). (Jestem trochę powolny w pobieraniu pytona, ale pracuję w nim). W każdym razie, tak, myślę, że rozumiem twoją metodę - i myślę, że jej sedno polega na tym, że interpolacja odpowiedzi fazowej wyniku korelacji krzyżowej jest pobierana i stamtąd odczytywana jest odpowiednia wartość . Może potrzebuję więcej czasu do strawienia, ale mimo to interesującego. Gdzie / dlaczego użyłeś go zamiast interpolacji w dziedzinie czasu? Kontekst może pomóc. Dzięki!

t a u

$tau$

— Spacey

To była naiwna pogoń za prędkością, chociaż cieszę się, że mogę powiedzieć, że istnieje szybszy algorytm interpolacji w dziedzinie czasu. Moim uzasadnieniem jest to, że aby wykonać przesunięcie czasowe w liczbie niecałkowitej w dziedzinie czasu, potrzebujesz mnożenia celu wykonania splotu w porównaniu do przy użyciu metody Fouriera (lub o niej ). W obu przypadkach korelacja jest brana w dziedzinie czasu. Jeśli spróbujesz ponownie spróbować, wydaje mi się to bardzo powolne (i zrobiłbym to również w dziedzinie Fouriera!).

N^{2}

$N^2$

N (\log N + 1)

$N\left(\log N + 1\right)$

— Henry Gomersall

Uważam też, że myślenie w dziedzinie Fouriera jest znacznie prostsze. Ale może to nie jest normalne!

— Henry Gomersall

2

Istnieje intuicyjny dowód, że upsampling przed korelacją krzyżową jest równoważny z wykonaniem go później:

Korelacja krzyżowa jest splotem z innym sygnałem odwróconym w czasie. Odwrócenie czasu nie wpływa na przepustowość. Konwolucja to zwielokrotnienie w dziedzinie częstotliwości, co również nie zwiększa przepustowości. Jeśli oryginalne sygnały są właściwie ograniczone pasmem, do połowy częstotliwości próbkowania, to również będzie wynik korelacji krzyżowej. Nie wprowadzono żadnego aliasingu, który zniszczyłby wynik. Interpolacja oszczędza pracę.

— Olli Niemitalo
źródło