DE3874705T2 - Verfahren zur bewegungsabschaetzung mit mehreren prediktoren fuer punkte eines elektronischen bildes. - Google Patents

Description

• Die Erfindung betrifft die Analyse und Codierung von Sequenzen elektronischer Bilder, und insbesondere die Analyse der Bewegung der Bildpunkte solcher elektronischer Bilder.
• In einem spezifischen Fall, der nachfolgend im Detail behandelt ist, wird das erfindungsgemäße Verfahren auf die Analyse von Hochauflösungsbildsequenzen angewandt, die über einen Kanal mit begrenztem Durchsatz gesendet werden. Eine bevorzugte Anwendung dieser Art ist das Senden von Hochauflösungsfernsehen über einen MAC-Kanal.
• Das erfindungsgemäße Verfahren kann jedoch auch auf jedes System angewandt werden, in welchem Bildsequenzen analysiert werden (Robotertechnik, Zielverfolgung, Suchen von Raum- und/oder Zeitparametern, usw.) , oder Sequenzen von Datenmengen (medizinische Anwendungen, meteorologische Anwendungen, usw.).
• Das erfindungsgemäße Verfahren soll in einer Bildverarbeitungskette eingefügt werden, wobei es ein Glied für die Analyse der Bildpunktgeschwindigkeiten in der Bildebene darstellen soll.
• Diese Analyse ist von vielseitigem Interesse.
• Im Falle der Transmission von Bildsequenzen über einen Kanal mit begrenztem Durchsatz hat die Bildverarbeitung den Zweck, die Menge der transmittierten Informationen zu reduzieren, so daß:
• - beim Senden eine Unterabtastung durchgeführt wird, wobei die Daten dieser Unterabtastung von "behelfsmässigen Daten" begleitet werden, die zusammen mit den Daten der Unterabtastung über den Datenkanal transmittiert werden;
• - beim Empfang eine umgekehrte Prozedur stattfindet, wobei die behelfsmäßigen Daten und die Daten der Unterabtastung zum Wiederherstellen eines Hochauflösungssignals verwendet werden.
• Gemäß der vorliegenden Erfindung erfolgt dann die Abschätzung der Bildpunktbewegung innerhalb dieses Musters beispielsweise vor der Unterabtastung beim Senden. Die Bewegungsabschätzung hat somit den Zweck, einen Grundstock räumlich-zeitlicher Daten bereitzustellen, welche für die Bewegung der Punkte sowohl in der Bildebene als auch zeitlich repräsentativ sind. Diese Daten ermöglichen die Bestimmung der geeignetsten Verarbeitungsprozedur, um eine Datenkompression durch Unterabtastung durchzuführen.
• Auf dem Gebiet der Datenkompressionsverfahren bei Berücksichtigung von Bildbewegungen kennt man bereits das "Verfahren zur Strukturanalyse von räumlich-zeiltlichen Unterabtastungen eines HDTV (High Definition Television = hochauflösendes Fernsehen)-Signals im Hinblick auf seine Weitergabe über einen MAC-Kanal", wie beschrieben in den Niederschriften des Kolloquiums TVHD 87, Ottawa 4. - 8. Oktober 1987, Band 1, Seiten 6.2.1 (P. BERNARD, M. VEILLARD, CCETT). Bei diesem bekannten Verfahren wird jedes Bild der Sequenz in Zonen aufgeteilt, wobei jede Zone systematisch drei parallel verlaufenden Verarbeitungsschritten mittels drei verschiedener Linearfilter unterworfen wird. Jeder Filter nimmt eine andere Unterabtastungsfiltration vor, jeweils gemäß einer Vorzugsfiltration für stehende Bilder, für mäßig bewegte Bilder und für schnell bewegte Bilder. Die Filterausgänge werden dann mit der Ursprungsquelle verglichen und eine Auswahl der besten Filtration durchgeführt, um zu bestimmen, welches der komprimierten Signale tatsächlich transmittiert werden soll.
• Eine solche Batterie linearer Filter hat den Nachteil, daß sie nur eine begrenzte Auswahl zwischen drei Arten von Unterabtastungsfiltrationen zuläßt, ohne Möglichkeit die Filtrationen den Besonderheiten der verarbeiteten Zonen spezifisch anzupassen. So wurden unter Anderem heterogene Auflösungen für verschiedene Zonen eines seben Bildes festgestellt, sowie eine schwache Leistung dieses Verfahrens bei der Verarbeitung langsamer Bewegungen. Dieses Problem erscheint beispielsweise sehr deutlich, in einer für den Zuschauer höchst unangenehmen Weise, beim Anhalten einer langsamen Bewegung, bzw. wenn ein ruhender Gegenstand in Bewegung gesetzt wird. Im ersten Falle wechselt man plötzlich von einem verschwommenen Bilde des bewegten Gegenstandes zu einem Bild maximaler Schärfe für den bewegten Gegenstand, und umgekehrt im zweiten Falle.
• Ein bekannter und schärferer Ansatz zum Lösen des Problems der Codierung einer Bildsequenz besteht in der Durchführung einer a priori Bewegungsabschätzung für die Bildsequenz.
• Diesbezüglich hat T.S.HUANG ("Image Sequence Analysis : Motion Estimation" in Image Sequence Analysis; Ed. T.S. HUANG, Springer Verlag 1981) drei verschiedene Verfahren identifiziert: das FOURIER-Verfahren, das "Zuordnungsverfahren" und das Verfahren welches räumliche oder zeitliche Gradienten anwendet. Die ersten zwei Verfahren haben einige Nachteile. Das FOURIER-Verfahren ist mit einem Problem der Phasenunbestimmtheit behaftet und setzt die Gleichmäßigkeit des Bildhintergrundes voraus. Das "Zuordnungsverfahren" (block matching) scheint komplexe Signalverarbeitungsschritte zu erfordern, deren versuchsweise Vereinfachung vermutlich die Gefahr von Divergenzen im Verarbeitungsalgorithmus in sich birgt.
• Unter den Methoden mit räumlichen und zeitlichen Gradienten sind einige Algorithmusvorschläge bekannt: LIM, J.O. und MURPHY, J.A. "Measuring the Speed of Moving Objects from Signals", IEEE Trans. on Com., April 75, Seiten 474-478; NETRAVALI, A.N., ROBBINS, J.D. "Motion Compensated Television Coding : Part I", BSTJ, Vol. 58, No. 3, March 79, Seiten 631-670; SABRI, S. "Motion Compensated Interframe Prediction for NTSC Color TV Signals", IEEE Transactions on Communications, Vol. COM 32, No. 8, August 1984, Seiten 954-968; ROBERT, P. "Définition d'un schéma de codage multimodes avec compensation de mouvement pour les séquences d'images de télévision", Thèse IRISA, nov. 83; LABIT, C. "Estimation de mouvement dans une séquence d'images de télévision", Thèse IRISA RENNES, Fév. 82; WALKER, D.R., RAO, K.R. "New Techniques in Pel-Recursive Motion Compensation", ICC 1984, "Links for the Future Science, System and Services for Communications, 14-17 Mai 1984, IEEE-Elsevier Science Publishers B.V. (North. Holland), Amsterdam, Seiten 703-706.
• Diese bekannten Abschätzungsmethoden sind in der Tat mit dreierlei Einschränkungen behaftet:
• - Einschränkungen die mit der ausgewählten algorithmischen Methode zusammenhängen,
• - Einschränkungen die mit dem rekursiven Aufbau der meisten Algorithmen zusammenhängen,
• - Einschränkungen die mit der vorgeschlagenen Ausgangshypothesenauswahl für die Abschätzungsalgorithmen zusammenhängen.
• Was die Grenzen algorithmischer Methoden betrifft, so kann man grundsätzlich die bekannten Verfahren in zwei Gruppen aufteilen: Algorithmen, welche die Komponenten des mit einem Bildblock zusammenhängenden Geschwindigkeitsvektors suchen (block matching) und Algorithmen, welche die Komponenten des mit einem Bildpunkt zusammenhängenden Geschwindigkeitsvektors suchen. Die Auswahlkriterien für die eine oder die andere Algorithmustechnik hängen grundsätzlich von der relativen Komplexität der angewandten Verarbeitungsmethoden ab sowie von der psycho-visuellen Wahrnehmung der relativen Effektivität, welche einer jeden dieser Techniken anhaftet.
• Für das erfindungsgemäße Verfahren wurde die Auswahl getroffen, vorzugsweise eine punktweise Bewegungsschätzfunktion einzusetzen, nämlich bevorzugt, aber nicht restriktiv, die durch WALKER und RAO beschriebene Bewegungsschätzfunktion. Die Gründe für diese Auswahl, welche Teil des Erfindungsvorgangs hinter der Methode sind, werden im folgenden aufgezeigt.
• Es ist jedoch zu bemerken, daß das Verfahren genau so gut auf die Abschätzung von Blockbewegungen anwendbar ist, wobei jeder Block durch einen einzigen, eventuell vektoriellen, Vertreter vertreten werden kann.
• Die zweite Einschränkung hängt mit dem rekursiven Charakter der meisten bekannten Algorithmen zusammen. Diese rekursive Eigenschaft hat den Nachteil, daß sie mehrere Rechenschleifen für die Abschätzung der Bewegung eines Punktes erfordert. Somit sind diese Vorgänge notwendigerweise sequentieller Natur, da die n-te Abschätzung erst dann durchgeführt werden kann, wenn die (n-1)-te Abschätzung bekannt ist. Bei den heutigen Fernsehfrequenzen ist diese Methode nicht kompatibel, zumindest ist sie von starkem Nachteil.
• Zuletzt hängt die dritte Art von Einschränkung mit dem heute empfohlenen Initialisierungsmodus für die bekannten Bewegungsabschätzungsalgorithmen, und hauptsächlich für die "rekursiv nach Punkten" genannten Abschätzungsalgorithmen (auf Englisch: pel-recursive) zusammen. Schließlich stehen diese Initialisierungsmodi allgemein mit den ausgewählten Algorithmustechniken und Rekursivitätsmodi im Zusammenhang. Unter diesem Gesichtspunkt lassen sich zwei Hauptrekursionstechniken voneinander unterscheiden, die einer Verfeinerung der Punktbewegungsabschätzung entsprechen: entweder durch Rauminterpolation (s. zum Beispiel A.N. NETRAVALI, J.D. ROBBINS, oben erwähnt; P. ROBERT, C. CAFFORIO, F. ROCCA, "Time/Space Recursions for Differential Motion Estimation", 2nd Internat. Tech. Symp. on Optical and Electro Optical Applied Science and Engineering, Cannes, Dezember 1985; B.K.P. HORN, B.G. SCHUNK, "Determining Optical Flow", Artificial Intelligence, vol. 17, Seiten 185-203, 1981; W. ENKELMANN, "Investigations of Multigrid Algorithms for the Estimation of Optical Flow Fields in Image Sequences", Workshop on Motion: Rep. and Analysis, IEEE, Mai 1986, Charleston), oder durch zeitliche Interpolation (Y. NINOMIYA, Y. OHTSUKA, "A Motion Compensated Interframe Coding Scheme for Television Pictures", IEEE Transactions on Communications, vol. COM - 30, n 1, Jan. 82, Seiten 201-211; R. PAQUIN, E. DUBOIS, "A Spatio-Temporal Gradient Method for Estimating the Displacement Vector Field in Time - Varying Imagery", Computer Vision, Graphics and Image Process., vol. 21, 1983, Seiten 205-221). Die zeitliche Interpolation eignet sich grundsätzlich besser für die Verarbeitung von Sequenzen stehender Bilder, während sich die räumliche Interpolation im Falle schneller Bildsequenzen als besonders zufriedenstellend erweist. Dagegen erweisen sich die vorhandenen Gesetze als untauglich im Falle langsamer Bewegungen, wo sie starke Streifenbildung in bevorzugter Richtung zeigen, wodurch sie starke und inkohärente Störungen der Bildcodierung verursachen.
• Das erfindungsgemäße Verfahren verfolgt unter anderem den Zweck, alle dem Stand der Technik entsprechenden Nachteile auszuräumen.
• Genauer gesagt besteht ein erstes Ziel der Erfindung darin, eine Methode für die Abschätzung der Bewegung elektronischer Bildpunkte in der Bildebene mittels einer schnellen, konvergenten und adaptiven Verarbeitung bereitzustellen, insbesondere mit dem Zweck, eine nachfolgende effektive Verarbeitungsprozedur für die Unterabtastung der Bildsequenz zu ermöglichen, ohne der psychovisuellen Qualität des aus dem unterabgetasteten Bilde rekonstruierten Bilde zu schaden. Diese Anwendung soll als Beispiel dienen.
• Ein zweites Ziel der Erfindung ist das Bereitstellen einer Bewegungsabschätzungsprozedur dieser Art, die vom Bildformat unabhängig ist. Die Prozedur kann sowohl auf das Format 4/3 als auch auf das Format 16/9 (HDTV) angewandt werden.
• Ein weiteres Ziel der Erfindung besteht im Bereitstellen einer solchen Bewegungsabschätzungsprozedur, die auf ein Kabelnetz anwendbar ist, wobei die Anzahl und die Kosten der Komponenten, insbesondere die Kapazität der erforderlichen Pufferspeicher, minimiert werden sollen.
• Ferner hat die Erfindung mehrere zusätzliche, untergeordnete Ziele, die mit der weiter unten dargestellten spezifischen Lösung im Zusammenhang stehen, wie die Lösung von Deutungskonflikten der Punktbewegungen, oder auch die Organisation der Bildschirmränder.
• Ein zusätzliches Ziel der Erfindung besteht in der Bereitstellung einer solchen Methode, von der mindestens eine Version mit den heute üblichen Verarbeitungssystemen kompatibel sein soll, insbesondere bei der Anwendung der Erfindung auf die Codierung von HDTV für MAC-Kanäle.
• Ein anderes Ziel der Erfindung ist es, die Durchführung einer Bewegungsabschätzung an Hand des Prinzips verschiedener Algorithmustypen zu ermöglichen, die entweder bekannt sind oder noch entwickelt werden müssen, so zum Beispiel der WALKER- und RAO-Algorithmus, oder der Algorithmus von ROBERT, CAFFORIO und ROCCA, die beide schon erwähnt wurden.
• Noch ein Ziel der Erfindung besteht in der Bereitstellung einer Bildcodierungsmethode mit den oben erwähnten Eigenschaften, wobei die besagte Codierungsmethode auch Auswahlfähigkeiten für die selektive Anwendung einer geeigneten Codierung zwischen mehreren verfügbaren Codierungsmöglichkeiten besitzen soll. Eine solche Codierungsmethode sollte insbesondere die Fähigkeit besitzen, die Codierung sowohl von stehenden als auch von bewegten Bildern zu optimieren, wobei die Bewegung langsam oder schnell sein kann, sowie die Codierung raum-zeitlicher Bruchzonen (Umrisse, plötzliche Bewegungsänderungen, usw.), ohne Verarbeitungsverzögerungen zu verursachen.
• Diese Ziele, sowie andere, die später dargestellt werden sollen, werden mittels einer Bewegungsabschätzungsmethode für elektronische Bildsequenzen erreicht, die insbesondere mit dem Zweck entwickelt wurde, jedem elektronischen Bildpunkt einen Bewegungsvektor in der Bildebene zum Zeitpunkt t zuzuordnen. Zweck dieser Entwicklung ist beispielsweise zuerst die Durchführung einer optimierten Kompressionsverarbeitung des Bildsignals, und/oder zweitens, eine Näherungsprojektion der Bildposition zum Zeitpunkt t in das folgende Bild zum Zeitpunkt (t+1) zu ermöglichen, wobei
• bestagter laufender Bewegungsvektor eines laufenden Punktes zum Zeitpunkt t gemäß eines algorithmischen Prädiktions-/Korrektur-Verfahrens berechnet wird, wobei ein vorausgesagter Bewegungswert als Ausgangshypothese für die Berechnung herangezogen wird, und dieser vorausgesagte Bewegungswert anschließend im Verlaufe des Verfahrens gemäß einem Korrekturverfahren durch Kriterienoptimierung berichtigt wird, dadurch gekennzeichnet, daß der oben erwähnte, vorausgesagte Bewegungswert des laufenden Punktes, der einem ursprünglichen Bildpunkt zum Zeitpunkt (t-1) zugeordnete Wert des ursprünglichen Bewegungsvektors ist, wobei besagter laufender Punkt die Näherungsprojektion des Ursprungspunktes gemäß dem ursprünglichen Bewegungsvektor ist.
• Es ist von Vorteil, wenn das besagte Prädiktions-/Korrektur-Verfahren zur Gattung der "rekursiv nach Punkten"-Algorithmen gehört, insbesondere der WALKER- und RAO-Algorithmus, oder auch der ROBERT-, CAFFORIO- und ROCCA-Algorithmus.
• Ein anderes wichtiges Ziel der Erfindung ist die Bereitstellung einer Bewegungsabschätzungsmethode für elektronische Bildsequenzen, die insbesondere mit dem Ziel entwickelt wurde, jedem elektronischen Bildpunkt einen Bewegungsvektor in der Bildebene zum Zeitpunkt t zuzuordnen, um beispielsweise zuerst die Durchführung einer optimierten Kompressionsverarbeitung des Bildsignals, und/oder zweitens eine Näherungsprojektion der Bildposition zum Zeitpunkt (t+1) zu ermöglichen, wobei besagter laufender Bewegungsvektor eines laufenden Punktes zum Zeitpunkt t gemäß eines algorithmischen Prädiktions-/Korrektur-Verfahrens berechnet wird, wobei ein vorausgesagter Bewegungswert als Ausgangshypothese für die Berechnung herangezogen wird und dieser vorausgesagte Bewegungswert anschließend im Verlaufe des Verfahrens gemäß einem Korrekturverfahren durch Kriterienoptimierung berichtigt wird, dadurch gekennzeichnet, daß besagtes Verfahren mindestens zwei parallel zueinander verlaufende Bewegungsabschätzungsberechnungen durchführt, ausgehend von zwei vorausgesagten Bewegungswerten des laufenden Punktes, wobei besagte Werte unter mindestens einer räumlich-zeitlichen Voraussage in Bewegungsrichtung ausgewählt werden, sowie unter mindestens einem der folgenden Werte:
• - mindestens eine räumliche Bewegungsvoraussage;
• - mindestens eine zeitliche Bewegungsvoraussage; und daß
• besagtes Verfahren die Abschätzung des Geschwindigkeitsvektors gemäß einer Entscheidungsprozedur nach Kriterienoptimierung auswählt.
• Andere Merkmale und Vorteile der Erfindung werden beim Lesen der nachfolgenden Beschreibung von detaillierten Ausführungsformen der Erfindung ersichtlich, welche als Beispiele aufgeführt werden, sowie der beiliegenden Zeichnungen, unter denen:
• - Fig. 1 ein Übersichtsdiagramm darstellt, worin die Stellung des Bewegungsabschätzungsverfahren gemäß der Erfindung innerhalb einer Codierungs-/Decodierungskette für die Weitergabe eines HDTV-Signals über einen MAC-Kanal gezeigt wird;
• - Fig. 2 die Bewegungsabschätzung durch räumliche Voraussage darstellt;
• - Fig. 3 die Bewegungsabschätzung durch zeitliche Voraussage darstellt;
• - Fig. 4 die Bewegungsvoraussage in Bewegungsrichtung darstellt;
• - die Fig. 5A und 5B das Zuordnungsverfahren einer punktmäßigen Voraussage mit Lösung des "mehrfachen Bewerber"-Konfliktes und ohne Lösung des "kein Bewerber"-Konfliktes, darstellen;
• - die Fig. 6 und 7 ein Ausführungsbeispiel der Erfindung darstellen, bei welchem solchen Punkten, die keine Voraussage besitzen, eine Voraussage zugeordnet wird;
• - die Fig. 8 und 9 Übersichtsdiagramme darstellen, worin die Anwendung eines Bewegungsabschätzungsverfahrens nach mehrfachen Voraussagen gemäß der Erfindung dargestellt ist.
Definitionen
• Bewegungsabschätzung: Signalverarbeitungsmethode, die dazu dient, für einen Punkt (bzw. einen Punktblock) eines mittig eingestellten Ursprungsbildes den Bewegungsvektor dieses Punktes von einem Bild zum nächsten in bezug auf den "Rahmen" der Bildsequenz zu bestimmen.
• Bewegungskompensation: Signalverarbeitungsmethode, die den Bewegungsvektor eines Punktes (bzw. eines Punktblocks) für die Interpolation des am Decoder empfangenen Signals verwendet, mit dem Zweck, ein Höchauflösungsbild bei der Ansicht von hochauflösendem Fernsehen zu erzielen.
• Kriterium für das Eignungsmaß des berechneten Bewegungsvektors: DFD ("Displaced Frame Difference") ("Abstand zwischen den Leuchtdichten des Quellpunktes (t-1) und des Zielpunktes (t), welche durch den berechneten Geschwindikeitsvektor miteinander verbunden sind"), gemäß dem Abschätzungsalgorithmus von WALKER und RAO; das Aufsuchen des optimalen Bewegungsvektors (dx, dy) am Punkt (x, y) des Bildes t besteht darin, im Bilde (t-1) den Punkt mit den Koordinaten
• (x - Dx, y - Dy)
• aufzusuchen, für welchen die DFD, definiert durch:
• DFD = I(x, y, t) - I(x - Dx, y - Dy, t-1) ,
• minimiert wird,
• wobei:
• x = Bildpunktabszisse;
• y - Bildpunktordinate;
• t = Abtastzeitpunkt eines Bildes;
• t-1 = Abtastungszeitpunkt des Bildes welches zeitlich vor dem Bilde zum Zeitpunkt t liegt;
• I(x, y, t) = Leuchtdichte des Bildpunktes (x, y) zum Zeitpunkt t.
Kontext der dargestellten Ausführungsform
• Die Ausführungsform der nachfolgend dargestellten Erfindung fügt sich in das Konzept und die Ausführung eines Schemas für das Codieren und Decodieren einer HDTV-Bildquelle ein, mit Hinblick auf ihre Weiterleitung über einen MAC-Kanal.
• Fig. 1 stellt ein Übersichtsdiagramm dar, worin die Stellung, die das Bewegungsabschätzungsverfahren gemäß der Erfindung innerhalb einer Codierungs-/Decodierungskette für die Weitergabe eines HDTV-Signals über einen MAC-Kanal einnimmt, gezeigt wird. Die Ausführungsform gemäß Fig. 1 entspricht einer spezifischen Fassung, die mit den bereits existierenden Systemen kompatibel ist, einschließlich paralleler Verarbeitungen durch Linearfilter, und einer "a posteriori" Codierung. Die Codierungsphase des HDTV-Signals besteht im:
• 1) Unterabtasten des Quellbildes (nach eventueller Filtration), um die Anzahl der Videoinformationen zu reduzieren, damit die MAC-Norm eingehalten wird (Schritt 10),
• 2) Behandeln der HDTV-Quellsequenz mit einem Codierer, um räumlich-zeitliche Daten (behelfsmäßige Daten), welche mit der besagten Frequenz zusammenhängen, weiterzuleiten (Schritt 11).
• Die Decodierungsphase 14 besteht im:
• 1) Empfang des transmittierten MAC-Signals, das dem unterabgetasteten Quellbild entspricht;
• 2) Sichtbarmachen des empfangenen Bildes ohne die zusätzlichen Daten zu berücksichtigen, wenn ein konventionelles Fernsehgerät für den Empfang verwendet wird. Dies nennt man kompatibles Bild;
• 3) Verarbeiten der zusätzlichen Daten, um mittels eines geeigneten Interpolations- und Kompensationssystems 14, ein hochauflösendes HDTV Bild wiederzugeben, wenn der Empfang mittels eines hochauflösenden Fernsehgeräts erfolgt.
• Es wird auf den Vorteil aufmerksam gemacht, der sich daraus ergibt, daß das unterabgetastete Videosignal über den Leuchtdichte-MAC-Kanal 12 transmittiert wird, während die behelfsmäßigen Daten 13, welche sich aus dem Schritt 11 ergeben, über den zugeordneten "Datenkanal" weitergegeben werden (s. MAC-Transmissionsnorm). Im Übersichtsdiagramm der Fig. 1 sieht man, daß Schritt 11, bei welchem die behelfsmäßigen Daten 13 erzeugt werden, durch die Vergleichsmittel 15 der Filtrations- und Bewegungsabschätzungsergebnisse gespeist wird, welche parallel zueinander in den Schaltkreisen 20, 21, 22 und 23 erzielt werden. Die Schaltkreise 20, 21, 22 und 23 entsprechen klassischen Filterschaltkreisen über Linearfilter. Die drei Pfade 21, 22 und 23 entsprechen jeweils einer Filtration, die für eine stehende Bildzone, für eine langsam bewegte Bildzone und für eine schnell bewegte Bildzone geeignet ist. Schaltkreis 20 entspricht der Ausführung des Bewegungsabschätzungsverfahrens gemäß der Erfindung. Dieses Verfahren setzt sich zusammen aus den Schritten 16 für die Analyse aller Bildpunkte sowie 17 zur Festlegung des mit jedem Bildpunkt zusammenhängenden Geschwindigkeitsvektors. Dieser Durchführungsmodus entspricht einem "a posteriori" Codierungssystem in dem Sinne, daß das hochauflösende Quellbildsignal gleichzeitig und parallel in den Schaltkreisen 20, 21, 22 und 23 einem Bewegungs-Filtrations-/Abschätzungsverfahren unterworfen wird, wobei die Auswahl der optimalen Codierungsverarbeitung nachträglich erfolgt, und zwar im Vergleichskreislauf 15.
• In einem anderen, leistungsfähigeren Ausführungsmodus, der jedoch mit den existierenden Systemen nicht kompatibel ist, wird das Bewegungsabschätzungsverfahren gemäß der Erfindung vor den Filtrationsvorgängen durchgeführt, wobei die am Ausgang des Schaltkreises 20 erzielten Ergebnisse die eventuelle Anwendung eines der Filter 21, 22, 23 bedingen, wenn der geschätzte Bewegungswert dies vorschreibt. In der Tat werden bei diesem Ausführungsmodus, den man als "a priori" Codierung bezeichnen kann, nur die Filter 21 und 23 für stehende bzw. schnell bewegte Zonen beibehalten. Das Filtrationsverfahren des einen oder anderen dieser Filter 21, 23 kann somit als optimales Verfahren beibehalten werden, je nachdem ob der Fall der Bewegungslosigkeit oder der schnellen Bewegung Vorausgeschätzt wird.
Bewegungsabschätzung
• Zweck der Bewegungsabschätzung ist es, jedem Punkt eines laufenden Bildes t den Bewegungsvektor dieses Punktes zwischen den Bildern t - 1 und t zuzuordnen.
• Durch Kenntnis dieses Bewegungsvektors wäre es somit möglich, für den Fall einer stetigen Bewegung (mit Bezug auf die Abtastgeschwindigkeit) nur jedes zweite Bild durch den MAC-Kanal zu senden, da jedes nicht gesendete Bild von dem unmittelbar vorausgegangenem Bild hergeleitet werden kann, mittels der Verschiebung der Punkte des hervorgegangenen Bildes gemäß ihrer Bewegungsvektoren. Eventuelle "Löcher" im rekonstituierten Bild können dann durch Interpolation ausgefüllt werden.
• Es wird dabei vorausgesetzt, daß die Hochauflösungsquellbilder perfekt bekannt und "non-interlaced" sind. Die Bewegungsvektoren werden über dem in der MAC-Norm vorgesehenen Datenkanal wesentlich wirtschaftlicher übertragen, als die Punktbilder des ausgelassenen Bildes.
• Es wurden viele Bewegungsabschätzungsalgorithmen entwickelt, die teilweise im Vorwort erwähnt sind. In allen Fällen besteht deren Rolle darin, jedem Punkt des Bildes t einem Vektor zuzuordnen, welcher die Kenntnis der Position dieses Punktes im Bilde t-1 ermöglicht. Die für diese Ausführungsform ausgewählte Bewegungsabschätzungsmethode ist die bereits erwähnte sog. "pel-recursive" Methode von WALKER und RAO. Um eine Bewegung zu schätzen, verwendet diese Methode eine Voraussage (d. h. einen wahrscheinlichen Anfangswert) dieser Bewegung, sowie eine Korrekturfunktion. Letztere ist von einem örtlichen Raumgradienten (grad), von einer variablen Zunahme, die mittels des Gradienten berechnet wird, sowie von einem mit DFD gekennzeichneten Leuchtdichtenabstand abhängig. Die DFD ist ein Maß für den Leuchtdichtenabstand zwischen dem laufenden Punkt und sein durch den Bewegungsvektor geortetes Gegenstück im vorhergegangenen Bild. Dieser DFD-Wert ist ein grundsätzlicher Begriff des erfindungsgemäßen Verfahrens, insoweit er nicht nur bei der Anwendung des WALKER- und RAO-Algorithmus für die Abschätzung im Sinne von Bewegung gemäß der Erfindung dienlich ist, sondern auch bei den Vergleichsverfahren für die Filtrations- und Bewegungsabschätzungsergebnisse. Diese Vergleiche ermöglichen die Festlegung der besten Codierungs-/Abtastungsmethode für das transmittierte Signal.
• Die WALKER- und RAO-Methode ist als iterative Methode mit einzelner Aussage bekannt.
• Die bisher bekannterweise angewandten Aussagen sind zweierlei Ordnungen:
• - räumliche Voraussage: (Fig. 2) es wird vorausgesagt, daß die Bewegung des Punktes (x, y) änlich der Bewegung eines der ihm im Bild t räumlich benachbarten Punkte ist, sei es zum Beispiel der vorhergehende Punkt in der selben Zeile (x - 1, y, t), oder eines der auf der vorhergehenden Zeile liegenden benachbarten Punkte (x, y - 1, t), (x - 1, y - 1, t), (x + 1, y - 1, t)
• Diese Voraussage ermöglicht eine zufriedenstellende Abschätzung der Bewegung von räumlich ausgedehnten Gegenständen, die sich schnell im Bild bewegen.
• - zeitliche Voraussage: (Fig. 3) die für den Bewegungsvektor des Punktes (x, y, t) ausgewählte Voraussage ist die Abschätzung, welche für den Punkt (x, y, t - 1) im vorangegangenen Bild (t - 1) berechnet wurde.
• Diese Art der Voraussage ist eindeutig optimal im Falle einer stehenden Bildsequenz, oder genauer gesagt von stehenden Bildzonen.
• Diese bekannten Abschätzungsmethoden sind zwar nützlich, aber bei weitem nicht ausreichend, wie bereits im Vorwort erklärt, und haben zur Entwicklung der folgenden drei Aspekte entsprechend dem erfindungsgemäßen Verfahren geführt:
• - Anwendung einer Voraussage des Bewegungsvektors in Bewegungsrichtung;
• - Verfahrensfunktion im "Multivoraussagen"-Modus;
• - Einfügung des Voraussageverfahrens in Bewegungsrichtung, und/oder der "Multivoraussage", in eine Codierungskette, die lineare Abtastungsfilter einschließt, wobei die Betriebsweise entweder im "a priori" Modus oder im "a posteriori" Modus erfolgt. Diese Alternative wurde bereits weiter oben vorgestellt.
Beschreibung der Voraussage in Bewegungsrichtung:
• Die Voraussage in Bewegungsrichtung besteht darin, das Feld der Bewegungsvektoren des Bildes t Punkt für Punkt in das Bild t+1 zu projizieren. Diese Projektion erfolgt gemäß den Beträgen der Komponenten Vx und Vy, um auf einem abgetasteten Punkt des Bildes t+1 anzukommen (Fig. 4). So ist die Projektion des Punktes A (x, y, t) mit dem geschätzten Bewegungsvektor Vt(vx, vy) im Bild (t+1), der Punkt B. Diesem Punkt B wird als Voraussagewert der Vektor Pt+1 zugeordnet, welcher folgende Komponenten hat:
• Px = Vx, und
• Py = Vy;
• seine räumliche Position im Bild t+1 ist:
• x + int(Vx)
• y + int(Vy),
• wobei x und y die Koordinaten des Punktes (x, y, t) mit dem Geschwindigkeitsvektor (Vx, Vy) sind. Das Zeitintervall zwischen zwei aufeinanderfolgenden Bildern wird gleich 1 gesetzt. Die Funktion "int" bezeichnet die ganze Zahl, die dem Klammerinhalt am nächsten liegt.
• Danach wird der Vektor Pt+1 in mindestens einer Iteration der WALKER- und RAO-Abschätzungsmethode angewandt, um nach Berichtigung den geschätzten Vektor Vt+1 am Punkt B(t + 1) zu erhalten.
• Vor Beginn der Projektion der Geschwindigkeitsvektoren besteht eine Initialisierungsphase darin, bei jedem Punkt (x, y, t + 1) des Zielbildes die folgenden Tabellen auszufüllen:
• Px(x, y, t + 1) = 0 (horizontale Komponente der Voraussage)
• Py(x, y, t + 1) = 0 (vertikale Komponente der Voraussage)
• DTD(x, y, t + 1) = 31 (absoluter DFD Wert, der auf 31 begrenzt ist).
• AXY (x, y, t + 1) = 0 (Bestätigungswert für die Validierung der Voraussage am laufenden Punkt)
• Die Begrenzung des DFD Wertes entspricht dem Zwang zum Erzielen eines begrenzten Leuchtdichtenabstandes zwischen dem vorhergehenden Quellpunkt und dem laufenden Zielpunkt. Die Zahl 31 ist kein restriktiver Erfindungswert, sondern sie entspricht einem korrekten experimentellen Wert gemäß der ersten Versuche, wenn man in Betracht zieht, daß die Leuchtdichte 255 verschiedene Werte annehmen kann.
• Eine zweite Begrenzung besteht darin, die Intensität der vorausgesagten und geschätzten Bewegungsvektoren auf einen Höchstwert zu begrenzen. Hierdurch werden Punkte mit schneller Bewegung aus dem Voraussage-/Korrekturprozeß für die Abschätzung des Bewegungsvektors der Bildpunkte eliminiert. In einer bevorzugten Ausführungsform der Erfindung werden die Koordinaten (vx, vy) der Bewegungsvektoren auf +/- 15 begrenzt.
• Sollte durch die Anwendung einer der zwei obigen Begrenzungen die Berechnung der Bewegungsvektorabschätzung für einen Bildpunkt unterbrochen werden, so würde der Bestätigungswert AXY für die Validierung der Voraussage am laufenden Punkt auf dem Wert Null verweilen. Die diesen Punkt betreffenden behelfsmäßigen Daten können somit nicht durch Abschätzung in Bewegungsrichtung festgestellt werden, dafür eventuell durch eine zeitliche bzw. räumliche Abschätzung, durch lineare Filtration oder durch Interpolation.
• Es ist jedoch zu bemerken, daß ein selber Punkt des Bildes t + 1 Quellpunkt für mehrere Zielpunkte des vorhergegangenen Bildes sein kann. In diesem Falle wird es für diesen Punkt nur dann keine Voraussage gemäß der Abschätzungsmethode in Bewegungsrichtung geben, wenn keiner der Quellpunkte eine für den Zielpunkt gültige Voraussage liefern kann.
• Der Simulationsalgorithmus des erfindungsgemäßen Verfahrens verwendet als Eingangsdaten die Koordinaten des Punktes (x, y, t) im Bild t, mit der geschätzten Geschwindigkeit (Vx, Vy) und der Intensität I(x, y, t), auch als Io gekennzeichnet.
• Das Ergebnis besteht darin, dem Punkt (x + int(Vx), y + int(Vy), t + 1) des Bildes t+1 eine vorausgesagte Geschwindigkeit zuzuordnen, die folgende Komponenten hat:
• Px(x + int(Vx), y + int(Vy), t + 1) = Vx
• Py(x + int(Vx), y + int(Vy), t + 1) = Vy.
• Dieser Auftreffpunkt hat die Intensität I(x + int(Vx), y + int(Vy), t + 1) , die mit I1 gekennzeichnet wird.
• Es wird sodann eine absolute versetzte Differenz als Funktion Io-I1 ermittelt.
• Der Algorithmus birgt drei Möglichkeiten in sich, genannt Bestätigung, Verwerfung und Mittelwert.
• Als Bestätigung ist die folgende Situation zu verstehen: wenn:
• Io - I1 < DTD(x + int(Vx), y + int(Vy), t + 1), dann gilt:
• Px(x + int(Vx), y + int(Vy), t + 1) = Vx(x, y, t)
• Py(x + int(Vx), y + int(Vy), t + 1) = Vy(x, y, t)
• DTD(x + int(Vx), y + int(Vy), t + 1) = Io -I1
• AXY(x t int(Vx), y + int(Vy), t + 1) = 1
• Die Vorschrift: DTD = Io - I1 bedeutet, daß der Wert Io - I1 , der kleiner ist als der ursprüngliche Inhalt von DTD, diesen Inhalt ersetzt.
• Der Bestätigungswert AXY nimmt den Wert 1 an, wenn eine Voraussage validiert wird.
• Als Verwerfung ist die folgende Situation zu verstehen: wenn:
• Io - I1 > DTD(x + int(Vx), y + int(Vy), t + 1), dann wird keine Tabelle verändert. Dieser Fall betrifft demnach diejenigen Projektionen des Geschwindigkeitsvektors, welche eine sehr schlechte Voraussage ergeben, weil die absolute, versetzte Differenz Io - I1 groß ist (größer als 31 im hier genannten Beispiel). Dieser Fall beträfft auch einen zweiten Kandidatenvektor, der verworfen wird, weil die absolute, versetzte Differenz, die vom besagten Kandidaten abgeleitet wird, größer ist als die eines ersten validierten Kandidaten (dieses Verfahren betrifft den Konflikt der multiplen Kandidaten an einem Punkt des Bildes t+1; s. weiter unten).
• Als Mittelwert ist die folgende Situation zu verstehen: wenn:
• Io - I1 = DTD(x + int(Vx), y + int(Vy), t + 1), dann wird der Vektor (Vx, Vy) mit dem Inhalt der Voraussage (Px(x + int(Vx), y + int(Vy), t + 1); Py(x + int(Vx), y + int(Vy), t + 1)), gemittelt. Das Ergebnis wird wieder am Punkt (x + int(Vx), y + int(Vy), t + 1) gespeichert. Der Bestätigungswert AXY(x + int(Vx), y + int(Vy), t + 1) wird auf 1 gesetzt. Der Mittelwert ist deshalb von Interesse, weil er die potentiellen Kandidaten in identischer Weise gewichtet, es sei denn, es treten drei (oder mehr) Kandidaten auf (dieser Fall ist statistisch so selten, daß er vernachlässigt werden kann).
• Eine vereinfachte Anwendung des Verfahrens besteht darin, den Ablauf an dieser Stelle abzubrechen. In diesem Falle kann die AXY-Tabelle verworfen werden.
• Fig. 5A, 5B stellen ein Übersichtsdiagramm des erfindungsgemäßen Verfahrens dar.
• Die Adresse des behandelten Punktes wird auf den Adressbus 49 weitergeleitet.
• Die Speichereinheiten der Datenspeicher 53, 54, 55, 56 und 58 berücksichtigen die folgenden Dynamiken und Genauigkeiten:
• Vx, Vy, Px, Py: +/- 15, Genauigkeit 1/8, also 8 Bits;
• DTD &le; 31: ganzer, positiver Wert, also 5 Bits;
• I: über 8 Bits codierte Intensität.
• In Bezug auf den Punkt (x, y, t) mit der Geschwindigkeit (Vx, Vy), finden alle Vorgänge im Bild t+1 am Punkt (x + int(Vx), y + int(Vy), t + 1) statt. Dementsprechend ist die Speicheradresse der validierten Daten durch x + int(Vx) und y + int(Vy) definiert.
• Ein als "Entscheidung" gekennzeichneter Block 50 verarbeitet die Werte Io - I1 sowie DTD(x + int(Vx), y + int(Vy), t + 1) gemäß der drei oben beschriebenen Situationen: Bestätigung, Verwerfung und Mittelwert. Eine "Bestätigung/Verwerfung" genannte Information 51 ermöglicht das Speichern oder nicht einer wiederaktualisierten DTD sowie der Komponenten Px und Py an der angegebenen Adresse.
• Eine als "Transfer/Mittelwert" gekennzeichnete Information 52 überschreibt den vorherigen Inhalt Px(x + int(Vx), y + int(Vy), t + 1) mit dem Kandidaten Vx. Gleiches findet zwischen Py und Vy statt. Es wird die halbe Summe zwischen dem vorherigen Inhalt Px und dem Kandidaten Vx gebildet, gleiches gilt für Py und Vy. Diese neuen Werte werden an der Adresse (x + int(Vx), y + int(Vy), t + 1) gespeichert (Stromkreise 59).
• Die Speicherkapazitäten richten sich nach den folgenden Nutzgrößen:
• Speicher I 53 (x, y, t + 1) --> 3l x 31, weil die Dynamik den Wert +/- 15 hat.
• Speicher Px 54 (x, y, t + 1) --> ein Bild
• Speicher Py 55 (x, y, t + 1) --> ein Bild
• Speicher DTD 56 (x, y, t + 1) --> 31 x N
• Speicher AXY 58 --> 1 Bit
• N ist die Anzahl der Punkte pro Bildzeile. Zu einem gegebenen Zeitpunkt ist nur ein Fenster 57 der Größe 31 x 31, welches auf den Punkt (x, y, t + 1) zentriert ist, zugänglich. Die DTD-Werte müssen jedoch über eine Länge N beibehalten werden, damit sie eventuell wiederverwendet werden können, ausgehend von einem anderen Punkt des Bildes t + 1. Insbesondere werden die DTD einer beliebigen Zeile L eventuell (als Funktion von Vx und Vy) adressiert, bis die Zeile L + 31 verarbeitet wurde.
Handhabung von Aussagenkonflikte in Bewegungsrichtung
• Drei Beispiele stellen Grenzfälle für die Anwendung des Bewegungsabschätzungsverfahrens in Bewegungsrichtung dar, für welche eine besondere Lösungsprozedur vorgesehen werden muß:
• - Existenz "multipler Projektionskandidaten A" an einem Punkt B(t + 1), daß heißt, Existenz mehrerer Bildquellpunkte A, deren geschätzter Bewegungsvektor am Punkt B des Bildes t + 1 endet;
• - Existenz von Bildpunkten B, die keinen Vorläufer im vorhergehenden Bild haben;
• - Handhabung der Bildränder.
• Die erste Konfliktart (mehrfache Kandidaten) wird dadurch gelöst, daß der Vektor, welcher eine minimale DFD ergibt, als Aussage ausgewählt wird. Gemäß einer bevorzugten Ausführungsform der Erfindung, die schon bei der Beschreibung der Abbildung 5 erwähnt wurde, und im Falle der Gleichheit zwischen zwei oder mehreren DFD, wird der Mittelwert der entsprechenden Kandidaten gebildet.
• Der zweite betrachtete Konfliktfall besteht in der Abwesenheit eines Kandidatenquellpunktes A für einen laufenden Punkt B des aktuellen Bildes.
• Das Verfahren läßt u. a. zwei Lösungsansätze für einen solchen Konflikt zu.
• Beim ersten Lösungsansatz wird ein vorausgesagter Vektor dem Punkt B durch räumliche Analyse der Umgebung des Punktes B im Bild t+1 und durch Vereinigung der Punkte eines selben Gegenstandes zugeordnet. Diese Lösung trägt effektiv zum Auffinden des wahren Geschwindigkeitsvektorenfeldes bei, sie ist jedoch schwer als Kompensation (beim Empfang) anwendbar, da die beim Empfang durchgeführte Interpolation eine Filtration in Bewegungsrichtung ist. Daraus ergeben sich Probleme, wenn es in der Bildebene zur Überlappung/Entflechtung zweier beweglicher Gegenstände oder zwischen einem Gegenstand und dem Bildhintergrund kommt.
• Die zweite Lösung, die bevorzugt eingesetzt wird, besteht darin, daß man um den kandidatlosen Punkt B herum die benachbarten Punkte sucht, welche einen vorausgesagten Vektor im Bild t + 1 besitzen. Unter diesen Vektoren wird derjenige zugeordnet, der für den laufenden Punkt B eine minimale DFD ergibt. Bei Gleichheit zwischen zwei oder mehreren DFD wird der Vektor mit dem kleinsten Modul gewählt, um jegliche Divergenzgefahr auszuschließen.
• Eine detaillierte Ausführungsform dieser Lösung wird weiter unten, mit Bezug auf die Fig. 6 und 7, vorgestellt.
• Aufgrund der Tatsache, daß die Punkt-für-Punkt Projektion des Bildes t auf das Bild t+1, welche außerdem in paralleler Richtung zum Geschwindigkeitsvektor des Ursprungspunktes erfolgt, nicht bijektiv ist, gibt es im Bild t + 1 Punkte ohne Voraussage Px, Py (AXY = 0).
• Diesen Punkten (x, y, t + 1) entspricht die Information:
• AXY (x, y, t + 1) = 0
• und nach der Initialisierungsphase des Systems:
• Px (x, y, t + 1) = 0
• Py (x, y, t + 1) = 0
• Daher ist die Annahme zulässig, gemäß welcher folgendes am Punkt (x, y, t + 1) gilt:
• AXY (x, y, t + 1) = 0
• Die Prozeduren, die angewandt werden, um diesem Punkt (x, y, t + 1) eine Voraussage zuzuordnen, sind folgende:
• 1) Orten der Punkte mit validierter Voraussage (AXY = 1) in der Umgebung 6l dieses Punktes
• 2) Überprüfen einer jeden am Punkt (x, y, t + 1) validierten Voraussage
• 3) Auswählen 79 der Voraussage, die eine minimale DFD ergibt.
• Die Umgebung 61 ist um den Punkt (x, y, t) zentriert und auf eine Größe von 3 x 3 begrenzt (Fig. 6). Die Kenntnis der folgenden Werte
• AXY (x - 1, y - 1, t + 1)
• AXY (x, y - 1, t + 1)
• AXY (x + 1, y - 1, t + 1)
• AXY (x - 1, y, t + 1)
• AXY (x + 1, y, t + 1)
• AXY (x - 1, y + 1, t + 1)
• AXY (x, y + 1, t + 1)
• AXY (x + 1, y + 1, t + 1)
• ermöglicht das Auflisten der Punkte, die eine vorher validierte Aussage besaßen (AXY = 1).
• Man betrachte einen dieser Punkte (i, j, t + 1), für welchen demnach Px(i, j, t + 1) und Py(i, j, t + 1) existieren; man kann dann folgende Berechnungen durchführen:
• - Io = I(x - Px(i, j, t + 1) , y - Py(i, j, t + 1), t)
• - I1 = I(x, y, t + 1)
• Io - I1
• Man bezeichne:
• IND = I(x, y, t + 1) - I(x, y, t)
• und: DR = 15 (maximales Modul eines Geschwindigkeitsvektors).
• Der Algorithmus gemäß Tabelle I ist aktiviert: Der Wert der Berechnung des Moduls DR ermöglicht die Auswahl des minimalen Wertes im Falle der Gleichheit.
• Ein Übersichtsdiagramm der Schaltkreise, die das Ausführen dieses Algorithmus ermöglichen, ist in Fig. 7 dargestellt.
• Der laufende Punkt, welcher der in Fig. 5 beschriebenen Verarbeitung entspricht, hat die räumlichen Koordinaten (x + 16, y + 16) im Bild t + 1. Um die Stabilität der Umgebung des Punktes (x, y, t+1) zu gewährleisten, darf diese Umgebung tatsächlich nicht mehr verändert werden, d.h., sie muß außer Reichweite der größten Verschiebung (+/- 15) sein. Daher hat der Datenspeicher AXY 60 die Kapazität 33 x N (Anzahl der Punkte pro Bildzeile).
• Wenn AXY(x, y, t + 1) nicht null ist, dann wird das System gem. Fig. 7 nie aktiviert.
• Wenn AXY(x, y, t + 1) null ist, so wird das System an einem Umgebungspunkt (i, j, t + 1) aktiviert falls AXY(i, j, t + 1) nicht null ist.
• Falls die Aktivierung verlangt wird, so werden in den Bildspeichern t und t + 1 70 die Adressen (x, y, t) und (x - Px(i, j, t + 1), y - Py(i, j, t + 1), t) für den ersten Speicher, bzw. (x, y, t + 1) für den zweiten Speicher, aufgerufen.
• Diese Zugänge liefern die Daten zum Berechnen von IND und Io - I1 .
• Im Entscheidungskreislauf 71 werden die Werte IND und Io - I1 , welche aus den entsprechenden Schaltkreisen 72 und 73 stammen, gemäß dem Algorithmus von Tabelle I verarbeitet.
• Eventuell wird Modul 74
• aufgerufen, um Gleichheitskonflikte zu lösen. TABELLE I
• Folgende Signale verlassen den Entscheidungskreislauf 71:
• * Signal "Austausch" 75, welches IND verändert bzw. unverändert läßt, in Abhängigkeit von Io - I1 ; das Gleiche gilt für Modul DR 74;
• * Signal "Kriterium" 76, welches den Vektor Px(i, j, t + 1), Py(i, j, t + 1) an die Adresse (x, y) der Datenspeicher 78 Px und Py weiterleitet oder nicht. Der durch den Auswahlschaltkreis 79 validierte Vektor entspricht dem Kriterium, gemäß welchem Io - I1 den Minimalwert annimmt;
• * die Adresse (x, y) des Datenspeichers AXY wird auf 1 gesetzt, sobald dem Punkt (x, y, t + 1) eine Voraussage zugeordnet wird 77.
• Es muß selbstverständlich Vorsorge getroffen werden für die erforderliche Verwaltung der Datenspeicher 70, Adressen für die Bilder t und t + 1, der Voraussagen-Datenspeicher Px und Py sowie des Datenspeichers AXY 60 (nicht dargestellt). In der Tat werden aus diesen verschiedenen Datenspeichern verschiedene Adressen gelesen, um ein gutes Funktionieren der Anordnung gemäß Fig. 7 zu gewährleisten.
• Im ersten Falle ist die Adresse:
• x + 16 + int(Vx)
• y + 16 + int(Vy) ohne die Bilddatenspeicher t und t+1 zu vergessen (s. Fig. 6).
• Im zweiten Fall wird der Datenspeicher AXY 60 an der Adresse (x, y) angesprochen und danach an den Umgebungspunkten, zuerst im Ablesemodus, dann im Überschreibmodus. Die Datenspeicher 78 Px und Py werden an der Adresse (x, y) angesprochen und die Bilddatenspeicher t und t + 1 70 jeweils an den Adressen (x, y, t), (x - Px(i, j, t + 1), y - Py (i, j, t + 1), t) bzw. (x, y, t + 1).
• Der letzte und dritte Fall der aufgeführten Konflikte, nämlich das Problem der Bildrandhandhabung, wird entweder durch Anwendung eines räumlichen Bildinterpolationsverfahrens gelöst, oder durch Anwendung des Multivoraus-Sagensystems der Erfindung.
Beschreibung des Multivoraussagensystems
• Es wird daran erinnert, daß der Algorithmus zur Bewegunsabschätzung durch die Formel dargestellt wird:
• Schätzwert E = Voraussage P + Korrekturfunktion Die Korrekturfunktion ist ein bekannter Ausdruck der Art Gewinn x DFD x räumlicher Gradient.
• Die Multivoraussage besteht darin, mehrere Voraussagen für Bewegungsvektoren parallel anzuwenden und danach die optimale Voraussage in Abhängigkeit eines Testes (Suchen des geringsten Fehlers bei der Bildrekonstruktion) zu wählen, und somit den besten Schätzwert zu erhalten. Anders gesagt: es werden mehrere Kandidaten für die Voraussage P herangezogen, und ihre relative Relevanz nach Berechnung des Schätzwertes E gemessen, damit der beste unter ihnen zur Auswahl kommt.
• Die zur Auswahl stehenden Voraussagen sind dreierlei Art:
• - räumliche Voraussagen;
• - zeitliche Voraussagen;
• - eine "räumlich-zeitliche" Voraussage in Bewegungsrichtung.
• In der Praxis sind zwei Verfahrensmuster denkbar, die jeweils in den Tabellen 2 und 3 dargestellt sind. In der Tabelle 2 werden die n parallelen Voraussagen gemäß der WALKER- und RAO-Methode verarbeitet, um zu einen Schätzwert 1, 2, 3..., n zu gelangen, durch Anwendung einer Korrekturfunktion.
• Ausgehend von jedem Schätzwert wird, für jeden laufenden Punkt des laufenden Bildes, der entsprechende Quellpunkt gesucht. Nach Kompensation wird die DFD (Abstand der Leuchtdichten) zwischen dem berechneten Punkt und dem reellen Punkt des Quellbildes gemessen.
• Gewissermaßen wird beim Sender ein Vergleich durchgeführt, und zwar zwischen dem Ergebnis, das beim Empfänger erzielt werden soll (rekonstruiertes Bild) und der Realität (nicht transmittiertes, oder nur teilweise transmittiertes Quellbild). Erfindungsgemäß erfolgt die Auswahl des besten Schätzwertes des Geschwindigkeitsvektors am Punkt (x, y, t) durch Feststellung der minimalen DFD.
• Bei einer anderen Ausführungsform, die einer echten Multivoraussage entspricht (Tabelle 3), wird die DFD unmittelbar für jede Voraussage berechnet. Danach erfolgt die Auswahl der besten Voraussage durch Suchen der minimalen DFD. Die Berechnung des Schätzwertes des Geschwindigkeitsvektors am Punkt (x, y, t) erfolgt auf der alleinigen Basis dieser Voraussage durch Anwendung der Korrekturfunktion von WALKER und RAO. Dieses zweite Verfahrensmuster ist scheinbar einfacher, da nur eine Korrekturfunktion berechnet wird. In der Tat hat es sich jedoch bei den durchgeführten Versuchen als weniger leistungsfähig als das erste Verfahrensmuster erwiesen; dennoch birgt es einige interessante Punkte in sich.
• In der folgenden Beschreibung bezieht sich der Ausdruck Multivoraussage tatsächlich auf die Ausführungsform gemäß Tabelle 2.
• Das Übersichtsdiagramm der Fig. 8 zeigt, wie die erfindungsspezifische Multivoraussagenlogik 81 in einem Bildcodierungsprozeß eingefügt wird.
• Wie bereits für Tabelle 2 erläutert, werden parallel zueinander eine oder mehrere räumliche Voraussage(n) 82, eine oder mehrere zeitliche Voraussage(n) 83, und eine Voraussage in Bewegungsrichtung 84, durchgeführt. Diese Voraussagen werden durch die Schätzfunktionselemente 85 verarbeitet und die beste Voraussage wird bei 86 gemäß dem Kriterium der minimalen DFD ausgewählt.
• Das Multivoraussagen-Schätzfunktionselement 81 kann wahlweise mit einer zusätzlichen Schätzungsstufe 87 ausgerüstet werden. Der Schritt 87 besteht in einer zusätzlichen Iteration der WALKER- und RAO-Methode, ausgehend von der in 86 berechneten DFD. Diese zusätzliche Iteration ist vorteilhaft, wenn die Abschätzung des Geschwindigkeitsvektors weiter verfeinert werden soll. Darüber hinaus ist sie hinsichtlich der Rechnerkapazität nicht teuer, angesichts der Tatsache, daß in der Schätzungsgleichung nach WALKER und RAO die Berechnung der DFD die aufwendigste Verarbeitung erfordert. Da die DFD bei Schritt 86 zur Verfügung steht, kann man folgerichtig behaupten, daß die zusätzliche Abschätzung 87 eine sinnvolle Option darstellt.
• Das Übersichtsdiagramm aus Fig. 8 zeigt auch die Anwendung der Pufferdatenspeicher 88 und 89, welche die Voraussageschritte 82, 83 und 84 mit Daten versorgen. Datenspeicher 88 speichert die laufenden Punkte des laufenden Bildes und versorgt den Block für räumliche Voraussagen 82 mit Daten. Im Datenspeicher 89 werden die Koordinaten der Geschwindigkeitsvektoren des vorangegangenen Bildes gespeichert. Der Ausgang dieses Speichers ist einerseits mit dem Block für zeitliche Voraussagen 83 und andererseits mit dem Block für Voraussagen in Bewegungsrichtung 84 über die Schritte 90 und 91 verbunden. Bei Schritt 90 wird das vorangegangene Bild auf das laufende Geschwindigkeitsvektorenbild projiziert, gemäß dem oben beschriebenen Verfahren der Abschätzung in Bewegungsrichtung. Schritt 91 entspricht der Konfliktverwaltungsstufe, die bereits diskutiert wurde.
• Fig. 9 zeigt im Detail eine mögliche Anordnung der verschiedenen Schaltkreise, aus denen sich das Multivoraussagen-Bewegungsabschätzungssystem der Erfindung zusammensetzt.
• Als Kandidaten stehen die folgenden Voraussagen zur Verfügung (x, y, t entspricht dem Punkt mit den Raumkoordinaten x, y und der zeitlichen Komponente t):
• P1 (x, y, t) = E (x - 1, y - 1, t)
• P2 (x, y, t) = E (x, y - 1, t)
• P3 (x, y, t) = E (x + 1, y - 1, t)
• P4 (x, y, t) = E (x, y, t - 1)
• P5 (x, y, t) = PM (x - 1, y, t)
• P6 (x, y, t) = PM (x + 1, y, t)
• P7 (x, y, t) = PM (x - 1, y + 1, t)
• P8 (x, y, t) = PM (x, y + 1, t)
• P9 (x, y, t) = PM (x + 1, y + 1, t)
• P10 (x, y, t) = PM (x, , t) ..... Bezeichnungen:
• P1 (x, y, t) ist Voraussagekandidat für die Abschätzung Ei des Punktes (x, y, t)
• E (k, l, in) ist die vorher berechnete Abschätzung am Punkt (k, l, m)
• PM (n, p, t) ist die Voraussage in Bewegungsrichtung, welche dem Punkt (n, p, t) zugeordnet wird.
• Man kann die Zahl der Kandidaten erhöhen, um möglicherweise das Ergebnis zu verbessern, die Einschränkungen der praktischen Ausführung erfordern jedoch eine Kürzung dieser Zahl. Es wurden zufriedenstellende Ergebnisse alleine mit den Voraussagen P2, P5, P6, P8 und P10 erzielt.
• Jede Voraussage Pi bestimmt eine Korrekturfunktion und deren Kombination ergibt einen Schätzwert Ei. Um den besten Schätzwert des Bewegungsvektors am Punkt (x, y, t) zu wählen, berechnet man die einer jeden potentiellen Abschätzung zugeordneten DFD.
• Das Auswahlkriterium besteht im Beibehalten des Schätzwertes, für welches die DFD minimal ist. Im Konfliktfalle fällt die Wahl vorzugsweise auf P10, oder P8, oder P6, oder P5. Jeder Pfad 1 bis n besitzt einen Rechenschaltkreis für die Korrekturfunktion 100. Jeweils ein Ausgang dieser Rechenschaltkreise ist mit einem Additionsschaltkreis 101 verbunden, der wiederum am Eingang zusätzlich den Wert der Voraussage Pi aufnimmt. Die Additionsschaltkreise 101 geben an ihren Ausgängen jeweils einen Schätzwert Ei parallel zueinander weiter. Jeder Schätzwert Ei wird einem Rechenschaltkreis 102 zur Berechnung der DFD zugeführt, d. h., den Leuchtdichtenabstand zwischen dem aus dem Schätzwert Ei rekonstituierten Bild und dem reellen Bild. Jeder Schaltkreis 102 berechnet ebenfalls den Gewinn und den Gradienten des Schätzwertes, im Sinne von WALKER und RAO.
• Somit besitzt das System die folgende Arbeitslogik:
• - die in den Schaltkreisen 102 berechneten DFD werden im Schaltkreis 103 verglichen, um den Index des Schätzwertes P&sub1;. . Pn zu finden, der die minimale DFD ergibt. Dieser Index wird über 104 weitergeleitet bis zum Auswahlschaltkreis 105, der am Eingang die Schätzwerte E&sub1;,...En aufnimmt und am Ausgang den gewählten Schätzwert Es herausgibt.
• Dieser Schätzwert Es wird dann im Schaltkreis 108 einer weiteren Iteration nach der WALKER- und RAO-Methode unterworfen, ausgehend von den Gewinnwerten, den Gradientwerten und den DFD, die in den Schaltkreisen 102 berechnet wurden. Schließlich gibt Schaltkreis 108 am Ausgang den endgültigen Schätzwert des Geschwindigkeitsvektors heraus.
• Die durchgeführten Versuche haben gezeigt, daß in mehr als 99 % der Fälle die Voraussage in Bewegungsrichtung den besten Schätzwert für den Geschwindigkeitsvektor ergibt. TABELLE 2 MULTIVORAUSSAGENABSCHÄTZUNG Voraussage Korrekturfunktion Schätzwert DFD Auswahlkriterium für den besten Schätzwert = DFDmin Schätzwert des Geschwindigkeitsvektors am Punkte (x, y, t) TABELLE 3 TATSÄCHLICHE MULTIVORAUSSAGE Voraussage DFD DFD min Korrekturfunktion Schätzwert des Bewegungsvektors am Punkte (x, y, t)

Claims (12)

1. Verfahren zur Bewegungsabschätzung für Sequenzen elektronischer Bilder, das insbesondere dazu bestimmt ist, jedem elektronischen Bildpunkt einen Bewegungsvektor in der Bildebene zum Zeitpunkt t zuzuteilen, mit dem Ziel, beispielsweise einerseits eine Verarbeitung optimierter Kompression des Bildsignals durchzuführen und/oder andererseits eine Näherungsprojektion der Position jedes Bildpunktes t im nachfolgenden Bild zum Zeitpunkt (t + 1) zu ermöglichen, wobei der laufende Bewegungsvektor eines aktuellen Punktes (B, Fig. 4) zum Zeitpunkt t gemäß einem algorithmischen Prozeß der Prädiktion/Korrektur berechnet wird, der darin besteht, als Ausgangshypothese der Berechnung einen vorhergesagten Bewegungswert ( t+1) zu nehmen, der anschließend mittels des Prozesses gemäß einem Korrekturverfahren durch Kriterienoptimierung korrigiert wird, dadurch gekennzeichnet, daß

der vorhergesagte Bewegungswert ( t+1) des aktuellen Punktes (B) der Wert des ursprünglichen Bewegungsvektors ( t) ist, der einem Ursprungs-Bildpunkt (A) zum Zeitpunkt (t - 1) zugeordnet ist, wobei der aktuelle Punkt (B) die Näherungsprojektion des Ursprungspunktes (A) gemäß dem ursprünglichen Bewegungsvektor ( t) ist.

2. Verfahren gemäß Anspruch 1, dadurch gekennzeichnet, daß der algorithmische Prozeß der Prädiktion/Korrektur ein Prozeß vom Typ "rekursiv durch Punkte" und vorzugsweise der Prozeß von WALKER und RAO oder der Prozeß von ROBERT CAFFORIO und ROCA ist.

3. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Näherungsprojektion des Ursprungspunktes darin besteht, als projizierten aktuellen Punkt eines der nächsten Pixel zu wählen.

4. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß alle Ursprungspunkte des Bildes (t - 1) einen geschätzten Bewegungsvektor aufweisen, daß man jeden der Ursprungspunkte auf deren aktuelle Zielpunkte des Bildes t projiziert, und daß man den geschätzten Bewegungsvektor jedes der aktuellen Zielpunkte gemäß dem Prädiktion/Korrektur-Prozeß berechnet.

5. Verfahren gemäß Anspruch 1 zur Bewegungsabschätzung für Sequenzen elektronischer Bilder, das insbesondere dazu bestimmt ist, jedem elektronischen Bildpunkt einen Bewegungsvektor in der Bildebene zum Zeitpunkt t zuzuteilen, mit dem Ziel, beispielsweise einerseits eine Verarbeitung optimierter Kompression des Bildsignals durchzuführen und/oder andererseits eine Näherungsprojektion der Position jedes Bildpunktes zum Zeitpunkt (t + 1) zu ermöglichen,

wobei der laufende Bewegungsvektor eines aktuellen Punktes zum Zeitpunkt t gemäß einem algorithmischen Prozeß der Prädiktion/Korrektur berechnet wird, der darin besteht, als Ausgangshypothese der Berechnung einen vorhergesagten Bewegungswert zu nehmen, der anschließend mittels des Prozesses gemäß einem Korrekturverfahren durch Kriterienoptimierung korrigiert wird,

dadurch gekennzeichnet, daß das Verfahren parallel wenigstens zwei Bewegungsabschätzungsberechnungen durchführt, ausgehend von zwei vorhergesagten Bewegungswerten des aktuellen Punktes, wobei die vorhergesagten Werte wenigstens eine räumlich-zeitliche Vorhersage auf der Bewegungsachse und wenigstens einen der folgenden Werte umfassen:

wenigstens eine räumliche Vorhersage von Bewegungen; und wenigstens eine zeitliche Vorhersage von Bewegungen; und daß das Verfahren die Abschätzung des Geschwindigkeitsvektors gemäß einem Entscheidungsverfahren durch Kriterienoptimierung wählt.

6. Verfahren gemäß Anspruch 1 zur Bewegungsabschätzung für Sequenzen elektronischer Bilder, das insbesondere dazu bestimmt ist, jedem elektronischen Bildpunkt einen Bewegungsvektor in der Bildebene zum Zeitpunkt t zuzuteilen, mit dem Ziel, beispielsweise einerseits eine Verarbeitung optimierter Kompression des Bildsignals durchzuführen und/oder andererseits eine Näherungsprojektion der Position jedes Bildpunktes zum Zeitpunkt (t + 1) zu ermöglichen,

wobei der laufende Bewegungsvektor eines aktuellen Punktes zum Zeitpunkt t gemäß einem algorithmischen Prozeß der Prädiktion/Korrektur bereichnet wird, der darin besteht, als Ausgangshypothese der Berechnung einen vorhergesagten Bewegungswert zu nehmen, der anschließend mittels des Prozesses gemäß einem Korrekturverfahren durch Kriterienoptimierung korrigiert wird,

dadurch gekennzeichnet, daß

das Verfahren wenigstens zwei unterschiedliche vorhergesagte Bewegungswerte für jeden aktuellen Punkt in Betracht zieht, wobei vorhergesagten Werte wenigstens eine räumlich-zeitliche Vorhersage auf der Bewegungsachse und wenigstens einen der folgenden Werte umfassen:

wenigstens eine räumliche Vorhersage von Bewegungen; und wenigstens eine zeitliche Vorhersage von Bewegungen; und daß das Verfahren einen vorhergesagten Bewegungswert gemäß einem Entscheidungsprozeß durch Kriterienoptimierung wählt und den geschätzten Bewegunsvektor des aktuellen Punktes gemäß dem algorithmischen Prozeß der Prädiktion/Korrektur berechnet.

7. Verfahren zur Bewegungsabschätzung gemäß einem der Ansprüche 1, 5 oder 6, dadurch gekennzeichnet, daß jedem der aktuellen Bildpunkte, die nicht mit einem abgeschätzten Bewegungsvektor versehen sind, der Bewegungsvektor von den Punkten zugeteilt wird, die dem aktuellen Punkt nahe sind, wodurch die getreueste Wiederherstellung bezüglich des reellen aktuellen Punktes erhalten werden kann.

8. Verfahren nach einem der Ansprüche 1, 5 und 6, dadurch gekennzeichnet, daß das Optimierungskriterium die Leuchtdichten-Abweichung DFD von WALKER und RAO ist.

9. Verfahren nach einem der Ansprüche 5 oder 6, dadurch gekennzeichnet, daß wenigstens einer der vorhergesagten Werte der Bewegungsvektoren für den aktuellen Punkt eine Vorhersage in Bewegungsrichtung eines Punktes ist, der zur Gruppe von acht Punkten gehört, die den aktuellen Punkt in dem aktuellen Bild umgeben.

10. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß die vorhergesagten, parallel gelieferten Werte wenigstens die folgende Werte umfassen:

- P2 (x,y,t) = E (x,y - 1, t),

- P5 (x,y,t) = PM (x - 1, y,t),

- P6 (x,y,t) = PH (x + 1, y,t),

- P8 (x,y,t) = PH (x, y + 1, t),

- P10 (x,y,t) = PM (x,y,t),

mit:

E(k,l,m): vorher berechnete Abschätzung im Punkt (k, l, m);

PH (n,p,t): zugeteilte Vorhersage in Bewegungsrichtung im Punkt (n,p,t).

11. Kodierungsverfahren von Sequenzen elektronischer Bilder, das einen Kodierungsprozeß durch Bewegungsabschätzung gemäß einem der Ansprüche 1 bis 10 umfaßt, dadurch gekennzeichnet, daß

das Kodierungsverfahren auch Hittel zum Einsatz eines parallelen Kodierungsprozesses durch lineares Abtastfilter einschließt,

und daß das Kodierungsverfahren Vergleichs- und Auswahlmittel des besten Kodierungsprozesses, der die getreueste Bildwiederherstellung ermöglicht, umfaßt.

12. Kodierungsverfahren von Sequenzen elektronischer Bilder, das einen Kodierungsprozeß durch Bewegungsabschätzung gemäß einem der Ansprüche 1 bis 10 umfaßt, dadurch gekennzeichnet, daß

das Kodierungsverfahren auch Hittel zum Einsatz eines parallelen Kodierungsprozesses durch lineares Abtastfilter einschließt,

und daß die Mittel zum Einsatz des Kodierungsprozesses durch Bewegungsabschätzung festlegen, ob eher eine Kodierung durch lineares Abtastfilter, insbesondere im Falle einer festen Zone oder Zone mit schneller Mobilität, angewandt werden soll oder nicht.