Ce este transforma lui Walsh Hadamard? Cum s-ar putea folosi în procesarea imaginilor?

NASA folosea transformata Hadamard ca bază pentru comprimarea fotografiilor din sondele interplanetare în anii 1960 și începutul anilor „Anii 70. Hadamard este un substitut mai simplu din punct de vedere al calculului pentru transformata Fourier, deoarece nu necesită operații de multiplicare sau divizare (toți factorii sunt plus sau minus unul). Operațiile de înmulțire și împărțire au fost extrem de mari în timp pe computerele mici utilizate la bordul acestor nave spațiale, astfel încât evitarea lor a fost benefică atât în ceea ce privește timpul de calcul cât și consumul de energie. Dar de la dezvoltarea computerelor mai rapide care încorporează multiplicatori cu un singur ciclu și perfecționarea unor algoritmi mai noi precum Transformarea Fourier rapidă, precum și dezvoltarea JPEG, MPEG și alte tipuri de compresie a imaginii, cred că Hadamard a căzut din uz. Cu toate acestea, înțeleg că este posibil să fie organizată o revenire pentru utilizarea în calculul cuantic. (Utilizarea NASA provine dintr-un articol vechi din NASA Tech Briefs; atribuirea exactă nu este disponibilă.)

Comentarii

• Cont istoric fantastic Domnule Peters, mulțumesc pentru aceasta. Puteți extinde la ce / cum vrei să spui că s-ar putea organiza o revenire în calculul cuantic? În ce mod faceți aluzie la aceasta în postarea dvs.?
• Potrivit unui articol din Wikipedia, mulți algoritmi cuantici folosesc transforma Hadamard ca pas inițial, deoarece mapează n qubits la o suprapunere a tuturor celor 2n ortogonale stări în baza cuantică cu greutate egală.
• Eric, poți oferi un link către articolul de pe Wikipedia pe care îl citezi? Dacă da, vă pot accepta răspunsul.
• Sigur. Este en.wikipedia.org/wiki/Hadamard_transform
• Eric, am crezut că este o altă sursă la care te refereai. Niciodata al meu. 🙂

Coeficienții transformatei Hadamard sunt toți +1 sau -1. Prin urmare, Transformarea rapidă Hadamard poate fi redusă la operații de adunare și scădere (fără divizare sau multiplicare). Acest lucru permite utilizarea unui hardware mai simplu pentru a calcula transformarea.

Deci, costul sau viteza hardware-ului poate fi aspectul dorit al transformării Hadamard.

Comentarii

• Vă mulțumim pentru răspuns, dar aș dori să înțeleg transformarea, vă rog? Nu-mi pasă acum de implementarea rapidă. Ce este această transformare? De ce este util? Ce perspectivă ne oferă VS alte transformări wavelet?

Aruncați o privire la această lucrare dacă au acces, am „lipit abstractul aici Pratt, WK; Kane, J .; Andrews, HC;,„ Hadamard transform image coding ”, Proceedings of the IEEE, vol.57, nr.1, pp. 58-68, Ianuarie 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Rezumat Introducere a algoritmului de transformare rapidă Fourier a condus la dezvoltarea tehnicii de codare a imaginii transformatei Fourier prin care transformata Fourier bidimensională a unei imagini este transmisă pe un canal mai degrabă decât imaginea în sine. Această dezvoltare a condus în continuare la o tehnică de codare a imaginii în care o imagine este transformată de un operator de matrice Hadamard. Matricea Hadamard este o matrice pătrată de plus și minus ale căror rânduri și coloane sunt ortogonale între ele. Un algoritm de calcul de mare viteză, similar cu Fourierul rapid a fost dezvoltat algoritmul de transformare, care efectuează transformarea Hadamard. Deoarece sunt necesare doar adunări și scăderi de numere reale cu transformata Hadamard, este posibil un avantaj al vitezei de mărime în comparație cu transformata Fourier a numărului complex. Transmiterea transformării Hadamard a unei imagini, mai degrabă decât reprezentarea spațială a imaginii oferă o toleranță potențială la erorile de canal și posibilitatea transmiterii lățimii de bandă reduse.

Comentarii

• Vă mulțumim pentru acest link, cu siguranță îl voi citi, dar s-ar putea să dureze ceva timp. Doar din abstract, se pare că Transformarea Hadamard poate fi utilizată ca … înlocuitor? … pentru transformata Fourier, în parte pentru că este foarte eficient din punct de vedere al calculului, dar poate și din alt motiv? Care a fost părerea dvs. generală în acest sens?
• Folosind transformata hadamard, putem transmite o versiune codificată a imaginii și apoi o putem reconstrui la receptor. În acest caz, autorul folosește transformarea pentru a concentra energia semnalului într-o bandă mai îngustă decât imaginea originală, astfel încât este mai puțin afectată de zgomot și poate fi reconstituită folosind hadamardul invers la receptor.
• Hmm, da, tocmai am terminat de citit lucrarea – se pare că transformarea Hadamard este doar o alternativă mai rapidă la transformarea fourier, dar nimic altceva nu iese în evidență. Conservă energia și entropia etc., dar mai mult sau mai puțin pare a fi exact ca FFT.
• Transformarea Hadamard face destul de bine (chiar dacă nu mai bine) o treabă împotriva altor transformări precum DFT sau chiar DCT. A fi rapid este bine, dar poate face cu adevărat o compresie la fel de bună precum spunem că DCT este o întrebare reală. Majoritatea standardelor convenționale JPEG, MPEGx nu ‘ o folosesc destul de mult BTW.

Aș dori să adăugăm că orice transformare m (matricea Toeplitz generată de o secvență m) poate fi descompusă în

P1 * WHT * P2

unde WHT este Transformarea Walsh Hadamard, P1 și P2 sunt permutări (ref: http://dl.acm.org/citation.cfm?id=114749 ).

transformarea m este utilizată pentru mai multe lucruri: (1) identificarea sistemului atunci când sistemul este afectat de zgomot și (2) prin virtual de (1) identificarea întârzierii de fază într-un sistem care este afectat de noise

pentru (1), transformata m recuperează nucleul (nucleele) sistemului atunci când stimulul este o secvență m, care este utilă în neurofiziologie (de exemplu, http://jn.physiology.org/content/99/1/367.full și altele) deoarece este de mare putere pentru un semnal de bandă largă.

Pentru (2), codul Gold este construit din secvențe m (http://en.wikipedia.org/wiki/Gold_code).

Sunt destul de bucuros să asist la o renaștere în jurul transformărilor Walsh-Paley-Hadamard (sau uneori numite Waleymard), vezi pot folosi transformarea Hadamard în extragerea caracteristicilor dintr-o imagine?

Sunt o instanță specială a funcțiilor Rademacher. Ele formează transformări ortogonale care, omițând normalizările de putere, pot fi implementate doar cu adunări și scăderi și schimbări potențiale binare. Practic, nu necesită multiplicare, permițând calcule rapide și nevoi mici de virgulă mobilă.

Coeficienții lor vectoriali sunt compuși din $ \ pm 1 $ , care imită o versiune binarizată a sinusului sau a bazelor de cosinus. Ordinea vectorilor Walsh este în secvență (în loc de frecvență) care contează numărul de modificări ale semnelor. Se bucură de algoritmi similari de fluturi pentru o implementare și mai rapidă.

Secvențele Walsh de lungime $ 2 ^ n $ pot fi interpretate și ca instanțe ale unui wavelet Haar pachet.

Ca atare, ele pot fi utilizate în orice aplicație în care sunt utilizate bazele cosinus / sinus sau ondulat, cu o implementare foarte ieftină. Pe datele întregi, ele pot rămâne întregi și permit transformări și compresii cu adevărat fără pierderi (în mod similar cu DCT întreg sau cu undele binare sau binlet). Deci, le puteți folosi în coduri binare. Sunt folosite și în detecția prin compresie.

Performanța lor este adesea considerată mai slabă decât alte transformări armonice ale semnalelor și imaginilor naturale, datorită naturii lor blocante. Cu toate acestea, unele variante sunt încă în uz, cum ar fi transformările de culoare reversibile (RCT) sau transformările de codificare video cu complexitate redusă ( Transformarea și cuantificarea cu complexitate redusă în H.264 / AVC ).

Câteva literaturi:

• Agaian, SS, Matricile Hadamard și aplicațiile lor, 1985
• Beauchamp, KG, funcțiile Walsh și aplicații, 1975
• Harmut, HF, Transmiterea informațiilor prin funcții ortogonale, 1970
• Algoritm de compresie video în timp real pentru transformata Hadamard procesare (NASA, 196)
• Un compresor video adaptabil în timp real adaptabil Hadamard (NASA, 196)

Unele link-uri: Pagina web

Descriere generală

Pentru distribuția Gaussian

Raport

Comentarii

• Este ‘ mai bine dacă puteți da o explicație de ce fiecare link este bun.Chiar și un titlu complet al documentului legat ar fi mai bun.
• Am încercat, dar software-ul forumului s-a descuiat, de aceea veți obține o versiune sumară. Dacă doriți să ștergeți totul în stilul wiki-police, faceți totul.
• Nu ‘ nu cred că este atât de mult ” wiki-policing ” în acest caz ca încercarea de a menține un standard pe formatul Q & A în acest sens bord. Obiectivul său nu este să funcționeze ca un forum. Așadar, feedback-ul cu privire la contribuția dvs. nu se referă la ștergerea acestuia, ci la luarea la bord, ci și la asigurarea conformității cu standardul. Acest lucru este comun în întreaga rețea de schimb de stive. Aș crede că merită să editați postarea.