Multimedia-Systeme: Übungsblatt 4

Aufgabe 1: Bewegungserkennung

Der MPEG Standard sieht die drei Bildtypen I-, P- und B-Frame vor. Wir wollen uns im folgenden mit P-Frames näher auseinandersetzen. P-Frames sehen zur Codierung eines Bildes Bewegungsvektoren vor, die die Position eines Makroblocks (16x16 Pixel) in Relation zum vorherigen I-Frame angeben. Der Standard beschreibt zwar die Codierung, gibt aber keinerlei Algorithmen zur Berechnung der Bewegungsvektoren vor (Bewegungserkennung).

Bei der Bewegungserkennung geht es darum, einen bestimmten Bereich des einen Bildes innerhalb eines Suchbereichs eines anderen Bildes möglichst exakt wiederzufinden.

In dieser Aufgabe soll ein einfacher Algorithmus zur Bewegungserkennung behandelt werden. Es handelt sich dabei um den sog. "Full-Search"-Algorithmus, der in einem vorgegebenen Suchbereich alle Blöcke auf Ähnlichkeit zu einem Referenzframe untersucht und den ähnlichsten Frame als Ergebnis ausgibt.

Gegeben sei der folgende Suchbereich S:

171	155	130	117	136	165	189	195
150	143	145	119	134	160	175	183
155	147	188	123	135	155	170	185
140	165	172	153	153	153	169	185
124	126	155	149	172	175	170	180
111	124	143	143	165	155	160	173
117	113	130	145	150	155	142	144
120	125	178	150	155	153	148	186

Der zu suchende Referenzframe M lautet:

Betrachten Sie den Wert 153 (x-Koord. = y-Koord=3, Ursprung des Suchraumes linke obere Ecke: x,y=0) als Zentrum des Suchraums und verwenden Sie einen Suchradius von p=3.

Verwenden Sie außerdem folgende Fehlerfunktion als Ähnlichkeitskriterium:

wobei M die Dimension des Referenzframes in x-Richtung und N die Dimension in y-Richtung angibt. R(u,v) gibt einen Pixelwert des aktuellen Suchraumes an, während C(u,v) die Pixelwerte des Referenzframes bezeichnet (Hinweis: Setzen Sie in der Formel x und y gleich 0). F(i,j) ist dann ein Fehlermaß für die Ähnlichkeit des Blocks an Koordinate (i,j) des Suchraumes.

Teilaufgabe (a)

Beschreiben Sie die Funktionsweise des Algorithmus.

Teilaufgabe (b)

Finden Sie den ähnlichsten Frame der Größe 2x2 innerhalb des Suchbereichs S.

Geben Sie bitte folgende Elemente der Lösungsmatrix an:

Obere linke Ecke: - 142 144 148 186

Obere rechte Ecke: - 142 144 148 186

Untere linke Ecke: - 142 144 148 186

Untere rechte Ecke: - 142 144 148 186

Wie groß ist der mit Hilfe der Formel F(i,j) berechnete Fehler? - 0,5 0,05 0,33 0,75

Teilaufgabe (c)

Wieviele Operationen (Additionen, Subtraktionen, Betragsberechnungen) benötigt Full Search, bis es diesen Block gefunden hat?

Aufgabe 2: Bewegungserkennung

Überlegen Sie sich einen schnelleren Algorithmus zur Bewegungserkennung. Nennen Sie Vor- und Nachteile.

(Tip: Der Algorithmus kann auch eine suboptimale Lösung zurückliefern...)

Abgabedaten:

Matrikelnummer: Password: