Einleitung

1

Vorgestellte Methoden

• Vollsuche
• Dreischrittmetode

Evaluierung der beiden Methoden

• Vollsuche - sehr genau, sehr rechenintensiv
• Dreischrittmethode - wenigere genau, 7 mal so schnell

2

Vorgestellte Methoden

Wie in der Lerneinheit MPEG-2 Levels und Profiles erwähnt, gibt es verschiedene Techniken, um basierend auf dem Blockmatchingverfahren die Position eines bestimmten Makroblockes aus einem Bild in einem Referenzbild wieder zu finden. Hier in dieser Lerneinheit werden zwei sehr gängige Techniken vorgestellt.

• Vollsuche
• 3Schrittmethode – ist jene Form der Mehrschrittsuche, wie sie bei MPEG Videokomprimierung zum Einsatz kommt.

Evaluierung der beiden Methoden

Grundlegend unterscheiden sich die beiden Techniken durch ihre Performance. Während die Vollsuche sehr genaue Ergebnisse liefert, benötigt sie eine lange Rechenzeit, was sie für viele Echtzeitanwendungen unbrauchbar macht. Die Dreischritt Methode hingegen arbeitet knapp sieben mal so schnell, allerdings ist sie nicht so genau.

Ausführlicher Suchalgorithmus

1

Funktionsweise

• Auswahl eines 16x16 Makroblockes im Bild
• Vergleich mit allen möglichen Makroblöcken im Suchraum des Referenzbildes
• Ähnlichkeitsbewertung mit Hilfe von Costfunctions

Nötige Iiterationsschritte für +/-6 Suchraum

2

Eigenschaften

Der ausführlicher Suchalgorithmus (=full search): ist der einfachste Algorithmus und liefert das genaueste Ergebnis, ist aber auch rechnerisch der zeitintensivste.

Funktionsweise

Es wird für einen 16x16 Makroblock ein Suchraum ausgewählt, wie in der Lerneinheit Bewegungsschätzung und -kompensation, Teil 2 beschrieben. Es werden alle möglichen Blöcke innerhalb des Suchraumes mit dem Block im Originalbild verglichen. Jener Block, der nach Evaluierung der entsprechenden Costfunction dem gesuchten Block am ähnlichsten ist, wird als dessen Konterpart im entsprechenden Bild bewertet, und als Grundlage zur Berechnung des Bewegungsvektors herangezogen.

Nötige Iterationsschritte

Bei einer Suchraumbeschränkung von +/-6 ergeben sich...

...Iterationen für jeden Makroblock

Die Mehr-Schritt Suche

1

Funktionsweise

1. Suchschritt

• Suchraum in 9 sich nicht überlappende Unterbereiche geteilt
• Berechnung, in welchem Unterbereich gesuchter Block sein muss

2. Suchschritt

• gefundener Unterbereich wieder in Unterbereiche geteilt
• Berechnung, in welchem Unterbereich gesuchter Block sein muss

Folgende Schritte

• gefundener Unterbereich wieder in Unterbereiche aufgeteilt
• wird so lange wiederholt, bis gefundener Unterbereich Dimension eines Makroblock hat
• Dieser Unterbereich ist der gesuchte Makroblock

Nötige Iterationsschritte

Bei einem Suchraum von +/-6 werden dazu 3 Schritte benötigt

...Iterationen für jeden Makroblock

2

Eigenschaften

Es müssen nicht alle Blöcke, die sich im Suchraum befinden, in die Berechnung mit einbezogen werden. Es wird der Suchraum in Unterbereiche unterteilt. Jeder Unterbereich beinhaltet mehrere mögliche Blockpositionen. Man versucht in einem ersten Schritt nicht die genaue Position des Makroblockes heraus zu finden, sondern nur den Unterbereich, in dem er sich befindet. So können in einem Rechengang gleich mehrere mögliche Blockpositionen ausgeschlossen werden.

Funktionsweise

• In einem ersten Schritt wird der gesamte Suchbereich in neun Unterbereiche aufgeteilt. Oben links, oben, oben rechts, links, gleich bleibende Position; rechts, unten links, unten, unten rechts.
• In einem ersten Rechendurchgang wird jener Unterbereich eruiert, in welchen sich der gesuchte Block befinden muss. Die verbleibenden acht Unterbereiche und damit all die darin befindlichen Blöcke scheiden als mögliche Kandidaten aus.
• Der errechnete Unterbereich wird in einem weiteren Schritt wieder in neun Unterbereiche gegliedert, und es wird wieder jener Unterbereich, in welchem sich der gesuchte Block befinden muss, errechnet.
• Dieser Vorgang wird solang fortgesetzt, bis die neu entstandenen Unterbereiche neun direkt nebeneinander liegender Blöcken entsprechen.
• Jener Block, der nun den besten Wert in Bezug auf Ähnlichkeit liefert, wird zur Errechnung des Bewegungsvektors herangezogen.

Nötige Iterationsschritte

Bei einem Suchraum von +/-6 werden dazu 3 Schritte benötigt (siehe PU4). Es werden in diesem Fall nur mehr...

...Iterationen pro Makroblock durchgeführt. Als Costfunction wird für die Mehrschritttechnik die Berechnung des "mittleren quadratischen Fehlers" verwendet (siehe Lerneinheit Bewegungsschätzung und -kompensation, Teil 2).

Die Drei-Schrittsuche

1

Abbildung:Die Drei-Schrittsuche PC

Abbildung:Die Drei-Schrittsuche PDA_Phone

2

Rechnerischer Aufwand

Wendet man die Mehrschrittsuche bei der MPEG Videokomprimierung an, so ergeben sich für einen 16x16 Makroblock und einer Suchraumgröße von +/-6 drei benötigte Rechenschritte. Im Folgenden sollen anhand eines Beispiels die drei Schritte des Algorithmus durchexerziert werden.

Abbildung:Die Drei-Schrittsuche PC

• M1-M9 sind die Mittelpunkte der ersten 9 Unterbereiche des gesamten Suchraums
• M11-M19 sind die Mittelpunkte der Unterbereiche oben rechts. Dieser wurde bei diesem Beispiel als neuer Suchraum aus Schritt eins Schritt zwei erkannt.

Abbildung:Die Drei-Schrittsuche PDA_Phone

• M1-M9 sind die Mittelpunkte der ersten 9 Unterbereiche des gesamten Suchraums
• M11-M19 sind die Mittelpunkte der Unterbereiche oben rechts. Dieser wurde bei diesem Beispiel als neuer Suchraum aus Schritt eins Schritt zwei erkannt.

Prozedere Dreischritt-Suche

• 1. Schritt: Es wird der Block im Originalbild mit dem Block im Referenzbild, der die selbe Position hat und mit den acht in dessen Nachbarschaft liegenden verglichen (links, rechts, oben links, oben Mitte, oben rechts, unten links, unten Mitte, unten rechts) Abstand ist +/-3. Jene Position, die den besten Wert liefert, wird für den nächsten Schritt als neues Zentrum gewählt
• 2. Schritt: Vom neuen Zentrum ausgehend , werden die 8 Nachbarschaftspositionen bewertet, allerdings in einem kleinerem Abstand +/-2. Jene Position, die den besten Wert liefert, wird für den nächsten Schritt als neues Zentrum gewählt
• 3. Schritt: ausgehend von neuer Position. Vergleich mit acht Nachbarschaftspositionen, Abstand +/-1. Jene Position, die den besten Wert liefert, wird zur Berechnung des Bewegungsvektors herangezogen.

Suchstrategien interaktiv

1

Applet Bewegungskompensation: Suchstrategien applet-m4_05_29_02

Online Alternative

2

Applet Bewegungskompensation: Suchstrategien applet-m4_05_29_02

Online Alternative

Applet Blockmatching (Makro)

Im Applet "Blockmatching", Reiter " Makro", wird Blockmatching mit unterschiedlichen Suchmethoden und unterschiedlichen Costfunctions (Siehe Lerneinheit Bewegungsschätzung und-kompensation, Teil1 dargestellt .Man kann im Bild 2 einen 16x16 pixel Makroblock auswählen, der im Bild 1 zu finden ist. Man kann sich die gewählte Suchmethode Schritt für Schritt oder in einem Rechendurchgang rechnen lassen. Angezeigt werden die momentanen Makroblöcke in Bild 1 und Bild 2, sowie deren Differenzbild. In der untersten Abbildung sieht man den Suchraum, in dessen Zentrum der Referenzblock liegt, und jenen Block,der zum momentanen Zeitpunkt vom Suchalgorithmus evaluiert wird. Für Karteireiter Vollbild siehe Lerneinheit Bewegungsschätzung und -kompensation 1.

Randblöcke

Makroblöcke, die sich am unmittelbaren Bildrand befinden, sind in diesem Applet nicht anwählbar. Der Grund ist, dass die Berechnung dieser Blöcke für den Demoeffekt nicht wirklich notwendig ist und die Komplexität der Algorithmen unnötig erhöht werden müßte. Beachte: Bei realen MPEG Encodern müssen diese Randblöcke sehr wohl berechnet werden!

Instruktionen

1. Wähle ein Bild aus der Auswahlliste und bestätigedieses mit dem rechts davon befindlichen _Laden Button.
2. Selektiere den von Dir gewünschten Algorithmus und die passende Funktion.
3. Nun folgt die Auswahl des zu findenden Blocks (Referenzblock) mit Hilfe des Mousecoursers.
4. Betätige den _Start Button zur Anzeige des Ergebnisses oder den _SchrittfürSchritt Button für eine interaktive Darstellung.
   1. Start hier wird der Suchalgorithmus gestartet. als Ergebnis wird der dem Referenzblock als am Ähnlichsten bewerteter Block angezeigt
   2. Bei Wahl Schritt für Schritt kannst du im unteren Suchraum mitverfolgen, wie der gewählte Algorithmus den Block sucht, für jeden Schritt siehst du in der oberen Bildreihe den momentan bewerteten Block, den Referenzblock und deren beider Differenzbild
5. Versuche nun herauszufinden, bei welchem Suchalgorithmus und welchen Costfunctions der Prädiktionsfehler am kleinsten wird.
6. Wieso ist die Rechenzeit unterschiedlich lang?
7. Findest du einen Zusammenhang zwischen benötigter Rechenzeit und Qualität des Suchergebnisses?
8. Für welche Bildsequenz und an welcher Bildstelle funktioniert das Blockmatching besonders gut, für welche weniger und für welche überhaupt nicht? Warum ist das so?
9. Gibt es einen Zusammenhang zwischen Qualität des Suchergebnisses und charakteristische Eigenschaften spezieller Bildstellen? Untersuche dafür Bildstellen mit scharfen Konturen, und gleichmäßige, konturlose Bildteile.

Bildsequenzen, die zur Auswahl stehen

• Bewegung
  • Hier wird die Maus am rechten Bildschirmrand um ca 25 Pixel nach links bewegt.
• Drehung
  • Bei dieser Bilderserie wurde die Kamera um die eigene Achse gedreht
• Helligkeit
  • Diese beiden Bilder weisen unterschiedliche Helligkeitswerte auf
• Objektdrehung
  • Das Objekt in der Mitte wird gedreht.
• Verschiebung
  • Das zweite Bild wird 3 Pixel nach links unten verschoben
• Objektverschiebung (Verschiebung 2)
  • Der Elefant wandert um 3 Pixel nach links, sonst bleibt das Bild gleich.