Trasformata di quantizzazione media successiva ottimizzata

L'algoritmo Successive Mean Quantization Transform (SMQT) è una trasformazione non lineare che rivela l'organizzazione o la struttura dei dati e rimuove proprietà come gain e bias. In un articolo intitolato The Successive Mean Quantization Transform, SMQT è "applicato nell'elaborazione del parlato e nell'elaborazione delle immagini". L'algoritmo applicato alle immagini "può essere visto come una messa a fuoco progressiva sui dettagli di un'immagine".

Secondo un altro documento intitolato Operatori di mappatura dei toni basati su SMQT per immagini ad alta gamma dinamica, produrrà un'"immagine con dettagli migliorati". Il documento descrive due tecniche per applicare questa trasformazione a un'immagine.

1. Applica SMQT sulla luminanza di ciascun pixel: descrive la formula per ottenere la luminanza dall'RGB di ciascun pixel.

2. Applicare SMQT su ciascun canale di RGB separatamente - per i canali R, G e B individualmente.

L'immagine seguente mostra il risultato delle due tecniche:

Applicando la seconda tecnica a un'immagine del Bruin Theatre di notte, possiamo vedere come l'algoritmo ingrandisce progressivamente i dettagli dell'immagine e rivela dettagli originariamente nascosti dall'oscurità:

In questo articolo, daremo un'occhiata più da vicino a come funziona questo algoritmo ed esploreremo una semplice ottimizzazione che consente all'algoritmo di essere molto più performante nelle applicazioni pratiche di elaborazione delle immagini.

L'algoritmo SMQT

Nel documento originale, l'algoritmo è descritto in modo astratto. Per comprendere meglio SMQT, analizzeremo alcuni semplici esempi.

Supponiamo di avere il seguente vettore (puoi pensarlo come un array):

Nel caso di un'immagine a colori, possiamo pensarla come tre vettori separati, ognuno dei quali rappresenta un particolare canale di colore (RGB), e ogni elemento del vettore rappresenta l'intensità del pixel corrispondente.

I passaggi coinvolti nell'applicazione dell'algoritmo SMQT sono:

1. Calcola la media del vettore, che in questo caso è 29,58.

2. Dividi il vettore in due, lasciando i numeri minori o uguali a 29,58 nella metà sinistra e i numeri maggiori nella metà destra:

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   La seconda riga è il codice che creeremo per ogni valore. I valori inferiori o uguali a 29,58 ottengono uno 0 nel suo codice e i numeri maggiori di 29,58 ottengono un 1 (questo è binario).

3. Ora entrambi i vettori risultanti vengono divisi individualmente, in modo ricorsivo, seguendo la stessa regola. Nel nostro esempio la media del primo vettore è (15 + 4 + 0 + 5 + 18) / 5 = 8.4, e la media del secondo vettore è (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48,7. Ciascuno di questi due vettori viene ulteriormente suddiviso in altri due vettori e a ciascuno viene aggiunto un secondo bit di codice a seconda del suo confronto con la media. Questo è il risultato:

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   Si noti che è stato nuovamente aggiunto uno 0 per i numeri inferiori o uguali alla media (per ciascun vettore) e un 1 per i numeri maggiori della media.

4. Questo algoritmo viene ripetuto ricorsivamente:

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10000	10010	10100	11000	11100	11101	11110

   A questo punto ogni vettore ha un solo elemento. Quindi ad ogni passo successivo verrà aggiunto uno 0, poiché il numero sarà sempre uguale a se stesso (la condizione per uno 0 è che il numero deve essere minore o uguale alla media, che è essa stessa).

Finora abbiamo un livello di quantizzazione di L=5. Se dovessimo usare L=8, dobbiamo aggiungere tre 0 a ciascun codice. Il risultato della conversione di ogni codice da binario a intero (per L=8) sarebbe:

Il vettore finale è ordinato in ordine crescente. Per ottenere il vettore di output, dobbiamo sostituire il valore originale del vettore di input con il suo codice.

Si noti che nel vettore risultante:

• Il guadagno è stato rimosso. Quello originale aveva un guadagno basso, con la sua gamma che andava da 0 a 64. Ora il suo guadagno va da 0 a 240, che è quasi l'intera gamma di 8 bit. Si dice che il guadagno viene rimosso perché non importa se moltiplichiamo tutti gli elementi del vettore originale per un numero, come 2, o se dividiamo tutto per 2, il vettore di output sarebbe più o meno lo stesso. Il suo intervallo sarebbe circa l'intero intervallo del vettore di destinazione (8 bit per L=8). Se moltiplichiamo il vettore di input per due, il vettore di output sarà effettivamente lo stesso, perché in ogni passaggio gli stessi numeri che erano al di sotto o al di sopra della media continueranno a essere al di sotto o al di sopra di esso e aggiungeremo gli stessi 0 o 1 all'uscita. Solo se lo dividiamo il risultato sarebbe più o meno lo stesso, e non esattamente lo stesso, perché i numeri dispari come 15 dovranno essere arrotondati e quindi i calcoli possono variare. Siamo passati da un'immagine scura a un'immagine con i suoi pixel che vanno dai colori scuri (0) ai colori più chiari (240), utilizzando l'intera gamma.
• La distorsione viene rimossa, anche se non possiamo osservarla del tutto in questo esempio. Questo perché non abbiamo una distorsione poiché il nostro valore più basso è 0. Se avessimo effettivamente una distorsione, sarebbe stata rimossa. Se prendiamo qualsiasi numero "K" e lo aggiungiamo a ciascun elemento del vettore di input, il calcolo dei numeri sopra e sotto la media in ogni passaggio non varierà. L'output sarà sempre lo stesso. Ciò renderebbe anche immagini troppo luminose per diventare immagini che vanno dai colori scuri a quelli chiari.
• Abbiamo un'immagine con dettagli migliorati. Nota come per ogni passaggio ricorsivo che facciamo stiamo effettivamente ingrandendo i dettagli e costruendo l'output rivelando quei dettagli il più possibile. E poiché applicheremo questa tecnica a ciascun canale RGB, riveleremo quanti più dettagli possibili, pur perdendo informazioni sui toni originali di ciascun colore.

Data un'immagine come un vettore di pixel RGB, con ogni punto a 8 bit per R, 8 per G e 8 per B; possiamo estrarre tre vettori da esso, uno per ogni colore, e applicare l'algoritmo a ciascun vettore. Quindi formiamo nuovamente il vettore RGB da quei tre vettori di output e abbiamo l'immagine elaborata SMQT, come fatto con quella del Bruin Theatre.

Complessità

L'algoritmo richiede che per ogni livello di quantizzazione (L), N elementi debbano essere ispezionati in un primo passaggio per trovare la media per ciascun vettore, e quindi in un secondo passaggio, ciascuno di quegli N elementi debba essere confrontato con la media corrispondente in per dividere ogni vettore a turno. Infine, N elementi devono essere sostituiti dai loro codici. Pertanto la complessità dell'algoritmo è O((L*2*N) + N) = O((2*L + 1)*N), che è O(L*N).

Il grafico estratto dalla carta è coerente con la complessità O(L*N). Più bassa è la L, più veloce sarà l'elaborazione in modo approssimativamente lineare (maggiore numero di fotogrammi al secondo). Per migliorare la velocità di elaborazione, il documento suggerisce di abbassare i valori di L: “selezionare un livello L inferiore può essere un modo diretto per ridurre la velocità di elaborazione ma con una qualità dell'immagine ridotta”.

Miglioramento

Qui troveremo un modo per migliorare la velocità senza ridurre la qualità dell'immagine. analizzeremo il processo di trasformazione e troveremo un algoritmo più veloce. Per avere una prospettiva più completa su questo, vediamo un esempio con numeri ripetuti:

I vettori non possono più essere divisi e gli zeri devono essere aggiunti fino ad arrivare alla L desiderata.

Per semplicità, supponiamo che l'input possa andare da 0 a 31, e l'output da 0 a 7 (L=3), come si vede nell'esempio.

Si noti che il calcolo della media del primo vettore (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 dà lo stesso risultato del calcolo della media dell'intero ultimo vettore, poiché è solo lo stesso vettore con gli elementi in un ordine diverso: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

Nella seconda fase dobbiamo calcolare ogni vettore in modo ricorsivo. Quindi calcoliamo la media degli input in grigio, che sono i primi 6 elementi ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8), e la media degli input vuoti, che sono gli ultimi 4 elementi ((25 + 31 + 31 + 25) / 4 = 28):

Si noti ancora che se utilizziamo l'ultimo vettore, quello che è completamente ordinato, i risultati sono gli stessi. Per i primi 6 elementi abbiamo: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8), e per gli ultimi 4 elementi: ((25 + 25 + 31 + 31) / 4 = 28) . Dal momento che è solo un'aggiunta, l'ordine delle addizioni non ha importanza.

Lo stesso vale per il passaggio successivo:

I calcoli sono gli stessi dell'ultimo vettore: ((7 + 1 + 1 + 7) / 4 = 4) sarà uguale a ((1 + 1 + 7 + 7) / 4 = 4).

E lo stesso vale per il resto dei vettori e dei passaggi.

Il calcolo della media è solo la somma dei valori degli elementi nell'intervallo, divisa per il numero degli elementi nell'intervallo. Ciò significa che possiamo precalcolare tutti quei valori ed evitare di ripetere questo calcolo L volte.

Vediamo i passaggi per applicare quello che chiameremo algoritmo FastSMQT al nostro esempio:

1. Crea una tabella con 32 colonne e 3 righe come puoi vedere di seguito. La prima riga della tabella rappresenta l'indice della tabella (da 0 a 31) e non è necessario includerla durante la codifica della tabella. Ma viene mostrato esplicitamente per rendere l'esempio più facile da seguire.

2. Iterare gli N elementi una volta contando la frequenza di ciascun valore. Nel nostro esempio, gli elementi 1, 7, 16, 25 e 31 hanno tutti una frequenza di 2. Tutti gli altri elementi hanno una frequenza di 0. Questo passaggio ha una complessità di O(N).

3. Ora che il vettore di frequenza è pieno, dobbiamo iterare quel vettore (il vettore delle frequenze, non il vettore di input). Non iteriamo più N elementi, ma R (R essendo nell'intervallo: 2^L), che in questo caso è 32 (da 0 a 31). Durante l'elaborazione dei pixel, N può essere molti milioni (megapixel), ma R è solitamente 256 (un vettore per ogni colore). Nel nostro esempio è 32. riempiremo contemporaneamente le due righe seguenti della tabella. La prima di queste righe (la seconda della tabella) avrà la somma delle frequenze finora. Il secondo (il terzo della tabella) avrà la somma del valore di tutti gli elementi apparsi fino a quel momento.

   Nel nostro esempio, quando arriviamo a 1, mettiamo un 2 nella seconda riga della tabella perché finora sono comparsi due 1. E mettiamo anche un 2 nella terza riga della tabella, perché 1 + 1 = 2. Continuiamo a scrivere quei due valori su ciascuna delle posizioni successive fino ad arrivare a 7. Poiché il numero 7 appare due volte, aggiungiamo 2 al accumulatore della seconda riga, perché ora sono comparsi 4 numeri (1, 1, 7, 7). E aggiungiamo 7 + 7 = 14 alla terza riga, risultando in 2 + 14 = 16, perché 1 + 1 + 7 + 7 = 16. Continuiamo con questo algoritmo finché non finiamo di iterare quegli elementi. La complessità di questo passaggio è O(2^L), che nel nostro caso è O(32), e quando si lavora con pixel RGB è O(256).

   io	0	1	2	...	6	7	8	...	15	16	17	...	24	25	26	...	30	31
   n	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   n-cumulativo	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   somma	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. Il passaggio successivo consiste nel rimuovere dalla tabella le colonne con elementi che hanno frequenza 0, e per vedere l'esempio più chiaro rimuoveremo anche la seconda riga poiché non è più rilevante, come vedrai.

   io	1	7	16	25	31
   n	2	4	6	8	10
   somma	2	16	48	98	160

5. Ricorda che potremmo usare l'ultimo vettore (completamente ordinato) per eseguire i calcoli per ogni passaggio e i risultati saranno sempre gli stessi. Si noti che qui, in questa tabella, abbiamo l'ultimo vettore con tutti i pre-calcoli già effettuati.

   Fondamentalmente dobbiamo eseguire l'algoritmo SMQT su questo piccolo vettore, ma a differenza di farlo sul vettore originale con cui abbiamo iniziato, questo sarà molto più semplice.

   Per prima cosa dobbiamo calcolare la media di tutti i campioni. Possiamo trovarlo facilmente con: sum[31] / n[31] = 160 / 10 = 16. Quindi dividiamo la tabella in due vettori e iniziamo a scrivere il codice binario per ciascuno:

   io	1	7	16	25	31
   n	2	4	6	8	10
   somma	2	16	48	98	160
   codice	0	0	0	1	1

   Ora dividiamo nuovamente ogni vettore. La media del primo vettore è: sum[16] / n[16] = 48 / 6 = 8. E la media del secondo vettore è: (sum[31] – sum[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   io	1	7	16	25	31
   n	2	4	6	8	10
   somma	2	16	48	98	160
   codice	00	00	01	10	11

   È rimasto solo un vettore da dividere. La media è: sum[7] / n[7] = 16 / 4 = 4.

   io	1	7	16	25	31
   n	2	4	6	8	10
   somma	2	16	48	98	160
   codice	000	001	010	100	110

   Come puoi vedere, il codice per ogni elemento è lo stesso se avessimo seguito l'algoritmo originale. E abbiamo eseguito l'SMQT su un vettore molto più piccolo di quello con N elementi e abbiamo anche precalcolato tutti i valori di cui abbiamo bisogno per trovare la media, quindi è semplice e veloce calcolare il vettore risultante.

   La complessità di questo passaggio è O(L*(2^L)), che per un L=8, e nelle esigenze pratiche di elaborazione delle immagini, è O(8*(256)) = O(2048) = costante.

6. Il passaggio finale consiste nell'iterare N elementi ancora una volta sostituendo l'elemento con il suo codice per ogni elemento: element[i] = code[i]. La complessità è O(N). La complessità di FastSMQT è O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

Parallelismo

Entrambi gli algoritmi possono essere parallelizzati, sebbene sia più efficiente eseguire un algoritmo per core se è necessario trasformare più vettori. Ad esempio, durante l'elaborazione delle immagini possiamo elaborare ciascun canale RGB in un core diverso invece di parallelizzare ciascuno di questi tre calcoli.

Per parallelizzare l'algoritmo SMQT, quando dividiamo un vettore in due, possiamo elaborare ciascun sottovettore in un nuovo core se è disponibile un core (in realtà un sottovettore nel core corrente e l'altro in un nuovo core). Questo può essere fatto in modo ricorsivo fino a raggiungere il numero totale di core disponibili. Le sostituzioni di valori con codici possono essere effettuate anche in parallelo per.

L'algoritmo FastSMQT può anche essere parallelizzato. Nella prima fase, il vettore di input deve essere diviso nel numero di core disponibili (C). Un vettore di conteggio delle frequenze deve essere creato per ciascuna di queste parti e deve essere compilato in parallelo. Quindi aggiungiamo i valori di quei vettori in un vettore di frequenze risultante. Il passo successivo che può essere parallelizzato è l'ultimo, quando stiamo sostituendo i valori con i loro codici. Questo può essere fatto in parallelo per.

Confronto di complessità

La complessità totale dell'algoritmo SMQT originale è O((2*L + 1)*N), che è O(L*N).

La complessità di FastSMQT è O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

Data una L fissa, la complessità diventa solo O(N) per entrambi. Ma la costante che moltiplica N è molto più piccola per FastSMQT e, come vedremo, fa una grande differenza nel tempo di elaborazione.

Il grafico seguente confronta le prestazioni degli algoritmi SMQT e FastSMQT per L=8, come nel caso dell'elaborazione delle immagini. Il grafico mostra il tempo (in millisecondi) necessario per elaborare N elementi. Si noti che la complessità (con costanti) di SMQT per L=8 è O(17*N), mentre per FastSMQT è O(2*N + 2304).

Più grande è la N, più tempo impiega SMQT per elaborare l'immagine. Per FastSMQT, invece, la crescita è molto più lenta.

Per valori di N ancora maggiori, la differenza di prestazioni è molto più evidente:

Qui SMQT impiega più secondi per elaborare determinate immagini, mentre FastSMQT si trova ancora all'interno della zona "pochi millisecondi".

Anche con più core (due, in questo caso), FastSMQT è chiaramente superiore al solo SMQT:

FastSMQT non dipende da L. SMQT, d'altra parte, dipende linearmente dal valore di L. Ad esempio, con N = 67108864, il runtime di SMQT aumenta all'aumentare del valore di L, mentre FastSMQT no:

Conclusione

Non tutte le tecniche di ottimizzazione sono applicabili a tutti gli algoritmi e la chiave per migliorare le prestazioni di un algoritmo è spesso nascosta in alcune informazioni su come funziona l'algoritmo. Questo algoritmo FastSMQT sfrutta le possibilità di precalcolo dei valori e la natura dei calcoli medi. Di conseguenza consente un'elaborazione più rapida rispetto all'SMQT originale. La velocità non è influenzata dall'incremento di L, anche se L non può essere molto maggiore del solito 8 perché l'utilizzo della memoria è 2^L, che per 8 è un accettabile 256 (numero di colonne nella nostra tabella delle frequenze), ma il guadagno di prestazioni ha evidenti vantaggi pratici.

Questo miglioramento della velocità ha consentito a MiddleMatter di implementare l'algoritmo in un'applicazione iOS (e un'applicazione Android) che migliora le immagini e i video acquisiti in condizioni di scarsa illuminazione. Con questo miglioramento, è stato possibile eseguire l'elaborazione video nell'applicazione, che altrimenti sarebbe stata troppo lenta per i dispositivi iOS.

Il codice C++ per gli algoritmi SMQT e FastSMQT è disponibile su GitHub.