Hvad er Walsh Hadamard Transform? Hvordan kunne man bruge det til billedbehandling?

NASA brugte Hadamard-transformationen som grundlag for komprimering af fotografier fra interplanetære sonder i løbet af 1960erne og tidligt “70erne. Hadamard er en beregningsmæssigt enklere erstatning for Fourier-transformationen, da den ikke kræver multiplikations- eller divisionsoperationer (alle faktorer er plus eller minus en). Multiplikation og opdeling var ekstremt tidskrævende på de små computere, der blev brugt ombord på disse rumfartøjer, så det var en fordel at undgå dem både med hensyn til beregningstid og energiforbrug. Men siden udviklingen af hurtigere computere, der indeholder enkeltcyklusmultiplikatorer og perfektion af nyere algoritmer som Fast Fourier Transform, såvel som udviklingen af JPEG, MPEG og anden billedkomprimering, tror jeg Hadamard er ude af brug. Jeg forstår dog, at det kan være et iscenesættelse af et comeback til brug i quantum computing. (NASA-brugen er fra en gammel artikel i NASA Tech Briefs; nøjagtig tilskrivning ikke tilgængelig.)

Kommentarer

• Fantastisk historisk beretning hr. Peters, tak for det. Kan du udvide om, hvad / hvordan du mener, at det måske iscenesætter et come back i quantum computing? På hvilken måde henviser du til det i dit indlæg?
• Ifølge en artikel i Wikipedia bruger mange kvantealgoritmer Hadamard-transformationen som et indledende trin, da den kortlægger n qubits til en superposition af alle 2n ortogonale angiver kvantegrundlaget med lige stor vægt.
• Eric, kan du give et link til den wikipedia-artikel, du citerer? Hvis du gør det, kan jeg acceptere dit svar.
• Sikkert. Det er da.wikipedia.org/wiki/Hadamard_transform
• Eric, jeg troede, det var en anden kilde, du henviste til. Aldrig min. 🙂

Koefficienterne for Hadamard-transformationen er alle +1 eller -1. Den hurtige Hadamard-transformation kan derfor reduceres til additions- og subtraktionsoperationer (ingen division eller multiplicering). Dette gør det muligt at bruge enklere hardware til at beregne transformationen.

Så hardwareomkostninger eller hastighed kan være det ønskelige aspekt af Hadamard-transformationen.

Kommentarer

• Tak for svaret, men jeg vil gerne forstå transformationen tak? Jeg er ligeglad lige nu med hurtig implementering. Hvad er denne transformation? Hvorfor er det nyttigt? Hvilken indsigt giver det os mod andre wavelet-transformationer?

Se på dette papir, hvis du har adgang, jeg har her indsat det abstrakte 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

Abstrakt Introduktion af den hurtige Fourier-transformeringsalgoritme har ført til udviklingen af Fourier-transform-billedkodningsteknikken, hvorved den to-dimensionelle Fourier-transformation af et billede transmitteres over en kanal snarere end selve billedet. Denne devlopement har yderligere ført til en relateret billedkodningsteknik hvor et billede transformeres af en Hadamard-matrixoperator. Hadamard-matrixen er en firkantet række af plus og minus dem, hvis rækker og kolonner er vinkelrette på hinanden. En højhastigheds beregningsalgoritme, der ligner den hurtige Fourier transformeringsalgoritme, der udfører Hadamard-transformation, er blevet udviklet. Da kun reelle antal tilføjelser og subtraktioner er nødvendige med Hadamard-transformationen, er en størrelsesorden hastighedsfordel mulig sammenlignet med det komplekse tal Fourier-transformation. Transmission af Hadamard-transformationen af et billede snarere end den rumlige repræsentation af billedet giver en potentiel tolerance for kanalfejl og muligheden for reduceret båndbreddetransmission.

Kommentarer

• Tak for dette link, jeg vil helt sikkert læse det, men det kan tage lidt tid. Bare fra det abstrakte ser det ud til, at Hadamard Transform kan bruges som en … erstatning for Fourier-transformationen, delvis fordi den er beregningsmæssigt meget effektiv, men måske af en anden grund også? Hvad var din generelle holdning til dette?
• Ved hjælp af hadamard-transformeringen er vi i stand til at transmittere en kodet version af billedet og derefter rekonstruere det på modtageren. I dette særlige tilfælde bruger forfatteren transformationen til at koncentrere signalets energi i et mere snævert bånd end det originale billede, så det er mindre påvirket af støj og kan rekonstrueres ved hjælp af det omvendte hadamard ved modtageren. li>
• Hmm, ja, jeg er lige færdig med at læse papiret – det ser ud til, at Hadamard-transformationen bare er et hurtigere alternativ til Fourier-transformationen, men intet andet skiller sig virkelig ud. Det sparer energi og entropi osv., Men mere eller mindre ser det ud til at være ligesom FFT.
• Gør Hadamard Transform godt nok (selvom ikke bedre) job mod anden transformation som DFT eller endda DCT. At være hurtig er god, men kan det virkelig gøre så god kompression som at sige, at DCT er et rigtigt spørgsmål. De fleste konventionelle standarder JPEG, MPEGx bruger ‘ det ikke helt BTW.

Jeg er ret glad for at være vidne til en vækkelse omkring Walsh-Paley-Hadamard (eller undertiden kaldet Waleymard) transformationer, se Hvordan vi kan du bruge Hadamard-transformationen til udtrækning af funktioner fra et billede?

De er en særlig forekomst af Rademacher-funktioner. De danner ortogonale transformationer, som, udeladende strømnormaliseringer, kun kan implementeres med tilføjelser og subtraheringer og potentielt binære skift. Dybest set kræver de ingen gang, hvilket tillader hurtige beregninger og små fancy flydende punktbehov.

Deres vektorkoefficienter er lavet af $ \ pm 1 $ , der efterligner en binærversion af sinus- eller cosinusbaser. Ordren af Walsh-vektorer er i sekvens (i stedet for frekvens), der tæller antallet af tegnændringer. De nyder lignende sommerfuglealgoritmer til endnu hurtigere implementering.

Walsh-sekvenser af længde $ 2 ^ n $ kan også fortolkes som forekomster af en Haar wavelet pakke.

Som sådan kan de bruges i enhver applikation, hvor cosinus / sinus- eller wavelet-baser bruges, med en meget billig implementering. På heltalsdata kan de forblive heltal og tillade virkelig tabsfri transformation og komprimering (på samme måde som heltal DCT eller binære bølger eller binlet). Så man kan bruge dem i binære koder. De bruges også til komprimeringsregistrering.

Deres ydeevne betragtes ofte dårligere end andre harmoniske transformationer på naturlige signaler og billeder på grund af deres blokerende natur. Nogle varianter er dog stadig i brug som til reversible farvetransformationer (RCT) eller videokodningstransformationer med lav kompleksitet ( Transformation og kvantisering med lav kompleksitet i H.264 / AVC ).

Litteratur:

• Agaian, SS, Hadamard Matrices and Their Applications, 1985
• Beauchamp, KG, Walsh-funktioner og deres applikationer, 1975
• Harmut, HF, transmission af information med ortogonale funktioner, 1970
• Realtidskomprimeringsalgoritme til Hadamard-transformation behandling (NASA, 196)
• En realtidsadaptiv Hadamard-transformeringsvideokompressor (NASA, 196)

Nogle links: Webside

Generel beskrivelse

Til Gaussisk distribution

Rapport

Kommentarer

• Det ‘ er bedre, hvis du kan give en forklaring på, hvorfor hvert link er godt.Selv en fuld titel på det linkede dokument ville være bedre.
• Jeg prøvede, men forumsoftwaren flakede ud, så du får en oversigtsversion. Hvis du vil wiki-politistil slette alt, skal du under alle omstændigheder gøre det.
• Jeg tror ikke ‘ Jeg tror ikke, det er så meget ” wiki-policing ” i dette tilfælde som forsøg på at opretholde en standard på formatet Q & A om dette bestyrelse. Dets mål er ikke at fungere som et forum. Så feedbacken på dit bidrag handler ikke om at slette det, det handler om at tage det ombord, men også at sikre, at det overholder standarden. Dette er almindeligt på tværs af stack-udvekslingsnetværket. Jeg ville tro, at det er værd at redigere indlægget.