DE19633581C1

DE19633581C1 - Verfahren zur Auswahl eines wahrscheinlichen Bewegungsvektors für eine Echtzeitbewegungsschätzung bei Bewegtbildsequenzen

Info

Publication number: DE19633581C1
Application number: DE19633581A
Authority: DE
Inventors: Christoph Dr Ing Heer
Original assignee: Siemens AG; Siemens Corp
Current assignee: Siemens AG; Siemens Corp
Priority date: 1996-08-20
Filing date: 1996-08-20
Publication date: 1998-02-26
Anticipated expiration: 2016-08-21

Description

Eine Bewegungsschätzung in Bewegtbildsequenzen wird zum Bei spiel zur Reduktion der zeitlichen Redundanz in der Bildco dierung und zur Interpolation von Zwischenbildern in einer Bildersequenz verwendet. Dazu werden die Bilder in kleinere Bildausschnitte zerlegt und für jeden Bildausschnitt wird ein Bewegungsvektor bezogen auf das vorhergehende Bild ermittelt. Der Bewegungsvektor kann zur Rekonstruktion des aktuellen Bildausschnittes aus der Information des vorhergehenden Bil des verwendet werden. In der Regel setzt sich die Bewegungs schätzung aus der Bestimmung der zwei in der Bildebene gele genen translatorischen Komponenten des Bewegungsvektors zu sammen. Für alle betrachteten Bewegungen eines Bildausschnit tes muß ein Verfahren zur Auswahl des wahrscheinlichsten Be wegungsvektors durchgeführt werden.

Aus den IEEE Transactions on Circuits and Systems, VOL. 37, NO. 5, MAY 1990, Seiten 649-651, sind solche Verfahren bekannt, wobei beim so genannten MSD-Verfahren die Summe der Quadrate oder beim so genannten MAD-Verfahren die Summe der Absolutwerte der Diffe renzen zwischen den Pixelwerten des aktuellen Bildausschnitts und den Pixelwerten eines entsprechenden Bildausschnitts des vorhergehenden Bildes oder aber beim sogenannten PCD- Verfahren die Anzahl der absoluten Differenzen zwischen den Pixelwerten des aktuellen Bildausschnitts und der Pixelwerte eines entsprechenden Bildausschnittes des vorhergehenden Bil des, die eine vorgegebene Schwelle unterschreiten als Krite rium für die Auswahl des wahrscheinlichsten Bewegungsvektor dienen.

Das MSD-Verfahren ist wegen der Quadrierung sehr aufwendig und das das MAD-Verfahren liefert ein vergleichsweise schlechtes Signal/Rausch-Verhältnis (SNR). Das PCD-Verfahren ist sehr einfach realisierbar, liefert aber nur sehr unbe friedigende Ergebnisse hinsichtlich des Signal/Rausch-Ver hältnisses.

Aus der deutschen Offenlegungsschrift DE 42 21 320 A1 ist eine Bewegungsvektor-Erfassungsvorrichtuung bekannt, bei der ohne Erhöhung des Schaltungsaufwandes die Erfassungsgenauig keit dadurch erhöht wird, daß eine Vielzahl von Sätzen reprä sentativer Punkte gespeichert werden, die im selben Intervall ausgewählt sind wie jene für Suchbereiche, deren jeder aus Q·R Pixeln eines Bildes eines Teilbildes besteht, welches dem gerade vorliegenden Teilbild um ein oder mehrere Teilbilder vorangeht.

Aus der deutschen Offenlegungsschrift DE 43 44 924 A1 sind ein Verfahren und eine Vorrichtung zur Bewegungsschätzung be kannt, wobei die Auswertung nur bestimmter Bits, z. B. des MSB oder der beiden MSBs, der Bildpunkt-Werte erfolgt, um Rechen zeit zu sparen.

Aus der deutschen Patentschrift DE 40 23 449 C1 ist ein Ver fahren zum Bestimmen von Bewegungsvektoren für Teilbildberei che einer Quellbildsequenz bekannt, bei dem zunächst zwei Be wegungsvektoren in einem Bild mit reduzierter Auflösung ge sucht werden und dann zwischen dem Nullvektor und den beiden Vektoren eine verfeinerte Suche durchgeführt wird.

Aus den Proceedings of the IEEE, Vol. 83, No. 6, June 1965 sind Bewegungsschätztechniken für das digitale Fernsehen be kannt, bei denen die Bandbreite der hinsichtlich der des Vor hersagefehlers und der Bewegungsparameter dadurch minimiert werden, daß ein lokal adaptives Mehrfachgitter-Block-Matching angewendet wird.

Die der Erfindung zu Grunde liegende Aufgabe liegt nun darin, ein Verfahren zur Auswahl eines wahrscheinlichen Bewegungs vektors für eine Echtzeitbewegungsschätzung bei Bewegtbildse quenzen anzugeben, bei dem die Vorteile der obengenannten Verfahren vereint werden.

Diese Aufgabe wird erfindungsgemäß durch die Merkmale des Pa tentanspruchs 1 gelöst. Vorteilhafte Weiterbildungen des Ver fahrens ergeben sich aus den Unteransprüchen.

Die Erfindung wird nachfolgend anhand der Zeichnungen näher erläutert. Dabei zeigt

Fig. 1 ein Ablaufdiagramm zur Erläuterung des erfindungsge mäßen Verfahrens,

Fig. 2 eine Prinzipschaltbild zur Erläuterung einer vorteil haften Weiterbildung des erfindungsgemäßen Verfahrens und

Fig. 3 ein Beispiel einer Quantisierung innerhalb des erfin dungsgemäßen Verfahrens.

In Fig. 1 ist ein Ablaufdiagramm zur Erläuterung des erfin dungsgemäßen Verfahrens gezeigt, wobei die aufeinanderfolgen den Verfahrenschritte Differenzbildung D, Absolutwertbildung A, Quantisierung Q, Summenbildung S und Minimumbildung MIN durch miteinander verbundene Blöcke angedeutet sind. Während der Differenzbildung D werden aus einem aktuellen Bildaus schnitt S_f(k, l) und aus einem vorhergehenden Bildausschnitt S_f-1(k+i, l+j) für eine Mehrzahl von Pixelvektoren (k, l) der Bildausschnitte und für eine Mehrzahl Bewegungsvektoren (i, j) Differenzen d(k, l, i, j) beziehungsweise durch die anschließen de Absolutwertbildung A die Absolutwerte der Differenzen d(k, l, i, j) gebildet. Dem Absolutbetrag einer jeweiligen Dif ferenz wird nun anschließend während der Quantisierung Q über eine treppenförmige Kennlinie mit exponentiell ansteigender Stufenbreite, in Fig. 3 mit SB bezeichnet, und exponentiell ansteigender Stufenhöhe, in Fig. 3 mit SH bezeichnet, je weils eine quantisierte Differenz T(k, l, i, j) zugeordnet. Für einen jeweiligen Bewegungsvektor (i, j) werden anschließend entweder alle quantisierten Differenzen selbst oder aber alle quadrierten quantisierten Differenzen über alle Pixelvektoren der Mehrzahl von Pixelvektoren (k, l) während der Summenbil dung S zu einem jeweiligen Summenwert LPDC(i, j) aufsummiert, wobei eine Summenbildung über k und eine Summenbildung über l durchzuführen ist. Zum Schluß wird während der Minimumbildung MIN ein wahrscheinlichster Bewegungsvektor dadurch ermittelt, daß derjenige Bewegungsvektor mit dem geringsten Summenwert Min( LPCD(i, j)) ermittelt wird.

In Fig. 3 ist ein Beispiel einer vorteilhaften Quantisierung Q in Form eine Quantisierungskennlinie mit der Differenz d(k, l, i, j) auf der Ordinate und der quantisierten Differenz T(k, l, i, j) auf der Abszisse dargestellt, wobei die Stufenhöhe und die Stufenbreite jeweils zur Basis 2 exponentiell an steigt. Die zugehörige Quantisierungskennlinie kann also hier wie folgt beschrieben werden:

Die Stufenbreite SB und Stufenhöhe SH der treppenförmigen Quantisierungskennlinie kann zwar zu einer beliebigen Basis exponentiell ansteigen, es ist jedoch von Vorteil wenn die Stufenbreite SB der treppenförmigen Quantisierungskennlinie zur Basis 2^m exponentiell und die Stufenhöhe SH der treppen förmigen Quantisierungskennlinie zur Basis 2^p exponentiell ansteigt, wobei m und p positive ganze Zahlen größer gleich Eins sind und wobei m und p auch gleich groß sein können.

Für das Verfahren mit der in Fig. 3 gezeigten Kennlinie, al so für einen exponentiellen Anstieg der Stufenhöhe und der Stufenbreite zur Basis 2, ist eine rechentechnisch besonders einfach durchzuführende Weiterbildung des erfindungsgemäßen Verfahrens möglich, die anhand der in Fig. 2 gezeigten Prin zipschaltung im folgenden näher erläutert wird. Diese Prin zipschaltung weist ein Register REG mit den Stellen R1 . . . R5 und einer Vorzeichenstelle VZ, ein Akkumulatorregister ACC mit den Bitstellen A1 . . . A5 und einer Vorzeichenstelle VZ, ei ne Einheit NV zum bitweisen Nullvergleich sowie Auswahlschal ter S1 und S2 auf, wobei das Register REG zur Aufnahme der Differenz d(k, l, i, j) und das Akkumulatorregister ACC zu Auf nahme der quantifizierten Differenz T(k, l, i, j) dienen. Die Quantisierung wird hierbei durch Maskierung der binären Dar stellung der jeweiligen Differenz d(k, l, i, j) erzeugt. Die bi näre Darstellung der jeweiligen Differenz wird dabei ausge hend vom höchstwertigen Bit R5 Bit für Bit nacheinander so lange ausgelesen, bis mit Hilfe der Einheit NV festgestellt wird das gerade ausgelesene Bit verschieden von Null ist. Die Absolutwertbildung erfolgt auf sehr einfache Weise dadurch, daß dabei das Vorzeichenbit VZ des Registers REG ignoriert wird. Ist das über den Auswahlschalter S1 gerade ausgelesene Bit ungleich Null, so wird es über den Schalter S2 an einer entsprechenden Bitstelle im Akkumulatorregister aufaddiert.

Werden für einen jeweiligen Bewegungsvektor (i, j) alle quan tisierten Differenzen über alle Pixelvektoren der Mehrzahl von Pixelvektoren (k, l) zu einem jeweiligen Summenwert (LPDC(i, j)) aufsummiert, so wird das von Null verschiedene Bit stellenrichtig aufaddiert. Das bedeutet beispielsweise, daß das von Null verschiedene Bit an der Stelle R2 im Regi ster an der Stelle A2 im Akkumulatorregister ACC aufaddiert wird.

Entsprechend können auch für einen jeweiligen Bewegungsvektor (i, j) alle quadrierten quantisierten Differenzen über alle Pixelvektoren der Mehrzahl von Pixelvektoren (k, l) dadurch zu einem jeweiligen Summenwert (LPDC(i, j)) aufsummiert werden, daß das von Null verschiedene Bit um die seiner Wertigkeit entsprechenden Anzahl von Stellen erhöht in einem Akkumulator aufaddiert wird, wodurch sich eine Verdopplung der jeweiligen Wertigkeit ergibt. Das heißt, daß im obigen Beispiel nicht in der Stelle A2 sondern in der Stelle A4 des Akkumulatorregi sters ACC aufaddiert wird.

Claims

1. Verfahren zur Auswahl eines wahrscheinlichen Bewegungsvek tors für eine Echtzeitbewegungsschätzung bei Bewegtbildse quenzen,
bei dem aus einem aktuellen Bildausschnitt (S_f(k, l)) und aus einem vorhergehenden Bildausschnitt (S_f-1(k+i, l+j)) für eine Mehrzahl von Pixelvektoren (k, l) der Bildausschnitte und für eine Mehrzahl Bewegungsvektoren (i, j) Differenzen gebildet werden,
bei dem dem Absolutbetrag einer jeweiligen Differenz über ei ne treppenförmige Quantisierungskennlinie mit exponentiell ansteigender Stufenbreite und exponentiell ansteigender Stu fenhöhe jeweils eine quantisierte Differenz (T(k, l, i, j)) zu geordnet wird,
bei dem für einen jeweiligen Bewegungsvektor (i, j) alle quan tisierten Differenzen selbst beziehungsweise alle quadrierten quantisierten Differenzen über alle Pixelvektoren der Mehr zahl von Pixelvektoren (k, l) zu einem jeweiligen Summenwert (LPDC(i, j)) aufsummiert werden und
bei dem der wahrscheinlichste Bewegungsvektor dadurch ermit telt wird, daß derjenige Bewegungsvektor mit dem geringsten Summenwert ermittelt wird.

2. Verfahren zur Auswahl eines wahrscheinlichen Bewegungsvek tors nach Anspruch 1, bei dem die Stufenbreite (SB) der treppenförmigen Quantisie rungskennlinie zur Basis 2^m exponentiell und die Stufenhöhe (SH) der treppenförmigen Quantisierungskennlinie zur Basis 2^p exponentiell ansteigt, wobei m und p positive ganze Zahlen größer gleich Eins sind.

3. Verfahren zur Auswahl eines wahrscheinlichen Bewegungsvek tors nach Anspruch 2, bei dem die Stufenbreite (SB) und die Stufenhöhe (SH) zur gleichen Basis exponentiell ansteigen.

4. Verfahren zur Auswahl eines wahrscheinlichen Bewegungsvek tors nach Anspruch 3, bei dem die Stufenbreite (SB) und die Stufenhöhe (SH) zur Ba sis 2 exponentiell ansteigen.

5. Verfahren zur Auswahl eines wahrscheinlichen Bewegungsvek tors nach Anspruch 4,
bei dem die Quantisierung durch Maskierung der binären Dar stellung der jeweiligen Differenz erzeugt wird, wobei die bi näre Darstellung der jeweiligen Differenz, ausgehend vom höchstwertigen Bit, Bit für Bit nacheinander solange ausgele sen werden, bis das gerade ausgelesene Bit verschieden von Null ist, und
bei dem für einen jeweiligen Bewegungsvektor (i, j) alle quan tisierten Differenzen selbst beziehungsweise alle quadrierten quantisierten Differenzen über alle Pixelvektoren der Mehr zahl von Pixelvektoren (k, l) dadurch zu einem jeweiligen Sum menwert (LPDC(i, j)) aufsummiert werden, daß das von Null ver schiedene Bit stellenrichtig beziehungsweise um die seiner Wertigkeit entsprechende Anzahl von Stellen erhöht in einem Akkumulator aufaddiert wird.