EINE STUFE EINER KETTE — WAS ANKOMMT, WAS HERAUSGEHT, WAS DANACH BRICHT
Wo diese Stufe in der Encoding-Pipeline sitzt
Ein Video-Encoder ist kein einzelner Algorithmus, sondern acht Stufen in fester Reihenfolge — und die Reihenfolge ist nicht beliebig: Jede Stufe existiert, weil die vorherige ihre Arbeit erst möglich gemacht hat. Dieses Werkzeug modelliert eine davon. Die Kette unten verlinkt die anderen sieben.
Bewegungsschätzungs-Simulator — findet, wohin sich jeder Block bewegt hat, und codiert dann die Differenz statt des Blocks
- Was ankommt
- Ein P- oder B-Frame zusammen mit seinen Referenzbildern.
- Was herausgeht
- Ein Bewegungsvektor pro Block und ein Residuum — genau das, was die Vorhersage falsch getroffen hat.
- Was die nächste Stufe voraussetzt
- Die Quantisierung erhält ein Residuum, kein Bild. Residuen liegen fast überall nahe null, und genau deshalb ist ihre Quantisierung günstig.
- Was hier schiefgeht
- Eine schlechte Übereinstimmung erzeugt kein falsches Bild, sondern ein teures. Das Residuum trägt mehr Energie, und dieselbe Quantisierereinstellung gibt dafür mehr Bits aus. Diese Stufe verändert die Größe der Ausgabe, nicht deren Einstellungen.
Aufgabe vollständig gelöst
-
Das aus 225 Positionen pro Block abgeleitete Suchfenster 5 Schritte
Eine vollständige Bewegungssuche prüft 225 Positionen pro Block, insgesamt 14 400. Ermitteln Sie daraus das Suchfenster und was eine schnelle Suche brings.
-
225 ist eine perfekte Quadratzahl, und das ist der Hinweis: Die Suche ist ein quadratisches Fenster von 15 mal 15 Kandidaten-Verschiebungen, was −7 bis +7 Pixel in jede Richtung bedeutet.
-
Dividiert man die Gesamtanzahl durch die Anzahl pro Block, erhält man die Anzahl der Blöcke, in die das Einzelbild unterteilt wurde.
-
Der Aufwand wächst mit dem Quadrat des Suchradius, daher wird eine Vergrößerung des Fensters schnell teuer: Radius 7 kostet 225 Positionen, Radius 15 kostet 961, Radius 31 kostet 3969.
-
Dieses quadratische Wachstum ist der Grund, warum es schnelle Suchen gibt. Eine Drei-Schritt-Suche tastet neun Punkte ab, verfeinert und wiederholt — 27 Positionen statt 225.
-
Achtmal günstiger und nicht gleichwertig: Sie steigt zu einem lokalen Minimum ab und kann am echten besten Treffer vorbeilaufen, wenn die Fehlerfläche mehr als eine Senke aufweist.
Antwort
Das Werkzeug meldet 14400 durchsuchte Punkte bei 225,0 pro Block. Darin zeigt sich der zentrale Zielkonflikt der praktischen Videocodierung: Die Vollsuche liefert das Optimum, ihr Aufwand wächst jedoch quadratisch mit dem Suchradius. Deshalb verwendet jeder Encoder ein heuristisches Verfahren und nimmt in Kauf, gelegentlich einen schlechteren Vektor zu wählen. Eine der Folgen erkennst du in der Zeile Restenergie (MSE). Ein ungeeigneter Vektor lässt ein größeres Residuum zurück, für dessen Codierung mehr Daten nötig sind. Die schnelle Bewegungssuche spart nicht einfach nur Rechenzeit. Sie setzt darauf, dass durch ungenaue Vektoren weniger Bits verloren gehen, als sich an anderer Stelle sinnvoll einsetzen lassen.
-
Quellen (2)
- Block matching and motion vectors as the standard uses them: T. Wiegand, G. J. Sullivan, G. Bjontegaard and A. Luthra, "Overview of the H.264/AVC video coding standard." IEEE Transactions on Circuits and Systems for Video Technology 13(7), 560–576, 2003.
- The diamond search this tool implements alongside full search: S. Zhu and K.-K. Ma, "A new diamond search algorithm for fast block-matching motion estimation." IEEE Transactions on Image Processing 9(2), 287–290, 2000.