Wie ich einen Filter erstellt habe, der das Bild auch nach einer Million Läufen nicht beschädigt - Teil 2

Im ersten Teil dieses Beitrags habe ich darüber gesprochen, wie die wiederholte Verwendung von Standard-Halfpel-Filtern zu verzerrten Bildern führt, und dann einen neuen Filter gezeigt, bei dem dieses Problem nicht auftritt.

Es war etwas verschwommener und das würde nicht jedem passen. Es war jedoch besser als seine Alternativen - tatsächlich wurde dieser Filter in der Originalversion von Bink 2 verwendet . Aufgrund der ständigen Arbeitsbelastung gelang es mir nie wieder, zu ihm zurückzukehren und ihn genauer zu untersuchen.

Aber jetzt, da ich die Zeit gefunden habe, zu diesem Filter zurückzukehren und einen Artikel darüber zu schreiben, sollte ich endlich die Frage stellen: Gibt es einen weniger unscharfen Filter, der immer noch die Eigenschaft „unendliche Stabilität“ beibehält?

Spoiler-Warnung: Die richtige Antwort lautet "wahrscheinlich nicht" und "definitiv da". Bevor wir jedoch herausfinden, warum es zwei Antworten auf diese Frage gibt und was sie bedeuten, sollten wir den Prüfstand besser vorbereiten.

Offset-Einstellung

Als ich anfänglich an diesem Problem arbeitete, hatte ich keine Ahnung, wonach ich suchte. Ich wusste nicht einmal, dass es so etwas wie einen „unendlich stabilen“ Halbpel-Filter gibt, also habe ich bei seiner Suche kein System erstellt. Ich war nur auf der Suche nach etwas, das den „vielen“ Filteriterationen ohne Bildverzerrung standhält. Alle Bilder aus dem ersten Teil spiegeln diese Methode wider: Das Bild wird jeweils um ein halbes Pixel von rechts nach links verschoben. Wenn Sie den Filter also 100 Mal anwenden, wird das resultierende Bild um 50 Pixel verschoben.

Jetzt, da wir wissen, wonach wir tatsächlich suchen, können wir etwas genauer sein. Wenn Sie den Halfpel-Filter zweimal anwenden, verschieben wir das Bild genau um ein Pixel. Das heißt, wenn wir das Bild einfach um ein Pixel zurück verschieben , bleibt es im selben Raum. Dank dessen sieht der Test viel schöner aus, da wir dann den Filter nicht nur beliebig oft anwenden können, ohne befürchten zu müssen, dass das Bild vom Bildschirm "wegkriecht", sondern auch den Unterschied des Bildes zu früheren Versionen und zum Original feststellen können.

Dadurch können wir die Filter automatisch testen. Wir wenden den Filter einfach viele Male an und sehen eines von zwei Dingen: entweder Konvergenz zu einem unveränderten Bild, was darauf hinweist, dass der Filter unendlich stabil ist, oder eine signifikant große Abweichung vom Originalbild, was darauf hinweist, dass der Filter „defekt“ ist. Für diese Tests habe ich den durchschnittlichen Fehler pro Kanal 64 (von 255) oder den maximalen Fehler auf einem der Kanäle bis zum vollen 255 als "signifikant groß" gewählt. Wenn eine dieser Bedingungen zutrifft, gehen wir davon aus, dass der Filter "kaputt" ist. ".

Testen Sie die Filter aus dem ersten Teil erneut

Jetzt verstehen wir besser, wie diese Filter getestet werden. Schauen wir uns also die Filter aus dem ersten Teil genauer an. Beginnen wir mit einem Bilinear, was natürlich nicht sehr interessant ist:


Dies ist ein Bild nach 244 Iterationen. Wie zu erwarten, "bricht" das Bild aufgrund der konstanten Mittelung der Pixel allmählich. Aber auch es erreicht allmählich die Grenze des durchschnittlichen Fehlers.

Hier ist h.264:


Um das Bild zu brechen, reichen ihm 78 Iterationen. Der HEVC-Filter mit 8 Samples verhält sich etwas besser, bricht aber nach 150 Iterationen immer noch:


Lanczos mit 6 Proben bricht nach 166 Iterationen:


Das sind alle unsere kaputten Filter. Alles was bleibt ist mein ganzzahliger Filter:


Wie erwartet war er nicht der einzige , der brach. Nach 208 Iterationen konvergiert es zu einem unendlich stabilen Bild.

Was wir hier wissen, ist bemerkenswert: Zumindest für eine Vielzahl von Testbildern ist dieser Filter unendlich stabil , dh er erzeugt niemals ein Artefakt, egal wie oft er verwendet wird.

Dies bringt uns zurück zu der ursprünglichen Frage: Ist er wirklich der Beste? Und Sie kennen die Antworten bereits, denn am Anfang des Artikels habe ich auch geschrieben: „wahrscheinlich nicht“ und „definitiv ja“.

Schauen wir uns zuerst den Teil „wahrscheinlich nicht“ an.

Ganzzahlige Filter

Im ersten Teil des Beitrags erwähnte ich, dass der Filterkern, den ich fand, "der beste der erkannten" war, und dies ist seine Besonderheit. Und hier ist die Funktion:

Als ich nach diesem Filter suchte, suchte ich tatsächlich nicht nach dem besten Filter. Ich suchte nach dem besten Filter , der mit einer sehr kleinen Anzahl von ganzzahligen Verschiebungen, Additionen und Subtraktionen ausgedrückt werden kann . Es mag seltsam erscheinen, aber nehmen Sie sich Zeit.

Sie haben vielleicht bemerkt, dass ich die Koeffizienten von h.264, HEVC und dem bilinearen Filter sowie meinen Filter als ganzzahlige Zähler über ganzzahlige Nenner wie folgt notiert habe:

MyKernel[] = {1.0/32.0, -4.0/32.0, 19.0/32.0, 19.0/32.0, -4.0/32.0, 1.0/32.0}; 

Aber im Fall von Fenster-Sinc habe ich anders gehandelt und es so geschrieben:

 LanczosKernel[] = {0.02446, -0.13587, 0.61141, 0.61141, -0.13587, 0.02446}; 

Der Grund dafür ist, dass Fenster-Sinc tatsächlich aus einer kontinuierlichen mathematischen Funktion abgeleitet wird, die nichts mit gewöhnlichen ganzzahligen Brüchen zu tun hat. Bei Verwendung dieses Filters werden Gleitkommazahlen (so genau wie möglich) verwendet, die den Werten der sinc-Funktion entsprechen. Wenn Sie sich bemühen, sie genau anzuwenden, sollten Sie sie nicht auf gewöhnliche Brüche runden, da dies zu einem Fehler führt.

Videocodecs können es sich traditionell nicht leisten, solche Vorgänge auszuführen. Gleitkommaoperationen bei so „schweren“ Aufgaben wie der Bewegungskompensation sind bei Geräten mit geringem Stromverbrauch oder Spezialgeräten einfach nicht möglich. Dies gilt insbesondere dann, wenn es sich um Codecs nach Industriestandard handelt, die auf einer Vielzahl von Geräten ausgeführt werden sollten, einschließlich kostengünstiger, kostengünstiger eingebetteter Chips.

Selbst wenn Sie sie auf der CPU ausführen, basieren moderne Befehlssätze auf SIMD, dh Ganzzahloperationen auf der CPU können immer noch schneller ausgeführt werden: Sie können zwei 16-Bit-Ganzzahlen in den Raum eines 32-Bit-Gleitkommas einfügen, wodurch sich die Leistung von Operationen im Wesentlichen verdoppelt. Wenn wir also die genaue Anzahl der Zyklen pro Operation berücksichtigen, ist ein Gleitkomma nicht immer die schnellste Option.

Jetzt sehen Sie, warum diese Funktion wichtig war. Da ich nur einfache 16-Bit-Ganzzahloperationen benötigte, suchte ich nach den Kerneln, die als kleine Ganzzahlen über Teilern in der Potenz von zwei bis 64 und nicht mehr ausgedrückt werden können. Dies ist ein viel begrenzterer Satz von Filtern als wenn ich einen Satz von 6 Gleitkommakoeffizienten in Betracht ziehen würde .

In ähnlicher Weise habe ich aus Effizienzgründen keine andere Anzahl von Proben berücksichtigt. Die einzige Option war 6 oder weniger, daher habe ich nicht einmal Versionen mit 8 oder 10 Beispielen getestet.

So kamen wir zur ersten Antwort: "wahrscheinlich nicht." Wenn wir diese Einschränkungen einhalten, werden wir höchstwahrscheinlich keinen besseren Filter finden, der unendlich oft ohne Verschlechterung angewendet werden kann. Der Filterkern aus dem ersten Teil ist wahrscheinlich der beste, den wir finden können, obwohl ich zugeben muss, dass ich ihn nicht erschöpfend beweisen kann.

Aber was ist, wenn wir uns nicht an solche Beschränkungen halten müssen?

Gleitkomma-Version

Wenn wir die Einschränkungen für die Originalversion von Bink 2 (die mittlerweile ziemlich veraltet ist - seitdem wurden viele Revisionen veröffentlicht) aufheben und beliebige Gleitkommakoeffizienten verwenden, wie stark können die Ergebnisse dann verbessert werden?

Nun, da wir wissen, dass sich mein ganzzahliger Kernel niemals verschlechtert und wir wissen, dass Lanczos eine Schärfe aufweist, diese sich jedoch verschlechtert, ist es logisch, dass wir einen Ort zwischen zwei Koeffizientensätzen finden können, an dem die Verschlechterung beginnt. Also habe ich ein Programm geschrieben, das mir geholfen hat, diesen bestimmten Punkt zu finden, und hier ist der Kernel, den ich gefunden habe:

 MyFloatKernel6[] = {0.027617, -0.130815, 0.603198, 0.603198, -0.130815, 0.027617}; 

Dieser Kernel benötigt 272 Iterationen, um zu konvergieren, aber er ist unendlich stabil und sieht viel schärfer aus als mein ganzzahliger Filter:


Tatsächlich ist es vom Original kaum zu unterscheiden:


Fast ... aber nicht ganz. Wenn Sie genau hinschauen, können Sie in kontrastreichen Bereichen immer noch Unschärfe und Dämpfung feststellen. Der einfachste Weg, dies zu sehen, ist im Auge eines orangefarbenen "Dinosauriers" und in hellen Lichtbereichen hinter Bambus.

Das heißt, ein Gleitkommafilter mit 6 Abtastwerten ist definitiv besser, aber nicht perfekt. Kann es noch verbessert werden?

Filterbreite erhöhen

Anfangs wurde ein Filter mit 6 Proben aus den gleichen Gründen wie Brüche mit kleinen ganzen Zahlen ausgewählt: Ich suchte nach einem äußerst effizienten Filter. Aber jetzt forschen wir und sind bereits zu Gleitkommazahlen übergegangen. Warum also nicht einen breiteren Filter in Betracht ziehen?

Durch die Kombination unseres 6-Sample-Integer-Filters mit dem 6-Sample-Lanczos haben wir einen sehr guten Filter erhalten. Warum kombinieren wir es nicht mit den Lanczos mit 8 Stichproben?

Der Lanczos mit 8 Stichproben sieht folgendermaßen aus:

 Lanczos8[] = {-0.01263, 0.05976, -0.16601, 0.61888, 0.61888, -0.16601, 0.05976, -0.01263}; 

Wie der Lanczos mit 6 Stichproben ist er sehr instabil und kollabiert nach 178 Iterationen:


Wenn wir nach einem besseren Filter zwischen einem 6-Sample-Integer-Filter und einem 8-Sample-Lanczos suchen, finden wir diesen bemerkenswerten 8-Sample-Filter:

 MyFloatKernel8[] = {-0.010547, 0.052344, -0.156641, 0.614844, 0.614844, -0.156641, 0.052344, -0.010547}; 

Als unendlich stabiler Filter arbeitet er erstaunlich gut. Es konvergiert nach 202 Iterationen (Konvergenz ist schneller als meine beiden Filter) und ähnelt so sehr dem Original, dass es schwierig ist zu erkennen, welcher von ihnen welcher ist:


Hier ist noch einmal das Original als Referenz:


Im Vergleich zu meinem ursprünglichen Ganzzahlfilter gibt es eine signifikante Verbesserung.

Wie funktionieren unendlich stabile Filter?

Ich wollte diesen Beitrag so etwas beenden:

"Ich weiß nicht genau, wie das alles funktioniert. In anderen Bereichen, in denen ich mit den unendlich anwendbaren Transformationen gearbeitet habe, weiß ich, wie Grenzmathematik durchgeführt und nützliche Analysen erstellt werden. Zunächst geht es um die Analyse der Grenzfläche für Unterteilungsflächen, bei der die Eigenwerte und Eigenvektoren der Unterteilungsmatrix berechnet werden, wonach die Grenze bis zu einem unendlichen Grad genommen werden kann. Ich habe jedoch keine Erfahrung mit der Durchführung einer solchen Analyse für Halfpel-Filter, da diese Pixel nicht an Ort und Stelle belassen, sondern seitwärts verschieben. "

Das war mein Plan. Aber zwischen dem Schreiben des ersten und zweiten Teils schickte ich die Ergebnisse des verbesserten Filters an Fabien Giessen und Charles Bloom . Es ist nicht überraschend, dass sie die Mathematik kannten, die für die analytische Untersuchung dieses Problems erforderlich ist. Es stellte sich heraus, dass es für Filter tatsächlich eine Analyse von Eigenwerten und Vektoren gibt, aber das funktioniert nicht ganz so.

Aber es kann leicht ausgeführt werden - tatsächlich ist es als trivialer Ein-Schritt-Prozess in CAM-Programme integriert, und wir können die Eigenwerte für Filter wirklich betrachten. Er gibt uns keine vollständigen Antworten, da hier die Tatsache des Rundens (oder Abschneidens) auf 8 Bit (oder 10 Bit oder 12 Bit) nach jeder Filterung wichtig ist, da das Abschneiden die Methode der Fehlerakkumulation im Vergleich zur unendlich genauen Algebra beeinflusst.

Da dies überhaupt nicht mein Fachgebiet ist, kann ich mir leider nicht einmal einen genauen Überblick über diese Analyse verschaffen. Ich fragte Fabien und Charles, ob sie Posts mit den guten Informationen schreiben könnten, die sie mir per E-Mail geschickt hatten (beide haben technische Blogs - das Ryg-Blog und Cbloom Rants ), und Fabien schrieb eine ausgezeichnete Artikelserie über die mathematischen Grundlagen stabiler Filter . Wenn Sie an der theoretischen Struktur meiner beiden Beiträge interessiert sind, empfehle ich Ihnen, diese Reihe zu lesen!