Cosè la trasformazione di Walsh Hadamard? Come si potrebbe usarlo nellelaborazione delle immagini?

La NASA usava la trasformata di Hadamard come base per comprimere fotografie da sonde interplanetarie durante gli anni 60 e allinizio “Anni 70. Hadamard è un sostituto computazionalmente più semplice della trasformata di Fourier, poiché non richiede operazioni di moltiplicazione o divisione (tutti i fattori sono più o meno uno). Le operazioni di moltiplicazione e divisione erano estremamente dispendiose in termini di tempo sui piccoli computer utilizzati a bordo di quei veicoli spaziali, quindi evitarle era vantaggioso sia in termini di tempo di calcolo che di consumo energetico. Ma dallo sviluppo di computer più veloci che incorporano moltiplicatori a ciclo singolo e dalla perfezione di algoritmi più recenti come Fast Fourier Transform, nonché dallo sviluppo di JPEG, MPEG e altre compressioni di immagini, credo che Hadamard sia caduto in disuso. Tuttavia, capisco che potrebbe rappresentare un ritorno per luso nellinformatica quantistica. (Lutilizzo della NASA proviene da un vecchio articolo in NASA Tech Briefs; lattribuzione esatta non è disponibile.)

Commenti

• Fantastico resoconto storico Mr Peters, grazie per esso. Puoi approfondire cosa / come intendi dire che potrebbe mettere in scena un ritorno nellinformatica quantistica? In che modo alludi ad essa nel tuo post?
• Secondo un articolo su Wikipedia, molti algoritmi quantistici usano la trasformata di Hadamard come passo iniziale, poiché mappa n qubit a una sovrapposizione di tutti i 2n ortogonali afferma in base quantistica con uguale peso.
• Eric, puoi fornire un collegamento allarticolo di wikipedia che citi? Se lo fai, posso accettare la tua risposta.
• Sicuramente. È en.wikipedia.org/wiki/Hadamard_transform
• Eric, pensavo fosse unaltra fonte a cui ti riferivi. Mai mio. 🙂

I coefficienti della trasformata di Hadamard sono tutti +1 o -1. La Trasformata Rapida di Hadamard può quindi essere ridotta a operazioni di addizione e sottrazione (nessuna divisione o moltiplicazione). Ciò consente luso di hardware più semplice per calcolare la trasformazione.

Quindi il costo o la velocità dellhardware può essere laspetto desiderabile della trasformata di Hadamard.

Commenti

• Grazie per la risposta ma vorrei capire la trasformazione per favore? In questo momento non mi interessa limplementazione rapida. Cosè questa trasformazione? Perché è utile? Che cosa ci fornisce rispetto ad altre trasformazioni wavelet?

Dai unocchiata a questo documento se hanno accesso, ho incollato labstract qui Pratt, WK; Kane, J .; Andrews, HC;, “Hadamard transform image coding,” Proceedings of the IEEE, vol.57, no.1, pp. 58- 68, Gennaio 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Abstract Lintroduzione dellalgoritmo della trasformata di Fourier veloce ha portato allo sviluppo della tecnica di codifica dellimmagine della trasformata di Fourier in base alla quale la trasformata di Fourier bidimensionale di unimmagine viene trasmessa su un canale anziché sullimmagine stessa. Questo sviluppo ha ulteriormente portato a una tecnica di codifica dellimmagine correlata in cui unimmagine viene trasformata da un operatore di matrice Hadamard. La matrice di Hadamard è una matrice quadrata di più e meno le cui righe e colonne sono ortogonali luna allaltra. Un algoritmo di calcolo ad alta velocità, simile al veloce Fourier è stato sviluppato lalgoritmo di trasformazione, che esegue la trasformazione di Hadamard. Poiché con la trasformata di Hadamard sono necessarie solo addizioni e sottrazioni di numeri reali, è possibile un vantaggio in termini di velocità dellordine di grandezza rispetto alla trasformata di Fourier dei numeri complessi. La trasmissione della trasformata di Hadamard di unimmagine piuttosto che la rappresentazione spaziale dellimmagine fornisce una potenziale tolleranza agli errori di canale e la possibilità di una trasmissione a larghezza di banda ridotta.

Commenti

• Grazie per questo collegamento, lo leggerò sicuramente, ma potrebbe volerci del tempo. Solo dallastratto, sembra che la trasformata di Hadamard possa essere utilizzata come … sostituto? … per la trasformata di Fourier, in parte perché è computazionalmente molto efficiente, ma forse anche per un altro motivo? Qual è stata la tua opinione generale su questo?
• Usando la trasformata di hadamard siamo in grado di trasmettere una versione codificata dellimmagine e poi ricostruirla al ricevitore. In questo caso particolare lautore sta utilizzando la trasformata per concentrare lenergia del segnale in una banda più stretta rispetto allimmagine originale, quindi è meno influenzata dal rumore e può essere ricostruita utilizzando il hadamard inverso sul ricevitore.
• Hmm, sì, ho appena finito di leggere larticolo – sembra che la trasformata di Hadamard sia solo una alternativa più veloce alla trasformata di Fourier, ma nientaltro spicca davvero. Conserva energia, entropia, ecc., Ma più o meno sembra essere proprio come la FFT.
• Hadamard Transform fa un lavoro abbastanza buono (anche se non migliore) contro altre trasformazioni come DFT o persino DCT. Essere veloci è buono, ma può davvero fare una buona compressione come si dice che DCT sia una vera domanda. La maggior parte degli standard convenzionali JPEG, MPEGx non ‘ t lo usano abbastanza BTW.

Sono molto lieto di assistere a una rinascita intorno alle trasformazioni Walsh-Paley-Hadamard (o talvolta chiamate Waleymard), vedi Come facciamo può usare la trasformazione Hadamard nellestrazione di caratteristiche da unimmagine?

Sono unistanza particolare delle funzioni di Rademacher. Formano trasformazioni ortogonali che possono, omettendo le normalizzazioni di potenza, essere implementate con solo addizioni e sottrazioni e potenzialmente spostamenti binari. Fondamentalmente, non richiedono moltiplicazioni, consentendo calcoli veloci e poche fantasiose esigenze di virgola mobile.

I loro coefficienti vettoriali sono costituiti da $ \ pm 1 $ , che imitano una versione binarizzata di basi seno o coseno. Lordine dei vettori Walsh è in sequenza (invece della frequenza) che conta il numero di cambiamenti di segno. Godono di algoritmi a farfalla simili per unimplementazione ancora più rapida.

Le sequenze Walsh di lunghezza $ 2 ^ n $ possono anche essere interpretate come istanze di un wavelet di Haar pacchetto.

In quanto tali, possono essere utilizzati in qualsiasi applicazione in cui vengono utilizzate basi coseno / seno o wavelet, con unimplementazione molto economica. Sui dati interi, possono rimanere interi e consentire trasformazioni e compressioni veramente prive di perdite (analogamente a DCT interi, wavelet binarie o binlet). Quindi è possibile utilizzarli in codici binari. Sono utilizzati anche nel rilevamento compressivo.

Le loro prestazioni sono spesso considerate inferiori rispetto ad altre trasformazioni armoniche su segnali e immagini naturali, a causa della loro natura a blocchi. Tuttavia, alcune varianti sono ancora in uso come per trasformazioni di colore reversibili (RCT) o trasformazioni di codifica video a bassa complessità ( Trasformata e quantizzazione a bassa complessità in H.264 / AVC ).

Un po di letteratura:

• Agaian, SS, Hadamard Matrices and Their Applications, 1985
• Beauchamp, KG, funzioni Walsh e loro applicazioni, 1975
• Harmut, HF, Trasmissione di informazioni tramite funzioni ortogonali, 1970
• Algoritmo di compressione video in tempo reale per trasformata di Hadamard elaborazione (NASA, 196)
• Un compressore video trasformato Hadamard adattivo in tempo reale (NASA, 196)

Alcuni link: Pagina Web

Descrizione generale

Per la distribuzione gaussiana

Rapporto

Commenti

• ‘ è meglio se puoi fornire una spiegazione del motivo per cui ogni link è valido.Anche un titolo completo del documento linkato sarebbe meglio.
• Ho provato ma il software del forum si stava deteriorando, quindi ottieni una versione di riepilogo. Se vuoi cancellare tutto in stile wiki, fallo assolutamente.
• Non ‘ penso che sia così tanto ” wiki-policing ” in questo caso come tentativo di mantenere uno standard sul formato di Q & A su questo tavola. Il suo obiettivo non è quello di fungere da forum. Quindi, il feedback sul tuo contributo non riguarda leliminazione, si tratta di prenderlo a bordo ma anche di assicurarti che sia conforme allo standard. Questo è comune in tutta la rete di scambio di stack. Penso che valga la pena modificare il post.