DE4333368C2 - Verfahren zur Aufbereitung von Daten zur Beschreibung von Bildbereichen, sowie Anordnung hierzu - Google Patents

Description

Die Erfindung geht aus von einem Verfahren zur Aufbereitung von Verschiebungsinformationen, insbesondere für die Übertragung komprimierter Bilddaten.

Aus der DE 37 27 530 A1 ist ein Verfahren zur Bestimmung von Bewegungsvektoren (Verschiebungsinformationen) für die Übertragung komprimierter Bilddaten bekannt. Dort erfolgt eine blockweise Zerlegung von Videobildern. Ein dem Codierer zugeführter Eingangsblock wird mit gleich großen Bildausschnitten des vorangegangenen Bildes verglichen und dem Eingangsblock derjenige Vektor als Bewegungsvektor zugeordnet, der die Verschiebung von der Position des Eingangsblocks innerhalb des Bildes zu demjenigen Bildausschnitt angibt, der die größte Ähnlichkeit mit dem Eingangsblock hat. Zur Feststellung dieser Ähnlichkeit gibt es zahlreiche Kriterien, z. B. den quadratischen Quantisierungsfehler (Bosch Technische Berichte 1992, Heft 55, Seiten 32-39).

In der DE 35 46 337 A1 ist ein Verfahren und eine Vorrichtung zur Aufbereitung binärcodierter Bilddaten beschrieben. Dort wird ein Referenz-Bildbereich (Fenster) über einen Suchbereich geführt, und für jede Position innerhalb des Suchbereiches werden die Bilddaten miteinander verglichen, um Vergleichsergebnisse zu erhalten, die dann zur Verschiebungsinformation weiterverarbeitet wird. Zur Bereitstellung der Bilddaten werden mehrere zum Teil parallel arbeitende RAM benutzt, deren Speicherinhalte miteinander verknüpft und verglichen werden. Ähnliche Verfahren bzw. Vorrichtungen sind aus EP 395 293 A1, EP 479 511 A2, EP 276 434 A1 und WO 89/03152 A1 bekannt.

Beste Ergebnisse liefern die Block-Matching-Verfahren dann, wenn zur Bestimmung der Verschiebungsinformation sogenannte "Full-Search-Verfahren" (DE 38 37 590 A1) angewendet werden, die jedoch einen hohen Verarbeitungsaufwand erfordern.

Aus der US 5 173 771 ist ein Verfahren zur Bilddatenkomprimierung für Übertragungszwecke bekannt. In einem ersten Speicher werden aktuelle Bilddaten für einen Referenz-Bildbereich an einer Suchposition innerhalb eines Suchbereiches bereitgestellt. Bilddaten für den Suchbereich werden in einem zweiten Speicher bereitgestellt. Über parallel arbeitende Vergleichseinheiten erfolgt für eine Gruppe von Suchposition gleichzeitig eine Vergleichsauswertung in einer Ausbreitungsrichtung eines Bildblockes. Suchpositionen in der anderen Ausbreitungsrichtung des Blockes werden zeitlich danach bearbeitet. Zur Aktualisierung der Speicher werden jeweils komplette Frames geladen. Vorgenannte Schritte werden für weitere Gruppen von Suchpositionen wiederholt bis ein komplettes Bild verarbeitet ist.

Aus der DE 38 34 477 A1 ist es ebenfalls bekannt, zur Bewegungsschätzung aktuelle Bildblöcke und Suchbereiche zwischenzuspeichern um Vergleiche durchzuführen, wobei auch dort Positionen in einer Ausbreitungsrichtung eines Bildblockes gleichzeitig und in der anderen Ausbreitungsrichtung zeitlich danach abgearbeitet werden. Die Vergleichsergebnisse werden dort aufgrund von FD (Frame- Difference) -Operationen ermittelt, wobei minimale FD-Werte eines Verarbeitungsschrittes als Referenzwerte für die nächsten Verarbeitungsschritte herangezogen werden. Die Speicher stehen mit den Vergleichseinrichtungen derart in Wirkverbindung, daß jede der Vergleichseinrichtungen Bilddaten zur Verfügung gestellt bekommen, die sich in ihrer Gesamtheit um mindestens einen Bildpunkt von den Bilddaten, die den anderen Vergleichseinrichtungen zugeführt werden, unterschieden. Außerdem sind Addierwerte zur Aufaddition der Vergleichergebnisse vorgesehen sowie ein Komparator zur Ermittlung der kleinsten Bilddifferenz mit zugehörigem Verschiebungsvektor. Aus der EP 05 27 446 A2 ist ein ähnliches Vergleichsverfahren für Bildblockdaten bekannt.

Aufgabe der vorliegenden Erfindung ist es, ein Verfahren zur Aufbereitung von Verschiebungsinformationen anzugeben, das mit vergleichsweise geringem Schaltungsaufwand realisiert werden kann und vorgegebenen Geschwindigkeitsanforderungen genügt.

Diese Aufgabe wird durch die Schritte des Patentanspruches 1 gelöst. Der Patentanspruch 7 betrifft eine Anordnung zur Aufbereitung von Verschiebungsinformationen. Die weiteren Ansprüche zeigen Ausgestaltungen des Verfahrens bzw. der Anordnung auf.

Das Verfahren bzw. die Anordnung nach der Erfindung ermöglicht bei relativ geringem Hardware-Aufwand eine zuverlässige Ermittlung der Verschiebungsinformation für bewegte Bildbereiche. Durch die Auswertung mehrerer Suchpositionen in einem Zeitschritt bei gleichzeitiger Aktualisierung der für diese Auswertung nicht benötigten Speicherplätze erfüllt ein nach dem Verfahren der Erfindung konzipierter Videocodec übliche Geschwindigkeitsanforderungen für die Bildverarbeitung. Aufgrund der Zuverlässigkeit und der Erfüllung der Geschwindigkeitsanforderungen ist ein Videocodec nach der Erfindung für den Einsatz in Raumfahrtprojekten, z. B. HERMES, COLUMBUS, geeignet, wo es auf die sichere Erkennung von sich zum Teil schnell ändernden Bildinhalten ankommt.

Anhand der Zeichnungen wird die Erfindung und die der Erfindung zugrunde liegenden Voraussetzungen näher erläutert. Es zeigen

Fig. 1 das Prinzip eines Hybrid-Bildcoders in Funktionsblöcken,

Fig. 2 das Prinzip der Bewegungsschätzung,

Fig. 3a eine modifizierte Bewegungsschätzung mit Unterabtastung,

Fig. 3b eine weitere modifizierte Bewegungsschätzung mit Unterabtastung,

Fig. 4 das Prinzip der hierarchischen Bewegungsschätzung,

Fig. 5 ein Blockschaltbild eines Video-Coders,

Fig. 6 ein Blockschaltbild für die Bewegungsschätzung,

Fig. 7 das Blockmatching für die erste Hälfte von 4 Vektoren,

Fig. 8 das Blockmatching für die zweite Hälfte von 4 Vektoren,

Fig. 9 das Blockmatching für 4 weitere Vektoren,

Fig. 10 die Abarbeitung von sich überlappenden Suchbereichen.

In Fig. 1 ist das Prinzip eines Hybrid-Bildcoders in Funktionsblöcken dargestellt. Er besteht aus einem Prädiktions-Bildspeicher P zur Zwischenspeicherung der Rekonstruktion des vorherigen Bildes, einer Blocktransformationseinheit T, einem Quantisierer Q, einer Codiereinheit C zur statistischen Codierung und einer inversen Blocktransformationseinheit T^-1. Diese Einheiten sind Bestandteil einer üblichen DPCM-Schleife. Das Ziel einer solchen Anordnung ist es, jene Teile eines Bildes zu extrahieren, die gegenüber dem zeitlich davorliegenden Bild eine Änderung erfahren haben. Die Differenzen sind umso kleiner je besser die Prädiktion ist. In einfachen Systemen besteht der Prädiktor aus einem "Frame-Memory" (Speicher für ein Vollbild), da Pixels (Bildpunkte) benachbarter Frames sehr stark korreliert sind. Ein Prädiktionswert aus dem Bildspeicher P wird von einem aktuellen Bildwert (input) mittels eines Subtrahierers Pe subtrahiert. Die Differenzen werden in den Frequenzbereich transformiert, beispielsweise mittels DCT-Transformation (CCITT Recommendation, H. 261, Joint Photographic Experts Group ISO/IEC JTC1/SC2/WG8 / CCITT SG VIII). Die DCT-Koeffizienten werden quantisiert und codiert (Stufe C) unter Berücksichtigung ihrer statistischen Eigenschaften (Entropiecodierung). Der Prädiktionsfehler und der resultierende Codiergewinn kann durch Verwendung einer bewegungskompensierten Prädiktion MCP, beispielsweise gemäß DE 37 04 777 C1, erheblich gesteigert werden. Der Bewegungsschätzer liefert den minimalen Prädiktionsfehler. Da ein Bewegungsvektor (motion vector) nicht für jeden Bildpunkt zur Erreichung eines Codiergewinnes übertragen werden kann, sollte ein solcher Bewegungsvektor für einen größeren Bildbereich oder Block Gültigkeit haben.

Zur Gewinnung des minimalen Prädiktionsfehlers mit guter Codiereffizienz wird das Block-Matching-Verfahren verwendet. Dabei wird ein Bild in sogenannte Macroblocks MB der Größe 16×16 Bildelemente (pel) gemäß vorgenannter Empfehlung H. 261 unterteilt. Die Bewegungsschätzung wird auf diese "Nacroblocks" angewendet. In der CCITT Empfehlung H. 261 sind nur ganzzahlige Werte für die Vektorkomponenten definiert. Deshalb muß der Bewegungsschätzer keine Vektoren mit Subpegelgenauigkeit liefern.

Bei dem Blockmatching-Verfahren wird die beste Korrelation eines Nacroblocks des Frame k in einem Suchbereich (search area) eines zeitlich davorliegenden Frame k-1 gesucht (Fig. 2). Die Größe dieses Suchbereichs hängt vom gewünschten Verschiebungsbereich ab. In der Empfehlung H. 261 wird ein maximaler Verschiebungsbereich von ±15 pel in horizontaler und vertikaler Richtung vereinbart. Der Verschiebungsvektorbereich kann auf ±7 pel reduziert werden, ohne wahrnehmbare Verschlechterung der Bildqualität bei Übertragungsraten um 2 Mbit/s mit Bildwiederholungsraten von 25 Hz oder höher.

Die DFD-Werte (displaced frame differences) an einigen oder an allen möglichen Positionen des aktuellen Blocks des Frame k innerhalb des korrespondierenden Suchbereichs des Frame k-1 werden berechnet (Fig. 2), um die beste Korrelation zu erhalten. Diese Berechnung führt zu einem Satz von Frame- Differenzwerten, die zu einem Satz von Bewegungsvektoren gehören. Alle DFD-Werte des Satzes werden mit allen anderen verglichen, um das Minimum zu finden, welches den Bewegungsvektor repräsentiert.

Die Berechnung der DFD-Werte für einen Bewegungsvektor D (dx, dy) ergibt sich aus folgender Beziehung:

Die DFD-Berechnung ergibt sich demnach durch die Summation der absoluten Differenzen in der h-ten Potenz aller Bildpunkte ¹k des aktuellen Blocks und seinen korrespondierenden Bildpunkten I_k-1 im Block des zeitlich davorliegenden Frame. Der Wert von h kann 1 sein (mittlere absolute Differenz, MAD) oder 2 (mittlerer quadratischer Fehler, MSE). Im allgemeinen wird h = 1 gewählt, um den Verarbeitungsaufwand klein zu halten. Mit einer Blockgröße von 16×16 pels müssen 256 Differenzen, 256 Absolutwerte und 255 Summenwerte berechnet werden. Insgesamt müssen 767 arithmetische Operationen mit ganzzahligen Werten zur Ermittlung eines DFD-Wertes ausgeführt werden.

Mit dem "Full-Search" Verfahren werden alle möglichen Verschiebungsvektoren D innerhalb eines Suchbereiches betrachtet. Der Vektor mit der kleinsten DFD wird ausgewählt. In den meisten Fällen, insbesondere wenn ein Einzelobjekt oder ein Teil eines Objektes mit hohem Kontrast vor einem Hintergrund mit geringerem Kontrast gefunden wird, beschreibt der resultierende Vektor die wahre Bewegung des Objekts. Die Annahme trifft nicht zu, wenn zwei oder mehr Objekte innerhalb des Blocks in verschiedene Richtungen bewegt werden. Gleichwohl wird ein minimaler Prädiktionsfehler gefunden. Für eine praktische Realisierung eines Bildcoders ist der Vektorbereich auf -8/+7 pel reduziert worden und der Suchbereich auf 31×31 pel. Dies führt zu 256 möglichen Vektoren. Der Rechenaufwand beträgt danach 196 600 arithmetische Operationen einschließlich der Suche des DFD- Minimums, um den Bewegungsvektor eines Macroblocks zu ermitteln. Mit einer Framewiederholungsrate von 25 Hz müssen etwa 1,900,000,000 arithmetische Operationen in einer Sekunde ausgeführt werden, um alle Bewegungsvektoren zu erhalten. Mit den Maßnahmen nach der Erfindung kann dieser Aufwand ohne Qualitätsverlust reduziert werden. Es wird hierzu insbesondere parallel verarbeitende Hardware eingesetzt und durch spezielle Schritte der Hardwareaufwand reduziert.

Je nach Größe eines Macroblocks muß jede DFD-Berechnung die Summe von 256 absoluten Bilddifferenzwerten liefern. Dieser Aufwand kann dadurch reduziert werden, daß ein unterabgetasteter Macroblock verwendet wird mit einer reduzierten Anzahl von Bildpunkten aber einem Bildbereich der gleichen Größe.

Fig. 3 zeigt zwei Möglichkeiten für eine solche modifizierte Bewegungsschätzung und zwar Fig. 3a eine Reduktion um den Faktor 2 und Fig. 3b eine Reduktion um den Faktor 8.

Wie Fig. 3a zeigt, werden alle Bildpunkte, die mit einem Punkt markiert sind, ausgelassen. Für die DFD-Berechnung werden demnach nur halb so viele Bildpunkte verwendet, was auch die Zahl der notwendigen arithmetischen Operationen halbiert. Der Hardware-Aufwand kann verringert werden hinsichtlich der zu verarbeitenden Wortlänge, der Zahl parallel arbeitender Module und/oder der Taktgeschwindigkeit. Die verbleibenden Bildpunkte sind "quincunxförmig" angeordnet, d. h. wie die Augen einer FÜNF beim Würfel, um die beste Abdeckung des Macroblocks zu erreichen.

Normalerweise sollte der Macroblock vor der Unterabtastung bandbegrenzt werden, um Aliasingfehler zu vermeiden. Diese Maßnahme ist jedoch nur bei höheren Reduzierungsfaktoren (Fig. 3b) notwendig. Diese modifizierte DFD-Berechnung kann auf alle Blockmatching-Verfahren angewendet werden, um Hardware- oder Geschwindigkeitsaufwand einzusparen.

Auch in der Bitauflösung, die normalerweise 8 Bit pro Bildpunkt erfordert, kann der Aufwand reduziert werden. So kann die maximale DFD-Wortlänge auf 12 Bit anstatt 16 Bit reduziert werden.

Durch Verwendung eines hierarchischen, z. B. dreistufigen Suche (DE 38 37 590 A1) gemäß Fig. 4, kann der Verarbeitungsaufwand weiter reduziert werden.

Im ersten Schritt (Step 1) werden nur 9 Positionen des Suchbereiches (durch Quadrate markiert) betrachtet. Die DFD- Werte werden berechnet und an der Stelle des kleinsten Wertes (mit einem Stern markiert) wird der zweite Suchschritt initiiert. An dieser Stelle werden 8 weitere Positionen in einer näheren Umgebung untersucht. Der neunte DFD-Wert ist aus dem vorangehenden Schritt bereits bekannt. Im dritten Schritt wird diese Methode in einer Umgebung mit nur einem Pel Abstand wiederholt.

Mit dieser Vorgehensweise wird ein Bewegungsvektor mit nur 25 DFD Berechnungen gefunden. Im Vergleich zum "Full-Search" Verfahren ist die Zahl der Berechnungen um den Faktor 9 reduziert. Der resultierende Vektor ist im Bereich von ±7 pel.

Erfahrungsgemäß liegen die DFD-Werte häufig im Bereich ±1 pel, so daß ein zusätzlicher vierter Schritt das Schätzergebnis verbessern kann. Dieser vierte Schritt wird mit der Bildpunktumgebung aus dem dritten Schritt auf den jeweils mittleren Bildpunkt des ersten Schrittes angewendet. Die daraus sich ergebenden 8 DFD Berechnungen reduzieren den Codiergewinn von 9 auf 6.8.

Neben den zuvor beschriebenen Verfahren ist noch das Block- Matching Verfahren mit nichtlinearer Vektorquanisierung und das hierarchische Block-Matching Verfahren zur Reduzierung des Verarbeitungsaufwandes anwendbar. Verglichen mit den "Full- Search" Verfahren liefern alle modifizierten Verfahren in etwa alle modifizierten Verfahren in etwa 80 bis 95% aller Fälle die gleichen Vektoren.

Aus diesem Grunde werden die Schritte der Erfindung nachfolgend anhand des "Full-Search" Verfahrens erläutert. Eine entsprechende Übertragung-auf die modifizierten Verfahren ist natürlich möglich.

Fig. 5 zeigt ein Blockschaltbild eines Video-Coders. Aktuelle und die rekonstruierten Bilder (frames) sind beispielsweise in einem externen Bildspeicher EBS abgespeichert. Es sind zwei lokale Speicher vorgesehen, und zwar ein erster Speicher SRD für die aktuellen Blockdaten des Referenz-Bildbereiches und ein zweiter Speicher SSD für Bilddaten des Suchbereichs. Die Speicher SSD und SRD erlauben einen wiederholten Zugriff auf den Referenzblock (aktuellen Block) und den Suchblock. Beide Speicher SSD und SRD erhalten ihre Daten vom externen Bildspeicher EBS.

Im "interframe mode" (vgl. H. 261) ermittelt ein Bewegungsschätzer ME die Bewegungsvektoren. Ein Prädiktionsblock wird für den Luminanzanteil vom SSD-RAM an ein Filternetzwerk FN geleitet und für den Chrominanzanteil direkt vom externen Bildspeicher EBS, gegebenenfalls nach Serien-Parallelwandlung S/P. Ein Prädiktionsblock wird jeweils mit einem aktuellen Block verglichen, d. h. vom aktuellen Block subtrahiert mittels der Einrichtung SB. Ein nichtlineares Gewichtungsnetzwerk NL vermindert Störungen, die durch Rauschanteile hervorgerufen werden. Nach der Transformation in den Spektralbereich durch die DCT-Einheit erfolgt die Quantisierung und Codierung mittels der Einheit QUA.

Im "intraframe mode" wird ein aktueller Block direkt vom SRD- RAM zur DCT-Einheit weitergeleitet.

Für die Bewegungsschätzung werden nur Luminanzbildpunkte ausgewertet. Um den Bewegungsvektor für einen Makroblock (Referenzblock der Größe 16 × 16 pel) zu finden, muß er mit allen Blöcken innerhalb des Suchbereichs (ein 31 × 31 pel Block des davorliegenden Frame) verglichen werden durch Berechnung der "displaced frame difference" DFD. Die beste Korrelation befindet sich beim Minimum der DFD-Werte. Für die Bestimmung eines Bewegungsvektors muß jeder Bildpunkt des Referenzblocks 256 Mal geladen werden. Die Bildpunkte des Suchbereichs müssen zwischen 1 und 256 Mal geladen werden in Abhängigkeit ihrer Position innerhalb des Suchbereichs. Jedoch muß unter Berücksichtigung der überlappenden Suchbereiche des Frame k-1 jeder Bildpunkt des Frame k-1 256 Mal für die Bewegungsschätzung geladen werden. Dies verursacht eine extrem hohe Datentransferrate zwischen dem Bildspeicher EBS, welcher den aktuellen und den davorliegenden Frame enthält, und der Blockmatching-Einrichtung. Um den Datentransfer auf einem 8 bit Bus ausführen zu können, muß die Zugriffszeit der externen RAMs allein für das Blockmatching kleiner als 0,8 ns sein, was mit heutiger Technologie, z. B. der HCMOS Technologie, nicht zu erreichen ist. Wie zuvor schon erwähnt wurde beträgt der Rechenaufwand ungefähr 1,900,000,000 arithmetische Operationen. Aus diesem Grund wird eine parallele und pipelineartige Architektur mit lokalen Cache-RAMs verwendet.

In Anlehnung an die CCITT Empfehlung H. 261, die die Sequenz der Macroblöcke vorgibt, wird die Arbeitssequenz für den Bewegungsschätzer in gleicher Weise festgelegt. Ein eingangsseitiges Bild im CIF-Format wird in 12 Gruppen von Blöcken unterteilt, die jeweils aus 33 (11 × 3) Macroblöcken bestehen.

Gemäß Fig. 6 speichert das SRD-RAM die Daten des aktuellen Macroblocks, die für die Bewegungsschätzung und für die Berechnung des Prädiktionsfehlers herangezogen werden. Es ist als 2 Port-RAM aufgebaut. Um einen Macroblock zu laden, sind 64 Zeitschritte (write cycles) notwendig. Zur Ermittlung eines Vektors, muß der Bewegungsschätzer 2048 Lesezugriffe über einen 64 bit Bus zum SRD-RAM ausführen. Das SSD-RAM stellt die Bildpunktdaten für den Suchbereich zur Verfügung. Der Bewegungsschätzer weist vier parallele Zweige auf, um vier Bewegungsvektoren in x-Richtung gleichzeitig aufbereiten zu können. Das SSD-RAM muß demzufolge 11 pels, respektive 88 bit an Bildpunktdaten, liefern. Es ist als 4 Port-RAM ausgebildet mit einem Schreibeingang und 3 Leseausgängen. Die Busbreite der drei Leseausgänge beträgt 32 bit und die des Schreibeingangs 24 bit. Die RAM-Größe beträgt 186 × 32 bit, so daß nur a = 6 Spalten eines Suchbereichs gespeichert werden können, wobei eine Spalte q = 4 Pels breit und 31 Zeilen tief ist.

Fig. 7 zeigt, durch die "o" Markierung, die oberste Zeile des Suchbereichs mit 31 pel. Die unterstrichenen pel (Spalten 1 bis 3 des Suchbereiches) werden den Vergleichseinheiten V1 bis V4 im ersten Schritt des Blockmatching vom SSD-RAM gleichzeitig zugeleitet. Das Symbol "m" kennzeichnet die erste Hälfte der ersten Zeile des Referenzblocks (pel 1 bis 8). Die korrespondierenden "m" - "o" Kombinationen aus dem SSD-RAM und dem SRD-RAM werden benutzt, um den Betrag A-B der Frame- Differenz FD für 8 pel und vier Vektoren parallel in einem Verfahrensschritt (Zeitschritt) zu bestimmen. Wie Fig. 6 zeigt, sind die ersten Vergleichseingänge der Vergleichseinheiten V1 bis V4 mit allen Ausgängen des SRD-RAM in Wirkverbindung, wohingegen die zweiten Vergleichseingänge jeweils um einen Bildpunkt versetzt Bilddaten vom SSD-RAM erhalten (1 . . . 8, 2 . . . 9, 3 . . . 10, 4 . . . 11).

Somit werden im ersten Zeitschritt p = 4 verschiedene Suchpositionen gleichzeitig abgearbeitet. Während der folgenden 15 Zeitschritte werden die nächsten Zeilen des Referenzblocks (8 pel) und des Suchbereichs (11 pel) geladen und der Betrag der Frame-Differenz berechnet. Die ermittelten Frame-Differenz-Beträge werden mittels der Addierwerke A1, A2, A3, A4 bezüglich jeweils einer Vergleichseinheit aufsummiert und in Registern abgespeichert. Für die Addierwerke wird beispielsweise die bekannte "Wallace Tree"-Struktur (EP 249 279 B1 angewandt. Damit werden jeweils 8 Vergleichsergebnisse und das rückgeführte Ergebnis der vorherigen Suche aufwandsarm aufaddiert. Die minimalen Frame- Differenzen FD_min aus allen Parallelzweigen sowie die zugehörigen Vektoren werden über den einen Minimum-Komparator K ausgegeben. Zur Vervollständigung der Berechnung der Frame- Differenzen muß die zweite Hälfte des Blockmatchings an den Suchpositionen gemäß Fig. 8 durchgeführt werden. Das Symbol "n" repräsentiert dort die erste Zeile der zweiten Hälfte des Referenzblocks (pel 9 bis 16).

Diese Berechnung erfordert weitere 16 Zeitschritte. Demzufolge werden 4 Frame-Differenzwerte FD innerhalb von 32 Zeitschritten berechnet. Die Frame-Differenzwerte FD mit den minimalen Werten und der korrespondierende Vektor wird gespeichert als FD_min, x_min und y_min und steht/stehen als Bezugswert/e für den nächsten Schritt zur Verfügung. Im nächsten Schritt werden die Registerinhalte über entsprechende Rückführschleifen den Addierwerken A1 bis A4 erneut zugeführt. Als Ergebnis wird der beste Repräsentant für die Vektorpositionen (-8, -8), (-7, -8) (-6, -8) (-5, -8) gefunden.

Der nächste Suchschritt ist in Fig. 7 ebenfalls dargestellt, aber nun kennzeichnet "o" die zweite Zeile des Suchbereichs, um die Vektorpositionen (-8, -7), (-7, -7), (-6, -7), (-5, -7) abzuarbeiten. Der zuvor ermittelte FD_min-Wert wird nun mit dem Minimum der neuen FD-Werte verglichen. Der kleinste FD-Wert und die dazu korrespondierende Vektorposition wird als FD_min, x_min und y_min gespeichert. Dieser Suchschritt wird so lange wiederholt, bis alle 16 vertikalen Suchpositionen (y-Richtung) abgearbeitet sind. Auf diese Weise wird die beste "Matching- Position" im Bereich (x, y) = (-8 . . . -5, -8 . . . +7) gefunden. Insgesamt erfordert dies 512 Zeitschritte.

Im vorgestellten Beispiel werden von den a Spalten 5 Spalten zur DF-Berechnung und Bestimmung von q = 4 Vektoren mit 4x und 16y Komponenten benutzt, während die sechste Spalte zum Nachladen (Aktualisieren) des Suchbereiches mit einer q = 4 pel breiten Spalte Vorgesehen ist. Die Verfahrensschritte werden nun entsprechend der in Fig. 9 dargestellten Positionen wiederholt, um den nächsten Satz von 4 Vektoren zu ermitteln. Jetzt werden die Spalten 2, 3 und 4 bzw. 4, 5 und 6 zur Ermittlung der FD-Werte an den Vektorpositionen (x, y) = (-4 . . . -1, -8 . . . +7) benutzt. Gleichzeitig wird die Spalte 7 vom externen Speicher EBS aus aktualisiert. Für die übrigen Vektorpositionen werden vorgenannte Schritte so oft wiederholt, bis alle Vektorpositionen eines Makroblocks innerhalb von 2048 Zeitschritten abgearbeitet sind.

Normalerweise besteht ein Suchbereich aus a = 8 Spalten mit einer Breite von q = 4 pel und einer Tiefe von 31. Diese Daten müssen für einen Initialisierungsblock geladen werden. Für die FD-Berechnung des nächsten Blocks sind jedoch bereits 4 Spalten im SSD-RAM geladen, so daß nur noch 4 weitere 4-pel breite Spalten nachgeladen werden müssen. Diese Vorgehensweise halbiert den Datentransfer vom externen Bildspeicher ESB zum SSD-RAM. Jedoch müssen an den Randbereichen einer Makroblockzeile zusätzliche Daten für den Suchbereich geladen werden.

Fig. 10 zeigt einige Referenzblöcke (Reference Blocks) mit den korrespondierenden Suchbereichen (Search Areas). Wenn der Block i-1 abgearbeitet ist, ist die erste Hälfte des Suchbereiches für die Bearbeitung des Blockes i schon im SSD- RAM geladen, so daß nur noch die zweite Hälfte geladen werden muß. Mit Ausnahme der Blöcke an den Randbereichen müssen 496 pel vom externen Speicher ESB zum SSD-RAM übertragen werden. Dies geschieht innerhalb von 124 Zeitschritten.

Claims (5)

1. Verfahren zur Aufbereitung von Daten zur Beschreibung von Bildbereichen, insbesondere für die Übertragung komprimierter Bilddaten, mit folgenden Schritten:

• - Bereitstellen von aktuellen Bilddaten für einen Referenz- Bildbereich an einer Suchposition innerhalb eines Suchbereiches in einem ersten Speicher (SRD),
• - Bereitstellen von Bilddaten für den Suchbereich in einem zweiten Speicher (SSD), wobei der Suchbereich in Zeilen und Spalten unterteilt ist,
• - Zuführen der Bilddaten des ersten und zweiten Speichers (SSD, SRD) an mehrere Vergleichseinheiten (V1, V2, V3, V4) und zwar so, daß diese Vergleichseinheiten (V1, V2, V3, V4) für eine erste Gruppe von Suchpositionen in einem ersten Verarbeitungsschritt gleichzeitig Vergleichsergebnisse liefern, wobei Vergleichsergebnisse für q Bildpunkte einer Zeile und p Vektoren innerhalb eines Verarbeitungsschrittes ermittelt werden,
• - Aktualisieren jener Bereiche oder eines Teils jener Bereiche des zweiten Speichers (SSD) im ersten Verarbeitungsschritt mit aktuellen Bilddaten, die für die Verarbeitung der ersten Gruppe von Suchpositionen im ersten Verarbeitungsschritt nicht benötigt werden derart, daß der Suchbereich in a Spalten mit jeweils einer Breite von q Bildpunkten unterteilt wird, daß jeweils a-1 Spalten zum Ermitteln der Vergleichsergebnisse benutzt werden und jeweils eine Spalte zur Aktualisierung des Suchbereichs,
• - Wiederholen vorgenannter Schritte für eine zweite oder weitere Gruppe von Suchpositionen in einem zweiten oder weiteren Verarbeitungsschritt,
• - Verknüpfen der Vergleichsergebnisse zu Daten, die jeweils einen ganzen Bildbereich beschreiben.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß bei Benutzung blockartig strukturierter Bildbereiche p verschiedene Suchpositionen in einer Ausbreitungsrichtung des blockartigen Suchbereichs gleichzeitig bearbeitet werden und daß die Suchpositionen in der anderen Ausbreitungsrichtung zeitlich nacheinander bearbeitet werden.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die Vergleichsergebnisse aufgrund von FD (frame­ difference) -Operationen ermittelt werden, wobei die minimalen FD-Werte eines Verarbeitungsschrittes als Referenzwerte für den jeweils nächsten Verarbeitungsschritt herangezogen werden.

4. Anordnung zur Aufbereitung von Daten zur Beschreibung von Bildbereichen, insbesondere für die Übertragung komprimierter Bilddaten, bestehend aus:

• - einem ersten Speicher (SRD) für Bilddaten eines Referenz- Bildbereichs,
• - einem zweiten Speicher (SSD) für Bilddaten eines Suchbereiches, wobei der zweite Speicher (SSD) Mittel aufweist zur Spaltenweisen Aktualisierung des Suchbereichs mit Daten eines externen Speichers (EBS) jeweils um jene Bereiche, die für einen sich anschließend Vergleich aktuell nicht benötigt werden,
• - mehreren Vergleichseinheiten (V1, V2, V3, V4), deren erste Vergleichseingänge mit allen Ausgängen des ersten Speichers (SRD) in Wirkverbindung stehen und deren zweite Vergleichseingänge mit jeweils nur einem Teil der Ausgänge des zweiten Speichers (SSD) in Wirkverbindung stehen und zwar so, daß jede der Vergleichseinrichtungen (V1, V2, V3, V4) Bilddaten zur Verfügung gestellt bekommt, die sich in ihrer Gesamtheit um mindestens einen Bildpunkt von den Bilddaten, die den anderen Vergleichseinrichtungen zur Verfügung gestellt werden, unterscheiden,
• - den Vergleichseinheiten (V1, V2, V3, V4) jeweils zugeordneten Addierwerken (A1, A2, A3, A4) zur Aufaddition der mit den Vergleichseinheiten (V1, V2, V3, V4) gewonnenen Vergleichsergebnisse,
• - einem Komparator (K) zur Ermittlung der kleinsten Bilddifferenz mit zugehörigem Verschiebungsvektor aus den aufaddierten Vergleichsergebnissen.

5. Anordnung nach Anspruch 4, dadurch gekennzeichnet, daß die Vergleichseinheiten (V1, V2, V3, V4) so ausgestaltet sind, daß sie jeweils Bildpunkt-Betragsdifferenzen der ihnen von den beiden Speichern (SSD, SRD) zugeführten Daten bilden.