Co je transformace Walsha Hadamarda? Jak je možné jej použít při zpracování obrazu?

NASA používala Hadamardovu transformaci jako základ pro kompresi fotografií z meziplanetárních sond během 60. let a na počátku „70. léta. Hadamard je výpočetně jednodušší náhrada Fourierovy transformace, protože nevyžaduje žádné operace násobení ani dělení (všechny faktory jsou plus nebo minus jedna). Operace násobení a dělení byly na malých počítačích používaných na palubě těchto kosmických lodí extrémně časově náročné, takže jejich vyhýbání bylo výhodné jak z hlediska výpočetního času, tak spotřeby energie. Ale od vývoje rychlejších počítačů, které obsahují multiplikátory s jedním cyklem, a dokonalosti novějších algoritmů, jako je Fast Fourierova transformace, stejně jako vývoj JPEG, MPEG a další komprese obrazu, věřím, že Hadamard přestal být používán. Chápu však, že to může být návrat na scénu pro použití v kvantových výpočtech. (Použití NASA pochází ze starého článku v NASA Tech Briefs; přesné uvedení zdroje není k dispozici.)

Komentáře

• Fantastický historický účet Pane Petersi, děkuji za to. Můžete rozšířit, co / jak máte na mysli, že by mohlo dojít k návratu v kvantové práci s počítačem? Jak na to ve svém příspěvku narážíte?
• Podle článku na Wikipedii používá mnoho kvantových algoritmů jako první krok Hadamardovu transformaci, protože mapuje n qubits na superpozici všech 2n ortogonálních uvádí na kvantové bázi se stejnou váhou.
• Eric, můžete uvést odkaz na citovaný článek na wikipedii? Pokud ano, mohu vaši odpověď přijmout.
• Jistě. Je to en.wikipedia.org/wiki/Hadamard_transform
• Eriku, myslel jsem, že je to další zdroj, na který odkazujete. Nikdy moje. 🙂

Koeficienty Hadamardovy transformace jsou všechny +1 nebo -1. Rychlou Hadamardovu transformaci lze proto omezit na operace sčítání a odčítání (bez dělení nebo násobení). To umožňuje použití jednoduššího hardwaru k výpočtu transformace.

Takže náklady nebo rychlost hardwaru mohou být žádoucím aspektem Hadamardovy transformace.

Komentáře

• Děkuji za odpověď, ale rád bych této transformaci porozuměl, prosím? Právě teď se nestarám o rychlou implementaci. Co je to za transformaci? Proč je to užitečné? Jaký přehled nám poskytuje VS jiné vlnkové transformace?

Podívejte se na tento článek, pokud mít přístup, „vložil jsem sem abstrakt Pratt, WK; Kane, J .; Andrews, HC;“ Hadamard transformace obrazu, „Proceedings of the IEEE, sv. 57, č. 1, str. 58-68, Leden 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Abstrakt Úvod rychlého algoritmu Fourierovy transformace vedlo k vývoji techniky kódování obrazu Fourierovy transformace, při níž se dvojrozměrná Fourierova transformace obrazu přenáší spíše přes kanál než samotný obraz. Toto odchýlení dále vedlo k související technice kódování obrazu ve kterém je obraz transformován operátorem Hadamardovy matice. Hadamardova matice je čtvercové pole plus a minus, jejichž řádky a sloupce jsou navzájem kolmé. Vysokorychlostní výpočetní algoritmus, podobný rychlému Fourierovi Byl vyvinut algoritmus transformace, který provádí Hadamardovu transformaci. Vzhledem k tomu, že u Hadamardovy transformace jsou vyžadována pouze sčítání a odčítání reálných čísel, je ve srovnání s Fourierovou transformací komplexního čísla možná výhoda rychlosti řádově. Přenos Hadamardovy transformace obrazu, spíše než prostorová reprezentace obrazu, poskytuje potenciální toleranci k chybám kanálu a možnost sníženého přenosu šířky pásma.

Komentáře

• Děkuji za tento odkaz, určitě si ho přečtu, ale může to chvíli trvat. Z abstraktu se zdá, že Hadamardovu transformaci lze použít jako … náhražku? … Fourierovy transformace, zčásti proto, že je výpočetně velmi efektivní, ale možná i z jiného důvodu? Jaký byl váš obecný názor na to?
• Pomocí hadamardové transformace jsme schopni přenést kódovanou verzi obrazu a poté jej rekonstruovat u přijímače. V tomto konkrétním případě autor používá transformaci za účelem soustředění energie signálu v užším pásmu než původní obraz, takže je méně ovlivněna šumem a může být rekonstruována pomocí inverzní hadamard na přijímači.
• Hmm, ano, právě jsem dočetl článek – zdá se, že Hadamardova transformace je jen rychlejší alternativou k Fourierově transformaci, ale nic jiného nevyniká. Šetří energii a entropii atd., Ale víceméně se jeví jako FFT.
• Dělá Hadamard Transform dostatečně dobrou (i když ne lepší) práci proti jiným transformacím, jako je DFT nebo dokonce DCT. Být rychlý je dobrý, ale může to opravdu udělat tak dobrou kompresi, jak říká DCT, je skutečná otázka. Většina konvenčních standardů JPEG, MPEGx to ‚ zcela nepoužívá BTW.

Chtěl bych dodat, že jakoukoli m-transformaci (Toeplitzovu matici generovanou m-sekvencí) lze rozložit na

P1 * WHT * P2

kde WHT je Walsh Hadamard Transform, P1 a P2 jsou permutace (ref: http://dl.acm.org/citation.cfm?id=114749 ).

m-transformace se používá pro řadu věcí: (1) identifikace systému, když je systém sužován hlukem, a (2) virtuální (1) identifikace fázového zpoždění v systému, který je sužován šum

pro (1), m-transformace obnoví jádra systému, když je stimulem m-sekvence, což je užitečné v neurofyziologii (např. http://jn.physiology.org/content/99/1/367.full a další), protože je to vysoký výkon pro širokopásmový signál.

Pro (2) je Gold kód vytvořen z m-sekvencí (http://en.wikipedia.org/wiki/Gold_code).

Jsem docela rád, že jsem svědkem oživení kolem transformací Walsh-Paley-Hadamard (nebo někdy také Waleymard), viz Jak jsme můžete použít Hadamardovu transformaci při extrakci prvků z obrázku?

Jsou to konkrétní instance funkcí Rademacher. Tvoří ortogonální transformace, které lze, s vynecháním normalizace výkonu, realizovat pouze sčítáním a odčítáním a potenciálně binárními posuny. V zásadě nevyžadují žádné násobení, což umožňuje rychlé výpočty a malé potřeby s plovoucí desetinnou čárkou.

Jejich vektorové koeficienty jsou tvořeny $ \ pm 1 $ , které napodobují binarizovanou verzi sinusových nebo kosinových bází. Uspořádání Walshových vektorů je v sekvenci (místo frekvence), která počítá počet změn znaménka. Užívají si podobné motýlí algoritmy pro ještě rychlejší implementaci.

Walshovy sekvence délky $ 2 ^ n $ lze také interpretovat jako instance haarské vlnky paket.

Jako takové je lze použít v jakékoli aplikaci, kde se používají kosinové / sinusové nebo waveletové báze, s velmi levnou implementací. Na celočíselných datech mohou zůstat celými čísly a umožňují skutečně bezztrátové transformace a kompresi (podobně jako celočíselné DCT nebo binární vlnky nebo binlet). Lze je tedy použít v binárních kódech. Používají se také v kompresním snímání.

Jejich výkon je kvůli své blokové povaze často považován za horší než jiné harmonické transformace přirozených signálů a obrazů. Některé varianty se však stále používají, například pro reverzibilní barevné transformace (RCT) nebo transformace kódování videa s nízkou složitostí ( Transformace s nízkou složitostí a kvantizace v H.264 / AVC ).

Některá literatura:

• Agaian, SS, Hadamardovy matice a jejich aplikace, 1985
• Beauchamp, KG, Walshovy funkce a jejich applications, 1975
• Harmut, HF, Transmission of information by orthogonal functions, 1970
• Algoritmus komprese videa v reálném čase pro Hadamardovu transformaci zpracování (NASA, 196)
• Adaptivní Hadamardův transformátor videa v reálném čase (NASA, 196)

Některé odkazy: Webová stránka

Obecný popis

Pro Gaussovu distribuci

Zpráva

Komentáře

• Je lepší ‚ vysvětlit, proč je každý odkaz dobrý.Dokonce i celý název propojeného dokumentu by byl lepší.
• Zkoušel jsem to, ale software fóra se odlupoval, takže získáte souhrnnou verzi. Pokud chcete styl wiki-police odstranit vše, v každém případě to udělejte.
• Nemyslím si ‚, že je to tolik “ wiki-policing “ v tomto případě pokus o zachování standardu ve formátu Q & A prkno. Jeho cílem není fungovat jako fórum. Zpětná vazba k vašemu příspěvku tedy není o jeho smazání, ale o jeho převzetí, ale také o ujištění, že odpovídá standardu. To je běžné v síti výměny zásobníku. Myslel bych si, že stojí za to upravit příspěvek.