Zoptymalizowana sukcesywna transformacja średniej kwantyzacji

Algorytm sukcesywnej transformacji średniej kwantyzacji (SMQT) to nieliniowa transformacja, która ujawnia organizację lub strukturę danych i usuwa właściwości, takie jak wzmocnienie i obciążenie. W artykule zatytułowanym The Successive Mean Quantization Transform, SMQT jest „stosowany w przetwarzaniu mowy i przetwarzania obrazu”. Algorytm zastosowany do obrazów „może być postrzegany jako stopniowe skupianie się na szczegółach obrazu”.

Według innego artykułu zatytułowanego Operatory mapowania tonów oparte na SMQT dla obrazów o wysokim zakresie dynamicznym, uzyska „obraz o ulepszonych szczegółach”. Artykuł opisuje dwie techniki zastosowania tej transformacji do obrazu.

1. Zastosuj SMQT do luminancji każdego piksela - opisuje wzór na uzyskanie luminancji z RGB każdego piksela.

2. Zastosuj SMQT na każdym kanale RGB osobno - dla kanałów R, G i B osobno.

Poniższy rysunek przedstawia wynik dwóch technik:

Stosując drugą technikę na nocnym zdjęciu Bruin Theatre, możemy zobaczyć, jak algorytm stopniowo powiększa szczegóły obrazu i ujawnia szczegóły, które pierwotnie były ukryte przez ciemność:

W tym artykule przyjrzymy się bliżej, jak działa ten algorytm i zbadamy prostą optymalizację, która pozwala algorytmowi być znacznie bardziej wydajnym w praktycznych zastosowaniach do przetwarzania obrazu.

Algorytm SMQT

W oryginalnej pracy algorytm jest opisany w sposób abstrakcyjny. Aby lepiej zrozumieć SMQT, omówimy kilka prostych przykładów.

Załóżmy, że mamy następujący wektor (możesz o nim myśleć jak o tablicy):

W przypadku obrazu kolorowego możemy myśleć o nim jako o trzech oddzielnych wektorach, z których każdy reprezentuje określony kanał koloru (RGB), a każdy element wektora reprezentuje intensywność odpowiedniego piksela.

Kroki związane z zastosowaniem algorytmu SMQT to:

1. Oblicz średnią wektora, która w tym przypadku wynosi 29,58.

2. Podziel wektor na dwie części, pozostawiając liczby mniejsze lub równe 29,58 w lewej połowie i większe w prawej połowie:

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

   Drugi wiersz to kod, który utworzymy dla każdej wartości. Wartości mniejsze lub równe 29,58 otrzymują w swoim kodzie 0, a liczby większe niż 29,58 otrzymują 1 (jest to binarne).

3. Teraz oba wynikowe wektory są dzielone indywidualnie, w sposób rekurencyjny, zgodnie z tą samą zasadą. W naszym przykładzie średnia pierwszego wektora to (15 + 4 + 0 + 5 + 18) / 5 = 8,4 a średnia drugiego wektora to (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48,7. Każdy z tych dwóch wektorów jest dalej dzielony na dwa kolejne wektory i do każdego z nich dodawany jest drugi bit kodu w zależności od jego porównania ze średnią. Oto wynik:

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

   Zwróć uwagę, że ponownie dodano 0 dla liczb mniejszych lub równych średniej (dla każdego wektora), a 1 dla liczb większych od średniej.

4. Ten algorytm jest powtarzany rekurencyjnie:

   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

   W tym momencie każdy wektor ma tylko jeden element. Tak więc dla każdego kolejnego kroku zostanie dodane 0, ponieważ liczba zawsze będzie sobie równa (warunek dla 0 jest taki, że liczba musi być mniejsza lub równa średniej, która jest sama).

Jak dotąd mamy poziom kwantyzacji L=5. Jeśli mamy używać L=8, musimy do każdego kodu dodać trzy zera. Wynik konwersji każdego kodu z binarnego na całkowity (dla L=8) byłby następujący:

Ostateczny wektor jest sortowany w kolejności rosnącej. Aby uzyskać wektor wyjściowy, musimy zastąpić oryginalną wartość wektora wejściowego jego kodem.

Zauważ, że w wynikowym wektorze:

• Wzmocnienie zostało usunięte. Pierwotny miał niskie wzmocnienie, z zakresem od 0 do 64. Teraz jego wzmocnienie wynosi od 0 do 240, co stanowi prawie cały 8-bitowy zakres. Mówi się, że wzmocnienie jest usuwane, ponieważ nie ma znaczenia, czy pomnożymy wszystkie elementy oryginalnego wektora przez liczbę, taką jak 2, czy jeśli podzielimy wszystko przez 2, wektor wyjściowy będzie mniej więcej taki sam. Jego zakres byłby mniej więcej cały zakres wektora docelowego (8 bitów dla L=8). Jeśli pomnożymy wektor wejściowy przez dwa, wektor wyjściowy będzie faktycznie taki sam, ponieważ w każdym kroku te same liczby, które były poniżej lub powyżej średniej, będą nadal znajdować się poniżej lub powyżej niej i dodamy te same 0 lub 1 do wyjścia. Tylko jeśli to podzielimy, wynik byłby mniej więcej taki sam, a nie dokładnie taki sam, ponieważ liczby nieparzyste, takie jak 15, będą musiały zostać zaokrąglone, a obliczenia mogą się wtedy różnić. Przeszliśmy od ciemnego obrazu do obrazu z pikselami w zakresie od ciemnych kolorów (0) do jaśniejszych kolorów (240), wykorzystując cały zakres.
• Błąd jest usunięty, chociaż nie możemy go całkiem zaobserwować w tym przykładzie. Dzieje się tak, ponieważ nie mamy odchylenia, ponieważ nasza najniższa wartość wynosi 0. Gdybyśmy faktycznie mieli stronniczość, zostałyby usunięte. Jeśli weźmiemy dowolną liczbę „K” i dodamy ją do każdego elementu wektora wejściowego, obliczenia liczb powyżej i poniżej średniej w każdym kroku nie będą się różnić. Dane wyjściowe będą nadal takie same. Spowodowałoby to również, że obrazy są zbyt jasne, aby stać się obrazami o kolorach od ciemnych do jasnych.
• Mamy obraz z ulepszonymi szczegółami. Zwróć uwagę, jak dla każdego rekurencyjnego kroku, który wykonujemy, w rzeczywistości powiększamy szczegóły i konstruujemy dane wyjściowe, ujawniając te szczegóły tak bardzo, jak to możliwe. A ponieważ zastosujemy tę technikę do każdego kanału RGB, ujawnimy jak najwięcej szczegółów, tracąc jednak informacje o oryginalnych tonach każdego koloru.

Mając obraz podobny do wektora pikseli RGB, gdzie każdy punkt ma 8 bitów dla R, 8 dla G i 8 dla B; możemy z niego wyodrębnić trzy wektory, po jednym dla każdego koloru, i zastosować algorytm do każdego wektora. Następnie ponownie tworzymy wektor RGB z tych trzech wektorów wyjściowych i mamy obraz przetworzony przez SMQT, tak jak w przypadku tego z Teatru Bruin.

Złożoność

Algorytm wymaga, aby dla każdego poziomu kwantyzacji (L) w pierwszym przejściu zbadać N elementów, aby znaleźć średnią dla każdego wektora, a następnie w drugim przejściu każdy z tych N elementów musi zostać porównany z odpowiednią średnią w aby podzielić każdy wektor po kolei. Na koniec N elementów należy zastąpić ich kodami. Dlatego złożoność algorytmu wynosi O((L*2*N) + N) = O((2*L + 1)*N), czyli O(L*N).

Wykres wyodrębniony z pracy jest zgodny ze złożonością O(L*N). Im niższe L, tym szybsze przetwarzanie w sposób w przybliżeniu liniowy (większa liczba klatek na sekundę). W celu poprawy szybkości przetwarzania artykuł sugeruje obniżenie wartości L: „wybór niższego poziomu L może być bezpośrednim sposobem na zmniejszenie szybkości przetwarzania, ale przy obniżonej jakości obrazu”.

Poprawa

Tutaj znajdziemy sposób na poprawę szybkości bez obniżania jakości obrazu. przeanalizujemy proces transformacji i znajdziemy szybszy algorytm. Aby uzyskać pełniejszą perspektywę, zobaczmy przykład z powtarzającymi się liczbami:

Wektorów nie można już dzielić, a zera muszą być dodawane, dopóki nie osiągniemy pożądanego L.

Dla uproszczenia załóżmy, że wejście może wynosić od 0 do 31, a wyjście od 0 do 7 (L=3), jak widać na przykładzie.

Zauważ, że obliczenie średniej pierwszego wektora (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 daje ten sam wynik, co obliczenie średniej całego ostatniego wektora, ponieważ jest to tylko ten sam wektor z elementami w innej kolejności: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

W drugim kroku musimy rekurencyjnie obliczyć każdy wektor. Obliczamy więc średnią danych wejściowych wyszarzonych, które są pierwszymi 6 elementami ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8) i średnią pustych danych wejściowych, które są ostatnimi 4 elementami ((25 + 31 + 31 + 25) / 4 = 28):

Zauważ ponownie, że jeśli użyjemy ostatniego wektora, tego, który jest całkowicie uporządkowany, wyniki są takie same. Dla pierwszych 6 elementów mamy: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8) a dla ostatnich 4 elementów: ((25 + 25 + 31 + 31) / 4 = 28) . Ponieważ to tylko dodatek, kolejność sum nie ma znaczenia.

To samo dotyczy następnego kroku:

Obliczenia są takie same jak w przypadku ostatniego wektora: ((7 + 1 + 1 + 7) / 4 = 4) będzie równe ((1 + 1 + 7 + 7) / 4 = 4).

To samo dotyczy pozostałych wektorów i kroków.

Obliczenie średniej to po prostu suma wartości elementów w przedziale podzielona przez liczbę elementów w przedziale. Oznacza to, że możemy wstępnie obliczyć wszystkie te wartości i uniknąć powtarzania tego obliczenia L razy.

Zobaczmy, jak zastosować to, co nazwiemy algorytmem FastSMQT w naszym przykładzie:

1. Utwórz tabelę z 32 kolumnami i 3 wierszami, jak widać poniżej. Pierwszy wiersz w tabeli reprezentuje indeks tabeli (od 0 do 31) i nie trzeba go uwzględniać podczas kodowania tabeli. Ale jest to wyraźnie pokazane, aby ułatwić naśladowanie tego przykładu.

2. Przeprowadź iterację N elementów, licząc częstotliwość każdej wartości. W naszym przykładzie wszystkie elementy 1, 7, 16, 25 i 31 mają częstotliwość 2. Wszystkie pozostałe elementy mają częstotliwość 0. Ten krok ma złożoność O(N).

3. Teraz, gdy wektor częstotliwości jest wypełniony, musimy iterować ten wektor (wektor częstotliwości, a nie wektor wejściowy). Nie iterujemy już N elementów, ale R (R należy do zakresu: 2^L), co w tym przypadku wynosi 32 (0 do 31). Podczas przetwarzania pikseli N może wynosić wiele milionów (megapikseli), ale R wynosi zwykle 256 (jeden wektor dla każdego koloru). W naszym przykładzie jest to 32. Wypełnimy jednocześnie dwa kolejne wiersze tabeli. Pierwszy z tych wierszy (drugi w tabeli) będzie zawierał sumę dotychczasowych częstotliwości. Druga (trzecia tabela) będzie zawierała sumę wartości wszystkich elementów, które pojawiły się do tej pory.

   W naszym przykładzie, kiedy dochodzimy do 1, wstawiamy 2 w drugim rzędzie tabeli, ponieważ do tej pory pojawiły się dwie jedynki. Wstawiamy również 2 w trzecim wierszu tabeli, ponieważ 1 + 1 = 2. Kontynuujemy zapisywanie tych dwóch wartości na każdej z kolejnych pozycji, aż dojdziemy do 7. Ponieważ liczba 7 pojawia się dwukrotnie, dodajemy 2 do akumulator drugiego rzędu, bo do tej pory pojawiły się 4 liczby (1, 1, 7, 7). I dodajemy 7 + 7 = 14 do trzeciego wiersza, co daje 2 + 14 = 16, ponieważ 1 + 1 + 7 + 7 = 16. Kontynuujemy ten algorytm, aż zakończymy iterację tych elementów. Złożoność tego kroku to O(2^L), co w naszym przypadku to O(32), a przy pracy z pikselami RGB jest to 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-skumulowany	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   suma	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. Następnym krokiem jest usunięcie z tabeli kolumn z elementami, które mają częstotliwość 0, i aby przykład był wyraźniejszy, usuniemy również drugi wiersz, ponieważ nie ma on już znaczenia, jak zobaczysz.

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

5. Pamiętaj, że moglibyśmy użyć ostatniego (całkowicie uporządkowanego) wektora do wykonania obliczeń dla każdego kroku, a wyniki nadal będą takie same. Zauważ, że tutaj, w tej tabeli, mamy ostatni wektor ze wszystkimi już wykonanymi obliczeniami wstępnymi.

   Zasadniczo musimy wykonać algorytm SMQT na tym małym wektorze, ale w przeciwieństwie do oryginalnego wektora, od którego zaczęliśmy, ten będzie znacznie łatwiejszy.

   Najpierw musimy obliczyć średnią wszystkich próbek. Możemy to łatwo znaleźć przez: sum[31] / n[31] = 160 / 10 = 16. Dzielimy więc tabelę na dwa wektory i zaczynamy pisać kod binarny dla każdego z nich:

   i	1	7	16	25	31
   n	2	4	6	8	10
   suma	2	16	48	98	160
   kod	0	0	0	1	1

   Teraz ponownie dzielimy każdy wektor. Średnia pierwszego wektora to: suma[16] / n[16] = 48/6 = 8. A średnia drugiego wektora to: (suma[31] – suma[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   i	1	7	16	25	31
   n	2	4	6	8	10
   suma	2	16	48	98	160
   kod	00	00	01	10	11

   Do podziału pozostał tylko jeden wektor. Średnia wynosi: suma[7] / n[7] = 16 / 4 = 4.

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

   Jak widać, kod dla każdego elementu jest taki sam, gdybyśmy postępowali zgodnie z oryginalnym algorytmem. I zrobiliśmy SMQT na znacznie mniejszym wektorze niż ten z N elementami, a także wstępnie obliczyliśmy wszystkie wartości potrzebne do znalezienia średniej, więc obliczenie wynikowego wektora jest proste i szybkie.

   Złożoność tego kroku to O(L*(2^L)), co dla L=8, aw praktycznych potrzebach przetwarzania obrazu, jest to O(8*(256)) = O(2048) = stała.

6. Ostatnim krokiem jest iteracja N elementów jeszcze raz, zastępując element przez jego kod dla każdego elementu: element[i] = kod[i]. Złożoność to O(N). Złożoność FastSMQT to O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

Równoległość

Oba algorytmy można zrównoleglać, chociaż bardziej wydajne jest uruchamianie jednego algorytmu na rdzeń, jeśli konieczne jest przekształcenie wielu wektorów. Na przykład podczas przetwarzania obrazów możemy przetwarzać każdy kanał RGB w innym rdzeniu zamiast zrównoleglać każdy z tych trzech obliczeń.

Aby zrównoleglić algorytm SMQT, dzieląc wektor na dwa, możemy przetworzyć każdy podwektor w nowym rdzeniu, jeśli rdzeń jest dostępny (w rzeczywistości jeden podwektor w bieżącym rdzeniu, a drugi w nowym rdzeniu). Można to robić rekursywnie, aż osiągniemy całkowitą liczbę dostępnych rdzeni. Równolegle można też dokonywać zamiany wartości na kody.

Algorytm FastSMQT może być również zrównoleglony. W pierwszym kroku wektor wejściowy należy podzielić na liczbę dostępnych rdzeni (C). Dla każdej z tych części należy utworzyć jeden wektor zliczania częstotliwości, który należy wypełnić równolegle. Następnie dodajemy wartości tych wektorów do jednego wynikowego wektora częstotliwości. Kolejnym krokiem, który można zrównoleglić, jest ostatni, w którym zastępujemy wartości ich kodami. Można to zrobić równolegle.

Porównanie złożoności

Całkowita złożoność oryginalnego algorytmu SMQT wynosi O((2*L + 1)*N), czyli O(L*N).

Złożoność FastSMQT to O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

Biorąc pod uwagę stałe L, złożoność staje się po prostu O(N) dla obu. Ale stała, która mnoży N, jest znacznie mniejsza dla FastSMQT i jak zobaczymy, ma dużą różnicę w czasie przetwarzania.

Poniższy wykres porównuje wydajność algorytmów SMQT i FastSMQT dla L=8, co ma miejsce w przypadku przetwarzania obrazu. Wykres pokazuje czas (w milisekundach) potrzebny do przetworzenia N elementów. Zauważ, że złożoność (ze stałymi) SMQT dla L=8 wynosi O(17*N), podczas gdy dla FastSMQT wynosi O(2*N + 2304).

Im większe N, tym dłużej trwa przetwarzanie obrazu przez SMQT. Z drugiej strony w przypadku FastSMQT wzrost jest znacznie wolniejszy.

Dla jeszcze większych wartości N różnica w wydajności jest znacznie bardziej widoczna:

W tym przypadku SMQT zajmuje do wielu sekund przetworzenie niektórych obrazów, podczas gdy FastSMQT nadal znajduje się w strefie „kilku milisekund”.

Nawet przy wielu rdzeniach (w tym przypadku dwa), FastSMQT jest wyraźnie lepszy od samego SMQT:

FastSMQT nie jest zależny od L. Z drugiej strony SMQT jest liniowo zależny od wartości L. Na przykład przy N = 67108864 czas działania SMQT rośnie wraz ze wzrostem wartości L, podczas gdy FastSMQT nie:

Wniosek

Nie wszystkie techniki optymalizacji mają zastosowanie do wszystkich algorytmów, a klucz do poprawy wydajności algorytmu jest często ukryty w pewnym wglądzie w jego działanie. Algorytm FastSMQT wykorzystuje możliwości wstępnego obliczania wartości i charakter obliczeń średnich. W rezultacie umożliwia szybsze przetwarzanie niż oryginalny SMQT. Przyrost L nie ma wpływu na szybkość, chociaż L nie może być dużo większe niż zwykłe 8, ponieważ użycie pamięci wynosi 2^L, co dla 8 jest akceptowalnym 256 (liczba kolumn w naszej tabeli częstotliwości), ale wzrost wydajności ma oczywiste zalety praktyczne.

Ta poprawa szybkości pozwoliła firmie MiddleMatter na zaimplementowanie algorytmu w aplikacji na iOS (i aplikacji na Androida), który poprawia zdjęcia i filmy rejestrowane w warunkach słabego oświetlenia. Dzięki temu ulepszeniu możliwe było przetwarzanie wideo w aplikacji, które w innym przypadku byłoby zbyt wolne dla urządzeń z systemem iOS.

Kod C++ dla algorytmów SMQT i FastSMQT jest dostępny w serwisie GitHub.