Motion Compensation

Algorithmen zur Videokompression

Unter dem Oberbegriff Motion Compensation (dt. etwa: „Bewegungsausgleich“) oder Motion Prediction (deutsch: „Bewegungsvorhersage“) wird eine Reihe von Algorithmen zusammengefasst, die hauptsächlich bei der Videokompression eingesetzt werden. Die temporären Relationen zwischen benachbarten Einzelbildern ("frames") werden ausgenutzt, um die Gesamtmenge der zu komprimierenden Daten zu minimieren. Vereinfacht ausgedrückt heißt dies, dass Bildbereiche, die über mehrere Einzelbilder hinweg sehr ähnlich aussehen, nicht in einer weiteren Kopie gespeichert werden, sondern nur die Veränderung ihrer Position gegenüber anderen Bildern.

Visualisierte Bewegungsvektoren der MPEG-Kodierung über einem Standbild aus Elephants Dream. Erkennbar sind die Bewegungen der verschiedenen Plattformen und Körperteile der Figur.

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 Verschiebungsvektor beschrieben. Ab dann muss nur noch der entsprechende Verschiebungsvektor gespeichert werden, welcher deutlich weniger Speicher als die eigentlichen Bilddaten benötigt, was zu einer teils enormen Platzersparnis führt.

Im Endeffekt wird nur das erste Bild der Szene vollständig gespeichert. Für die folgenden Einzelbilder müssen dann lediglich diejenigen Bildteile neu hinterlegt werden, die ursprünglich durch das sich bewegende Objekt verdeckt waren. Allerdings wird dennoch üblicherweise das komplette Bild in regelmäßigen Abständen neu gespeichert, um sowohl die Fehlertoleranz zu erhöhen als auch das Hin- und Herspringen innerhalb einer Videodatei zu ermöglichen.

Funktionsweise

Bearbeiten

Die Motion Compensation basiert auf der Beobachtung, dass ein Großteil der Bewegung in Bildern aus einer Verschiebung eines Bildelements besteht. Die Motion Compensation nimmt jeden Makroblock und vergleicht ihn mit allen möglichen Makroblöcken, die durch horizontale oder vertikale Verschiebungen in kleinen Schritten gebildet werden. Wenn die beste Anpassung gefunden wurde, werden dem Empfänger Anweisungen übermittelt, mit dem Inhalt des Makroblocks zu arbeiten und ihn anschließend mit einem Bewegungsvektor an seine neue Position zu verschieben. Anweisungen an den Empfänger weisen ihn an, den Inhalt einer Anzahl von Blöcken im Speicher zu nehmen und ihn an andere Stellen zu verschieben, an denen eine bestimmte Anzahl von Pixeln horizontal und vertikal verschoben ist.

Der Algorithmus stellt normalerweise fest, dass die Übereinstimmung von Makroblöcken nicht perfekt ist, und codiert daher alle Änderungen und überträgt sie mit dem Bewegungsvektor. Es würde nicht ausreichen, ein Bildelement nur leicht horizontal und vertikal zu bewegen, wenn es sich leicht dreht. Der Unterschied zwischen seinen vorherigen Pixeln und seinen neuen Pixeln wird codiert. In den meisten Fällen ist dies nur ein kleiner Bruchteil der gesamten Pixel. Die meisten bleiben unverändert. Die resultierenden Anweisungen an den Empfänger umfassen das Entfernen von Blöcken aus dem Speicher, das geringfügige Ändern und das anschließende Verschieben von Blöcken. Wenn sie verschoben werden, überlagern Teile andere Blöcke, und Teile werden von anderen Blöcken abgedeckt. Diese Informationen müssen ebenfalls übermittelt werden. Löcher im Bild werden erstellt. Sie müssen gefüllt werden. Die verschiedenen Teile des Bildes können sich um unterschiedliche Beträge in verschiedene Richtungen bewegen.

Die Motion Compensation macht den Codierer viel komplexer als den Decodierer, was akzeptabel ist, da es viel mehr Decodierungsstellen als Codierungsstellen gibt.[1]

Block Motion Compensation

Bearbeiten

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

Ein Pixelblock kann auch als Matrix interpretiert werden. Sei nun Bx,y ∈ Nn×n ein Pixelblock des aktuellen Einzelbilds mit der horizontalen Position n ⋅ x und der vertikalen Position n ⋅ y. Die Matrixelemente bi,j seien die Pixel an der Position (n ⋅ x + i, n ⋅ y + j), pi,j entsprechend die Pixel im vorherigen Bild. Um nun den Verschiebungsvektor zu finden, vergleicht man Bx,y mit einem um den Vektor (u, v) verschobenen Bildausschnitt im vorherigen Bild. Ein Indikator für den Unterschied du,v zwischen Pixelblock und Bildausschnitt ist die Summe der quadrierten Differenzen (engl. "Sum of Squared Differences" bzw. SSD):[2]

 

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

Eine Verbesserung des BMC-Algorithmus kann erreicht werden, indem neben dem vorherigen auch das nachfolgende Einzelbild zur Bestimmung des Verschiebungsvektors herangezogen wird. Mittlerweile wurden auf Basis der "Block Motion Compensation" weitere Algorithmen entwickelt, die zum Teil deutlich bessere Ergebnisse liefern, beispielsweise Variable Block-Size Motion Compensation und Overlapped Block Motion Compensation.

Quarter Pixel Motion Compensation

Bearbeiten

Die Quarter Pixel Motion Compensation (oft nur kurz Qpel, Quarter pixel oder Q-Pel genannt) arbeitet 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)

Bearbeiten

Die Global Motion Compensation (GMC) wird bei der digitalen Videokompression verwendet, vor allem MPEG-4 (z. B. Xvid). Im Gegensatz zur blockbasierten Motion Compensation wird die Bewegung zwischen zwei Einzelbildern 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 erkauft wird. GMC ist ein relativ neues Verfahren, das noch nicht von allen Abspielgeräten unterstützt wird.

Siehe auch

Bearbeiten

Einzelnachweise

Bearbeiten
  1. ScienceDirect: Motion Compensation
  2. Bernd Girod, Stanford University: Motion Compensated Coding