Transformarea de cuantizare medie succesivă optimizată

Algoritmul SMQT (Succesive Mean Quantization Transform) este o transformare neliniară care dezvăluie organizarea sau structura datelor și elimină proprietăți precum câștigul și părtinirea. Într-o lucrare intitulată The Successive Mean Quantization Transform, SMQT este „aplicat în procesarea vorbirii și procesarea imaginilor”. Algoritmul atunci când este aplicat imaginilor „poate fi văzut ca o focalizare progresivă asupra detaliilor dintr-o imagine”.

Potrivit unei alte lucrări intitulate Operatori de cartografiere a tonurilor bazate pe SMQT pentru imagini cu gamă dinamică înaltă, va produce o „imagine cu detalii îmbunătățite”. Lucrarea descrie două tehnici de aplicare a acestei transformări la o imagine.

1. Aplicați SMQT pe luminanța fiecărui pixel - descrie formula pentru a obține luminanța din RGB-ul fiecărui pixel.

2. Aplicați SMQT pe fiecare canal de RGB separat - pentru canalele R, G și B individual.

Următoarea imagine arată rezultatul celor două tehnici:

Aplicând cea de-a doua tehnică la o imagine a Teatrului Bruin pe timp de noapte, putem vedea cum algoritmul mărește progresiv detaliile imaginii și dezvăluie detalii care sunt ascunse inițial de întuneric:

În acest articol, vom arunca o privire mai atentă asupra modului în care funcționează acest algoritm și vom explora o optimizare simplă care permite algoritmului să fie mult mai performant în aplicațiile practice de procesare a imaginilor.

Algoritmul SMQT

În lucrarea originală, algoritmul este descris într-o manieră abstractă. Pentru a înțelege mai bine SMQT, vom parcurge câteva exemple simple.

Să presupunem că avem următorul vector (vă puteți gândi la el ca la o matrice):

În cazul unei imagini color, o putem gândi ca fiind trei vectori separați, fiecare reprezentând un anumit canal de culoare (RGB) și fiecare element al vectorului reprezentând intensitatea pixelului corespunzător.

Pașii implicați în aplicarea algoritmului SMQT sunt:

1. Calculați media vectorului, care în acest caz este 29,58.

2. Împărțiți vectorul în două, lăsând numerele care sunt mai mici sau egale cu 29,58 în jumătatea stângă și numerele care sunt mai mari în jumătatea dreaptă:

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

   Al doilea rând este codul pe care îl vom crea pentru fiecare valoare. Valorile mai mici sau egale cu 29,58 primesc un 0 în codul său, iar numerele mai mari de 29,58 primesc un 1 (acesta este binar).

3. Acum ambii vectori rezultați sunt împărțiți individual, într-un mod recursiv, urmând aceeași regulă. În exemplul nostru, media primului vector este (15 + 4 + 0 + 5 + 18) / 5 = 8,4, iar media celui de-al doilea vector este (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48,7. Fiecare dintre acești doi vectori este împărțit în continuare în încă doi vectori și un al doilea bit de cod este adăugat fiecăruia în funcție de comparația cu media. Acesta este rezultatul:

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

   Rețineți că un 0 a fost adăugat din nou pentru numerele mai mici sau egale cu media (pentru fiecare vector) și un 1 pentru numerele mai mari decât media.

4. Acest algoritm se repetă recursiv:

   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

   În acest moment, fiecare vector are un singur element. Deci pentru fiecare pas succesiv se va adăuga un 0, deoarece numărul va fi întotdeauna egal cu el însuși (condiția pentru un 0 este ca numărul să fie mai mic sau egal cu media, care este el însuși).

Până acum avem un nivel de cuantizare de L=5. Dacă urma să folosim L=8, trebuie să adăugăm trei 0-uri la fiecare cod. Rezultatul conversiei fiecărui cod din binar în întreg (pentru L=8) ar fi:

Vectorul final este sortat în ordine crescătoare. Pentru a obține vectorul de ieșire, trebuie să înlocuim valoarea inițială a vectorului de intrare cu codul său.

Observați că în vectorul rezultat:

• Câștigul a fost eliminat. Cel inițial a avut un câștig scăzut, cu intervalul său mergând de la 0 la 64. Acum câștigul său merge de la 0 la 240, care este aproape întregul interval de 8 biți. Se spune că câștigul este eliminat pentru că nu contează dacă înmulțim toate elementele vectorului original cu un număr, cum ar fi 2, sau dacă le împărțim pe toate la 2, vectorul de ieșire ar fi cam același. Intervalul său ar fi aproximativ întregul interval al vectorului de destinație (8 biți pentru L=8). Dacă înmulțim vectorul de intrare cu doi, vectorul de ieșire va fi de fapt același, deoarece în fiecare pas aceleași numere care au fost sub sau deasupra mediei vor continua să fie sub sau deasupra acesteia și vom adăuga aceleași 0 sau 1. la ieșire. Doar dacă o împărțim, rezultatul ar fi aproximativ același, și nu exact același, deoarece numerele impare precum 15 vor trebui rotunjite și calculele pot varia atunci. Am trecut de la o imagine întunecată la o imagine cu pixelii săi variind de la culori întunecate (0) la culori mai deschise (240), folosind întreaga gamă.
• Prejudecata este eliminată, deși nu o putem observa în acest exemplu. Acest lucru se datorează faptului că nu avem o prejudecată, deoarece valoarea noastră cea mai mică este 0. Dacă am avut de fapt o prejudecată, aceasta ar fi fost eliminată. Dacă luăm orice număr „K” și îl adăugăm la fiecare element al vectorului de intrare, calculul numerelor de deasupra și de sub medie în fiecare pas nu va varia. Ieșirea va fi în continuare aceeași. Acest lucru ar face, de asemenea, imagini prea luminoase pentru a deveni imagini care variază de la culori întunecate la culori deschise.
• Avem o imagine cu detalii îmbunătățite. Observați cum pentru fiecare pas recursiv pe care îl facem, de fapt, mărim detaliile și construim rezultatul dezvăluind acele detalii cât mai mult posibil. Și întrucât vom aplica această tehnică fiecărui canal RGB, vom dezvălui cât mai multe detalii, deși pierzând informații despre tonurile originale ale fiecărei culori.

Dată o imagine ca un vector de pixeli RGB, fiecare punct fiind de 8 biți pentru R, 8 pentru G și 8 pentru B; putem extrage trei vectori din el, câte unul pentru fiecare culoare și să aplicăm algoritmul fiecărui vector. Apoi formăm din nou vectorul RGB din cei trei vectori de ieșire și avem imaginea procesată SMQT, așa cum se face cu cea a Teatrului Bruin.

Complexitate

Algoritmul cere ca pentru fiecare nivel de cuantizare (L), N elemente să fie inspectate într-o primă trecere pentru a găsi media pentru fiecare vector, iar apoi, într-o a doua trecere, fiecare dintre aceste N elemente trebuie comparat cu media corespunzătoare din pentru a împărți fiecare vector pe rând. În cele din urmă, N elemente trebuie înlocuite cu codurile lor. Prin urmare, complexitatea algoritmului este O((L*2*N) + N) = O((2*L + 1)*N), care este O(L*N).

Graficul extras din hârtie este în concordanță cu complexitatea O(L*N). Cu cât L este mai mic, cu atât procesarea este mai rapidă într-un mod aproximativ liniar (număr mai mare de cadre pe secundă). Pentru a îmbunătăți viteza de procesare, lucrarea sugerează scăderea valorilor lui L: „selectarea unui nivel L mai mic poate fi o modalitate directă de a reduce viteza de procesare, dar cu o calitate redusă a imaginii”.

Îmbunătăţire

Aici vom găsi o modalitate de a îmbunătăți viteza fără a reduce calitatea imaginii. vom analiza procesul de transformare și vom găsi un algoritm mai rapid. Pentru a obține o perspectivă mai completă asupra acestui lucru, să vedem un exemplu cu numere repetate:

Vectorii nu mai pot fi împărțiți și trebuie adăugate zerouri până când ajungem la L dorit.

De dragul simplității, să presupunem că intrarea poate merge de la 0 la 31, iar ieșirea de la 0 la 7 (L=3), așa cum se poate vedea în exemplu.

Rețineți că calcularea mediei primului vector (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 dă același rezultat ca și calcularea mediei întregului vector, deoarece este exact același vector cu elementele într-o ordine diferită: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

În a doua etapă trebuie să calculăm fiecare vector recursiv. Deci calculăm media intrărilor gri, care sunt primele 6 elemente ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8), și media intrărilor necompletate, care sunt ultimele 4 elemente ((25 + 31 + 31 + 25) / 4 = 28):

Rețineți că dacă folosim ultimul vector, cel care este complet ordonat, rezultatele sunt aceleași. Pentru primele 6 elemente avem: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8), iar pentru ultimele 4 elemente: ((25 + 25 + 31 + 31) / 4 = 28) . Deoarece este doar o adăugare, ordinea sumelor nu contează.

Același lucru este valabil și pentru următorul pas:

Calculele sunt aceleași ca la ultimul vector: ((7 + 1 + 1 + 7) / 4 = 4) va fi egal cu ((1 + 1 + 7 + 7) / 4 = 4).

Și același lucru se va aplica și pentru restul vectorilor și pașilor.

Calculul mediei este doar suma valorilor elementelor din interval, împărțită la numărul de elemente din interval. Aceasta înseamnă că putem precalcula toate acele valori și putem evita repetarea acestui calcul de L ori.

Să vedem pașii pentru a aplica ceea ce vom numi algoritmul FastSMQT exemplului nostru:

1. Creați un tabel cu 32 de coloane și 3 rânduri, așa cum puteți vedea mai jos. Primul rând din tabel reprezintă indexul tabelului (de la 0 la 31) și nu este necesar să fie inclus la codificarea tabelului. Dar este arătat în mod explicit pentru a face exemplul mai ușor de urmat.

2. Repetați cele N elemente o dată numărând frecvența fiecărei valori. În exemplul nostru, elementele 1, 7, 16, 25 și 31 au toate o frecvență de 2. Toate celelalte elemente au o frecvență de 0. Acest pas are o complexitate de O(N).

3. Acum că vectorul de frecvență este umplut, trebuie să repetăm ​​acel vector (vectorul de frecvențe, nu vectorul de intrare). Nu mai repetăm ​​N elemente, ci R (R fiind în intervalul: 2^L), care în acest caz este 32 (0 la 31). La procesarea pixelilor, N poate fi de multe milioane (megapixeli), dar R este de obicei 256 (un vector pentru fiecare culoare). În exemplul nostru este 32. vom completa următoarele două rânduri ale tabelului în același timp. Primul dintre aceste rânduri (al doilea din tabel) va avea suma frecvențelor de până acum. Al doilea (al treilea din tabel) va avea suma valorii tuturor elementelor apărute până acum.

   În exemplul nostru, când ajungem la 1, punem un 2 în al doilea rând al tabelului pentru că până acum au apărut doi 1. Și punem și un 2 în al treilea rând al tabelului, pentru că 1 + 1 = 2. Continuăm să scriem acele două valori pe fiecare dintre pozițiile următoare până ajungem la 7. Deoarece numărul 7 apare de două ori, adăugăm 2 la acumulator al al doilea rând, pentru că acum au apărut 4 numere până acum (1, 1, 7, 7). Și adăugăm 7 + 7 = 14 la al treilea rând, rezultând 2 + 14 = 16, deoarece 1 + 1 + 7 + 7 = 16. Continuăm cu acest algoritm până când terminăm de iterarea acelor elemente. Complexitatea acestui pas este O(2^L), care în cazul nostru este O(32), iar când lucrați cu pixeli RGB este O(256).

   i	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-cumulativ	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   sumă	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. Următorul pas este să eliminați din tabel coloanele cu elemente care au frecvența 0, iar pentru a vedea exemplul mai clar vom elimina și al doilea rând deoarece nu mai este relevant, după cum veți vedea.

   i	1	7	16	25	31
   n	2	4	6	8	10
   sumă	2	16	48	98	160

5. Amintiți-vă că am putea folosi ultimul vector (complet ordonat) pentru a face calculele pentru fiecare pas și rezultatele vor fi în continuare aceleași. Rețineți că aici, în acest tabel, avem ultimul vector cu toate precalculele deja făcute.

   Practic, trebuie să facem algoritmul SMQT pe acest vector mic, dar spre deosebire de a-l face pe vectorul original cu care am început, acesta va fi mult mai ușor.

   Mai întâi trebuie să calculăm media tuturor probelor. Îl putem găsi cu ușurință prin: sum[31] / n[31] = 160 / 10 = 16. Deci împărțim tabelul în doi vectori și începem să scriem codul binar pentru fiecare:

   i	1	7	16	25	31
   n	2	4	6	8	10
   sumă	2	16	48	98	160
   cod	0	0	0	1	1

   Acum împărțim din nou fiecare vector. Media primului vector este: sum[16] / n[16] = 48 / 6 = 8. Iar media celui de-al doilea vector este: (sum[31] – sum[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   i	1	7	16	25	31
   n	2	4	6	8	10
   sumă	2	16	48	98	160
   cod	00	00	01	10	11

   Mai rămâne un singur vector de împărțit. Media este: suma[7] / n[7] = 16 / 4 = 4.

   i	1	7	16	25	31
   n	2	4	6	8	10
   sumă	2	16	48	98	160
   cod	000	001	010	100	110

   După cum puteți vedea, codul pentru fiecare element este același dacă am fi urmat algoritmul original. Și am făcut SMQT pe un vector mult mai mic decât cel cu N elemente și, de asemenea, am precalculat toate valorile de care avem nevoie pentru a găsi media, așa că este simplu și rapid să calculăm vectorul rezultat.

   Complexitatea acestui pas este O(L*(2^L)), care pentru un L=8, iar în nevoile practice de procesare a imaginii, este O(8*(256)) = O(2048) = constantă.

6. Pasul final este de a repeta N elemente încă o dată, înlocuind elementul cu codul său pentru fiecare element: element[i] = cod[i]. Complexitatea este O(N). Complexitatea FastSMQT este O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

Paralelism

Ambii algoritmi pot fi paralelizați, deși este mai eficient să rulați un algoritm per nucleu dacă trebuie transformați mai mulți vectori. De exemplu, atunci când procesăm imagini, putem procesa fiecare canal RGB într-un nucleu diferit, în loc să paralelizăm fiecare dintre aceste trei calcule.

Pentru a paraleliza algoritmul SMQT, atunci când împărțim un vector în două, putem procesa fiecare sub-vector într-un nucleu nou dacă este disponibil un nucleu (de fapt, un subvector în nucleul curent și celălalt într-un nucleu nou). Acest lucru se poate face recursiv până când ajungem la numărul total de nuclee disponibile. Înlocuirile valorilor cu coduri se pot face și în paralel pt.

Algoritmul FastSMQT poate fi, de asemenea, paralelizat. În primul pas, vectorul de intrare trebuie împărțit în numărul de nuclee disponibile (C). Trebuie creat un vector de numărare a frecvenței pentru fiecare dintre acele părți și completat în paralel. Apoi adăugăm valorile acelor vectori într-un vector de frecvențe rezultat. Următorul pas care poate fi paralelizat este ultimul, când înlocuim valorile cu codurile lor. Acest lucru se poate face în paralel pt.

Comparație de complexitate

Complexitatea totală a algoritmului SMQT original este O((2*L + 1)*N), care este O(L*N).

Complexitatea FastSMQT este O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

Având în vedere un L fix, complexitatea devine doar O(N) pentru ambele. Dar constanta care înmulțește N este mult mai mică pentru FastSMQT și face o mare diferență în timpul de procesare, după cum vom vedea.

Următorul grafic compară performanța ambelor algoritmi SMQT și FastSMQT pentru L=8, ceea ce este cazul procesării imaginilor. Graficul arată timpul (în milisecunde) necesar procesării N elemente. Rețineți că complexitatea (cu constante) SMQT pentru L=8 este O(17*N), în timp ce pentru FastSMQT este O(2*N + 2304).

Cu cât N este mai mare, cu atât este nevoie de mai mult timp pentru ca SMQT să proceseze imaginea. Pentru FastSMQT, pe de altă parte, creșterea este mult mai lentă.

Pentru valori și mai mari ale lui N, diferența de performanță este mult mai evidentă:

Aici SMQT durează până la mai multe secunde pentru a procesa anumite imagini, în timp ce FastSMQT se află încă în zona de „câteva milisecunde”.

Chiar și cu mai multe nuclee (două, în acest caz), FastSMQT este în mod clar superior doar SMQT:

FastSMQT nu este dependent de L. SMQT, pe de altă parte, este dependent liniar de valoarea lui L. De exemplu, cu N = 67108864, timpul de rulare al SMQT crește odată cu creșterea valorii lui L, în timp ce FastSMQT nu:

Concluzie

Nu toate tehnicile de optimizare sunt aplicabile pentru toți algoritmii, iar cheia îmbunătățirii performanței unui algoritm este adesea ascunsă într-o perspectivă asupra modului în care funcționează algoritmul. Acest algoritm FastSMQT profită de posibilitățile de precalculare a valorilor și de natura calculelor medii. Ca rezultat, permite o procesare mai rapidă decât SMQT original. Viteza nu este afectată de creșterea lui L, deși L nu poate fi mult mai mare decât 8 obișnuit, deoarece utilizarea memoriei este de 2^L, care pentru 8 este un 256 acceptabil (numărul de coloane din tabelul nostru de frecvență), dar câștigul de performanță are beneficii practice evidente.

Această îmbunătățire a vitezei a permis lui MiddleMatter să implementeze algoritmul într-o aplicație iOS (și o aplicație Android) care îmbunătățește imaginile și videoclipurile capturate în condiții de lumină scăzută. Cu această îmbunătățire, a fost posibil să se efectueze procesarea video în aplicație, care altfel ar fi prea lentă pentru dispozitivele iOS.

Codul C++ pentru algoritmii SMQT și FastSMQT este disponibil pe GitHub.