DE3036770C1

DE3036770C1 - Verfahren zur Schätzung der Verschiebung und/oder Geschwindigkeit von Objekten in Video-Szenen

Info

Publication number: DE3036770C1
Application number: DE3036770A
Authority: DE
Inventors: Arun Narayan 07747 Matawan N.J. Netravali; John David 07747 Aberdeen N.J. Robbins
Original assignee: Western Electric Co Inc
Current assignee: AT&T Corp
Priority date: 1979-03-16
Filing date: 1980-02-25
Publication date: 1983-12-08
Also published as: CA1143827A; US4218703A; WO1980001977A1; JPS56500115A; GB2060309B; GB2060309A

Description

Gebiet der Erfindung

Die Erfindung betrifft eine Vorrichtung zur Erzeugung eines Schätzwertes für die Verschiebung eines Objektes in einer Videoszene zwischen einem früheren und einem augenblicklichen Bild mit Schaltungen zur Berechnung eines ersten Schätzwertes für die Verschiebung unter Verwendung der Bildintensitätsdifferenz zwischen wenigstens einem Bildelement im augenblicklichen Bild und einem räumlich entsprechenden Bildelement im vorhergehenden Bild.

Beschreibung des Standes der Technik

Eine Geschwindigkeits- und Verschiebungsschätzung hat sich in vielen Anwendungen als zweckmäßig erwiesen, und zwar einschließlich von Nachführ- und Überwachungssystemen, bei der Auswertung von fotografischen Aufnahmen, die von Satelliten aus gemacht worden sind, sowie bei der wirksamen Codierung von sich bewegenden Bildfolgen für die Übertragung und/ oder Speicherung. Ein Verfahren zur Messung der Geschwindigkeit ist in Verbindung mit einem Voraussage-Videocodierer in der DE-PS 20 62 922 beschrieben. Dort wird die Intensität einer bestimmten Bildstelle in einem augenblicklichen Bild (Rahmen) unter Verwendung einer Folge von Korrektoren mit der intensität einer Folge von verschobenen Bildstellen in einem vorhergehenden Bild korreliert. Die Korrelator-Ausgangssignale werden dann als Zwischenbild-Intensitätskorrespondenz zwischen anderen, sich bewegenden Stellen im Bild integriert und ausgewertet. Dieser Lösungsversuch für die Geschwindigkeitsfeststellung hat sich als unbequem herausgestellt, da viele Multiplikationen für jedes sich bewegende Bildelement erforderlich waren. Wenn beispielsweise die Geschwindigkeit im Bereich zwischen 0 und 4 Pels ( = Bildelemente von Picture Element) je Rahmen (Pef von Picture Elements Per Frame) mit einer Genauigkeit von 0,25 Pef festgestellt werden soll, ist für jede der 1089 möglichen 1/4-Element-Verschiebungen ein Bewegungsbereich-Korrelationskoeffizient erforderlich. Es ist offensichtlich, daß eine größere Genauigkeit oder ein größerer Geschwindigkeitsbereich noch größere Verarbeitungskapazitäten erforderlich machen würde.

Eine wesentliche Verringerung für die Anzahl der beim bekannten Verfahren erforderlichen Berechnungen ist durch ein späteres Geschwindigkeitsschätzverfahren ermöglicht worden. Dieses spätere Verfahren beruht auf der Erkenntnis, daß die Größe des Bilddifferenzsignals (Intensitätsdifferenz einer bestimmten Bildstelle zwischen einem Bild und dem nächsten Bild), das von einem sich bewegenden Objekt erzeugt wird, eine Funktion seiner Geschwindigkeit und

^b5 außerdem der Größe des Objekts und der Anzahl von Einzelheiten ist, die das Objekt enthält. Da außerdem die Größe und Einzelheiten zur Größe des Elementoder Zeilendifferenzsignals (Differenz der Intensität

zwischen zwei bestimmten Stellen im gleichen Bild = Rahmen) in Beziehung stehen, das durch das Objekt erzeugt wird, läßt sich ein von der Größe und den Einzelheiten im wesentlichen unabhängiger Schätzwert für die Geschwindigkeit dadurch erhalten, daß die Bilddifferenz mit der Element- oder Zeilendifferenz normiert wird.

Mathematisch ist die von Limb und Murphy beschriebene Verschiebungsberechnung (für die horizontale oder x-Richtung) gegeben durch:

Σ (FDIF), · Sgn (EDIF),

(D

15

wobei FDIF die Bild- oder Rahmendifferenz (von Frame Difference), EDIF die Elementdifferenz sind und die Summierung über diejenigen Elemente im Bild durchgeführt wird, für die FDIF oberhalb eines Schwellenwertes liegt, wodurch ein sich bewegender Bereich angegeben wird. Zur Berechnung von Vy (Verschiebung in der vertikalen Richtung) erfolgt eine entsprechende Berechnung unter Verwendung der Zeilendifferenz LDlF anstelle der Bilddifferenz EDlF. Die Geschwindigkeit kann dann aufgrund geeigneter Vektorkombinationen von Vx, Vy und Vi berechnet werden.

Dieses spätere Verfahren führt zwar zu weniger Berechnungsvorgängen als beim früheren Verfahren, es jo beruht aber auf der Vereinfachung einer Taylor-Reihen entwicklung, die annimmt, daß Vx klein war. Wenn jedoch Vx groß ist, wird die Taylor-Annäherung ungenau, wodurch der Verschiebungsschätzwert schwerwiegend beeinträchtigt wird. Außerdem liefert dieses Verfahren gelegentlich unbefriedigende Ergebnisse in Szenen mit mehreren, sich bewegenden Objekten.

Im Hinblick auf die vorstehenden Ausführungen hat die Erfindung generell zum Ziel, Mittel und ein Verfahren zur genaueren Bestimmung der Verschiebung und/oder Geschwindigkeit von sich bewegenden Obiekten in Videoszenen oder ähnlichem bereitzustellen. Das Verfahren muß sich an Bilder mit Bereichen unterschiedlicher Bewegung anpassen und sich so verwirklichen lassen, daß es nicht zu kompliziert oder aufwendig wird.

Das Problem -wird erfindungsgemäß mit einer Vorrichtung zur Erzeugung eines Schätzwertes für die Verschiebung eines Objektes in einer Videoszene zwischen einem früheren und einem augenblicklichen Bild dadurch gelöst, daß die Vorrichtung eine Aktualisierungsschaltung zur wiederholten Aktualisierung des ersten Verschiebungsschätzwertes unter Verwendung der Intensitätsdifferenz zwischen dem wenigstens einen Bildelement im augenblicklichen Bild und einer Stelle im vorhergehenden Bild aufweist, die gegen das augenblickliche Bildelement um den ersten Verschiebungsschätzwert verschoben ist. Entsprechend der Erfindung wird die Verschiebung eines Objektes in einer Videoszene unter Verwendung des vorhergehenden Verschiebungsschätzwertes zur Aktualisierung des augenblicklichen Verschiebungsschätzwertes wiederholt bestimmt. Die Wiederholung kann für jedes Bildelement, für eine Gruppe von Bildelementen oder für ein vollständiges Feld oder ein vollständiges Bild (Rahmen) durchgeführt werden. Tatsächlich können in gewissen Fällen Schätzwerte wiederholt für ein gegebenes Bildelement erstellt werden. Die wiederholende oder rekursive Art entsprechend der Erfindung ist gekennzeichnet durch einen Rückführungsweg zwischen dem Ausgang des Systems (der die Verschiebung angibt) und dem System selbst derart, daß der Fehler zwischen jedem aufeinanderfolgenden Verschiebungsschätzwert und der tatsächlichen Verschiebung im Idealfall sich dem Wert Null nähert

Entsprechend der Erfindung wird die Genauigkeit des Verschiebungsschätzwertes wesentlich verbessert Dadurch wird wiederum die Unterscheidung zwischen sich bewegenden Objekten und dem unbedeckten Hintergrund im verarbeitenden Bild ermöglicht und kann zu einer verbesserten Codiererkonstruktion führen.

Die rekursiven Verfahren nach der vorliegenden Erfindung lassen sich leicht mit einer Anzahl von Ausführungsbeispielen verwirklichen, die nicht übermäßig kompliziert oder aufwendig sind.

Beschreibung der Zeichnungen

Die Erfindung soll anhand der nachfolgenden, ins einzelne gehenden Beschreibung in Verbindung mit den Zeichnungen beschrieben werden. Es zeigt

Fig. Γ das Blockschaltbild einer Vorrichtung zur wiederholten Berechnung eines Schätzwertes für die horizontale Komponente einer Verschiebung bei einer Anzahl von Bildern entsprechend der Erfindung,

F i g. 2 die räumlichen Stellen, die beim für die Vorrichtung nach Fig. 1 benutzten Verfahren beteiligt sind,

F i g. 3 das Blockschaltbild eines weiteren Ausführungsbeispiels für eine Vorrichtung zur Berechnung der Verschiebung nach der Erfindung.

Die Ableitung der oben angegebenen Gleichung (1) ist für das Verständnis der vorliegenden Erfindung von Bedeutung. Nimmt man an, daß jedes Bild (= Rahmen) der Videoinformation entlang einer Vielzahl von im allgemeinen parallelen, horizontalen Zeilen abgetastet wird und daß die Lage eines Punktes innerhalb des Bildes entweder in Form üblicher rechtwinkliger Koordinaten (x.y)oder in Form eines zweidimensionalen Vektors x_ ausgedrückt werden kann, dann läßt sich die Intensität eines bestimmten Punktes im Bild darstellen als I(x, i^zum Zeitpunkt rund I(x, t-τ) für das vorhergehende Bild angeben, wobei τ die Zeit zwischen zwei Bildern ist. Wenn sich ein Objekt innerhalb des Bildes translatorisch bewegt und für den Augenblick ein unbedeckter Hintergrund im Bewegungsbereich unbeachtet bleibt, dann hat jeder Punkt im augenblicklichen Bild eine Intensität, die der Intensität eines bestimmten (üblicherweise verschiedenen) Punktes im vorhergehenden Bild entspricht. Demgemäß gilt:

l(x-D, t-τ)

wobei Dder Translationsvektor für das Objekt während des Intervalls τ zwischen den Bildern ist.

Traditionell wird das Bilddifferenzsignal FDIF an der Stelle λ- angegeben durch:

FDIV(x)= l(x, t)-IQc, t-τ) (3a)

wodurch angegeben wird, daß FDIF die Intensitätsdifferenz an einer festen Stelle χ für ein Zeitintervall τ ist. Die gleiche Differenz läßt sich jedoch mit räumlichen Ausdrücken angeben zu:

FDIF = IQc. I)- IQc+ D, t)

(3b)

da die Intensität der Stelle x-t- D zum Zeitpunkt t gleich der Intensität an der Stelle χ im vorhergehenden Bild

(Zeitpunkt t-τ) angenommen wird.

Gleichung (3b) läßt sich für kleine D mit Hilfe einer Taylor-Reihenentwicklung im Bereich von x. schreiben als:

FDIF (x) = ~D^TVl(x, t) + Terme höherer (4) Ordnungen für D

wobei Vder Gradient mit Bezug auf χ und der obere Index T eines Vektors dessen Transposition angeben. Wenn die translatoriüche Bewegung des Objektes über den gesamten Bewegungsbereich (mit Ausnahme des unbedeckten Hintergrundes) konstant ist und die Terme höherer Ordnung für D vernachlässigt werden können, dann lassen sich beide Seiten der Gleichung (4) über den gesamten Bewegungsbereich summieren, und man erhält einen Schätzwert D für die translalorische Bewegung wie folgt:

Σ FDIF Qc) ■ Vorz. (EDIF Qc))

Σ I EDIF(A)I
Σ FDIF Qc) ■ Vorz. (LDIF Qc))

LDIFCx)I

(5)

[0, wenn ζ = 0

Vorz. (z) = { ζ . (6)

U—r im anderen Fall

Gleichung (5) ist identisch mit einer der von Limb und Murphy angegebenen Gleichungen und gibt an, daß V7 ein Vektor der Element- und Zeilendifferenzen (EDIF bzw. LDlF) sein kann, wenn die Intensität des Bildes in einem diskreten Gitter verfügbar ist, wie dies dann gilt, wenn die Intensität abgetastet wird. Der obere Term in Gleichung (5) bezieht sich auf die Verschiebung in der horizontalen Richtung, während der untere Term sich auf die vertikale Richtung bezieht.

10 Wie oben angegeben, ist der Schätzwert für Q nur so lange gültig, wie D klein ist. Wenn D ansteigt, wird die Qualität der Taylor-Reihenentwicklung schlecht. Entsprechend der Erfindung wird dies durch eine Linearisierung der Intensitätsfunktion im Bereich eines Anfangsschätzwertes von D überwunden. Demgemäß wird für das /-te Bild der Verschiebungsschätzwert Ώ dadurch gewonnen, daß die Intensitätsfunktion um den Verschiebungsschätzwert für das vorhergehende ((i— l)-te) Bild herum linearisiert wird. Dieses Verfahren führt zur folgenden Rekursion:

+ U¹

(7)

wobei /)' ' ein Anfangsschätzwert für Z)' und U' der auf den neuesten Stand gebrachte Wert (Aktualisierungswert) von Ζ)'¹ sind, der den Wert genauer macht, d. h. ein Schätzwert von D-D'~^x.
Es wird jetzt die Größe DFD Qc, Ö'~^l) definiert, die die verschobene Bilddifferenz (DFD von Displaced Frame Difference) genannt wird und analog dem in den Gleichungen (3 a) und (3 b) verwendeten Wert FDIF(X) ist:

25 DFD Qc, Ζ)'"¹) - IQc, t) - /(X-Zr¹, t-τ) (8)

Aus Gleichung (8) erkennt man, daß DFD anhand von zwei Größen definiert ist:

(a) die räumliche Stelle x, an der die_ Auswertung

stattfindet, und (b) die Verschiebung D-¹, mit der

ausgewertet wird. Offensichtlich wird im Fall eines

zweidimensionalen Gitters diskreter Abtastwerteein Interpolationsprozeß zur Auswertung von /(*-/>-',

t-τ) für nicht ganzzahlige Werte vor, />-' benutzt.

Entsprechend der Definition hat der Wert DFD die

Eigenschaft, daß er auf Null konvergiert, wenn £> zur

tatsächlichen Verschiebung D des Objektes konvergiert.

Außerdem ist DFD = FDIF, wenn Z>-'«0.

DFD läßt sich auf ähnliche Weise wie oben ausdrucken zu:

DFD(x,D'-') = /(x, t) - IQc+D-U'-^]), t) = -(D-D'"¹ )^rV/(x,/) +Terme höherer Ordnung

(9)

Läßt man Ausdrücke, höherer Ordnung außer Acht und benutzt man Annäherungen ähnlich denen für Gleichung (5) so ergibt sich ein Schätzwert D-D'~\ der in Kombination mit Gleichung (7) ergibt:

Σ DFD (χ, Ö'~^]) ■ Vorz. (EDIF Qc))

Σ I EDIF (χ) I

Σ DFD (χ, Ρ'"¹) · Vorz. (LDIF Qy))

ΣI LDIF Cx) I

In Gleichung (10) werden die Summierungen über den gesamten Bewegungsbereich durchgeführt

Der obere Ausdruck in Gleichung (10) betrifft die Verschiebung in horizontaler Richtung und der untere Ausdruck die Verschiebung in vertikaler Richtung. Aus Gleichung (10) ergibt sich, daß entsprechend der vorliegenden Erfindung jeder Verschiebungsschätzwert eine Aktualisierung des vorhergehenden Schätzwertes ist und den vorhergehenden Schätzwert zur Durchführung der Aktualisierung benutzt Zu Anfang ist für D'-¹ = 0, DFD = FDIF. Danach wird Z>" unter Verwen- c> dung von />'-' sowie eines Korrekturterms aktualisiert, der eine Funktion von (a) DFD und EDIF für die ^-Richtung und von (b) DFD und LDIF für die (10)

y-Richtung ist Anders gesagt, die Aktualisierung ist eine Funktion des vorhergehenden Verschiebungsschätzwertes, der zur Berechnung einer verschobenen Bilddifferenz benutzt wird, welche dann normiert wird, um örtlichen Intensitätsschwankungen zwischen dem verarbeiteten Element und benachbarten Bildelementen Rechnung zu tragen.

Ein erstes Ausführungsbeispiel der vorliegenden Erfindung, welche die im oberen Ausdruck in Gleichung (10) mit Bezug lediglich auf die Verschiebung in der x-Richtung verwirklicht ist in Form eines Blockschaltbildes in Fig. 1 gezeigt Eingangssignalabtastwerte, die je die Intensität eines Bildes an einer bestimmten Stelle (Pel) innerhalb des Bildes darstellen, werden an eine

Eingangsleitung 101 angelegt. Diese Abtastwerte können durch übliche Abtastvorrichtungen gewonnen werden, die dem Fachmann bekannt sind, oder irgendwelche anderen Einrichtungen, die so ausgelegt sind, daß sie Intensitätsinformationen für eine Folge von Pel-Stellen liefern. Es wird eine gleichförmige Formatierung für Intensitätsdaten benutzt, die von aufeinanderfolgenden Bildern (Rahmen) abgeleitet sind.

Die Abtastwerte auf der Leitung 101 werden an einen Bildspeicher 102, eine Element-Verzögerungsschaltung 103 und an den ersten Eingang eines Paares von Subtrahierschaltungen 104 und 105 gegeben. Der Bildspeicher 102 ist zweckmäßig eine angezapfte Verzögerungsleitung, die auf der Leitung 106 ein Ausgangssignal liefert, welches den Intensitätswert einer bestimmten räumliehen Steile im vorhergehenden Bild darstellt. Die genaue Stelle wird aufgrund eines an die Leitung 107 angelegten Steuersignals gewählt. Erfindungsgemäß ist dieses Steuersignal eine Funktion des vorhergehenden Verschiebungsschätzwertes, und die gewählte Stelle ist diejenige, welche am besten der verarbeiteten Stelle im augenblicklichen Bild (Rahmen) entspricht. Die Element-Verzögerungsschaltung 103 liefert ein Ausgangssignal, das um ein Abtastintervall mit Bezug auf sein Eingangssignal verzögert ist.

Das Intensitätswert-Ausgangssignal des Bildcpeichers 102 auf der Leitung 106 wird an den zweiten Eingang der Subtrahierschaltung 104 gegeben und das Intensitätswert-Ausgangssignal der Element-Verzögerungsschaltung 103 an den zweiten Eingang der Subtrahierschaltung 105. Da die beim vorhergehenden Bild gewählte Stelle gegenüber der im Augenblick verarbeiteten Stelle um den früheren Verschiebungsschätzwert verschoben ist, stellt das Ausgangssignal der Schaltung 104 demgemäß die in Gleichung (10) definierte, verschobene Bilddifferenz DFD dar. Das Ausgangssignal der Subtrahierschaltung 105 ist die ebenfalls in Gleichung (10) definierte Elementdifferenz EDlF.

Das Vorzeichenbit der Elementdifferenz EDIF wird *o von einem an den Ausgang der Subtrahierschaltung 105 angeschalteten Register 108 abgenommen und zur selektiven Steuerung des Vorzeichens von DFD in einer Vorzeichen-Änderungsschaltung 109 benutzt, der das Ausgangssignal der Subtrahierschaltung 104 zugeführt wird. Dieses Vorzeichensignal auf der Leitung 121 genügt der »Vorzeichen«-Funktion in Gleichung (10). Anschließend wird der algebraische Wert des Produktes von DFD und des Vorzeichens von EDlF in einem ersten Akkumulator 111 angesammelt, während die Größe von EDIF in einem zweiten Akkumulator 112 summieri wird. Da jedoch die Berechnung gemäß Gleichung (10) nur in sich bewegenden Bereichen durchgeführt wird, werden die Schalter 113 und 114, die in die Eingangsleitung der Akkumulatoren 111 bzw. 112 eingefügt sind, nur bei Auftreten eines entsprechenden Steuersignals von der Bewegungsbereich-Segmentschaltung 120 gleichzeitig geschlossen. Die Schaltung 120, die auf ähnliche Weise wie die bekannte Vorrichtung gemäß F i g. 2 aufgebaut sein kann, schließt die Schalter 113 und 114 dann, wenn die Bilddifferenz FDIF einen voreingestellten Schwellenwert übersteigt

Die in den Akkumulatoren 111 und 112 enthaltenen Werte, die der Zähler bzw. Nenner des oberen Ausdruckes in Gleichung (10) sind, werden in einer Teilerschaltung 115 dividiert und am Ende jedes Berechnungsintervalls von M Pels an einen ersten Eingang eines Addierers 116 gegeben. Dieses Eingangssignal stellt den Aktualisierungsausdruck für die Verschiebung in x-Richtung dar und wird zum vorhergehenden Verschiebungsschätzwert />'-' für die x-Richtung addiert. Das Addierer-Ausgangssignal ist zum Eingang einer Verzögerungsschaltung 117 zurückgeführt, so daß es zum nächsten Wert wird, der zu aktualisieren ist. Das Ausgangssignal der Verzögerungsschaltung 117, das den vorhergehenden Verschiebungsschätzwert darstellt, ist außerdem das Eingangssteuersignal für den Bildspeicher 102 auf der Leitung 107, wie oben erläutert. Der Inhalt der Akkumulatoren 111 und 112 wird am Ende jedes Intervalls von N Pels gelöscht.

Die Vorrichtung gemäß F i g. 1 ist so ausgelegt, daß sie die Verschiebung in der λγ-Richtung berechnet. Die Verschiebung in der y-Richtung (entsprechend dem unteren Ausdruck in Gleichung (10)) wird auf ähnliche Weise berechnet, wobei eine Zeilenverzögerungsschaltung anstelle der Elementverzögerungsschaltung 103 verwendet wird. Auf diese Weise wird die Zeilendifferenz LDIF als Ausgangssignal von der Subtrahierschaltung 105 statt der Elementdifferenz EDIF abgegeben.

Computer-Simulationen der in F i g. 1 dargestellten Vorrichtung zeigen, daß Rekursionen unter Verwendung eines Feldintervalls zu einem guten Schätzwert für die Verschiebung führen. Selbstverständlich ändert sich die Konvergenzrate mit dem Intervall und mit der Art der verwendeten Bildfolgen. Die Wahl eines Feldintervalls ist zwar typisch, eine Rekursion kann aber, falls gewünscht, für einen kleineren Block durchgeführt werden (beispielsweise 16x16 Pels).

Der Bildspeicher 102 läßt sich auf einfache Weise aufbauen, wenn eine weitere Näherung in Gleichung (10) erfolgt, derart, daß der anfängliche und der nachfolgende Schätzwert für die Verschiebung D nur ganzzahlige Komponenten enthält, die durch Ab- oder Aufrunden des auf der Leitung 107 zurückgeführten Steuersignals gebildet werden können. In diesem Fall kann der Speicher 102 eine angezapfte Verzögerungsleitung zusammen mit einem Datenschalter sein, der geeignete Anzapfungen auswählt. Alternativ muß, wenn die Komponenten von D nicht ganzzahlig sind, das Ausgangssignal der angezapften Verzögerungsleitung unter Verwendung von Verfahren interpoliert werden, die dem Fachmann bekannt sind.

Die Schaltungsanordnung nach F i g. 1 läßt sich, wie oben angegeben, in vielen Anwendungsfällen einsetzen, aber es werden bestimmte Abänderungen für das Verfahren der Verschiebungsschätzung empfohlen, wenn die Schätzwerteinrichtung in einem Vorhersage-Codierer verwendet werden soll. Zunächst ist es — da ein Codierer auf der Grundlage Pel für Pel arbeitet — zweckmäßig, den Verschicbangsschäizwert für jedes Bewegungsbereich-Pel abzuändern. Dies hat den zusätzlichen Vorteil, daß weitgehend die Probleme überwunden werden, die aufgrund mehrerer, sich bewegender Objekte oder deswegen auftreten, weil unterschiedliche Teile eines Objektes unterschiedliche Verschiebungen zeigen, da die Rekursion häufiger auftritt Natürlich ist eine schnelle Konvergenz der Rekursionsgleichung erforderlich.

Zum zweiten ist es in einem Vorhersage-Codierer wünschenswert, den Vorhersagefehler möglichst klein zu machen, damit der Wirkungsgrad des Codierers erhöht werden kann, wenn der dynamische Bereich des Fehlersignals abnimmt Da die verschobene Bilddifferenz (DFD) ein Maß für den Vorhersagefehler ist, ist die Minimierung seines Wertes in der Verschiebungsschätzeinrichtung zweckmäßig. Mathematisch sollte, wenn ein

Pel an der Stellen, mit der Verschiebung &-^] und der Intensität

1(X₁₁-U''¹, t-T)

vorausgesagt wird und zu einem Voraussagefehler DFD (X₀, ΰ'~^λ) führt, die Schätzwerteinrichtung versuchen, einen neuen Schätzwert ß' zu erzeugen, derart, daß gilt:

IDFD Qc₀, />') I < IDFD &, fi'"¹) | ·
Zu diesem Zweck ist es erwünscht, rekursiv

10

für jedes Bewegungsbereich-Element zu minimieren, und zwar unter Verwendung eines Gradienten-Lösungsversuchs. Beispielsweise kann unter Verwendung der üblichen Verfahren für den steilsten Abfall der neue Schätzwert /)' zum alten Schätzwert />'""' so in Beziehung stehen, daß gilt:

fr - />'"' - (ε/2) V₀ [DFD (χ,, Λ'"¹ )]² (11)

25

die sich auseinanderziehen läßt zu:
/>' = Z)'"¹ - ^DFD(X₀, />'-')

(12)

V₀(DFD(X₁₁, />'-

-Ö'-¹, t-τ)

O'' = ΰ'~^χ - ε DFD (je,, A'"¹)

30

In beiden Gleichungen (11) und (12) ist V₀ der Gradient mit Bezug auf die Verschiebung D, und~f ist eine positive, skalare Konstante, die typisch im Bereich 10~⁵ < ε < 10~² liegt. Der Gradient V₀IaBt sich anhand der Definition von DFD gemäß Gleicfiung (9) und unter Beachtung der nachfolgenden Gleichung auswerten:

(13)

wobei V der Gradient mit Bezug auf χ ist. Diese Substitution führt zu:

D' = Ζ)¹'"¹ - ε DFD(X₁₁, /T¹) V/^-/)'"', t-τ) (14)

wobei DFD und V/durch Interpolation für nicht ganzzahliges ΰ'~^ι ausgewertet werden. Eine wesentliche Verringerung der Berechnungsarbeit für V/wird erzielt, indem man ΰ'~^λ zur Berechnung des Gradienten V/auf einen ganzzahligen Wert quantisiert. Wenn demgemäß [Z)'-'] einen aufgerundeten oder abgerundeten Wert jeder der Komponenten Ö'~^l darstellt, dann läßt sich der Schätzwert für dij Gleichung (14) vereinfachen zu:

(15)

Man beachte, daß \7d unter Anwendung der Gleichung (9) ausgewertet werden könnte, wobei sich ein Schätzwert ergibt, bei dem V/ bei (x* t) statt bei (χ>—ύ~\ t-τ) ausgewertet wird. Dieses alternative Verfahren beinhaltet eine Annahme für die Linearität von /, die dann nicht gültig sein könnte, wenn D-Of-¹ groß ist Außerdem ist kein Unterschied hinsichtlich der Berechnungskompliziertheit, wenn angenommen wird, daß eine lineare Interpolation von IQc, t—τ) zur Berechnung von DFD benutzt wird und die sich ergebenden, verschobenen Zeilen- und Elementdifferenzen zur Berechnung von V/ in Gleichung (15) verwendet werden.

Bei der Erläuterung der Bedeutung von Gleichung (15) läßt sich feststellen, daß bei jedem Näherungsschritt zum alten Schätzwert eine Vektorgröße parallel zur Richtung des räumlichen Gradienten der Bildintensität addiert wird, deren Größe proportional zum bewegungskompensierten Vorhersagefehler DFDte* />'-') ist. Anhand von Gleichung (9) läßt sich erkennen, daß — wenn der Korrekturterm (Q- />-') senkrecht zum Intensitätsgradienten V/ ist — die verschobene Bilddifferenz DFD Null wird, wodurch sich eine Aktualisierung Null für die Rekursion der Gleichung (15) ergibt. Das kann auftreten, obwohl das Objekt sich tatsächlich bewegt hat. Dabei handelt es sich jedoch nicht um einen Fehler der Bewegungsschätzwerttechnik, sondern um den gleichen Fall, bei dem eine Intensitätsrampe translatorisch bewegt wird und nur eine Bewegung parallel zur Rampenrichtung (V/) wahrnehmbar ist. Eine Bewegung senkrecht zur Rampenrichtung ist nicht feststellbar und als solche beliebig. Anders gesagt, nur wegen des Auftretens von Kanten mit unterschiedlichen Orientierungen in reellen Bildern ist eine Konvergenz von £> auf den tatsächlichen Wert von D möglich.

Die Bedeutung der Größen in Gleichung (15) ist graphisch in Fig.2 dargestellt, bei der die Rechtecke 201 und 202 die räumlichen Grenzen eines vergangenen und eines augenblicklichen Bildes (Rahmens) darstellen. Im Bild 201 ist eine Folge von generell parallelen Abtastzeilen /„-2, Ai-1. Ai und Ai₊1 zur Vereinfachung der Erläuterung in weit auseinandergezogener Form dargestellt. Die entsprechenden Abtastzeilen im Bild 202 sind bezeichnet mit: /'„_:, V_n-1, I'_n und /'„+1.

Im augenblicklichen Bild 202 bedeutet das A^- bei 203 die Stelle des Bildelements, für das ein Verschiebungsschätzwert berechnet wird, und der Vektor x_a gibt die Stelle des Elements 203 mit Bezug auf ein festes Koordinatensystem innerhalb des Bildes an. Im vorhergehenden Bild 201 gibt das χ bei 204 die gleiche Stelle bei x* an. und der Vektor 205 stellt den vorhergehenden Verschiebungsschätzwert —&-'¹ dar.

Entsprechend Gleichung (15) wird £'-' zur Berechnung von V/auf den nächsten ganzzahligen Wert [Z>-'] auf- oder abgerundet. Dies wird erreicht durch Beachtung der benachbarten Stellen in der vorhergehenden, augenblicklichen und nachfolgenden Abtastzeile (bei diesem Beispiel den Zeilen /„_2, l_n-i und I_n), um festzustellen, welches diskrete Bildelement am besten />-' darstellt. In diesem Zusammenhang wird die Stelle eines diskreten Bildelementes durch den Zeitpunkt bestimmt, zu dem das Bildintensitätssignal abgetastet worden ist. Demgemäß geben in F i g. 2 die ©-Werte, die mit b,c,d,e, /bezeichnet sind, Bildelemente an, die die durch die. Spitze des Vektors 205 bezeichnete Stelle umgeben. Bei diesem Beispiel liegt der Vektor 206 von der Stelle 204 zum Pel dam dichtesten an der durch den Vektor 204 bezeichneten Stelle. Demgemäß wird S7I(ia— &~^Λ, t—τ)beim Pel «/ausgewertet

Ein einfaches Schema zur Abschätzung des Gradienten ^JI besteht darin, die mittlere vertikale und horizontale Intensitätsdifferenz zwischen Pils zu berechnen, die das Pei d umgeben, und dann diese Ergebnisse vektoriell zu kombinieren. Bei diesem Schema ist

EDIF (horizontale Komponente) =

LDIF (vertikale Komponente) =

wobei 4 die Intensität beim Pel b, /_rdie Intensität beim Pel cund so weiter sind.

Die andere Größe in Gleichung (15), die ausgewertet werden muß, ist DFDfx,, 2>-'), nämlich die Intensitätsdifferenz zwischen dem Pel 203 und der durch den Ve! tor 205 angegebenen Stelle. Der Intensitätswert ι ο dieser letztgenannten Stelle läßt sich durch Interpolation im wesentlichen auf die gleiche Weise wie für V/ berechnen, nämlich durch Kombinieren des richtigen Bruchteils von EDlF und LDIF mit den Intensitätswerten für das Pel d.

Ein Blockschaltbild der Vorrichtung zur Berechnung eines Verschiebungsschätzwertes gemäß Gleichung (14) oder (15) ist in Fig. 3 gezeigt. Die Eingangs-Videoabtastwerte auf der Leitung 301 werden an einen Bildspeicher 302 und an einen Eingang einer Subtrahierschaltung 303 gegeben. Nimmt man an, daß der Verschiebungsschätzwert für das vorhergehende Bild £>-' in einer Verzögerungsschaltung 304 gespeichert ist, so wird er im Quantisierer 305 quantisiert und sein ganzzahliger Anteil [D¹-'] an den Steuereingang des Bildspeichers 302 gegeben. Dieser Speicher, der ähnlich ausgebildet sein kann wie der Speicher 102 in Fig. 1, liefert Ausgangssignale auf einer Anzahl von Leitungen 306, die die Intensität von Pels im gespeicherten Bild wiedergeben, welche die Stelle des Pels Aa-[O'"¹] umgeben, das gegen das Pel x_a im augenblicklichen, gerade verarbeiteten Bild verschoben ist. Für das Beispiel gemäß F i g. 2 wird die Intensität der Pels b, c, e und /geliefert.

Die Intensitätswert-Ausgangssignale des Speichers 302 werden an einen Interpolator 307 zusammen mit dem Ausgangssignal für den vorhergehenden Schätzwert vom Verzögerungselement 304 gegeben. Der Interpolator 307 hat zwei Funktionen, nämlich den Intensitätsgradienten V/und den Intensitätswert an der Stelle Xa- Df-' zu berechnen. Beide Funktionen sind leicht zu übersehen und lassen sich einfach durch lineare Interpolationen verwirklichen. Es können dem Fachmann bekannte Anordnungen zur Berechnung von bewerteten Mittelwerten zu diesem Zweck benutzt werden.

Der im Interpolator 307 berechnete Intensitätswert Ifa — D*'') wird an den zweiten Eingang der Subtrahierschaltung 303 gegeben, deren Ausgangssignal die verschobene Bilddifferenz DFD ist, die in Gleichung (8) definiert wird. Dieser Wert wird als Eingangssignal an eine unten beschriebene Verschiebungsfehler-Berechnungsschaltung 309 gegeben. Die x- und y-Komponenten des im Interpolator 307 gebildeten Intensitätsgradienten werden auf entsprechende Weise über Leitungen 308 an Eingänge der Schaltung 309 angelegt.

Die Berechnungsschaltung 309 ist so ausgelegt, daß sie die in den Gleichungen (14) oder (15) definierte Fehlertermberechnung ausführt, und kann geeignete Multiplizier- und Maßstahsschaitungen enthalten. Es kann ein weiterer, nicht gezeigter Eingang zur Beeinflussung des Wertes von e vorhanden sein.

Das Ausgangssignal der Schaltung 309 ist der Verschiebungsfehler oder der Aktualisierungsterm, der mittels einer Addierschaltung 310 zum vorhergehenden, im Verzögerungselement 304 gespeicherten Verschiebungsschätzwert addiert wird. Die Aktualisierung wird jedoch nur im Bewegungsbereich des Bildes durchgeführt, und aus diesem Grund ist ein Schalter 311 in die Ausgangsleitung der Schaltung 309 eingefügt. Der Schalter 311 wird unter Steuerung der Bewegungsbereich-Segmentschaltung 312 gesteuert, die ein Eingangssignal auf der Leitung 301 aufnimmt. Die Segmentschaltung 312 kann auf entsprechende Weise wie die Segmentschaltung 120 in Fig. 1 aufgebaut sein, so daß der Schalter 311 nur dann geschlossen wird, wenn die Bilddifferenz FDIF einen vorgewählten Schwellenwert übersteigt. Das Ausgangssignal der Schätzwertschaltung gemäß Fig.3 kann entweder am Verzögerungselement 304 oder am Ausgang des Addierers 310 entnommen werden, wobei das Ausgangssignal im ersten Fall einfach nur eine verzögerte Version des Ausgangssignals für den zweiten Fall ist.

Bei der Durchführung von Simulationen zur Bewertung der Güte der Verschiebungsschätzwertverfahren nach der vorliegenden Erfindung hat sich gezeigt, daß sich Gleichung (15) weiter wie folgt vereinfachen läßt:

/>'' = ΰ'-^χ-ε- Vorz. (DFD

Vorz.

(21)

wobei das Vorzeichen einer Vektorgröße der Vektor für die Vorzeichen seiner Komponenten ist. Die durch Gleichung (6) definierte Vorzeichenfunktion vermeidet die Multiplikation, die zur Berechnung des Aktuaiisierungsterms erforderlich ist. Statt dessen bestehen für die Aktualisierung jeder Verschiebungskomponente von einem Bildelement zum nächsten nur drei Möglichkeiten, nämlich 0 oder ± ε. Die Güte eines Vorhersage-Codierers unter Verwendung dieser Vereinfachung war, gemessen in Codierbits/Feld, scheinbar die gleiche wie bei einem Codierer unter Verwendung einer Schätzwertschaltung, die Gleichung (15) verwirklicht

Die Verschiebungs-Schätzwertschaltungen gemäß F i g. 1 und 3 haben gemeinsam die wiederholte Aktualisierung jedes Verschiebungsschätzwertes, wobei der vorhergehende Schätzwert zur Berechnung des Korrekturterms benutzt wird. Bei der Schaltungsanordnung nach F i g. 1, die Gleichung (10) verwirktlicht, wird die verschobene Bilddifferenz beruhend auf dem vorhergehenden Verschiebungsschätzwert entsprechend der Bildaktivität (gemessen durch EDIF oder LDlF) normiert und akkumuliert, um den aktualisierten Verschiebungsschätzwert zu gewinnen. Die Rekursion kann über ein Feld oder eine Gruppe von Pels durchgeführt werden. Bei der Schaltungsanordnung nach Fig.3, die Gleichung (14) oder (15) verwirklicht, werden der Intensitätswert und der Intensitätsgradient in der Nachbarschaft des vorhergehenden Verschiebungsschätzwertes berechnet, maßstäblich bearbeitet und zur Berechnung des neuen Schätzwertes verwendet Die Rekursion erfolgt typisch Pel für Pel.

Hierzu 3 Blatt Zeichnungen

Claims

Patentansprüche:

1. Vorrichtung zur Erzeugung eines Schätzwertes für die Verschiebung eines Objektes in einer Videoszene zwischen einem früheren und einem augenblicklichen Bild, mit Schaltungen zur Berechnung eines ersten Schätzwertes für die Verschiebung unter Verwendung der Bildintensitätsdifferenz zwischen wenigstens einem Bildelement im augenblicklichen Bild und einem räumlich entsprechenden Bildelement im vorhergehenden Bild, dadurch gekennzeichnet, daß die Vorrichtung eine Aktualisierungsschaltung (Fig. 1) zur wiederholten Aktualisierung des ersten Verschiebungischätzwertes unter Verwendung der intensitätsdifferenz zwischen dem wenigstens einen Bildelement im augenblicklichen Bild und einer Stelle im vorhergehenden Bild aufweist, die gegen das augenblickliche Bildelement um den ersten Verschiebungsschätzwert verschoben ist

2. Vorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Aktualisierungsschaltung einen Speicher und einen Subtrahierer (102, 104) zur Bildung der Intensitätsdifferenz DFD&D¹-¹) zwischen dem wenigstens einen Bildelement an der Stelle χ und einer Stelle im vorhergehenden Bild, die gegen die Stelle χ um den ersten Verschiebungsschätzwert &~^] verschoben ist, und eine Normierungsschaltung (103, 105, 115) zur Normierung von DFD durch ein Maß für die lokalen Intensitätsschwankungen aufweist, die die Stelle χ umgeben.

3. Vorrichtung nach Anspruch 2, dadurch gekennzeichnet, daß die Normierungsschaltung so ausgelegt ist, daß sie die Elementdifferenz EDlF zwischen der Intensität an der Stelle x. und der Intensität des vorhergehenden Bildelements berechnet.

4. Vorrichtung nach Anspruch 2, dadurch gekennzeichnet, daß die Normierungsschaltung so ausgelegt ist, daß sie die Zeilendifferenz LDlF zwischen der Intensität an der Stelle χ und der Intensität des vertikal verschobenen Bildelements auf der vorhergehenden Zeile berechnet.

5. Vorrichtung nach Anspruch 2, dadurch gekennzeichnet, daß die Aktualisierungsschaltung ferner einen Akkumulator (111) zur Akkumulierung von Intensitätsdifferenzen für Bildelemente in einem gewählten Intervall N und eine Vorzeichen-Änderungsschaltung (109) zur Inkrementierung oder Dekrementierung des Akkumulators als Funktion der örtlichen Intensitätsschwankungen enthält.

6. Vorrichtung nach Anspruch 5, dadurch gekennzeichnet, daß ferner eine Segmentschaltung (120) zur Aufnahme nur derjenigen Bildelemente in das gewählte Intervall N vorgesehen ist, die eine Bilddifferenz (FDIF) haben, welche einen Schwellenwert übersteigt.

7. Verfahren zur Erzeugung eines Schätzwertes für die Verschiebung eines Objektes in einer Videoszene zwischen einem früheren und einem augenblicklichen Bild nach den Vorrichtungsansprüchen 1 bis 6, dadurch gekennzeichnet, daß folgende Verfahrensschritte vorgesehen sind:

Berechnen eines ersten Schätzwertes für die Verschiebung unter Verwendung der Bildintensitätsdifferenz zwischen wenigstens einem Bildelement im augenblicklichen Bild und einem räumlich entsprechenden Bildelement im vorhergehenden Bild;

wiederholtes Aktualisieren des ersten Verschiebungsschätzwertes unter Verwendung der Intensitätsdifferenz zwischen dem wenigstens einen Bildelement im augenblicklichen Bild und einer Stelle im vorhergehenden Bild, die gegen das entsprechende Bildelement um den ersten Verschiebungsscnätzwert verschoben ist