DE69320118T2

DE69320118T2 - Motion estimation

Info

Publication number: DE69320118T2
Application number: DE69320118T
Authority: DE
Inventors: Gerard C/O Int. Octrooibureau B.V. Nl-5656 Aa Eindhoven De Haan; Hendrik C/O Int. Octrooibureau B.V Nl-5656 Aa Eindhoven Huijgen
Original assignee: Philips Electronics NV
Current assignee: Trident Microsystems Far East Ltd Cayman Islands
Priority date: 1992-05-06
Filing date: 1993-05-03
Publication date: 1999-03-11
Anticipated expiration: 2013-05-04
Also published as: KR930024488A; DE69320118D1; JPH07282267A; KR100247370B1; JP3370726B2

Description

Die vorliegende Erfindung bezieht sich auf ein Verfahren und eine Anordnung zum Schätzen von Bewegungsvektoren und auf einen Video-Signalempfänger mit einem bewegungskompensierten Zeilenzahlwandler.The present invention relates to a method and an arrangement for estimating motion vectors and to a video signal receiver with a motion-compensated line count converter.

In EP-A-0.474.276 (PHN 13.439) wird einen Bewegungsschätzer beschrieben, wobei geringfügige Zunahmen zu einem Prädiktionsvektor hinzuaddiert werden zum Erhalten einer Anzahl Kandidatvektoren, aus denen ein Ausgang selektiert wird. In diesem Schätzer hat eine erste Zunahme in einer ersten Richtung eine Größe, die von einer zweiten Zunahme in einer zweiten Richtung abweicht. Diese Maßnahme hält die Stabilität und die Genauigkeit der vorhergehenden Schätzer aufrecht, während die Konvergenzgeschwindigkeit gesteigert wird.EP-A-0.474.276 (PHN 13.439) describes a motion estimator wherein small increments are added to a prediction vector to obtain a number of candidate vectors from which an output is selected. In this estimator, a first increment in a first direction has a magnitude that differs from a second increment in a second direction. This measure maintains the stability and accuracy of the previous estimators while increasing the speed of convergence.

Der Artikel "Low-rate sequence image coding via vector quantization" von Chen u. a. in "Signal Processing" Heft 26, Nr. 3, 3/92, Seiten 265-283 beschreibt die bewegungskompensierte Zwischenbildcodierung im Kontext eines Vektorquantisierungsbildcodierungssystems. Bei diesem Codierungsplan wird dr Richtung der Bewegung eines Gegenstandes entweder durch eine Pixelrekursive Technik oder durch eine Blockdeckungstechnik gefolgt. In einem Drei-Stufen-Bewegungssuchalgorithmus wird eine Suchfehlerfunktion zunächst ohne Bewegungskompensation berechnet. Wenn der berechnete Suchfehlerfunktionswert eine Störschwelle nicht überschreitet, ist der untersuchte Block von Pixeln ein keine-Änderung-Block und es wird keine weitere Bewegungssuche durchgeführt. Im anderen Fall wird die Suchfehlerfunktion für jeden der acht den aktuellen Block umgebenden Blöcke berechnet. Wenn der Mindestwert dieser berechneten Suchfehlerfunktionswerte die Störschwelle nicht überschreitet, bezeichnet der Mindestwert den Bewegungsvektor gegenüber dem Vektor von dem aktuellen Block zu demjenigen umgebenden Block, der dem minimalen Suchfehlerfunktionswert entspricht. Wenn aber der Mindestwert der berechneten Suchfehlerfunktionswerte dennoch die Störschwelle überschreitet, wird die Suchfehlerfunktion für die acht Blöcke berechnet, die den Block umgeben, der dem Mindestwert entspricht. Wenn der Mindestwert dieser berechneten Suchfehlerfunktionswerte die Störschwelle nicht überschreitet, bezeichnet der Mindestwertden Bewegungsvektor. Im anderen Fall wird eine nicht-bewegungskompensierte Zwischenbildcodierung durchgeführt, es sei denn, daß der berechnete Mindestwert des zuletzt durchgeführten Suchschrittes wesentlich kleiner ist als der berechnete Mindestwert des vorhergehenden Suchschrittes, was folglich angibt, daß die Bewegungsvektorsuche in Richtung eines befriedigenden Ergebnisses geht. In diesem letzteren Fall wird die Suchfehlerfunktion für die acht Blöcke berechnet, die den Block umgeben, der dem zuletzt berechneten minimalen Suchfehlerfiinktionswert entspricht in der Hoffnung, daß der Mindestwert der nun berechneten Suchfehlerfunktionswerte die Störschwelle nicht überschreitet. Wenn dies der Fall ist, wird der Bewegungsvektor gefunden; wenn nicht, muß eine Rückkehr zu einer nichtbewegungskompensierten Zwischenbildcodierung vorgenommen werden.The article "Low-rate sequence image coding via vector quantization" by Chen et al. in "Signal Processing" Volume 26, No. 3, 3/92, pages 265-283 describes motion-compensated interframe coding in the context of a vector quantization image coding system. In this coding scheme, the direction of motion of an object is followed either by a pixel recursive technique or by a block coverage technique. In a three-step motion search algorithm, a search error function is first calculated without motion compensation. If the calculated search error function value does not exceed a noise threshold, the block of pixels under investigation is a no-change block and no further motion search is performed. Otherwise, the search error function is calculated for each of the eight blocks surrounding the current block. If the minimum value of these calculated search error function values does not exceed the interference threshold, the minimum value denotes the motion vector relative to the vector from the current block to the surrounding block that corresponds to the minimum search error function value. However, if the minimum value of the calculated search error function values nevertheless exceeds the interference threshold, the search error function for the eight blocks calculated that surround the block corresponding to the minimum value. If the minimum value of these calculated search error function values does not exceed the noise threshold, the minimum value indicates the motion vector. In the other case, non-motion compensated inter-frame coding is performed, unless the calculated minimum value of the last search step performed is significantly smaller than the calculated minimum value of the previous search step, thus indicating that the motion vector search is moving towards a satisfactory result. In this latter case, the search error function is calculated for the eight blocks surrounding the block corresponding to the last calculated minimum search error function value in the hope that the minimum value of the now calculated search error function values does not exceed the noise threshold. If this is the case, the motion vector is found; if not, a return to non-motion compensated inter-frame coding must be made.

Es ist nun u. a. eine Aufgabe der vorliegenden Erfindung eine verbesserte Bewegungsschätzung zu schaffen. Es ist weitrhin eine Aufgabe der vorliegenden Erfindung eine Bewegungsschätzung zu schaffen, die einfachere Hardware erfordert und/oder bessere Schätzungsergebnisse liefert.It is now, among other things, an object of the present invention to create an improved motion estimation. It is also an object of the present invention to create a motion estimation that requires simpler hardware and/or provides better estimation results.

Nach einem ersten Aspekt schafft die Erfindung ein Bewegungsschätzverfahren wie in Anspruch 1 definiert. Nach einem zweiten Aspekt schafft die Erfindung eine Bewegungsschätzanordnung wi in Anspruch 7 dfiniert. Nach einem dritten Aspekt schafft die Erfindung einen Video-Signalempfänger mit einem Eingangskreis zum Empfangn eines Video-Signals mit einer ersten Zeilenzahl je Sekunde und mit einem mit dem Eingangskreis gekoppelten Zeilenzahlwandler zum Liefern eines Ausgangs-Videosignals mit einer größeren Zeilenzahl pro Sekunde, wobei der Zeilenzahlwandler eine Bewegungsschätzanordnung aufweist zum Liefern von Bewegungsvektoren und eine bewegungskompensierte Inteipolationsanordnung zum Liefern des Ausgangs-Videosignals in Abhängigkeit von den Bewegungsvektoren, wobei die Bewegungsschätzanordnung Mittel aufweist zum Liefern eines Prädiktionsvektors, und gekennzeichnet durch Mittel zum pseudobeliebigen Selektieren eines Aktualisierungsvektors aus einem Satz von Aktualisierungsvektoren, und durch Mittel zum Addieren des pseudobeliebig selektierten Aktualisierungsvektors zu dem Prädiktionsvektor, zum Erhalten eines neuen Vektors. Sehr einfache und vorteilhafte Ausführungsformen der Erfindung werden in den Unteransprüchen definiert.According to a first aspect, the invention provides a motion estimation method as defined in claim 1. According to a second aspect, the invention provides a motion estimation arrangement as defined in claim 7. According to a third aspect, the invention provides a video signal receiver with an input circuit for receiving a video signal with a first number of lines per second and with a line number converter coupled to the input circuit for supplying an output video signal with a larger number of lines per second, the line number converter having a motion estimation arrangement for supplying motion vectors and a motion-compensated interpolation arrangement for supplying the output video signal in dependence on the motion vectors, the motion estimation arrangement having means for supplying a prediction vector, and characterized by means for pseudo-arbitrarily selecting an update vector from a set of update vectors, and by means for adding the pseudo-arbitrarily selected update vector to the prediction vector to obtain a new vector. Very simple and advantageous embodiments of the invention are defined in the subclaims.

Wenn ein Aktualisierungsvektor mit einer scheinbar beliebigen Größe und Richtung aus einem Satz von Aktualisierungsvektoren mit verschiedenen Aktualisierungsvektoren unterschiedlicher Größe und Richtung selektiert wird, ist die erhaltene Schätzungsqualität bei Gebrauch nur eines oder einer sehr geringen Anzahl Aktualisierungsvektoren vergleichbar mit der Schätzungsqualität, die erhalten wird, wenn eine Anzahl Aktualisierungsvektoren mit anderer Größe und Richtung als bei bekannten Anordnungen verwendet werden. Überraschenderweise zeigte sich, daß der Gebrauch eines einzigen pseudobeliebigen Aktualisierungsvektors bessere Bewegungsvektoren ergab als der Gebrauch verschiedener "fester" Aktualisierungsvektoren. Es dürfte einleuchten, daß der Gebrauch nur eines oder einer sehr geringen Anzahl Aktualisierungsvektoren die Möglichkeit einer einfacheren Hardware-Implementierung schafft.When an update vector with a seemingly arbitrary size and direction is selected from a set of update vectors with several update vectors of different sizes and directions, the quality of the estimate obtained using only one or a very small number of update vectors is comparable to the quality of the estimate obtained using a number of update vectors with different sizes and directions than in known arrangements. Surprisingly, it was found that the use of a single pseudo-arbitrary update vector gave better motion vectors than the use of several "fixed" update vectors. It should be clear that the use of only one or a very small number of update vectors creates the possibility of a simpler hardware implementation.

Ein Ausführungsbeispiel der Erfindung ist in der Zeichung dargestellt und wird im Folgenden näher beschrieben. Es zeigen:An embodiment of the invention is shown in the drawing and is described in more detail below. They show:

Fig. 1 eine Ausführungsform einer Bewegungsschätzanordnung nach der vorliegenden Erfindung.Fig. 1 shows an embodiment of a motion estimation arrangement according to the present invention.

In Fig. 1 wird ein Signal der Pixelblockfrequenz fBL, d. h. ein Signal das einmal für jeden Pixelblock in dem Bild auftritt, einem Takteingang eines Zählers 1 zugeführt. Der Zählerausgang ist mit einer Vergleichsschaltung 2, sowie mit einem Adresseingang eines Verweistabellenfestwertspeichers (LUT) 3 verbunden. Der LUT 3 enthält die horizontaln Elemente Ux und die vertikalen Elemente Uy von M möglichen Aktualisierungsvektoren. Die Vergleichsschaltung 2 vergleicht den Ausgang des Zählers 1 mit der Anzahl M und stellt den Zähler 1 zurück, wenn dessen Ausgang den Wert M erreicht. Die Aktualisierungsvektorelemente Ux, Uy, angegeben durch den Zählerausgang, werden den Addierern 4, 5 zugeführt, in denen sie zu den Prädiktionsvektorelementen Px, Py hinzuaddiert werden. Die Addierer 4, 5 liefern neue Vektorelemente Nx, Ny.In Fig. 1, a signal of the pixel block frequency fBL, i.e. a signal that occurs once for each pixel block in the image, is fed to a clock input of a counter 1. The counter output is connected to a comparison circuit 2 and to an address input of a look-up table read-only memory (LUT) 3. The LUT 3 contains the horizontal elements Ux and the vertical elements Uy of M possible update vectors. The comparison circuit 2 compares the output of the counter 1 with the number M and resets the counter 1 when its output reaches the value M. The update vector elements Ux, Uy, indicated by the counter output, are fed to the adders 4, 5, in which they are added to the prediction vector elements Px, Py. The adders 4, 5 provide new vector elements Nx, Ny.

Wenn dieser neue Vektor (Nx, Ny) als Kandidatvektor verwendet wird, dessen Schätzungsfehler mit dem anderer Kandidatvektoren in anderen (nicht dargestellten) Teilen der Bewegungsschätzanordnung verglichen wird, kann der LUT 3 weiterhin einen Strafwert Pn liefern entsprechend dem neuen Vektor (Nx, Ny). Eine Bewegungsschätzung, in der Schätzungsfehler verschiedener Kandidatvektoren um die betreffenden Strafwerte vermehrt werden, bevor der Kandidatvektor mit dem geringsten Schätzungsfehler selektiert wird, ist an sich aus EP-A-0.474.276 bekannt. Ein anderes einfaches Verfahren zum Erhalten des Strafwertes Pn startet von den summierten Längen der Aktualisierungsvektorelementen. Bevorzugte andere Kandidatvektoren sind der Null-Vektor, der Prädiktionsvektor (Px, Py) selbst und ein Vektor, der während einer vorhergehenden Teilbildperiode für einen zweiten benachbarten Block geschätzt worden ist.If this new vector (Nx, Ny) is used as a candidate vector, the estimation error of which is compared with that of other candidate vectors in other (not shown) parts of the motion estimation arrangement, the LUT 3 can further provide a penalty value Pn corresponding to the new vector (Nx, Ny). A motion estimation in which estimation errors of various candidate vectors are multiplied by the respective penalty values before the candidate vector with the smallest estimation error is selected is known per se from EP-A-0.474.276. Another simple method for obtaining the penalty value Pn starts from the summed lengths of the update vector elements. Preferred other candidate vectors are the zero vector, the prediction vector (Px, Py) itself and a vector estimated during a previous field period for a second neighboring block.

Wenn zwei Vektor-Schätzungsanordnungen parallel verwendet werden, wie in EP-A-0.415.491 (PHN 13.068) detailliert beschrieben, sind die von den LUTen dieser beiden Schätzungsanordnungen gelieferten Aktualisierungen einander vorzugsweise nicht glich.When two vector estimation systems are used in parallel, as described in detail in EP-A-0.415.491 (PHN 13.068), the updates provided by the LUTs of these two estimation systems are preferably not equal to each other.

Der LUT 3 enthält vorzugsweise die Aktualisierungsvektoren (0,1), (0,-1), (0,2), (0,-2). (1,0), (-1,0), (3,0) und (-3,0), so daß M gleich 8 ist. Die Reihenfolge der Aktualisierungsvektoren in dem LUT 3 können beliebig gewählt werden, sie sollen aber in einer pseudo-beliebigen Reihenfolge ausgelesen werden. Gewünschtenfalls können einige der Aktualisierungsvektoren einige Male in dem LUT 3 erscheinen. Wie dem auch sei, die Adressierung des LUTs 3 durch den Zähler 1 ergibt eine zyklische Selektion eines Aktualisierungsvektors aus dem Satz von Aktualisierungsvektoren. Die Länge dieses Zyklus kann derart gewählt werden, daß ein nicht-ganzzahliges Vielfaches der Zykluslänge der Anzahl Bλocke in der horizontalen und vertikalen Richtung entspricht; wobei auf alternative Weise ein ganzzahliges Vielfaches gewählt werden kann.The LUT 3 preferably contains the update vectors (0,1), (0,-1), (0,2), (0,-2), (1,0), (-1,0), (3,0) and (-3,0) so that M is 8. The order of the update vectors in the LUT 3 can be chosen arbitrarily, but they should be read out in a pseudo-arbitrary order. If desired, some of the update vectors can appear several times in the LUT 3. In any case, addressing the LUT 3 by the counter 1 results in a cyclic selection of an update vector from the set of update vectors. The length of this cycle can be chosen such that a non-integer multiple of the cycle length corresponds to the number of blocks in the horizontal and vertical directions; alternatively, an integer multiple can be chosen.

Hilfspixelgenauigkeit der Bewegungsschätzung kann auf sehr einfache und effiziente Weise dadurch erhalten werden, daß in den Aktualisierungsvektorsatz ganzzahlige Aktualisierungsvektoren sowie nicht-ganzzahlige Aktualisierungsvektoren aufgenommen werden, wobei nicht-ganzzahlige Aktualisierungsvektoren Aktualisierungsvektoren mit wenigstens einem nicht-ganzzahligen Aktualisierungsvektorelement Ux, Uy sind.Auxiliary pixel accuracy of motion estimation can be obtained in a very simple and efficient way by including integer update vectors and non-integer update vectors in the update vector set , where non-integer update vectors are update vectors with at least one non-integer update vector element Ux, Uy.

Weitere Einzelheiten über eine Bewegungsschätzanordnung, bei der die vorliegende Ausführungsform vorzugsweise verwendet wird zum Liefern eines der Kandidatvektoren, aus denen der Ausgangsvektor selektiert wird, sind in EP-A- 0.415.491 und EP-A-0.474.276 eingehend beschrieben, so daß es sich erübrigt, diese Einzelheiten bei dieser Anmeldung zu beschreiben.Further details of a motion estimation arrangement in which the present embodiment is preferably used to provide one of the candidate vectors from which the output vector is selected are described in detail in EP-A-0.415.491 and EP-A-0.474.276, so that it is unnecessary to describe these details in this application.

Obschon die oben beschriebene Verweistabelle wegen deren Einfachheit sehr vorteilhaft ist, sei es erwähnt, daß alle anderen Mittel zum Erzeugen eines pseudobeliebigen Aktualisierungsvektors aus einem Satz erlaubter Aktualisierungsvektoren geeignet sind. Der Fachmann wird imstande sein, im Rahmen der durch die nachfolgenden Ansprüche definierten Erfindung, viele alternative Ausführungsformen zu schaffen.Although the look-up table described above is very advantageous because of its simplicity, it should be noted that all other means for generating a pseudo-arbitrary update vector from a set of allowed update vectors are suitable. The person skilled in the art will be able to create many alternative embodiments within the scope of the invention defined by the following claims.

Claims

1. Method for estimating motion vectors, this method comprising the following method step:

providing a prediction vector (Px, Py); and which is characterized by the following method steps: pseudo-arbitrary selection (3) of an update vector (Ux, Uy) from a set of update vectors; and

adding (4, 5) the said pseudo-arbitrarily selected update vector (Ux. Uy) to the prediction vector (Px, Py) to obtain a new vector (Nx, Ny).

2. The method of claim 1, wherein said selecting step (3) comprises a selection in a predetermined cyclic order.

3. Method according to claim 2, wherein said selection comprises a sequential reading of update vector elements from a look-up table (3), wherein for each new vector (Nx, Ny) a set (Ux, Uy) of update vector elements is read out for each pixel block.

4. Method according to claim 3, wherein said reference table (3) provides penalty values (Pn) corresponding to the pseudo-arbitrarily selected update vectors (Ux, Uy), wherein from said motion vectors, by selecting from at least two candidate vectors, each of which has an estimation error to which a penalty value (Pn) is added, the candidate vector which has a minimal sum of estimation errors and penalty values (Pn) is selected, wherein the new vector (Nx, Ny) is one of the candidate vectors, and wherein the penalty values are preferably obtained as a dependence on a summed length of the update vector elements (Ux. Uy).

5. Method according to claim 1, wherein at least two new vectors (Nx, Ny) are obtained by adding two mutually different pseudo-arbitrarily selected update vectors (Ux, Uy) to two respective prediction vectors (Px, Py).

6. The method of claim 1, wherein said update vector set (3) comprises integer update vectors and non-integer update vectors, wherein the non-integer update vectors are update vectors having at least one non-integer vector element.

7. Motion estimation arrangement with:

Means for providing a prediction vector (Px, Py); and characterized by: Means (3) for pseudo-arbitrarily selecting an update vector (Ux, Uy) from a set of update vectors; and

Means (4, 5) for adding said pseudo-arbitrarily selected update vector (Ux, Uy) to said prediction vector (Px, Py) to obtain a new vector (Nx, Ny).

8. Video signal receiver with an input circuit for receiving a video signal with a first number of lines per second and with a line number converter coupled to the input circuit for supplying an output video signal with a larger number of lines per second, the line number converter having a motion estimation arrangement for supplying motion vectors and a motion-compensated interpolation arrangement for supplying the output video signal in dependence on the motion vectors, the motion estimation arrangement having means for supplying a prediction vector (Px, Py), and is characterized by means (3) for pseudo-arbitrarily selecting an update vector (Ux, Uy) from a set of update vectors, and by means (4, 5) for adding the pseudo-arbitrarily selected update vector to the prediction vector (Px, Py) to obtain a new vector (Nx, Ny).