Trasformata wavelet: determinare esempio di applicazione

L'avvento delle macchine fotografiche digitali a buon mercato ha fatto sì che una gran parte degli abitanti del pianeta, indipendentemente dall'età e dal sesso, ha preso l'abitudine di catturare ogni suo passo e mettere le loro immagini esposte al pubblico nelle reti sociali. Inoltre, se l'archivio fotografico di famiglia in precedenza è stato collocato nello stesso album, oggi si compone di centinaia di immagini. Al fine di facilitare lo stoccaggio e la trasmissione attraverso reti richiedono un'immagine digitale di riduzione del peso. A tal fine, vengono utilizzati metodi che si basano su vari algoritmi, tra cui una trasformata wavelet. Di cosa si tratta, raccontare il nostro articolo.

Che cosa è un'immagine digitale

informazioni visive nel computer è rappresentato in forma di numeri. In termini semplici, una fotografia scattata con un dispositivo digitale, è una tabella in cui le cellule vengono immessi i valori di ciascuna di colore del pixel. Quando si tratta di un'immagine monocromatica, poi vengono sostituiti da valori di luminanza del intervallo [0, 1], dove 0 è usato per indicare al nero, e 1 – bianco. Altri colori sono dati numeri frazionari, ma con essi scomodi da azionare, quindi l'intervallo è estesa e il valore selezionato dalla intervallo tra 0 e 255. Perché è questo? E 'semplice! Con questa scelta nella rappresentazione binaria per codificare la luminanza di ciascun pixel richiede esattamente un byte. E 'ovvio che un sacco di memoria è necessario per memorizzare anche una piccola immagine. Ad esempio, la dimensione dell'immagine di 256 x 256 pixel richiede 8 Kbyte.

Qualche parola su metodi di compressione immagine

Sicuramente tutti hanno visto la scarsa qualità delle immagini in cui ci sono distorsioni sotto forma di rettangoli dello stesso colore, che sono chiamati artefatti. Essi sorgono a seguito della cosiddetta compressione lossy. Si può ridurre in modo significativo il peso delle immagini, tuttavia, sarà inevitabilmente un impatto sulla sua qualità.

Per lossy algoritmi di compressione comprendono:

• JPEG. Questo è di gran lunga uno degli algoritmi più popolari. Si basa sull'impiego di trasformata coseno discreta. In tutta onestà va ricordato che ci sono opzioni per la compressione JPEG senza perdita di dati performante. Questi includono Lossless JPEG e JPEG-LS.
• JPEG 2000. L'algoritmo viene utilizzato su piattaforme mobili, e basa sull'applicazione di una trasformata wavelet discreta.
• compressione frattale. In alcuni casi, permette di ottenere immagini di ottima qualità anche con una forte compressione. Tuttavia, a causa di problemi con la brevettazione di questo metodo continua ad essere esotici.

algoritmi di compressione senza perdita eseguiti da:

• RLE (utilizzata come metodo primario nel formato TIFF, BMP, TGA).
• LZW (usato in formato GIF).
• LZ-Huffman (usata per il formato PNG).

trasformata di Fourier

Prima di passare alla wavelet, ha senso esplorare le relative funzioni, che descrive i coefficienti dell'espansione delle prime informazioni in componenti elementari, cioè. Vibrazioni E. armoniche con frequenze differenti. In altre parole, la trasformata di Fourier – uno strumento unico collegamento mondi discrete e continue.

Ecco come si presenta:

La formula di inversione è scritto come segue:

Che cosa è un wavelet

Dietro a questo nome si nasconde una funzione matematica, che permette di analizzare le diverse componenti di frequenza dei dati di test. Suo grafico è un'ondulazione cui ampiezza diminuisce a 0 distanza dall'origine. Nell'interesse generale sono i coefficienti wavelet determinato segnale integrale.

spettrogrammi wavelet sono diversi dagli spettri di Fourier convenzionale, poiché varie funzioni associate segnali di spettro con la loro componente temporale.

trasformazione wavelet

Questo metodo di conversione del segnale (funzioni) permette di tradurre da un tempo nella rappresentazione tempo-frequenza.

Per wavelet trasformazione era possibile, per la corrispondente funzione wavelet, le seguenti condizioni siano soddisfatte:

• Se per qualche funzione ψ (t) -Fourier trasformare ha la forma

tale condizione deve essere soddisfatta:

Inoltre:

• Wavelet deve avere un'energia finita;
• dovrebbe essere integrabile permanente ed avere supporto compatto;
• wavelet deve essere localizzato sia nella frequenza e nel tempo (spazio).

tipi

Un wavelet continua trasformazione viene utilizzato per i rispettivi segnali. Molto più interessante è il suo analogo discreto. Dopo tutto, può essere utilizzato per l'elaborazione delle informazioni nel computer. Tuttavia, sorge un problema in quanto la formula per una fibra discreto non può essere ottenuta con semplice appropriata formule discretizzazione DNP.

La soluzione a questo problema è stato trovato da Daubechies, che era in grado di scegliere un metodo per costruire una serie di wavelet ortogonali, ciascuno dei quali è definito da un numero finito di coefficienti. In seguito sono stati creati algoritmi veloci, come ad esempio l'algoritmo Malla. Nella sua applicazione a decomporsi o per ripristinare l'ordine richiesto per eseguire operazioni cN, dove N – lunghezza del campione, e con – il numero di coefficienti.

Vayvlet Haar

Per comprimere un'immagine, è necessario trovare una certa regolarità tra i suoi dati, e meglio ancora se sarà lunghe catene di zeri. Questo è dove può essere utile per la trasformata wavelet algoritmo. Tuttavia, continuiamo a rivedere i metodi di lavoro in ordine.

In primo luogo è necessario ricordare che le immagini la luminosità dei pixel adiacenti è di solito caratterizzato da una piccola quantità. Anche se ci sono immagini su siti reali con tagliente, differenze di luminosità di contrasto, questi occupano solo una piccola porzione dell'immagine. Come esempio, assumere la prova noto Lenna scala di grigi. Se prendiamo una matrice di luminanza dei suoi pixel, allora la parte della prima linea apparirà come una sequenza di numeri 154, 155, 156, 157, 157, 157, 158, 156.

è possibile applicare il cosiddetto metodo delta per arrivare zeri ad esso. Per fare questo, mantenere solo il primo numero, e per gli altri prendono solo le differenze di ciascuno di quella precedente con il segno "+" o "-".

Il risultato è una sequenza 154,1,1,1,0,0,1, -2.

Uno svantaggio di delta-codifica è la non-località. In altre parole, è impossibile portare solo una fetta della sequenza e scoprire che la luminosità è codificato, decodificato, se non tutti i valori di fronte a lui.

Per superare questo inconveniente, il numero è diviso in coppie e ogni sono la metà della somma di (v. A) e metà della differenza (v. D), m. F. Per (154,155) (156,157) (157,157) (158,156) hanno (154,5, 0,5) (156.5,0.5) (157,0.0), (157, -1.0). In questo caso, è sempre possibile trovare il valore dei due numeri in una coppia.

In generale, la wavelet trasformata discreta del segnale S, abbiamo:

Questo metodo risulta dal caso discreto di wavelet continua trasformata, Haar e ampiamente usato in vari campi di elaborazione dei dati e la compressione.

compressione

Come già menzionato, una delle applicazioni di trasformata wavelet algoritmo è il metodo di compressione JPEG 2000 utilizzando Haar basato sulla definizione del vettore di due pixel nelle direzioni X e Y vettore (X + Y) / 2 e (X – Y) / 2. È sufficiente moltiplicare il vettore iniziale nella matrice.

Se i punti più, prendono più matrice, che sono disposti su una matrice diagonale H. Di conseguenza, il vettore iniziale indipendentemente dalla sua lunghezza è trasformato in coppie.

filtri

La risultante "semisomma" – sono i valori medi di luminanza dei pixel in coppie. Questo è il valore quando convertito l'immagine dovrebbe dargli una copia, ridotto 2 volte. In questo semisomma media luminosità, t. E. "filtrata" esplosioni casuali di loro valori e agiscono come filtri di frequenza.

Ora cerchiamo di trattare con quelli che mostrano la differenza. Essi sono interpixel "burst" "isolato", rimuovendo il componente costante, cioè. E. "filtrata" valori alle basse frequenze.

Anche dal sopra Haar trasformata wavelet per i "dummy" diventa evidente che si tratta di una coppia di filtri che dividono il segnale in due componenti: l'elevata frequenza e bassa frequenza. semplicemente riunire questi elementi per ottenere il segnale originale.

esempio

Supponiamo di voler comprimere il (immagine di prova Lenna) fotografia. Si consideri l'esempio della trasformata wavelet matrice di luminosità dei pixel. La componente ad alta frequenza di questa immagine è responsabile della visualizzazione dettagli e descrive il rumore. Per quanto riguarda la bassa frequenza, contiene informazioni sulla forma del viso e lisce gradienti di luminosità.

Caratteristiche le foto della percezione umana sono tali che il secondo è componente più importante. Ciò significa che quando compresso una certa parte dei dati ad alta frequenza può essere scartato. Tanto più che ha meno valore è codificato e più compatto.

Per aumentare il grado di compressione può essere applicata più volte Haar trasformazione in dati a bassa frequenza.

L'utilizzo di matrici bidimensionali

Come già accennato, l'immagine digitale nel computer sono in forma di una matrice di valori intensità dei suoi pixel. Quindi, dovremmo essere interessati ad un Haar bidimensionale trasformata wavelet. Per implementare è necessario semplicemente per svolgere la sua conversione dimensionale per ciascuna riga e ciascuna colonna della matrice delle intensità dei pixel nell'immagine.

Valori prossimi allo zero, possono essere scartati senza danni significativi per l'immagine decodificata. Questo processo è noto come quantizzazione. E in questa fase delle informazioni è perduto. Tra l'altro, il numero di fattori nullable può cambiare, regolando così il grado di compressione.

Tutti questi passaggi provocano che la matrice è ottenuto che contiene grandi quantità di 0. dovrebbe essere scritto riga per riga in un file di testo e comprimere qualsiasi archiviazione.

decodifica

La trasformazione inversa nell'immagine sulla seguente algoritmo:

• Si scompatta un archivio;
• vale inversa Haar trasformare;
• L'immagine decodificata viene convertita in una matrice.

I vantaggi rispetto a JPEG

было сказано, что он основан на ДКП. Quando si considera l'algoritmo di Joint Photographic Experts Group è stato detto che si basa su DCT. Questa conversione viene effettuata in blocchi (8 x 8 pixel). Di conseguenza, se una forte compressione sull'immagine ridotta diventa struttura a blocchi apprezzabile. Durante la compressione utilizzando wavelet tale problema è assente. Tuttavia, il rumore può apparire diverso tipo che hanno l'aspetto di increspature intorno ai bordi. Si ritiene che i manufatti simili, in media, meno evidente di "piazze" che vengono creati quando si utilizza l'algoritmo JPEG.

Ora che sapete che cosa wavelets sono quello che sono e quello che uso pratico per loro è stato trovato nel campo della trasformazione e compressione di immagini digitali.