Title of Invention

TRANSFER SYSTEM

Abstract

A method for estimating motion between an incoming frame F(n) of a I sequence of frames and a large static image M( n-1), said large static image being constructed from previous frames F(l) ...F(n-l) of said sequence, said motion estimation method using a motion model based on a two-dimensional perspective transform containing eight motion parameters and comprising an optimization step of a cost function, said eight motion parameters being the coordinates of the four vertices of the incoming frame, said vertices being successively moved in two directions to find an estimation of the motion parameters corresponding to an optimum of the cost function, characterized in that the cost function is derived from a sum, for a set of pixels, of products of a square of a difference rp between original and predicted values of a pixel p by a weighting coefficient

Full Text

.FIELD OF THE INVENTION The present invention relates to a method and its corresponding device for estimating motion between an incoming frame F(n) of a sequence of frames and a large static image M(n-l), said large static image being constructed from previous frames F(l) ...F(n-l) of said sequence, said motion estimation method using a motion model based on a two- dimensional perspective transform containing eight motion parameters and comprising an optimization step of a cost function. Such an invention can be useful for applications related to MPEG-4 and, more especially, to MPEG- 7 standard, such as sprite generation or mosaicing. BACKGROUND OF THE INVENTION A method of the above kind is known from the patent application WO 98/59497. This patent application describes a method used in video coding for generating a sprite from the video objects in the frame of a video sequence. The method estimates the global motion between a video object in a current frame and a sprite constructed from video objects for previous frames. Specifically, the global motion estimation method computes motion coefficients of a two-dimensional transform that minimizes the intensity errors between pixels in the video object and corresponding pixels in the sprite. The Levenberg- Marquardt method is employed for the minimizing step, which consists in the minimization of an analytical function related to the intensity errors, and allows to select the most representative points and reject the others as outliers. Nevertheless, the previously described global motion estimation method has several drawbacks. The major one is that it is very sensitive to outliers, which are pixels that .do not follow the global motion and corresponds to objects having their own motion. It means that the global motion estimation method can sometimes fail with some particular video sequences. Another drawback is also its inability to converge efficiently and fast for certain kind of video sequences. SUMMARY OF THE INVENTION It is therefore an object of the present invention to propose another global motion estimation method that is very robust to outliers but that can also allow an efficient and fast convergence. To this end, the method according to the invention is characterized in that the eight motion parameters are the coordinates of the four vertices of the incoming frame, said vertices being successively moved in two directions to find an estimation of the motion parameters corresponding to an optimum of the cost function. The motion estimation method is based on a geometrical approach that treats successively and iteratively the eight motion parameters by optimizing a numerical function whereas the approach of the background art, based on the Levenberg-Marquardt algorithm, treats the eight motion parameters simultaneously by minimizing an analytical function. As a consequence, the motion estimation method based on the displacement of the four vertices has proved to be more robust to outliers than the one used in the background art. The method according to the invention is also characterized in that the motion estimation method includes a first iterative method that comprises, at each iteration, the optimization step to determine an estimation of the eight motion parameters, followed by a step of calculation of the two directions of motion of each of the four vertices by taking into account the last deformation, said iterative method being performed until a defined criteria is reached. The iterative method is based on the Powell's algorithm that improves the convergence of said method. The method according to the invention is finally characterized in that the optimization step comprises a second iterative method performing, at each iteration, a parabolic interpolation operation of values of the cost function to estimate successively the motion parameters. The use of a parabolic interpolation operation makes the convergence of the motion estimation method faster, especially in the case of large motion. As a consequence, the present motion estimation method could be advantageously included in a method for generating a large static image, such as a sprite or a mosaic, and implemented in a device for generating such a large static image. These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter. *RIEF DESCRIPTION OF ffiE DRAWINGS The present invention will now be described, by way of example, with reference to the accompanying drawings, wherein: Fig. 1 shows a geometrical representation of the optimization step for the first iteration, Fig. 2 is a flowchart for the process used to perform the automatic initialization of the motion parameters for the two first pictures, Fig. 3 is a flowchart for the iterative process used to optimize the motion parameters, Fig. 4 shows a geometrical representation of the optimization step for the iteration (1+1), Fig. 5 shows a scheme of a large static image generation device. DESCRIPTION OF THE INVENTION The present invention proposes a new global motion estimation method between an incoming frame F(n) of a sequence of frames and a large static image M(n-l), which is constructed from previous frames F(l), F(2),..., F(n-1) of the video sequence. The principle of the motion estimation method is depicted in Figure 1. Said motion estimation method uses a motion model based on a two-dimensional perspective transform, which is also called the perspective model, in order to characterize the motion between two frames. This model contains eight motion parameters and is preferably chosen because it allows more camera motion possibilities than the other ones, such as, for example, translation, zoom, or rotation. The use of the perspective model is valid in the two following cases: All views share the same optical center. This is more or less the case when a camera is fixed to a rotating tripod: the rotation axis may pass through or very near the optical center of the camera. If the captured objects are very far from the camera, this assumption is always verified. The captured scene corresponds to a flat surface. A perspective projection transforms a rectangle into a quadrilateral. The two-dimensional coordinates of the four vertices of the quadrilateral completely define the eight motion parameters ao to a7 of the perspective projection. Thus, the eight motion parameters are, in the present invention, the two-dimensional coordinates of the four vertices, which are at the beginning of the process A(0) (ao(0), a,(0)), B(0) (a2(0), a3(0)), C(0) (a*(0), as(0)) and D(0)(a6(0)>a7(0)). The motion estimation method according to the invention enables any displacement of the four comers of the original rectangular image to fit the next one by optimizing a cost function. Starting from an initial position for these four vertices, corresponding to an initial set of motion parameters, the method tries to optimize the cost function by slight displacements of the four vertices. Each vertex is displaced by a small amount around its initial position in order to find a local optimum for the cost function. For example, A(0) is moved along the direction d|(0), which is in this particular case an horizontal direction, in order to find an optimum of the cost function. Then, the obtained point is moved along the direction dj(0), which is in this particular case a vertical direction, until another optimum is found giving a new vertex A(l) (ao(l), ai(l))- This operation is then performed successively for the other vertices and a new quadrilateral image is obtained. In the preferred embodiment the cost function is related to the Displaced Frame Difference (DFD). The DFD measurement is computed on the pixels belonging to the area S overlapping both incoming frame F(n) and current large static image M(n-l) as follows: DFD = £Vp2 where rp is a difference between original and predicted values of s a pixel p defined as follows: rp=L(x,y)-L(x'/y*) where: - L(x,y) is the luminance value of the video signal corresponding to the pixel p(x,y) of the incoming frame F(n), L(x',y') is the luminance value of the video signal corresponding to the pixel p'(x\y') of the large static image M(n-1). (x'.y') are the floating point value of the pixel p' to be extracted from the large static image. The value of the luminance corresponding to this pixel is calculated with respect to the four closest integer coordinates in the image, which are (xo,yo), (xi,yi), (X2.v2), (X3,y3) with respective luminance values LO, LI, L2 and L3, using a bilinear interpolation; a calculation sub-step (CALC) of the value j of the pixel position corresponding to the minimum of the cost function costQ when applying translations on the incoming frame in an horizontal direction, the amplitude i of the translation vector being comprised where Argmin is the function that returns the abscissa corresponding to the minimum of the cost function, giving here the displacement between the two frames for the considered direction, a test (Cj) on the value of j, if the test is not satisfied (j is not equal to zero), a sub-step of re¬calculation (INC) of the value xx_min: xxmin = xx_min + j, if the test is satisfied (j = 0), the end of the process (RES) giving the final translation xx_min in the horizontal direction. The same algorithm is applied in the vertical direction in order to find the translation yy_mra to be performed. Figure 3 is a flowchart showing the iterative process used to optimize the motion parameters. This method is based on Powell's convergence method. The set of eight motion parameters, corresponding to the coordinates of the four vertices, is initialized to values given by the prediction of global motion, in a*(Q) with ) The step of optimization of the motion parameters comprises: an initialization sub-step (TNIkl) of k and of a counter 1: k = 1 = 0, a test (Ck) on the value of k, if the value of k is strictly lower than 8 (y), a sub-step of calculation (PI) of the value of the motion parameter at(!+l), which corresponds to a nunimum of the cost fttnction cost(): ak(l + l)= Argmin [cost (ak(t)+i)] ieSR followed by a sub-step of incrementation by one of k (INCk), in the contrary case (n), a second test (Ca) on the maximum M, for the different values of k, of the absolute value of the difference between atfl+11 and aM): M = max(|ak(Ul)-a)((l)j), if the value of M is inferior to a threshold (y), the end of the process (RESa) giving the values of arfl+l), in the contrary case (n), a sub-step of computation of new directions of minimization (DIR), followed by a sub-step of incrementation by one of 1 (INC1) and a sub-step of re-initialization of k (TNJk). The sub-step of calculation (PI) of the value akfl+l) is performed using parabolic interpolations. A first parabolic interpolation is performed on the values of the cost function corresponding to three consecutive pixels. Then, a new parabolic interpolation is performed on the three pixels nearest the minimum of the parabola previously found. The process ends when the minimum of the parabola is comprised in the window defined by the three investigated pixels. Such a calculation method increases the convergence of the optimization step. When a parabolic interpolation operation is not possible (that is when the parabola has a maximum instead of a minimum), the calculation of the value of a^l+l) is performed using a gradient descent, which consists in successive comparisons of values of the cost function of consecutive pixels until a minimum of said cost function is reached. When 1 = 0, the directions followed by the eight parameters for nunimizing the cost function are horizontal for abscissa or vertical for ordinates, as described in figure 1. When 1> 1,the directions followed for optimization are reviewed given the last deformation, as described in figure 4. The optimization direction are defined as the direction di(l) going from the vertex A(I-l) to the vertex A(l) and its perpendicular d2(l) and so on for the three other vertices. This motion estimation method can be used in a method and its corresponding device for generating a large static image M(n), such as a sprite or a mosaic. Such a method is described in figure 5. Three main steps may compose a large static image M(n) generation. First, the global motion estimation step (ME) according to the invention has to be performed in order to merge the incoming frame F(n) with the Jarge static image M(n-1) already composed of the previous frames F(l)> F(2), ■■ -, F(n-1). Said global motion estimation step (ME) gives the motion parameters ak. The current frame is then compensated using the motion parameters; this second step is also called warping (WAR). The warped current frame F(n) is finally blended (BLE) with the large static image M(n-1) in order to form a new accreted large static image M(n) giving a panoramic view of the scene, which is stored in a memory (MEM) in order to be merged with the next incoming frame F(n+1), and so on. WE CLAIM : 1. A method for estimating motion between an incoming frame F(n) of a I sequence of frames and a large static image M( n-1), said large static image being constructed from previous frames F(l) ...F(n-l) of said sequence, said motion estimation method using a motion model based on a two-dimensional perspective transform containing eight motion parameters and comprising an optimization step of a cost function, said eight motion parameters being the coordinates of the four vertices of the incoming frame, said vertices being successively moved in two directions to find an estimation of the motion parameters corresponding to an optimum of the cost function, characterized in that the cost function is derived from a sum, for a set of pixels, of products of a square of a difference rp between original and predicted values of a pixel p by a weighting coefficient wp which value depends on the difference rp. 6. The method as claimed in claim 1, wherein said motion estimation method comprises a step of automatic initialization of said motion parameters for the two first frames using a two-dimensional translation transform. 7. The method as claimed in claim 1 wherein said motion estimation method comprises a first iterative method that comprises, at each iteration, said optimization step to determine an estimation of the eight motion parameters, followed by a step of calculation of the two directions of motion of each of the four vertices by taking into account the last deformation, said iterative method being performed until a defined criteria is, reached. 8. The method as claimed in claim 7 wherein said optimization step comprises a second iterative method performing, at each iteration, a parabolic interpolation operation of values of said cost function to estimate successively the motion parameters. 9. A method for generating a large static image M(n)comprising the steps of: -estimating motion between an incoming frame F(n) of a sequence of frames and a large static image M(n-I), said large static image being constructed from previous frames F(I) ...F(n-l) of said sequence, said motion estimation method using a motion model based on a two-dimensional perspective transform containing eight motion parameters and comprising an optimization step of a cost function, said eight motion parameters being the coordinates of the four vertices of the incoming frame, said vertices being successively moved in two directions to find an estimation of the motion parameters corresponding to an optimum of the cost function, the cost ■a H* function being derived from a sum, for a set of pixels,of products.of a square of a difference rp between original and predicted values of a pixel p .by a weighting coefficient wp which value depends on the difference rp, -compensating for the incoming frame F(n) using the estimated motion parameters, -blending the compensated incoming frame F(n) with the large static image M(n-1) to form the large static image M(n). 10. A device for generating a large static image M(n)comprising: -means for estimating motion between an incoming frame F(n) of a sequence of frames and a large static image M(n-l), said large static image being constructed from previous frames F(l) ...F(n-l) of said sequence, said device implementing a motion model based on a two-dimensional perspective transform containing eight motion parameters and comprising means for optimizing a cost function, said eight motion parameters being the coordinates of 10 the four vertices of the incoming frame, said vertices being successively moved in two directions to find an estimation of the motion parameters corresponding to an optimum of the cost function, the cost function being derived from a sum, for a set of pixels, of products of a square of a difference rp between original and predicted values of a pixel p by a weighting coefficient wp which value depends on the difference rp, -means for compensating for the incoming frame F(n) using the estimated motion parameters,

Documents:

in-pct-2001-0685-che claims-duplicate.pdf

in-pct-2001-0685-che claims.pdf

in-pct-2001-0685-che correspondnece-others.pdf

in-pct-2001-0685-che correspondnece-po.pdf

in-pct-2001-0685-che description(complete)-duplicate.pdf

in-pct-2001-0685-che description(complete).pdf

in-pct-2001-0685-che drawings-duplicate.pdf

in-pct-2001-0685-che drawings.pdf

in-pct-2001-0685-che form-1.pdf

in-pct-2001-0685-che form-19.pdf

in-pct-2001-0685-che form-26.pdf

in-pct-2001-0685-che form-3.pdf

in-pct-2001-0685-che form-5.pdf

in-pct-2001-0685-che others.pdf

in-pct-2001-0685-che pct.pdf

in-pct-2001-0685-che petition.pdf