Hva er Walsh Hadamard Transform? Hvordan kan man bruke det i bildebehandling?

NASA brukte Hadamard-transformasjonen som grunnlag for å komprimere fotografier fra interplanetære sonder i løpet av 1960-tallet og tidlig «70 tallet. Hadamard er en beregningsmessig enklere erstatning for Fourier-transformasjonen, siden den ikke krever noen multiplikasjons- eller divisjonsoperasjoner (alle faktorene er pluss eller minus en). Multipliserings- og delingsoperasjoner var ekstremt tidskrevende på de små datamaskinene som ble brukt om bord på romfartøyet, så det var gunstig å unngå dem både når det gjelder beregningstid og energiforbruk. Men siden utviklingen av raskere datamaskiner som inneholder en-syklus multiplikatorer, og perfeksjon av nyere algoritmer som Fast Fourier Transform, samt utviklingen av JPEG, MPEG og annen bildekomprimering, tror jeg Hadamard har falt ut av bruk. Jeg forstår imidlertid at det kan være et iscenesettelse av et comeback for bruk i kvanteberegning. (NASA-bruk er fra en gammel artikkel i NASA Tech Briefs; eksakt attribusjon utilgjengelig.)

Kommentarer

• Fantastisk historisk beretning Peters, takk for den. Kan du utvide hva / hvordan du mener at det kan iscenesette en come back i quantum computing? På hvilken måte henviser du til det i innlegget ditt?
• I følge en artikkel i Wikipedia bruker mange kvantealgoritmer Hadamard-transformasjonen som et innledende trinn, siden den kartlegger n qubits til en superposisjon av alle 2n ortogonale fastslår i kvantegrunnlaget med lik vekt.
• Eric, kan du gi en lenke til wikipedia-artikkelen du siterer? Hvis du gjør det, kan jeg godta svaret ditt.
• Sikkert. Det er no.wikipedia.org/wiki/Hadamard_transform
• Eric, jeg trodde det var en annen kilde du refererte til. Aldri min. 🙂

Koeffisientene til Hadamard-transformasjonen er alle +1 eller -1. Fast Hadamard Transform kan derfor reduseres til addisjon og subtraksjon (ingen deling eller multiplisering). Dette tillater bruk av enklere maskinvare for å beregne transformasjonen.

Så maskinvarekostnad eller hastighet kan være det ønskelige aspektet ved Hadamard-transformasjonen.

Kommentarer

• Takk for svaret, men jeg vil gjerne forstå transformasjonen takk? Jeg bryr meg ikke akkurat nå om rask implementering. Hva er denne transformasjonen? Hvorfor er det nyttig? Hvilken innsikt gir det oss mot andre wavelet-transformasjoner?

Ta en titt på denne artikkelen hvis du har tilgang, jeg har her limt inn 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 Innledningen av den raske Fourier-transformeringsalgoritmen har ført til utviklingen av Fourier-transform-bildekodingsteknikken, der den todimensjonale Fourier-transformasjonen av et bilde overføres over en kanal i stedet for selve bildet. Denne utviklingen har videre ført til en relatert bildekodingsteknikk der et bilde blir transformert av en Hadamard-matriseoperatør. Hadamard-matrisen er et kvadratisk utvalg av pluss og minus de hvis rader og kolonner er ortogonale mot hverandre. En høyhastighets beregningsalgoritme, lik den raske Fourier transformasjonsalgoritme, som utfører Hadamard-transformasjonen, er utviklet. Siden bare reelle talltillegg og subtraksjoner kreves med Hadamard-transformasjonen, er en fordel med størrelsesorden hastighetsfordel mulig sammenlignet med det komplekse tallet Fourier-transform. Overføring av Hadamard-transformasjonen av et bilde i stedet for den romlige representasjonen av bildet gir en potensiell toleranse for kanalfeil og muligheten for redusert båndbreddetransmisjon.

Kommentarer

• Takk for denne lenken, jeg vil absolutt lese den, men det kan ta litt tid. Bare fra det abstrakte ser det ut til at Hadamard Transform kan brukes som en … erstatning for Fourier-transformasjonen, delvis fordi den er beregningsmessig veldig effektiv, men av en annen grunn også? Hva var din generelle oppfatning av dette?
• Ved hjelp av hadamard-transformasjonen kan vi overføre en kodet versjon av bildet og deretter rekonstruere det på mottakeren. I dette spesielle tilfellet bruker forfatteren transformasjonen for å konsentrere signalets energi i et smalere bånd enn det opprinnelige bildet, slik at det blir mindre påvirket av støy og kan rekonstrueres ved å bruke det omvendte hadamard på mottakeren. li>
• Hmm, ja, jeg har nettopp lest ferdig papiret – det virker som om Hadamard-transformasjonen bare er et raskere alternativ til Fourier-transformasjonen, men ingenting annet skiller seg virkelig ut. Det sparer energi og entropi osv., Men mer eller mindre ser ut til å være akkurat som FFT.
• Gjør Hadamard Transform god nok (selv om ikke bedre) jobb mot andre transformasjoner som DFT eller DCT. Å være rask er bra, men kan det virkelig gjøre så god komprimering som å si at DCT er et reelt spørsmål. De fleste konvensjonelle standarder JPEG, MPEGx bruker ikke ‘ t helt og holdent.

Jeg er ganske glad for å være vitne til en vekkelse rundt Walsh-Paley-Hadamard (eller noen ganger kalt Waleymard) transformasjoner, se Hvordan vi kan du bruke Hadamard-transformasjonen i funksjonsutvinning fra et bilde?

De er en spesiell forekomst av Rademacher-funksjoner. De danner ortogonale transformasjoner som, utelatt kraftnormaliseringer, kan implementeres med bare tilføyer og trekker fra, og potensielt binære skift. I utgangspunktet krever de ingen multiplisering, noe som tillater raske beregninger og lite fancy behov for flytende punkt.

Deres vektorkoeffisienter er laget av $ \ pm 1 $ , som etterligner en binarisert versjon av sinus- eller cosinusbaser. Bestillingen av Walsh-vektorer er i sekvens (i stedet for frekvens) som teller antall tegnendringer. De liker lignende sommerfuglalgoritmer for enda raskere implementering.

Walsh-sekvenser av lengde $ 2 ^ n $ kan også tolkes som forekomster av en Haar-wavelet pakke.

Som sådan kan de brukes i alle applikasjoner der cosinus / sinus- eller wavelet-baser brukes, med en veldig billig implementering. På heltallsdata kan de forbli heltall, og tillate virkelig tapsløse transformasjoner og komprimering (på samme måte som heltall DCT eller binære bølger eller binlet). Så man kan bruke dem i binære koder. De brukes også i kompresjonssensing.

Ytelsen deres blir ofte ansett som dårligere enn andre harmoniske transformasjoner på naturlige signaler og bilder på grunn av deres blokkerende natur. Noen varianter er imidlertid fortsatt i bruk som for reversible fargetransformasjoner (RCT) eller videokodingstransformasjoner med lav kompleksitet ( Transformasjon og kvantisering med lav kompleksitet i H.264 / AVC ).

Litt litteratur:

• Agaian, SS, Hadamard Matrices and Their Applications, 1985
• Beauchamp, KG, Walsh-funksjoner og deres applikasjoner, 1975
• Harmut, HF, Overføring av informasjon med ortogonale funksjoner, 1970
• Sanntids videokomprimeringsalgoritme for Hadamard-transform bearbeiding (NASA, 196)
• En sanntidsadaptiv Hadamard transform-videokompressor (NASA, 196)

Noen lenker: Nettside

Generell beskrivelse

For Gaussisk distribusjon

Rapport

Kommentarer

• Det ‘ er bedre hvis du kan gi en forklaring på hvorfor hver lenke er god.Selv en full tittel på det tilknyttede dokumentet ville være bedre.
• Jeg prøvde, men forumprogramvaren flakket ut, og du får derfor en sammendragsversjon. Hvis du vil wiki-politistil slette alt, må du for all del gjøre det.
• Jeg tror ikke ‘ t at det er så mye » wiki-policing » i dette tilfellet som å prøve å opprettholde en standard på formatet Q & A om dette borde. Målet er ikke å fungere som et forum. Så tilbakemeldingen på ditt bidrag handler ikke om å slette det, det handler om å ta det ombord, men også å sørge for at det er i samsvar med standarden. Dette er vanlig i hele stack exchange-nettverket. Jeg vil tro at det er verdt å redigere innlegget.