Method and device for estimation of motions of image portions for moving image compression circuits

[0002] 1. Field of the Invention

[0003] The present invention relates to a circuit for compression of moving images, such as television images. It more specifically relates to the estimation of motions of portions of images, a portion of a current image being compared with its environment in the preceding image.

[0004] 2. Discussion of the Related Art

[0005] A circuit of this type is used for coding the images so that they can be transmitted, in the context of a video image transmission, while minimizing the amount of information to be transmitted. The compression performed by the circuit consists, among others, in performing an estimation of the motion between portions of two successive images. This motion estimation enables to code, and thus to transmit, for portions of a current image, only motion vectors and distortion information associated with these portions.

[0006] The images, for example, coming from a video camera, are cut into image portions, called “macroblocks”. These macroblocks generally correspond to a cutting up of the image into squares, each square having a dimension of 16×16 pixels. An image is stored sequentially, line by line, in a video memory, and the pixels so stored are extracted from this video memory by sets of pixels corresponding to square portions of the image. These sets of pixels, or macroblocks, are stored in a cache memory, to be used by a computer for, among others, determining the motion vector of the considered macroblock.

[0007] To perform the motion estimation of a macroblock, the computer is provided not only with the pixels of the considered macroblock of the current image, but also with pixels surrounding the corresponding macroblock in the preceding image. The computer sequentially processes each macroblock of the current image, by using, at least partially, the pixels of neighboring macroblocks in the preceding image which constitute a set of reference values, called the “reference window”. In practice, a first cache memory contains the current macroblock and a second cache memory contains a larger reference window. This reference window includes, in addition to the pixels of the considered macroblock in the preceding image, at least part of the pixels of the macroblocks of the preceding image which are sequentially neighbor thereto in all directions.

[0008] FIG. 1 schematically shows an example of motion estimation device to which the present invention applies.

[0009] This device communicates by means of buses 1, 2, with a processor that controls the moving image compression circuit and with a processor that controls access to a video memory containing the data to be processed. The motion estimator includes a first finished state machine 3 (TOP CONTROL) managing the operation of the motion estimator and, in particular, the writing of the data into cache memories 4 (CW_RAM) and 5 (SW_RAM) for containing, respectively, the current macroblock to be processed and the reference window associated therewith. State machine 3 includes a link 6 to bus 1 and transfers the data, that it receives via a link 7 to bus 2, to controllers 8, 9 (CTRL) of memories 4, 5, via links 10, 11, on which the data, the write addresses and the control signals altogether transit. An example of addressing of a cache memory of a moving image compression circuit is described in patent application Ser. No. 94/05339, the content of which is incorporated herein by reference.

[0010] The estimation of the motion of a macroblock consists of determining the motion vector of this macroblock with respect to a macroblock of the preceding image and the distortion between the two macroblocks, that is, the cumulated difference between the pixels of the two macroblocks. The motion vector is determined by searching, in the reference window, the macroblock which exhibits a minimum distortion.

[0011] The vector of motion of a current macroblock with respect to the position of this macroblock in the preceding image is determined by examining the cumulated distortion of all the pixels in this current macroblock with respect to the pixels of macroblocks extracted from the reference window in all the positions likely to be taken by the current macroblock in this reference window. For this purpose, the motion estimator includes a unit 12 (DIST_OPE) of operators organized in systolic architecture which calculate, in parallel for a given motion in one direction, the distortion of the current macroblock with respect to all motions in the other direction. Unit 12 includes two data inputs 13 and 14 connected to the data outputs of memories 4, 5, for receiving, for each calculation cycle, a new pixel from each of the memories. Unit 12 includes as many outputs 15 as it includes operators. These outputs are connected to a unit 16 (MIN_OPE) of determination of the minimum distortion to determine the motion vector of the current macroblock. An output 17 of unit 16 issues this motion vector and the corresponding distortion to a set of registers 18 (REG), communicating over a link 19 with state machine 3. The set of registers 18 is meant to store the operation parameters supplied by the control processor of the moving image compression circuit and the results of the operations performed. Units 12 and 16 communicate, via links 20 and 21, with a second finished state machine 22 (OPE_CONTROL) for, in particular, organizing the reading of the data from memories 4 and 5. Read control signals of memories 4 and 5 and information relative to the state of progress of the operational process are issued by outputs 23, 24 of state machine 22 to transcoders 25, 26 (TRC) respectively associated with memories 4, 5. Transcoders 25, 26 determine, based on state signals issued by machine 22 and coming from counters (not shown), the read addresses of memories 4, 5.

[0012] The motion estimator shown in FIG. 1 is likely to perform a hierarchic motion estimation, that is, an estimation including several phases of different level for each macroblock. A first phase corresponds, for example, to searching the minimum distortion based on a macroblock and a reference window decimated by a factor two and then determining a motion vector to within two pixels. A second phase consists of determining the motion vector to within half a pixel based on a macroblock and a reference window reconstituted by linear interpolation. The use of a hierarchic (or telescopic) process of motion estimation is well known in the art. For clarity, it will be spoken of a macroblock, be it a portion of a basic, decimated, or interpolation-obtained image. It should only be noted that the data present in memories 4 and 5 must be coherent with one another.

[0013] The different phases are performed by means of the same motion estimator, and state machine 3 communicates parameters characteristic of each phase to the different components of the estimator. For this purpose, state machine 3 uses links 27, 28, 29, with state machine 22, transcoder 25 and transcoder 26 as well as links 19, 20, and 21 previously described. It should be noted that all components of the motion estimator, including the state machine, the operator units and the transcoders are wired, that is, are implemented in hardware form, as opposed to a software form.

[0014] The use of a hierarchic search process is linked, in particular, with the size of the reference window and with the image transmission rate. Indeed, the larger the reference window, the more necessary it is to perform a great number of operations for a given image transmission rate. For example, in an H263 standard applied to videophony, the macroblocks contain 16×16 pixels and the search is to be performed with a motion of plus or minus 16 pixels in all directions. Further, this standard provides an accuracy which can be as much as to within half a pixel by linear interpolation. The application of a search in the entire reference window in a single phase as has been previously done for the application to an H261 standard is not applicable since it would lead to using too large a number of operators. Standard H261 applies to the processing of images in the so-called “QCIF” format transmitted at a rate of 15 images per second, where each image is formed of 99 macroblocks of 16×16 pixels. Standard H263 provides the processing of images in the so-called “CIF” format at a rate of 30 images per second, where each image includes 396 macroblocks of 16×16 pixels. The application of the methods used for standard H261 would lead to providing around 480 parallel operators.

[0015] Further, if the application of a hierarchic search process enables respecting the time constraints for the determination of the motion vectors of the entire macroblocks, standard H263 also provides an operating mode in which the accuracy is increased by determining the motion of four separate blocks in each macroblock. It is then no longer possible to maintain the time constraints of the images at the CIF format with a unit 12 including 16 parallel operators.

[0016] The present invention aims at providing a method and a device for motion estimation which reduces the time required for the estimation of the motion of at least some macroblocks of the images.

[0017] The present invention also aims at providing a method and a device of motion estimation which are compatible with both a hierarchic search and a single-phase search.

[0018] To achieve these objects, the present invention provides a method of estimation of the motion of a macroblock of pixels of a current image with respect to a reference window taken in a preceding image, including, in a first step, determining the cumulated distortion of the pixels of the current macroblock for a null motion vector in the reference window; choosing, as the motion vector of the current macroblock, the null vector if the distortion is lower than or equal to a first threshold; and otherwise choosing, in a second step, a vector for which the current macroblock exhibits a minimum distortion with respect to a macroblock of the reference window.

[0019] According to an embodiment of the present invention, this method includes, during the second step, comparing the distortion calculated for each motion vector with a minimum distortion previously calculated for a previously examined vector, the minimum distortion being initialized by the distortion calculated during the first step; and replacing the minimum distortion with the current distortion if the latter is lower.

[0020] According to an embodiment of the present invention, this method includes, during the second step, comparing, for each modification of the minimum distortion, the value of this minimum distortion with a second predetermined threshold value; and choosing, as the motion vector of the current macroblock, the vector associated with this minimum distortion.

[0021] According to an embodiment of the present invention, the method includes, during the second step, using operators organized in systolic architecture to calculate, for each position of the current macroblock in a first direction of the reference window, the distortion between the current macroblock and several macroblocks in a second direction of the reference window; and interrupting the calculations of distortion performed for this position in the first direction if, during the calculations, the distortions become, for all positions in the second direction, higher than the minimum distortion.

[0022] According to an embodiment of the present invention, the method includes a step intermediary between the first and second steps including calculating the distortion between the current macroblock and the mean value of the pixels of this macroblock; and interrupting the motion estimation of the current macroblock if the distortion with respect to the mean value of the pixels is lower than or equal to a third predetermined threshold.

[0023] The present invention also provides a device for estimation of the motion of a macroblock of a current image in a reference window containing the current macroblock and its environment in a preceding image, including: a first cache memory for containing the current macroblock; a second cache memory for containing the reference window; and a unit of operators, organized in systolic architecture and supplied by a reading from the cache memories, for calculating, for each position of the current macroblock in a first direction of the reference window, the distortion between the current macroblock and several macroblocks of the reference window in a second direction of the reference window; and means implementing the above motion estimation method.

[0024] The foregoing objects, features and advantages of the present invention will be discussed in detail in the following non-limiting description of specific embodiments made in connection with the accompanying drawings.

[0025] FIG. 1, previously described, is meant to show the state of the art and the problem to solve;

[0026] FIG. 2 schematically shows a macroblock to be processed and a reference window of its environment in the preceding image;

[0027] FIG. 3 shows, in the form of a simplified flowchart, an embodiment of the method according to the present invention for estimating the motion of a given macroblock;

[0028] FIG. 4 illustrates, in the form of a flowchart, an embodiment of a phase of scanning of a reference window according to the present invention; and

[0029] FIG. 5 shows, in the form of a flowchart, a detail of a block of FIG. 4.

[0030] For clarity, only those elements of the device and those steps of the method which are necessary to the understanding of the present invention have been shown in the drawings.

[0031] A characteristic of the present invention is to start the motion estimation for each macroblock with a calculation of the distortion of this macroblock with respect to the same macroblock in the preceding image, that is, with a null motion, and to proceed to the processing of the next macroblock if the distortion is lower than a predetermined threshold. This threshold corresponds to a sufficiently low distortion value for which it is assumed that the macroblock is identical to the macroblock of same position of the preceding image, that is, this portion of the image has remained substantially unaltered. Thus, a scanning of the reference window associated with each macroblock is performed to determine the minimum distortion, only if necessary. Thus, for the image portions which remain unaltered, a considerable number of calculation cycles is saved.

[0032] Another characteristic of the present invention is that, during the determination of the minimum distortion of the current macroblock based on a parallel calculation of this distortion in a given direction (for example, the vertical direction) of the reference window for each position in the other direction (for example, the horizontal direction), the distortion calculations are interrupted to proceed to the following horizontal position if, during the calculation, the distortions become, for all the vertical positions, higher than the minimum distortion already found.

[0033] FIG. 2 shows an example of macroblock to be processed and the reference window associated therewith, that is, the respective contents of cache memories 4 and 5 for the processing of a given macroblock.

[0034] In this example, a macroblock MB(k, t) to be processed of the current image is a square array of(n+1).(n+1) pixels. The reference window SW(k, t−1) associated therewith in the preceding image further includes macroblock MB(k, t−1), the eight macroblocks which surround the latter in the preceding image in all directions.

[0035] In the following, “macroblock” will be used to designate the set of values submitted to the motion estimation method according to the present invention, be it a macroblock decimated by a factor two or a macroblock reconstituted by linear interpolation to within one half pixel. Thus, for image macroblocks of 16×16 pixels to be analyzed in a reference window of 48×48 pixels, macroblock MB(k, t) shown in FIG. 2 includes 8×8 pixels after decimating the original macroblock for a motion estimation to within two pixels, reference window SW(k, t−1) including 24×24 pixels. For the motion estimation to within one half pixel, the macroblock and the reference window respectively correspond to sets of 16×16 pixels and 8×8 pixels, this calculation phase to within one half pixel corresponding to improving the determination to within two pixels.

[0036] An embodiment of the method according to the present invention for squares macroblocks and reference windows, respectively of (n+1).(n+1) and 3(n+1).3(n+1) pixels by means of 2(n+1) operators in systolic architecture, will be discussed hereafter. The transposition of the described operation to arrays of different dimensions is performed by adapting the addressing of the cache memories in the read mode and/or the number of operators used in the series of operators of the motion estimator.

[0037] FIG. 3 very schematically shows an embodiment of the method according to the present invention. The example shown corresponds to the motion estimation for a macroblock MB(k, t) of rank k (block 30) in the current image.

[0038] First (block 31), distortion Δ(k) between macroblock MB(k, t) and this same macroblock MB(k, t−1) in the reference window, that is, the distortion for a null motion, is determined. The determination of the distortion for a null motion can be performed on a decimated or undecimated macroblock.

[0039] Then (block 32), a determination of the distortion Δ_Ibetween macroblock MB(k, t) and the mean value of the pixels of the macroblock is performed. The mean value of all pixels of the macroblock is thus first calculated. Then, the distortion calculation performed by operator unit 12 (FIG. 1) is applied by using a single operator successively receiving all the pixels in memory 4 and, for each calculation, the same value on its input 14.

[0040] If desired, distortions Δ(k) and Δ_Ican be performed simultaneously if the systolic architecture organization of the operators of unit 12 can be parametered to make two of these operators individually usable.

[0041] Then (block 33), distortion Δ(k) is compared with a predetermined threshold S0. Threshold S0 is chosen to correspond to a distortion value acceptable for substantially fixed images. If Δ(k)S0, the result of the motion estimation stored in registers 18 corresponds to a null vector V(k) and to distortion Δ(k) (block 34). Otherwise (block 35), distortion Δ_Iis compared with a predetermined threshold S_I. This comparison 35 is directed, according to a characteristic of the present invention, to selecting a macroblock of very low contrast (very uniform). If Δ_IS_I, this then means that the variable-length coding performed on the macroblock for its transmission will lead to a specifically short data message since, after coding a first pixel of this macroblock, the other pixels of the macroblock can be coded with a very low number of bits due to the inverse cosine transform coding method used for this kind of transmission.

[0042] This characteristic of the present invention reduces the duration of the image transmission. Indeed, the standards provide that each macroblock is to be transmitted integrally (in so-called “Intra” mode) at maximum intervals (for example, every 100 images) to regenerate the motion estimation in order to reduce the effect of error accumulations linked with image compression. An advantage of the present invention is that instead of transmitting at fixed intervals a macroblock in Intra mode, at the risk of having to transmit it when it is of particularly high contrast, a transmission in Intra mode is selected (block 36) when the block has little contrast. Whether at the end of step 34 or 36, the following macroblock of the current image is then processed (block 37).

[0043] If the result of the comparison performed in step 35 is negative, a scanning of the reference window is then performed to determine the motion vector associated with a minimum distortion of the current macroblock.

[0044] As indicated previously, this motion estimation by scanning can be performed in several phases (blocks 38 and 39).

[0045] FIGS. 4 and 5 illustrate the operation of the method according to the present invention during a phase of scanning of the reference window.

[0046] This operation will be described by taking as an example a horizontal scanning of vertical motion vectors processed in parallel by unit 12 starting from vector [−(n+1); −(n+1)]. It should however be noted that the present invention applies whatever the direction processed in parallel by unit 12 and whatever the order (scanning or other) in which the motion vectors are examined.

[0047] In the example shown in FIGS. 4 and 5, the horizontal position x is first set (block 40) to value −(n+1). Then (block 41), the parallel determination of the distortions Δ(x, y) for all the vertical positions of the macroblock in the reference window are determined by means of unit 12, that is, for −(n+1)yn.

[0048] This determination is conventional and one could refer, for example, to application Ser. No. 08/423,581, filed Apr. 19, 1995 and entitled Device For Providing Pixels To A Series Of Operators Of A Circuit For Compressing Motion Pictures, now allowed, which is incorporated herein by reference. However, a characteristic of the present invention is to enable, in some cases which will be discussed hereafter in relation with FIG. 5, to interrupt this determination to proceed to the next horizontal position (arrow 42).

[0049] If the calculation of the distortion of the entire macroblock is completed, the minimum distortion among the 2(n+1) values obtained is determined by means of unit 16. For example, a counter of vertical position y is initialized (block 43) to value −(n+1), then Δ(x, y) is compared with a minimum distortion Δmin (block 44). If Δ(x, y)<Δmin, the value Δmin stored in unit 16 is replaced with the current value of Δ(x, y) and coordinates x, y, are also stored as corresponding to vector V(k) of motion of the current vector (block 45). Otherwise, the vertical position is incremented (block 46) and operations 44, 45, and 46 are repeated as long as value n has not been exceeded (block 47). It should be noted that value Δmin must have been initialized. For this purpose, value Δmin is, preferably, initialized to the previously calculated distortion value for a null motion (block 31, FIG. 3).

[0050] Then, the counter associated with the horizontal position (block 48) is incremented and steps 41, 43, 44, 45, 46, 47, 48, are repeated as long as all horizontal positions have not been examined, that is, as long as xn (block 49). Coordinates [x, y] corresponding to the motion vector V(k) for which distortion Δ(k)=Δmin are then available in unit 16 (block 50).

[0051] A characteristic of the present invention is to provide an interruption (block 51) of the macroblock processing if value Δmin modified at step 45 is lower than or equal to a predetermined threshold S1. This threshold is, for example, set to a value for which the economy in length of the message to be transmitted would be negligible if the search was continued to find a still lower distortion. An advantage of this characteristic is that it interrupts the processing as soon as a motion vector for which the distortion is acceptable has been found. However, this interruption 51 will preferably not be implemented for phases of motion estimation based on decimated macroblocks and reference windows. Indeed, in such a case, the exploited values correspond to mean values over several pixels. Thus, this step 51 will be, in the example shown in FIG. 3, implemented at step 39 and not at step 38.

[0052] The advantage of this characteristic is especially useful in an embodiment where the examination of the motion vectors is performed in an increasing order starting from a null motion vector. Indeed, in such a case, the motion determination is stopped as soon as the distortion is acceptable from the point of view of the length of the message to be transmitted and this interruption occurs for a minimum motion vector, that is, the variable-length coding of which requires a minimum message length.

[0053] Such an organization of the exploration of the reference window is, for example, performed by modifying the determination of the read addresses by transcoder 26 (FIG. 1) for the horizontal positions and by interpreting the distortion results in unit 16 from the central position of the vertical distortion vector issued by unit 12.

[0054] FIG. 5 illustrates another characteristic of the present invention implemented during the calculation of the distortions for different vertical positions with a same horizontal position. This drawing details block 41 of FIG. 4.

[0055] For each horizontal position x (block 51), a counter of horizontal positions i (block 52) and a counter of vertical positions j (block 53) of the pixels of macroblock MB(k, t) to be read from memory 4 are initialized. Then, conventionally, a calculation (block 54) of the distortion Δ(x, y, j) taking into account, for each operator of unit 12, the distortion value Δ(x, y, j−1) calculated with the preceding pixel of the current macroblock, the current pixel PC(i, j), and the pixel PC(x, y) of the reference window associated with the current vertical position j, is performed. The addressing of memories 4 and 5 in the read mode can be performed conventionally and at the end of step 54, intermediary distortion values Δ(x, y, j) for j−(n+1)yj+n are obtained.

[0056] Then, according to the present invention, a comparison (block 55) of these intermediary values with minimum distortion Δmin is performed. If all intermediary values are higher than or equal to Δmin, the distortion calculation for the next vertical vector, that is, for the next horizontal position x, is performed, without it being necessary to complete the calculation of the distortions for the current vertical vector.

[0057] An advantage of this characteristic of the present invention is that it enables interruption of the calculation, performed by means of unit 12 for a given horizontal position in the reference window, as soon as all the individual results of the operators are higher than a minimum distortion value previously found for another motion vector.

[0058] If there remains at least one intermediary value lower than minimum distortion Δmin, the calculation of the distortion in this horizontal position is carried on for all the vertical positions of the current macroblock in the reference window. Thus, the vertical position in the current macroblock is incremented (block 56) and steps 54, 55, and 56 are repeated until the last line of the macroblock is reached (block 57). Then, the horizontal position of the pixel read from the current macroblock is incremented (block 58) and steps 53, 54, 55, 56, 57, and 58 are repeated until the last pixel of the macroblock is processed (block 59).

[0059] If the distortion calculations have not been interrupted by block 55, then the distortions Δ(x, y) for 2(n+1) macroblocks (−(n+1)yn) with a same horizontal motion x are obtained.

[0060] An advantage of the present invention is that it considerably reduces, statistically, the calculation time required for the motion estimations of the macroblocks.

[0061] Another advantage of the present invention is that it applies whatever the read addressing mode used for cache memories 4 and 5.

[0062] Of course, the present invention is likely to have various alterations, modifications, and improvements which will readily occur to those skilled in the art. In particular, although reference has been made in the preceding description to a videophony standard H263, the present invention can also be implemented for other image compression standards. Further, the present invention is not limited to the processing of macroblocks of 16×16 pixels such as described as an example and applies, generally, whatever the type of operator used and whatever the parameter (here, distortion) considered for selecting a motion vector.

[0063] Such alterations, modifications, and improvements are intended to be part of this disclosure, and are intended to be within the spirit and the scope of the invention. Accordingly, the foregoing description is by way of example only and is not intended to be limiting. The invention is limited only as defined in the following claims and the equivalents thereto.