Poszukiwanie dopasowujące

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Rekonstrukcja przykładowego sygnału algorytmem matching pursuit za pomoca programu mp4 (http://eeg.pl/mp).

Poszukiwanie dopasowujące (ang. Matching pursuit), jest rodzajem techniki numerycznej, która polega na znalezieniu "najlepszego dopasowania" funkcji z określonego słownika D do wielowymiarowych danych. Podstawowa idea polega na reprezentacji sygnału f z przestrzeni Hilberta H jako ważonej sumy funkcji g_{\gamma_n} (zwanych atomami) ze słownika D:

 f(t) = \sum_{n=-\infty}^{+\infty} a_n g_{\gamma_n}(t)

Przykładem podobnych reprezentacji jest rozwinięcie w szereg Fouriera gdy słownik jest zbudowany tylko z podstawowych funkcji (najmniejszy możliwy kompletny słownik). Główną wadą analizy Fouriera w cyfrowym przetwarzaniu sygnałów jest to, że mówi nam ona tylko o globalnych cechach sygnałów i nie dostosowuje się do analizowanych sygnałów f. Używając redundantnego słownika możemy szukać w nim funkcji, które najlepiej pasują do sygnału f. Znalezienie takiej reprezentacji, gdzie większość współczynników w sumie jest zbliżone do 0 jest pożądane m.in. do kodowania sygnału i kompresji.


Algorytm[edytuj | edytuj kod]

Przeszukiwanie bardzo dużych słowników dla najlepszego dopasowania jest nie do zaakceptowania przy obliczeniach w zastosowaniach praktycznych. W 1993 Mallat i Zhang [1] zaproponowali jako rozwiązanie algorytm zachłanny, znany od tego czasu jako Matching Pursuit. Jest to algorytm rekurencyjny, którego realizacja wygląda następująco:

  1. Wejście: Sygnał: f(t).
  2. Wyjście: Lista współczynników:  \left( a_n, g_{\gamma_n}\right) .
  3. Inicjalizacja: Rf_1 \leftarrow f(t)\;;
  4. Powtarzaj:
    1. znajdź g_{\gamma_n} \in D z maksymalną wartością bezwzględną iloczynu skalarnego |\langle Rf_n, g_{\gamma_n} \rangle|;
    2.  a_n  \leftarrow \langle Rf_n, g_{\gamma_n} \rangle ;
    3.  Rf_{n+1} \leftarrow Rf_n - a_n g_{\gamma_n};
    4.  n \leftarrow n + 1;
aż do stanu zatrzymania (na przykład: \lVert Rf_n \rVert < \mbox{threshold}\;)

Najczęściej używa się słownika składającego się z funkcji Gabora :

g_{\gamma_n}(t) = K(\gamma \phi)e^{-\pi (\frac{t-u}{s})^2} \sin (\omega(t-u)+\phi)

Taki dobór funkcji bazowych minimalizuje zasadę nieoznaczoności w przestrzeni czas-częstość.

Właściwości[edytuj | edytuj kod]

  • Dla każdego m tspełniona jest zasada zachowania energii:
\lVert f \rVert^2 = \sum_{n=0}^{m-1}{| a_n |^2} + \lVert Rf_m \rVert^2
  • Błąd \lVert Rf_n \rVert maleje monotonicznie (jego zanik jest wykładniczy).

Przypisy

  1. S. G. Mallat and Z. Zhang, Matching Pursuits with Time-Frequency Dictionaries, IEEE Transactions on Signal Processing, December 1993, pp. 3397-3415.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]