Co to jest transformacja Walsha-Hadamarda i do czego służy?

Próbuję nauczyć się o WHT, ale wydaje się, że nie ma wielu dobrych wyjaśnień online. Myślę, że wymyśliłem sposób obliczania WHT, ale naprawdę staram się zrozumieć, dlaczego uważa się to za przydatne w dziedzinie rozpoznawania obrazów.

Co jest w tym takiego wyjątkowego i jakie właściwości wywołuje w sygnale, który nie pojawiałby się w klasycznych transformatach Fouriera lub innych transformatach falkowych? Dlaczego wskazano tutaj rozpoznawanie obiektów ?

NASA używała transformacji Hadamarda jako podstawy do kompresji zdjęć z sond międzyplanetarnych w latach 60. i wczesnych 70. Hadamard jest obliczeniowo prostszym zamiennikiem transformaty Fouriera, ponieważ nie wymaga żadnych operacji mnożenia ani dzielenia (wszystkie czynniki są plus lub minus jeden). Operacje mnożenia i dzielenia były niezwykle czasochłonne na małych komputerach używanych na pokładzie tych statków kosmicznych, więc ich unikanie było korzystne zarówno pod względem czasu obliczeniowego, jak i zużycia energii. Ale od czasu opracowania szybszych komputerów z multiplikatorami jednocyklowymi i udoskonalenia nowszych algorytmów, takich jak szybka transformacja Fouriera, a także opracowania JPEG, MPEG i innych kompresji obrazów, uważam, że Hadamard przestał być używany. Jednak, Rozumiem, że może to być powrót do użycia w obliczeniach kwantowych. (Wykorzystanie NASA pochodzi ze starego artykułu w NASA Tech Briefs; dokładne przypisanie jest niedostępne).

Współczynniki transformacji Hadamarda wynoszą +1 lub -1. Szybką transformację Hadamarda można zatem zredukować do operacji dodawania i odejmowania (bez dzielenia lub mnożenia). Pozwala to na użycie prostszego sprzętu do obliczenia transformacji.

Zatem koszt lub szybkość sprzętu mogą być pożądanym aspektem transformacji Hadamarda.

Spójrz na ten artykuł, jeśli masz dostęp, wkleiłem tutaj streszczenie Pratt, WK; Kane, J .; Andrews, HC; , „Kodowanie obrazu transformacji Hadamarda”, Proceedings of IEEE, vol.57, no.1, str. 58-68, styczeń 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp /stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Streszczenie Wprowadzenie algorytmu szybkiej transformacji Fouriera doprowadziło do opracowania techniki kodowania obrazu z transformacją Fouriera, w której dwuwymiarowa transformata Fouriera obrazu jest przesyłana kanałem, a nie samym obrazem. To rozwinięcie doprowadziło ponadto do pokrewnej techniki kodowania obrazu, w której obraz jest transformowany przez operatora macierzy Hadamarda. Macierz Hadamarda to kwadratowa tablica plusów i minusów, których rzędy i kolumny są do siebie prostopadłe. Opracowano szybki algorytm obliczeniowy, podobny do algorytmu szybkiej transformaty Fouriera, który wykonuje transformację Hadamarda. Ponieważ tylko transformaty Hadamarda wymagają dodawania i odejmowania liczb rzeczywistych, możliwa jest przewaga prędkości rzędu wielkości w porównaniu do transformaty Fouriera o liczbie zespolonej.

Chciałbym dodać, że dowolna transformacja m (macierz Toeplitza wygenerowana przez sekwencję m) może zostać rozłożona

P1 * WHT * P2

gdzie WHT jest transformacją Walsha Hadamarda, P1 i P2 są permutacjami (zob .: http://dl.acm.org/citation.cfm?id=114749 ).

transformacja m jest używana do wielu rzeczy: (1) identyfikacji systemu, gdy system jest nękany hałasem i (2) przez wirtualne z (1) identyfikacji opóźnienia fazowego w systemie nękanym hałasem

dla (1) transformacja m odzyskuje jądro systemu, gdy bodziec jest sekwencją m, co jest przydatne w neurofizjologii (np . http://jn.physiology.org/content/99/1/367. pełne i inne), ponieważ jest to duża moc dla sygnału szerokopasmowego.

Dla (2) złoty kod jest zbudowany z sekwencji m (http://en.wikipedia.org/wiki/Gold_code).

Cieszę się, że jestem świadkiem ożywienia wokół transformacji Walsha-Paleya-Hadamarda (lub czasem nazywanych Waleymardem). Zobacz, jak możemy wykorzystać transformację Hadamarda do wydobywania cech z obrazu?

$\pm 1$

$2^n$

Jako takie, można je stosować w dowolnej aplikacji, w której stosuje się zasady cosinus / sinus lub falki, z bardzo tanią implementacją. W przypadku danych liczb całkowitych mogą pozostać liczbami całkowitymi i pozwolić na naprawdę bezstratne transformacje i kompresję (podobnie jak liczby całkowite DCT lub binarne falki lub binlet). Można więc używać ich w kodach binarnych.

Ich działanie jest często uważane za gorsze niż inne transformacje harmoniczne naturalnych sygnałów i obrazów, ze względu na ich blokowy charakter. Jednak niektóre warianty są nadal w użyciu, na przykład w przypadku odwracalnych transformacji kolorów (RCT) lub transformacji kodowania wideo o niskiej złożoności (transformacja i kwantyzacja o niskiej złożoności w H.264 / AVC ).

Trochę literatury:

• Agaian, SS, Matryce Hadamarda i ich zastosowania, 1985
• Beauchamp, KG, funkcje Walsha i ich zastosowania, 1975
• Harmut, HF, Przekazywanie informacji przez funkcje ortogonalne, 1970
• Algorytm kompresji wideo w czasie rzeczywistym dla przetwarzania transformacji Hadamarda (NASA, 196)
• Adaptacyjna kompresor wideo Hadamarda z transformacją w czasie rzeczywistym (NASA, 196)

Niektóre linki: strona internetowa

Ogólny opis

Dla rozkładu Gaussa

Raport