Wat is de Walsh Hadamard-transformatie? Hoe zou je het kunnen gebruiken bij beeldverwerking?

NASA gebruikte de Hadamard-transformatie als basis voor het comprimeren van fotos van interplanetaire sondes in de jaren 60 en het begin van de “jaren 70. Hadamard is een computationeel eenvoudiger substituut voor de Fourier-transformatie, omdat het geen vermenigvuldiging of deelbewerkingen vereist (alle factoren zijn plus of min één). Vermenigvuldigen en delen waren buitengewoon tijdintensief op de kleine computers die aan boord van die ruimtevaartuigen werden gebruikt, dus het vermijden ervan was zowel in termen van rekentijd als energieverbruik gunstig. Maar sinds de ontwikkeling van snellere computers met multipliers van één cyclus en de perfectie van nieuwere algoritmen zoals de Fast Fourier Transform, en de ontwikkeling van JPEG, MPEG en andere beeldcompressie, denk ik dat Hadamard buiten gebruik is geraakt. Ik begrijp echter dat het een comeback kan zijn voor gebruik in kwantumcomputers. (NASA-gebruik komt uit een oud artikel in NASA Tech Briefs; exacte toeschrijving niet beschikbaar.)

Opmerkingen

• Fantastisch historisch verslag, mijnheer Peters, bedankt voor het. Kun je uitweiden over wat / hoe je bedoelt dat het misschien een terugkeer in quantum computing in gang zet? Op welke manier zinspeelt u er in uw post op?
• Volgens een artikel op Wikipedia gebruiken veel kwantumalgoritmen de Hadamard-transformatie als een eerste stap, omdat het n qubits toewijst aan een superpositie van alle 2n orthogonale staat in de kwantumbasis met gelijk gewicht.
• Eric, kun je een link geven naar het Wikipedia-artikel dat je citeert? Als je dat doet, kan ik je antwoord accepteren.
• Zeker. Het is en.wikipedia.org/wiki/Hadamard_transform
• Eric, ik dacht dat het een andere bron was waarnaar je verwees. Nooit de mijne. 🙂

De coëfficiënten van de Hadamard-transformatie zijn allemaal +1 of -1. De Fast Hadamard Transform kan daarom worden teruggebracht tot optellen en aftrekken (geen delen of vermenigvuldigen). Dit maakt het gebruik van eenvoudiger hardware mogelijk om de transformatie te berekenen.

Dus hardwarekosten of -snelheid kunnen het wenselijke aspect van de Hadamard-transformatie zijn.

Opmerkingen

• Bedankt voor het antwoord, maar ik zou de transformatie graag willen begrijpen? Snelle implementatie kan me nu niet schelen. Wat is deze transformatie? Waarom is het nuttig? Welk inzicht geeft het ons in vergelijking met andere wavelet-transformaties?

Bekijk dit artikel eens als je hebben toegang, ik “heb hier de samenvatting geplakt Pratt, WK; Kane, J .; Andrews, HC;,” Hadamard transform image coding, “Proceedings of the IEEE, vol. 57, nr. 1, blz. 58-68, Jan. 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Samenvatting De introductie van het snelle Fourier-transformatie-algoritme heeft geleid tot de ontwikkeling van de Fourier-transformatie-beeldcoderingstechniek waarbij de tweedimensionale Fourier-transformatie van een afbeelding wordt verzonden via een kanaal in plaats van het beeld zelf. Deze ontwikkeling heeft verder geleid tot een gerelateerde beeldcoderingstechniek waarin een afbeelding wordt getransformeerd door een Hadamard-matrixoperator. De Hadamard-matrix is een vierkante array van plus- en minusen waarvan de rijen en kolommen orthogonaal op elkaar staan. Een rekenalgoritme met hoge snelheid, vergelijkbaar met de snelle Fourier transform-algoritme, dat de Hadamard-transformatie uitvoert, is ontwikkeld. Omdat bij de Hadamard-transformatie alleen optellingen en aftrekkingen van reële getallen nodig zijn, is een snelheidsvoordeel van de orde van grootte mogelijk vergeleken met de Fourier-transformatie met complexe getallen. Het verzenden van de Hadamard-transformatie van een afbeelding in plaats van de ruimtelijke weergave van de afbeelding biedt een potentiële tolerantie voor kanaalfouten en de mogelijkheid van transmissie met verminderde bandbreedte.

Reacties

• Bedankt voor deze link, ik zal hem zeker lezen, maar het kan even duren. Alleen al vanuit het abstracte lijkt het erop dat de Hadamard-transformatie kan worden gebruikt als een … vervanging? … voor de Fourier-transformatie, gedeeltelijk omdat het rekenkundig zeer efficiënt is, maar misschien ook om een andere reden? Wat was uw algemene mening hierover?
• Met behulp van de hadamard-transformatie zijn we in staat om een gecodeerde versie van de afbeelding te verzenden en deze vervolgens bij de ontvanger te reconstrueren. In dit specifieke geval gebruikt de auteur de transformatie om de energie van het signaal te concentreren in een smallere band dan het originele beeld, zodat het minder wordt beïnvloed door ruis en kan worden gereconstrueerd door de inverse hadamard bij de ontvanger te gebruiken.
• Hmm, ja, ik ben net klaar met het lezen van de paper – het lijkt erop dat de Hadamard-transformatie gewoon een sneller alternatief is voor de fourier-transformatie, maar niets anders valt echt op. Het bespaart energie, en entropie enz., Maar lijkt min of meer op de FFT te lijken.
• Doet Hadamard Transform het goed genoeg (zelfs als het niet beter is) tegen andere transformaties zoals DFT of zelfs DCT. Snel zijn is goed, maar kan het echt net zo goed worden gecomprimeerd als zeggen dat DCT echt de vraag is. De meeste conventionele standaarden JPEG, MPEGx gebruiken ‘ ze trouwens niet helemaal.

Zou hieraan willen toevoegen dat elke m-transformatie (Toeplitz-matrix gegenereerd door een m-reeks) kan worden ontleed in

P1 * WHT * P2

waarbij WHT is de Walsh Hadamard-transformatie, P1 en P2 zijn permutaties (ref: http://dl.acm.org/citation.cfm?id=114749 ).

m-transform wordt voor een aantal dingen gebruikt: (1) systeemidentificatie wanneer het systeem wordt geplaagd door ruis en (2) door virtueel (1) identificeren van fasevertraging in een systeem dat wordt geplaagd door ruis

voor (1), herstelt m-transform de systeemkernel (s) wanneer de stimulus een m-reeks is, wat handig is in de neurofysiologie (bijv. http://jn.physiology.org/content/99/1/367.full en anderen) omdat het een hoog vermogen is voor een breedbandsignaal.

Voor (2) is Gold-code opgebouwd uit m-reeksen (http://en.wikipedia.org/wiki/Gold_code).

Ik ben heel blij getuige te zijn van een heropleving rond de Walsh-Paley-Hadamard (of ook wel Waleymard genoemd) transformaties, zie Hoe we kan de Hadamard-transformatie gebruiken bij het extraheren van objecten uit een afbeelding?

Dit zijn specifieke instanties van Rademacher-functies. Ze vormen orthogonale transformaties die, met weglating van machtsnormalisaties, kunnen worden geïmplementeerd met alleen optellen en aftrekken, en mogelijk binaire verschuivingen. In principe hebben ze geen vermenigvuldiging nodig, waardoor snelle berekeningen en weinig luxe drijvende-kommabehoeften mogelijk zijn.

Hun vectorcoëfficiënten zijn gemaakt van $ \ pm 1 $ , die een gebinariseerde versie van sinus- of cosinusbasissen nabootsen. De volgorde van Walsh-vectoren is in sequentie (in plaats van frequentie) die het aantal tekenwisselingen telt. Ze gebruiken vergelijkbare vlinderalgoritmen voor een nog snellere implementatie.

Walsh-reeksen met lengte $ 2 ^ n $ kunnen ook worden geïnterpreteerd als instanties van een Haar-wavelet packet.

Als zodanig kunnen ze worden gebruikt in elke toepassing waar cosinus / sinus- of waveletbases worden gebruikt, met een zeer goedkope implementatie. Op integer-data kunnen ze integer blijven en werkelijk verliesloze transformaties en compressie mogelijk maken (vergelijkbaar met integer DCT of binaire wavelets of binlet). Je kunt ze dus in binaire codes gebruiken. Ze worden ook gebruikt bij compressieve detectie.

Hun prestatie wordt vaak als slechter beschouwd dan andere harmonische transformaties op natuurlijke signalen en beelden, vanwege hun blokkerige karakter. Sommige varianten zijn echter nog steeds in gebruik, zoals voor omkeerbare kleurtransformaties (RCT) of low-complexity videocoderingstransformaties ( Low-complexity transformatie en kwantisering in H.264 / AVC ).

Wat literatuur:

• Agaian, SS, Hadamard Matrices and Their Applications, 1985
• Beauchamp, KG, Walsh-functies en hun applicaties, 1975
• Harmut, HF, Overdracht van informatie door orthogonale functies, 1970
• Real-time videocompressie-algoritme voor Hadamard-transformatie processing (NASA, 196)
• Een real-time adaptieve Hadamard-transformatie-videocompressor (NASA, 196)

Enkele links: Webpagina

Algemene beschrijving

Voor Gaussiaanse distributie

Rapport

Opmerkingen

• Het is ‘ beter als je kunt uitleggen waarom elke link goed is.Zelfs een volledige titel van het document waarnaar gelinkt wordt, zou beter zijn.
• Ik heb het geprobeerd, maar de forumsoftware was aan het mislukken, daarom krijg je een samenvattende versie. Als je de stijl van wiki-politie wilt, verwijder alles dan.
• Ik denk niet dat ‘ niet dat het zo is ” wiki-policing ” in dit geval als een poging om een standaard te handhaven op het formaat van Q & A op dit bord. Het doel is niet om als forum te functioneren. De feedback op uw bijdrage gaat dus niet over het verwijderen ervan, het gaat erom dat u het meeneemt, maar ook om ervoor te zorgen dat het voldoet aan de norm. Dit is gebruikelijk in het stapeluitwisselingsnetwerk. Ik zou denken dat het de moeite waard is om het bericht te bewerken.