| Title: | Bewegungsschätzung und -kompensation, Teil 1 | ||
|---|---|---|---|
| Abstract: | Um zeitliche Redundanzen einer Videosequenz für dessen Komprimierung zu nutzen, verwendet MPEG Video die Technik der Bewegungskompensation. In dieser Lerneiheit werden die Begriffe Bewegungsschätzung und -kompensation definiert und das Block-Matching Verfahren vorgestellt. | ||
| Status: | Captions missing, one link dead | Version: | 2005-01-07 |
| History: |
2005-02-21 (Martin Hon): applet-m4_05_29_02 nicht erlaubte attribute entfernt 2005-02-21 (Martin Hon): codebase für applet-m4_05_29_02 hinzugefügt 2005-01-07 (Robert Fuchs): Captions missing, one link dead; added applet-m4_05_29_02. 2004-09-22 (Thomas Migl): Text Applet "Bewegungskompensation" implementiert, 2004-09-16 (Thomas Migl): alle pdas hionzugefügt 2004-09-13 (Thomas Migl): Einführenden Text für Applet geschrieben, 2004-08-16 (Robert Fuchs): Checked, fixed and exported for Review #2. 2004-07-29 (Robert Fuchs): Fixed HTMLAuth2 gremlins. 2004-07-29 (Thomas Migl): Inhalte zugefügt, Bilder (PC final) importiert. 2004-07-26 (Robert Fuchs): Manual import into the Greybox. 2004-03-12 (Robert Fuchs): Closed for 50% Content Deadline import in Scholion. 2004-03-12 (Robert Fuchs): Fixed bugs in content tagging; image tagged as "sHeader". 2004-03-10 (Thomas Migl): LOD1, abstract added 2004-03-05 (Robert Fuchs): Added links. 2004-03-04 (Robert Fuchs): Imported and tagged content from "m4-LU34-Bewegungsschätzung1-fertig.doc" 2004-02-25 (HTMLContentTools): Created skeleton page. |
||
| Author 1: | Thomas Migl | E-Mail: | migl@ims.tuwien.ac.at |
|---|---|---|---|
| Author 2: | Chrisitian Ritzinger | E-Mail: | (empty) |
| Author 3: | (empty) | E-Mail: | (empty) |
| Author 4: | (empty) | E-Mail: | (empty) |
| Author 5: | (empty) | E-Mail: | (empty) |
| Organization: | Technische Universität Wien; Institut für Softwaretechnik und Interaktive Systeme; Arbeitsgruppe für Interaktive Multimediale Systeme; http://www.ims.tuwien.ac.at/ | ||
Definition Bewegungsschätzung und -kompensation1Bewegungsschätzung
Bewegungskompensation
2AUTOIm Allgemeinen haben aufeinander folgende Bilder einer Videosequenz einen durch Bewegungen verursachten veränderten Bildinhalt. Diese können Translationsbewegungen, verursacht durch Bewegung der Kamera oder der Motive, Zoomeffekte, etc. sein. stru2002, 152 BewegungsschätzungBewegungsschätzung ist eine Bewegungsanalysetechnik. Man betrachtet in einem Bild einer Videosequenz eine Gruppe von Pixel. Unter der Annahme, dass benachbarte Bildpunkte gleiche bzw. ähnliche Bewegungen ausführen, versucht man die Position dieser Gruppe in einem Referenzbild (=vorhergehendes oder nachfolgendes Bild) wieder zu finden. Als Ergebnis liefert die Bewegungsschätzung einen Bewegungsvektor. BewegungskompensationBewegungskompensation ist eine spezielle Form der Prädiktionstechnik. Man versucht ein Bild innerhalb einer Videosequenz mit Hilfe von Bewegungsanalysen als Prädiktionsbild eines Referenzbildes (vorhergehend oder nachfolgend) darzustellen. Zur Bewegungsanalyse verwendet man die Bewegungsschätzung. Das Prädiktionsbild ergibt sich aus dem Referenzbild und den Bewegungsvektoren. KameraschwenkEin einfaches Beispiel ist ein Kameraschwenk. Es werden alle Objekte im Originalbild gegenüber dem vorhergehenden Bild örtlich versetzt erscheinen. Die örtliche Verschiebung der Objekte kann durch einen zweidimensionalen Vektor, den Bewegungsvektor, beschrieben werden. Für dieses einfache Beispiel ist dieser Vektor für alle Objekte gleich. Es kann jetzt mit Hilfe des Referenzbildes und des Bewegungsvektors ein Prädiktionsbild erstellt werden, dass im Idealfall - Bewegungsvektor beschreibt exakt die Bewegung - mit dem Originalbild ident ist. siko1997 AUTOBei komplexeren Bewegungen werden verschiedene Bildbereiche unterschiedliche Bewegungen erfahren. Hier berechnet die Bewegungsschätzung für jeden Unterbereich einen eigenen Bewegungsvektor. Jeder Vektor gibt dabei die Verschiebung jenes Unterbereiches an, den er repräsentiert. Das Prädiktionsbild ergibt sich wieder aus Referenzbild und den Bewegungsvektoren. Grenzen der Bewegungsschätzung und -kompensation1AUTO
2AUTODie Grenzen der Prädiktionstechnik durch Bewegungskompensation liegen dort, wo unterschiedliche Inhalte zweier aufeinander folgender Bilder sich nicht aus rein translatorischen Bewegungen der Motive ableiten lassen. Änderungen von LichtverhältnissenWandernde Schatten, Sonne wird plötzlich von Himmel verdeckt, Änderung der Beleuchtungsfarbtemperatur, Sonnenreflexe auf bewegter Wasseroberfläche, etc. Bewegung der KameraEs tauchen am Rand neue Bildinhalte auf, etc. Bewegung des MotivsDurch die Bewegung eines Motivs kann die Sicht auf einen Hintergrund freigegeben werden, der im Referenzbild noch nicht zu sehen war. Drehung des MotivsEs wird eine neue Perspektive des Motivs freigegeben. Definition Block-Matching1AUTO
2AUTOBlockmatching ist ein Verfahren zur Bewegungsschätzung. Es fasst Bildpunkte blockweise zu einer Gruppe zusammen. Zur Suche eines Blockes in einem Referenzbild orientiert sich das Blockmatchingverfahren an den Grauwerten der Blockbildpunkte. stru2002, 152 AUTOMPEG-1 und MPEG-2 verwenden das Block-Matching Verfahren. Es werden jeweils die Pixel eines 16x16 - Blockes zu einer Gruppe zusammengefasst. Diese 16x16 Blöcke werden als Makroblöcke bezeichnet. Die Festlegung der Größe des Blockes ist ein Kompromiss.
Arbeitsweise Block-Matching1Abbildung:Arbeitsweise Block-Matching PC
Abbildung:Arbeitsweise Block-Matching PDA_Phone
2Abbildung:Arbeitsweise Block-Matching PC
Für einen 16x16 Makroblock im Originalbild wird im Referenzbild ein Block mit möglichst ähnlichem Bildinhalt gesucht. Anschaulich gesprochen, verschiebt man dazu das Originalbild solange über das Referenzbild, bis die beiden identen Blöcke übereinander liegen. Daraus errechnet man die beiden Koordinaten des gesuchten Bewegungsvektors. Diese Prozedur wird für alle Blöcke des Bildes wiederholt. Abbildung:Arbeitsweise Block-Matching PDA_Phone
Für einen 16x16 Makroblock im Originalbild wird im Referenzbild ein Block mit möglichst ähnlichem Bildinhalt gesucht. Anschaulich gesprochen, verschiebt man dazu das Originalbild solange über das Referenzbild, bis die beiden identen Blöcke übereinander liegen. Daraus errechnet man die beiden Koordinaten des gesuchten Bewegungsvektors. Diese Prozedur wird für alle Blöcke des Bildes wiederholt. AUTOAls Ergebnis hat man eine Repräsentation des Originalbildes, dessen Makroblöcke nur durch die Koordinatenwerte der Bewegungsvektoren beschrieben werden. Diese Darstellung ist gegenüber einer Vollbildrepräsentation natürlich viel weniger speicherintensiv. Suchstrategien1Bewertung der Ähnlichkeit zweier Blöcke
Abbildung: Suchraum PC
Abbildung: Suchraum PDA_Phone
2AUTOFür das Block-Matching Bewegungsschätzungsverfahren sind die verschiedensten Suchalgorithmen entwickelt worden. Allen ist das Prinzip gemeinsam, dass die Blöcke im Referenzbild in der Umgebung der ursprünglichen Position des Blockes mit dem gesuchten Block aus dem Originalbild verglichen werden. (siehe Lerneineheit Bewegungsschätzung und -kompensation, Teil 2). Bewertung der Ähnlichkeit zweier BlöckeAls Maß der Ähnlichkeit zweier Blöcke betrachtet man deren Differenzen. Dafür bildet man pixelweise die Differenzwerte der beiden zu vergleichenden Blöcke. Für die Differenzwerte werden dann wahlweise, je nach verwendetem Algorithmus, der "Mittlere quadratische Fehler", die "mittlere absolute Differenz" oder die "Kreuzkorellation" eruiert. Jener Block, für den sich der kleinste Betrag errechnet, wird als der dem gesuchten Block am ähnlichsten bewertet. CostfunctionsDer mittlerer absolute Fehler (MAD):
Der Mittlere quadratische Fehler:
Kreuzkorrelationsfunktion:
AUTO
AUTOMAF arbeitet zwar nicht so effizient wie die beiden anderen Funktionen, wird aber wegen ihrer geringen Komplexität oft vor allem für Video Hardware Implementationen verwendet. SuchraumSo simpel das Prinzip von Block-Matching auch erscheinen mag, so gewaltig kann auch der Rechenaufwand ausfallen. Um den Rechenaufwand in einem realistischen Rahmen zu halten, wird die Suche auf einen beschränkten Suchraum um dem Block angewandt. watk2001-1 Größe des SuchraumsBei der Wahl der Größe des Suchraumes bezieht man sich auf die maximal zu erwartenden Bewegungsdistanzen. Aus Erfahrungswerten hat sich für die MPEG Videokomprimierung eine Suchraumgröße von +/-6 Pixel (oben, unten, links, rechts) etabliert. furt1995 Abbildung: Suchraum PC
Suchraum für das Blockmatchingverfahren. Die linke Grafik stellt einen allgemeinen Fall dar. Die rechte Grafik zeigt Makroblock und Suchraum in der Dimension, wie sie von MPEG-Standard verwendet wird. Abbildung: Suchraum PDA_Phone
Suchraum für das Blockmatchingverfahren. Die linke Grafik stellt einen allgemeinen Fall dar. Die rechte Grafik zeigt Makroblock und Suchraum in der Dimension, wie sie von MPEG-Standard verwendet wird. Bewegungskompensation interakiv1Applet Bewegungskompensation applet-m4_05_29_02
2Applet Bewegungskompensation applet-m4_05_29_02
Applet Blockmatching (Vollbild)Mit dem Applet Bewegungskompensation, Reiter Vollbild, kann man nachvollziehen, wie sich bei zwei aufeinanderfolgenden Bilder einer Videosequenz sich die Bewegungsvektoren und der Prädiktionsfehler ergeben. Man kann eine bestimmte Videosequenz, die Costfunction und die Suchmethode, die bei der Blocksuche verwendet werden sollen, wählen . Angezeigt werden die errechneten Bewegungsvektoren, das Differenzbild (durch Schaltfläche Change wahlweise bewegungskompensiert oder nicht bewegungskompensiert), und ein Bild, das nur anhand der Bewegungsvektoren rekonstruiert worden ist (ohne Prädiktionsfehler). Der Prädiktionsfehler ist das Differenzbild bei Bewegungskompensation. Für Karteireiter Makro siehe Lerneinheit Bewegungsschätzung und -kompensation 2. Instruktionen
Bildsequenzen, die zur Auswahl stehen
Genauigkeit des Bewegungsvektors pere2002,3041auto
Bewegungsvektor mit „Ein Pixel“-Genauigkeit watk2001-1,148
Bewegungsvektor mit „Halbes Pixel“ - Genauigkeit pere2002,304
Interpolation für „Halbe Pixel“-Genauigkeit PC
Interpolation für „Halbe Pixel“-Genauigkeit PDA_Phone
Bewegungsvektor mit „Viertel Pixel“-Genauigkeit pere2002,304
„Viertel Pixel“- Genauigkeit für MPEG-4Für MPEG-4 wurde ein Interpolationsalgorithmus entwickelt, der neben der ein Pixel- und der halbes Pixel- eine „Viertel Pixel“- Genauigkeit der Bewegungsvektorenkomponenten bietet. Die Qualitätssteigerung gegenüber der „halbes Pixel“ Genauigkeit ist dabei signifikant. Dieser Umstand ist mitverantwortlich, dass MPEG-4 auch bei äußerst niedrigen Datenbitraten brauchbare Bildqualität bieten kann. Abbildung: Interpolation für Viertel Pixel Genauigkeit PC
Abbildung: Interpolation für Viertel Pixel Genauigkeit PDA_Phone
Berechnung der interpolierten WerteDie Berechnung der Helligkeitswerte der virtuellen Bildpunkte erfolgt in zwei Schritten:
2autoAls Ergebnis des Block-Matchingverfahrens werden die x- und y- Koordinaten des Bewegungsvektors angegeben. Dabei gilt, je genauer diese errechnet werden, desto besser wird die Qualität des komprimierten Videos ausfallen. Eine hohe Genauigkeit der Bewegungsvektoren hält den zu kodierenden Prädiktionsfehler niedrig und ist daher vor allem für niedrige Datenstromraten wichtig. Die Genauigkeit ergibt sich einerseits aus der Qualität des gewählten Suchalgorithmus, andererseits aber auch aus der Auflösung der Koordinaten des Bewegungsvektors Bewegungsvektor mit „Ein Pixel“-Genauigkeit watk2001-1,148Es sind nur ganzzahlige Vektorkomponenten möglich. Die Koordinaten geben an, um wie viele Pixel sich ein Makroblock zwischen zwei Bildern verschoben hat. Reale Bewegungen können in dieser beschränkten Auflösung oft nur unzureichend beschrieben werden. Es ergeben sich daher dementsprechend hohe Prädiktionsfehler. Verwendet wird die „Ein Pixel“-Genauigkeit für H.261. Bewegungsvektor mit „Halbes Pixel“ - Genauigkeit pere2002,304Eine wesentliche Verbesserung gegenüber der „ein Pixel-Genauigkeit“ ist die „Halbes Pixel“ - Genauigkeit. Es können dabei die Vektorkomponenten ganze oder halbe Pixelwerte annehmen. Verwendet wird dieses Verfahren von MPEG-1, MPEG-2 und H.263. Content: Durch Interpolation der tatsächlich vorhandenen Bildpunkte erzeugt man zusätzliche Bildpunkte, die im ursprünglichen Bild eigentlich gar nicht vorhanden waren. So können natürliche Bewegungen kontinuierlicher beschrieben werden, um so genauer kann auch daher die Bewegungskompensation arbeiten, der Prädiktionsfehler wird dementsprechend kleiner. Interpolation für „Halbe Pixel“-Genauigkeit PCDie Punkte A, B, C und D sind vier benachbarte Bildpunkte. Durch bilineare Interpolation werden die im Halben Pixelabstand liegenden Punkte b,c,d errechnet.
+…..reale Bildpunkte nterpolation für „Halbe Pixel“-Genauigkeit PDA_PhoneDie Punkte A, B, C und D sind vier benachbarte Bildpunkte. Durch bilineare Interpolation werden die im Halben Pixelabstand liegenden Punkte b,c,d errechnet.
+…..reale Bildpunkte Interpolationsalgorithmus
A, B, C, D beziehungsweise b,c,d, geben die dem Ort entsprechenden Luminanzwerte an. Bewegungsvektor mit „Viertel Pixel“-Genauigkeit pere2002,304Nachdem sich die „Halbes Pixel-Genauigkeit“ für viele Anwendungen etabliert hat, gab es unzählige Versuche, durch eine noch höhere Auflösung der Bewegungsvektorkomponenten die Genauigkeit weiter zu steigern. In den meisten Fällen war allerdings die Verbesserung der Genauigkeit nicht wirklich signifikant, vielmehr handelte man sich oft höhere Bitraten ein, verursacht durch notwendige Zusatzinformationen. „Viertel Pixel“- Genauigkeit für MPEG-4
Abbildung: Interpolation für Viertel Pixel Genauigkeit PC
+ ….reale Bildpunkte o….durch Interpolation erhaltene Bildpunkte Abbildung: Interpolation für Viertel Pixel Genauigkeit PDA_Phone
+ ….reale Bildpunkte o….durch Interpolation erhaltene Bildpunkte
Berechnung der interpolierten WerteZwei Schritte:
Überlappende Block Bewegungskompensation watk2001-1,2841Ziel
Funktionsweise
2ZielMit nur einem Bewegungsvektor pro Block kann nicht für alle Pixel des Blockes die gleiche Genauigkeit erzielt werden. Im Allgemeinen werden die Pixel im Zentrum des Blockes durch den Bewegungsvektor genauer, die Pixel in Randnähe jedoch ungenauer prädiziert. In hochkomprimierenden Standards wie MPEG-4 und H.263 wird nun die Möglichkeit der „überlappenden Block Bewegungskompensation“ geboten, eine Technik, die diese Ungenauigkeit an den Blockrändern reduzieren kann. FunktionsweiseFür jene Pixel, die in Randnähe liegen, ist der Abstand zum eigenen Blockzentrum praktisch gleich groß wie zu den benachbarten Blockzentren. Die Überlappende Block Bewegungskompensation nutzt nun die Tatsache, dass diese Randbereiche oft durch den Bewegungsvektor eines der Nachbarblöcke genauer als durch den eigenen prädiziert werden können. Es wird jeder 16x16 Makroblock in vier 8x8 Pixel Blöcke aufgeteilt. Mit Hilfe effizienter Algorithmen wird für jeden dieser Subblöcke separat entschieden, welcher Bewegungsvektor der best geeignete ist. Mit Hilfe einer ausgeklügelten Prädiktionstechnik können die dadurch entstandenen zusätzlichen Informationen kodiert werden, ohne dass eine zusätzliche Datenstromrate entsteht. |
![<math display='block'> <semantics> <mrow> <mi>M </mi> <mi>Q </mi> <mi>F </mi> <mo stretchy='false'>( </mo> <mi>i </mi> <mo>, </mo> <mi>j </mi> <mo stretchy='false'>) </mo> <mo>= </mo> <mfrac> <mn>1 </mn> <mrow> <mi>m </mi> <mi>n </mi> </mrow> </mfrac> <mstyle displaystyle='true'> <munderover> <mo>∑ </mo> <mrow> <mi>i </mi> <mo>= </mo> <mo>− </mo> <mi>n </mi> <mo>/ </mo> <mn>2 </mn> </mrow> <mrow> <mi>n </mi> <mo>/ </mo> <mn>2 </mn> </mrow> </munderover> <mrow> <mstyle displaystyle='true'> <munderover> <mo>∑ </mo> <mrow> <mi>j </mi> <mo>= </mo> <mo>− </mo> <mi>m </mi> <mo>/ </mo> <mn>2 </mn> </mrow> <mrow> <mi>m </mi> <mo>/ </mo> <mn>2 </mn> </mrow> </munderover> <mrow> <msup> <mrow> <mrow> <mo>[ </mo> <mrow> <mi>F </mi> <mo stretchy='false'>( </mo> <mi>i </mi> <mo>, </mo> <mi>j </mi> <mo stretchy='false'>) </mo> <mo>− </mo> <mi>G </mi> <mo stretchy='false'>( </mo> <mi>i </mi> <mo>+ </mo> <mi>d </mi> <mi>x </mi> <mo>, </mo> <mi>j </mi> <mo>+ </mo> <mi>d </mi> <mi>y </mi> <mo stretchy='false'>) </mo> </mrow> <mo>] </mo> </mrow> </mrow> <mn>2 </mn> </msup> </mrow> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding='MathType-MTEF'> MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9 gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDY LwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rq qrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0 FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaa GcbaGaamytaiaadgfacaWGgbGaaiikaiaadMgacaGGSaGaamOAaiaac McacqGH9aqpdaWcaaqaaiaaigdaaeaacaWGTbGaamOBaaaadaaeWbqa amaaqahabaWaamWaaeaacaWGgbGaaiikaiaadMgacaGGSaGaamOAaia acMcacqGHsislcaWGhbGaaiikaiaadMgacqGHRaWkcaWGKbGaamiEai aacYcacaWGQbGaey4kaSIaamizaiaadMhacaGGPaaacaGLBbGaayzxa aWaaWbaaSqabeaacaaIYaaaaaqaaiaadQgacqGH9aqpcqGHsislcaWG TbGaai4laiaaikdaaeaacaWGTbGaai4laiaaikdaa0GaeyyeIuoaaSq aaiaadMgacqGH9aqpcqGHsislcaWGUbGaai4laiaaikdaaeaacaWGUb Gaai4laiaaikdaa0GaeyyeIuoaaaa@667A@ </annotation> </semantics> </math>](images/34mqf_formula.gif){kind=small}
repräsentiert einen mxn Makroblock im betrachteten Frame
repräsentiert den selben Block im Referenzblock
dieser Vektor repräsentiert die relatve Position der beiden Blöcke
im Suchraum
| (empty) |