Abstract:
A device for addressing a cache memory of a motion picture compression circuit, executing series of comparisons to estimate the motion of a current window of pixels of a current picture with respect to a reference window of a preceding picture, includes a first cache memory partitioned into four physical segments of equal size. Each physical segment is adapted to contain one half-macroblock of the reference window, and a circuit for addressing the first cache memory, the addressing being different for a motion estimation related to a current window of even rank and for a motion estimation related to a current window of odd rank.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to circuits for compressing motion pictures, such as television pictures, and more particularly to the use of cache memories included in such circuits to form motion estimations of picture portions, a current picture portion being compared with its environment in a preceding picture. 
     2. Discussion of the Related Art 
     A motion picture compression circuit is used for encoding pictures so that they cab be transmitted in a TV transmission, by minimizing the amount of information to be transmitted. The compression achieved by this circuit includes, among other operations, carrying out a motion estimation between portions of two successive pictures. This motion estimation allows the encoding, and therefore the transmission, for current picture portions that are already existing in the preceding picture, of only motion vectors associated with these portions. Each motion vector characterizes the motion between a preceding picture portion and a corresponding portion of the current picture. 
     For this purpose, the pictures, for example provided by a video camera, are partitioned into picture portions, referred to as &#34;macroblocks&#34;. These macroblocks generally correspond to a partitioning of the picture into squares, each square having a 16×16-pixel size. In fact, a picture is sequentially stored line by line in a video memory. The pixels so stored are extracted from this video memory by pixel blocks corresponding to square portions of the picture. These pixel blocks, or macroblocks, are stored in a cache memory, to be used by a calculation processor designed, in particular, to determine the motion vector of the considered macroblock. Cache memories are needed because the calculation processor executes a series of comparisons on the same macroblock of a picture. Thus, the number of operations for accessing the video memory is decreased, which increases the processing speed of the pictures. 
     To perform motion estimation, the calculation processor uses the pixels of the considered macroblock of the current picture and the pixels surrounding the corresponding macroblock of the preceding picture. The calculation processor sequentially processes each macroblock of the current picture, constituting a current window, by using, at least partially, the pixels of the adjacent macroblocks of the preceding picture constituting a reference window in the preceding picture. A first cache memory contains a current window, and a second cache memory contains a larger reference window that includes, in addition to the pixels of the current window in the preceding picture, a portion of the macroblock pixels of the preceding picture which are sequentially adjacent thereto in all the directions. 
     Cache memories are conventionally addressed by loading a current window and a reference window in the cache memories before each series of comparisons used for the motion estimation of the considered macroblock. 
     In addition to the above-described application the present invention more generally relates to the use of a cache memory in a process involving several sets of values mutually having a sequential relationship. The invention more particularly applies to a process in which a series of operations has to be performed on two sets of values. The first set corresponds to a set of current values and the second set corresponds to a set of reference values, at least a portion of the reference set being used for the series of operations related to the next set of current values. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to minimize the loading times of the cache memory which stores the reference values, using a process such as the one described above. 
     To achieve this object, in one illustrative embodiment of the present invention, a device is provided for addressing a cache memory of a motion picture compression circuit, carrying out series of comparisons to estimate the motion of a current window of pixels of a current picture with respect to a reference window taken in the preceding picture. The addressing device includes a first cache memory partitioned into four physical segments of the same size, each physical segment being adapted to contain one half-macroblock of the reference window, and means for addressing the cache memory. The means for addressing operates differently for motion estimation related to a current window of even rank as compared to motion estimation related to a current window of odd rank. 
     According to an embodiment of the invention, the device additionally includes a second cache memory for containing a macroblock of pixels of the current picture constituting the current window, and means for loading the second cache memory, before each motion estimation, with pixels of a new current window. 
     According to a further embodiment of the invention, the device also includes means for loading, before each motion estimation, two of the four segments of the first cache memory, the last two half-macroblocks of a reference window being loaded in the last two segments for a motion estimation of even rank, and in the first two segments for a motion estimation of odd rank, respectively. 
     According to another embodiment of the invention, the device also includes means for reading the first cache memory, by assigning the content of the first two segments to the first two half-macroblocks of the reference window for a motion estimation of even rank, and to the last two half-macroblocks for a motion estimation of odd rank, respectively. The content of the last two segments is assigned to the last two half-macroblocks of the reference window for a motion estimation of even rank and to the first two half-macroblocks of the reference window for a motion estimation of odd rank, respectively. 
     In another illustrative embodiment of the invention, a method is provided for compressing motion pictures, executing a motion estimation of a macroblock of pixels of a current picture, and storing a reference window in a first cache memory by including, in addition to the current macroblock in the preceding picture, the two half-macroblocks sequentially surrounding the last one, in the preceding picture. The motion picture compression method further includes addressing the first cache memory, the addressing being different for a motion estimation of a current macroblock of even rank and for a motion estimation of a current macroblock of odd rank. 
     According to another embodiment of the invention, the method includes partitioning the first cache memory into four physical segments, and partitioning a reference window into four half-macroblocks, and addressing, for an even rank motion estimation, the first two physical segments as containing the first two half-macroblocks and the last two physical segments as containing the last two half-macroblocks of the reference window and, for an odd rank motion estimation, the last two physical segments as containing the first two half-macroblocks and the first two physical segments as containing the last two half-macroblocks of the reference window. 
     According to another embodiment of the invention, the method includes, between each motion estimation, loading in a second cache memory a macroblock of pixels of a current picture and, in the first cache memory, two half-macroblocks of the preceding picture, two other half-macroblocks of the reference window having been loaded for the motion estimation related to the macroblock of the current picture. 
     According to another embodiment of the invention, the method uses a state machine for controlling the calculation process of the addresses of the first cache memory. 
     In another illustrative embodiment of the invention, a method is provided for addressing a cache memory designed to be used in a process executing a series of operations on two sets of values, a first set corresponding to a set of current values and a second set corresponding to a set of reference values stored in the cache memory. At least a portion of the reference see is used for a series of operations related to a following set of current values. The method includes addressing the cache memory, differently for a series of operations of even rank and for a series of operations of odd rank. 
     According to one embodiment of the invention, the method includes partitioning the cache memory into four physical segments, and the set of reference values into four logic sub-sets having an identical size, and to address, for a series of operations of even rank, the first two physical segments as containing the first two logic sub-sets and the last two physical segments as containing the last two logic sub-sets and, for a series of operations of odd rank, the last two physical segments as containing the first two logic sub-sets and the first two physical segments as containing the last two logic subsets. 
     Addressing, according to the invention, the cache memory differently for the motion estimations, or series of comparisons, of even rank and for the motion estimations, or series of comparisons, of odd rank allows minimization of the loading times of the cache memory. In fact, one half of a reference window stored in the cache memory for a series of comparisons of rank &#34;i&#34; related to a current window can be used again for the following series of comparisons of rank i+1 related to the next current window. It is no longer necessary, as in the related art, to load the whole reference window before each series of comparisons. It is sufficient to load one half of this window between each motion estimation, the invention allowing each half of the reference window to be used during two successive series of comparisons. 
     Thus, the time required to load the first cache memory of the motion picture compression circuit, between two motion estimations is decreased by one half. The loading of a whole reference window, that is, two macroblocks, is only needed at the passage from a first row of macroblocks to a second row or at the beginning of a new picture. 
     The foregoing and other objects, features, aspects and advantages of the invention will become apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF DRAWINGS 
     In the drawings, FIG. 1 schematically represents an exemplary implementation of cache memories in a motion picture compression circuit according to the invention; 
     FIG. 2 schematically represents an exemplary loading mode of a cache memory, according to the invention, to perform a motion estimation of a row of macroblocks of a motion picture; and 
     FIG. 3 schematically represents two sequentially associated sets of values such as those to which the invention applies. 
    
    
     DETAILED DESCRIPTION 
     In the example represented in FIG. 1, a macroblock M(i,j), constituted by a matrix of mxn pixels of a current picture I(j), forms a current window C(i) to which a comparison process must be applied to estimate the motion of this macroblock with respect to a preceding picture I(j-1). Index i designates the sequential position, or rank, of the macroblock in the picture, and index j designates the picture rank. Macroblock M(i,j) is stored in a cache memory 2. The comparison is performed with respect to a reference window R(i), formed by a matrix of n lines and 2 m columns. This reference window R(i) corresponds to two macroblocks of the preceding picture I(j-1). Window R(i), in addition to macroblock M(i,j-1), includes the equivalent of two half-macroblocks of pixels sequentially surrounding the latter in the preceding picture I(j-1). These pixels correspond to a second half B(i-1,j-1)2 of macroblock M(i-1,j-1) and to a first half B(i+1,j-1)1 of macroblock M(i+1,j-1) of the preceding picture I(j-1). The reference window R(i) is partitioned into four half-macroblocks B(i-1,j-1)2, B(i,j-1)1, B(i,j-1)2, B(i+1,j-1)1, each containing a matrix of pixels of n lines and m/2 columns. Each half-macroblock is contained in a physical segment s1, s2, s3, s4 of a cache memory 1 which is partitioned for this purpose. The motion estimation includes performing a series of comparisons OP(i) on these two picture windows C(i) and R(i). An elementary comparison is performed on a pair of macroblocks M(i,j), {B(i-1,j-1)2, B(i,j-1)1}, then by shifting by one column at each elementary comparison, up to the macroblock pair M(i,j), {B(i,j-1)2, B(i+1,j-1)1}. 
     In practice, once the motion estimation is performed in all the directions of the picture, a current window is compared to a reference window corresponding to four macroblocks. Macroblock M(i,j) is effectively compared by taking into account the half-macroblocks surrounding its position in the preceding picture I(j-1) in all the directions. For the sake of simplification, only the sequential motions in the horizontal direction of the picture are shown. However, the motion estimation in the vertical direction is performed in the same manner, by repeating series of comparisons, shifting line by line pairs of macroblocks included in the reference window. 
     The present invention is based on the fact that two successive series of comparisons, or motion estimations, OP(i) and OP(i+1) use two successive macroblocks M(i,j) and M(i+1,j) of the current picture I(j) that are distinct but correspond to two adjacent reference windows R(i) and R(i+1). The two reference windows R(i) and R(i+1) are sequentially associated, i.e., they have two common half-macroblocks B(i,j-1)2 and B(i+1,j-1)1. In other words, the last two half-macroblocks of a reference window R(i) correspond to the first two half-macroblocks of the next reference window R(i+1). 
     FIG. 2 illustrates the loadings performed in the cache memory 1 for the motion estimation of a row of macroblocks of the current picture. 
     After a first series of comparisons OP(1) for which the four half-macroblocks B(0,j-1)2, B(1,j-1)1, B(1,j-1)2, and B(2,j-1)1 have been stored in the segments s3, s4, s1 and s2, respectively, only the last two half-macroblocks of the reference window R(2), for each series of comparisons, are loaded in the cache memory 1. 
     To perform the series of comparisons OP(2), the two half-macroblocks B(2,j-1)2 and B(3,j-1)1 are stored in segments s3 and s4, the two half-macroblocks B(1,j-1)2 and B(2,j-1)1 being already present in segments s1 and s2 since they have been used for the series of comparisons OP(1), as the last two half-macroblocks of the reference window R(1). Then, the first two segments s1 and s2 are addressed as including the first two half-macroblocks B(1,j-1)2 and B(2,j-1)1 of window R(2) respectively, and the last two segments s3 and s4 as including the last two half-macroblocks B(2,j-1)2 and B(3,j-1)1 of window R(2), respectively. 
     To perform a series of comparisons OP(i), i.e., even rank comparisons, the half-macroblocks B(i,j-1)2 and B(i+1,j-1)1 are stored in segments s3 and s4, the two half-macroblocks B(i-1,j-1)2 and B(i,j-1)1 being already present in segments s1 and s2 of the cache memory 1 since they were used for the preceding series of comparisons OP(i-1) as the last two half-macroblocks of the reference window R(i-1). The first two segments s1 and s2 are addressed as including the first two half-macroblocks B(i-1,j-1)2 and B(i,j-1)1 of window R(i) respectively, and the last two segments s3 and s4 as including the last two half-macroblocks B(i,j-1)2 and B(i+1,j-1)1 of window R(i), respectively. 
     To perform a series of comparisons OP(i+1), i.e., odd rank comparisons, the half-macroblocks B(i+1,j-1)2 and B(i+2,j-1)1 are stored in segments s1 and s2, the two half-macroblocks B(i,j-1)2 and B(i+1,j-1)1 being already present in segments s3 and s4 of the cache memory 1 since they were used for the preceding series of comparisons OP(i) as the last two half-macroblocks of the reference window R(i). Then, the first two segments s1 and s2 are addressed as including the first two half-macroblocks B(i+1,j-1)2 and B(i+2,j-1)1 of window R(i+1), respectively, and the last two segments s3 and s4 as including the first two half-macroblocks B(i,j-1)2 and B(i+1,j-1)1 of window R(i+1), respectively. 
     As the process includes p series of comparisons, corresponding to the number of macroblocks in a row of macroblocks in the picture, this loading mode is continued until the series of comparisons OP(p). In the example represented in FIG. 2, the process achieves an even number, p, of series of comparisons, or motion estimations, OP(i). The loading and addressing mode is identical in case of an odd number of series of comparisons OP(i). The first series of comparisons OP(1) was of odd rank, but the process optionally could be implemented with a first series of even rank. 
     The address calculations to be achieved for implementing the invention can, for example, be performed in a state machine controlling the process. 
     As can be seen, the invention allows, for the motion estimation of a row of p macroblocks of the current picture, the loading of only the equivalent of p+1 macroblocks of pixels, i.e., the equivalent of (p+1)/2 reference windows whereas it was previously needed to load p reference windows, i.e., the equivalent of 2p macroblocks. 
     In an implementation of the invention adapted to a videophone, a macroblock corresponds to a square matrix of 16×16 pixels, one half-macroblock corresponding to a 16×8-pixel matrix. 
     The above description, relative to a motion estimation process for motion pictures, can be extended to any process using two successive and discontinuous sets C(i) and C(i+1) of current values, and two continuous sets R(i) and R(i+1) of reference values. 
     FIG. 3 illustrates this general application by representing an example of two sets of sequentially associated values to which the present invention may apply. 
     In this example, a set of current values C(i), constituted by a matrix of n lines and m columns, constitutes one of the operands of a process OP(i) whose second operand is formed by a set of reference values R(i). Set R(i) is constituted by a matrix of n lines and 2 m columns partitioned into four logic sub-sets B(i)1, B(i)2, B(i)3, and B(i)4, each corresponding to a matrix of n lines and m/2 columns. The process includes performing a series of operations OP(i) on two sets of values C(i) and R(i). An elementary operation is performed on a pair of matrices having the same size, for example on the pair of matrices C(i), {B(i)2, B(i)3}. The series of operations is performed on the pair of matrices C(i), {B(i)1, B(i)2}, then by shifting by one column at each elementary operation, to the pair of matrices C(i), {B(i)3, B(i)4}. The two sets R(i) and R(i+1) are sequentially associated, the sub-sets B(i+1)1 and B(i+1)2 correspond to the sub-sets B(i)3 and B(i)4, respectively. 
     The sets of reference values R(i) and current values C(i) are stored in cache memories to be used by a calculation processor performing the series of operations. 
     To perform a series of operations OP(i), referred to as an even rank operation, the logic sub-sets B(i)3 and B(i)4 are stored in segments s3 and s4 of a cache memory, the sub-sets B(i)1 and B(i)2 being already present in segments s1 and s2 of the cache memory since they were used for the preceding series of operations OP(i-1) as being the sub-sets B(i-1)3 and B(i-1)4. The first two segments s1 and s2 are addressed as including the subsets B(i)1 and B(i)2, respectively, and the last two segments s3 and s4 as including the sub-sets B(i)3 and B(i)4, respectively. 
     To perform a series of operations OP(i+1), referred to as an odd rank operation, the logic sub-sets B(i+1)3 and B(i+1)4 are stored in segments s1 and s2 of the cache memory, the sub-sets B(i+1)1 and B(i+1)2 being already present in segments s3 and s4 of the cache memory since they were used for the preceding series of operations OP(i) as the sub-sets B(i)3 and B(i)4. Then, the first two segments s1 and s2 are addressed as including the sub-sets B(i+1)3 and B(i+1)4, respectively, and the last two segments s3 and s4 as including the sub-sets B(i+1)1 and B(i+1)2, respectively. 
     As is apparent to those skilled in the art, various modifications can be made to the above disclosed preferred embodiments. More particularly, the invention may apply to any type of process, using comparators, adders, subtracters, etc, or any combination of elementary operators. Similarly, the sets of values may correspond to matrices of arbitrary square or rectangular size. Furthermore, while the invention has been described considering that two sub-sets of reference values were common to two sequentially adjacent sets, alternatively an arbitrary number of sub-sets of a reference set could be common to a following reference set. 
     Having thus described at least one illustrative embodiment of the invention, various alterations, modifications, and improvements will readily occur to those skilled in the art. Such alterations, modifications, and improvements are intended to be within the spirit and 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.