Optimierte sukzessive mittlere Quantisierungstransformation

Der SMQT-Algorithmus (Successive Mean Quantization Transform) ist eine nichtlineare Transformation, die die Organisation oder Struktur der Daten aufzeigt und Eigenschaften wie Verstärkung und Verzerrung entfernt. In einem Artikel mit dem Titel The Successive Mean Quantization Transform wird SMQT „in der Sprachverarbeitung und Bildverarbeitung angewendet“. Der Algorithmus kann, wenn er auf Bilder angewendet wird, „als fortschreitende Fokussierung auf die Details in einem Bild angesehen werden“.

Laut einem anderen Artikel mit dem Titel SMQT-based Tone Mapping Operators for High Dynamic Range Images wird es ein „Bild mit verbesserten Details“ ergeben. Das Papier beschreibt zwei Techniken zum Anwenden dieser Transformation auf ein Bild.

1. Wenden Sie SMQT auf die Luminanz jedes Pixels an - es beschreibt die Formel, um die Luminanz aus dem RGB jedes Pixels zu erhalten.

2. Wenden Sie SMQT separat auf jeden RGB-Kanal an – für die Kanäle R, G und B einzeln.

Das folgende Bild zeigt das Ergebnis der beiden Techniken:

Indem wir die zweite Technik auf ein Bild des Bruin-Theaters bei Nacht anwenden, können wir sehen, wie der Algorithmus schrittweise auf die Details des Bildes zoomt und Details enthüllt, die ursprünglich von der Dunkelheit verdeckt wurden:

In diesem Artikel werden wir uns die Funktionsweise dieses Algorithmus genauer ansehen und eine einfache Optimierung untersuchen, die es dem Algorithmus ermöglicht, in praktischen Bildverarbeitungsanwendungen viel leistungsfähiger zu sein.

Der SMQT-Algorithmus

In der Originalarbeit wird der Algorithmus abstrakt beschrieben. Um SMQT besser zu verstehen, werden wir einige einfache Beispiele durchgehen.

Angenommen, wir haben den folgenden Vektor (Sie können ihn sich wie ein Array vorstellen):

Im Falle eines Farbbildes können wir es uns als drei separate Vektoren vorstellen, die jeweils einen bestimmten Farbkanal (RGB) darstellen, und jedes Element des Vektors die Intensität des entsprechenden Pixels darstellt.

Die Schritte zur Anwendung des SMQT-Algorithmus sind:

1. Berechnen Sie den Mittelwert des Vektors, der in diesem Fall 29,58 beträgt.

2. Teilen Sie den Vektor in zwei Teile und lassen Sie die Zahlen, die kleiner oder gleich 29,58 sind, in der linken Hälfte und die Zahlen, die größer sind, in der rechten Hälfte:

   fünfzehn	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   Die zweite Zeile ist der Code, den wir für jeden Wert erstellen werden. Die Werte kleiner oder gleich 29,58 erhalten eine 0 in ihrem Code, und die Zahlen größer als 29,58 erhalten eine 1 (dies ist binär).

3. Nun werden die beiden resultierenden Vektoren einzeln rekursiv nach derselben Regel geteilt. In unserem Beispiel ist der Mittelwert des ersten Vektors (15 + 4 + 0 + 5 + 18) / 5 = 8,4, und der Mittelwert des zweiten Vektors ist (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48,7. Jeder dieser zwei Vektoren wird weiter in zwei weitere Vektoren aufgeteilt, und jedem wird ein zweites Codebit hinzugefügt, abhängig von seinem Vergleich mit dem Mittelwert. Das ist das Ergebnis:

   4	0	5	fünfzehn	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   Beachten Sie, dass für Zahlen, die kleiner oder gleich dem Mittelwert sind (für jeden Vektor), eine 0 und für Zahlen, die größer als der Mittelwert sind, eine 1 angehängt wurde.

4. Dieser Algorithmus wird rekursiv wiederholt:

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

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

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

   An dieser Stelle hat jeder Vektor nur ein Element. Daher wird für jeden aufeinanderfolgenden Schritt eine 0 angehängt, da die Zahl immer gleich sich selbst ist (die Bedingung für eine 0 ist, dass die Zahl kleiner oder gleich dem Mittelwert sein muss, der sie selbst ist).

Bisher haben wir einen Quantisierungspegel von L=5. Wenn wir L = 8 verwenden würden, müssten wir an jeden Code drei Nullen anhängen. Das Ergebnis der Konvertierung jedes Codes von binär nach ganzzahlig (für L=8) wäre:

Der endgültige Vektor wird in aufsteigender Reihenfolge sortiert. Um den Ausgangsvektor zu erhalten, müssen wir den ursprünglichen Wert des Eingangsvektors durch seinen Code ersetzen.

Beachten Sie, dass im resultierenden Vektor:

• Der Gewinn wurde entfernt. Das Original hatte eine niedrige Verstärkung mit einem Bereich von 0 bis 64. Jetzt reicht seine Verstärkung von 0 bis 240, was fast dem gesamten 8-Bit-Bereich entspricht. Es wird gesagt, dass die Verstärkung entfernt wird, weil es keine Rolle spielt, ob wir alle Elemente des ursprünglichen Vektors mit einer Zahl wie 2 multiplizieren oder alle durch 2 teilen, der Ausgabevektor wäre ungefähr gleich. Sein Bereich wäre ungefähr der gesamte Bereich des Zielvektors (8 Bits für L = 8). Wenn wir den Eingabevektor mit zwei multiplizieren, ist der Ausgabevektor tatsächlich derselbe, da in jedem Schritt dieselben Zahlen, die unter oder über dem Mittelwert lagen, weiterhin unter oder über ihm liegen, und wir werden dieselben Nullen oder Einsen hinzufügen zum Ausgang. Nur wenn wir es dividieren, wäre das Ergebnis ungefähr gleich und nicht genau gleich, da ungerade Zahlen wie 15 gerundet werden müssen und die Berechnungen dann variieren können. Wir gingen von einem dunklen Bild zu einem Bild, dessen Pixel von dunklen Farben (0) bis zu helleren Farben (240) reichten, wobei wir den gesamten Bereich nutzten.
• Die Vorspannung wird entfernt, obwohl wir sie in diesem Beispiel nicht ganz beobachten können. Dies liegt daran, dass wir keine Verzerrung haben, da unser niedrigster Wert 0 ist. Wenn wir tatsächlich eine Verzerrung hätten, wäre sie entfernt worden. Wenn wir eine beliebige Zahl „K“ nehmen und sie zu jedem Element des Eingabevektors hinzufügen, ändert sich die Berechnung der Zahlen über und unter dem Mittelwert in jedem Schritt nicht. Die Ausgabe wird immer noch die gleiche sein. Dies würde auch Bilder erzeugen, die zu hell sind, um zu Bildern zu werden, die von dunklen bis zu hellen Farben reichen.
• Wir haben ein Bild mit verbesserten Details. Beachten Sie, dass wir bei jedem rekursiven Schritt, den wir unternehmen, tatsächlich in die Details hineinzoomen und die Ausgabe konstruieren, indem wir diese Details so weit wie möglich offenlegen. Und da wir diese Technik auf jeden RGB-Kanal anwenden, werden wir so viele Details wie möglich offenlegen, obwohl wir Informationen über die ursprünglichen Töne jeder Farbe verlieren.

Gegeben ist ein Bild wie ein Vektor aus RGB-Pixeln, wobei jeder Punkt 8 Bit für R, 8 für G und 8 für B ist; Wir können daraus drei Vektoren extrahieren, einen für jede Farbe, und den Algorithmus auf jeden Vektor anwenden. Dann bilden wir den RGB-Vektor wieder aus diesen drei Ausgabevektoren und wir haben das SMQT-verarbeitete Bild, wie es beim Bruin Theatre gemacht wurde.

Komplexität

Der Algorithmus erfordert, dass für jede Quantisierungsstufe (L) N Elemente in einem ersten Durchgang untersucht werden müssen, um den Mittelwert für jeden Vektor zu finden, und dann in einem zweiten Durchgang jedes dieser N Elemente mit dem entsprechenden Mittelwert in verglichen werden muss um jeden Vektor der Reihe nach aufzuteilen. Schließlich müssen N Elemente durch ihre Codes ersetzt werden. Daher ist die Komplexität des Algorithmus O((L*2*N) + N) = O((2*L + 1)*N), was O(L*N) ist.

Der aus dem Papier extrahierte Graph stimmt mit der O(L*N)-Komplexität überein. Je niedriger L, desto schneller die Verarbeitung auf annähernd lineare Weise (größere Anzahl von Bildern pro Sekunde). Um die Verarbeitungsgeschwindigkeit zu verbessern, schlägt das Papier vor, die Werte von L zu verringern: „Die Auswahl eines niedrigeren L-Levels kann ein direkter Weg sein, die Verarbeitungsgeschwindigkeit zu verringern, jedoch mit verringerter Bildqualität“.

Verbesserung

Hier werden wir einen Weg finden, die Geschwindigkeit zu verbessern, ohne die Bildqualität zu verringern. Wir werden den Transformationsprozess analysieren und einen schnelleren Algorithmus finden. Um eine vollständigere Perspektive zu erhalten, sehen wir uns ein Beispiel mit wiederholten Zahlen an:

Die Vektoren können nicht mehr geteilt werden, und es müssen Nullen angehängt werden, bis wir das gewünschte L erreicht haben.

Nehmen wir der Einfachheit halber an, dass der Eingang von 0 bis 31 gehen kann und der Ausgang von 0 bis 7 (L=3), wie es im Beispiel zu sehen ist.

Beachten Sie, dass die Berechnung des Mittelwerts des ersten Vektors (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 dasselbe Ergebnis liefert wie die Berechnung des Mittelwerts des gesamten letzten Vektors, da dies der Fall ist nur derselbe Vektor mit den Elementen in einer anderen Reihenfolge: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

Im zweiten Schritt müssen wir jeden Vektor rekursiv berechnen. Also berechnen wir den Mittelwert der grau hinterlegten Eingaben, die die ersten 6 Elemente sind ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8), und den Mittelwert der leeren Eingabe, die die letzten 4 Elemente sind ((25 + 31 + 31 + 25) / 4 = 28):

Beachten Sie noch einmal, dass die Ergebnisse dieselben sind, wenn wir den letzten Vektor verwenden, den vollständig geordneten. Für die ersten 6 Elemente haben wir: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8), und für die letzten 4 Elemente: ((25 + 25 + 31 + 31) / 4 = 28) . Da es sich nur um eine Addition handelt, spielt die Reihenfolge der Summanden keine Rolle.

Gleiches gilt für den nächsten Schritt:

Die Berechnungen sind die gleichen wie beim letzten Vektor: ((7 + 1 + 1 + 7) / 4 = 4) wird gleich ((1 + 1 + 7 + 7) / 4 = 4).

Und das gleiche gilt für den Rest der Vektoren und Schritte.

Die Berechnung des Mittelwerts ist einfach die Summe der Werte der Elemente im Intervall, dividiert durch die Anzahl der Elemente im Intervall. Das bedeutet, dass wir all diese Werte im Voraus berechnen können und vermeiden, diese Berechnung L-mal zu wiederholen.

Sehen wir uns die Schritte an, um den sogenannten FastSMQT-Algorithmus auf unser Beispiel anzuwenden:

1. Erstellen Sie eine Tabelle mit 32 Spalten und 3 Zeilen, wie Sie unten sehen können. Die erste Zeile in der Tabelle stellt den Index der Tabelle dar (0 bis 31) und muss beim Codieren der Tabelle nicht eingeschlossen werden. Aber es wird explizit gezeigt, um das Beispiel leichter nachvollziehen zu können.

2. Iteriere die N Elemente einmal und zähle die Häufigkeit jedes Werts. In unserem Beispiel haben die Elemente 1, 7, 16, 25 und 31 alle eine Häufigkeit von 2. Alle anderen Elemente haben eine Häufigkeit von 0. Dieser Schritt hat eine Komplexität von O(N).

3. Nachdem der Frequenzvektor gefüllt ist, müssen wir diesen Vektor iterieren (den Frequenzvektor, nicht den Eingabevektor). Wir iterieren nicht mehr N Elemente, sondern R (R liegt im Bereich: 2^L), was in diesem Fall 32 (0 bis 31) ist. Bei der Verarbeitung von Pixeln kann N viele Millionen (Megapixel) betragen, aber R ist normalerweise 256 (ein Vektor für jede Farbe). In unserem Beispiel ist es 32. Wir werden die folgenden zwei Zeilen der Tabelle gleichzeitig füllen. Die erste dieser Zeilen (die zweite der Tabelle) enthält die Summe der bisherigen Häufigkeiten. Der zweite (der dritte der Tabelle) wird die Summe des Wertes aller Elemente haben, die bisher erschienen sind.

   Wenn wir in unserem Beispiel bei 1 angelangt sind, schreiben wir eine 2 in die zweite Reihe der Tabelle, weil bisher zwei 1en erschienen sind. Und wir schreiben auch eine 2 in die dritte Zeile der Tabelle, weil 1 + 1 = 2. Wir fahren fort, diese beiden Werte auf jede der nächsten Positionen zu schreiben, bis wir bei 7 angelangt sind. Da die Zahl 7 zweimal vorkommt, addieren wir 2 zu der Akkumulator der zweiten Reihe, weil jetzt bisher 4 Zahlen erschienen sind (1, 1, 7, 7). Und wir addieren 7 + 7 = 14 zur dritten Zeile, was 2 + 14 = 16 ergibt, weil 1 + 1 + 7 + 7 = 16. Wir fahren mit diesem Algorithmus fort, bis wir die Iteration dieser Elemente abgeschlossen haben. Die Komplexität dieses Schritts ist O(2^L), was in unserem Fall O(32) ist, und wenn man mit RGB-Pixeln arbeitet, ist es O(256).

   ich	0	1	2	...	6	7	8	...	fünfzehn	16	17	...	24	25	26	...	30	31
   n	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   n-kumulativ	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   Summe	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. Der nächste Schritt besteht darin, die Spalten mit Elementen mit einer Häufigkeit von 0 aus der Tabelle zu entfernen, und um das Beispiel klarer zu sehen, entfernen wir auch die zweite Zeile, da sie nicht mehr relevant ist, wie Sie sehen werden.

   ich	1	7	16	25	31
   n	2	4	6	8	10
   Summe	2	16	48	98	160

5. Denken Sie daran, dass wir den letzten (vollständig geordneten) Vektor verwenden könnten, um die Berechnungen für jeden Schritt durchzuführen, und die Ergebnisse immer noch dieselben sind. Beachten Sie, dass wir hier in dieser Tabelle den letzten Vektor mit allen bereits durchgeführten Vorberechnungen haben.

   Grundsätzlich müssen wir den SMQT-Algorithmus mit diesem kleinen Vektor ausführen, aber im Gegensatz zu dem ursprünglichen Vektor, mit dem wir begonnen haben, ist dieser viel einfacher.

   Zuerst müssen wir den Mittelwert aller Stichproben berechnen. Wir können es leicht finden durch: sum[31] / n[31] = 160 / 10 = 16. Also teilen wir die Tabelle in zwei Vektoren und beginnen, den Binärcode für jeden zu schreiben:

   ich	1	7	16	25	31
   n	2	4	6	8	10
   Summe	2	16	48	98	160
   Code	0	0	0	1	1

   Jetzt teilen wir jeden Vektor erneut. Der Mittelwert des ersten Vektors ist: sum[16] / n[16] = 48 / 6 = 8. Und der Mittelwert des zweiten Vektors ist: (sum[31] – sum[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   ich	1	7	16	25	31
   n	2	4	6	8	10
   Summe	2	16	48	98	160
   Code	00	00	01	10	11

   Es bleibt nur noch ein Vektor zu teilen. Der Mittelwert ist: Summe[7] / n[7] = 16 / 4 = 4.

   ich	1	7	16	25	31
   n	2	4	6	8	10
   Summe	2	16	48	98	160
   Code	000	001	010	100	110

   Wie Sie sehen können, ist der Code für jedes Element gleich, wenn wir dem ursprünglichen Algorithmus gefolgt wären. Und wir haben die SMQT mit einem viel kleineren Vektor als dem mit N Elementen durchgeführt und wir haben auch alle Werte vorberechnet, die wir brauchen, um den Mittelwert zu finden, so dass es einfach und schnell ist, den resultierenden Vektor zu berechnen.

   Die Komplexität dieses Schritts ist O(L*(2^L)), was für L=8 und in praktischen Bildverarbeitungsanforderungen O(8*(256)) = O(2048) = Konstante ist.

6. Der letzte Schritt besteht darin, N Elemente zu iterieren, wobei wiederum das Element durch seinen Code für jedes Element ersetzt wird: element[i] = code[i]. Die Komplexität ist O(N). Die Komplexität von FastSMQT ist O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

Parallelität

Beide Algorithmen können parallelisiert werden, obwohl es effizienter ist, stattdessen einen Algorithmus pro Kern auszuführen, wenn mehrere Vektoren transformiert werden müssen. Wenn wir beispielsweise Bilder verarbeiten, können wir jeden RGB-Kanal in einem anderen Kern verarbeiten, anstatt jede dieser drei Berechnungen zu parallelisieren.

Um den SMQT-Algorithmus zu parallelisieren, können wir, wenn wir einen Vektor in zwei teilen, jeden Teilvektor in einem neuen Kern verarbeiten, wenn ein Kern verfügbar ist (eigentlich ein Teilvektor im aktuellen Kern und der andere in einem neuen Kern). Dies kann rekursiv erfolgen, bis wir die Gesamtzahl der verfügbaren Kerne erreicht haben. Das Ersetzen von Werten durch Codes kann auch parallel für erfolgen.

Der FastSMQT-Algorithmus kann auch parallelisiert werden. Im ersten Schritt muss der Eingabevektor in die Anzahl der verfügbaren Kerne (C) geteilt werden. Für jeden dieser Teile muss ein Vektor der Häufigkeitszählung erstellt und parallel gefüllt werden. Dann addieren wir die Werte dieser Vektoren zu einem resultierenden Frequenzvektor. Der nächste Schritt, der parallelisiert werden kann, ist der letzte, wenn wir die Werte durch ihre Codes ersetzen. Dies kann parallel z.

Komplexitätsvergleich

Die Gesamtkomplexität des ursprünglichen SMQT-Algorithmus beträgt O((2*L + 1)*N), also O(L*N).

Die Komplexität von FastSMQT ist O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

Bei einem festen L wird die Komplexität für beide zu O(N). Aber die Konstante, die N multipliziert, ist für FastSMQT viel kleiner und macht einen großen Unterschied in der Verarbeitungszeit, wie wir sehen werden.

Die folgende Grafik vergleicht die Leistung von SMQT- und FastSMQT-Algorithmen für L=8, was bei der Bildverarbeitung der Fall ist. Das Diagramm zeigt die Zeit (in Millisekunden), die für die Verarbeitung von N Elementen benötigt wird. Beachten Sie, dass die Komplexität (mit Konstanten) von SMQT für L = 8 O (17 * N) ist, während für FastSMQT O (2 * N + 2304) ist.

Je größer das N, desto länger dauert es, bis SMQT das Bild verarbeitet hat. Bei FastSMQT hingegen ist das Wachstum viel langsamer.

Bei noch größeren Werten von N ist der Leistungsunterschied viel deutlicher:

Hier benötigt SMQT bis zu mehreren Sekunden Zeit, um bestimmte Bilder zu verarbeiten, während FastSMQT noch im Bereich der „wenigen Millisekunden“ liegt.

Selbst mit mehreren Kernen (in diesem Fall zwei) ist FastSMQT SMQT eindeutig immer noch überlegen:

FastSMQT ist nicht von L abhängig. SMQT hingegen ist linear vom Wert von L abhängig. Beispielsweise steigt bei N = 67108864 die Laufzeit von SMQT mit zunehmendem Wert von L, während FastSMQT dies nicht tut:

Fazit

Nicht alle Optimierungstechniken sind auf alle Algorithmen anwendbar, und der Schlüssel zur Verbesserung der Leistung eines Algorithmus liegt oft in einem Einblick in die Funktionsweise des Algorithmus. Dieser FastSMQT-Algorithmus macht sich die Möglichkeiten der Vorberechnung von Werten und die Art der Mittelwertberechnung zunutze. Dadurch ermöglicht es eine schnellere Verarbeitung als das ursprüngliche SMQT. Die Geschwindigkeit wird durch das Inkrement von L nicht beeinflusst, obwohl L nicht viel größer als die üblichen 8 sein kann, da der Speicherverbrauch 2 ^ L beträgt, was für 8 akzeptable 256 (Anzahl der Spalten in unserer Häufigkeitstabelle) ist, aber der Leistungsgewinn hat offensichtliche praktische Vorteile.

Diese Geschwindigkeitsverbesserung ermöglichte es MiddleMatter, den Algorithmus in einer iOS-Anwendung (und einer Android-Anwendung) zu implementieren, die Bilder und Videos verbessert, die bei schlechten Lichtverhältnissen aufgenommen wurden. Mit dieser Verbesserung war es möglich, eine Videoverarbeitung in der Anwendung durchzuführen, die sonst für iOS-Geräte zu langsam wäre.

Der C++-Code für SMQT- und FastSMQT-Algorithmen ist auf GitHub verfügbar.