L'algoritmo è stato sviluppato dal Joint Photographic Expert Group appositamente per la compressione di immagini a 24 bit e in scala di grigi nel 1991. Questo algoritmo non comprime molto bene le immagini a due livelli, ma fa un buon lavoro nel gestire le immagini a tono continuo in cui i pixel vicini tendono ad avere colori simili. Di solito l'occhio non è in grado di notare alcuna differenza quando viene compresso con questo metodo di 10 o 20 volte.
L'algoritmo si basa sulla DCT applicata ad una matrice di blocchi immagine disgiunti di 8x8 pixel. DCT decompone questi blocchi in base alle ampiezze di determinate frequenze. Il risultato è una matrice in cui molti coefficienti, di regola, sono prossimi allo zero, che può essere rappresentata 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 che venga compressa un'immagine a colori a 24 bit. In questo caso, otteniamo le seguenti fasi di lavoro.
Passo 1. Convertiamo l'immagine dallo spazio RGB allo spazio YCbCr utilizzando la seguente espressione:
Notiamo subito che la trasformazione inversa si ottiene facilmente moltiplicando matrice inversa in un vettore, che è essenzialmente uno spazio YUV:
.
Passo 2. Dividiamo l'immagine originale in matrici 8x8. Formiamo tre matrici DCT funzionanti da ciascuna: 8 bit separatamente per ciascun componente. A rapporti di compressione elevati, il blocco 8x8 viene scomposto in componenti YCbCr nel formato 4:2:0, cioè i componenti per Cb e Cr sono presi attraverso il punto in righe e colonne.
Passaggio 3. Applicazione DCT a blocchi di immagini da 8x8 pixel. Formalmente, la DCT diretta per un blocco 8x8 può essere scritta come
Dove 
. Poiché il DCT è il “cuore” dell'algoritmo JPEG, in pratica è auspicabile calcolarlo il più rapidamente possibile. Un approccio semplice per velocizzare i calcoli consiste nel calcolare in anticipo le funzioni 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 di 8x8 elementi, che descrive uno spazio a 8 dimensioni, per rappresentare le colonne di un blocco in questo spazio. La matrice è una matrice trasposta e fa la stessa cosa, ma per 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 altrettante addizioni, che è significativamente inferiore ai calcoli diretti utilizzando la formula sopra. Ad esempio, per convertire un'immagine che misura 512x512 pixel ti servirà operazioni aritmetiche. Tenendo conto di 3 componenti di luminosità, otteniamo un valore di 12.582.912 operazioni aritmetiche. Il numero di moltiplicazioni e addizioni può essere ulteriormente ridotto utilizzando l'algoritmo di trasformata veloce di Fourier. Di conseguenza, per trasformare un blocco 8x8 dovrai fare 54 moltiplicazioni, 468 addizioni e spostamenti di bit.
Come risultato della DCT otteniamo una matrice in cui i coefficienti sono a sinistra angolo superiore corrispondono alla componente a bassa frequenza dell'immagine e in basso a destra - ad alta frequenza.
Passaggio 4. Quantizzazione. In questa fase, alcune informazioni vengono scartate. Qui, ogni numero della matrice viene diviso per un numero speciale dalla "tabella di quantizzazione" e il risultato viene arrotondato all'intero più vicino:
.
Inoltre, per ciascuna 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, il che aumenterà la dimensione complessiva del file. È chiaro che è difficile per l'utente selezionare in modo indipendente 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 la luminanza e una per la crominanza. Queste tabelle sono presentate di seguito. Il secondo approccio consiste nel sintetizzare (calcolo al volo) una tabella di quantizzazione che dipende da un parametro specificato dall'utente. La tabella stessa è costruita secondo la formula
La fase di quantizzazione è quella in cui viene controllato il rapporto di compressione e dove si verificano le maggiori perdite. È chiaro che specificando tabelle di quantizzazione con coefficienti elevati, otterremo più zeri e, quindi, un rapporto di compressione più elevato.
Effetti specifici dell'algoritmo sono associati anche alla quantizzazione. A grandi valori fase di quantizzazione, le perdite possono essere così grandi che l'immagine si spezza in quadrati monocromatici 8x8. A loro volta, le perdite nelle alte frequenze possono manifestarsi nel cosiddetto “effetto Gibbs”, quando attorno ai contorni si forma un “alone” ondulato con una netta transizione di colore.
Passaggio 5. Convertiamo la matrice 8x8 in un vettore di 64 elementi utilizzando la scansione a zigzag (Fig. 2).
Riso. 2. Scansione a zigzag
Di conseguenza, i coefficienti diversi da zero verranno, di regola, scritti all'inizio del vettore e alla fine si formeranno catene di zeri.
Passaggio 6. Trasformiamo il vettore utilizzando il modificato Algoritmo RLE, all'uscita del quale otteniamo coppie del tipo (salta, numero), dove "salta" è il contatore degli zeri saltati e "numero" è il valore che deve essere inserito nella cella successiva. Ad esempio, il vettore 1118 3 0 0 0 -2 0 0 0 0 1 ... verrà compresso in coppie (0, 1118) (0,3) (3,-2) (4,1) ... .
Va notato che il primo numero della componente convertita è sostanzialmente uguale alla luminosità media del blocco 8x8 ed è chiamato coefficiente DC. Lo stesso per tutti i blocchi immagine. Questa circostanza suggerisce che i coefficienti DC possono essere efficacemente compressi se si ricordano non i loro valori assoluti, ma quelli relativi sotto forma di differenza tra il coefficiente DC del blocco corrente e il coefficiente DC del blocco precedente, e si ricorda il primo coefficiente come è. In questo caso l'ordinamento dei coefficienti DC può essere effettuato, ad esempio, in questo modo (Fig. 3). I restanti coefficienti, detti coefficienti AC, rimangono invariati.
Passaggio 7 Convolviamo le coppie risultanti utilizzando codici Huffman non uniformi con una tabella fissa. Inoltre, per i coefficienti DC e AC, codici diversi, cioè. tavoli diversi con codici Huffman.
Riso. 3. Schema di ordinamento dei coefficienti 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 perdite visive evidenti.
Durante lo sviluppo di questo standard, siamo stati guidati dal fatto che questo algoritmo ho dovuto comprimere le immagini abbastanza velocemente, non più di un minuto in media. Questo è nel 1991! E la sua implementazione hardware dovrebbe essere relativamente semplice ed economica. In questo caso, l'algoritmo doveva essere simmetrico nel tempo operativo. Prestazione ultimo requisito fatto possibile apparizione fotocamere digitali che riprendono immagini a 24 bit. Se l'algoritmo fosse asimmetrico, sarebbe spiacevole aspettare molto tempo affinché il dispositivo si “ricarichi” e comprima l'immagine.
Sebbene Algoritmo JPEG ed è uno standard ISO, il suo formato file non è stato corretto. Approfittando di ciò, i produttori creano i propri formati che sono incompatibili tra loro e, quindi, possono modificare l'algoritmo. Pertanto, le tabelle degli algoritmi interni raccomandati dall'ISO vengono sostituite dalle proprie. Sono disponibili anche opzioni JPEG per applicazioni specifiche.
È facile calcolare che un'immagine a colori non compressa con una dimensione di 2000 * 1000 pixel avrà una dimensione di circa 6 megabyte. Se parliamo di immagini ottenute da fotocamere o scanner professionali alta risoluzione, allora la loro dimensione potrebbe essere ancora maggiore. Nonostante la rapida crescita della capacità dei dispositivi di memorizzazione, diversi algoritmi di compressione delle immagini sono ancora molto rilevanti.
Tutti gli algoritmi esistenti possono essere suddivisi in due grandi classi:
- Algoritmi di compressione senza perdite;
- Algoritmi di compressione con perdita.
Algoritmi di compressione senza perdite
Algoritmo RLE
Tutti gli algoritmi Serie RLE si basano su un'idea molto semplice: i gruppi ripetuti di elementi vengono sostituiti da una coppia (numero di ripetizioni, elemento ripetuto). Consideriamo questo algoritmo usando l'esempio di una sequenza di bit. Questa sequenza alternerà gruppi di zeri e uno. Inoltre, i gruppi avranno spesso più di un elemento. Quindi la sequenza 11111 000000 11111111 00 corrisponderà al seguente insieme di numeri 5 6 8 2. Questi numeri indicano il numero di ripetizioni (il conteggio inizia da uno), ma anche questi numeri devono essere codificati. Assumeremo che il numero di ripetizioni sia compreso tra 0 e 7 (ovvero, 3 bit sono sufficienti per codificare il numero di ripetizioni). Quindi la sequenza considerata sopra viene codificata dalla seguente sequenza di numeri 5 6 7 0 1 2. È facile calcolare che sono necessari 21 bit per codificare la sequenza originale, e nella compressa Metodo RLE Nella forma, questa sequenza richiede 18 bit.Sebbene questo algoritmo sia molto semplice, la sua efficienza è relativamente bassa. Inoltre, in alcuni casi, l'utilizzo di questo algoritmo non porta ad una diminuzione, ma ad un aumento della lunghezza della sequenza. Ad esempio, considera la seguente sequenza 111 0000 11111111 00. La sequenza RL corrispondente è simile a questa: 3 4 7 0 1 2. La lunghezza della sequenza originale è 17 bit, la lunghezza della sequenza compressa è 18 bit.
Questo algoritmo è più efficace per le immagini in bianco e nero. Viene spesso utilizzato anche come uno degli stadi intermedi di compressione di algoritmi più complessi.
Algoritmi del dizionario
L'idea alla base degli algoritmi del dizionario è che vengono codificate catene di elementi della sequenza originale. Questa codifica utilizza un dizionario speciale, ottenuto in base alla sequenza originale.Esiste un'intera famiglia di algoritmi di dizionario, ma esamineremo i più comuni Algoritmo LZW, dal nome dei suoi sviluppatori Lepel, Ziv e Welch.
Il dizionario in questo algoritmo è una tabella che viene riempita con catene di codifica durante l'esecuzione dell'algoritmo. Quando il codice compresso viene decodificato, il dizionario viene ripristinato automaticamente, quindi non è necessario trasmettere il dizionario insieme al codice compresso.
Il dizionario viene inizializzato con tutte le stringhe singleton, ad es. le prime righe del dizionario rappresentano l'alfabeto in cui codifichiamo. Durante la compressione viene ricercata la catena più lunga già registrata nel dizionario. Ogni volta che si incontra una catena che non è stata ancora scritta nel dizionario, questa viene aggiunta lì e viene emesso un codice compresso corrispondente alla catena già scritta nel dizionario. In teoria non vengono imposte restrizioni alla dimensione del dizionario, ma in pratica ha senso limitare questa dimensione, poiché nel tempo iniziano ad apparire catene che non si trovano più nel testo. Inoltre, quando raddoppiamo la dimensione della tabella, dobbiamo allocare un bit in più per memorizzare i codici compressi. Al fine di prevenire tali situazioni, viene introdotto codice speciale, che simboleggia l'inizializzazione della tabella con tutte le catene singleton.
Consideriamo un esempio di algoritmo di compressione. Comprimeremo la linea cuckoocuckoocuckoohood. Supponiamo che il dizionario contenga 32 posizioni, il che significa che ciascuno dei suoi codici occuperà 5 bit. Inizialmente, il dizionario è compilato come segue:
Questa tabella esiste sia dalla parte di chi comprime l'informazione, sia dalla parte di chi la decomprime. Ora esamineremo il processo di compressione. 
La tabella mostra il processo di compilazione del dizionario. È facile calcolare che il codice compresso risultante richiede 105 bit e testo originale(assumendo di spendere 4 bit per codificare un carattere) richiede 116 bit.
In sostanza, il processo di decodifica si riduce alla decodifica diretta dei codici ed è importante che la tabella venga inizializzata allo stesso modo della codifica. Ora diamo un'occhiata all'algoritmo di decodifica. 
Possiamo definire completamente la stringa aggiunta al dizionario al passo i-esimo solo a i+1. Ovviamente la riga i-esima deve terminare con il primo carattere della riga i+1. Quello. Abbiamo appena scoperto come ripristinare un dizionario. Di un certo interesse è la situazione in cui viene codificata una sequenza della forma cScSc, dove c è un carattere e S è una stringa, e la parola cS è già nel dizionario. A prima vista può sembrare che il decoder non riesca a risolvere questa situazione, ma in realtà tutte le righe di questo tipo devono terminare sempre con lo stesso carattere con cui iniziano.
Algoritmi di codifica statistica
Gli algoritmi di questa serie assegnano il codice compresso più breve agli elementi più frequenti delle sequenze. Quelli. sequenze della stessa lunghezza sono codificate con codici compressi di diversa lunghezza. Inoltre, quanto più spesso si verifica una sequenza, tanto più corto è il corrispondente codice compresso.Algoritmo di Huffman
L'algoritmo di Huffman consente di costruire codici prefisso. Puoi pensare ai codici prefisso come a percorsi verso albero binario: un passaggio da un nodo al suo figlio sinistro corrisponde a 0 nel codice, e al suo figlio destro corrisponde a 1. Se etichettiamo le foglie dell'albero con i caratteri da codificare, otteniamo la rappresentazione codice prefisso sotto forma di albero binario.Descriviamo l'algoritmo per costruire un albero di Huffman e ottenere i codici di Huffman.
- I caratteri dell'alfabeto in input formano un elenco di nodi liberi. Ogni foglia ha un peso tale uguale alla frequenza aspetto del simbolo
- Vengono selezionati due nodi dell'albero liberi con i pesi più piccoli
- Il loro genitore viene creato con un peso pari al peso totale
- Il genitore viene aggiunto all'elenco dei nodi liberi e i suoi due figli vengono rimossi da questo elenco
- A un arco che esce dal genitore viene assegnato il bit 1, all'altro il bit 0
- I passaggi a partire dal secondo vengono ripetuti finché nell'elenco dei nodi liberi rimane un solo nodo libero. Questa sarà considerata la radice dell'albero.
Codifica aritmetica
Gli algoritmi di codifica aritmetica codificano stringhe di elementi in una frazione. In questo caso, viene presa in considerazione la distribuzione di frequenza degli elementi. SU questo momento Gli algoritmi di codifica aritmetica sono protetti da brevetti, quindi esamineremo solo l'idea di base.Supponiamo che il nostro alfabeto sia costituito rispettivamente da N simboli a1,...,aN e dalle loro frequenze di occorrenza p1,...,pN. Dividiamo la metà dell'intervallo. In generale, l'algoritmo si basa su una trasformata discreta del coseno (di seguito denominata DCT) applicata alla matrice immagine per ottenere una nuova matrice di coefficienti. Per ottenere l'immagine originale viene applicata una trasformazione inversa.
DCT decompone l'immagine in base alle ampiezze di determinate frequenze. Pertanto, durante la trasformazione, otteniamo una matrice in cui molti coefficienti sono vicini o uguali a zero. Inoltre, a causa delle imperfezioni della visione umana, è possibile approssimare i coefficienti in modo più grossolano senza una notevole perdita di qualità dell'immagine.
A questo scopo viene utilizzata la quantizzazione dei coefficienti. Nel caso più semplice, si tratta di uno spostamento aritmetico bit a destra verso destra. Con questa conversione alcune informazioni vengono perse, ma è possibile ottenere un grado di compressione maggiore.
Come funziona l'algoritmo
Quindi, diamo un'occhiata all'algoritmo in modo più dettagliato (Fig. 2.1). Comprimiamo un'immagine a 24 bit.
Passo 1. Convertiamo l'immagine dallo spazio colore RGB, con le componenti responsabili delle componenti rossa (Rosso), verde (Verde) e blu (Blu) del colore del punto, in spazio colore YCrCb (a volte chiamato YUV).
In esso, Y è la componente di luminosità e Cr, Co sono i componenti responsabili del colore (rosso cromatico e blu cromatico). Poiché l'occhio umano è meno sensibile al colore che alla luminosità, è possibile archiviare array per componenti Cr e Co con grandi perdite e, di conseguenza, rapporti di compressione elevati. Una conversione simile è stata utilizzata da tempo in televisione. Qui viene assegnata una banda di frequenza più stretta per i segnali responsabili del colore. Una traduzione semplificata dallo spazio colore RGB allo spazio colore YCrCb può essere rappresentata utilizzando una matrice di transizione:
Passo 2. Dividiamo 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 riga e tramite una colonna. Cioè, dalla matrice 16x16 originale, si ottiene una sola matrice DCT funzionante. In questo caso, come è facile intuire, perdiamo 3/4 informazioni utili sulle componenti di colore dell'immagine e ottieni immediatamente una compressione 2 volte superiore. Possiamo farlo lavorando nello spazio YCrCb. Come ha dimostrato la pratica, ciò non ha un effetto significativo 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 rY) Yq= InteroRound Questo passaggio è dove viene controllato il rapporto di compressione e dove si verificano le maggiori perdite. È chiaro che specificando MK con coefficienti grandi, otterremo più zeri e, quindi, un rapporto di compressione più elevato. Effetti specifici dell'algoritmo sono associati anche alla quantizzazione. A valori gamma elevati, la perdita delle basse frequenze può essere così grande che l'immagine si spezza in quadrati 8x8. Le perdite alle alte frequenze possono manifestarsi nel cosiddetto Effetto Gibbs, quando si forma una sorta di "alone" attorno ai contorni con una netta transizione di colore. Fare un passo 5. Convertiamo la matrice 8x8 in un vettore di 64 elementi utilizzando la scansione a zig-zag, ovvero prendiamo elementi con indici (0,0), (0,1), (1,0), (2,0 ).. . Pertanto, all'inizio del vettore otteniamo coefficienti di matrice corrispondenti alle basse frequenze e alla fine a quelle alte. Passaggio 6. Comprimiamo il vettore utilizzando l'algoritmo di codifica del gruppo. In questo caso otteniamo coppie del tipo<пропустить, число>, dove "skip" è il conteggio degli zeri saltati e "number" è il valore da inserire nella cella successiva. Pertanto, il vettore 42 3000-2 00001 ... verrà piegato in coppie (0,42) (0,3) (3,-2) (4,1).... Fare un passo 7. Comprimiamo le coppie risultanti utilizzando la 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: ■ il livello di compressione è impostato; ■ L'immagine a colori in uscita può essere di 24 bit per punto. Gli aspetti negativi dell’algoritmo sono che: ■ All'aumentare del livello di compressione, l'immagine viene suddivisa in singoli quadrati (8x8). Ciò è dovuto al fatto che durante la quantizzazione si verificano grandi perdite alle basse frequenze e diventa impossibile ripristinare i dati originali. ■ Appare l'effetto Gibbs: aloni lungo i confini delle transizioni di colore nette. Come già accennato, JPEG è stato standardizzato relativamente di recente, nel 1991. Ma anche allora esistevano algoritmi che comprimevano più fortemente con una minore perdita di qualità. Il fatto è che le azioni degli sviluppatori standard erano limitate dalla potenza della tecnologia esistente in quel momento. Cioè, anche su un PC, l'algoritmo doveva funzionare per meno di un minuto sull'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 la nascita di dispositivi come le fotocamere digitali che scattano fotografie a 24 bit su una scheda flash da 8-256 MB." Quindi questa scheda viene inserita nello slot del laptop e il programma corrispondente ti consente leggere le immagini. Non è vero Nya, se l'algoritmo fosse asimmetrico, sarebbe spiacevole attendere molto tempo affinché il dispositivo si “ricarichi” e comprima l'immagine. Un'altra proprietà non molto piacevole del JPEG è Quello, che spesso le strisce orizzontali e verticali sul display sono completamente invisibili e possono apparire solo durante la stampa sotto forma di effetto moiré. Si verifica quando un retino di stampa inclinato si sovrappone alle strisce orizzontali e verticali dell'immagine. A causa di queste sorprese, JPEG non lo è attivamente raccomandato utilizzato nella stampa, impostando coefficienti di matrice di quantizzazione elevati. Tuttavia, quando si archiviano immagini destinate alla visione umana, attualmente è indispensabile. Largo L'uso del JPEG per molto tempo è stato limitato, forse, solo dal fatto che funziona su immagini a 24 bit. Pertanto, per visualizzare un'immagine con una qualità accettabile su un normale monitor in una tavolozza di 256 colori, era necessario l'uso di algoritmi appropriati e, di conseguenza, una certa quantità di tempo. Nelle applicazioni rivolte ad utenti esigenti, come i giochi, tali ritardi sono inaccettabili. Inoltre, se hai immagini, ad esempio, in formato GIF a 8 bit, convertite in JPEG a 24 bit e poi nuovamente in GIF per la visualizzazione, la perdita di qualità si verificherà due volte durante entrambe le conversioni. Tuttavia, il guadagno in termini di dimensioni dell'archivio è spesso così grande (3-20 volte) e la perdita di qualità è così piccola che la memorizzazione delle immagini in JPEG è molto efficace. Occorre dire qualche parola sulle modifiche di questo algoritmo. Sebbene JPEG sia uno standard ISO, il suo formato file non è stato corretto. Approfittando di ciò, i produttori creano i propri formati che sono incompatibili tra loro e, quindi, possono modificare l'algoritmo. Pertanto, le tabelle degli algoritmi interni raccomandati dall'ISO vengono sostituite dalle proprie. Inoltre, c'è una leggera confusione quando si imposta il grado di perdita. Ad esempio, durante i test risulta che la qualità "eccellente", "100%" e "10 punti" danno immagini significativamente diverse. Tuttavia, la qualità “100%” non significa compressione senza perdite. Sono disponibili anche opzioni JPEG per applicazioni specifiche. Come standard ISO, JPEG viene sempre più utilizzato per lo scambio di immagini nelle reti di computer. L'algoritmo JPEG è supportato nei formati Quick Time, PostScript Level 2, Tiff 6.0 e attualmente occupa un posto di rilievo nei sistemi multimediali. Caratteristiche dell'algoritmo JPEG: o ! w. ,. Rapporto di compressione: 2-200 (impostato dall'utente). ,ts, :_,. . Classe immagine: immagini a colori 2jj.bit o iso-| riflessi in scala di grigi senza transizioni di colore nette (foto). Simmetria: 1. Caratteristiche: in alcuni casi l'algoritmo crea! "alone" attorno ai confini orizzontali e verticali netti di un'immagine (effetto Gibbs). Inoltre, con un rapporto di compressione elevato, iso-! L'immagine è suddivisa in blocchi di 8x8 pixel. Conoscere l'algoritmo JPEG è molto utile non solo per la compressione delle immagini. Utilizza la teoria dell'elaborazione del segnale digitale, dell'analisi matematica, dell'algebra lineare, della teoria dell'informazione, in particolare della trasformata di Fourier, della codifica senza perdite, ecc. Pertanto, la conoscenza acquisita può essere utile ovunque. Se lo desideri, ti suggerisco di eseguire tu stesso gli stessi passaggi parallelamente all'articolo. Controlla quanto sia appropriato il ragionamento di cui sopra per immagini diverse, prova ad apportare le tue modifiche all'algoritmo. È molto interessante. Come strumento, posso consigliare la meravigliosa combinazione di Python + NumPy + Matplotlib + PIL(Pillow). Quasi tutto il mio lavoro (compresa la grafica e l'animazione) è stato svolto utilizzandoli. Attenzione, traffico! Molte illustrazioni, grafici e animazioni (~ 10 Mb). Per ironia della sorte, nell'articolo su JPEG ci sono solo 2 immagini su cinquanta con questo formato. Ci addestreremo sui gatti procione. L'immagine grigia qui sopra è presa come esempio. Combina bene sia le aree omogenee che quelle contrastanti. E se impariamo a comprimere il grigio, non ci saranno problemi con il colore. Puoi pensare mentalmente a come potrebbe essere scomposto un segnale i cui valori diminuiscono gradualmente da un valore massimo all'inizio a un valore minimo alla fine. Un'approssimazione più o meno adeguata potrebbe essere fatta solo dagli armonici verso la fine, il che per noi non è un granché. La figura a sinistra è un'approssimazione di un segnale single-ended. A destra - simmetrico: Quindi ti è venuta l'idea di inventare la tua trasformazione. Ricorda questo: I blocchi di grandi dimensioni non vengono mostrati, poiché visivamente sono quasi indistinguibili da 32x32. Ora vediamo la differenza assoluta con l'immagine originale (amplificata di 2 volte, altrimenti non si vede nulla): 8x8 dà risultati migliori di 4x4. Un ulteriore aumento delle dimensioni non offre più un vantaggio chiaramente visibile. Anche se prenderei seriamente in considerazione 16x16 invece di 8x8: aumentare la complessità del 33% (più sulla complessità nel paragrafo successivo) dà un miglioramento piccolo ma ancora visibile per lo stesso numero di coefficienti. Tuttavia, la scelta di 8x8 sembra abbastanza ragionevole e potrebbe rappresentare la via d'uscita. JPEG è stato pubblicato nel 1991. Penso che tale compressione fosse molto difficile per i processori dell'epoca. Secondo discussione. Una cosa da tenere a mente è che aumentare la dimensione del blocco richiederà più calcoli. Stimiamo quanto. La complessità della conversione, come già sappiamo abbastanza bene: O(N 2), poiché ogni coefficiente è composto da N termini. Ma in pratica viene utilizzato un efficiente algoritmo Fast Fourier Transform (FFT). La sua descrizione va oltre lo scopo di questo articolo. La sua complessità: O(N*logN). Per un'espansione bidimensionale è necessario utilizzarlo due volte N volte. Quindi la complessità della DCT 2D è O(N 2 logN). Ora confrontiamo la complessità del calcolo di un'immagine con un blocco e diversi piccoli: Terzo discussione. Se nell'immagine è presente un bordo di colori netto, ciò influenzerà l'intero blocco. Forse sarebbe meglio che questo isolato fosse abbastanza piccolo, perché in molti isolati vicini probabilmente non esisterà più tale confine. Tuttavia, lontano dai confini, l’attenuazione avviene abbastanza rapidamente. Inoltre, il confine stesso avrà un aspetto migliore. Controlliamolo utilizzando un esempio con un gran numero di transizioni di contrasto, ancora una volta, con solo un quarto dei coefficienti: E per il dessert, considera una qualità del 5% (durante la codifica in Fast Stone). A proposito, qualità circa al 100%. Come puoi immaginare, in questo caso la matrice di quantizzazione è costituita interamente da unità, ovvero non avviene alcuna quantizzazione. Tuttavia, a causa dell'arrotondamento dei coefficienti all'intero più vicino, non è possibile ripristinare con precisione l'immagine originale. Ad esempio, il procione ha mantenuto esattamente il 96% dei pixel, ma il 4% era sfasato di 1/256. Naturalmente tali “distorsioni” non possono essere notate visivamente. Esempio 0(per il riscaldamento) Indicheremo parole come A, B, C..., e le chiameremo simboli. Inoltre, sotto il simbolo può nascondersi qualsiasi cosa: una lettera dell'alfabeto, una parola o un ippopotamo nello zoo. La cosa principale è che simboli identici corrispondono a concetti identici e simboli diversi corrispondono a concetti diversi. Poiché il nostro compito è una codifica (compressione) efficiente, lavoreremo con i bit, poiché queste sono le unità più piccole di rappresentazione delle informazioni. Pertanto, scriviamo l'elenco come ABBAAABA. Invece di "prima parola" e "seconda parola", è possibile utilizzare i bit 0 e 1. Quindi ABBAAABA viene codificato come 01100010 (8 bit = 1 byte). Esempio 1 Esempio 2 Esempio 3 Esempio 4 Ora è tutto in ordine. Abbiamo scoperto come vengono archiviati i controller di dominio: Guardiamo AC: Costruiamo un istogramma della dipendenza dalla quantità per queste coppie e un albero di Huffman. Caratteristiche di implementazione in JPEG: Abbiamo scoperto che ogni blocco è codificato e archiviato in un file come questo: Spero che ora tu capisca l'algoritmo JPEG in modo intuitivo. Grazie per aver letto! AGGIORNAMENTO Tag: aggiungi tag L'algoritmo per la conversione di un'immagine grafica JPEG è costituito da diverse fasi eseguite sull'immagine in sequenza, una dopo l'altra: – conversioni dello spazio colore, – sottocampionamento, – trasformata discreta del coseno (DCT), - quantizzazione, – codifica. Nella fase di conversione dello spazio colore, l'immagine viene convertita dallo spazio colore RGB a YCbCr (dove Y è la luminosità e Cb e Cr sono i componenti della differenza cromatica del punto dell'immagine): Applicazione dello spazio YCbCr invece del solito RGBè spiegato dalle caratteristiche fisiologiche della visione umana, vale a dire dal fatto che il sistema nervoso umano ha una sensibilità significativamente maggiore alla luminosità ( Y) che ai componenti della differenza di colore (in questo caso Cb E Cr). Conversione inversa dello spazio colore (da YCrCb V RGB) ha la forma: L'algoritmo di compressione JPEG consente di comprimere immagini con diverse dimensioni del piano colore. Indichiamo con x io E sì io larghezza e altezza io il piano di colore dell'immagine. Permettere X= massimo(x io), Y= massimo(sì io), definiamo per ciascun piano i coefficienti CIAO= X/ x io E V i= Y/ sì io. Il valore più alto per X E Y secondo l'algoritmo JPEG è 2 16, e per CIAO E V i– 2 2 . Pertanto, la larghezza e l'altezza dei piani di colore possono essere da 1 a 4 volte inferiori alle dimensioni del piano più grande. Per ordinario RGB immagini, le dimensioni di tutti i piani di colore sono uguali. Il sottocampionamento consiste nel ridurre la dimensione dei piani Cr E Cb. La riduzione più comune è 2 volte in larghezza e 2 volte in altezza (vedere Figura 1). Per questo Cr E Cb I piani dell'immagine sono divisi in blocchi con una dimensione di 2 per 2 pixel, e il blocco viene sostituito da un campione dei componenti della differenza di colore (al posto dei 4 campioni esistenti, viene messa la loro media aritmetica per ciascun blocco, il che rende è possibile ridurre di 2 volte la dimensione dell'immagine originale). Figura 1 – Tipi comuni di downsampling Quindi, separatamente per ciascun componente dello spazio colore Y, Cb E Cr, viene eseguita una trasformata coseno discreta diretta. Per fare ciò, l'immagine viene divisa in blocchi con una dimensione di 8 per 8 pixel e ciascun blocco viene trasformato secondo la formula: L'utilizzo della trasformazione discreta del coseno permette di passare dalla rappresentazione spaziale dell'immagine a quella spettrale. La trasformata discreta inversa del coseno ha la forma: Successivamente, puoi procedere alla quantizzazione delle informazioni ricevute. L'idea della quantizzazione è di scartare una certa quantità di informazioni. È noto che l'occhio umano è meno sensibile alle alte frequenze (soprattutto alle alte frequenze dei componenti della differenza di colore; la maggior parte delle immagini fotografiche contiene poche componenti ad alta frequenza); Inoltre, la comparsa delle alte frequenze è una conseguenza del processo di digitalizzazione, ad es. a causa della comparsa di rumore di campionamento e di quantizzazione. In questa fase, il cosiddetto tabelle di quantizzazione- matrici costituite da numeri interi positivi di dimensione 8 per 8, in cui sono divise le frequenze corrispondenti dei blocchi immagine, il risultato viene arrotondato a un numero intero: Il processo di dequantizzazione utilizza le stesse tabelle della quantizzazione. La dequantizzazione consiste nel moltiplicare le frequenze quantizzate per gli elementi corrispondenti della tabella di quantizzazione: Pertanto, all’aumentare del fattore di quantizzazione, aumenta la quantità di informazioni scartate. Diamo un'occhiata a questo in modo più dettagliato utilizzando un esempio. Blocco prima della quantizzazione: 3862, –22, –162, –111, –414, 12, 717, 490, 383, 902, 913, 234, –555, 18, –189, 236, 229, 707, –708, 775, 423, –411, –66, –685, 231, 34, –928, 34, –1221, 647, 98, –824, –394, 128, –307, 757, 10, –21, 431, 427, 324, –874, –367, –103, –308, 74, –1017, 1502, 208, –90, 114, –363, 478, 330, 52, 558, 577, 1094, 62, 19, –810, –157, –979, –98 Tabella di quantizzazione (qualità 90): 24, 16, 16, 24, 40, 64, 80, 96, 16, 16, 24, 32, 40, 96, 96, 88, 24, 24, 24, 40, 64, 88, 112, 88, 24, 24, 32, 48, 80, 136, 128, 96, 32, 32, 56, 88, 112, 176, 168, 120, 40, 56, 88, 104, 128, 168, 184, 144, 80, 104, 128, 136, 168, 192, 192, 160, 112, 144, 152, 160, 176, 160, 168, 160 Blocco dopo la quantizzazione: 161, –1, –10, –5, –10, 0, 9, 5, 24, 56, 38, 7, –14, 0, –2, 3, 10, 29, –30, 19, 7, –5, –1, –8, 10, 1, –29, 1, –15, 5, 1, –9, –12, 4, –5, 9, 0, 0, 3, 4, 8, –16, –4, –1, –2, 0, –6, 10, 3, –1, 1, –3, 3, 2, 0, 3, 5, 8, 0, 0, –5, –1, –6, –1 3864, –16, –160, –120, –400, 0, 720, 480, 384, 896, 912, 224, –560, 0, –192, 264, 240, 696, –720, 760, 448, –440, –112, –704, 240, 24, –928, 48,–1200, 680, 128, –864, –384, 128, –280, 792, 0, 0, 504, 480, 320, –896, –352, –104, –256, 0,–1104, 1440, 240, –104, 128, –408, 504, 384, 0, 480, 560, 1152, 0, 0, –880, –160,–1008, –160 Tabella di quantizzazione (qualità 45): 144, 96, 88, 144, 216, 352, 456, 544, 104, 104, 128, 168, 232, 512, 536, 488, 128, 112, 144, 216, 352, 504, 616, 496, 128, 152, 192, 256, 456, 776, 712, 552, 160, 192, 328, 496, 600, 968, 912, 680, 216, 312, 488, 568, 720, 920, 1000, 816, 432, 568, 696, 776, 912, 1072, 1064, 896, 640, 816, 840, 872, 992, 888, 912, 880 Blocco dopo la quantizzazione: 27, 0, –2, –1, –2, 0, 2, 1, 4, 9, 7, 1, –2, 0, 0, 0, 2, 6, –5, 4, 1, –1, 0, –1, 2, 0, –5, 0, –3, 1, 0, –1, –2, 1, –1, 2, 0, 0, 0, 1, 2, –3, –1, 0, 0, 0, –1, 2, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, –1, 0, –1, 0 Blocco dopo la conversione inversa: 3888, 0, –176, –144, –432, 0, 912, 544, 416, 936, 896, 168, –464, 0, 0, 0, 256, 672, –720, 864, 352, –504, 0, –496, 256, 0, –960, 0,–1368, 776, 0, –552, –320, 192, –328, 992, 0, 0, 0, 680, 432, –936, –488, 0, 0, 0,–1000, 1632, 0, 0, 0, 0, 912, 0, 0, 896, 640, 816, 0, 0, –992, 0, –912, 0 Come si può vedere, nel primo caso il cambiamento DC il coefficiente risultante dalla compressione è 2, e nel secondo 26, mentre è quantizzato DC il coefficiente nel secondo caso è 6 volte inferiore rispetto al primo. La codifica è la fase finale della compressione durante la quale i blocchi di immagini vengono convertiti in forma vettoriale secondo la regola specificata dai blocchi della forma: 0, 1, 5, 6, 14, 15, 27, 28, 2, 4, 7, 13, 16, 26, 29, 42, 3, 8, 12, 17, 25, 30, 41, 43, 9, 11, 18, 24, 31, 40, 44, 53, 10, 19, 23, 32, 39, 45, 52, 54, 20, 22, 33, 38, 46, 51, 55, 60, 21, 34, 37, 47, 50, 56, 59, 61, 35, 36, 48, 49, 57, 58, 62, 63 dove gli indici vettoriali dei corrispondenti componenti della matrice sono indicati come elementi a blocco. In questo caso l'elemento zero viene codificato come differenza con l'elemento zero del blocco precedente. Zero elementi indicano DC, contengono la componente costante del blocco (tutti gli altri elementi AC sono solitamente indicati AC.). I dati risultanti vengono quindi compressi utilizzando la codifica aritmetica o una modifica dell'algoritmo di Huffman. Questa fase non è di grande interesse dal punto di vista della steganografia nelle immagini grafiche, quindi esula dall'ambito della nostra considerazione.
Hai capito correttamente dal titolo che questa non è una descrizione molto ordinaria dell'algoritmo JPEG (ho descritto in dettaglio il formato del file nell'articolo "Decodifica JPEG for Dummies"). Innanzitutto, il metodo scelto per presentare il materiale presuppone che non sappiamo nulla non solo del JPEG, ma anche della trasformata di Fourier e della codifica di Huffman. In generale, ricordiamo poco delle lezioni. Hanno semplicemente scattato la foto e hanno iniziato a pensare a come comprimerla. Pertanto, ho cercato di esprimere chiaramente solo l'essenza, ma in cui il lettore svilupperà una comprensione abbastanza profonda e, soprattutto, intuitiva dell'algoritmo. Formule e calcoli matematici: come minimo, solo quelli importanti per capire cosa sta succedendo.
Qualunque sia l'algoritmo di compressione delle informazioni, il suo principio sarà sempre lo stesso: trovare e descrivere modelli. Maggiore è il numero di modelli, maggiore è la ridondanza, minore è l'informazione. Gli archiviatori e i programmatori sono solitamente “su misura” per un tipo specifico di informazioni e sanno dove trovarle. In alcuni casi, uno schema è immediatamente visibile, come nell'immagine di un cielo azzurro. Ogni riga della sua rappresentazione digitale può essere descritta in modo abbastanza accurato da una linea retta.Rappresentazione vettoriale
Innanzitutto, controlliamo quanto sono dipendenti due pixel vicini. È logico supporre che molto probabilmente saranno molto simili. Controlliamo questo per tutte le coppie di immagini. Contrassegniamoli sul piano delle coordinate con punti in modo che il valore del punto lungo l'asse X sia il valore del primo pixel e lungo l'asse Y sia il secondo. Per la nostra immagine che misura 256 x 256, otteniamo 256*256/2 pixel: 
Com'era prevedibile, la maggior parte dei punti si trovano sopra o vicino alla linea y=x (e ce ne sono ancora di più di quelli che si possono vedere nella figura, poiché si sovrappongono più volte e, inoltre, sono traslucidi). Se così fosse sarebbe più semplice lavorare ruotandoli di 45°. Per fare ciò, è necessario esprimerli in un sistema di coordinate diverso. 
I vettori fondamentali del nuovo sistema sono ovviamente: . Siamo costretti a dividere per la radice di due per ottenere un sistema ortonormale (le lunghezze dei vettori base sono pari a uno). Qui viene mostrato che un certo punto p = (x, y) nel nuovo sistema sarà rappresentato come un punto (a 0 , a 1). Conoscendo i nuovi coefficienti, possiamo facilmente ottenere quelli vecchi capovolgendoli. Ovviamente la prima (nuova) coordinata è la media, e la seconda è la differenza di xey (ma divisa per radice 2). Immagina che ti venga chiesto di lasciare solo uno dei valori: uno 0 o un 1 (ovvero, equiparare l'altro a zero). È meglio scegliere uno 0, poiché molto probabilmente il valore di 1 sarà attorno allo zero. Questo è cosa succede se ripristiniamo l'immagine solo da 0: 
Ingrandimento 4x: 
Questa compressione non è molto impressionante, a dire il vero. È meglio dividere in modo simile l'immagine in triplette di pixel e presentarli in uno spazio tridimensionale. 
Questo è lo stesso grafico, ma da diversi punti di vista. Le linee rosse sono gli assi che si sono suggeriti. Corrispondono ai vettori: . Lascia che ti ricordi che devi dividere per alcune costanti in modo che le lunghezze dei vettori diventino uguali a uno. Quindi, espandendo su questa base, otteniamo 3 valori: 0, 1, 2 e 0 è più importante di 1 e 1 è più importante di 2. Se eliminiamo un 2, il grafico si “appiattirà” nella direzione del vettore e 2. Questo foglio tridimensionale già piuttosto sottile diventerà piatto. Non perderà molto, ma ci libereremo di un terzo dei valori. Confrontiamo le immagini ricostruite dalle triple: (a 0 , 0, 0), (a 1 , a 2 , 0) e (a 0 , a 1 , a 2). Nell'ultima versione non abbiamo buttato via nulla, quindi prenderemo l'originale. 
Ingrandimento 4x: 
Il secondo disegno è già buono. Le aree nitide sono state leggermente attenuate, ma nel complesso l'immagine è stata conservata molto bene. E ora dividiamo per quattro allo stesso modo e determiniamo visivamente la base nello spazio quadridimensionale... Oh, beh, sì. Ma puoi indovinare quale sarà uno dei vettori base: (1,1,1,1)/2. Pertanto, si può 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 come trasformare (x 0 , x 1 , ..., x n-1) in (a 0 , a 1 , ..., a n-1) in modo che ogni valore di a i sia meno importante rispetto ai precedenti. Se riusciamo a farlo, forse gli ultimi valori della sequenza possono essere eliminati del tutto. Gli esperimenti di cui sopra suggeriscono che è possibile. Ma non puoi fare a meno di un apparato matematico.
Quindi, dobbiamo trasformare i punti in una nuova base. Ma prima devi trovare una base adeguata. Torniamo al primo esperimento di abbinamento. Consideriamolo in generale. Abbiamo definito i vettori base: 
Abbiamo espresso il vettore attraverso di loro P:
o in coordinate: 
Per trovare uno 0 e un 1 è necessario proiettare P SU e 0 e e 1 rispettivamente. E per questo devi trovare il prodotto scalare
simile:
Nelle coordinate: 
Spesso è più conveniente effettuare la trasformazione in forma matriciale. 
Quindi A = EX e X = E T A. Questa è una forma bella e conveniente. La matrice E si chiama matrice di trasformazione ed è ortogonale, la incontreremo più avanti. Transizione dai vettori alle funzioni.
È conveniente lavorare con vettori di piccole dimensioni. Tuttavia, vogliamo trovare pattern in blocchi più grandi, quindi invece di vettori N-dimensionali è più conveniente operare con le sequenze che rappresentano l'immagine. Chiamerò tali successioni funzioni discrete, poiché il ragionamento seguente vale anche per le funzioni continue.
Tornando al nostro esempio, immaginiamo una funzione f(i), definita solo in due punti: f(0)=x e f(1)=y. Allo stesso modo, definiamo le funzioni di base e 0 (i) ed e 1 (i) in base alle basi e 0 e e 1 . Noi abbiamo: 
Questa è una conclusione molto importante. Ora nella frase “espansione di un vettore in vettori ortonormali” possiamo sostituire la parola “vettore” con “funzione” e ottenere l'espressione completamente corretta “espansione di una funzione in funzioni ortonormali”. Non importa che abbiamo ottenuto una funzione così breve, poiché lo stesso ragionamento vale 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. Al contrario, puoi rappresentare una funzione come un vettore. Inoltre, una funzione continua ordinaria può essere rappresentata da un vettore a dimensione infinita, sebbene non nello spazio euclideo, ma nello spazio di Hilbert. Ma non andremo lì; saremo interessati solo alle funzioni discrete.
E il nostro problema di trovare una base si trasforma nel problema di trovare un sistema adeguato di funzioni ortonormali. Nel ragionamento seguente, si presuppone che in qualche modo abbiamo già determinato un insieme di funzioni di base, in base alle quali scomporremo.
Diciamo che abbiamo qualche funzione (rappresentata, ad esempio, da valori) che vogliamo rappresentare come la somma di altre. Puoi rappresentare questo processo in forma vettoriale. Per scomporre una funzione è necessario “proiettarla” sulle funzioni base una per una. In senso vettoriale, il calcolo della proiezione fornisce l'avvicinamento minimo del vettore originale a un altro in termini di distanza. Ricordando che la distanza viene calcolata utilizzando il teorema di Pitagora, una rappresentazione simile sotto forma di funzioni fornisce la migliore approssimazione della radice quadrata di una funzione rispetto a un'altra. Pertanto, ciascun coefficiente (k) determina la “vicinanza” della funzione. Più formalmente, k*e(x) è la migliore approssimazione quadratica media 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'è una rappresentazione vettoriale. 
In relazione al nostro esperimento di divisione in coppie, possiamo dire che questi due punti (0 e 1 lungo l'ascissa) sono una coppia di pixel vicini (x, y).
La stessa cosa, ma con l'animazione: 
Se prendiamo 3 punti, allora dobbiamo considerare i vettori tridimensionali, ma l'approssimazione sarà più accurata. E per una funzione discreta con N valori, devi considerare i vettori N-dimensionali.
Avendo un insieme di coefficienti ottenuti, puoi facilmente ottenere la funzione originale sommando le funzioni base prese con i coefficienti corrispondenti. L'analisi di questi coefficienti può fornire molte informazioni utili (a seconda della base). Un caso particolare 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 carino scomporre una funzione nei suoi componenti. All'inizio del XIX secolo anche Fourier pensava a questo. È vero, non aveva la foto di un procione, quindi ha dovuto studiare la distribuzione del calore lungo l'anello di metallo. Poi scoprì che è molto conveniente esprimere la temperatura (e la sua variazione) in ciascun punto dell'anello come somma di sinusoidi con periodi diversi. "Fourier ha scoperto (consiglio di leggerlo, è interessante) che la seconda armonica decade 4 volte più velocemente della prima, e le armoniche di ordine superiore decadono a una velocità ancora più veloce."
In generale, si scoprì presto che le funzioni periodiche possono essere perfettamente scomposte nella somma delle sinusoidi. E poiché in natura esistono molti oggetti e processi descritti da funzioni periodiche, è apparso un potente strumento per la loro analisi.
Forse uno dei processi periodici più visivi è il suono. 
Se mi avessero dato i valori dell'ultima funzione in quel momento in cui non sapevo della serie di Fourier e mi avessero chiesto di analizzarli, allora sarei sicuramente rimasto confuso e non avrei potuto dire nulla di utile. Ebbene sì, una sorta di funzione, ma come fai a capire che c'è qualcosa di ordinato lì? Ma se avessi indovinato di ascoltare l'ultima funzione, il mio orecchio avrebbe colto un tono puro in mezzo al rumore. Anche se non molto buono, poiché durante la generazione ho selezionato appositamente tali parametri in modo che sul grafico riassuntivo il segnale si dissolvesse visivamente nel rumore. A quanto ho capito, non è ancora chiaro come faccia esattamente un apparecchio acustico. Tuttavia, recentemente è diventato chiaro che non decompone il suono in onde sinusoidali. Forse un giorno capiremo come ciò accade e appariranno algoritmi più avanzati. Bene, per ora lo stiamo facendo alla vecchia maniera.
Perché non provare a utilizzare le sinusoidi come base? In effetti, lo abbiamo già fatto. Ricordiamo la nostra scomposizione in 3 vettori base e presentiamoli nel grafico: 
Sì, sì, lo so, sembra un aggiustamento, ma con tre vettori è difficile aspettarsi di più. Ma ora è chiaro come ottenere, ad esempio, 8 vettori base: 
Un controllo non molto complicato mostra che questi vettori sono a coppie perpendicolari, cioè ortogonali. Ciò significa che possono essere utilizzati come base. La trasformazione su tale base è ampiamente conosciuta ed è chiamata trasformata discreta del coseno (DCT). Penso che sia chiaro dai grafici sopra come si ottiene la formula di trasformazione DCT:
Questa è sempre la stessa formula: A = EX con una base sostituita. I vettori base della DCT specificata (sono anche vettori riga della matrice E) sono ortogonali, ma non ortonormali. Questo va ricordato durante la trasformazione inversa (non mi dilungherò su questo, ma per chi fosse interessato, la DCT inversa ha termine 0.5*a 0 , poiché il vettore base zero è maggiore 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 alcune argomentazioni sull'opportunità di scegliere una base del genere, non esistono ancora argomenti reali. Infatti, a differenza del suono, la fattibilità della scomposizione di un'immagine in funzioni periodiche è molto meno ovvia. Tuttavia, l'immagine può effettivamente essere troppo imprevedibile anche in una piccola area. Pertanto, l'immagine è divisa in pezzi abbastanza piccoli, ma non assolutamente piccoli, affinché la scomposizione abbia un senso. In JPEG, l'immagine viene “tagliata” in quadrati 8x8. All'interno di un pezzo del genere, le fotografie sono generalmente molto uniformi: lo sfondo più piccole fluttuazioni. Tali aree sono meravigliosamente avvicinate dalle sinusoidi.
Bene, diciamo che questo fatto è più o meno intuitivo. Ma c'è una brutta sensazione riguardo alle transizioni di colore improvvise, perché cambiare lentamente le funzioni non ci salverà. Dobbiamo aggiungere varie funzioni ad alta frequenza che fanno il loro lavoro, ma appaiono lateralmente su uno sfondo omogeneo. Prendiamo un'immagine 256x256 con due aree contrastanti: 
Scomponiamo ogni riga utilizzando DCT, ottenendo così 256 coefficienti per riga.
Quindi lasciamo solo i primi n coefficienti e impostiamo il resto a zero e, quindi, l'immagine verrà presentata come una somma delle sole prime armoniche: 
Il numero nell'immagine è il numero di quote rimaste. Nella prima immagine rimane solo il valore medio. Sul secondo è già stata aggiunta una sinusoide a bassa frequenza, ecc. A proposito, presta attenzione al bordo: nonostante tutta la migliore approssimazione, accanto alla diagonale sono chiaramente visibili 2 strisce, una più chiara, l'altra più scura. Parte dell'ultima immagine ingrandita 4 volte:
E in generale, se lontano dal confine vediamo uno sfondo iniziale uniforme, allora avvicinandosi ad esso l'ampiezza inizia a crescere, raggiunge infine il valore minimo, per poi diventare improvvisamente massimo. Questo fenomeno è noto come effetto Gibbs. 
L'altezza di queste gobbe, che compaiono in prossimità delle discontinuità della funzione, non diminuirà all'aumentare del numero degli addendi delle funzioni. In una trasformazione discreta scompare solo quando vengono preservati quasi tutti i coefficienti. Più precisamente, diventa invisibile.
L'esempio seguente è del tutto simile alla scomposizione dei triangoli sopra, ma su un vero procione: 
Quando si studia la DCT si può avere la falsa impressione che siano sempre sufficienti solo i primi coefficienti (a bassa frequenza). Questo è vero per molte fotografie, quelle il cui significato non cambia radicalmente. Tuttavia, al confine delle aree contrastanti, i valori “salteranno” rapidamente e anche gli ultimi coefficienti saranno elevati. Pertanto, quando senti parlare delle proprietà di conservazione dell'energia del DCT, tieni conto del fatto che si applica a molti tipi di segnali incontrati, ma non a tutti. Ad esempio, pensa a come sarebbe una funzione discreta, i cui coefficienti di espansione sono uguali a zero, tranne l'ultimo. Suggerimento: pensa alla scomposizione in forma vettoriale.
Nonostante i difetti, la base scelta è una delle migliori tra le fotografie reali. Vedremo un piccolo confronto con gli altri un po' più tardi. DCT contro tutto il resto
Quando ho studiato la questione delle trasformazioni ortogonali, a dire il vero, non ero molto convinto dall'argomentazione secondo cui tutto intorno è la somma di oscillazioni armoniche, quindi è necessario scomporre le immagini in sinusoidi. O forse alcune funzioni passo-passo sarebbero migliori? Pertanto, ho cercato risultati di ricerca sull'ottimalità della DCT su immagini reali. Il fatto che “è la DCT a trovarsi più spesso nelle applicazioni pratiche a causa della proprietà di “compattazione energetica”” è scritto ovunque. Questa proprietà fa sì che la massima quantità di informazione sia contenuta nei primi coefficienti. E perché? Non è difficile condurre una ricerca: ci armiamo di un mucchio di immagini diverse, di basi conosciute diverse e iniziamo a calcolare la deviazione standard dall’immagine reale per un diverso numero di coefficienti. Ho trovato un piccolo studio in un articolo (immagini utilizzate) su questa tecnica. Mostra i grafici della dipendenza dell'energia immagazzinata dal numero dei primi coefficienti di espansione per basi diverse. Se guardavi le classifiche, eri convinto che DCT occupi costantemente un onorevole... ehm... 3° posto. Come mai? Che tipo di conversione KLT è questa? Stavo lodando il DCT, e poi... KLT
Tutte le trasformazioni, tranne KLT, sono trasformazioni con base costante. E in KLT (trasformata di Karhunen-Loeve) viene calcolata la base ottimale per diversi vettori. Viene calcolato in modo tale che i primi coefficienti forniscano l'errore quadratico medio più piccolo in totale per tutti i vettori. In precedenza abbiamo eseguito manualmente un lavoro simile, determinando visivamente la base. All'inizio sembra una buona idea. Potremmo, ad esempio, dividere l'immagine in piccole sezioni e calcolare la propria base per ciascuna. Ma non c'è solo la preoccupazione di memorizzare questa base, ma anche l'operazione di calcolo è piuttosto laboriosa. Ma DCT perde solo poco e inoltre DCT ha algoritmi di conversione veloci. DFT
DFT (Trasformata Discreta di Fourier) - trasformata discreta di Fourier. Con questo nome a volte viene indicata non solo una trasformazione specifica, ma anche l'intera classe delle trasformazioni discrete (DCT, DST...). Diamo un'occhiata alla formula DFT: 
Come puoi immaginare, questa è una trasformazione ortogonale con una sorta di base complessa. Poiché una forma così complessa si presenta un po' più spesso del solito, ha senso studiarne la derivazione.
Può sembrare che qualsiasi segnale armonico puro (con frequenza intera) con decomposizione DCT fornirà solo un coefficiente diverso da zero corrispondente a questa armonica. Questo non è vero perché oltre alla frequenza è importante anche la fase di questo segnale. Ad esempio, l'espansione del seno in coseno (in modo simile nell'espansione discreta) sarà così:
Questo per quanto riguarda le armoniche pure. Ne ha generati un sacco di altri. L'animazione mostra i coefficienti DCT di un'onda sinusoidale in diverse fasi. 
Se ti è sembrato che le colonne ruotassero attorno ad un asse, non ti è sembrato.
Ciò significa che ora espanderemo la funzione nella somma di sinusoidi non solo di frequenze diverse, ma anche spostate lungo qualche fase. Sarà più conveniente considerare lo sfasamento usando l'esempio del coseno:
Una semplice identità trigonometrica fornisce un risultato importante: lo sfasamento è sostituito dalla somma di seno e coseno, presi con i coefficienti cos(b) e sin(b). Ciò significa che le funzioni possono essere espanse nella somma di seni e coseni (senza fasi). Questa è una forma trigonometrica comune. Tuttavia, il complesso viene utilizzato molto più spesso. Per ottenerlo è necessario utilizzare la formula di Eulero. Sostituendo semplicemente le formule derivate di seno e coseno, otteniamo: 
Ora per un piccolo cambiamento. Il trattino basso è il numero coniugato.
Otteniamo l'uguaglianza finale:
c è un coefficiente complesso, la cui parte reale è uguale al coefficiente coseno e la parte immaginaria è uguale al coefficiente seno. E l'insieme dei punti (cos(b), sin(b)) è un cerchio. In tale registrazione, ogni armonica entra nell'espansione sia con una frequenza positiva che negativa. Pertanto, in varie formule di analisi di Fourier, la somma o l'integrazione avviene solitamente da meno a più infinito. Spesso è più conveniente eseguire i calcoli in questa forma complessa.
La trasformazione decompone il segnale in armoniche con frequenze da uno a N oscillazioni nella regione del segnale. Ma la frequenza di campionamento è N per area del segnale. E secondo il teorema di Kotelnikov (noto anche come teorema di Nyquist-Shannon), la frequenza di campionamento deve essere almeno il doppio della frequenza del segnale. Se così non fosse, l'effetto è la comparsa di un segnale con una falsa frequenza: 
La linea tratteggiata mostra il segnale ricostruito in modo errato. Hai spesso riscontrato questo fenomeno nella vita. Ad esempio, il divertente movimento delle ruote di un'auto in un video o l'effetto moiré.
Ciò porta al fatto che la seconda metà delle ampiezze del complesso N sembra essere costituita da altre frequenze. Queste false armoniche della seconda metà sono un'immagine speculare della prima e non portano informazioni aggiuntive. Pertanto, 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 non è preso interamente dal bordo. Inoltre, ogni armonica è quasi specularmente simmetrica rispetto al suo centro. Tutti questi fenomeni sono particolarmente forti alle basse frequenze, che sono importanti per noi durante la codifica. Anche questo è negativo perché i confini dei blocchi saranno visibili nell'immagine compressa. Lasciatemi illustrare la base DFT con N=8. Le prime 2 righe sono componenti del coseno, le ultime sono seno: 
Prestare attenzione alla comparsa di componenti duplicati man mano che la frequenza aumenta. 
Le cose vanno estremamente male con il primo.
Quindi forse possiamo farlo 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 da fare al riguardo.Ora legale
Cosa succede se usiamo i seni invece dei coseni nella DCT? Otterremo la Trasformata Sinusoidale Discreta (DST). Ma per il nostro compito non sono tutti interessanti, poiché sia il periodo intero che quello semi-seno sono vicini allo zero ai confini. Cioè, otterremo all'incirca la stessa scomposizione inappropriata di quella di DFT. Ritornando al DCT
Come va alle frontiere? Bene. Ci sono antifasi e nessuno zero. Tutto il resto
Trasformate non di Fourier. Non lo descriverò.
WHT: la matrice è composta solo da componenti di gradini con valori -1 e 1.
Haar è anche una trasformata wavelet ortogonale.
Sono inferiori al DCT, ma sono più facili da calcolare.
Non sarà facile, vero? Tuttavia per alcuni tipi di immagini è possibile selezionare una base migliore rispetto a quella DCT. Trasformazioni 2D
Ora proviamo a condurre un simile esperimento. Prendiamo, ad esempio, un pezzo di un'immagine. 
Il suo grafico 3D: 
Esaminiamo DCT(N=32) attraverso ciascuna riga: 
Ora voglio che tu scorra ogni colonna dei coefficienti risultanti, cioè dall'alto verso il basso. Ricorda che il nostro obiettivo è lasciare meno valori possibili, eliminando quelli non significativi. Probabilmente hai intuito che i valori di ciascuna colonna dei coefficienti risultanti possono essere espansi esattamente allo stesso modo dei valori dell'immagine originale. Nessuno ci limita nella scelta di una matrice di trasformazione ortogonale, ma lo rifaremo utilizzando DCT(N=8): 
Il coefficiente (0,0) si è rivelato troppo grande, quindi nel grafico è ridotto di 4 volte.
Allora, cos'è successo?
L'angolo in alto a sinistra è i coefficienti più significativi dell'espansione dei coefficienti più significativi.
L'angolo inferiore sinistro rappresenta i coefficienti più insignificanti dell'espansione dei coefficienti più significativi.
L'angolo in alto a destra rappresenta i coefficienti di espansione più significativi dei coefficienti più insignificanti.
L'angolo in basso a destra rappresenta i coefficienti più insignificanti dell'espansione dei coefficienti più insignificanti.
È chiaro che la significatività dei coefficienti diminuisce se ci si sposta diagonalmente dall'alto a sinistra verso il 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 le colonne), quindi per colonne: A=EA 0 = EXE T . Se calcoli attentamente, ottieni la formula:
Pertanto, se un vettore viene scomposto in sinusoidi, la matrice viene scomposta in funzioni della forma cos(ax)*cos(by). Ogni blocco 8x8 in JPEG è rappresentato come una somma di 64 funzioni nel formato: 
In Wikipedia e altre fonti, tali funzioni sono presentate in una forma più conveniente: 
Pertanto, i coefficienti (0, 7) o (7, 0) sono ugualmente utili.
Tuttavia, in realtà questa è una normale scomposizione unidimensionale in 64 basi 64-dimensionali. Tutto quanto sopra si applica non solo alla DCT, ma anche a qualsiasi scomposizione ortogonale. Procedendo per analogia, nel caso generale si ottiene una trasformazione ortogonale N-dimensionale.
Ed ecco una trasformazione 2D di un procione (DCT 256x256). Anche in questo caso con i valori azzerati. Numeri - il numero di coefficienti non azzerati tra tutti (sono stati mantenuti i valori più significativi, situati nell'area triangolare nell'angolo in alto a sinistra). 
Ricorda che il coefficiente (0, 0) si chiama DC, i restanti 63 si chiamano AC. Scelta della dimensione del blocco
Un amico chiede perché JPEG utilizza il partizionamento 8x8. Dalla risposta votata negativamente: 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.
Ad esempio, DCT funziona bene solo su funzioni periodiche e, se vai in grande, probabilmente otterrai un salto gigantesco 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 con le prime componenti.
Nella stessa pagina c'è una risposta dalle FAQ MPEG, con i principali argomenti contro i blocchi di grandi dimensioni:
Ti suggerisco di ricercarlo tu stesso. Iniziamo con Primo.
L'asse orizzontale mostra la quota dei primi coefficienti non azzerati. Verticale: deviazione standard dei pixel dall'originale. La deviazione massima possibile è considerata pari a uno. Naturalmente, una foto chiaramente non è sufficiente per un verdetto. Inoltre, non mi comporto in modo del tutto corretto, mi limito a resettare a zero. In un JPEG reale, a seconda della matrice di quantizzazione, vengono azzerati solo piccoli valori dei componenti ad alta frequenza. Pertanto, i seguenti esperimenti e conclusioni hanno lo scopo di far emergere i principi e i modelli.
Puoi confrontare la divisione in diversi blocchi con il 25% dei coefficienti a sinistra (da sinistra a destra, poi da destra a sinistra): 
Ciò significa che, ad esempio, il calcolo per una partizione 64x64 è due volte più complesso di quello per una partizione 8x8. 
Sebbene la distorsione dei blocchi 16x16 si estenda oltre quella dei blocchi 8x8, i caratteri sono più uniformi. Pertanto, solo i primi due argomenti mi hanno convinto. Ma in qualche modo mi piace di più la divisione 16x16.Quantizzazione
In questa fase abbiamo un gruppo di matrici 8x8 con coefficienti di trasformata coseno. È tempo di sbarazzarsi dei coefficienti insignificanti. Esiste una soluzione più elegante del semplice azzeramento degli ultimi coefficienti, come abbiamo fatto sopra. Non ci accontentiamo di questo metodo, poiché i valori non azzerati vengono memorizzati con eccessiva precisione, e tra gli sfortunati potrebbero essercene di abbastanza importanti. La soluzione è utilizzare una matrice di quantizzazione. Le perdite si verificano proprio in questa fase. Ogni coefficiente di Fourier viene diviso per il numero corrispondente nella matrice di quantizzazione. Diamo un'occhiata a un esempio. Prendiamo il primo blocco dal nostro procione ed eseguiamo la quantizzazione. La specifica JPEG fornisce una matrice standard: 
La matrice standard corrisponde al 50% di qualità in FastStone e IrfanView. Questa tabella è stata scelta in termini di equilibrio tra qualità e rapporto di compressione. Penso che il valore del coefficiente DC sia maggiore rispetto ai suoi vicini perché il DCT non è normalizzato e il primo valore è maggiore di quanto dovrebbe essere. I coefficienti ad alta frequenza vengono grossolani maggiormente a causa della loro minore importanza. Penso che tali matrici siano usate raramente ora, poiché il deterioramento della qualità è chiaramente evidente. Nessuno vieta di utilizzare la tua tabella (con valori da 1 a 255)
Durante la decodifica, avviene il processo inverso: 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 ripristinare 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: 
Quando ripristiniamo questo blocco, otterremo solo il valore medio più il gradiente verticale (a causa del valore conservato di -1). Ma per questo vengono memorizzati solo due valori: 7 e -1. La situazione non è migliore con gli altri blocchi, ecco l'immagine ripristinata: 
Oppure puoi guardare le matrici di quantizzazione di varie fotocamere.Codifica
Prima di proseguire, dobbiamo utilizzare esempi più semplici per capire come possiamo comprimere i valori risultanti.
Immagina una situazione del genere in cui il tuo amico ha dimenticato un pezzo di carta con un elenco a casa tua e ora ti chiede di dettarlo al telefono (non esistono altri metodi di comunicazione).
Elenco:
Come renderesti più semplice il tuo compito? Non hai un desiderio particolare di dettare dolorosamente tutte queste parole. Ma ce ne sono solo due e si ripetono. Pertanto, in qualche modo detti semplicemente le prime due parole e accetti che d'ora in poi chiamerai "d9rg3" la prima parola e "wfr43gt" la seconda. Poi basterà dettare: 1, 2, 2, 1, 1, 1, 2, 1. 
Codifica ABC.
Non è possibile associare 3 caratteri diversi (A, B, C) a 2 possibili valori di bit (0 e 1). E se è così, puoi usare 2 bit per simbolo. Per esempio:
La sequenza di bit associata ad un simbolo verrà chiamata codice. ABC sarà codificato in questo modo: 000110. 
Codifica AAAAAABC.
Usare 2 bit per carattere A sembra un po' uno spreco. E se provassi questo:
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 qualsiasi separatore tra i codici, penseremo a come aggirare questo ostacolo in modo diverso. Quindi il fallimento è dovuto al fatto che il codice di C inizia con il codice di A. Ma siamo determinati a codificare A con un bit, anche se B e C ne hanno due ciascuno. In base a questo desiderio diamo ad A il codice 0. Quindi i codici B e C non possono iniziare con 0. Ma possono iniziare con 1: 
La sequenza è codificata così: 0000001011. Prova a decodificarla mentalmente. Puoi farlo solo in un modo.
Abbiamo sviluppato due requisiti di codifica:
Ovviamente l'ordine dei caratteri non è importante, a noi interessa solo la frequenza con cui si presentano. Pertanto ad ogni simbolo è associato un numero chiamato peso. Il peso di un simbolo può essere un valore relativo, che riflette la proporzione della sua occorrenza, o un valore assoluto, pari al numero di caratteri. La cosa principale è che i pesi siano proporzionali alla presenza dei simboli.
Consideriamo il caso generale di 4 simboli con qualsiasi peso.
Senza perdita di generalità, poniamo pa ≥ pb ≥ pc ≥ pd. Esistono solo due opzioni fondamentalmente diverse nella lunghezza del codice: 
Quale è preferibile? Per fare ciò, è necessario calcolare la lunghezza risultante dei messaggi codificati:
W1 = 2*pa + 2*pb + 2*pc + 2*pd
W2 = pa + 2*pb + 3*pc + 3*pd
Se W1 è inferiore a W2 (W1-W2<0), то лучше использовать первый вариант:
W1-W2 = pa - (pc+pd)< 0 =>papà< pc+pd.
Se C e D insieme si presentano più spesso di altri, il loro vertice comune riceve il codice a un bit più breve. Altrimenti un bit va al carattere A. Ciò significa che l'unione dei caratteri si comporta come un carattere indipendente e ha un peso pari alla somma dei caratteri in ingresso.
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.
Consideriamolo in un caso semplice (può essere facilmente rappresentato come un albero). Quindi, dobbiamo codificare caratteri da 2 s con pesi uguali (1/2 s). A causa dell'uguaglianza dei pesi, le lunghezze dei codici saranno le stesse. Ogni carattere richiederà s bit. Ciò significa che se il peso di un simbolo è 1/2 s, allora la sua lunghezza è s. Se sostituiamo il peso con p, otteniamo la lunghezza del codice s=-log 2 p . Ciò significa che se un carattere ricorre il doppio della frequenza di un altro, la lunghezza del suo codice sarà più lunga di un bit. Tuttavia, questa conclusione è facile da trarre se si ricorda che l'aggiunta di un bit consente di raddoppiare il numero di opzioni possibili.
E ancora un'osservazione: i due simboli con il peso più piccolo hanno sempre la lunghezza del codice più grande ma uguale. Inoltre, i loro pezzi, tranne l'ultimo, sono gli stessi. Se ciò non fosse vero, almeno un codice potrebbe essere abbreviato di 1 bit senza interrompere il prefisso. Ciò significa che i due simboli con il peso più piccolo nell'albero del codice hanno un genitore comune a un livello superiore. Puoi vederlo negli esempi C e D sopra.
Proviamo a risolvere il seguente esempio, sulla base delle conclusioni ottenute nell'esempio precedente.
I passaggi vengono ripetuti finché rimane un solo gruppo. All'interno di ciascun gruppo, a un carattere (o sottogruppo) viene assegnato il bit 0 e a un altro carattere il 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). Sulla destra c'è il peso del simbolo (o del gruppo). 
Codifichiamo i coefficienti
Torniamo indietro. 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 coefficiente, ovviamente senza successo. Costruiamo un istogramma di tutti i valori ottenuti (ovvero la dipendenza del numero di coefficienti dal loro valore): 
Nota: la scala è logaritmica! Potete spiegare il motivo della comparsa di un cluster di valori superiori a 200? Questi sono coefficienti DC. Poiché sono molto diversi dagli altri, non sorprende che siano codificati separatamente. Ecco solo DC: 
Si noti che la forma del grafico ricorda i grafici dei primi esperimenti di accoppiamento e triplicazione dei pixel.
In generale, i valori del coefficiente DC possono variare da 0 a 2047 (più precisamente da -1024 a 1023, poiché JPEG sottrae 128 da tutti i valori originali, il che corrisponde a sottrarre 1024 da DC) e sono distribuiti abbastanza uniformemente con piccoli picchi. Quindi la codifica di Huffman non sarà di grande aiuto qui. E immagina quanto sarà grande l'albero del codice! E durante la decodifica dovrai cercare significati in esso. È molto caro. Pensiamo ulteriormente.
Il coefficiente DC è il valore medio di un blocco 8x8. Immaginiamo una transizione sfumata (anche se non ideale), 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à ancora una volta un albero troppo grande). I valori piccoli (in valore assoluto) sono comuni, i valori grandi sono rari. E poiché i valori piccoli occupano pochi bit (se vengono rimossi gli zeri iniziali), una delle regole di compressione è ben seguita: ai simboli con pesi grandi vengono assegnati codici brevi (e viceversa). Attualmente siamo limitati dal mancato rispetto di un'altra regola: l'impossibilità di decodifica univoca. In generale, questo problema può essere risolto nei seguenti modi: preoccuparsi del codice delimitatore, indicare la lunghezza del codice, utilizzare codici prefisso (li conosci già - questo è il caso in cui nessun codice inizia con un altro). Andiamo con la seconda opzione semplice, cioè ogni coefficiente (più precisamente, la differenza tra quelli vicini) verrà scritto così: (lunghezza)(valore), secondo questo segno: 
Cioè, i valori positivi sono codificati direttamente dalla loro rappresentazione binaria, mentre 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 Huffman. 
Sono presenti più valori con lunghezze 4 e 6, quindi hanno ottenuto i codici più brevi (00 e 01).
Potrebbe sorgere la domanda: perché nell'esempio il valore 9 ha il codice 1111110 e non 1111111? Dopotutto, puoi tranquillamente aumentare il "9" a un livello più alto, accanto allo "0"? Il fatto è che in JPEG non è possibile utilizzare un codice composto solo da uno: tale 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 la loro lunghezza sarà la stessa. Utilizzando l'algoritmo di Huffman, si ottengono le lunghezze dei codici e si generano i codici stessi (l'algoritmo è semplice: inizia con codici brevi e aggiungili uno per uno all'albero il più a sinistra possibile, preservando la proprietà del prefisso ). 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.
[Codice Huffman per la lunghezza della differenza CC (in bit)]
dove DC diff = corrente DC - DC precedente
Poiché il grafico è molto simile al grafico delle differenze CC, il principio è lo stesso: [codice Huffman per la lunghezza CA (in bit)]. Ma non proprio! Poiché la scala sul grafico è logaritmica, non si nota immediatamente che ci sono circa 10 volte più valori zero rispetto ai valori 2, i successivi più frequenti. Questo è comprensibile: non tutti sono sopravvissuti alla quantizzazione. Torniamo alla matrice dei valori ottenuti in fase di quantizzazione (utilizzando la matrice di quantizzazione FastStone, 90%). 
Poiché ci sono molti gruppi di zeri consecutivi, nasce l'idea di scrivere solo il numero di zeri nel gruppo. Questo algoritmo di compressione è chiamato RLE (codifica Run-length). Resta da scoprire la direzione della tangenziale "consecutiva": 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ù si avvicinano all'angolo in basso a destra, più sono gli zeri. 
Pertanto, JPEG utilizza un ordine chiamato "Zig-zag", mostrato nella figura a sinistra. Questo metodo distingue bene i gruppi di zeri. Nella foto a destra c'è un metodo di bypass alternativo, non legato al JPEG, ma con un nome interessante (prova). Può essere utilizzato in MPEG per la compressione video interlacciata. La scelta dell'algoritmo di attraversamento non influisce sulla qualità dell'immagine, ma può aumentare il numero di gruppi di zeri codificati, che in definitiva possono influire sulla dimensione del file.
Modifichiamo la nostra voce. Per ogni coefficiente AC diverso da zero:
[Numero di zeri prima di AC] [Codice Huffman per la lunghezza AC (in bit)]
Penso che si capisca subito che anche il numero di zeri è perfettamente codificato da Huffman! Questa è una risposta molto vicina e buona. Ma può essere leggermente ottimizzato. Immagina di avere un coefficiente AC, davanti al quale c'erano 7 zeri (ovviamente, se scritti 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. Ciò significa che il numero di zeri davanti ad AC e la lunghezza di AC sono quantità dipendenti. Pertanto lo scriviamo così:
[Codice Huffman per (Numero di zeri prima di AC, lunghezza di AC (in bit)]
L'algoritmo di codifica rimane lo stesso: quelle coppie (numero di zeri prima di AC, lunghezza di AC) che si verificano frequentemente riceveranno codici brevi e viceversa. 
La lunga “dorsale montuosa” conferma la nostra ipotesi.
Tale coppia occupa 1 byte: 4 bit per il numero di zeri e 4 bit per la lunghezza di AC. 4 bit sono valori da 0 a 15. Per la lunghezza di AC questo è 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 coefficiente diverso da zero. Poiché ci sono sempre molti zeri verso la fine del blocco, viene utilizzata la coppia (0,0) dopo l'ultimo coefficiente diverso da zero. Se viene riscontrato durante la decodifica, i valori rimanenti sono 0.
[Codice Huffman per la lunghezza del differenziale DC]
[Codice Huffman per (numero di zeri prima di AC 1, lunghezza di AC 1]
…
[Codice Huffman per (numero di zeri prima di AC n, lunghezza di AC n]
Dove AC i sono coefficienti AC diversi da zero.Immagine a colori
Il modo in cui viene presentata un'immagine a colori dipende da quella selezionata modello di colore. Una soluzione semplice è utilizzare RGB e codificare separatamente ciascun canale di colore dell'immagine. Quindi la codifica non sarà diversa dalla codifica di un'immagine grigia, solo 3 volte più lavoro. Ma la compressione dell'immagine può essere aumentata se ricordiamo che l'occhio è più sensibile ai cambiamenti di luminosità rispetto ai colori. Ciò significa che il colore può essere immagazzinato con perdite maggiori rispetto alla luminosità. RGB non ha un canale di luminosità separato. Dipende dalla somma dei valori di ciascun canale. Pertanto, il cubo RGB (questa è una rappresentazione di tutti i valori possibili) viene semplicemente "posizionato" sulla diagonale: più è alto, più è luminoso. Ma non si fermano qui: il cubo viene leggermente premuto dai lati e risulta più simile a un parallelepipedo, ma questo solo per tenere conto delle caratteristiche dell'occhio. Ad esempio, è più sensibile al verde che al blu. Ecco come è apparso il modello YCbCr. 
(Immagine da Intel.com)
Y è la componente di luminanza, Cb e Cr sono le componenti della differenza di colore blu e rosso. Pertanto, se si desidera comprimere maggiormente l'immagine, RGB viene convertito in YCbCr e i canali Cb e Cr vengono assottigliati. Cioè, sono divisi in piccoli blocchi, ad esempio 2x2, 4x2, 1x2, e viene calcolata la media di tutti i valori di un blocco. O, in altre parole, riducono la dimensione dell'immagine di questo canale di 2 o 4 volte in verticale e/o in orizzontale. 
Ogni blocco 8x8 è codificato (DCT + Huffman) e le sequenze codificate sono scritte in questo ordine:
È curioso che le specifiche JPEG non limitino la scelta del modello, ovvero l'implementazione del codificatore può dividere arbitrariamente l'immagine in componenti di colore (canali) e ciascuno verrà salvato separatamente. Sono a conoscenza dell'uso della scala di grigi (1 canale), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). I primi tre sono supportati quasi da tutti, ma ci sono problemi con gli ultimi a 4 canali. FastStone, GIMP li supportano correttamente, e i programmi standard di Windows, paint.net estraggono correttamente tutte le informazioni, ma poi buttano via il 4° canale del nero, quindi (Antelle ha detto che non lo buttano via, leggete i suoi commenti) mostrano un colore più chiaro Immagine. A sinistra c'è il classico YCbCr JPEG, a destra c'è CMYK JPEG: 
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 browser diversi. E un'altra cosa
In poche parole sulle funzionalità aggiuntive. Modalità progressiva
Scomponiamo le tabelle risultanti dei coefficienti DCT 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)). Per prima cosa codifichiamo tutti i primi termini (come abbiamo già imparato: Huffman e zigzag traversal), poi il secondo, ecc. Questo trucco è utile quando Internet è lento, poiché prima vengono caricati solo i coefficienti DC, che servono per costruire un'immagine approssimativa con 8x8 “pixel”. Quindi arrotondare i coefficienti AC per affinare la figura. Poi correzioni grossolane, poi correzioni più precise. E così via. I coefficienti vengono 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 Huffman. Modalità senza perdite
Compressione senza perdite. Niente DCT. Viene utilizzata la previsione del 4° punto basata su 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 viene codificato come al solito, quindi viene codificata solo la differenza (raffinazione dell'immagine) tra gli strati (finta per essere una wavelet Haar). Per la codifica viene utilizzato DCT o Lossless. Secondo me viene usato un po’ meno spesso che mai. Codifica aritmetica
L'algoritmo di Huffman produce codici ottimali in base al peso dei caratteri, ma questo è vero solo per una mappatura fissa da carattere a codice. L'aritmetica non ha un legame così rigido, che consente l'uso di codici come se avessero un numero frazionario di bit. Afferma di ridurre le dimensioni dei file in media del 10% rispetto a Huffman. Non diffuso a causa di problemi di brevetto, non supportato da tutti.
vanwin ha suggerito di indicare il software utilizzato. Ho il piacere di annunciare che tutto è disponibile e gratuito:
.
