Co to jest transformacja Walsha Hadamarda? Jak można to wykorzystać w przetwarzaniu obrazu?

NASA używała transformacji Hadamarda jako podstawy do kompresji zdjęć z sond międzyplanetarnych w latach sześćdziesiątych i wczesnych „Lata 70. Hadamard jest obliczeniowo prostszym substytutem transformaty Fouriera, ponieważ nie wymaga operacji mnożenia ani dzielenia (wszystkie czynniki mają wartość 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 unikanie ich było korzystne zarówno pod względem czasu obliczeniowego, jak i zużycia energii. Ale od czasu opracowania szybszych komputerów z mnożnikami pojedynczego cyklu i udoskonalenia nowszych algorytmów, takich jak szybka transformacja Fouriera, a także opracowania formatu JPEG, MPEG i innych kompresji obrazu, uważam, że Hadamard wypadł z użycia. Rozumiem jednak, że może to oznaczać powrót do wykorzystania w komputerach kwantowych. (Wykorzystanie NASA pochodzi ze starego artykułu w NASA Tech Briefs; dokładne źródła niedostępne).

Komentarze

• Fantastyczna relacja historyczna Panie Peters, dziękuję za to. Czy możesz rozwinąć, co / jak masz na myśli, mówiąc, że może to oznaczać powrót do obliczeń kwantowych? W jaki sposób nawiązujesz do tego w swoim poście?
• Zgodnie z artykułem w Wikipedii, wiele algorytmów kwantowych wykorzystuje transformatę Hadamarda jako początkowy krok, ponieważ odwzorowuje n kubitów na superpozycję wszystkich 2n ortogonalnych stwierdza w bazie kwantowej o równej wadze.
• Eric, czy możesz podać link do cytowanego artykułu na Wikipedii? Jeśli tak, przyjmuję twoją odpowiedź.
• Oczywiście. To en.wikipedia.org/wiki/Hadamard_transform
• Eric, myślałem, że to kolejne źródło, do którego się odnosisz. Nieważne. 🙂

Wszystkie współczynniki transformacji Hadamarda wynoszą +1 lub -1. Szybka transformacja Hadamarda może zatem zostać zredukowana do operacji dodawania i odejmowania (bez dzielenia lub mnożenia). Pozwala to na użycie prostszego sprzętu do obliczenia transformacji.

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

Komentarze

• Dziękuję za odpowiedź, ale czy chciałbym zrozumieć transformację? Nie obchodzi mnie teraz szybka implementacja. Co to za transformacja? Dlaczego jest to przydatne? Jaki wgląd daje nam to w porównaniu z innymi transformacjami falkowymi?

Spójrz na ten artykuł, jeśli mam dostęp, wklejam tutaj streszczenie: Pratt, WK; Kane, J .; Andrews, HC;, „Hadamard transform image coding”, Proceedings of the IEEE, tom 57, nr 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 transformaty Fouriera doprowadziło do opracowania techniki kodowania obrazu z transformacją Fouriera, w której dwuwymiarowa transformata Fouriera obrazu jest przesyłana przez kanał, a nie przez sam obraz. Ten rozwój doprowadził do powstania powiązanej techniki kodowania obrazu w którym obraz jest przekształcany przez operator macierzy Hadamarda. Macierz Hadamarda to kwadratowa tablica liczb dodatnich i ujemnych, których wiersze i kolumny są względem siebie ortogonalne. Szybki algorytm obliczeniowy, podobny do szybkiego algorytmu Fouriera opracowano algorytm transformacji, który wykonuje transformację Hadamarda. Ponieważ w przypadku transformaty Hadamarda wymagane są tylko dodawanie i odejmowanie liczb rzeczywistych, możliwa jest przewaga prędkości rzędu wielkości w porównaniu z transformatą Fouriera liczby zespolonej. Przesyłanie transformaty Hadamarda obrazu zamiast reprezentacji przestrzennej obrazu zapewnia potencjalną tolerancję na błędy kanału i możliwość zmniejszonej transmisji w paśmie.

Komentarze

• Dzięki za ten link, z pewnością go przeczytam, ale może to zająć trochę czasu. Z abstrakcji wynika, że transformata Hadamarda może być użyta jako… substytut?… Transformaty Fouriera, po części dlatego, że jest obliczeniowo bardzo wydajna, ale może z innego powodu? Jakie było Twoje ogólne zdanie na ten temat?
• Używając transformaty Hadamarda, jesteśmy w stanie przesłać zakodowaną wersję obrazu, a następnie zrekonstruować ją w odbiorniku. W tym konkretnym przypadku autor używa transformacji, aby skoncentrować energię sygnału w węższym paśmie niż oryginalny obraz, dzięki czemu jest mniej obciążony szumem i można go zrekonstruować za pomocą odwrotnej hadamardy w odbiorniku.
• Hmm, tak, właśnie skończyłem czytać artykuł – wygląda na to, że transformacja Hadamarda jest po prostu szybszą alternatywą dla transformaty Fouriera, ale nic innego tak naprawdę się nie wyróżnia. Oszczędza energię, entropię itp., Ale wydaje się być mniej więcej taki sam jak FFT.
• Czy Hadamard Transform radzi sobie wystarczająco dobrze (nawet jeśli nie lepiej) przeciwko innym transformacjom, takim jak DFT lub nawet DCT. Bycie szybkim jest dobre, ale czy naprawdę może dać tak dobrą kompresję, jak powiedzmy, że DCT to prawdziwe pytanie. Większość konwencjonalnych standardów JPEG, MPEGx don ' – tak przy okazji, całkiem go używam.

Chciałbym dodać, że każda transformata m (macierz Toeplitza wygenerowana przez sekwencję m) może zostać rozłożona na

P1 * WHT * P2

gdzie WHT to transformacja Walsha Hadamarda, P1 i P2 to permutacje (ref: http://dl.acm.org/citation.cfm?id=114749 ).

m-transformacja jest używana do wielu rzeczy: (1) identyfikacja systemu, gdy system jest nękany szumem i (2) wirtualna (1) identyfikacja opóźnienia fazy w systemie, który jest nękany szum

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

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

Cieszę się, że jestem świadkiem odrodzenia wokół transformacji Walsha-Paleya-Hadamarda (lub czasami nazywanego Waleymardem). Zobacz Jak my może używać transformacji Hadamarda do wyodrębniania cech z obrazu?

Są to szczególne przykłady funkcji Rademachera. Tworzą transformacje ortogonalne, które mogą, pomijając normalizację potęgi, być realizowane za pomocą tylko dodawania i odejmowania oraz potencjalnie binarnych przesunięć. Zasadniczo nie wymagają one mnożenia, co pozwala na szybkie obliczenia i niewielkie, wymyślne potrzeby zmiennoprzecinkowe.

Ich współczynniki wektorowe składają się z $ \ pm 1 $ , które naśladują binaryzowaną wersję zasad sinusowych lub cosinusowych. Porządkowanie wektorów Walsha jest zgodne z sekwencją (zamiast częstotliwości), która zlicza liczbę zmian znaku. Cieszą się podobnymi algorytmami motylkowymi do jeszcze szybszej implementacji.

Sekwencje Walsha długości $ 2 ^ n $ można również interpretować jako instancje falki Haara pakiet.

Jako takie, mogą być używane w dowolnej aplikacji, w której używane są bazy cosinus / sinus lub wavelet, z bardzo tanią implementacją. W przypadku danych całkowitych mogą pozostać liczbami całkowitymi i umożliwiać prawdziwie bezstratne transformacje i kompresję (podobnie jak w przypadku liczb całkowitych DCT lub binarnych fal lub binletów). Więc można ich używać w kodach binarnych. Są również używane w wykrywaniu kompresyjnym.

Ich wydajność jest często uważana za gorszą niż inne transformacje harmoniczne na naturalnych sygnałach i obrazach, ze względu na ich blokowy charakter. Jednak niektóre warianty są nadal używane, na przykład w przypadku odwracalnych transformacji kolorów (RCT) lub transformacji kodowania wideo o niskiej złożoności ( Transformacja o niskiej złożoności i kwantyzacja w H.264 / AVC ).

Część literatury:

• Agaian, SS, Hadamard Matrices and their Applications, 1985
• Beauchamp, KG, Walsh functions and their aplikacje, 1975
• Harmut, HF, Transmisja informacji przez funkcje ortogonalne, 1970
• Algorytm kompresji wideo w czasie rzeczywistym dla transformacji Hadamarda przetwarzanie (NASA, 196)
• Adaptacyjny kompresor wideo transformacji Hadamarda w czasie rzeczywistym (NASA, 196)

Niektóre linki: Strona internetowa

Opis ogólny

Rozkład Gaussa

Raport

Komentarze

• ' jest lepiej, jeśli możesz wyjaśnić, dlaczego każdy link jest dobry.Nawet pełny tytuł dokumentu, do którego prowadzi łącze, byłby lepszy.
• Próbowałem, ale oprogramowanie forum się rozpadało, więc otrzymujesz wersję podsumowującą. Jeśli chcesz usunąć wszystko w stylu policyjnym wiki, zrób to.
• Nie ' nie sądzę, że to aż tak dużo ” wiki-policing ” w tym przypadku jako próba utrzymania standardu formatu Q & A w tym tablica. Jego celem nie jest pełnienie funkcji forum. Tak więc opinia na temat Twojego wkładu nie polega na usunięciu go, chodzi o wzięcie go na pokład, ale także upewnienie się, że jest zgodny ze standardem. Jest to powszechne w całej sieci wymiany stosów. Myślę, że warto edytować post.