Motion Prediction

Unter dem Oberbegriff Motion Compensation oder Motion Prediction (wortwörtlich: Bewegungsvorhersage) wird eine Reihe von Algorithmen zusammengefasst, die hauptsächlich unterstützend bei der Videokompression eingesetzt werden. Die temporären Relationen zwischen benachbarten Frames werden ausgenutzt, um die Gesamtmenge der zu komprimierenden Daten zu minimieren. Vereinfacht heißt dies, dass Bildbereiche, die über mehrere Einzelbilder hinweg sehr ähnlich aussehen, nicht ein weiteres Mal komplett gespeichert werden müssen, sondern nur die Veränderung ihrer Position gegenüber anderen Bildern.

Einfache Kompressionsverfahren reduzieren nur unbewegte Bildanteile, beispielsweise den Hintergrund vor dem ein Nachrichtensprecher sitzt, oder einfache Kamerabewegungen wie Zoom, Horizontal- oder Vertikalverschiebung. Aktuelle Videocodecs verwenden jedoch komplexere Algorithmen, welche auch bewegte Bildanteile entsprechend komprimieren können. Hierbei wird die Bewegungsrichtung eines Objektes vorhergesagt und durch einen Bewegungs- oder Verschiebevektor beschrieben. Ab dann muss nur noch der entsprechende Verschiebevektor gespeichert werden, welcher deutlich wenig Speicher als die eigentlichen Bilddaten benötigt, was zu einer teils enormen Platzersparnis führt.

Im Endeffekt wird das erste Bild der Szene anfangs nur einmal gespeichert; Für die folgenden Frames müssen dann lediglich diejenigen Bildteile neu hinterlegt werden, die ursprünglich durch das sich bewegende Objekt verdeckt waren. Allerdings wird üblicherweise das komplette Bild in regelmäßigen Abständen neu gespeichert um sowohl die Fehlertoleranz zu erhöhen, als auch das hin und her Springen (nicht Spulen) innerhalb eines Videos zu ermöglichen.

Block Motion Compensation

Die Block Motion Compensation (BMC) wird unter Anderem im MPEG-2 Standard verwendet. Bei diesem Verfahren wird jeder Frame in n mal n große Pixelblöcke unterteilt, welche mit dem vorherigen Frame verglichen werden. Findet sich dort ein ähnlicher Bildausschnitt, so wird nur der Verschiebevektor gespeichert um den sich dieser Ausschnitt bewegt.

Ein Pixelblock kann auch als Matrix interpretiert werden. Sei nun B_x,y ∈ N^n×n ein Pixelblock des aktuellen Frames mit dem horizontalen Offset n ⋅ x und dem vertikalen Offset n ⋅ y. Die Matrixelemente b_i,j seien die Pixel an der Position (n ⋅ x + i, n ⋅ y + j), p_i,j entsprechend die Pixel im vorherigen Frame. Um nun den Verschiebevektor zu finden vergleicht man B_x,y mit einem um den Vektor (u, v) verschobenen Bildausschnitt im vorherigen Frame. Ein Indikator für den Unterschied d_u,v zwischen Pixelblock und Bildausschnitt ist die Summe der quadrierten Differenzen (Sum of Squared Differences, SSD):

$d_{u,v} = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} (b_{i,j} - p_{i,j})^2$

Andere Indikatoren wären beispielsweise die Summe der absoluten Differenzen (Sum of Absolute Differences, SAD) oder die Kreuzkorrelation. Man berechnet d_u,v für alle Verschiebungen innerhalb einer festgelegten Umgebung von B_x,y und wählt den Vektor (u, v) als Verschiebevektor, bei dem d_u,v ≤ d_max und das Minimum aller Unterschiede ist. Setzt man d_max = 0, so ist der ursprüngliche Datenstrom vollständig rekonstruierbar, bei einem d_max > 0 komprimiert die Motion Compensation nicht mehr verlustfrei.

Eine Verbesserung des BMC-Algorithmus kann erreicht werden, indem neben dem vorherigen auch der nachfolgende Frame zur Bestimmung des Verschiebevektors herangezogen wird. Mittlerweile wurden auf Basis der Block Motion Kompensation weitere Algorithmen zur Motion Prediction entwickelt, die zum Teil deutlich bessere Ergebnisse liefern. Zum Einen sei hier die Variable Block-Size Motion Compensation und zum Anderen die Overlapped Block Motion Compensation genannt.

Quarter Pixel Motion Compensation

Quarter Pixel Motion Compensation (oft nur kurz Qpel, Quarter pixel oder Q-Pel genannt) ist bei digitaler Videokodierung Motion Compensation mit Bewegungsvektoren von der Genauigkeit eines Viertel Bildpunktes. Qpel dient einer besseren Vorhersage von Bewegungen und produziert somit bessere Bildqualität bzw. geringe Dateigrößen.

Quarter Pixel Motion Compensation ist Teil des MPEG-4-ASP- (optional) und AVC-Standards (Pflicht) und wird häufig in Verbindung mit Global Motion Compensation (nur ASP) verwendet.

Global Motion Compensation (GMC)

Die Global Motion Compensation (GMC) wird bei der digitalen Videokodierung verwendet, vor allem MPEG-4 (z. B. Xvid). Im Gegensatz zur blockbasierten Motion Compensation wird die Bewegung zwischen zwei Frames global mit einer affinen Abbildung beschrieben. Dadurch können auch Bewegungen, die über das bloße Verschieben hinausgehen, wie z.B. Drehungen oder Verzerrungen beschrieben werden. Das Ziel von GMC ist eine bessere Kodierungsqualität bei schnellen Bewegungsszenen, wie z. B. Explosionen. Die Verwendung von GMC führt zu einer besseren Bildqualität bzw. geringeren Dateigröße, was allerdings mit einem höheren Kodierungsaufwand einhergeht. GMC ist ein junges Verfahren, das noch nicht von allen Abspielgeräten unterstützt wird und somit zu Problemen führen kann.