file 17 dicembre 2013 alle 14:09

Reinventare il JPEG

• Algoritmi,
• Elaborazione delle immagini

• Tutorial

Hai capito bene dal titolo che questa non è una descrizione del tutto ordinaria dell'algoritmo JPEG (ho descritto il formato del file in dettaglio nell'articolo). Innanzitutto, il modo scelto di presentare il materiale presuppone che non si sappia nulla non solo di JPEG, ma anche della trasformata di Fourier e della codifica di Huffman. E in generale, non ricordiamo molto delle lezioni. Hanno appena scattato una foto e hanno iniziato a pensare a come comprimerla. Pertanto, ho cercato di esprimere solo l'essenza in un modo accessibile, ma in cui il lettore svilupperà una comprensione sufficientemente profonda e, soprattutto, intuitiva dell'algoritmo. Formule e calcoli matematici: come minimo, solo quelli importanti per capire cosa sta succedendo.

Conoscere l'algoritmo JPEG è molto utile per qualcosa di più della semplice compressione delle immagini. Usa la teoria di elaborazione digitale segnali, analisi matematica, algebra lineare, teoria dell'informazione, in particolare la trasformata di Fourier, codifica senza perdite, ecc. Pertanto, le conoscenze acquisite possono essere utili ovunque.

Se c'è un desiderio, allora propongo di seguire gli stessi passaggi da solo in parallelo con l'articolo. Controlla come il ragionamento di cui sopra è adatto a diverse immagini, prova a fare le tue modifiche all'algoritmo. È molto interessante. Come strumento, posso consigliare una meravigliosa combinazione di Python + NumPy + Matplotlib + PIL (cuscino). Quasi tutto il mio lavoro (inclusa la grafica e l'animazione) è stato svolto utilizzandoli.

Attenzione, traffico! Molte illustrazioni, grafica e animazioni (~ 10 Mb). Ironia della sorte, nell'articolo su JPEG ci sono solo 2 immagini con questo formato su cinquanta.

Qualunque sia l'algoritmo di compressione delle informazioni, il suo principio sarà sempre lo stesso: trovare e descrivere modelli. Più modelli, più ridondanza, meno informazioni. Gli archivisti e i programmatori di solito sono "affilati" per un tipo specifico di informazioni e sanno dove trovarli. In alcuni casi, il motivo è immediatamente visibile, ad esempio un motivo a cielo azzurro. Ogni riga della sua rappresentazione digitale può essere descritta in modo abbastanza accurato da una linea retta.

Ci alleneremo sui gatti procione. L'immagine grigia sopra è presa come esempio. Combina bene sia aree omogenee che contrastanti. E se impariamo a comprimere il grigio, non ci saranno problemi con il colore.

Rappresentazione vettoriale

Innanzitutto, controlliamo quanto sono dipendenti due pixel vicini. È logico presumere che molto probabilmente saranno molto simili. Verifichiamo questo per tutte le coppie dell'immagine. Segnaliamoli sul piano delle coordinate con punti in modo che il valore del punto lungo l'asse X sia il valore del primo pixel, lungo l'asse Y - il secondo. Per la nostra immagine 256 per 256, otteniamo 256 * 256/2 punti:

È prevedibile che la maggior parte dei punti si trovi sulla o vicino alla linea y = x (e sono anche più di quelli che puoi vedere in figura, poiché sono ripetutamente sovrapposti l'uno all'altro e, inoltre, sono traslucidi) . In tal caso, sarebbe più semplice lavorare ruotandoli di 45°. Per fare ciò, è necessario esprimerli in un diverso sistema di coordinate.

I vettori base del nuovo sistema sono ovviamente i seguenti:. Costretto a dividere per una radice di due per ottenere un sistema ortonormale (le lunghezze dei vettori di base sono uguali a uno). È mostrato qui che un certo punto p = (x, y) in nuovo sistema sarà rappresentato come un punto (a 0, a 1). Conoscendo i nuovi coefficienti, possiamo facilmente ottenere i vecchi mediante rotazione inversa. Ovviamente, la prima (nuova) coordinata è la media e la seconda è la differenza tra x e y (ma divisa per la radice di 2). Immagina che ti venga chiesto di lasciare solo uno dei valori: uno 0 o un 1 (ovvero, uguaglia l'altro a zero). È meglio scegliere uno 0, poiché è probabile che il valore di un 1 sia comunque vicino allo zero. Questo è ciò che accade se ripristiniamo l'immagine solo da uno 0:

Ingrandimento 4x:

Questo tipo di compressione non è molto impressionante, ad essere onesti. È meglio dividere l'immagine in triple di pixel allo stesso modo e rappresentarli nello spazio tridimensionale.

Questo è lo stesso grafico, ma con punti diversi visione. Le linee rosse sono gli assi che si sono suggeriti. Corrispondono ai vettori:. Ti ricordo che devi dividere per alcune costanti in modo che le lunghezze dei vettori diventino uguali a uno. Quindi, espandendo su tale base, otteniamo 3 valori uno 0, un 1, un 2 e uno 0 è più importante di un 1 e un 1 è più importante di un 2. Se eliminiamo un 2, il grafico si "appiattisce" nella direzione del vettore e 2. Questo foglio tridimensionale già piuttosto sottile diventerà piatto. Non perderà tanto, ma ci libereremo di un terzo dei valori. Confrontiamo le immagini ricostruite da terzine: (a 0, 0, 0), (a 1, a 2, 0) e (a 0, a 1, a 2). Nell'ultima versione, non abbiamo scartato nulla, quindi otterremo l'originale.

Ingrandimento 4x:

Il secondo disegno è già buono. Le aree nitide sono leggermente smussate, ma nel complesso l'immagine è conservata molto bene. E ora, allo stesso modo, dividiamoci in quattro e definiamo visivamente la base nello spazio quadridimensionale ... Ah, beh, sì. Ma puoi indovinare quale sarà uno dei vettori di base: (1,1,1,1) / 2. Pertanto, puoi guardare la proiezione dello spazio quadridimensionale sullo spazio perpendicolare al vettore (1,1,1,1) per identificarne altri. Ma questo non è il modo migliore.
Il nostro obiettivo è imparare a convertire (x 0, x 1, ..., x n-1) in (a 0, a 1, ..., a n-1) in modo che ogni valore di ai sia meno importante rispetto ai precedenti.... Se possiamo farlo, allora forse gli ultimi valori della sequenza possono essere eliminati del tutto. Le esperienze di cui sopra suggeriscono che è possibile. Ma non si può fare a meno di un apparato matematico.
Quindi, è necessario convertire i punti su una nuova base. Ma prima devi trovare una base adatta. Torniamo al primo esperimento di abbinamento. Considereremo in termini generali. Abbiamo definito i vettori di base:

Espresso attraverso di loro il vettore P:

o in coordinate:

Per trovare uno 0 e un 1 devi proiettare P sul e 0 e e 1 rispettivamente. E per questo devi trovare il prodotto scalare

allo stesso modo:

In coordinate:

Spesso è più conveniente eseguire la trasformazione in forma matriciale.

Quindi A = EX e X = E T A. Questa è una forma bella e conveniente. La matrice E è detta matrice di trasformazione ed è ortogonale, la incontreremo in seguito.

Passare dai vettori alle funzioni.

È conveniente lavorare con vettori di piccole dimensioni. Tuttavia, vogliamo trovare modelli in blocchi di grandi dimensioni, quindi invece di vettori N-dimensionali, è più conveniente operare con le sequenze che rappresentano l'immagine. Chiamerò tali sequenze funzioni discrete, poiché il seguente ragionamento è applicabile alle funzioni continue.
Tornando al nostro esempio, immaginiamo una tale funzione f (i), che è definita in due soli punti: f (0) = x e f (1) = y. Allo stesso modo, impostiamo Funzioni base e 0 (i) ed e 1 (i) in base alle basi e 0 e e uno . Noi abbiamo:

Questa è una conclusione molto importante. Ora, nella frase "scomposizione di un vettore in vettori ortonormali", possiamo sostituire la parola "vettore" con "funzione" e ottenere un'espressione completamente corretta "scomposizione di una funzione in funzioni ortonormali". Non importa che abbiamo ottenuto una funzione così scarsa, poiché lo stesso ragionamento funziona per un vettore N-dimensionale, che può essere rappresentato come una funzione discreta con N valori. E lavorare con le funzioni è più chiaro che con i vettori N-dimensionali. In alternativa, puoi rappresentare tale funzione come un vettore. Inoltre, il solito funzione continua può essere rappresentato come un vettore a dimensione infinita, anche se non più in euclideo, ma nello spazio di Hilbert. Ma non ci andremo, saremo interessati solo alle funzioni discrete.
E il nostro compito di trovare una base si trasforma nel compito di trovare un sistema adatto di funzioni ortonormali. Nel seguente ragionamento si assume di aver già in qualche modo definito un insieme di funzioni base, secondo le quali espanderemo.
Supponiamo di avere una funzione (rappresentata da valori, per esempio) che vogliamo rappresentare come somma di altre. Puoi rappresentare questo processo in forma vettoriale. Per scomporre una funzione, è necessario "proiettarla" a turno sulle funzioni di base. In senso vettoriale, il calcolo della proiezione fornisce l'avvicinamento minimo del vettore originale a un altro in distanza. Tenendo presente che la distanza viene calcolata utilizzando il teorema di Pitagora, quindi una rappresentazione simile sotto forma di funzioni fornisce la migliore approssimazione quadratica media di una funzione a un'altra. Pertanto, ogni coefficiente (k) determina la "vicinanza" della funzione. Più formalmente, k * e (x) è la migliore approssimazione efficace a f (x) tra l * e (x).
L'esempio seguente mostra il processo di approssimazione di una funzione utilizzando solo due punti. Sulla destra c'è la rappresentazione vettoriale.

Per quanto riguarda il nostro esperimento di suddivisione in coppie, possiamo dire che questi due punti (0 e 1 sull'ascissa) sono una coppia di pixel adiacenti (x, y).
Lo stesso, ma con l'animazione:

Se prendiamo 3 punti, dobbiamo considerare i vettori tridimensionali, ma l'approssimazione sarà più accurata. E per una funzione discreta con N valori, è necessario considerare vettori N-dimensionali.
Avendo un insieme di coefficienti ottenuti, si può facilmente ottenere funzione originale sommando le funzioni base assunte con i corrispondenti coefficienti. L'analisi di questi coefficienti può dare molto informazioni utili(a seconda della base). Un caso speciale di queste considerazioni è il principio di espansione in serie di Fourier. Dopotutto, il nostro ragionamento è applicabile a qualsiasi base e, quando si espande in una serie di Fourier, ne viene presa una completamente specifica.

Trasformate discrete di Fourier (DFT)

Nella parte precedente, siamo giunti alla conclusione che sarebbe bello scomporre la funzione in funzioni composte. All'inizio del XIX secolo, anche Fourier ha riflettuto su questo. È vero, non aveva una foto con un procione, quindi ha dovuto indagare sulla distribuzione del calore lungo l'anello di metallo. Poi scoprì che è molto conveniente esprimere la temperatura (e la sua variazione) in ogni punto dell'anello come somma di sinusoidi con periodi diversi. "Fourier ha scoperto (vi consiglio di leggerlo, è interessante) che la seconda armonica decade 4 volte più velocemente della prima, e le armoniche di ordine superiore decadono con una velocità ancora maggiore."
In generale, si è presto scoperto che le funzioni periodiche sono notevolmente scomposte nella somma delle sinusoidi. E poiché ci sono molti oggetti e processi in natura descritti da funzioni periodiche, è apparso un potente strumento per la loro analisi.
Forse uno dei processi periodici più visibili è il suono.

• 1° grafico - tono puro a 2500 hertz.
• 2° - rumore bianco. Cioè, rumore con frequenze uniformemente distribuite su tutta la gamma.
• 3° - la somma dei primi due.

Se mi dessero i valori dell'ultima funzione nel momento in cui non sapevo della serie di Fourier e chiedessero di analizzarli, allora sarei sicuramente in perdita e non sarei in grado di dire nulla di utile. Bene, sì, una specie di funzione, ma come capire che c'è qualcosa ordinato lì? Ma se avessi indovinato di ascoltare ultima funzione, allora l'orecchio captava un tono puro tra il rumore. Sebbene non molto buono, poiché ho selezionato appositamente tali parametri durante la generazione in modo che il segnale si dissolva visivamente nel rumore sul grafico di riepilogo. A quanto ho capito, non è ancora chiaro come l'apparecchio acustico faccia ciò. Tuttavia, recentemente è diventato chiaro che non decompone il suono in sinusoidi. Forse un giorno capiremo come questo accade e appariranno algoritmi più avanzati. Bene, siamo ancora alla vecchia maniera.
Perché non provare a prendere i sinusoidi come base? In effetti, l'abbiamo già fatto. Ricordiamo la nostra scomposizione in 3 vettori base e li rappresentiamo sul grafico:

Sì, sì, lo so che sembra un adattamento, ma con tre vettori è difficile aspettarsi di più. Ma ora è chiaro come ottenere, ad esempio, 8 vettori di base:


Non bene controllo complesso mostra che questi vettori sono perpendicolari a due a due, cioè ortogonali. Ciò significa che possono essere utilizzati come base. La trasformazione su tale base è ampiamente nota ed è chiamata trasformata del coseno discreta (DCT). Penso che dai grafici forniti sia chiaro come si ottiene la formula di trasformazione DCT:

È sempre la stessa formula: A = EX con una base sostituita. I vettori base del DCT specificato (sono anche vettori riga della matrice E) sono ortogonali, ma non ortonormali. Questo dovrebbe essere ricordato quando trasformazione inversa(Non mi soffermerò su questo, ma chi è interessato - il termine 0,5 * a 0 appare nel DCT inverso, poiché il vettore a base zero è più grande degli altri).
L'esempio seguente mostra il processo di approssimazione dei totali parziali ai valori originali. Ad ogni iterazione, la base successiva viene moltiplicata per il coefficiente successivo e aggiunta alla somma intermedia (cioè la stessa dei primi esperimenti sul procione: un terzo dei valori, due terzi).

Tuttavia, nonostante alcuni argomenti sull'opportunità di scegliere una tale base, non ci sono ancora argomenti reali. Infatti, a differenza del suono, l'opportunità di scomporre un'immagine in funzioni periodiche è molto meno ovvia. Tuttavia, l'immagine può essere davvero troppo imprevedibile anche in una piccola area. Pertanto, l'immagine è divisa in pezzi abbastanza piccoli, ma non del tutto minuscoli, perché la scomposizione abbia un senso. In JPEG, l'immagine viene "tagliata" in quadrati 8x8. All'interno di un tale pezzo, le fotografie sono solitamente molto uniformi: lo sfondo più lievi fluttuazioni. Tali aree sono intelligentemente approssimate da sinusoidi.
Beh, diciamo che questo fatto è più o meno intuitivo. Ma c'è una brutta sensazione riguardo alle transizioni di colore nitide, perché le funzioni che cambiano lentamente non ci salveranno. Dobbiamo aggiungere varie funzioni ad alta frequenza che fanno il loro lavoro, ma fianco a fianco su uno sfondo uniforme. Scatta un'immagine 256x256 con due aree contrastanti:

Scomponiamo ogni riga utilizzando DCT, ottenendo così 256 coefficienti per riga.
Quindi lasceremo solo i primi n coefficienti e identifichiamo il resto a zero e, quindi, l'immagine verrà presentata come una somma delle sole prime armoniche:

Il numero nella foto è il numero di quote rimaste. Nella prima immagine è rimasta solo la media. Sulla seconda è già stata aggiunta una sinusoide a bassa frequenza, ecc. A proposito, presta attenzione al bordo: nonostante tutta la migliore approssimazione, 2 strisce sono chiaramente visibili accanto alla diagonale, una è più chiara, l'altra più scura . Parte dell'ultima immagine ingrandita 4 volte:

E in generale, se lontano dal confine vediamo lo sfondo uniforme iniziale, quindi quando ci si avvicina, l'ampiezza inizia a crescere, raggiunge infine un valore minimo e quindi diventa bruscamente massimo. Questo fenomeno è noto come effetto Gibbs.

L'altezza di queste gobbe, che compare in prossimità delle discontinuità della funzione, non diminuirà all'aumentare del numero dei termini nelle funzioni. In una trasformazione discreta, scompare solo se vengono conservati quasi tutti i coefficienti. Più precisamente, diventa invisibile.
L'esempio seguente è completamente simile alla scomposizione di triangoli sopra, ma su un vero procione:


Quando si studia la DCT, si può avere la falsa impressione che siano sempre sufficienti solo pochi primi coefficienti (a bassa frequenza). Questo è vero per molti pezzi di fotografie, quelli i cui valori non cambiano drasticamente. Tuttavia, al confine delle aree contrastanti, i valori "saltano" rapidamente e anche gli ultimi coefficienti saranno grandi. Pertanto, quando si sente parlare della proprietà di conservazione dell'energia del DCT, tenere conto del fatto che si applica a molti tipi di segnali incontrati, ma non a tutti. Ad esempio, pensa a come apparirà una funzione discreta, i cui coefficienti di espansione sono uguali a zero, tranne l'ultimo. Suggerimento: pensa alla scomposizione in forma vettoriale.
Nonostante le carenze, la base scelta è una delle migliori nelle fotografie reali. Poco dopo vedremo un piccolo confronto con gli altri.

DCT contro tutto il resto

Quando ho studiato la questione delle trasformazioni ortogonali, poi, a dire il vero, non ero molto convinto dagli argomenti che tutto intorno è una somma vibrazioni armoniche, quindi devi scomporre le immagini in sinusoidi. O forse alcune funzioni di passaggio sono migliori? Pertanto, stavo cercando i risultati degli studi sull'ottimalità della DCT su immagini reali. Il fatto che "È il DCT che si trova più spesso nelle applicazioni pratiche a causa della proprietà di" densificazione dell'energia "" è scritto ovunque. Questa proprietà significa che la quantità massima di informazioni è contenuta nei primi coefficienti. E perché? Non è difficile condurre una ricerca: ci armiamo di un mucchio di immagini diverse, varie basi note e iniziamo a calcolare la deviazione standard dall'immagine reale per quantità diverse coefficienti. Ho trovato una piccola ricerca nell'articolo (immagini usate) su questa tecnica. Mostra i grafici della dipendenza dell'energia immagazzinata dal numero dei primi coefficienti di espansione in diverse basi. Se hai guardato le classifiche, sei convinto che DCT ottenga costantemente l'onorevole ... ehm ... 3 ° posto. Come mai? Che cos'è la trasformazione KLT? Stavo lodando il DCT, ma qui...

KLT

Tutte le trasformazioni eccetto KLT sono trasformazioni a base costante. E in KLT (trasformazione di Karunen-Loeve) viene calcolata la base ottimale per diversi vettori. Viene calcolato in modo tale che i primi coefficienti diano l'errore quadratico medio più piccolo in totale per tutti i vettori. Abbiamo fatto un lavoro simile in precedenza manualmente, definendo visivamente la base. All'inizio sembra un'idea sensata. Potremmo, ad esempio, dividere l'immagine in piccole sezioni e calcolare una base diversa per ciascuna. Ma non solo appare la preoccupazione per l'archiviazione di questa base, ma anche l'operazione di calcolo è piuttosto laboriosa. E DCT perde solo un po', e inoltre, DCT ha algoritmi di conversione veloci.

DFT

DFT (trasformata discreta di Fourier) - trasformazione discreta Fourier. Questo nome a volte si riferisce non solo a una specifica trasformazione, ma anche all'intera classe di trasformazioni discrete (DCT, DST ...). Diamo un'occhiata alla formula DFT:

Come puoi immaginare, questa è una trasformazione ortogonale con una base complessa. Dal momento che un simile forma complessa si verifica un po 'più spesso del solito, quindi ha senso studiarne la conclusione.
Si potrebbe avere l'impressione che qualsiasi segnale armonico puro (con una frequenza intera) quando DCT scomposto darà solo un coefficiente diverso da zero corrispondente a questa armonica. Non è così, poiché oltre alla frequenza è importante anche la fase di questo segnale. Ad esempio, l'espansione del seno in coseni (analogamente all'espansione discreta) sarà la seguente:

Tanto per un'armonica pura. Ha generato un gruppo di altri. L'animazione mostra i coefficienti DCT di una sinusoide in diverse fasi.


Se ti sembrava che le colonne ruotassero attorno a un asse, allora non ti sembrava.
Quindi ora scomponiamo la funzione nella somma di sinusoidi non solo di frequenze diverse, ma anche spostate in qualche fase. Sarà più conveniente considerare lo sfasamento usando l'esempio di un coseno:

Una semplice identità trigonometrica dà un risultato importante: lo sfasamento è sostituito dalla somma di seno e coseno, presi con i coefficienti cos (b) e sin (b). Ciò significa che puoi scomporre le funzioni nella somma di seno e coseno (senza fasi). Questa è una forma trigonometrica comune. Tuttavia, il complesso viene utilizzato molto più spesso. Per ottenerlo, è necessario utilizzare la formula di Eulero. Basta sostituire le derivate della formula per seno e coseno, otteniamo:


Ora un piccolo sostituto. Il carattere di sottolineatura è un numero coniugato.

Otteniamo l'uguaglianza finale:

c è un coefficiente complesso, la cui parte reale è uguale al coefficiente del coseno e la parte immaginaria è uguale al coefficiente del seno. E l'insieme dei punti (cos (b), sin (b)) è un cerchio. In un tale record, ogni armonica entra nella decomposizione con frequenze sia positive che negative. Pertanto, in varie formule dell'analisi di Fourier, la somma o l'integrazione di solito si verificano da meno a più infinito. Spesso è più conveniente eseguire calcoli in questa forma complessa.
La trasformazione scompone il segnale in armoniche con frequenze da una a N oscillazioni sull'area del segnale. Ma la frequenza di campionamento è N nell'area del segnale. E secondo il teorema di Kotelnikov (noto anche come teorema di Nyquist - Shannon), la frequenza di campionamento dovrebbe essere almeno il doppio della frequenza del segnale. In caso contrario, si ottiene l'effetto della comparsa di un segnale con una frequenza falsa:

La linea tratteggiata mostra un segnale ricostruito in modo errato. Hai incontrato spesso un tale fenomeno nella tua vita. Ad esempio, un divertente movimento delle ruote di un'auto in un video o un effetto moiré.
Ciò fa sembrare che la seconda metà delle ampiezze del complesso N sia composta da altre frequenze. Queste false armoniche della seconda metà sono un'immagine speculare della prima e non contengono informazioni aggiuntive. Quindi, ci rimangono N / 2 coseni e N / 2 seni (che formano una base ortogonale).
Ok, c'è una base. I suoi componenti sono armoniche con un numero intero di oscillazioni nella regione del segnale, il che significa che i valori estremi delle armoniche sono uguali. Più precisamente, sono quasi uguali, poiché l'ultimo valore è preso non proprio dal bordo. Inoltre, ogni armonica è quasi speculare rispetto al suo centro. Tutti questi fenomeni sono particolarmente forti su basse frequenze, che sono importanti per noi durante la codifica. Questo è anche un male perché i confini del blocco saranno evidenti nell'immagine compressa. Illustrerò la base DFT con N = 8. Le prime 2 righe sono componenti del coseno, le ultime sono componenti del seno:

Prestare attenzione alla comparsa di duplicati dei componenti con frequenza crescente.

Puoi pensare mentalmente a come potrebbe essere scomposto un segnale, i cui valori diminuiscono gradualmente da valore massimo all'inizio al minimo alla fine. Solo le armoniche più vicine alla fine potrebbero fare un'approssimazione più o meno adeguata, il che non è molto grande per noi. La figura a sinistra è un'approssimazione di un segnale single-ended. A destra - simmetrico:


Con il primo, le cose vanno molto male.
Quindi si può fare come in DCT: ridurre le frequenze di 2 o un altro numero di volte, in modo che il numero di alcune oscillazioni sia frazionario e i confini siano in fasi diverse? Quindi i componenti saranno non ortogonali. E non c'è niente che tu possa fare al riguardo.

DST

Cosa succede se si usano i seni invece dei coseni in DCT? Otteniamo la trasformata sinusoidale discreta (DST). Ma per il nostro problema, non sono tutti interessanti, poiché sia ​​​​l'intero che le metà dei periodi dei seni sono vicini allo zero ai bordi. Cioè, otteniamo circa la stessa decomposizione inappropriata della DFT.

Tornando a DCT

Come se la cava alle frontiere? Bene. Ci sono antifasi e non ci sono zeri.

Tutto il resto

Trasformate non di Fourier. non descriverò.
WHT - La matrice è composta da soli componenti a gradini con valori -1 e 1.
Haar è anche una trasformata wavelet ortogonale.
Sono inferiori a DCT, ma più facili da calcolare.

Quindi, hai l'idea di elaborare la tua trasformazione. Ricorda questo:

1. La base deve essere ortogonale.
2. Con una linea di base fissa, non puoi battere KLT in qualità di compressione. Nel frattempo, nelle fotografie reali, DCT è quasi quanto di meglio si possa immaginare.
3. Con DFT e DST come esempio, è necessario ricordare i confini.
4. E ricorda che DCT ha un altro buon vantaggio: vicino ai confini dei loro costituenti, i loro derivati ​​sono uguali a zero, il che significa che la transizione tra blocchi adiacenti sarà abbastanza fluida.
5. Le trasformate di Fourier hanno algoritmi veloci con complessità O (N * logN), al contrario del calcolo frontale: O (N 2).

Non sarà facile, vero? Tuttavia, per alcuni tipi di immagini, puoi scegliere una base migliore rispetto a DCT.

Trasformazioni bidimensionali

Ora proviamo a condurre un tale esperimento. Prendi, ad esempio, una fetta di un'immagine.

Il suo grafico 3D:

Passiamo a DCT (N = 32) per ogni riga:

Ora voglio che passi gli occhi su ogni colonna dei coefficienti ottenuti, cioè dall'alto verso il basso. Ricorda che il nostro obiettivo è mantenere i valori il più piccoli possibile, rimuovendo quelli insignificanti. Probabilmente hai indovinato che i valori di ciascuna colonna dei coefficienti ottenuti possono essere scomposti allo stesso modo dei valori dell'immagine originale. Nessuno ci pone limiti nella scelta della matrice di trasformazione ortogonale, ma lo rifaremo con DCT (N = 8):

Il coefficiente (0,0) si è rivelato troppo grande, quindi viene ridotto di 4 volte sul grafico.
Allora, cos'è successo?
L'angolo in alto a sinistra è i coefficienti di espansione più significativi dei coefficienti più significativi.
L'angolo in basso a sinistra è i coefficienti di espansione più insignificanti dei coefficienti più significativi.
L'angolo in alto a destra è i coefficienti di espansione più significativi dei coefficienti più insignificanti.
L'angolo in basso a destra è i coefficienti di espansione più insignificanti dei coefficienti più insignificanti.
È chiaro che il significato dei coefficienti diminuisce se ci si sposta in diagonale dall'angolo in alto a sinistra a quello in basso a destra. Cos'è più importante: (0, 7) o (7, 0)? Cosa significano?
Innanzitutto, per righe: A 0 = (EX T) T = XE T (trasposto, poiché la formula A = EX è per colonne), quindi per colonne: A = EA 0 = EXE T. Se lo calcoli con attenzione, ottieni la formula:

Pertanto, se il vettore viene scomposto in sinusoidi, la matrice in funzioni della forma cos (ax) * cos (by). Ogni blocco 8x8 in JPEG è rappresentato come somma di 64 funzioni della forma:


Wikipedia e altre fonti forniscono tali funzioni in una forma più conveniente:

Pertanto, i coefficienti (0, 7) o (7, 0) sono ugualmente utili.
Tuttavia, in effetti, questa è la solita scomposizione unidimensionale in 64 basi a 64 dimensioni. Tutto quanto sopra si applica non solo alla DCT, ma anche a qualsiasi scomposizione ortogonale. Per analogia, nel caso generale, si ottiene una trasformazione ortogonale N-dimensionale.
Ed ecco la trasformazione bidimensionale del procione (DCT 256x256). Di nuovo con valori azzerati. Numeri - il numero di coefficienti non zero di tutti (il più valori significativi che si trovano nell'area triangolare a sinistra angolo in alto).

Ricorda che il coefficiente (0, 0) si chiama DC, gli altri 63 si chiamano AC.

Scegliere una dimensione del blocco

Un amico chiede: perché in JPEG viene utilizzato il partizionamento 8x8. Dalla risposta postata:

Il DCT tratta il blocco come se fosse periodico e deve ricostruire il salto risultante ai confini. Se prendi blocchi 64x64, "molto probabilmente avrai un enorme salto ai confini e avrai bisogno di molti componenti ad alta frequenza per ricostruirlo con una precisione soddisfacente

Dicono che DCT funziona bene solo su funzioni periodiche e se prendi una dimensione grande, molto probabilmente otterrai un salto da gigante ai confini del blocco e avrai bisogno di molti componenti ad alta frequenza per coprirlo. Questo non è vero! Questa spiegazione è molto simile a DFT, ma non a DCT, poiché copre perfettamente tali salti già con i primi componenti.
La stessa pagina fornisce una risposta dalle FAQ MPEG, con i principali argomenti contro i blocchi di grandi dimensioni:

• Poco profitto quando si divide in grandi blocchi.
• Maggiore complessità computazionale.
• C'è un'alta probabilità di un gran numero di spigoli vivi in ​​un blocco, che causerà l'effetto Gibbs.

Ti suggerisco di indagare da solo. Iniziamo con il primo.


L'asse orizzontale è la frazione dei primi coefficienti non zero. Verticale: la deviazione standard dei pixel dall'originale. La massima deviazione possibile viene presa come unità. Naturalmente, una foto non è chiaramente sufficiente per un verdetto. Inoltre, non sto agendo in modo corretto, sto solo azzerando. Nel JPEG reale, a seconda della matrice di quantizzazione, vengono azzerati solo piccoli valori delle componenti ad alta frequenza. Pertanto, i seguenti esperimenti e conclusioni hanno lo scopo di rivelare superficialmente principi e modelli.
Puoi confrontare la suddivisione in blocchi diversi con il restante 25 percento dei coefficienti (da sinistra a destra, quindi da destra a sinistra):

I blocchi di grandi dimensioni non vengono mostrati, poiché sono visivamente quasi indistinguibili da 32x32. Vediamo ora la differenza assoluta con l'immagine originale (amplificata di 2 volte, altrimenti non si vede proprio nulla):

8x8 dà risultati migliori di 4x4. Un ulteriore aumento delle dimensioni non fornisce più un vantaggio chiaramente visibile. Anche se penserei seriamente al 16x16, invece che all'8x8: aumentando la difficoltà del 33% (circa la difficoltà nel paragrafo successivo), si ottiene un piccolo, ma comunque visibile miglioramento a parità di coefficienti. Tuttavia, la scelta di 8x8 sembra abbastanza ragionevole e, forse, è la media aurea. JPEG è stato pubblicato nel 1991. Penso che questo tipo di compressione fosse molto difficile per i processori dell'epoca.

Secondo discussione. Ricorda che aumentare la dimensione del blocco richiederà più calcolo. Stimiamo quanto. La complessità della conversione alla fronte, come già sappiamo bene: O (N 2), poiché ogni coefficiente è composto da N termini. Ma in pratica si usa algoritmo efficiente Trasformata di Fourier veloce (FFT). La sua descrizione esula dallo scopo di questo articolo. La sua complessità: O (N * logN). Per una scomposizione bidimensionale, è necessario utilizzarla due volte N volte. Quindi la complessità di 2D DCT è O (N 2 logN). Ora confrontiamo le complessità del calcolo di un'immagine con un blocco e diversi piccoli:

• Un blocco (kN) x (kN): O ((kN) 2 log (kN)) = O (k 2 N 2 log (kN))
• k * k blocchi N * N: O (k 2 N 2 logN)

Ciò significa che, ad esempio, una partizione 64x64 è due volte più difficile da calcolare rispetto a una partizione 8x8.

Terzo discussione. Se abbiamo nella foto bordo tagliente colori, questo influenzerà l'intero blocco. Forse è meglio che questo blocco sia abbastanza piccolo, perché in molti blocchi vicini probabilmente un tale confine non esisterà più. Tuttavia, svanire dai confini è abbastanza veloce. Inoltre, il confine stesso avrà un aspetto migliore. Verifichiamo con un esempio grande quantità transizioni di contrasto, ancora, con solo un quarto dei coefficienti:


Sebbene la distorsione dei blocchi 16x16 si estenda oltre l'8x8, le scritte sono più uniformi. Pertanto, solo i primi due argomenti mi hanno convinto. Ma mi piace di più la divisione 16x16.

Quantizzazione

A questo punto, abbiamo un mucchio di matrici 8x8 con coefficienti di trasformata del coseno. È tempo di sbarazzarsi dei coefficienti insignificanti. C'è una soluzione più elegante del semplice azzeramento delle ultime quote come abbiamo fatto sopra. Non ci accontentiamo di questo metodo, poiché i valori non azzerati vengono memorizzati con eccessiva precisione, e tra coloro che sono sfortunati potrebbero essercene di abbastanza importanti. La via d'uscita è usare una matrice di quantizzazione. Le perdite si verificano proprio in questa fase. Ciascun coefficiente di Fourier è diviso per il numero corrispondente nella matrice di quantizzazione. Diamo un'occhiata a un esempio. Prendiamo il primo blocco dal nostro procione e quantizziamolo. La specifica JPEG fornisce una matrice standard:


La matrice standard è di qualità 50% in FastStone e IrfanView. Questa tabella è stata scelta in termini di equilibrio tra qualità e rapporto di compressione. Penso che il valore per il coefficiente DC sia maggiore di quelli vicini a causa del fatto che il DCT non è normalizzato e il primo valore è maggiore di quanto dovrebbe essere. I coefficienti di alta frequenza sono più approssimativi perché meno importanti. Penso che ora tali matrici vengano utilizzate raramente, poiché il deterioramento della qualità è chiaramente evidente. Nessuno vieta di utilizzare la propria tabella (con valori da 1 a 255)
Durante la decodifica, si verifica il processo opposto: i coefficienti quantizzati vengono moltiplicati termine per termine per i valori della matrice di quantizzazione. Ma poiché abbiamo arrotondato i valori, non saremo in grado di ricostruire con precisione i coefficienti di Fourier originali. Maggiore è il numero di quantizzazione, maggiore è l'errore. Pertanto, il coefficiente ricostruito è solo il multiplo più vicino.
Un altro esempio:

E per dessert, considera la qualità del 5% (quando si codifica in Fast Stone).


Quando si ripristina questo blocco, si ottiene solo il valore medio più il gradiente verticale (a causa del valore conservato -1). Ma per esso vengono memorizzati solo due valori: 7 e -1. La situazione non è migliore con altri blocchi, ecco l'immagine ricostruita:

A proposito, circa il 100% di qualità. Come puoi immaginare, in questo caso la matrice di quantizzazione è composta interamente da uno, cioè non si verifica alcuna quantizzazione. Tuttavia, a causa dell'arrotondamento dei coefficienti all'intero, non è possibile ripristinare esattamente l'immagine originale. Ad esempio, un procione ha mantenuto accurato il 96% dei pixel e il 4% differiva di 1/256. Naturalmente, tali "distorsioni" non possono essere viste visivamente.
E puoi vedere le matrici di quantizzazione di varie fotocamere.

codifica

Prima di andare avanti, dobbiamo capire, usando esempi più semplici, come si possono comprimere i valori ottenuti.

Esempio 0(per il riscaldamento)
Immagina una situazione in cui il tuo amico ha dimenticato un pezzo di carta con una lista a casa tua e ora ti chiede di dettarlo al telefono (non ci sono altri modi di comunicazione).
Elenco:

• d9rg3
• wfr43gt
• wfr43gt
• d9rg3
• d9rg3
• d9rg3
• wfr43gt
• d9rg3

Come semplificheresti il ​​tuo compito? Non hai alcun desiderio particolare di dettare dolorosamente tutte queste parole. Ma sono solo due e si ripetono. Pertanto, in qualche modo detti le prime due parole e accetti che l'ulteriore "d9rg3" verrà chiamato la prima parola e "wfr43gt" la seconda. Quindi sarà sufficiente dettare: 1, 2, 2, 1, 1, 1, 2, 1.

Designeremo parole come A, B, C ... e le chiameremo simboli. Inoltre, sotto il simbolo si può nascondere qualsiasi cosa: una lettera dell'alfabeto, una parola o un ippopotamo in uno zoo. La cosa principale è che gli stessi concetti corrispondono agli stessi simboli e quelli diversi corrispondono a quelli diversi. Poiché il nostro compito è la codifica efficiente (compressione), lavoreremo con i bit, poiché queste sono le unità più piccole di rappresentazione dell'informazione. Pertanto, scriveremo l'elenco come ABBAAABA. I bit 0 e 1 possono essere utilizzati al posto di “prima parola” e “seconda parola”, quindi ABBAAABA è codificato come 01100010 (8 bit = 1 byte).

Esempio 1
Codifica ABC.
3m simboli diversi(A, B, C) non c'è modo di abbinare 2 valori possibili bit (0 e 1). E se è così, puoi usare 2 bit per carattere. Ad esempio:

• A: 00
• B: 01
• C: 10

La sequenza di bit associata a un simbolo sarà chiamata codice. ABC sarà codificato in questo modo: 000110.

Esempio 2
Codifica AAAAAABC.
L'utilizzo di 2 bit per carattere A sembra un po' uno spreco. E se lo provassi in questo modo:

• C: 00

Sequenza codificata: 000000100.
Ovviamente questa opzione non è adatta, poiché non è chiaro come decodificare i primi due bit di questa sequenza: come AA o come C? È molto dispendioso utilizzare una sorta di separatore tra i codici, penseremo a come aggirare questo ostacolo in un modo diverso. Quindi, l'errore era dovuto al fatto che il codice C inizia con il codice A. Ma siamo determinati a codificare A con un bit, anche se B e C sono due. Sulla base di questo desiderio, daremo ad A il codice 0. Quindi i codici B e C non possono iniziare con 0. Ma possono iniziare con 1:

• SI: 10
• C: 11

La sequenza è codificata in questo modo: 0000001011. Prova a decodificarla mentalmente. C'è solo un modo per farlo.
Abbiamo sviluppato due requisiti di codifica:

1. Maggiore è il peso di un carattere, più breve dovrebbe essere il suo codice. E viceversa.
2. Per la decodifica univoca, un codice carattere non può iniziare con nessun altro codice carattere.

Ovviamente l'ordine dei simboli non è importante, ci interessa solo la frequenza della loro occorrenza. Pertanto, ad ogni simbolo è associato un certo numero, chiamato peso. Il peso di un carattere può essere un valore relativo, che riflette la proporzione della sua occorrenza, o un valore assoluto, uguale al numero di caratteri. La cosa principale è che i pesi sono proporzionali all'occorrenza dei simboli.

Esempio 3
Consideriamo il caso generale per 4 simboli con qualsiasi peso.

• A: pa
• B: pb
• C: pc
• D: pd

Senza perdita di generalità, poniamo pa ≥ pb ≥ pc ≥ pd. Ci sono solo due codici varianti che sono fondamentalmente diversi in lunghezza:


Quale è preferibile? Per fare ciò, è necessario calcolare le lunghezze ricevute dei messaggi codificati:
W1 = 2 * pa + 2 * pb + 2 * pc + 2 * pd
W2 = pa + 2 * pb + 3 * pc + 3 * pd
Se W1 è minore di W2 (W1-W2<0), то лучше использовать первый вариант:
W1-W2 = pa - (pc + pd)< 0 =>papà< pc+pd.
Se C e D si verificano insieme più spesso di altri, il loro vertice comune riceve il codice più breve di un bit. Altrimenti un bit va al simbolo A. Ciò significa che l'unione dei simboli si comporta come un simbolo indipendente ed ha un peso pari alla somma dei simboli in arrivo.
In generale, se p è il peso di un carattere rappresentato dalla frazione della sua occorrenza (da 0 a 1), allora la migliore lunghezza del codice è s = -log 2 p.
Consideralo su caso semplice(è facile pensarlo come un albero). Quindi, devi codificare caratteri di 2 s con pesi uguali (1/2 s). A causa dell'uguaglianza dei pesi, le lunghezze dei codici saranno le stesse. Ogni personaggio ha bisogno di s bit. Quindi, se il peso di un simbolo è 1/2 s, la sua lunghezza è s. Se il peso viene sostituito da p, otteniamo la lunghezza del codice s = -log 2 p. Ciò significa che se un carattere si verifica due volte meno spesso dell'altro, la lunghezza del suo codice sarà di un bit più lunga. Tuttavia, questa conclusione è facile da trarre se si ricorda che l'aggiunta di un bit consente di raddoppiare il numero di opzioni possibili.
E un'altra osservazione: i due simboli con i pesi più bassi hanno sempre il più alto, ma lunghezze uguali codici. Inoltre, i loro pezzi, tranne l'ultimo, sono gli stessi. Se ciò non fosse vero, almeno un codice potrebbe essere accorciato di 1 bit senza interrompere il prefisso. Quindi, i due simboli con i pesi più piccoli in albero del codice avere un genitore comune a un livello superiore. Puoi vederlo nell'esempio C e D sopra.

Esempio 4
Proviamo a risolvere prossimo esempio, secondo le conclusioni ottenute nell'esempio precedente.

1. Tutti i simboli sono ordinati in ordine decrescente di peso.
2. Gli ultimi due caratteri sono combinati in un gruppo. A questo gruppo viene assegnato un peso pari alla somma dei pesi di questi elementi. Questo gruppo partecipa all'algoritmo insieme ai simboli e ad altri gruppi.

I passaggi vengono ripetuti fino a quando rimane un solo gruppo. All'interno di ciascun gruppo, a un simbolo (o sottogruppo) viene assegnato il bit 0 e l'altro bit 1.
Questo algoritmo è chiamato codifica di Huffman.
L'illustrazione mostra un esempio con 5 caratteri (A: 8, B: 6, C: 5, D: 4, E: 3). Il peso del simbolo (o gruppo) è indicato a destra.

Codifichiamo i coefficienti

Noi torniamo. Ora abbiamo molti blocchi con 64 coefficienti ciascuno che devono essere salvati in qualche modo. La soluzione più semplice è utilizzare un numero fisso di bit per fattore - ovviamente sfortunato. Costruiamo un istogramma di tutti i valori ottenuti (ovvero la dipendenza del numero di coefficienti dal loro valore):

Attenzione: la scala è logaritmica! Puoi spiegare il motivo dell'accumulo di valori superiori a 200? Questi sono coefficienti DC. Poiché sono molto diversi dagli altri, non sorprende che siano codificati separatamente. Ecco solo la DC:

Si noti che la forma del grafico ricorda la forma dei grafici dei primissimi esperimenti di divisione in coppie e terzine di pixel.
In generale, i valori dei coefficienti DC possono variare da 0 a 2047 (più precisamente, da -1024 a 1023, poiché in JPEG, 128 viene sottratto da tutti i valori originali, che corrisponde a sottrarre 1024 da DC) e distribuiti in modo abbastanza uniforme con piccole punte. Quindi la codifica di Huffman non sarà di grande aiuto qui. Immagina anche quanto sarà grande l'albero dei codici! E durante la decodifica, dovrai cercare i valori al suo interno. Questo è molto costoso. Pensiamo oltre.
Il fattore DC è il valore medio di un blocco 8x8. Immagina una transizione sfumata (sebbene non perfetta) che si trova spesso nelle fotografie. I valori DC stessi saranno diversi, ma rappresenteranno una progressione aritmetica. Ciò significa che la loro differenza sarà più o meno costante. Costruiamo un istogramma delle differenze:

Questo è meglio, perché i valori sono generalmente concentrati intorno allo zero (ma l'algoritmo di Huffman darà di nuovo un albero troppo grande). Valori piccoli (di valore assoluto) sono comuni, quelli grandi sono rari. E poiché i valori piccoli occupano pochi bit (se rimuovi gli zeri iniziali), una delle regole di compressione segue bene: assegnare codici brevi a caratteri con pesi grandi (e viceversa). Siamo ancora limitati dal mancato rispetto di un'altra regola: l'impossibilità di una decodifica univoca. In generale, questo problema è risolto nei seguenti modi: confondersi con il codice delimitatore, specificare la lunghezza del codice, utilizzare codici prefisso(li conosci già - questo è il caso in cui nessun codice inizia con un altro). Andiamo secondo la semplice seconda opzione, cioè ogni coefficiente (più precisamente la differenza tra quelli vicini) verrà scritto come segue: (lunghezza) (valore), secondo la seguente targa:

Cioè, i valori positivi sono codificati direttamente nella loro rappresentazione binaria e i valori negativi sono codificati allo stesso modo, ma con l'1 iniziale sostituito da 0. Resta da decidere come codificare le lunghezze. Poiché ci sono 12 valori possibili, è possibile utilizzare 4 bit per memorizzare la lunghezza. Ma è qui che è meglio usare la codifica di Huffman.

I valori con lunghezze 4 e 6 sono i più, quindi hanno ottenuto i codici più brevi (00 e 01).

Può sorgere la domanda: perché, ad esempio, il valore 9 ha il codice 1111110 e non 1111111? Dopotutto, puoi tranquillamente aumentare "9" a un livello più alto, accanto a "0"? Il fatto è che in JPEG non è possibile utilizzare un codice composto solo da uno: questo codice è riservato.
C'è un'altra caratteristica. I codici ottenuti dall'algoritmo di Huffman descritto potrebbero non coincidere in bit con i codici in JPEG, sebbene le loro lunghezze siano le stesse. Usando l'algoritmo di Huffman, si ottengono le lunghezze dei codici e vengono generati i codici stessi (l'algoritmo è semplice: iniziano con codici brevi e li aggiungono uno per uno all'albero il più a sinistra possibile, preservando il prefisso proprietà). Ad esempio, per l'albero sopra, l'elenco viene memorizzato: 0,2,3,1,1,1,1,1. E, naturalmente, viene memorizzato un elenco di valori: 4,6,3,5,7,2,8,1,0,9. Durante la decodifica, i codici vengono generati allo stesso modo.

Ora è l'ordine. Abbiamo capito come vengono archiviati i DC:
[Codice Huffman per DC diff length (in bit)]
dove DC diff = DC current - DC precedente

Guardando AC:

Poiché il grafico è molto simile al grafico per le differenze CC, il principio è lo stesso: [codice di Huffman per la lunghezza CA (in bit)]. Ma non proprio! Poiché la scala sul grafico è logaritmica, non è immediatamente evidente che zero valori circa 10 volte più del valore 2 - il successivo in frequenza. Questo è comprensibile: non tutti sono sopravvissuti alla quantizzazione. Torniamo alla matrice dei valori ottenuti in fase di quantizzazione (usando la matrice di quantizzazione FastStone, 90%).

Poiché ci sono molti gruppi di zeri consecutivi, appare l'idea di registrare solo il numero di zeri nel gruppo. Questo algoritmo di compressione è chiamato RLE (Run-length encoding). Resta da scoprire la direzione del bypass del "cammino consecutivo" - chi c'è dietro chi? Scrivere da sinistra a destra e dall'alto verso il basso non è molto efficace, poiché i coefficienti diversi da zero sono concentrati vicino all'angolo in alto a sinistra e più vicino all'angolo in basso a destra, più zeri.

Pertanto, JPEG utilizza un ordine chiamato "Zig-zag" come mostrato nella figura a sinistra. Questo metodo distingue bene i gruppi di zeri. Nella foto a destra - modo alternativo bypass, non correlato a JPEG, ma con un nome curioso (prova). Può essere utilizzato in MPEG durante la compressione di video interlacciati. La scelta dell'algoritmo di bypass non influisce sulla qualità dell'immagine, ma può aumentare il numero di gruppi di zeri codificati, che alla fine possono influire sulla dimensione del file.
Modifichiamo il nostro record. Per ogni AC diverso da zero - coefficiente:
[Numero di zeri prima dell'AC] [Codice di Huffman per la lunghezza dell'AC (in bit)]
Penso che tu possa dirlo subito: anche il numero di zeri è perfettamente codificato da Huffman! Questa è una risposta molto vicina e buona. Ma puoi ottimizzare un po '. Immagina di avere un certo coefficiente AC, prima del quale c'erano 7 zeri (ovviamente, se lo scriviamo a zigzag). Questi zeri sono lo spirito dei valori che non sono sopravvissuti alla quantizzazione. Molto probabilmente, anche il nostro coefficiente è stato gravemente danneggiato ed è diventato piccolo, il che significa che la sua lunghezza è breve. Quindi, il numero di zeri davanti ad AC e la lunghezza di AC sono grandezze dipendenti. Pertanto, lo scrivono in questo modo:
[Codice Huffman per (Numero di zeri prima di AC, lunghezza AC (in bit)]
L'algoritmo di codifica rimane lo stesso: quelle coppie (numero di zeri davanti ad AC, lunghezza di AC) che ricorrono frequentemente riceveranno codici funzione e viceversa.

Costruiamo un istogramma della dipendenza della quantità per queste coppie e un albero di Huffman.


La lunga "gamma montana" conferma la nostra ipotesi.

Caratteristiche di implementazione in JPEG:
Tale coppia occupa 1 byte: 4 bit per il numero di zeri e 4 bit per la lunghezza dell'AC. 4 bit sono valori da 0 a 15. Per la lunghezza di AC, è più che sufficiente, ma possono esserci più di 15 zeri? Quindi vengono utilizzate più coppie. Ad esempio, per 20 zeri: (15, 0) (5, AC). Cioè, il sedicesimo zero è codificato come un coefficiente diverso da zero. Poiché più vicino alla fine del blocco ci sono sempre pieni di zeri, quindi dopo l'ultimo coefficiente diverso da zero, viene utilizzata la coppia (0,0). Se viene rilevato durante la decodifica, i valori rimanenti sono uguali a 0.

Ho scoperto che ogni blocco è codificato è memorizzato in un file come questo:
[Codice Huffman per la lunghezza delle differenze DC]
[Codice Huffman per (numero di zeri prima di AC 1, lunghezza AC 1]
…
[Codice di Huffman per (numero di zeri prima di AC n, lunghezza AC n]
Dove AC i - coefficienti AC diversi da zero.

Immagine a colori

Il modo in cui viene presentata un'immagine a colori dipende dal selezionato modello di colore... Una soluzione semplice consiste nell'utilizzare RGB e codificare separatamente ciascun canale di colore dell'immagine. Quindi la codifica non differirà dalla codifica dell'immagine grigia, solo il lavoro è 3 volte di più. Ma la compressione dell'immagine può essere aumentata se si ricorda che l'occhio è più sensibile ai cambiamenti di luminosità rispetto al colore. Ciò significa che il colore può essere memorizzato con una perdita maggiore della luminosità. RGB non ha un canale di luminanza separato. Dipende dalla somma dei valori di ciascun canale. Pertanto, un cubo RGB (questa è una rappresentazione di tutti i valori possibili) viene semplicemente "messo" sulla diagonale: più è alto, più è luminoso. Ma questo non è limitato a: il cubo è leggermente schiacciato dai lati e risulta piuttosto un parallelepipedo, ma questo è solo per tenere conto delle peculiarità dell'occhio. Ad esempio, è più suscettibile al verde che al blu. Ecco come è apparso il modello YCbCr.

(Immagine tramite Intel.com)
Y è la componente di luminanza, Cb e Cr sono le componenti della differenza di colore blu e rosso. Pertanto, se vogliono comprimere di più l'immagine, RGB viene convertito in YCbCr e i canali Cb e Cr vengono decimati. Cioè, sono divisi in piccoli blocchi, ad esempio 2x2, 4x2, 1x2 e tutti i valori di un blocco vengono mediati. O, in altre parole, ridurre la dimensione dell'immagine per questo canale di 2 o 4 volte verticalmente e/o orizzontalmente.

Ogni blocco 8x8 è codificato (DCT + Huffman) e le sequenze codificate sono scritte in questo ordine:

È curioso che la specifica JPEG non limiti la scelta del modello, ovvero l'implementazione dell'encoder può dividere arbitrariamente l'immagine in componenti di colore (canali) e ciascuno verrà salvato separatamente. Sono a conoscenza di utilizzare Grayscale (1 canale), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). I primi tre sono supportati da quasi tutti, ma ci sono problemi con gli ultimi a 4 canali. FastStone, GIMP li supportano correttamente e i programmi Windows standard, paint.net estraggono correttamente tutte le informazioni, ma poi buttano fuori 4 canali neri, quindi (ha detto che non lo buttano via, leggi i suoi commenti) mostra di più immagine chiara... Sinistra - JPEG YCbCr classico, JPEG CMYK destro:



Se differiscono nel colore o è visibile solo un'immagine, molto probabilmente hai IE (qualsiasi versione) (UPD. Nei commenti dicono "o Safari"). Puoi provare ad aprire l'articolo in diversi browser.

E un'altra cosa

In poche parole, sulle funzionalità aggiuntive.

Modalità progressiva

Scomponiamo le tabelle dei coefficienti DCT ottenute nella somma delle tabelle (approssimativamente così (DC, -19, -22, 2, 1) = (DC, 0, 0, 0, 0) + (0, -20, -20, 0, 0) + (0, 1, -2, 2, 1)). Innanzitutto, codificheremo tutti i primi termini (come abbiamo già imparato: Huffman e bypass a zigzag), quindi il secondo, ecc. Questo trucco è utile su una Internet lenta, poiché prima vengono caricati solo i coefficienti DC, che viene utilizzato per costruire un'immagine approssimativa con 8x8 "pixel". Quindi i coefficienti AC arrotondati per affinare la figura. Poi correzioni grossolane, poi più precise. E così via. I coefficienti sono arrotondati, poiché nelle prime fasi del caricamento la precisione non è così importante, ma l'arrotondamento ha un effetto positivo sulla lunghezza dei codici, poiché ogni fase utilizza la propria tabella di Huffman.

Modalità senza perdite

Compressione senza perdite. DCT n. Viene utilizzata la previsione del 4° punto di tre vicini. Gli errori di previsione sono codificati da Huffman. Secondo me viene usato un po' più spesso che mai.

Modalità gerarchica

Dall'immagine vengono creati diversi livelli con risoluzioni diverse. Il primo strato grossolano è codificato come al solito, e poi solo la differenza (raffinamento dell'immagine) tra i livelli (finge di essere una wavelet Haar). DCT o Lossless viene utilizzato per la codifica. A mio parere, è usato un po' meno spesso che mai.

Codifica aritmetica

L'algoritmo di Huffman genera codici ottimali per il peso dei caratteri, ma questo è vero solo per una corrispondenza fissa di caratteri con codici. L'aritmetica non ha un legame così rigido, che rende possibile l'uso di codici, per così dire, con un numero frazionario di bit. Si sostiene che riduca le dimensioni del file in media del 10% rispetto a Huffman. Non comune a causa di problemi di brevetto, non supportato da tutti.

Spero che ora tu capisca intuitivamente l'algoritmo JPEG. Grazie per aver letto!

AGGIORNA
offerto per indicare il software utilizzato. Sono lieto di annunciare che tutto è disponibile e gratuito:

• Python + NumPy + Matplotlib + PIL (cuscino)... Lo strumento principale. Trovato emettendo "alternativa gratuita Matlab". Consiglia! Anche se non hai familiarità con Python, in un paio d'ore imparerai come fare calcoli e costruire bellissimi grafici.
• JpegSnoop... Mostra informazioni dettagliate su un file jpeg.
• yEd... Editore grafico.
• Inkscape... Ci sono state delle illustrazioni, come un esempio dell'algoritmo di Huffman. Ho letto alcune lezioni, si è rivelato molto bello.
• Editor di equazioni di Daum... Stavo cercando editor visivo formule, dal momento che non sono molto amico del Latex. Daum Equation - un plugin per Chrome, l'ho trovato molto conveniente. Oltre a scegliere il mouse, puoi modificare Latex.
• FastStone... Non credo ci sia bisogno di presentarlo.
• Picpick. Alternativa gratuita SnagIt. Si siede nel vassoio, screenshot di quello che dicono dove dicono. Inoltre ogni sorta di gadget, come un righello, una pipetta, un goniometro, ecc.

tag:

• jpeg
• dct
• dft
• fourier
• Huffman

Aggiungi i tag

Area di applicazione

Algoritmo JPEG più adatto per comprimere fotografie e dipinti contenenti scene realistiche con transizioni fluide luminosità e colore. JPEG è più ampiamente utilizzato nella fotografia digitale e per l'archiviazione e la trasmissione di immagini tramite Internet.

D'altra parte, JPEG è di scarsa utilità per la compressione di disegni, testo e grafica di caratteri, dove il forte contrasto tra pixel adiacenti porta a notevoli artefatti. Si consiglia di salvare tali immagini in formati lossless come TIFF, GIF o PNG.

JPEG (come altri metodi di compressione distorsiva) non è adatto per comprimere immagini con elaborazione a più fasi, poiché verranno introdotte distorsioni nelle immagini ogni volta che vengono salvati risultati di elaborazione intermedi.

JPEG non dovrebbe essere utilizzato nemmeno nei casi in cui una perdita anche minima è inaccettabile, ad esempio durante la compressione di immagini astronomiche o mediche. In tali casi, può essere consigliata la modalità di compressione JPEG Lossless fornita dallo standard JPEG (che, tuttavia, non è supportata dalla maggior parte dei codec più diffusi) o lo standard di compressione JPEG-LS.

Compressione

Quando è compressa, l'immagine viene convertita da RGB a YCbCr (YUV). Si precisa che lo standard JPEG (ISO/IEC 10918-1) non regola in alcun modo la scelta di YCbCr, consentendo altri tipi di conversione (ad esempio con un numero di componenti diverso da tre), e compressione senza conversione (direttamente a RGB), tuttavia, la specifica JFIF (JPEG File Interchange Format, proposta nel 1991 da C-Cube Microsystems, e ora lo standard de facto) presuppone l'uso della conversione RGB-> YCbCr.

Dopo la conversione RGB-> YCbCr per i canali immagine Cb e Cr responsabili del colore, è possibile eseguire il "sottocampionamento", il che significa che a ciascun blocco di 4 pixel (2x2) del canale di luminanza Y vengono assegnati i valori Cb e Cr medi (schema di decimazione "4: 2: 0"). Allo stesso tempo, per ogni blocco 2x2, invece di 12 valori (4 Y, 4 Cb e 4 Cr), ne vengono utilizzati solo 6 (4 Y e una media di Cb e Cr). Se vengono imposti requisiti maggiori sulla qualità dell'immagine recuperata dopo la compressione, la decimazione può essere eseguita solo in una direzione: verticalmente (schema "4: 4: 0") o orizzontalmente ("4: 2: 2") o no. affatto ("4: 4: 4").

Lo standard consente anche la decimazione con la media di Cb e Cr non per un blocco 2x2, ma per quattro pixel consecutivi (verticalmente o orizzontalmente), ovvero per blocchi 1x4, 4x1 (schema 4: 1: 1), nonché 2x4 e 4x2 (schema "4: 1: 0"). È anche consentito utilizzare diversi tipi di decimazione per Cb e Cr, ma in pratica tali schemi sono usati raramente.

Inoltre, la componente luma Y e le componenti Cb e Cr responsabili del colore sono divise in blocchi di 8x8 pixel. Ciascuno di questi blocchi subisce una trasformata coseno discreta (DCT). I coefficienti DCT ottenuti vengono quantizzati (per Y, Cb e Cr, nel caso generale, vengono utilizzate diverse matrici di quantizzazione) e impacchettati utilizzando la codifica della corsa e i codici di Huffman. Lo standard JPEG consente anche l'uso di una codifica aritmetica molto più efficiente, ma a causa di restrizioni sui brevetti (il brevetto per l'encoder aritmetico QM descritto nello standard JPEG è di proprietà di IBM) è raramente utilizzato nella pratica. L'ultima popolare libreria libjpeg include il supporto per codifica aritmetica, ma la visualizzazione di immagini compresse con questo metodo può essere problematica perché molti visualizzatori non supportano la decodifica.

Le matrici utilizzate per quantizzare i coefficienti DCT sono memorizzate nella parte di intestazione del file JPEG. Di solito sono costruiti in modo che i coefficienti di alta frequenza siano quantizzati più fortemente di quelli di bassa frequenza. Ciò porta all'ingrossamento dei dettagli fini nell'immagine. Maggiore è il rapporto di compressione, più fortemente sono quantizzati tutti i coefficienti.

Quando si salva un'immagine in un file JPEG, viene specificato il parametro di qualità, specificato in alcune unità arbitrarie, ad esempio da 1 a 100 o da 1 a 10. Un numero maggiore di solito corrisponde a una qualità migliore (e una dimensione maggiore file compresso). Tuttavia, anche quando si utilizza la massima qualità(corrispondente ad una matrice di quantizzazione composta da sole uno) l'immagine ricostruita non coinciderà esattamente con quella originale, che è associata sia all'accuratezza finale dell'esecuzione del DCT sia alla necessità di arrotondare i valori di Y, Cb, Cr e coefficienti DCT al numero intero più vicino. La modalità di compressione JPEG senza perdita, che non utilizza DCT, fornisce corrispondenza esatta le immagini restaurate e originali, tuttavia, la sua bassa efficienza (il rapporto di compressione raramente supera i 2) e la mancanza di supporto da parte degli sviluppatori software non hanno contribuito alla popolarità di Lossless JPEG.

Varietà di schemi di compressione JPEG

Lo standard JPEG fornisce due modi principali per rappresentare i dati codificati.

Il più comune, supportato dalla maggior parte dei codec disponibili, è la rappresentazione JPEG sequenziale dei dati, che comporta l'attraversamento sequenziale dell'immagine codificata blocco per blocco da sinistra a destra, dall'alto verso il basso. Le operazioni sopra descritte vengono eseguite su ciascun blocco di immagine codificata e i risultati della codifica vengono inseriti nel flusso di output sotto forma di un singolo "scansione", ovvero un array di dati codificati corrispondente al passaggio sequenziale ("scansionato") Immagine. La modalità di codifica baseline o "baseline" consente solo questa rappresentazione. La modalità estesa (estesa), insieme a quella sequenziale, consente anche la presentazione progressiva dei dati (JPEG progressivo).

Nel caso di JPEG progressivo, i dati compressi vengono scritti nel flusso di output come un insieme di scansioni, ciascuna delle quali descrive l'immagine per intero con un grado di dettaglio crescente. Ciò si ottiene registrando in ciascuna scansione non un set completo di coefficienti DCT, ma solo alcuni di essi: prima - bassa frequenza, nelle scansioni successive - alta frequenza (metodo di selezione spettrale, cioè campioni spettrali), oppure per via sequenziale, da scansione a scansione, affinamento dei coefficienti DCT (metodo "successive approssimazioni", ovvero approssimazioni successive). Questa rappresentazione progressiva dei dati è particolarmente utile durante la trasmissione immagini compresse utilizzando canali di comunicazione a bassa velocità, poiché consente di avere un'idea dell'intera immagine dopo il trasferimento di una piccola parte del file JPEG.

Entrambi gli schemi descritti (JPEG sia sequenziale che progressivo) sono basati su DCT e fondamentalmente non consentono di ottenere un'immagine restaurata assolutamente identica a quella originale. Tuttavia, lo standard consente anche una compressione che non utilizza DCT, ma è costruita sulla base di un predittore lineare (lossless, cioè "lossless", JPEG), che garantisce la piena coincidenza bit per bit dell'originale e immagini ricostruite. Allo stesso tempo, il rapporto di compressione per le immagini fotografiche raramente raggiunge 2, ma l'assenza garantita di distorsione in alcuni casi risulta essere richiesta. Rapporti di compressione notevolmente più elevati possono essere ottenuti utilizzando il metodo di compressione JPEG-LS descritto da ISO/IEC 14495-1, che, nonostante la somiglianza nei nomi, non è direttamente correlato allo standard JPEG ISO/IEC 10918-1 (ITU T. 81 Raccomandazione) (Raccomandazione ITU T.87).

Sintassi e struttura

Il file JPEG contiene una sequenza marcatori, ognuno dei quali inizia con il byte 0xFF, che indica l'inizio del marker, e il byte identificativo. Alcuni marker sono costituiti solo da questa coppia di byte, mentre altri contengono dati aggiuntivi costituiti da un campo a due byte con la lunghezza della parte informativa del marker (compresa la lunghezza di questo campo, ma meno i due byte dell'inizio del marker, ovvero 0xFF e l'identificatore) e i dati stessi. Questa struttura di file consente di trovare rapidamente un marker con i dati necessari (ad esempio, con la lunghezza della linea, il numero di linee e il numero di componenti di colore dell'immagine compressa).

Marcatori JPEG di base

marcatore	byte	Lunghezza	Appuntamento	Commenti (1)
COSÌ IO	0xFFD8	No	Inizio immagine
SOF0	0xFFC0	dimensione variabile	Inizio frame (base, DCT)	Indica che l'immagine è stata codificata in modalità base utilizzando il codice DCT e Huffman. Il marker contiene il numero di righe e la lunghezza della linea dell'immagine (campi a due byte con offset rispettivamente di 5 e 7 rispetto all'inizio del marker), il numero di componenti (campo byte con offset 8 relativo all'inizio del marker), il numero di bit per componente (campo byte con un offset di 4 rispetto all'inizio del marker), nonché il rapporto dei componenti (ad esempio 4: 2: 0) .
SOF1	0xFFC1	dimensione variabile	Inizio frame (esteso, DCT, codice Huffman)	Indica che l'immagine è stata codificata in modalità estesa utilizzando il codice DCT e Huffman. Il marker contiene il numero di righe e la lunghezza della riga dell'immagine, il numero di componenti, il numero di bit per componente e il rapporto dei componenti (ad esempio 4: 2: 0).
SOF2	0xFFC2	dimensione variabile	Inizio frame (progressivo, DCT, codice Huffman)	Indica che l'immagine è stata codificata progressivamente utilizzando il codice DCT e Huffman. Il marker contiene il numero di righe e la lunghezza della riga dell'immagine, il numero di componenti, il numero di bit per componente e il rapporto dei componenti (ad esempio 4: 2: 0).
DHT	0xFFC4	dimensione variabile	Contiene tabelle di Huffman	Specifica una o più tabelle di Huffman.
DQT	0xFFDB	dimensione variabile	Contiene tabelle di quantizzazione	Specifica una o più tabelle di quantizzazione.
DRI	0xFFDD	4 byte	Specifica l'intervallo di ripetizione	Specifica la spaziatura tra i marker RST n nei macroblocchi.
sos	0xFFDA	dimensione variabile	Inizia la scansione	L'inizio della prima o della successiva scansione dell'immagine con la direzione di marcia da sinistra a destra dall'alto verso il basso. Se è stata utilizzata la modalità di codifica di base, viene utilizzata una scansione. Quando si utilizzano le modalità progressive, vengono utilizzate più scansioni. Il marcatore SOS è il separatore tra le parti informative (intestazione) e codificate (in realtà dati compressi) dell'immagine.
RST n	0xFFD n	No	Ricomincia	Inserimento in ciascuno R macroblocco dove R- Intervallo di riavvio del marker DRI. Non utilizzato se non è presente un marker DRI. n, i 3 bit meno significativi del marker di codice, esegue cicli da 0 a 7.
APP n	0xFFE n	dimensione variabile	Impostato dall'applicazione	Ad esempio, un file EXIF ​​JPEG utilizza il marker APP1 per memorizzare i metadati situati in una struttura basata su TIFF.
COM	0xFFFE	dimensione variabile	Un commento	Contiene il testo del commento.
EOI	0xFFD9	No	Fine della parte codificata dell'immagine.

Vantaggi e svantaggi

Gli svantaggi della compressione JPEG includono la comparsa di artefatti caratteristici sulle immagini ripristinate con rapporti di compressione elevati: l'immagine è sparsa in blocchi di 8x8 pixel (questo effetto è particolarmente evidente nelle aree dell'immagine con variazioni di luminosità uniformi), in aree con elevata spazialità frequenza (ad esempio, sui contorni di contrasto e sui bordi dell'immagine) gli artefatti appaiono sotto forma di aloni di rumore. Va notato che lo standard JPEG (ISO / IEC 10918-1, allegato K, clausola K.8) prevede l'uso di filtri speciali per sopprimere gli artefatti del blocco, ma in pratica tali filtri, nonostante la loro elevata efficienza, non sono praticamente Usato. Tuttavia, nonostante le carenze, JPEG è diventato molto diffuso a causa di un rapporto di compressione sufficientemente elevato (rispetto alle alternative esistenti al momento della sua comparsa), supporto per la compressione di immagini a colori e complessità computazionale relativamente bassa.

Prestazioni di compressione JPEG

Per accelerare il processo di compressione secondo lo standard JPEG, la parallelizzazione dei calcoli viene tradizionalmente utilizzata, in particolare, durante il calcolo DCT. Storicamente, uno dei primi tentativi di accelerare il processo di compressione utilizzando questo approccio è stato descritto in un articolo del 1993 di Kasperovich e Babkin, che proponeva un'approssimazione DCT originale che rende possibile parallelizzare in modo efficiente i calcoli utilizzando registri generici a 32 bit Processori Intel 80386. Più tardi, più produttivo circuiti di calcolo utilizzato SIMD-estensioni del set di istruzioni dei processori x86. Tanto risultati migliori consentono di realizzare schemi che utilizzano le capacità di calcolo degli acceleratori grafici (tecnologie NVIDIA CUDA e AMD FireStream) per organizzare calcoli paralleli non solo di DCT, ma anche di altre fasi Compressione JPEG(conversione dello spazio colore, livello di esecuzione, codifica entropica, ecc.) e per ogni blocco 8x8 dell'immagine codificata o decodificata. L'articolo è stato per la prima volta [ una fonte?] viene presentata l'implementazione della parallelizzazione di tutte le fasi dell'algoritmo JPEG utilizzando la tecnologia CUDA, che ha notevolmente accelerato le prestazioni di compressione e decodifica secondo lo standard JPEG.

Nel 2010, gli scienziati del progetto PLANETS hanno inserito le istruzioni per leggere il formato JPEG in una capsula speciale, che è stata collocata in uno speciale bunker nelle Alpi svizzere. Ciò è stato fatto per preservare per i posteri le informazioni sui formati digitali popolari all'inizio del 21° secolo.

Guarda anche

Note (modifica)

Link

• Specifica JFIF 1.02 (file di testo)
• Ottimizzazione JPEG. Parte 1, Parte 2, Parte 3.

Area di applicazione

Il formato è un formato di compressione con perdita, quindi non è corretto presumere che JPEG memorizzi i dati come 8 bit per canale (24 bit per pixel). D'altra parte, poiché i dati compressi JPEG e i dati decompressi sono generalmente rappresentati in formato 8 bit per canale, a volte viene utilizzata questa terminologia. È supportata anche la compressione delle immagini in scala di grigi.

Quando si salva un file JPEG, è possibile specificare il livello di qualità, e quindi il tasso di compressione, che di solito è impostato in alcune unità arbitrarie, ad esempio da 1 a 100 o da 1 a 10. Maggiore è il numero corrisponde alla migliore qualità , ma la dimensione del file aumenta. Di solito, la differenza di qualità tra 90 e 100 non è praticamente percepita dall'occhio. Tieni presente che l'immagine recuperata dal formato JPEG non lo è copia esatta originale. Un malinteso comune è che Qualità JPEGè identica alla condivisione delle informazioni memorizzate.

Il supporto diffuso per il formato JPEG da parte di una varietà di software spesso comporta la codifica JPEG di immagini che non erano destinate a tale scopo, senza alcun guadagno nel rapporto di compressione rispetto a PNG o GIF realizzati correttamente, ma con conseguenze sulla qualità deplorevoli. Ad esempio, un tentativo di registrare in JPEG un'immagine contenente piccoli dettagli contrastanti (soprattutto colore) porterà alla comparsa di artefatti caratteristici ben visibili, anche ad un "livello qualitativo" elevato.

Compressione

Quando è compressa, l'immagine viene convertita da RGB a YCbCr (YUV). Si precisa che lo standard JPEG (ISO/IEC 10918-1) non regola in alcun modo la scelta di YCbCr, consentendo altri tipi di conversione (ad esempio con un numero di componenti diverso da tre), e compressione senza conversione (direttamente a RGB), tuttavia, la specifica JFIF (JPEG File Interchange Format, proposta nel 1991 da C-Cube Microsystems, e ora lo standard de facto) presuppone l'uso della conversione RGB-> YCbCr.

Dopo la conversione RGB-> YCbCr, per i canali immagine Cb e Cr responsabili del colore, è possibile eseguire la "decimazione" (sottocampionamento), il che significa che a ogni blocco di 4 pixel (2x2) del canale di luminanza Y viene assegnata la media Cb e Cr valori (lo schema di decimazione è "4: 2: 0". Inoltre, per ogni blocco 2x2, invece di 12 valori (4 Y, 4 Cb e 4 Cr), solo 6 valori (4 Y e un Cb medio e Cr) Vengono imposti requisiti maggiori alla compressione delle immagini, la decimazione può essere eseguita solo in una direzione - verticalmente ("4: 4: 0") o orizzontalmente ("4: 2: 2") o non eseguita affatto ("4: 4: 4").

Lo standard consente anche la decimazione con una media di Cb e Cr non per un blocco 2x2, ma per quattro pixel consecutivi (verticalmente o orizzontalmente), ovvero per blocchi 1x4 o 4x1 (schema "4: 1: 1"). Sono ammessi anche diversi tipi di decimazione per Cb e Cr, ma in pratica tali schemi sono estremamente rari.

Inoltre, la componente luma Y e le componenti Cb e Cr responsabili del colore sono divise in blocchi di 8x8 pixel. Ciascuno di questi blocchi subisce una trasformata coseno discreta (DCT). I coefficienti DCT ottenuti vengono quantizzati (per Y, Cb e Cr, nel caso generale, vengono utilizzate matrici di quantizzazione diverse) e impacchettati utilizzando i codici di Huffman. Lo standard JPEG consente anche l'uso di una codifica aritmetica molto più efficiente, tuttavia, a causa di restrizioni sui brevetti (il brevetto per l'encoder aritmetico QM descritto nello standard JPEG appartiene a IBM), nella pratica non viene utilizzato.

Le matrici utilizzate per quantizzare i coefficienti DCT sono memorizzate nella parte di intestazione del file JPEG. Di solito sono costruiti in modo che i coefficienti di alta frequenza siano quantizzati più fortemente di quelli di bassa frequenza. Ciò porta all'ingrossamento dei dettagli fini nell'immagine. Maggiore è il rapporto di compressione, più fortemente sono quantizzati tutti i coefficienti.

Varietà di schemi di compressione JPEG

Lo standard JPEG fornisce due modi principali per rappresentare i dati codificati.

Il più comune, supportato dalla maggior parte dei codec disponibili, è la rappresentazione JPEG sequenziale dei dati, che comporta l'attraversamento sequenziale dell'immagine codificata blocco per blocco da sinistra a destra, dall'alto verso il basso. Le operazioni sopra descritte vengono eseguite su ciascun blocco di immagine codificata e i risultati della codifica vengono inseriti sequenzialmente nel flusso di output sotto forma di una singola "scansione" (una matrice di dati codificati). La modalità di codifica baseline o "baseline" consente solo questa rappresentazione. La modalità estesa (estesa), insieme a quella sequenziale, consente anche la presentazione progressiva dei dati (JPEG progressivo).

Nel caso di JPEG progressivo, i dati compressi vengono scritti nel flusso di output come un insieme di scansioni, ciascuna delle quali descrive l'immagine per intero con un grado di dettaglio crescente. Ciò si ottiene registrando in ogni scansione non un set completo di coefficienti DCT, ma solo alcuni di essi: prima - bassa frequenza, nelle scansioni successive - alta frequenza (il metodo di "selezione spettrale", cioè il campionamento spettrale) , oppure in modo sequenziale, da scansione a scansione, affinamento dei coefficienti DCT (metodo "approssimazione successiva", ovvero approssimazioni successive). Questa rappresentazione progressiva dei dati è particolarmente utile quando si trasferiscono immagini compresse utilizzando canali di comunicazione a bassa velocità, poiché consente di avere un'idea dell'intera immagine dopo che è stata trasferita solo una piccola parte del file JPEG.

Entrambi gli schemi descritti (JPEG sia sequenziale che progressivo) sono basati su DCT e fondamentalmente non consentono di ottenere un'immagine restaurata assolutamente identica a quella originale. Tuttavia, lo standard consente anche una compressione che non utilizza DCT, ma è costruita sulla base di un predittore lineare (lossless, cioè "lossless", JPEG), che garantisce la piena coincidenza bit per bit dell'originale e ricostruito immagini. Allo stesso tempo, il rapporto di compressione per le immagini fotografiche raramente raggiunge 2, ma l'assenza garantita di distorsione in alcuni casi risulta essere richiesta. Rapporti di compressione notevolmente più elevati possono essere ottenuti utilizzando un metodo che, nonostante la somiglianza nei nomi, non è strettamente correlato allo standard JPEG ISO / IEC 10918-1 (raccomandazione ITU T.81). Compressione JPEG-LS ISO/IEC 14495-1 (raccomandazione ITU T.87).

Sintassi e struttura

Il file JPEG contiene una sequenza di marker, ognuno dei quali inizia con un byte 0xFF che indica l'inizio del marker e un identificatore di byte. Alcuni marker sono costituiti solo da questa coppia di byte, mentre altri contengono dati aggiuntivi costituiti da un campo a due byte con la lunghezza della parte informativa del marker (compresa la lunghezza di questo campo, ma meno i due byte dell'inizio del marker, ovvero 0xFF e l'identificatore) e i dati stessi.

Marcatori JPEG di base

marcatore	byte	Lunghezza	Appuntamento

L'algoritmo è stato sviluppato da un gruppo di esperti nel campo della fotografia (Joint Photographic Expert Group) specificamente per la compressione di immagini a 24 bit e in scala di grigi nel 1991. Questo algoritmo non è molto bravo a comprimere le immagini a due livelli, ma gestisce in modo eccellente le immagini con toni continui, in cui i pixel vicini tendono ad avere colori simili. Di solito l'occhio non è in grado di notare alcuna differenza se compresso con questo metodo di 10 o 20 volte.

L'algoritmo è basato su DCT applicato a una matrice di 8x8 pixel di blocchi immagine disgiunti. DCT scompone questi blocchi in base alle ampiezze di determinate frequenze. Di conseguenza, si ottiene una matrice in cui molti coefficienti, di regola, sono vicini allo zero, che possono essere rappresentati in forma numerica approssimativa, ad es. in una forma quantizzata senza perdita significativa della qualità del restauro.

Consideriamo più in dettaglio il funzionamento dell'algoritmo. Supponiamo di comprimere un'immagine a 24 bit a colori. In questo caso, otteniamo le seguenti fasi di lavoro.

Passo 1. Traduciamo l'immagine dallo spazio RGB allo spazio YCbCr usando la seguente espressione:

Notiamo subito che la trasformazione inversa si ottiene facilmente moltiplicando la matrice inversa per un vettore, che è essenzialmente lo spazio YUV:

.

Passo 2. Dividi l'immagine originale in matrici 8x8. Formiamo tre matrici DCT funzionanti da ciascuna - 8 bit separatamente per ciascun componente. Ad alti rapporti di compressione, il blocco 8x8 viene scomposto in componenti YCbCr in formato 4: 2: 0, ad es. i componenti per Cb e Cr sono presi attraverso un punto lungo le righe e le colonne.

Passaggio 3. Applicazione di DCT a blocchi immagine di 8x8 pixel. Formalmente, il DCT diretto per il blocco 8x8 può essere scritto come

dove ... Poiché DCT è il "cuore" dell'algoritmo JPEG, in pratica è desiderabile calcolarlo il più rapidamente possibile. Un approccio semplice per accelerare i calcoli consiste nel calcolare in anticipo le funzioni del coseno e tabulare i risultati. Inoltre, data l'ortogonalità delle funzioni coseno con frequenze diverse, la formula precedente può essere scritta come

.

Ecco una matrice 8x8 che descrive uno spazio a 8 dimensioni per rappresentare le colonne di un blocco in quello spazio. Matrix è una matrice trasposta e fa lo stesso, ma per le righe di blocchi. Il risultato è una trasformazione separabile, che in forma matriciale si scrive come

Ecco il risultato del DCT, il cui calcolo richiede operazioni di moltiplicazione e quasi la stessa quantità di addizioni, che è significativamente inferiore ai calcoli diretti utilizzando la formula sopra. Ad esempio, per convertire un'immagine con una dimensione di 512x512 pixel, avrai bisogno di operazioni aritmetiche... Considerando 3 componenti di luminanza, si ottiene il valore di 12 582 912 operazioni aritmetiche. Il numero di moltiplicazioni e addizioni può essere ulteriormente ridotto utilizzando l'algoritmo Fast Fourier Transform. Di conseguenza, per trasformare un blocco 8x8, dovrai eseguire 54 moltiplicazioni, 468 addizioni e spostamenti di bit.

Come risultato di DCT, otteniamo una matrice in cui i coefficienti nell'angolo in alto a sinistra corrispondono al componente a bassa frequenza dell'immagine e in basso a destra a quello ad alta frequenza.

Passaggio 4. Quantizzazione. A questo punto, alcune informazioni vengono scartate. Qui, ogni numero della matrice è diviso per un numero speciale dalla "tabella di quantizzazione" e il risultato viene arrotondato all'intero più vicino:

.

Inoltre, per ogni matrice Y, Cb e Cr, è possibile impostare le proprie tabelle di quantizzazione. Lo standard JPEG consente anche l'utilizzo di proprie tabelle di quantizzazione, che però dovranno essere trasmesse al decoder insieme ai dati compressi, cosa che aumenterà la dimensione complessiva del file. È chiaro che è difficile per un utente selezionare da solo 64 coefficienti, quindi lo standard JPEG utilizza due approcci per le matrici di quantizzazione. Il primo è che lo standard JPEG include due tabelle di quantizzazione consigliate: una per luma e una per chroma. Queste tabelle sono presentate di seguito. Il secondo approccio consiste nel sintetizzare (calcolare al volo) una tabella di quantizzazione che dipende da un parametro specificato dall'utente. La tabella stessa è costruita usando la formula

Nella fase di quantizzazione, il rapporto di compressione è controllato e si verifica la perdita maggiore. È chiaro che impostando tabelle di quantizzazione con coefficienti grandi, otterremo più zeri e, quindi, un rapporto di compressione maggiore.

La quantizzazione è anche associata a effetti specifici dell'algoritmo. A grandi valori passo di quantizzazione, le perdite possono essere così grandi che l'immagine si scompone in quadrati monofonici 8x8. A loro volta, le perdite in alte frequenze possono manifestarsi nel cosiddetto "effetto Gibbs", quando si forma un "alone" ondulato attorno ai contorni con una netta transizione di colore.

Passaggio 5. Traduciamo la matrice 8x8 in un vettore di 64 elementi usando la scansione a "zigzag" (Fig. 2).

Riso. 2. Scansione a "zigzag"

Di conseguenza, all'inizio del vettore, di regola, verranno scritti coefficienti diversi da zero e alla fine si formeranno catene di zeri.

Passaggio 6. Trasformiamo il vettore utilizzando l'algoritmo RLE modificato, al cui output otteniamo coppie del tipo (skip, number), dove "skip" è il contatore degli zeri saltati e "number" è il valore che deve essere inserito la cella successiva. Ad esempio, il vettore 1118 3 0 0 0 -2 0 0 0 0 1… sarà piegato in coppie (0, 1118) (0,3) (3, -2) (4,1)….

Si noti che il primo numero della componente trasformata è sostanzialmente uguale alla luminanza media del blocco 8x8 ed è indicato come coefficiente DC. Allo stesso modo per tutti i blocchi immagine. Questa circostanza suggerisce che i coefficienti DC possono essere efficacemente compressi se si memorizzano non i loro valori assoluti, ma i valori relativi sotto forma della differenza tra il coefficiente DC del blocco corrente e il coefficiente DC del blocco precedente, e si ricorda il primo coefficiente così com'è. In questo caso, l'ordinamento dei coefficienti DC può essere effettuato, ad esempio, come segue (Fig. 3). Il resto dei coefficienti, che sono chiamati coefficienti AC, rimangono invariati.

Passaggio 7. Convolgi le coppie risultanti usando codici di Huffman a tavola fissa non uniformi. Inoltre, vengono utilizzati codici diversi per i coefficienti DC e AC, ad es. diverse tabelle con codici Huffman.

Riso. 3. Schema di ordinamento del coefficiente DC

Riso. 4. Schema a blocchi dell'algoritmo JPEG

Il processo di ripristino dell'immagine in questo algoritmo è completamente simmetrico. Il metodo consente di comprimere le immagini di 10-15 volte senza una notevole perdita visiva.

Durante lo sviluppo di questo standard, siamo stati guidati dal fatto che questo algoritmo doveva comprimere le immagini abbastanza rapidamente, non più di un minuto su un'immagine media. Siamo nel 1991! E la sua implementazione hardware dovrebbe essere relativamente semplice ed economica. In questo caso, l'algoritmo doveva essere simmetrico in termini di tempo di funzionamento. Il soddisfacimento dell'ultimo requisito effettuato possibile emergenza fotocamere digitali che riprendono immagini a 24 bit. Se l'algoritmo fosse asimmetrico, sarebbe spiacevole aspettare a lungo prima che il dispositivo si "ricarichi": comprimerà l'immagine.

Sebbene JPEG sia uno standard ISO, il suo formato di file non è stato corretto. Approfittando di ciò, i produttori creano i propri formati incompatibili e, quindi, possono modificare l'algoritmo. Pertanto, le tabelle interne dell'algoritmo consigliato dall'ISO vengono sostituite da esse con le proprie. Ci sono anche opzioni JPEG per applicazioni specifiche.

Generazione adattiva di matrici di quantizzazione in schemi tipo JPEG

Luzhkov Yuri Valerievich,

studente post-laurea di San Pietroburgo Università Statale informatica, meccanica e ottica.

Consulente scientifico - Dottore in Scienze Tecniche, Professore

Tropchenko Alexander Yuvenalievich.

introduzione

V l'anno scorso c'è una marcata tendenza a rendere popolari gli schemi di compressione delle immagini con perdita di dati basati sulle trasformazioni wavelet. Tuttavia, i formati di compressione delle immagini con trasformazione del coseno discreta (DCT) sono ancora i più comunemente usati.

Uso diffuso del formato JPEG (Gruppo congiunto di esperti fotografici) [ Wallace G.K.] pone ai ricercatori la seguente domanda: è possibile modificare lo schema di compressione esistente in modo tale da aumentare la qualità della compressione senza modificare l'algoritmo di decompressione? La soluzione a questo problema consentirà di apportare modifiche ai compressori esistenti senza preoccuparsi della disponibilità di software speciali (modificati) per la decompressione dell'immagine da parte degli utenti.

Per schema di tipo JPEG si intende una versione di uno schema di compressione con suddivisione di un'immagine in frammenti rettangolari, i cui elementi obbligatori sono: trasformazione ortogonale, quantizzazione dei dati convertiti e loro successiva codifica entropica.

Molti algoritmi di compressione utilizzano una serie di opzioni predefinite. In JPEG, questi includono matrici di quantizzazione e tabelle di Huffman. Vengono salvati nell'intestazione del file compresso e possono essere definiti dall'utente in modo indipendente, il che migliora la qualità della compressione.

Quindi, ad oggi, sono stati proposti diversi approcci per comporre matrici di quantizzazione JPEG (ad esempio, and), che, tuttavia, non sono universali. Nel nostro lavoro, prenderemo in considerazione un approccio generalizzato alla quantizzazione scalare adattativa dei coefficienti di spettro, che è semplice da implementare e può essere applicato in schemi simili a JPEG.

Quantizzazione del segnale adattivo

La quantizzazione è un metodo di elaborazione del segnale, abbinato all'introduzione di distorsione al suo interno. L'essenza quantizzazione scalare viene giù a dividere l'intervallo di valori di una funzione in un numero finito di intervalli con la successiva selezione di un valore per rappresentare qualsiasi valore da questo intervallo.

Quindi, sia dato un insieme di intervalli e un insieme di punti, allora funzione di quantizzazioneè definito come per. quando quantizzazione scalare uniforme l'insieme degli intervalli può essere rappresentato come:

dove - parametro, o passo di quantizzazione, - spostamento di base degli intervalli, , - numero dell'intervallo, che è l'oggetto codificato. Quindi l'operazione di quantizzazione può essere ridotta a una semplice divisione con arrotondamento:

.(1)

L'adattabilità nella quantizzazione scalare è ottenuta grazie alla selezione individuale della fase di quantizzazione per ciascun valore quantizzato.

Quantizzazione scalare adattiva pesata

L'approccio che proponiamo si basa su analisi statistica dei coefficienti spettrali... Può essere utilizzato in schemi di compressione (es. JPEG ) a condizione che la finestra di scansione del segnale abbia una dimensione costante.

Quindi, sia data una sequenza di quantità, suddivisa inmblocchi identici innvalori in ciascuno e - l'indice dell'elemento in questo blocco, ovvero ogni elemento ha il suo analogo in qualsiasi altro blocco. L'essenza dell'approccio proposto è la seguente: per ciascunonDell'elemento esimo, viene calcolato il valore di un criterio di peso speciale e il passo di quantizzazione di questo elemento dello spettro è impostato quanto più grande, minore è il valore del criterio di peso corrispondente.

Pertanto, la procedura di quantizzazione viene eseguita tenendo conto di alcune informazioni statistiche sul segnale, date come, raccolte damblocchi e univoci per gli elementi di ogni indice n... La funzione di quantizzazione (1) in questo caso sarà indicata come, e funzione del parametro di quantizzazione – .

Introduciamo un criterio, chiamandolo coefficiente di spettro peso... Il valore rifletterà il grado di significatività della posizione spettrale corrispondentencoefficienti .

Uno dei metodi di calcolo si basa sulle ampiezze medie:

.(2)

Gli esperimenti hanno dimostrato che il calcolo secondo (2) per i coefficienti DCT porta a una distribuzione sproporzionata dei valori dei criteri per i coefficienti dello spettro ad alta e bassa frequenza. Puoi risolvere la situazione usando funzione correttiva(vedi sotto), o calcolando i valori in base alle ampiezze massime:

.(3)

Passiamo alla questione della definizione di una funzione. Lascia che i suoi valori siano limitati dall'intervallo ... Introduciamo una funzione lineare di:

,

dove e sono rispettivamente i valori minimo e massimo (il caso è considerato separatamente).

In pratica, è utile utilizzare una funzione non lineare di, che si ottiene mediante l'uso di una funzione correttiva:

.(4)

Poiché any nel caso generale dipende da tutti gli elementi del vettore spettrale originale, la funzioneEdipende anche da. Infatti, questa è una funzione della fase di quantizzazione del segnale. Introduciamo la notazione ... Quindi la formula (4) assume finalmente la forma:

.(5)

Pertanto, la funzione della fase di quantizzazione è localizzata nell'intervallo daun 1 a un 2 Variando la sua forma, è possibile sopprimere in misura maggiore o minore determinati gruppi di coefficienti.

Applichiamo ora l'approccio proposto per la generazione adattiva di matrici di quantizzazione nello schema JPEG ... In (5), useremo una funzione di correzione lineare e il criterio per le ampiezze massime (3).

Grafici funzione di default del passo di quantizzazione JPEG sono mostrati in Fig.1 a Sinistra. Δ grafici generati in modo adattivo per l'immagine "Vecchio uomo"Sono mostrati in fig.1, a destra. In entrambi i casi, i valori sono ordinati in ordine crescente. Come puoi vedere, per il primo terzo dei valori dell'argomento, c'è un forte aumento di , che è particolarmente caratteristico delle funzioni generate. Su questo sito generato in alcuni punti è molto più grande dello standard, il che porta a una maggiore soppressione delle frequenze corrispondenti.

Riso. 1. Funzioni standard e generate del parametro di quantizzazione con ordinato

crescente per valori.

Il grafico per l'immagine"Vecchio uomo»È mostrato in Fig.2, sinistra. Sulla destra, i risultati della compressione vengono mostrati utilizzando le matrici predefinite e le matrici generate dall'esperimento. Come si può vedere dai risultati, la differenza nel rapporto di compressione è fino al 20% a favore dell'approccio adattivo a parità di valori PSNR.

Riso. 2. Generazione di matrici di quantizzazione adattativa per il circuito JPEG.

Conclusione

Abbiamo proposto un metodo per la quantizzazione scalare adattativa dei coefficienti spettrali, basato sul calcolo del criterio di significatività delle componenti spettrali. Gli esperimenti hanno dimostrato che l'uso dell'approccio considerato nello schema JPEG consente di ottenere un guadagno nel rapporto di compressione fino al 20% rispetto all'utilizzo di matrici di quantizzazione standard.

L'utilizzo pratico della modifica considerata presuppone l'implementazione del solo compressore, e per visualizzare le immagini è sufficiente utilizzare lo standard JPEG -decompressore, che rappresenta un importante vantaggio della soluzione proposta.

Letteratura

1. Fung H.T., Parker K.J. Progettazione di tabelle di quantizzazione adattive all'immagine per JPEG // Journal of Electronic Imaging. - 1996. - Vol. 4, N. 2. - Pag. 144 - 150.

2. Gray R.M., Neuhoff D.L.Quantizzazione // Transazioni IEEE sulla teoria dell'informazione. - 1998. - Vol. 44, N. 6. - P. 2325 - 2383.

3. Ratnakar V., Livny M. Estendendo RD -OPT con soglia globale per l'ottimizzazione JPEG // Data Compression Conference.– 1996.

4. Wallace G.K. Lo standard di compressione delle immagini fisse JPEG // IEEE Trans. Elettronica di consumo. - 1992. - Vol. 38, N. 1. - Pag. 18 - 34.