motion estimation

Ok, ich versuche mal zu erklären, und ich versuche es so zu machen, dass man das dann zusammen mit den Bilder von akapuma gut in die Wiki übernehmen kann (Zaunpfahl! :)) Vielleicht könnte man da sogar schöne Skizzen dazu malen als ersatz für die ASCIIs (Zaun!! :))

Die erkannte Bewegung wird verwendet, um aus bereits decodierten Frames bereits das nächste Bild möglichst gut anzunähern, so dass nur noch die Unterschiede gespeichert werden muss. Diesen Vorgang bezeichnet man als Motion Compensation.

Dabei gibt es verschiedene Ansätze (von komplex zu einfach geordnet):

Mesh-Based Motion: Das Frame wird in ein Gitter geteilt, und die Unterschiede werden als Verzerrung dieses Netzes modelliert. Kann auch komplexe Bewegungsmuster gut modellieren. Sowohl Estimation als auch Compensation sind sehr rechenintensiv. Mesh Based Motion wird in keinem populären Format wirklich verwendet, jedoch sind in MPEG4 Specifikationen dazu vorhanden.

Global Motion

Bewegung wird als affine Transformation beschrieben, D.h. als eine Mischung aus Zoom, Schwenk, Drehung und perspektivischer Verzerrung. Man benötigt nur sehr wenige Parameter dafür (platzsparend), jedoch ist nur sehr einfache Bewegung effektiv vorherzusagen. Estimation/Compensation sind rechenintensiv. Wird verwendet in MPEG4 ASP (z.B. XviD GMC), Dirac.

Overlapped Block Motion (OBMC/E)
Ähnlich der Block Motion (siehe unten), nur dass sich überlappende Blöcke verwendet werden. Im Überlappbereich wird eine Mischung aus den verschiedenen Blöcken als Vorhersage verwendet. Das ermöglicht bessere Vorhersagen und verringert Blockartefakte in der Vorhersage, was die Subjektive Qualität verbessert.
OBMC wird in Snow und Dirac verwendet, MPEG4 hat Spezifikationen dazu, wird aber in der Praxis nicht verwendet.

Block Motion:

Das Bild wird in sich Blöcke eingeteilt, und für jeden Block wird ein Bewegungsvektor bestimmt, der beschreibt, wie sich dieser Block im Vergleich zum Referenzframe verschoben hat.

Graphisches 1-dim Beispiel (| sind nur Markierungen):
Referenz:
aaaa|bbbb|cccc|dddd
Vorherzusagendes Frame
bbbb|aabc|cccc|ccca
Bewegungsvektoren
-4 | 2 | 0 | 4
Vorhersage
bbbb|aabb|cccc|cccc

Estimation und Compensation sind relativ einfach und schnell. Jedoch sind komplizierte Bewegung schlecht modellierbar und Vorhersage weist Blockartefakte auf.
Um effektiv kompliziertere Bewegungen modellieren zu können, müssen kleine Blöcke verwendet werden, was aber viele Bewegungsdaten erfordert. Moderne Formate erlauben daher unterschiedliche Blockgrößen in einem Frame (z.B. Blockgrößen von 16x16 bis 4x4 in bestimmten Anordnungen bei H.264). Block Motion findet in allen MPEG und den H.26x Formaten, sowie in sehr sehr vielen anderen Formaten Verwendung.

Man kann auch noch die Referenz "zoomen" also Pixel zwischen den eigentlichen dazuerfinden, in der Hoffnung, dass man dann bessere Vorhersagen bekommt. MPEG4 ASP und AVC unterstützen Bewegungsvektoren bis auf 0.25 Pixel (QPEL), Dirac bis 0.125 Pixel genau.

Hier jetzt eine kurze Besprechung der populärsten Suchverfahren (die aus x264 und Xvid) für Block Motion Estimation. Diese lassen sich mit kleinen Änderungen auch für OBME verwenden.

Man beginnt mit einer Abschätzung des Bewegungsvektors für den aktuellen Block. Die Abschätzung kann z.B. der bereits gefundene Bewegungsvektor des vorherigen Blocks sein, da die Bewegung von benachbarten Blöcken mit großer Wahrscheinlichkeit ähnlich ist.

Ein Bewegungsvektor zeigt auf einen Block im Referenzbild. Es ist also das gleiche, wenn man von Bewegungsvektoren oder Bildblöcken im Referenzbild spricht.

Um "gute" Bewegungsvektoren von "schlechten" Bewegungsvektoren unterscheiden zu können, muss man die Unterschiede zwischen dem Block im Referenzbild und dem Block, den man vorhersagen will (hier ab jetzt Zielbild genannt) messen können. Dazu gibt es verschiedene Metriken (es handelt sich sogar streng mathematisch um Metriken):

SAD (Sum Absolute Differences, Summe der Absoluten Differenzen):
Für jedes Pixel im Block wird der Absolutbetrag der Differenz des Pixelwerts im Referenzbild und im Zielbild berechnet und die Summe daraus gebildet. Sehr schnell.

SSD (Sum of Squared Differences, Summe der quadrierten Differenzen):
Für jedes Pixel im Block wird das Quadrat der Differenz des Pixelwerts im Referenzbild und im Zielbild berechnet und die Summe daraus gebildet. Große Differenzen werden so stärker gewichtet.

SATD (Sum of Hadamard Transformed Differences, Summe der Hadamardtransformierten Differenzen)
Es wird für jeden Pixel die Differenz zwischen Referenzframe und Zielframe berechnet und der Differenzblock Hadamardtransformiert. Die Hadamardtransformation ist eine mathematische Operation, die der DCT sehr ähnlich ist. SATD sagt nun also ungefähr etwas darüber aus, wie viel Speicherplatz die entstehenden Differenzen nach einer DCT benötigen. Relativ langsam, aber für manche Zwecke aussagekräftiger. Z.B. verwendet x264 zur Schätzung der Komplexität eines Frames im crf Modus SATD.

Um einen guten Bewegungsvektor zu finden gibt es verschiedene Strategien:

Diamond (a) /Hex (b) Search:

1) Man beginnt mit einer Schätzung des Bewegungsvektors.

2a) Jetzt misst man die Unterschiede der vier direkt benachbarten Bewegungsvektoren/Bildblöcke (also bei Ganzpixelsuche die, die ein Pixel nach oben, unten, links und rechts verschoben sind).

1[COLOR='Red']2[/COLOR]3[COLOR='Red']4[/COLOR][COLOR='Blue']5[/COLOR][COLOR='Red']6[/COLOR]7[COLOR='Red']8[/COLOR]9

Bei Zentrum 5 werden die Orte 2, 4, 6 und 8 geprüft.
2b) Jetzt misst man die Unterschiede der sechs in einem Hexagon um das Zentrum angeordeten benachbarten Bewegungsvektoren/Bildblöcke.

a[COLOR='Red']b[/COLOR]c[COLOR='Red']d[/COLOR]efghij[COLOR='Red']k[/COLOR]l[COLOR='Blue']m[/COLOR]n[COLOR='Red']o[/COLOR]pqrstu[COLOR='Red']v[/COLOR]w[COLOR='Red']x[/COLOR]y

3) Dann nimmt man die Position als neues Zentrum, die die geringsten Unterschiede aufweist.
4) Man bricht ab, wenn sich das Zentrum in zwei aufeinanderfolgenden Schritten nicht ändert, d.h. keine der umliegenden Positionen besser ist als das Zentrum.

Exhaustive Search:

Es werden alle Positionen in einem gewissen Fenster abgesucht. Sehr sehr langsam.

Uneven Cross Multihexagon:

Diese Methode funktioniert ungefähr so:

Zuerst werden einige Positionen in Kreuzform um die Vorhersage abgesucht, der horizontale Balken des Kreuzes ist länger, da horizontale Bewegungen häufiger sind als vertikale):

a
   b
cdefghi
   j
   k

Um die beste Position davon wird eine exhaustive Search mit kleinem Fenster durchgeführt, und ausserdem ein Hexagonsuche mit einem doppelten Hexagon (zwei Hexagons mit unterschiedlichen Radius um das selbe Zentrum). Ausserdem werden sehr komplizierte Kriterien verwendet, um die Suche abzubrechen, wenn schon früh im Suchvorgang "gute" Bewegungsvektoren gefunden wurden.

akapuma:
nach dieser etwas länglichen Erklärung sind die Antworten auf deine Fragen ganz kurz:

Es werden Bewegungsvektoren gesucht. Radius 1 und Radius 2 bedeuten, dass bei Dia Search der Diamant einen Radius von 1 hat, das Hexagon einen Radius von 2.

Merange ist ungefähr die maximale Länge des Bewegungsvektors. Bei Dia und Hex terminiert die Suche meistens früher, deshalb kein großer Effekt. Bei Esa wird die Suche sehr viel langsamer, und bei umhex beeinflusst es die größe des Kreuzes, und die maximale Anzahl der MHex Schritte.

so aus dem Bauch heraus:
merange = Größe der Umgebung in der gesucht wird
mvrange = Länge des maximal zulässigen Bewegungsvektors

Cu Selur

Ps.: Schön bald kann ich mir die Wissenswertes Teile sparen.