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 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, la conversione di un'immagine di 512x512 pixel richiede 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 valori elevati della fase di quantizzazione, le perdite possono essere così grandi che l'immagine si scompone in quadrati 8x8 monocolore. A loro volta, le perdite nelle 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 di quest'ultimo requisito ha reso possibile l'emergere di 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.
- Tutorial
UPD. È stato costretto a rimuovere la formattazione a spaziatura fissa. Un bel giorno, l'habraparser ha smesso di percepire la formattazione all'interno dei tag pre e code. L'intero testo si è trasformato in un pasticcio. L'amministrazione Habr non ha potuto aiutarmi. Ora irregolare, ma almeno leggibile.
Ti sei mai chiesto come funziona un file jpg? Scopriamolo ora! Riscalda il tuo compilatore preferito e l'editor esadecimale, decodifichiamo questo:
Ho appositamente preso un disegno più piccolo. Questa è la favicon di Google familiare ma fortemente compressa:
Ti avverto subito che la descrizione è semplificata, e le informazioni fornite non sono complete, ma in seguito sarà facile capire la specifica.
Senza nemmeno sapere come avviene la codifica, possiamo già estrarre qualcosa dal file.
- inizio marcatore. Si trova sempre all'inizio di tutti i file jpg.
Seguito da byte
... Questo è un marcatore che segna l'inizio della sezione dei commenti. Prossimi 2 byte
- la lunghezza della sezione (compresi questi 2 byte). Quindi nei prossimi due
- il commento stesso. Questi sono i codici per i caratteri ":" e ")", ad es. emoticon normale. Puoi vederlo sulla prima riga sul lato destro dell'editor esadecimale.
Un po' di teoria
Molto brevemente in passi:
Pensiamo all'ordine in cui questi dati possono essere codificati. Supponiamo, prima, completamente, per l'intera immagine, che sia codificato il canale Y, quindi Cb, quindi Cr. Tutti ricordano di aver caricato le immagini sul dial-up. Se fossero codificati in questo modo, dovremmo aspettare che l'intera immagine venga caricata prima che appaia sullo schermo. Sarà anche spiacevole se la fine del file viene persa. Probabilmente ci sono anche altre buone ragioni. Pertanto, i dati codificati sono disposti alternativamente, in piccole parti. 
Vi ricordo che ogni blocco Y ij, Cb ij, Cr ij è una matrice di coefficienti DCT codificati con codici di Huffman. Nel file sono disposti nel seguente ordine: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Lettura di un file
Dopo aver estratto il commento, dovrebbe essere facile capire che:- Il file è suddiviso in settori preceduti da marker.
- I marker sono lunghi 2 byte, con il primo byte.
- Quasi tutti i settori memorizzano la loro lunghezza nei 2 byte successivi al marker.
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78
FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 FF
C4 00 16 11 01 01 01 00 00 00 00 00 00 00 00 00
00 00 00 00 11 00 01 FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00 AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9
Marker: DQT - tabella di quantizzazione.
FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF
L'intestazione della sezione è sempre di 3 byte. Nel nostro caso lo è. L'intestazione è composta da:
Lunghezza: 0x43 = 67 byte
Lunghezza dei valori nella tabella: 0 (0 - 1 byte, 1 - 2 byte)
[_0]
ID tabella: 0
I restanti 64 byte devono riempire la tabella 8x8.
Dai un'occhiata più da vicino all'ordine in cui sono riempiti i valori della tabella. Questo ordine è chiamato ordine a zigzag: 
Marker: SOF0 - Baseline DCT
Questo marker si chiama SOF0, e significa che l'immagine è codificata dal metodo base. È molto comune. Ma su Internet, il metodo progressivo a te familiare non è meno popolare, quando viene caricata prima un'immagine a bassa risoluzione e poi un'immagine normale. Questo ti permette di capire cosa viene mostrato lì senza aspettare un download completo. La specifica definisce alcuni metodi in più, mi sembra, non molto comuni.FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01
Lunghezza: 17 byte.
Precisione: 8 bit. Nel metodo di base, è sempre 8. A quanto ho capito, questa è la profondità di bit dei valori del canale.
Altezza del motivo: 0x10 = 16
Larghezza del motivo: 0x10 = 16
Numero di componenti: 3. Molto spesso si tratta di Y, Cb, Cr.
1° componente:
ID: 1
Diradamento orizzontale (H 1): 2
[_2]
Decimazione verticale (V 1): 2
ID tabella di quantizzazione: 0
2° componente:
ID: 2
Diradamento orizzontale (H 2): 1
[_1]
Diradamento verticale (V 2): 1
3° componente:
ID: 3
Diradamento orizzontale (H 3): 1
[_1]
Diradamento verticale (V 3): 1
ID tabella di quantizzazione: 1
Ora vedi come determinare quanto è sottile l'immagine. Trova H max = 2 e V max = 2. Il canale i sarà tagliato in H max / H i volte orizzontalmente e V max / V i volte verticalmente.
Marker: DHT (tabella di Huffman)
Questa sezione memorizza i codici e i valori ottenuti dalla codifica di Huffman.FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02
lunghezza: 21 byte.
classe: 0 (0 - tabella coefficienti DC, 1 - tabella coefficienti AC).
[_0]
ID tabella: 0
Lunghezza del codice Huffman: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Numero di codici:
Il numero di codici indica il numero di codici di quella lunghezza. Nota che la sezione memorizza solo le lunghezze dei codici, non i codici stessi. Dobbiamo trovare i codici da soli. Quindi, abbiamo un codice di lunghezza 1 e uno - di lunghezza 2. Ci sono 2 codici in totale, non ci sono più codici in questa tabella.
Un valore è associato a ciascun codice e sono elencati di seguito nel file. I valori sono a byte singolo, quindi leggiamo 2 byte.
- il valore del 1° codice.
- il valore del 2° codice.
Costruire un albero del codice di Huffman
Dobbiamo costruire un albero binario dalla tabella che abbiamo ottenuto nella sezione DHT. E già da questo albero riconosciamo ogni codice. Aggiungiamo i valori nell'ordine in cui sono indicati nella tabella. L'algoritmo è semplice: non importa dove siamo, cerchiamo sempre di aggiungere un valore al ramo sinistro. E se è occupata, allora a destra. E se non c'è spazio lì, torniamo a un livello superiore e proviamo da lì. È necessario fermarsi a un livello pari alla lunghezza del codice. I rami di sinistra corrispondono a 0, i rami di destra - 1.Commento:
Non devi iniziare dall'alto ogni volta. Valore aggiunto: torna indietro di un livello. Esiste il ramo giusto? Se è così, sali di nuovo. In caso contrario, crea il ramo giusto e naviga lì. Quindi, da lì, inizia la tua ricerca per aggiungere il valore successivo.
Alberi per tutte le tabelle in questo esempio: 
UPD (grazie): I nodi del primo albero (DC, id = 0) devono avere i valori 0x03 e 0x02
Nei cerchi - i valori dei codici, sotto i cerchi - i codici stessi (spiegherò che li abbiamo ottenuti, andando dall'alto a ciascun nodo). È con tali codici (di questa e di altre tabelle) che viene codificato il contenuto della figura stessa.
Marcatore: SOS (inizio della scansione)
Il byte nel marker significa “SI! Infine, siamo passati direttamente all'analisi della sezione dell'immagine codificata! ". Tuttavia, la sezione è chiamata simbolicamente SOS.& nbsp FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
La lunghezza della parte dell'intestazione (non l'intera sezione): 12 byte.
Il numero di componenti di scansione. Abbiamo 3, uno per Y, Cb, Cr.
1° componente:
Numero parte immagine: 1 (Y)
ID tabella Huffman per coefficienti DC: 0
[_0]
ID tabella Huffman per coefficienti AC: 0
2° componente:
Numero parte immagine: 2 (Cb)
[_1]
3° componente:
Numero componente immagine: 3 (Cr)
ID tabella Huffman per coefficienti DC: 1
[_1]
ID tabella Huffman per coefficienti AC: 1
Questi componenti si alternano ciclicamente.
Qui è dove finisce la parte di intestazione, da qui alla fine (marcatore) dei dati codificati.
0
Trovare il coefficiente DC.
1.
Lettura di una sequenza di bit (se incontriamo 2 byte, allora questo non è un marker, ma solo un byte)... Dopo ogni bit ci spostiamo lungo l'albero di Huffman (con il corrispondente identificatore) lungo i rami 0 o 1, a seconda del bit letto. Ci fermiamo se siamo nel nodo finale.
10
1011101110011101100001111100100
2.
Prendiamo il valore del nodo. Se è 0, il coefficiente è 0, lo scriviamo nella tabella e procediamo alla lettura di altri coefficienti. Nel nostro caso - 02. Questo valore è la lunghezza del coefficiente in bit. Cioè, leggiamo i prossimi 2 bit, questo sarà il coefficiente.
10
10
11101110011101100001111100100
3. Se la prima cifra del valore in binario è 1, la lasciamo così com'è: DC_coef = value. Altrimenti, trasformiamo: DC_coef = valore-2 lunghezza del valore +1. Scriviamo il coefficiente nella tabella all'inizio dello zigzag - l'angolo in alto a sinistra.
Trovare i coefficienti AC.
1.
Simile al punto 1, trovare il coefficiente DC. Continuiamo a leggere la sequenza:
10
10
1110
1110011101100001111100100
2.
Prendiamo il valore del nodo. Se è uguale a 0, significa che i valori rimanenti della matrice devono essere riempiti con zeri. Quindi viene codificata la matrice successiva. I primi che hanno letto fino a questo punto e me ne hanno scritto in una personale, riceveranno un vantaggio in karma. Nel nostro caso, il valore del nodo è 0x31.
Primo nibble: 0x3 - questo è il numero di zeri che dobbiamo aggiungere alla matrice. Questi sono 3 coefficienti zero.
Secondo nibble: 0x1 - lunghezza del coefficiente in bit. Leggiamo il bit successivo.
10
10
1110
1
110011101100001111100100
3. Simile al punto 3 della ricerca del coefficiente DC.
Come hai già capito, devi leggere i coefficienti AC fino a quando non troviamo un valore di codice zero o fino a quando la matrice non è piena.
Nel nostro caso otteniamo:
10
10
1110
1
1100
11
101
10
0
0
0
1
11110
0
100
e la matrice:
Hai notato che i valori sono riempiti nello stesso ordine a zigzag?
La ragione per usare questo ordine è semplice: più grandi sono i valori di v e u, meno significativo è il coefficiente S vu nella trasformata discreta del coseno. Pertanto, ad alti rapporti di compressione, i coefficienti insignificanti vengono azzerati, riducendo così la dimensione del file.
[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-1 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[-4 2 2 1 0 0 0 0]
[-1 0 -1 0 0 0 0 0]
[-1 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Oh, ho dimenticato di dire che i coefficienti DC codificati non sono i coefficienti DC stessi, ma le loro differenze tra i coefficienti della tabella precedente (lo stesso canale)! È necessario correggere le matrici:
DC per il 2°: 2 + (-4) = -2
CD per il 3°: -2 + 5 = 3
CD per il 4°: 3 + (-4) = -1
[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………
Ora è l'ordine. Questa regola dura fino alla fine del file.
... e per matrice per Cb e Cr:
[-1 0 0 0 0 0 0 0]
[ 1 1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Poiché qui c'è solo una matrice, i coefficienti DC possono essere lasciati soli.
Calcoli
Quantizzazione
Ricordi che la matrice passa attraverso la fase di quantizzazione? Gli elementi della matrice devono essere moltiplicati termine per termine con gli elementi della matrice di quantizzazione. Resta da scegliere quello di cui hai bisogno. Per prima cosa, abbiamo scansionato il primo componente, il suo componente immagine = 1. Il componente immagine con questo identificatore usa la matrice di quantizzazione 0 (abbiamo il primo dei due). Quindi dopo aver moltiplicato:
[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Allo stesso modo, otteniamo altre 3 matrici del canale Y ...
[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
... e per matrice per Cb e Cr.
[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
Trasformata coseno discreta inversa
La formula non dovrebbe essere difficile *. S vu è la nostra matrice di coefficienti risultante. u è una colonna, v è una riga. s yx - valori di canale diretti.
* In generale, questo non è del tutto vero. Quando sono stato in grado di decodificare e visualizzare l'immagine 16x16 sullo schermo, ho scattato un'immagine 600x600 (a proposito, era la copertina dell'album preferito di Mind.In.A.Box, Lost Alone). Non ha funzionato subito: sono emersi vari bug. Presto ho potuto ammirare l'immagine correttamente caricata. Solo la velocità di download era molto sconvolgente. Ricordo ancora che ci vollero 7 secondi. Ma questo non è sorprendente, se usi sconsideratamente la formula sopra, quindi per calcolare un canale di un pixel, dovrai trovare 128 coseni, 768 moltiplicazioni e alcune aggiunte lì. Pensaci: quasi mille difficili operazioni su un solo canale di un pixel! Fortunatamente, c'è spazio per l'ottimizzazione (dopo molti esperimenti, ho ridotto il tempo di caricamento al limite di una precisione del timer di 15 ms, e successivamente ho cambiato l'immagine in una fotografia 25 volte più grande. Forse scriverò di questo in un articolo separato articolo).
Scriverò il risultato del calcolo solo della prima matrice del canale Y (i valori sono arrotondati):
[ 87 72 50 36 37 55 79 95]
[-10 5 31 56 71 73 68 62]
[-87 -50 6 56 79 72 48 29]
E i restanti 2:
Cb Cr
[ 60 52 38 20 0 -18 -32 -40] [ 19 27 41 60 80 99 113 120]
[ 48 41 29 13 -3 -19 -31 -37] [ 0 6 18 34 51 66 78 85]
[ 25 20 12 2 -9 -19 -27 -32] [-27 -22 -14 -4 7 17 25 30]
[ -4 -6 -9 -13 -17 -20 -23 -25] [-43 -41 -38 -34 -30 -27 -24 -22]
[ -37 -35 -33 -29 -25 -21 -18 -17] [-35 -36 -39 -43 -47 -51 -53 -55]
[ -67 -63 -55 -44 -33 -22 -14 -10] [ -5 -9 -17 -28 -39 -50 -58 -62]
[ -90 -84 -71 -56 -39 -23 -11 -4] [ 32 26 14 -1 -18 -34 -46 -53]
[-102 -95 -81 -62 -42 -23 -9 -1] [ 58 50 36 18 -2 -20 -34 -42]
- Oh, andiamo a mangiare!
- Sì, non entro affatto, di cosa si tratta.
- Una volta ricevuti i valori del colore YCbCr, resta da convertire in RGB, in questo modo: YCbCrToRGB (Y ij, Cb ij, Cr ij), Y ij, Cb ij, Cr ij - le nostre matrici risultanti.
- 4 matrici Y, e una ciascuna Cb e Cr, poiché abbiamo assottigliato i canali e 4 pixel di Y corrispondono a una Cb e Cr. Pertanto, calcola in questo modo: YCbCrToRGB (Y ij, Cb, Cr)
Da YCbCr a RGB
R = Y + 1,402 * CrG = Y - 0,34414 * Cb - 0,71414 * Cr
B = Y + 1,772 * Cb
Non dimenticare di aggiungere 128. Se i valori sono al di fuori dell'intervallo, assegnare i valori limite. La formula è semplice, ma consuma anche una frazione del tempo della CPU.
Ecco le tabelle risultanti per i canali R, G, B per il quadrato 8x8 in alto a sinistra del nostro esempio:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108
231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186
255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134
Fine
In generale, non sono uno specialista di JPEG, quindi difficilmente riesco a rispondere a tutte le domande. È solo che quando stavo scrivendo il mio decoder, ho dovuto spesso affrontare vari problemi incomprensibili. E quando l'immagine è stata visualizzata in modo errato, non sapevo dove ho commesso un errore. Forse ha interpretato male i bit, o forse ha abusato del DCT. Mi sono perso un esempio passo passo, quindi spero che questo articolo possa essere d'aiuto durante la scrittura di un decoder. Penso che copra la descrizione del metodo di base, ma ancora non puoi farlo. Ecco alcuni link che mi hanno aiutato:JPEG è uno degli algoritmi più recenti e potenti. In pratica, è lo standard de facto per le immagini a colori. L'algoritmo opera con aree 8x8, in cui la luminosità e il colore cambiano in modo relativamente fluido. Di conseguenza, quando la matrice di tale regione viene espansa in una doppia serie in coseni (formule sottostanti), solo i primi coefficienti sono significativi. Pertanto, la compressione in JPEG viene eseguita a spese di cambiamenti uniformi nei colori dell'immagine.
L'algoritmo è stato sviluppato da un gruppo di esperti di fotografia specificamente per la compressione di immagini JPEG a 24 bit - il Joint Photographic Expert Group - una divisione all'interno dell'ISO - l'Organizzazione internazionale per la standardizzazione. In generale, l'algoritmo si basa su una trasformata coseno discreta (di seguito DCT), applicata alla matrice immagine per ottenere una nuova matrice di coefficienti. Per ottenere l'immagine originale, viene applicata la trasformazione inversa
DCT scompone l'immagine nelle ampiezze di alcune frequenze, quindi, durante la trasformazione, otteniamo una matrice in cui molti coefficienti sono vicini o uguali a zero. Inoltre, il sistema di percezione del colore umano è incapace di riconoscere determinate frequenze. Pertanto, è possibile approssimare alcuni coefficienti in modo più approssimativo senza una notevole perdita di qualità dell'immagine.
Per questo, viene utilizzata la quantizzazione. Nel caso più semplice, si tratta di uno spostamento aritmetico bit per bit a destra. Con questa trasformazione, alcune informazioni vengono perse, ma è possibile ottenere rapporti di compressione elevati.
Operazione di algoritmo.
Comprimiamo un'immagine a 24 bit.
Passo I.
Traduciamo l'immagine dallo spazio colore RGB, con le componenti responsabili delle componenti rosso (rosso), verde (verde) e blu (blu) del colore del punto, nello spazio colore YCrCb (a volte chiamato YUV).
In esso, Y è la componente di luminosità e Cg, Cb sono le componenti responsabili del colore (rosso cromatico e blu cromatico). A causa del fatto che l'occhio umano è meno sensibile al colore che alla luminosità, diventa possibile archiviare array per componenti Cg e Cb con perdite elevate e, di conseguenza, rapporti di compressione elevati. Questa trasformazione è stata a lungo utilizzata in televisione. Ai segnali responsabili del colore viene assegnata una banda di frequenza più stretta.
La traduzione semplificata dallo spazio colore RGB allo spazio colore YCrCb può essere rappresentata come segue:
La trasformazione inversa si effettua moltiplicando il vettore YUV per la matrice inversa:
Passo 2.
Dividi l'immagine originale in matrici 8x8. Formiamo tre matrici DCT funzionanti da ciascuna - 8 bit separatamente per ciascun componente. A rapporti di compressione più elevati, questo passaggio può essere un po' più difficile. L'immagine è divisa per la componente Y - come nel primo caso, e per le componenti Cr e Cb le matrici sono digitate attraverso una linea e attraverso una colonna. Quelli. dalla matrice originale 16x16 si ottiene una sola matrice DCT funzionante. Inoltre, come è facile intuire, perdiamo 3/4 delle informazioni utili sulle componenti cromatiche dell'immagine e otteniamo subito una doppia compressione. Possiamo farlo lavorando nello spazio YCrCb. Come ha dimostrato la pratica, ciò non influisce in modo significativo sull'immagine RGB risultante.
Passaggio 3.
Applichiamo DCT a ciascuna matrice di lavoro. In questo caso, 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.
In forma semplificata, tale trasformazione può essere rappresentata come segue:
Passaggio 4.
Eseguiamo la quantizzazione. In linea di principio, si tratta semplicemente di dividere la matrice di lavoro per la matrice di quantizzazione elemento per elemento. Per ogni componente (Y, U e V), nel caso generale, è specificata la propria matrice di quantizzazione (di seguito MK).
In questa fase, il rapporto di compressione è controllato e si verifica la perdita maggiore. È chiaro che specificando MK 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 del coefficiente gamma , - la perdita nelle basse frequenze può essere così grande che l'immagine si divide in quadrati 8x8. Le perdite nelle alte frequenze possono manifestarsi nel cosiddetto "effetto Gibbs", quando si forma una sorta di "alone" attorno ai contorni con una netta transizione di colore
Passaggio 5.
Traduciamo la matrice 8x8 in un vettore di 64 elementi usando una scansione a zigzag, ad es. seleziona elementi con indici (0.0). (0.1). (1.0). (2.0) ...
Pertanto, all'inizio del vettore, otteniamo i coefficienti di matrice corrispondenti alle basse frequenze e alla fine - le alte frequenze.
Passaggio 6.
Convoluzione del vettore utilizzando l'algoritmo di codifica di gruppo. In questo caso, otteniamo coppie del tipo (skip, number), dove "skip" è il contatore degli zeri saltati e "number" è il valore che deve essere inserito nella cella successiva.
Quindi, il vettore sarà piegato in coppie (0, 42) (0, 3) (3, -2) (4, 1)
Passaggio 7.
Collassiamo le coppie apprese dalla codifica di Huffman con una tabella fissa.
Il processo di ripristino dell'immagine in questo algoritmo è completamente simmetrico. Il metodo consente di comprimere alcune immagini 10-15 volte senza gravi perdite.
Pipeline delle operazioni utilizzata nell'algoritmo JPEG.
Gli aspetti positivi significativi dell'algoritmo sono che:
- 1) Il rapporto di compressione è impostato
- 2) L'immagine a colori in uscita può essere di 24 bit per punto.
Gli svantaggi dell'algoritmo sono che:
- 1) Quando il rapporto di compressione viene aumentato, l'immagine si divide in quadrati separati (8x8). Ciò è dovuto al fatto che si verificano grandi perdite alle basse frequenze durante la quantizzazione e diventa impossibile ripristinare i dati originali.
- 2) Viene visualizzato l'effetto Gibbs: aloni lungo i confini delle transizioni di colore nitide.
JPEG è stato standardizzato relativamente di recente, nel 1991. Ma anche allora c'erano algoritmi che comprimono più forte con meno perdita di qualità. Il fatto è che le azioni degli sviluppatori dello standard erano limitate dal potere della tecnologia che esisteva in quel momento. Cioè, anche su un personal computer, l'algoritmo doveva funzionare per meno di un minuto su un'immagine media e la sua implementazione hardware doveva essere relativamente semplice ed economica. L'algoritmo doveva essere simmetrico (il tempo di decompressione è approssimativamente uguale al tempo di archiviazione).
Quest'ultimo requisito ha reso possibile l'emergere di fotocamere digitali, dispositivi delle dimensioni di una piccola videocamera che catturano fotografie a 24 bit su una scheda flash da 10-20 MB con un'interfaccia PCMCIA. Quindi la scheda viene inserita nello slot del laptop e il programma corrispondente consente di leggere le immagini. Se l'algoritmo fosse asimmetrico, sarebbe spiacevole aspettare a lungo prima che il dispositivo si "ricarichi": comprimerà l'immagine.
Una caratteristica non molto piacevole di JPEG è anche il fatto che spesso le strisce orizzontali e verticali sul display sono completamente invisibili e possono apparire solo se stampate sotto forma di un motivo moiré. Si verifica quando uno schermo di stampa obliquo viene sovrapposto alle strisce orizzontali e verticali dell'immagine. A causa di queste sorprese, non è consigliabile utilizzare JPEG attivamente nella stampa, impostando coefficienti elevati. Tuttavia, durante l'archiviazione e le immagini destinate alla visualizzazione umana, è attualmente insostituibile.
L'uso diffuso di JPEG è stato limitato per molto tempo, forse solo dal fatto che funziona con immagini a 24 bit. Pertanto, per visualizzare un'immagine con una qualità accettabile su un normale monitor in una tavolozza di 256 colori, è stato necessario utilizzare gli algoritmi appropriati e, quindi, un certo periodo di tempo. Nelle applicazioni destinate a un utente esigente, come i giochi, tali ritardi sono inaccettabili. Inoltre, se le immagini che hai, ad esempio, vengono convertite in formato GIF a 8 bit in JPEG a 24 bit e poi di nuovo in GIF per la visualizzazione, la perdita di qualità si verificherà due volte con entrambe le conversioni. Tuttavia, il guadagno nella dimensione degli archivi è spesso così grande (3-20 volte!) E la perdita di qualità è così piccola che l'archiviazione delle immagini in JPEG è molto efficiente.
Alcune parole dovrebbero essere dette sulle modifiche di questo algoritmo. Sebbene JPEG sia uno standard ISO, il suo formato di file non è stato corretto. Approfittando di ciò, i produttori utilizzano i propri formati incompatibili e, pertanto, possono modificare l'algoritmo. Quindi, le tabelle interne dell'algoritmo, consigliate dall'ISO. vengono sostituiti da loro con le proprie Krones, inoltre, c'è una leggera confusione quando si imposta il grado di perdite. Ad esempio, durante il test, si scopre che la qualità "eccellente", "100%" e "10 punti" danno immagini significativamente diverse. Inoltre, a proposito, la qualità "100%" non significa compressione senza perdita di dati. Ci sono anche opzioni JPEG per applicazioni specifiche.
Come standard ISO, JPEG sta diventando sempre più utilizzato nello scambio di immagini su reti di computer. L'algoritmo JPEG è supportato nei formati Quick Time, PostScript Level 2, Tiff 6.0 e, al momento, occupa un posto di rilievo nei sistemi multimediali.
Caratteristiche dell'algoritmo JPEGG:
Rapporti di compressione: 2-200 (Definito dall'utente).
Classe immagine: Immagini a colori a 24 bit o immagini in scala di grigi senza brusche transizioni di colore (fotografie).
Simmetria: 1.
Caratteristiche speciali: In alcuni casi, l'algoritmo crea un "alone" attorno ai bordi orizzontali e verticali tagliati nell'immagine (effetto Gibbs). Inoltre, quando il rapporto di compressione è elevato, l'immagine viene suddivisa in blocchi di 8x8 pixel.
(pronunciato "japeg" Joint Photographic Experts Group, dal nome dell'organizzazione di sviluppo) è uno dei formati grafici più diffusi utilizzati per archiviare immagini fotografiche e immagini simili. I file contenenti dati JPEG di solito hanno le estensioni .jpeg, .jfif, .jpg, .JPG o .JPE. Di questi, tuttavia, .jpg è l'estensione più popolare su tutte le piattaforme.
1. Gruppo congiunto di esperti fotografici;
2. Un metodo di compressione delle immagini sviluppato da questo gruppo e un formato grafico corrispondente spesso utilizzato sul WWW. È caratterizzato dalla compattezza dei file e, di conseguenza, dal trasferimento veloce, nonché dalla "perdita" della qualità dell'immagine. Utilizzato principalmente per le fotografie, poiché la perdita di qualità è meno critica per loro. Mantiene le impostazioni del colore nello spazio colore RGB.
JPEG(pronunciato " japeg", ing. Gruppo congiunto di esperti fotografici, secondo il nome dello sviluppatore) è uno dei formati grafici più diffusi utilizzati per archiviare immagini fotografiche e immagini simili. I file contenenti dati JPEG di solito hanno le estensioni .jpeg, .jfif, .jpg, .JPG, o .JPE... Tuttavia, tra questi .jpg l'estensione più popolare su tutte le piattaforme. Il tipo MIME è image/jpeg.
JPEG è un algoritmo di compressione dei dati con perdita di dati.
Area di applicazione
L'algoritmo JPEG è più adatto per comprimere fotografie e dipinti contenenti scene realistiche con transizioni uniformi di 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, PNG o RAW.
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, sfortunatamente, 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 una 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 . È 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 i codici di Huffman. Lo standard JPEG consente anche l'uso di una codifica aritmetica significativamente 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.
Quando si salva un'immagine in un file JPEG, viene specificato un parametro di qualità, specificato in alcune unità arbitrarie, ad esempio da 1 a 100 o da 1 a 10. Un numero più alto di solito corrisponde a una qualità migliore (e una dimensione del file compresso maggiore ). Tuttavia, anche utilizzando la qualità più elevata (corrispondente a una matrice di quantizzazione composta da soli), l'immagine ricostruita non coinciderà esattamente con quella originale, che è associata sia all'accuratezza finale dell'esecuzione del DCT, sia alla necessità di arrotondare il valori di Y, Cb, Cr e coefficienti DCT all'intero più vicino. La modalità di compressione JPEG senza perdita, che non utilizza DCT, fornisce una corrispondenza esatta delle immagini ricostruite e originali, tuttavia, la sua bassa efficienza (il rapporto di compressione raramente supera 2) e la mancanza di supporto da parte degli sviluppatori di software non hanno contribuito alla popolarità di JPEG senza perdita .
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 una singola "scansione", ovvero matrice di dati codificati corrispondenti all'immagine sequenzialmente attraversata ("scansionata"). 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 (il metodo di "selezione spettrale" cioè campionamento spettrale), 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 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 ricostruita 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 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 JPEG
Il file JPEG contiene una sequenza marcatori, ognuno dei quali inizia con il byte 0xFF, che indica l'inizio del marker, e byte - identificatore. 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.
| marcatore | byte | Lunghezza | Appuntamento |
|---|
JPEG è uno dei nuovi e sufficientemente potenti algoritmi. In pratica, è lo standard de facto per le immagini a colori. L'algoritmo opera con aree 8x8, in cui la luminosità e il colore cambiano in modo relativamente fluido. Di conseguenza, quando si scompone una tale matrice, l'area in una doppia riga in coseni (vedi formule sotto) è considerata significativa solo dai primi coefficienti, quindi la compressione in JPEG viene eseguita a causa della levigatezza dei cambiamenti di colore nell'immagine .
Un algoritmo sviluppato da un gruppo di esperti di fotografia appositamente per la compressione di immagini a 24 bit. JPEG - Joint Photographic Expert Group è una divisione all'interno dell'ISO - International Organization for Standardization. Il nome dell'algoritmo è ["jei" peg]. In generale, l'algoritmo si basa su una trasformata coseno discreta (di seguito denominata DCT), che viene applicata alla matrice immagine per ottenere una nuova matrice di coefficienti. Per ottenere l'immagine originale, viene applicata una trasformazione inversa.
DCT scompone l'immagine nelle ampiezze di determinate frequenze. Pertanto, durante la trasformazione, otteniamo una matrice in cui molti coefficienti sono vicini o uguali a zero. Inoltre, a causa dell'imperfezione della visione umana, i coefficienti possono essere approssimati in modo più approssimativo senza una notevole perdita di qualità dell'immagine.
Per questo, viene utilizzata la quantizzazione. Nel caso più semplice, si tratta di uno spostamento aritmetico bit per bit a destra. Con questa trasformazione, alcune informazioni vengono perse, ma è possibile ottenere un rapporto di compressione elevato.
Come funziona l'algoritmo
Quindi, consideriamo l'algoritmo in modo più dettagliato (Fig. 2.1). Diciamo che stiamo comprimendo un'immagine a 24 bit.
Passo 1. Traduciamo l'immagine dallo spazio colore RGB, con le componenti responsabili delle componenti rosso (rosso), verde (verde) e blu (blu) del colore del punto, nello spazio colore YCrCb (a volte chiamato YUV).
In esso, Y è la componente di luminosità e Cr, Co sono le componenti responsabili del colore (rosso cromatico e blu cromatico). A causa del fatto che l'occhio umano è meno sensibile al colore che alla luminosità, diventa possibile archiviare array per componenti Cr e Co con grandi perdite e, di conseguenza, grandi rapporti di compressione.Una tale trasformazione è stata a lungo utilizzata in televisione. Ai segnali responsabili del colore viene assegnata una banda di frequenza più stretta. La traduzione semplificata dallo spazio colore RGB allo spazio colore YCrCb può essere rappresentata utilizzando una matrice di transizione:
Passo 2. Dividi l'immagine originale in matrici 8x8. Formiamo 3 matrici DCT funzionanti da ciascuna - 8 bit separatamente per ciascun componente. A rapporti di compressione più elevati, questo passaggio può essere un po' più difficile. L'immagine viene divisa per la componente Y, come nel primo caso, e per le componenti Cr e Cb le matrici vengono digitate tramite una linea e tramite una colonna. Cioè, dalla matrice 16x16 originale, si ottiene solo una matrice DCT funzionante. Allo stesso tempo, come è facile intuire, perdiamo 3/4 delle informazioni utili sulle componenti cromatiche dell'immagine e otteniamo subito una compressione doppia. Possiamo farlo lavorando nello spazio YCrCb. Come ha dimostrato la pratica, questo ha scarso effetto sull'immagine RGB risultante.
Passaggio 3. In forma semplificata, la DCT per n = 8 può essere rappresentata come segue:
nu, v] = ^ Hc (i, u) xC (j, v) y r Y) Yq= InteroRound In questa fase, il rapporto di compressione è controllato e si verifica la perdita maggiore. È chiaro che specificando MK con coefficienti grandi, otterremo più zeri e, quindi, un rapporto di compressione maggiore. La quantizzazione è anche associata a effetti specifici dell'algoritmo. Ad alti valori di gamma, la perdita alle basse frequenze può essere così grande che l'immagine si divide in quadrati 8x8. Perdite nelle alte frequenze possono manifestarsi nelle cosiddette effetto Gibbs, quando si forma una sorta di "alone" attorno ai contorni con una netta transizione di colore. Fare un passo 5. Traduciamo la matrice 8x8 in un vettore di 64 elementi usando la scansione a "zig-zag", ovvero prendiamo elementi con indici (0,0), (0,1), (1,0), (2 ,0 ) ... Pertanto, all'inizio del vettore, otteniamo i coefficienti di matrice corrispondenti alle basse frequenze e alla fine - le alte frequenze. Passaggio 6. Convoluzione del vettore utilizzando l'algoritmo di codifica di gruppo. In questo caso si ottengono coppie del tipo<пропустить, число>dove "salta" è il conteggio degli zeri da saltare e "numero" è il valore da inserire nella cella successiva. Quindi, il vettore 42 3000-2 00001 ... sarà piegato in coppie (0.42) (0.3) (3, -2) (4.1) .... Fare un passo 7. Convolvere le coppie risultanti dalla codifica di Huffman con una tabella fissa. Il processo di ripristino dell'immagine in questo algoritmo è completamente simmetrico. Il metodo consente di comprimere alcune immagini 10-15 volte senza gravi perdite. Gli aspetti positivi significativi dell'algoritmo sono che: ■ viene impostato il grado di compressione; ■ l'immagine a colori in uscita può essere di 24 bit per punto. Gli svantaggi dell'algoritmo sono che: ■ L'aumento del rapporto di compressione divide l'immagine in quadrati separati (8x8). Ciò è dovuto al fatto che si verificano grandi perdite alle basse frequenze durante la quantizzazione e diventa impossibile ripristinare i dati originali. ■ Viene visualizzato l'effetto Gibbs: aloni lungo i bordi delle transizioni di colore nitide. Come già accennato, JPEG è stato standardizzato relativamente di recente, nel 1991. Ma anche allora esistevano algoritmi che comprimono più fortemente con una minore perdita di qualità. Il fatto è che le azioni degli sviluppatori dello standard erano limitate dal potere della tecnologia che esisteva in quel momento. Cioè, anche su un PC, l'algoritmo doveva funzionare per meno di un minuto su un'immagine media e la sua implementazione hardware doveva essere relativamente semplice ed economica. L'algoritmo doveva essere simmetrico (il tempo di decompressione è approssimativamente uguale al tempo di archiviazione). L'adempimento di quest'ultimo requisito ha reso possibile l'emergere di dispositivi come le fotocamere digitali che scattano fotografie a 24 bit su una scheda flash da 8-256 MB. "Ma questa scheda è inserita in uno slot sul tuo laptop e il programma corrispondente ti consente di leggere le immagini Non è vero. Nya, se l'algoritmo fosse asimmetrico, sarebbe spiacevole aspettare a lungo prima che il dispositivo si "ricarichi" - comprimerà l'immagine. È anche una caratteristica non molto bella di JPEG poi, che spesso le strisce orizzontali e verticali sul display sono completamente invisibili e possono apparire solo quando si stampa sotto forma di un motivo moiré. Si verifica quando uno schermo di stampa obliquo viene sovrapposto alle strisce orizzontali e verticali dell'immagine. A causa di queste sorprese, i JPEG non lo sono consigliato attivamente uso in stampa, impostando coefficienti elevati della matrice di quantizzazione. Tuttavia, quando si archiviano immagini destinate alla visualizzazione umana, è attualmente insostituibile. Ampio L'uso di JPEG è stato limitato per molto tempo, forse solo dal fatto che funziona con immagini a 24 bit. Pertanto, per visualizzare un'immagine con una qualità accettabile su un normale monitor in una tavolozza di 256 colori, è stato necessario utilizzare gli algoritmi appropriati e, quindi, un certo periodo di tempo. Nelle applicazioni destinate a un utente esigente, come i giochi, tali ritardi sono inaccettabili. Inoltre, se le immagini che hai, ad esempio, vengono convertite in formato GIF a 8 bit in JPEG a 24 bit e poi di nuovo in GIF per la visualizzazione, la perdita di qualità si verificherà due volte con entrambe le conversioni. Tuttavia, il guadagno nella dimensione degli archivi è spesso così grande (3-20 volte) e la perdita di qualità è così piccola che l'archiviazione delle immagini in JPEG risulta essere molto efficiente. Alcune parole dovrebbero essere dette sulle modifiche di questo algoritmo. Sebbene JPEG sia uno standard ISO, il suo formato di file non è stato corretto. Utilizzando questo, 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. Inoltre, c'è un po' di confusione quando si specifica un tasso di perdita. Ad esempio, durante il test, si scopre che la qualità "eccellente", "100%" e "10 punti" danno immagini significativamente diverse. Allo stesso tempo, tra l'altro, la qualità "100%" non significa compressione senza perdita di dati. Ci sono anche opzioni JPEG per applicazioni specifiche. Come standard ISO, JPEG sta diventando sempre più utilizzato nello scambio di immagini su reti di computer. L'algoritmo JPEG è supportato in Quick Time, PostScript Level 2, Tiff 6.0 e attualmente occupa un posto di rilievo nei sistemi multimediali. Caratteristiche dell'algoritmo JPEG: o! SH. ,. Rapporto di compressione: 2-200 (definito dall'utente). , C,: _ ,. ... Classe immagine: immagini a colori 2jj.bit o iso- | immagini in scala di grigi senza brusche transizioni di colore (foto). Simmetria: 1. Caratteristiche: in alcuni casi, l'algoritmo crea! "alone" attorno ai bordi orizzontali e verticali nitidi nell'immagine (effetto Gibbs). Inoltre, con un elevato rapporto di compressione, iso-! Il riflesso è suddiviso in blocchi di 8x8 pixel.
