Mikä on Walsh Hadamard -muunnos? Kuinka sitä voitaisiin käyttää kuvankäsittelyssä?

NASA käytti Hadamard-muunnosta pohjana valokuvien pakkaamiseen planeettojen välisistä koettimista 1960-luvulla ja aikaisin ”70-luku. Hadamard on laskennallisesti yksinkertaisempi korvike Fourier-muunnokselle, koska se ei vaadi kertolasku- tai jakooperaatioita (kaikki tekijät ovat plus tai miinus yksi). Kerro ja jaa -operaatiot olivat erittäin aikaa vieviä näissä avaruusaluksissa käytetyissä pienissä tietokoneissa, joten niiden välttäminen oli hyödyllistä sekä laskenta-ajan että energiankulutuksen kannalta. Mutta koska nopeammat tietokoneet, joissa on yksisykliset kertoimet, ja uudempien algoritmien, kuten nopean Fourier-muunnoksen, kehittäminen sekä JPEG-, MPEG- ja muun kuvan pakkaamisen kehitys, uskon, että Hadamard on pudonnut käytöstä. Ymmärrän kuitenkin, että se saattaa olla paluun palauttaminen käytettäväksi kvanttilaskennassa. (NASAn käyttö on peräisin NASAn teknisten tiedotteiden vanhasta artikkelista; tarkka määritys ei ole käytettävissä.)

Kommentit

• Fantastinen historiallinen kertomus Herra Peters, kiitos se. Voitteko laajentaa sitä, mitä / miten tarkoitatte, että se saattaa järjestää paluun kvanttilaskennassa? Millä tavoin viittaat siihen viestissäsi?
• Wikipedian artikkelin mukaan monet kvanttialgoritmit käyttävät Hadamard-muunnosta alkuvaiheena, koska se kartoittaa n qubitia kaikkien 2n kohtisuorien päällekkäin. ilmaisee kvanttipohjassa yhtä suurella painolla.
• Eric, voitko antaa linkin mainitsemallesi wikipedia-artikkelille? Jos hyväksyt, voin hyväksyä vastauksesi.
• Varmasti. Se on fi.wikipedia.org/wiki/Hadamard_transform
• Eric, luulin sen olevan toinen lähde, johon viittasit. Ei koskaan minun. 🙂

Hadamard-muunnoksen kertoimet ovat kaikki +1 tai -1. Nopea Hadamard-muunnos voidaan tällöin supistaa yhteenlasku- ja vähennysoperaatioihin (ei jakamista tai kertomista). Tämä sallii yksinkertaisemman laitteiston käytön muunnoksen laskemisessa.

Joten laitteistokustannukset tai -nopeus voivat olla Hadamard-muunnoksen toivottavia piirteitä.

Kommentit

• Kiitos vastauksesta, mutta haluaisin ymmärtää muutoksen kiitos? En välitä juuri nyt nopeasta toteutuksesta. Mikä tämä muunnos on? Miksi se on hyödyllinen? Mitä oivalluksia se antaa meille VS: n muille aallonmuutoksille?

Katsokaa tätä paperia, jos pääsyn, olen liittänyt abstraktin tähän Pratt, WK; Kane, J .; Andrews, HC; ”Hadamard transform image coding”, Proceedings of the IEEE, vol.57, no.1, s. 58-68, Tammikuu 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Tiivistelmä Johdanto Nopean Fourier-muunnosalgoritmin käyttö on johtanut Fourier-muunnoskuvakoodaustekniikan kehittämiseen, jossa kuvan kaksiulotteinen Fourier-muunnos lähetetään kanavan kautta itse kuvan sijaan. jossa kuva muunnetaan Hadamard-matriisioperaattorilla. Hadamard-matriisi on neliöryhmä plus- ja miinusrivejä, joiden rivit ja sarakkeet ovat kohtisuorassa toistensa kanssa. Nopea laskennallinen algoritmi, samanlainen kuin nopea Fourier Hadamard-muunnoksen suorittava muunnosalgoritmi on kehitetty. Koska Hadamard-muunnoksessa vaaditaan vain reaalilukujen lisäyksiä ja vähennyksiä, suuruusluokan nopeusetu on mahdollista verrattuna kompleksiluku Fourier-muunnokseen. Kuvan Hadamard-muunnoksen lähettäminen kuvan spatiaalisen esityksen sijasta tarjoaa potentiaalisen sietokyvyn kanavavirheille ja mahdollisuuden vähentää kaistanleveyttä.

Kommentit

• Kiitos tästä linkistä, luen sen varmasti, mutta se saattaa viedä jonkin aikaa. Aivan abstraktilta näyttää siltä, että Hadamard-muunnosta voidaan käyttää Fourier-muunnoksen … korvikkeena? … osittain siksi, että se on laskennallisesti erittäin tehokas, mutta ehkä myös toisesta syystä? Mikä oli yleinen mielipiteesi tästä?
• Hadard-muunnoksen avulla voimme lähettää kuvan koodatun version ja rekonstruoida sen sitten vastaanottimessa. Tässä nimenomaisessa tapauksessa kirjailija käyttää muunnosta keskittämään signaalin energia kapeammalle kaistalle kuin alkuperäinen kuva, jotta kohina vaikuttaa siihen vähemmän ja se voidaan rekonstruoida käyttämällä käänteistä hadamardia vastaanottimessa. li>
• Hmm, kyllä, olen juuri lukenut paperin – näyttää siltä, että Hadamard-muunnos on vain nopeampi vaihtoehto Fourier-muunnokselle, mutta mikään muu ei todellakaan erotu. Se säästää energiaa ja entropiaa jne., Mutta näyttää enemmän tai vähemmän olevan samanlainen kuin FFT.
• Onko Hadamard Transform riittävän hyvää (vaikka eikin parempaa) työtä muita muunnoksia, kuten DFT: tä tai jopa DCT: tä, vastaan. Nopeus on hyvä, mutta voiko se todella tehdä niin hyvän pakkauksen kuin DCT: n sanominen on todellinen kysymys. Useimmat tavanomaiset JPEG-, MPEGx-standardit eivät ’ käytä sitä BTW: llä.

Olen varsin iloinen nähdessäni herätyksen Walsh-Paley-Hadamard (tai joskus kutsutaan Waleymard) muutoksista, katso Kuinka me voivatko käyttää Hadamard-muunnosta kuvan poiminnassa?

Ne ovat erityisiä Rademacher-toimintoja. Ne muodostavat ortogonaalimuunnoksia, jotka voidaan jättää pois tehon normalisoinneista vain lisäämällä ja vähentämällä sekä mahdollisesti binäärisiirroilla. Pohjimmiltaan ne eivät vaadi kertomista, mikä mahdollistaa nopeat laskelmat ja vähän hienoja liukulukujen tarpeita.

Heidän vektorikertoimensa ovat $ \ pm 1 $ , jotka jäljittelevät sini- tai kosinipohjien binarisoitua versiota. Walsh-vektorien järjestys on jaksossa (taajuuden sijasta), joka laskee merkkimuutosten määrän. He nauttivat samankaltaisista perhosalgoritmeista entistä nopeammin.

Walsh-sekvenssit, joiden pituus on $ 2 ^ n $ , voidaan tulkita myös Haar-aallon esiintyminä. paketteja.

Niitä voidaan sellaisenaan käyttää missä tahansa sovelluksessa, jossa käytetään kosini- / sini- tai aaltopohjia, erittäin edullisella toteutuksella. Kokonaislukutiedoissa ne voivat pysyä kokonaislukuna ja sallia todella häviöttömät muunnokset ja pakkaamisen (samalla tavalla kuin kokonaisluku DCT tai binääriset aallot tai binetti). Joten niitä voidaan käyttää binaarikoodeina. Niitä käytetään myös puristustunnistuksessa.

Niiden suorituskykyä pidetään usein heikompana kuin muut luonnollisten signaalien ja kuvien harmoniset muunnokset niiden tukkeutuvan luonteen vuoksi. Joitakin muunnelmia käytetään kuitenkin edelleen, kuten palautuvissa värimuunnoksissa (RCT) tai pienikompleksisissa videokoodausmuunnoksissa ( Pienikompleksinen muunnos ja kvantisointi H.264 / AVC: ssä ).

Joitakin kirjallisuuksia:

• Agaian, SS, Hadamard Matrices and their Applications, 1985
• Beauchamp, KG, Walsh-funktiot ja niiden sovellukset, 1975
• Harmut, HF, Tiedonsiirto ortogonaalisten toimintojen avulla, 1970
• Reaaliaikainen videopakkausalgoritmi Hadamard-muunnokselle käsittely (NASA, 196)
• Reaaliaikainen adaptiivinen Hadamard-muunnosvideokompressori (NASA, 196)

Joitakin linkkejä: verkkosivu

Yleiskuvaus

Gaussin jakelulle

Ilmoita

Kommentit

• Se on ’ parempi, jos pystyt selittämään, miksi kukin linkki on hyvä.Jopa linkitetyn asiakirjan täydellinen otsikko olisi parempi.
• Yritin, mutta foorumiohjelmisto oli hilseilemässä, joten saat yhteenvedon version. Jos haluat wiki-poliisityylin poistaa kaiken, tee kaikin tavoin.
• En usko ’ luulevan, että se on niin paljon ” wiki-poliisi ” tässä tapauksessa yrittää ylläpitää standardia Q & A-muodossa. aluksella. Sen tarkoituksena ei ole toimia foorumina. Joten palautteesi ei koske sen poistamista, vaan sen ottamista mukaan, mutta myös sen varmistamista, että se on standardin mukainen. Tämä on yleistä pinonvaihtoverkossa. Luulen, että kannattaa muokata viestiä.