Vad är Walsh Hadamard Transform? Hur kan man använda det vid bildbehandling?

NASA använde Hadamard-transformen som bas för komprimering av fotografier från interplanetära sonder under 1960-talet och tidigt ”70-talet. Hadamard är ett beräkningsenligt enklare substitut för Fourier-transformen, eftersom den inte kräver multiplikations- eller delningsoperationer (alla faktorer är plus eller minus en). Multiplicera och dela operationer var extremt tidskrävande på de små datorerna som används ombord på dessa rymdfarkoster, så att undvika dem var fördelaktigt både när det gäller beräkningstid och energiförbrukning. Men sedan utvecklingen av snabbare datorer som innehåller encykelmultiplikatorer och perfektion av nyare algoritmer som Fast Fourier Transform, liksom utvecklingen av JPEG, MPEG och annan bildkomprimering, tror jag att Hadamard har gått ur bruk. Men jag förstår att det kan vara en iscensättning för användning i kvantberäkning. (NASA-användningen är från en gammal artikel i NASA Tech Briefs; exakt tillskrivning ej tillgänglig.)

Kommentarer

• Fantastiskt historiskt konto herr Peters, tack för den. Kan du utöka vad / hur du menar att det kan vara en iscensättning i kvantberäkning? På vilket sätt hänvisar du till det i ditt inlägg?
• Enligt en artikel på Wikipedia använder många kvantalgoritmer Hadamard-transformationen som ett inledande steg, eftersom den kartlägger n qubits till en superposition av alla 2n ortogonala anges i kvantbasen med lika vikt.
• Eric, kan du tillhandahålla en länk till wikipedia-artikeln du citerar? Om du gör det kan jag acceptera ditt svar.
• Visst. Det är sv.wikipedia.org/wiki/Hadamard_transform
• Eric, jag trodde det var en annan källa som du hänvisade till. Aldrig min. 🙂

Koefficienterna för Hadamard-transformationen är alla +1 eller -1. Fast Hadamard Transform kan därför reduceras till additions- och subtraktionsoperationer (ingen delning eller multiplicering). Detta möjliggör användning av enklare hårdvara för att beräkna transformationen.

Så hårdvarukostnad eller hastighet kan vara den önskvärda aspekten av Hadamard-transformationen.

Kommentarer

• Tack för svaret men jag skulle vilja förstå transformationen tack? Jag bryr mig inte just nu om snabb implementering. Vad är denna förändring? Varför är det användbart? Vilken insikt ger den oss mot andra wavelet-transformationer?

Ta en titt på det här papperet om du har tillgång, jag har klistrat in abstrakt här Pratt, WK; Kane, J.; Andrews, HC;, ”Hadamard transform image coding,” Proceedings of the IEEE, vol.57, nr 1, s 58-68, Jan 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Sammanfattning Inledningen av den snabba Fourier-transformeringsalgoritmen har lett till utvecklingen av Fourier-transformbildkodningstekniken, varigenom den tvådimensionella Fouriertransformationen av en bild överförs över en kanal snarare än själva bilden. Denna utveckling har vidare lett till en relaterad bildkodningsteknik där en bild transformeras av en Hadamard-matrisoperator. Hadamard-matrisen är en fyrkantig uppsättning med plus- och minus-rader vars rader och kolumner är ortogonala mot varandra. En höghastighetsberäkningsalgoritm, som liknar den snabba Fourier transformeringsalgoritmen, som utför Hadamard-omvandlingen har utvecklats. Eftersom endast reella talstillägg och subtraktioner krävs med Hadamard-transformationen är en storleksordning hastighetsfördel möjlig jämfört med det komplexa antalet Fourier-transform. Att sända Hadamard-transformationen av en bild snarare än den rumsliga representationen av bilden ger en potentiell tolerans för kanalfel och möjligheten till minskad bandbreddsändning.

Kommentarer

• Tack för den här länken, jag kommer säkert att läsa den, men det kan ta lite tid. Bara från abstrakt verkar det som om Hadamard Transform kan användas som en … ersättning för Fourier-transform, delvis för att den är beräkningsmässigt mycket effektiv, men kanske av en annan anledning också? Vad var din allmänna uppfattning om detta?
• Med hjälp av hadamardtransformationen kan vi överföra en kodad version av bilden och sedan rekonstruera den till mottagaren. I detta specifika fall använder författaren transformen för att koncentrera signalens energi i ett smalare band än originalbilden så att den påverkas mindre av brus och kan rekonstrueras genom att använda det inversa hadamardet vid mottagaren. li>
• Hmm, ja, jag har precis läst papperet – det verkar som om Hadamard-transformationen bara är ett snabbare alternativ till Fourier-transformet, men inget annat sticker verkligen ut. Det sparar energi och entropi etc, men mer eller mindre verkar vara precis som FFT.
• Gör Hadamard Transform tillräckligt bra (även om inte bättre) jobb mot andra transformationer som DFT eller till och med DCT. Att vara snabb är bra, men kan det verkligen göra så bra kompression som att säga att DCT är en riktig fråga. De flesta konventionella standarder JPEG, MPEGx använder inte ’ t helt och hållet.

Jag är ganska glad att bevittna en väckelse kring Walsh-Paley-Hadamard (eller ibland kallad Waleymard) omvandlingar, se Hur vi kan du använda Hadamard-transformationen i funktionsextraktion från en bild?

De är en speciell förekomst av Rademacher-funktioner. De bildar ortogonala transformationer som, med undantag av effektnormaliseringar, kan implementeras med endast tillägg och subtrahering och eventuellt binära skift. I grund och botten kräver de ingen multiplicering, vilket möjliggör snabba beräkningar och små snygga behov av flytande punkter.

Deras vektorkoefficienter är gjorda av $ \ pm 1 $ , som efterliknar en binärversion av sinus- eller cosinusbaser. Beställningen av Walsh-vektorer sker i sekvens (istället för frekvens) som räknar antalet teckenändringar. De har liknande fjärilsalgoritmer för ännu snabbare implementering.

Walsh-sekvenser av längd $ 2 ^ n $ kan också tolkas som exempel på en Haar-våg paket.

Som sådan kan de användas i alla applikationer där cosinus / sinus eller wavelet baser används, med en mycket billig implementering. På heltalsdata kan de förbli heltal och tillåta verkligt förlustfria transformationer och komprimering (på samma sätt som heltal DCT eller binära vågor eller binlet). Så man kan använda dem i binära koder. De används också vid komprimeringsavkänning.

Deras prestanda anses ofta vara sämre än andra harmoniska omvandlingar av naturliga signaler och bilder på grund av deras blockerade natur. Vissa varianter används dock fortfarande som för reversibla färgtransformationer (RCT) eller videokodningstransformationer med låg komplexitet ( Transformation och kvantisering med låg komplexitet i H.264 / AVC ).

Lite litteratur:

• Agaian, SS, Hadamard Matrices and Their Applications, 1985
• Beauchamp, KG, Walsh-funktioner och deras applikationer, 1975
• Harmut, HF, Överföring av information med ortogonala funktioner, 1970
• Videokomprimeringsalgoritm i realtid för Hadamard-transform bearbetning (NASA, 196)
• En realtidsadaptiv Hadamard transform-videokompressor (NASA, 196)

Några länkar: Webbsida

Allmän beskrivning

För Gaussisk distribution

Rapportera

Kommentarer

• Det ’ är bättre om du kan ge en förklaring till varför varje länk är bra.Till och med en fullständig titel på det länkade dokumentet skulle vara bättre.
• Jag försökte men forumprogramvaran flakade ut, så du får en sammanfattande version. Om du vill radera allt i wiki-polisstil, gör det på alla sätt.
• Jag tror inte ’ tänker att det är så mycket ” wiki-policing ” i detta fall som att försöka upprätthålla en standard för formatet Q & A om detta styrelse. Målet är inte att fungera som ett forum. Så feedbacken om ditt bidrag handlar inte om att radera det, det handlar om att ta det ombord utan också att se till att det överensstämmer med standarden. Detta är vanligt i hela stack-utbytesnätverket. Jag skulle tro att det är värt att redigera inlägget.