Nachdem ich die Erstellung der Webarchitektur für unseren neuen Webcomic
Meow the Infinite abgeschlossen hatte , entschied ich, dass es Zeit war, einige überfällige technische Artikel zu schreiben. Dieser Artikel konzentriert sich auf einen Filter, den ich vor einigen Jahren entwickelt habe. Es wurde noch nie im Bereich der Videokomprimierung diskutiert, obwohl es mir scheint, dass es sich lohnt, dies zu tun.
2011 habe ich den „Halbpel-Filter“ entwickelt. Dies ist eine spezielle Art von Filter, der ein eingehendes Bild aufnimmt und am überzeugendsten anzeigt, wie das Bild aussehen würde, wenn es
genau um ein halbes Pixel verschoben würde.
Sie fragen sich wahrscheinlich, warum ein solcher Filter überhaupt benötigt wird. Tatsächlich sind sie in modernen Video-Codecs weit verbreitet. Videocodecs verwenden ähnliche Filter, um Fragmente früherer Frames zu nehmen und in nachfolgenden Frames zu verwenden. Ältere Codecs haben Frame-Daten jeweils nur um ein ganzes Pixel verschoben, aber die neuen Codecs gingen noch weiter und ermöglichen eine Verschiebung von einem halben oder sogar einem Viertel Pixel, um kleine Bewegungen besser übertragen zu können.
Bei der Analyse des Verhaltens von Bewegungskompensationsalgorithmen in herkömmlichen Halfpel-Filtern stellte
Jeff Roberts fest, dass sie sich bei wiederholter Anwendung auf sequentielle Frames schnell verschlechtern und andere Teile des Videokompressors dazu zwingen, mehr Daten als erforderlich zur Korrektur von Artefakten zu verwenden. Wenn Sie diese Korrekturen deaktivieren und die "rohen" Ergebnisse des Halfpel-Filters anzeigen, ist dies das Originalbild:
verwandelt sich in diese:
Nur eine Sekunde später das Video. Wie es sollte, wird es zur Seite verschoben, da jedes Bild das Bild um ein halbes Pixel verschoben hat. Das Ergebnis sieht jedoch nicht wie eine verschobene Version des Originalbilds aus, sondern ist stark verzerrt.
Während des "Ein-Sekunden-Videos" wird der Filter tatsächlich viele Male angewendet - 60, wenn das Video mit einer Frequenz von 60 Bildern pro Sekunde abgespielt wird. Idealerweise benötigen wir jedoch Filter, die gegen solche Verzerrungen beständig sind. Wenn wir sie hätten, wären Videos mit reibungslosem Bildlauf nicht mit so vielen Artefaktkorrekturen codiert worden, was sie weniger oder besser oder beides gemacht hätte.
Wenn Sie mit dem Bereich der Videokomprimierung vertraut sind, fragen Sie sich möglicherweise, warum wir den Halfpel-Filter überhaupt mehrmals verwenden müssen. Wenn Sie den Halfpel-Filter am Ende zweimal anwenden, verschieben wir bereits ein ganzes Pixel. Warum also nicht einfach die Daten von
zwei Frames zurück verwenden und sie einfach übernehmen?
Die Antwort ist nicht so einfach. Erstens, je mehr Daten wir zum Codieren der Daten benötigen, desto weniger Komprimierung erhalten wir. Wenn wir mit dem Codieren beginnen, ohne dass zu viele Daten erforderlich sind, z. B. "Aus welchem Frame sollen Daten aufgenommen werden", wird das Video daher nicht sehr gut komprimiert.
Dies ist jedoch nicht das Wichtigste. Das Hauptproblem ist, dass wir Informationen aus früheren Frames
speichern müssen , wenn wir sie übernehmen
müssen . Um die vorherigen zwei Frames anstelle von einem beizubehalten, müssen Sie davon ausgehen, dass Sie doppelt so viel Speicher haben. Für moderne CPUs ist dies kein besonderes Problem, sie haben viel Speicher und eine solche Kleinigkeit stört sie nicht. Dies ist jedoch ein
Problem für Sie, wenn Sie ein schnelles, tragbares und weit verbreitetes Videoformat erstellen möchten, das auf Geräten mit wenig Speicher (Mobiltelefone, integrierte Elektronik usw.) funktionieren sollte.
Wir wollen wirklich nicht mehrere Frames speichern, um die Bewegung zu kompensieren, nur um keinen Halfpel-Filter zu verwenden. Daher wurde ich angewiesen, herauszufinden, was genau hier passiert, und herauszufinden, ob ich einen Filter erstellen kann, der solche Probleme nicht hat.
Vorher hatte ich noch nie mit Filtern gearbeitet und hatte keine Ahnung, wie sie normalerweise entwickelt werden. Seltsamerweise stellte sich heraus, dass es zu meinen Gunsten war, weil ich dieses Problem ohne Vorurteile betrachten musste.
Die Grundlagen
Mir wurde schnell klar, dass die beliebtesten Halfpel-Filter eine ähnliche Struktur haben: Für jedes Pixel im Ausgabebild werden 2 bis 8 Pixel des Eingabebildes aufgenommen, die abgetastet und mit bestimmten Koeffizienten gemischt werden. Unterschiedliche Filter unterscheiden sich nur in der Anzahl der abgetasteten Quellpixel (im Fachjargon der Filterentwickler werden sie häufig als Tap bezeichnet) und den Pixelmischungsfaktoren. Diese Koeffizienten werden oft als "Filterkernel" bezeichnet. Dies ist alles, was zur vollständigen Beschreibung des Filters erforderlich ist.
Wenn Sie mit dem Abtasten oder erneuten Abtasten von Bildern (z. B. Skalieren von Bildern) vertraut sind, sollte dies für Sie klar sein. Im Wesentlichen machen Filter dasselbe. Da die Videokomprimierung ein weites Feld ist, in dem verschiedene Studien durchgeführt werden, gibt es offensichtlich viele
andere Möglichkeiten, um Bewegungen zu kompensieren, als die einfache Filterung. Gängige Codecs verwenden jedoch normalerweise Bewegungskompensationsverfahren mit Halbpel-Filtern, die im Wesentlichen mit Bildskalierungsfiltern identisch sind: Sie nehmen nur die Originalpixel, multiplizieren sie mit einigen Gewichten, addieren sie und erhalten die Ausgabepixel.
Das Bedürfnis nach "Schärfe"
Wir müssen das Bild also um ein halbes Pixel verschieben. Wenn Sie ein Grafikprogrammierer sind, aber mit dem Filtern nicht besonders vertraut sind, denken Sie vielleicht: "Ich habe auch ein Problem, verwenden Sie einfach einen bilinearen Filter." Dies ist ein Standardprozess bei der Arbeit mit Grafiken, wenn wir wie hier Zwischenwerte zwischen zwei eingehenden Datenelementen berechnen müssen.
Ein bilinearer Filter zum Verschieben von genau einem halben Pixel kann leicht durch den folgenden Filterkern beschrieben werden:
Dies wird funktionieren, aber nicht ohne Probleme. Wenn Ihr Ziel qualitativ hochwertige Bilder sind und bei der Videokomprimierung genau das das Ziel ist, ist ein bilinearer Filter nicht die beste Lösung, da er dem Ergebnis mehr Unschärfe verleiht als erforderlich. Es ist nicht so
viel , aber
mehr als andere Filter erstellen.
Um dies klar zu zeigen, ist hier ein ungefähres Bild des Walrossauges vom Originalbild nach einmaliger Anwendung der gängigsten Filter:
Links ist das Original, rechts ist die bilineare Filterung. Dazwischen befinden sich die am häufigsten verwendeten Halfpel-Filter von Video-Codecs. Wenn Sie genau hinschauen, können Sie feststellen, dass fast alle Bilder ähnlich aussehen, mit
Ausnahme eines bilinearen, das etwas verschwommener ist. Obwohl es nicht viel Unschärfe gibt, reicht es aus, wenn Ihr Hauptziel die Bildqualität ist, einen anderen Filter einem bilinearen Filter vorzuziehen.
Wie können andere Filter die Schärfe „beibehalten“ und Unschärfen vermeiden? Erinnern wir uns, wie der Kern der bilinearen Unschärfe aussieht:
BilinearKernel[] = {1.0/2.0, 1.0/2.0};
Es ist sehr einfach. Um das Bild um ein halbes Pixel zu verschieben, nehmen wir ein Pixel und mischen es zu 50% mit seinem Nachbarn. Das ist alles. Man kann sich vorstellen, wie dies das Bild „verwischt“, denn an den Stellen, an denen das hellweiße Pixel neben dem dunklen Schwarz liegt, werden diese beiden Pixel während der bilinearen Filterung gemittelt, wodurch ein graues Pixel entsteht, das den Rand „weicher“ macht. Dies geschieht mit jedem Pixel, also buchstäblich mit jedem Bereich, in dem es einen deutlichen Unterschied in Farbe oder Helligkeit gibt. geglättet.
Aus diesem Grund wird in hochwertigen Codecs die bilineare Filterung nicht zur Bewegungskompensation verwendet (obwohl sie in anderen Fällen verwendet werden kann). Stattdessen werden Filter verwendet, die die Schärfe beibehalten, z.
Wie Sie sehen können, berücksichtigen diese Filter bei der bilinearen Filterung nur zwei Pixel sechs (h.264) oder sogar acht (HEVC) Pixel. Außerdem berechnen sie nicht nur die üblichen gewichteten Durchschnittswerte dieser Pixel, sondern verwenden für einige Pixel
negative Gewichte, um diese Pixel von anderen Werten zu
subtrahieren .
Warum machen sie das?
Es ist eigentlich nicht schwer zu verstehen: Wenn sowohl positive als auch negative Werte verwendet werden und auch ein breiteres „Fenster“ berücksichtigt wird, kann der Filter den
Unterschied zwischen benachbarten Pixeln berücksichtigen und die Schärfe der beiden nächsten Pixel relativ zu ihren entferntesten Nachbarn simulieren. Auf diese Weise können Sie die Schärfe des Bildergebnisses an den Stellen beibehalten, an denen sich die Pixel erheblich von ihren Nachbarn unterscheiden, während die Mittelung weiterhin verwendet wird, um glaubwürdige Werte für "Halbpixel" -Verschiebungen zu erstellen, die notwendigerweise die Kombination von Pixeln aus dem eingehenden Bild widerspiegeln müssen.
Instabile Filterung
Ist das Problem also gelöst? Ja, das ist möglich, aber wenn Sie nur einen halben Pixelversatz benötigen. Diese "Schärfungs" -Filter (und ich verwende diesen Begriff hier absichtlich) bewirken jedoch tatsächlich etwas Gefährliches, das im
Wesentlichen dem der bilinearen Filterung
ähnelt . Sie wissen einfach besser, wie man es versteckt.
Wenn die bilineare Filterung
die Bildschärfe
verringert ,
erhöhen diese Standardfilter diese, wie beim Schärfen in einigen Grafikprogrammen. Das Schärfen ist sehr gering. Wenn wir den Filter also nur einmal ausführen, werden wir dies nicht bemerken. Wenn die Filterung jedoch mehrmals durchgeführt wird, kann dies sehr auffällig werden.
Und da diese Schärfung prozedural ist und von der Differenz zwischen den Pixeln abhängt, wird leider
eine Rückkopplungsschleife erstellt , die denselben Rand immer wieder schärft, bis das Bild zerstört wird. Sie können dies anhand konkreter Beispiele zeigen.
Oben - das Originalbild unten - mit bilinearer Filterung über 60 Frames:
Wie zu erwarten ist, verringert das Verwischen die Bildschärfe einfach weiter, bis es ziemlich unscharf wird. Jetzt befindet sich das Original oben und der h.264-Codec-Halfpel-Filter, der unten für 60 Frames ausgeführt wird:
Sehen Sie all diesen Müll? Der Filter tat dasselbe wie der "Unschärfe" -Effekt der bilinearen Filterung, aber
umgekehrt - er "erhöhte die Bildschärfe", so dass alle Teile, in denen die Details waren, in stark verzerrte Hell / Dunkel-Muster umgewandelt wurden.
Verhält sich der HEVC-Codec mit 8 Pixeln besser? Nun, es macht definitiv besser als h.264:
Wenn wir jedoch die Zeit von 60 Bildern (1 Sekunde) auf 120 Bilder (2 Sekunden) erhöhen, werden wir immer noch feststellen, dass es eine Rückmeldung gibt und das Bild zerstört wird:
Für diejenigen, die die Signalverarbeitung mögen, füge ich als Referenz einen Fenster-Sinc-Filter (Lanczos-Filter genannt) hinzu:
Ich werde in diesem Artikel nicht erklären, warum sich jemand für "windowed sinc" interessiert, aber es genügt zu sagen, dass dieser Filter aus theoretischen Gründen beliebt ist. Schauen Sie also, wie er bei der Verarbeitung von 60 Frames (1 Sekunde) aussieht:
und bei der Verarbeitung von 120 Bildern (2 Sekunden):
Besser als h.264 und ungefähr das gleiche wie HEVC.
Stabile Filterung
Wie können wir bessere Ergebnisse erzielen als h.264, HEVC und windowed sinc? Und wie viel besser können sie sein?
Ich
würde erwarten, ähnliche Fragen in der Literatur zur Videokomprimierung zu sehen, und sie sollten den Komprimierungsspezialisten bekannt sein, aber tatsächlich (zumindest für 2011) habe ich niemanden gefunden, der zumindest angegeben hat, dass dies ein Problem ist. Also musste ich alleine eine Lösung finden.
Glücklicherweise ist die Erklärung des Problems sehr einfach: Erstellen Sie einen Filter, der so oft wie möglich angewendet werden kann, damit das Bild ungefähr so aussieht wie am Anfang.
Ich nenne diese Definition "stabile Filterung", weil sie meiner Meinung nach als Filtereigenschaft betrachtet werden kann. Ein Filter ist „stabil“, wenn er nicht in seine Rückkopplungsschleife fällt, dh er kann wiederholt angewendet werden, ohne Artefakte zu erzeugen. Ein Filter ist "instabil", wenn er Artefakte erzeugt, die durch wiederholte Verwendung verstärkt werden und schließlich das Bild zerstören.
Ich wiederhole, ich verstehe nicht, warum dieses Thema in der Literatur zu Videocodecs oder Bildverarbeitung nicht berücksichtigt wird. Vielleicht verwendet es eine andere Terminologie, aber ich habe es nicht getroffen. Das Konzept des "Feedbacks" ist im Bereich der Arbeit mit Klang gut etabliert. aber kein wichtiges Thema in der Bildverarbeitung. Vielleicht, weil Filter normalerweise nur einmal angewendet werden sollten?
Wenn ich ein Spezialist auf diesem Gebiet wäre, hätte ich höchstwahrscheinlich eine Meinung zu diesem Thema, und vielleicht würde ich sogar jene Ecken der Fachliteratur kennen, in denen es bereits Lösungen für dieses Problem gibt, die nur wenigen bekannt sind. Wie ich zu Beginn des Artikels sagte, konnte ich noch nie zuvor Filter erstellen. Deshalb habe ich nur in bekannten Artikeln gesucht (obwohl es erwähnenswert ist, dass es in der Literatur mindestens eine bekannte Person gibt, die so etwas auch noch nicht gehört hat )
Am Morgen sagten sie mir, dass wir diesen Filter brauchen, und ich habe den ganzen Tag versucht, ihn zu erstellen. Mein Ansatz war einfach: Ich habe ein Programm erstellt, das den Filter hunderte Male ausgeführt und am Ende ein Bild erstellt hat, damit ich das Ergebnis langer Läufe sehen kann. Dann habe ich mit verschiedenen Filterkoeffizienten experimentiert und die Ergebnisse beobachtet. Es war buchstäblich ein richtungsweisender Versuch und Irrtum.
Ungefähr eine Stunde später habe ich die besten Filterkoeffizienten ausgewählt, die für diese Aufgabe geeignet sind (aber sie hatten einen Fehler, den ich im zweiten Teil des Artikels diskutieren werde):
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};
Dieser Kern steht kurz vor dem Schärfen und Verwischen. Da das Schärfen immer zu Rückkopplungen führt, die lebendige und offensichtliche Artefakte erzeugen, bevorzugt dieser Filterkern ein wenig Unschärfe, damit das Bild nur ein wenig „langweiliger“ aussieht.
So sieht es nach 60 Frames aus. Als Referenz habe ich alle Filter in dieser Reihenfolge gezeigt: das Originalbild (ohne Filterung), mein Filter, bilinear, Lanczos, h.264, HEVC:
Wie Sie sehen können, liefert mein Filter etwas mehr unscharfe Ergebnisse als Schärfungsfilter, weist jedoch nach 60 Bildern keine inakzeptablen Schärfeartefakte auf. Möglicherweise bevorzugen Sie jedoch Unschärfeartefakte gegenüber Schärfungsartefakten, sodass Sie zwischen dem besten Schärfefilter (Lanczos) und meinem Filter wählen können. Wenn wir jedoch die Anzahl auf 120 Frames erhöhen, ist mein Filter außer Konkurrenz:
Nach 300 Bildern werden alle Filter außer meinen wie ein schlechter Witz:
Nach 600 Bildern wird der Witz noch grausamer:
Sie müssen nicht einmal sagen, was nach 900 Bildern passiert:
Wie stabil ist es?
In diesem Stadium wird sich natürlich fragen: Ist mein Filter
wirklich stabil oder ist es nur eine sehr langsame Unschärfe, viel langsamer als die bilineare Filterung? Vielleicht verwischt mein Filter nach Tausenden von Wiederholungen das Bild
allmählich ?
Überraschenderweise scheint die Antwort negativ zu sein. Obwohl im Verlauf von etwa hundert der ersten Überlagerungen ein wenig Unschärfe hinzugefügt wird, sieht es so aus, als würde der Filter zu einer stabilen Darstellung des Bildes
konvergieren , die sich dann
nie verschlechtert. Hier ist ein weiteres vergrößertes Bild eines Walrossauges:
Von links nach rechts: Das Originalbild wurde von meinem Filter 60-mal, 120-mal, 300-mal, 600-mal und 900-mal angewendet. Wie Sie sehen können, konvergiert die Unschärfe zu einem stabilen Zustand, der sich auch nach Hunderten von Filterüberlagerungen nicht mehr verschlechtert. Vergleichen Sie dies im Gegensatz dazu mit der Fenstersynchronisierung für die gleiche Anzahl von Samples (Tippen) und sehen Sie, wie schlecht (und schnell!) Die Artefakte das Feedback bilden und ein nutzloses Ergebnis erzeugen:
Mein Filter scheint sehr stabil zu sein und erzielt im Vergleich zu allen Filtern, die ich gesehen habe, nach wiederholtem Gebrauch die besten Ergebnisse. Es scheint, dass es eine bestimmte „asymptotische“ Eigenschaft hat, bei der die Daten schnell zu einem (begrenzten) geglätteten Bild konvergieren. Dieses geglättete Bild wird dann gespeichert und führt keine unbegrenzte Verschlechterung durch, um den Müll zu vervollständigen.
Ich habe sogar
millionenfach versucht, den Filter anzuwenden, und es scheint, dass er sich nach den ersten paar hundert Überlagerungen nicht weiter verschlechtert. Ohne eine bessere mathematische Analyse (und ich habe noch keine mathematische Lösung gefunden, die dies genau beweisen kann, aber ich weiß sicher, dass es irgendwo ist) kann ich nicht mit Sicherheit sagen, dass irgendwo nach Milliarden oder Billionen von Überlagerungen dies der Fall ist -es wird nicht brechen. Innerhalb vernünftiger Tests konnte ich keine weitere Verschlechterung feststellen.
Ist es der beste stabile Halfpel-Filter für sechs Zapfstellen?
In diesem Stadium wäre es logisch, die Frage zu stellen: Ist dies wirklich das Beste, was gefunden werden kann? Die Intuition sagt uns, dass dies nicht der Fall ist, da ich absolut keine Kenntnisse über die Entwicklung von Filtern hatte und fast nicht in die Literatur geschaut habe. Ich habe diesen Filter in nur einer Stunde aufgenommen. Zumindest kann davon
ausgegangen werden
, dass ich nach einer so kurzen Studie keinen endgültigen, besten, alles erobernden, großartigen Filter gefunden hätte.
Ist diese Annahme wahr? Und wenn ja,
was ist der endgültig beste Filter? Ich werde dies im zweiten Teil des Artikels genauer diskutieren.