Abstract:
The present invention relates to a method for performing video motion estimation in video encoding, in which video signal consists of frames comprising blocks. In the method a combined comparison value is calculated between a current video block of a frame to be encoded and at least one other video block of another frame. Said current video block of the frame to be encoded comprises a set of first data values, and said at least one other video block of another frame comprises a set of second data values. Data value pairs are formed of data values from said set of first data values and equal number of corresponding data values from said set of second data values. Said combined comparison value is formed by defining comparison values, each of which is defined by using data values of one data value pair of said data value pairs. Further, at least one threshold value is defined, and it is determined whether the process for defining said combined comparison value can be terminated. The method comprises at least a calculation step for forming at least one sub-set of comparison values each consisting of at least one comparison value, an accumulation step for forming a signal indicative of the current cumulative comparison value, which is updated iteratively using said at least one sub-set of comparison values obtained at the calculation step, a decision step performing the determination whether the process can be terminated by comparing at least one signal with at least one threshold value, and termination and initialization of a new process according to the decision made at the decision step.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates to a method for performing video motion estimation in video encoding, in which video signal consists of frames comprising blocks, a combined comparison value is formed by using a current video block of a frame to be encoded and at least one other video block of another frame, said current video block of the frame to be encoded comprises a set of first data values, said at least one other video block of another frame comprises a set of second data values, data value pairs are formed of data values from said set of first data values and equal number of corresponding data values from said set of second data values, and said combined comparison value is formed by defining comparison values, each of which is defined by using data values of one data value pair of said data value pairs, at least one threshold value is defined, and it is determined whether the process for defining said combined comparison value can be terminated. The invention also relates to a video encoding system for performing video motion estimation in video encoding, which video signal consists of frames comprising blocks, the system comprising means for forming a combined comparison value by using a current video block of a frame to be encoded and at least one other video block of another frame, said current video block of the frame to be encoded comprises a set of first data values, said at least one other video block of another frame comprises a set of second data values, said means for forming a combined comparison value comprise input means for entering a series of at least two subsets each consisting of equal number of data value pairs of data values from said set of first data values and equal number of corresponding data values from said set of second data values, means for defining comparison values, each of which is defined by using data values of one data value pair of said data value pairs, means for defining at least one first threshold value, and means for determining whether the process for defining said combined comparison value can be terminated. The invention further relates to a video encoding device, which comprises means for encoding video signal consisting of frames comprising blocks, means for performing video motion estimation, means for calculating a combined comparison value between a current video block of a frame to be encoded and at least one other video block of another frame, said current video block of the frame to be encoded comprises a set of first data values, said at least one other video block of another frame comprises a set of second data values, and said combined comparison value is formed by defining comparison values between value pairs of said set of first data values and said set of second data values, means for defining at least one threshold value, and means for determining whether the process for defining said combined comparison value can be terminated.  
         BACKGROUND OF THE INVENTION  
         [0002]    Video encoding systems are known in which an image to be encoded comprises video blocks. These blocks are then encoded and transmitted to a decoding device or stored into a storage medium. For reducing the amount of information to be transmitted, different compression methods have been developed, such as MPEG-2 (Motion Picture Experts Group). In the transmission of video images, image compression can be performed either as interframe compression, intraframe compression, or a combination of these. In interframe compression, the aim is to eliminate redundant information in successive image frames. Typically, images contain a large amount of such non-varying information, for example a motionless background, or slowly changing information, for example when the object moves slowly. In interframe compression, it is also possible to utilise motion compensation, wherein the aim is to detect such larger elements in the image which are moving, wherein the motion vector and some kind of difference information of this entity is transmitted instead of transmitting the pixels representing the whole entity. Thus, the direction of the motion and the speed of the subject in question is defined, to establish this motion vector. For compression, the transmitting and the receiving video terminals are required to have such a high processing rate that it is possible to perform compression and decompression in real time.  
           [0003]    Typically, image blocks are grouped together to form blocks. The block usually contains 16 rows by 16 pixels of luminance samples, mode information, and possible motion vectors. The block is divided into four 8×8 luminance blocks and to two 8×8 chrominance blocks. Scanning (and encoding/decoding) proceeds block by block, conventionally from the top-left to the bottom-right corner of the frame. Inside one block the scanning (and encoding/decoding) order is from the top-left to the boftom-right corner of the block.  
           [0004]    In MPEG-2 compression, an image is Discrete Cosine Transform (DCT)-coded in blocks so that the block size is 8×8 pixels. The luminance level to be transformed is in full resolution. Both chrominance signals are subsampled, for example a field of 16×16 pixels is subsampled into a field of 8×8 pixels. The differences in the block sizes are primarily due to the fact that the eye does not discern changes in chrominance equally well as changes in luminance, wherein a field of 2×2 pixels is encoded with the same chrominance value.  
           [0005]    The MPEG-2 defines three frame types: an I-frame (Intra), a P-frame (Predicted), and a B-frame (Bi-directional). The I-frame is generated solely on the basis of information contained in the image itself, wherein at the receiving end, this I-frame can be used to form the entire image. The P-frame is formed on the basis of a preceding I-frame or P-frame, wherein at the receiving stage the preceding I-frame or P-frame is correspondingly used together with the received P-frame. In the composition of P-frames, for instance motion compensation is used to compress the quantity of information. B-frames are formed on the basis of the preceding I-frame and the following P- or I-frame. Correspondingly, at the receiving stage it is not possible to compose the B-frame until the corresponding I-frame and P- or I-frame have been received. Furthermore, at the transmission stage, the order of these P- and B-frames is usually changed, wherein the P-frame following the B-frame is received first, which accelerates the reconstruction of the image in the receiver.  
           [0006]    Of these three image types, the highest efficiency is achieved in the compression of B-frames. It should be mentioned that the number of I-frames, P-frames and B-frames can be varied in the application used at a given time. It must, however, be noticed here that at least one I-frame must be received at the receiving end, before it is possible to reconstruct a proper image in the display device of the receiver.  
           [0007]    The aim of the motion estimation is to find such a block (a reference block) within a search area of some reference frame in a video sequence that is most similar to a given block within the current frame (block under examination). Among the variety of motion estimation algorithms, the most popular are those based on block matching where a sum of absolute differences (SAD) is used as the similarity criterion between frame blocks. Given two ordered sets of data X={x 1 , . . . , x K } and Y={y 1 , . . . , y K }, the value of the SAD is defined as:  
                 S                 A                   D        (     X   ,   Y     )         =       ∑     i   =   1     K          |       x   i     -     y   i       |         ,           (   1   )                               
 
           [0008]    In some publications SAD is defined as the sum SAD(X,Y) divided by the number K of its addends. In that case it may also be called mean absolute error (MAE). Since in the most of the cases K is a power of two, these two definitions are substantially equivalent from the implementation point of view because the later one may simply be obtained by shifting the value of the former one by certain number of bits.  
           [0009]    In a video encoding context, the SAD is computed between every (16×16) block X (c)  of every current interframe (in practice almost every frame of a video sequence) and a plurality of (16×16) blocks Y (c,r) , Y (c,r′)  within a search area S (c)  of one or more reference frame(s) (see FIG. 5). The blocks Y (c,R)  that corresponds to the minimum SAD value among SADs between X (c)  and blocks Y (c,r) , Y (c,r′)  within the search area S (c)  is then used to form a motion information. Thus, SAD is applied many times and even a smallest improvement in the execution time of one SAD operation leads to significant savings in total video processing time. Naturally, on the other hand, the hardware utilized for computation of SAD should not be too large or power consuming especially in portable/wireless video processing applications.  
           [0010]    There are many different motion estimation algorithms utilizing different search strategies in order to reduce the number and/or the size of SAD operations with possibly less degradation in the quality of the encoded video. They can roughly be grouped into two categories: data independent search where the choice of the next pair of X and Y blocks does not depend on the SAD value obtained at the previous step, and data dependent search. Normally, the data dependent search strategies require less SAD operations to be implemented. However, most of hardware implementations are based on data independent motion estimation algorithms due to simplicity of organizing regular data movements typical to such algorithms. Common to data dependent strategies is that there are several options to choose the next pair of X and Y blocks and which pair will be chosen depends on the current SAD value.  
           [0011]    According to recent investigations different motion estimation algorithms consume approximately 40%-80% of the total video encoding time when implemented in a General-Purpose Processor (GPP). The basic operation in the block matching motion estimation algorithms is the SAD, which is applied many times during the video encoding process. In typical fast motion estimation algorithms, SAD computation is repeated approximately 30 times for almost every block (usually, of the size (16×16)) within the video sequence. Even for a 15 frames per second QCIF resolution (Quarter Common Intermediate Format) video sequences this would mean at least 44550 256-point (16×16) SAD computations per second. In a purely software implementation on, e.g., ARM9E microprocessor, which is a typical microprocessor in embedded systems, computing one 256-point SAD takes several thousands of clock cycles. This means that even hundreds of millions of cycles per second are spent only for motion estimation in a software implementation of video encoding.  
           [0012]    Due to the importance of the problem, many motion estimation devices have been reported in the literature recently. One class of the architectures for SAD computation involved in such devices are cascade-connected architectures. An example of such architecture is disclosed in the patent U.S. Pat. No. 6,154,492.  
           [0013]    Another type of architectures are those which may, in general, be described according to the FIG. 6 and may be referred to as “parallel/iterative accumulation SAD architectures”. Examples of such architectures are found in e.g. U.S. Pat. No. 5,864,372 and U.S. Pat. No. 5,652,625 and in the paper “The sum-absolute-difference motion estimation accelerator” by S Vassiliadis, E. A. Hakkennes, J. S. S. M. Wong. And G. G. Pechanek published in Proceedings of Euromicro Conference, vol. 2, in 1998 (pages 559-566). In these architectures, some comparison values which are representatives of the absolute difference between every pair of data values (one from a current block and another from a reference block) are calculated at every step within a block of computational unit(s). These values are then one-by-one or portion-by-portion (iteratively), or all at once (in parallel) accumulated within a summation block which may have an internal feedback. After accumulating comparison values of all the pairs for given two blocks the SAD between these two blocks are obtained. SADs obtained between a given block X (c)  and a plurality of blocks Y (c,r)  within a search area S (c)  are then analysed within the minimum evaluator block and the block producing the smallest SAD is selected to produce the motion estimation information.  
           [0014]    In the practical use for motion compensation in video encoding, if the SAD value is too large it is not in an interest. Thus accumulation means within SAD architectures may be implemented with a lower precision (bit-width) than that for the correct SAD value in the worst case. While larger SAD values would then incorrectly be computed, normally this does not affect to the motion estimation result.  
           [0015]    Some interrupt mechanisms have been introduced e.g. in U.S. Pat. No. 6,154,492 to be used in connection with SAD calculation means. The patent publication discloses a motion vector detection apparatus, which comprises cascade-connected processor elements. The processor elements calculate the absolute value of the difference between each of a plurality of pixels which compose a picture and a corresponding one of the same number of pixels included in a block, and also performs cumulative addition of the difference absolute values in the block. These operations are performed for each of the blocks within the predetermined search area. A comparative device repeatedly compares the cumulative addition values of two blocks obtained sequentially in the processor element at the final stage, and selects the smaller one of the cumulative addition values. A subtracter compares the smaller cumulative addition value with a setting value. When the smaller cumulative addition value is smaller than the setting value, a control circuit halts the supply of clock signals to the processor elements and the comparison device, so as to halt the entire operations of the apparatus. Since only smaller SAD values are important for determining the motion vectors, the larger SAD values may be incorrectly computed. This means that the precision of the functional units within the apparatus may have smaller precision than what is necessary for correct SAD computation in the worst case. This clearly leads to additional savings in silicon area and in power consumption. However, in this solution only a part of the architecture is halted thus partially saving the power but not the execution time. In fact, the architecture of U.S. Pat. No. 6,154,492 is constructed from K=256 processing elements each consisting of three adders. Such architecture does not appear feasible at the current state of technology or at least it appears to be too large for incorporating into mobile video encoding systems. In addition, this architecture supports only regular, data independent search strategies for motion estimation since it is heavily pipelined (256 pipeline stages) and the full interruption of the architecture would mean full pipeline reload.  
           [0016]    There are several situations in the SAD computation for motion estimation where the calculation of a SAD between two given blocks X (c)  and Y (c,r)  may be terminated before completing the calculations and a new calculation of the sum of absolute differences between X (c)  and another block Y (c,r′)  from the search area S (c)  may be started substantially immediately after the early termination. Examples of such situations are the cases where in the middle of calculations for the SAD between X (c)  and Y (c,r)  a temporary SAD value is obtained which already exceeds a predetermined threshold value or an earlier obtained value of the SAD between X (c)  and some block Y (c,r″)  within the search area S (c) . In some other situations the search for a reference block within a given search area S (c)  may be terminated and motion compensation information for X (c)  may be formed before completing the process in the normal way. An example of such situation is the case where an SAD value between two blocks X (c)  and Y (c,R)  (not shown) is smaller than another predetermined threshold value. Therefore integrating some interrupt mechanisms into devices for motion estimation allowing pre-termination of the SAD computation and/or the reference block search would be rather advantageous.  
         SUMMARY OF THE INVENTION  
         [0017]    It is an aim of the present invention to provide an improved method, system and apparatus for performing motion estimation in video encoding. The invention is based on the idea of incorporating interrupt mechanisms into iterative/parallel accumulation SAD architectures allowing to terminate the calculation of the sum of absolute differences and/or the search for a reference block in some circumstances where the further computations are useless or undesired. In some situations a new calculation of the sum of absolute differences between the given block X (c)  and a new block Y (c,r′)  from the search area S (c)  is started substantially immediately after the early termination. In some other situations the search for a reference block within the given search area S (c)  is terminated and motion compensation information for the given block X (c)  will be formed. This is achieved by examining the intermediate SAD values to determine if they already are too high to interrupt the SAD calculation between said current block X (c)  and said other block Y (c,r′)  as well as by examining the final SAD values to determine if they are already enough low to terminate the search for a given block X (c)  within the given search area S (c) . The method according to the present invention is primarily characterized in that the method comprises at least:  
           [0018]    a calculation step for forming at least one sub-set of comparison values each consisting of at least one comparison value  
           [0019]    an accumulation step for forming a signal indicative of the current cumulative comparison value, which is updated iteratively using said at least one sub-set of comparison values obtained at the calculation step,  
           [0020]    a decision step performing the determination whether the process can be terminated by comparing at least one signal with at least one threshold value, and  
           [0021]    termination and initialisation of a new process for defining said combined comparison value according to the decision made at the decision step.  
           [0022]    The video encoding system according to the invention is primarily characterized in that the system comprises at least:  
           [0023]    calculation means for forming at least one sub-set of comparison values each consisting of at least one comparison value,  
           [0024]    accumulation means for forming a signal indicative of the current cumulative comparison value, which is updated iteratively using said at least one sub-set of comparison values obtained at the calculation step,  
           [0025]    decision means for determining whether the calculation process can be terminated comprise means for comparing at least one signal with at least one threshold value, and  
           [0026]    means for terminating the current process and initialising of a new process for defining said combined comparison value according to the decision made at the decision step.  
           [0027]    The video encoding device according to the invention is primarily characterized in that the device comprises at least:  
           [0028]    calculation means for forming at least one sub-set of comparison values each consisting of at least one comparison value,  
           [0029]    accumulation means for forming a signal indicative of the current cumulative comparison value, which is updated iteratively using said at least one sub-set of comparison values obtained at the calculation step,  
           [0030]    decision means for determining whether the calculation process can be terminated comprise means for comparing at least one signal with at least one threshold value, and  
           [0031]    means for terminating the current process and initialising of a new process for defining said combined comparison value according to the decision made at the decision step.  
           [0032]    The present invention provides significant advantages as compared with those prior art hardware solutions which don&#39;t provide early termination mechanisms and/or don&#39;t use iterative accumulation means of a lower bit-width than is necessary for largest possible SAD value. The examination of the blocks within the search area can be performed faster because the calculation of SAD values between the current block and one reference block can be preterminated and the examination of the next block can be started almost immediately when it is noticed that the reference block is not suitable for the motion estimation. Furthermore, SAD value computations between a given current block, say X (c) , and a plurality of reference blocks, say Y (C,R) , can be preterminated, if the SAD value between the current block X (c)  and a given reference block Y (C,RO)  was tested to be reasonably small enough. Therefore useless computation process can be avoided. These modifications lead to major improvements in saving the execution time and power consumption since the cases where useless computation is determined occur quit often in the most of the motion estimation algorithms. Possibility of using low-precision accumulating means significantly reduces the size, execution time of the architectures proposed in this invention. Reduction of the accumulator&#39;s size also means that higher speed architectures having more parallel computational units are becoming practically feasible.  
           [0033]    Advantages of the proposed termination mechanism compared to those used in U.S. Pat. No. 6,154,492 to improve the SAD calculation means are e.g. as follows:  
           [0034]    In an advantageous embodiment of the present invention computing the SAD for the next pair of blocks is started when unnecessary computation is determined thus saving both the execution time and power consumption. The interrupt mechanism of U.S. Pat. No. 6,154,492 halts only a part of the architecture and after a time when computations for unnecessary SADs could have already been performed.  
           [0035]    The present invention may support as regular as well as irregular data dependent search strategies in motion estimation due to only a restricted pipelining employed. In a preferred embodiment, essentially, two (out of four) pipeline stages must be reloaded after the termination. The architecture of U.S. Pat. No. 6,154,492, is oriented only to regular, data independent motion estimation algorithms. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0036]    In the following the invention will be described in more detail with reference to the appended drawings, in which  
         [0037]    [0037]FIG. 1 shows, in a reduced block diagram, a motion estimation block according to an advantageous embodiment of the invention,  
         [0038]    [0038]FIG. 2 shows, in a reduced block diagram, a SAD calculation means of the motion estimation block according to an advantageous embodiment of the invention,  
         [0039]    [0039]FIG. 3 shows, in a reduced block diagram, a video transmission system according to an advantageous embodiment of the invention,  
         [0040]    [0040]FIG. 4 shows, in a reduced block diagram, a communication device according to an advantageous embodiment of the invention,  
         [0041]    [0041]FIG. 5 shows a method for performing video motion estimation in video encoding,  
         [0042]    [0042]FIG. 6 shows a general structure of prior-art iterative/parallel accumulation SAD architectures, and  
         [0043]    [0043]FIG. 7 shows the general structure of iterative/parallel accumulation SAD architectures with integrated interrupt mechanisms according to an advantageous embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0044]    In the following the invention will be described for a general case assuming K pairs of n-bit input data even though in the video encoding context, K=256, n=8 is the most common case. It should be noted that sum of absolute differences might be used not only in video encoding but also in other applications such as medical imaging, radar imaging, and other signal processing tasks where pattern recognition is performed in real time (Electrocardiogram (ECG) devices, implantable cardioverter-defibrillator (ICD) devices recording the function of the heart, sound processing, etc).  
         [0045]    [0045]FIG. 5 shows the principle of the method for performing video motion estimation in video encoding. In FIG. 5 only two frames FR 1 , FR 2  are shown for clarity. The frame FR 1  to be encoded comprises one or more blocks X (c)  which comprise pixel values X i,j  of which only a few are shown. In the reference frame FR 2  a search area S (c)  is defined. The search area S (c)  defines the area in which the comparison between the current block X (c)  of the frame FR 1  to be encoded and the reference block Y (c,r)  of the reference frame FR 2  is performed. However, it is obvious that in some embodiments it is possible to use the whole area of the reference frame FR 2  as the search area S (c) . In the method a reference block Y (c,r) , Y (c,r′)  is selected, one by one, for comparison with the current block X (c) . The search process will be continued until the whole search area S (c)  is examined or if another possibly defined condition for terminating the search is fulfilled. In the following the search will be described in more detail.  
         [0046]    [0046]FIG. 7 shows the general structure of iterative/parallel accumulation SAD architectures of FIG. 6 with integrated interrupt mechanisms according to an advantageous embodiment of the present invention. It comprises e.g. memory means  25  for storing image data, a SAD calculation means  1 , and control circuitry. The SAD calculation means  1  comprises means P 1  for forming comparison values, means P 2 , P 3  for forming cumulative and combined comparison values by using the comparison values, and means P 4  for evaluating the minimum SAD value and for forming motion estimation information MEI.  
         [0047]    For a detailed description, however, the invention will be described with the help of FIG. 1 which is a more detailed example of the general structure of the iterative/parallel accumulation SAD architecture of FIG. 7. This example illustrates the method of the present invention by incorporating early termination mechanisms into the architecture disclosed in the parallel application by the applicant. FIG. 1 shows, in a reduced block diagram, a motion estimation block  16  according to an advantageous embodiment of the invention and FIG. 2 shows in a reduced block diagram, an advantageous embodiment of a SAD calculation means  1  of the motion estimation block  16  of FIG. 1. The SAD calculation means  1  comprises four pipeline stages P 1 , P 2 , P 3 , P 4  and buffers  7  in the input of the first pipeline stage P 1  and buffers  8 ,  11 ,  15  between consecutive pipeline stages P 1 , P 2 ; P 2 , P 3  and P 3 , P 4 . In this advantageous embodiment of the present invention there are three different interrupt signals which can be generated for terminating the SAD calculation. The first interrupt signal  17  is generated by the second pipeline stage P 2  and it simply constitutes the carry output of the summation circuit of the second pipeline stage P 2 . The second interrupt signal  18  and the third interrupt signal  19  are generated by the fourth pipeline stage P 4 . The second interrupt signal  18  is the output of comparison means within minimum evaluator  13  which is set high when an intermediate SAD value exceeds the current minimum value. The third interrupt signal  19  is the output of another comparison means within minimum evaluator  13  which is set high when a complete intermediate SAD value is below a predetermined threshold value. It should be noted, however, that the invention is not only restricted to applications in which all the three interrupts are in use, but the invention can also be applied using only one or two of the interrupts. It is also possible that more than three different interrupts can be in use in devices in which the present invention is applied.  
         [0048]    The control circuitry comprises e.g. OR gates  20 ,  21 ,  22 , X data address generator  23 , Y data address generator  24  and clock circuitry to control the operations of the motion estimation block  16 . The first interrupt signal  17  is coupled via the first OR gate  20  to a first control input of the Y data address generator  24 . The first interrupt signal  17  is also coupled via the second  21  and the third OR gate  22  to generate a reset signal to the SAD calculation means  1 . The second interrupt signal  18  is coupled via the first OR gate  20  to a first control input of an Y data address generator  24 . The second interrupt signal  18  is also coupled via the second  21  and the third OR gate  22  to generate the reset signal to the SAD calculation means  1 . The third interrupt signal is coupled via the second OR gate  21  to a control input of an X data address generator  23  and to a second control input of an Y data address generator  24 .  
         [0049]    In the following the operation of the motion estimation block  16  of FIG. 1 will be described in more detail. First, block data sets x={x 1 , . . . , X K } and y={y 1 , . . . , Y K } are entered, portion by portion, into the first pipeline stage P 1  from e.g. the memory  25 . In this advantageous embodiment of the invention the first pipeline stage comprises four groups  3  of computational units  2  and each group comprises four computational units  2 . In a more general case the first pipeline stage P 1  comprises s groups  3  and each group comprises p computational units  2 . The parameters s and p are selected such that m=sp and both parameters s, p are positive integers, i.e. s, p≧1. Each computational unit  2  of a group  3  shares the same inputs X 1 , Y 1 ; X 2 , Y 2 ; X 3 , Y 3 ; X 4 , Y 4  but at different clock cycles. The pair of inputs (X i , Y i ), i=1, . . . , 4, of the SAD calculation means  1  is connected to the pair of inputs (X i,j , Y i,j ) of every computational unit DS i,j , j=1, . . . , 4, of the i th  group through the input registers  7 . Every of these input registers  7  of the first pipeline stage are open only during one out of every 4 operating cycles of the SAD calculation means  1 . This way, at every operating step, each input pair (X i , Y i ), i=1, . . . , 4, of the SAD calculation means  1  is actually connected to the pair of inputs (X i,j , Y i,j ) of only one computational unit while the other connections are inactive since the corresponding input registers  7  of the first pipeline stage are closed for writing. The input registers  7  of the first pipeline stage at the inputs of the first computational units DS i,1  of every group i=1, . . . , 4 are open during the first of every 4 operating steps, the input registers of the first pipeline stage at the inputs of the second computational units DS i,2  of every group are open during the second of every 4 operating steps, etc. The outputs of the computational units  2  of the groups  3  are connected to inputs of two multiplexers  4 ,  5  such that the n-bit output of the computational unit  2  is connected to one of the n-bit inputs of the first multiplexer  4  and the 1-bit output of the computational unit  2  is connected to one of the 1-bit inputs of the second multiplexer  5 . The first multiplexers  4  comprise p n-bit inputs and one n-bit output. Respectively, the second multiplexers  5  comprise p 1-bit inputs and one 1-bit output. The computational units  2  of one group  3  operate with a time offset of approximately one operating step having the duration T p  which now approximately equals to the delay of the compression array  6 . Respectively, sign and difference data are formed at the outputs of computational units  2  also with the time offset of approximately one operating step. Output pairs of all the computational units  2  of one group  3  are connected to a single pair of inputs of the compression array  6  through multiplexers  4 ,  5  so that at every operating step the computational unit  2  which have just computed the sign and difference data is connected to the compression array  6  through multiplexers  4 ,  5  and output buffers  8 . Thus the compression array  6  receives and accumulates new sign and difference data portion at every operating step alternating between different computational units  2  of every group  3 .  
         [0050]    The second pipeline stage P 2  is a compression array  6  having s inputs from the first pipeline stage P 1  and two feedbacks from its sum  9  and carry outputs  10 . The compression array  6  receives all the difference data and sign data, which are added together to produce two (sum and carry term) rows of compressed difference and sign data. The compression array  6  updates the values of its sum and carry terms at every operating step by accumulating the sign and difference data at the outputs of buffers  8 . After the accumulation of the sign and difference data for all value pairs is performed, the output of the compression array  6  comprises the final compressed difference and sign data which are accumulated by an adder  12  which constitutes the third pipeline stage P 3 .  
         [0051]    The compression array  6  of the second pipeline stage P 2  is advantageously a carry-save adder tree constructed either from full adders (FA) or 4/2-ratio compressors which are known as such. Different constructions of the tree are possible. In order to provide correct SAD computation in the worst case the bit-width (precision) of the tree must be (n+log 2 K−1)-bit, where n is the number of bits in input data, and K is the number of input data samples within a block. For example, if 8-bit input values are used and the size of the block is 256, the bit-width of the compression array  6  should be 15-bits in order to obtain the sum and carry terms of the largest possible SAD value correctly.  
         [0052]    The second pipeline stage P 2  has also output registers  11  which temporarily store the values of the sum and carry term calculated by the compression array  6 . This is necessary for proper control of the synchronized pipeline clock timing. The output registers  11  are also used to store the sum and carry term and to feed these terms back to input of the compression array  6  to be summed in the subsequent operation step.  
         [0053]    As mentioned above, the third pipeline stage P 3  comprises an adder  12  which adds the calculated sum and carry terms to produce the sum of absolute differences between the current block and the current reference block. It is also possible that the adder  12  calculates e.g. the mean absolute error (MAE) by dividing the sum of absolute errors SAD(X,Y) by the number K of its addends as was described earlier in this description.  
         [0054]    The fourth pipeline stage is a minimum evaluator  13  comprising a comparison means (not shown) and means  14  for storing minimum SAD value. In the beginning of the motion estimation for a given current block X (c)  the minimum SAD value is set to an initial value (normally, a large value, for example, the greatest possible value for the minimum SAD value). Then the comparison means of the minimum evaluator  13  compares the latest SAD value formed at the adder  12  of the third pipeline stage with the stored minimum SAD value and, if the latest SAD value is smaller, then the so far found minimum SAD value is replaced with that value. After performing all SAD computations for a given current block X (c) , the minimum SAD value is used to form the motion estimation information MEI for X (c) .  
         [0055]    A reference is made to the co-pending application in its entirety by the same applicant, in which the above described embodiment of the SAD calculation unit  1  is described in more detail.  
         [0056]    The following two embodiments of the invention are based on an observation that in motion estimation process only sufficiently small SAD values are important. In the practical use for motion compensation in video encoding, if the SAD value is too large it is not in an interest. Therefore, it is not necessary to calculate SAD values that are larger than a predetermined threshold correctly. This may be used twofold: to reduce the bit-width of the summation and comparison means as well as to terminate calculation of an SAD when it&#39;s going to be larger than the predetermined threshold value.  
         [0057]    In an advantageous embodiment of the present invention, the compression array  6  of the second pipeline stage P 2 , the adder  12  of the third pipeline stage P 3 , and the minimum evaluator of the fourth pipeline stage P 4  of the SAD calculation means  1  can be implemented with a lower precision than necessary to obtain the largest possible SAD value correctly. That is, the compression array  6  may be implemented with lower than (n+log 2 K−1)-bit precision, and the adder  12  and the comparison means of the minimum evaluator  13  may be implemented with lower than (n+log 2 K)-bit precision which are needed in order to provide correct SAD computation in the worst case. Here n is the number of bits in input data, and K is the number of input data samples within a block as before. For example, if 8-bit input values are used and the size of the block is 256, the bit-width of the compression array  6  may be lower than 15-bits, for example 7-bits, and the bit-width of the adder  12  and the comparison means within the minimum evaluator  13  may be lower than 16-bits, for example 8-bits. While larger SAD values would then be incorrectly computed, normally this does not affect to the motion estimation result. This embodiment may lead to significant reduction in the size and power consumption of the SAD computation means  1 . Reduction in the size may also mean that faster means involving more computational units in the first pipeline stage become practically feasible.  
         [0058]    In another advantageous embodiment of the present invention, the carry term of the temporary sum of differences of already processed data formed by the compression array  6  is examined to determine if it has exceeded a predetermined first threshold value. In this advantageous embodiment this can be performed by examining the status of the carry output  10  of the second pipeline stage P 2 . In fact, the most significant bit of the carry output  10  is coupled to the first OR gate  20  which then acts as the first interrupt signal  17 . Therefore, if the most significant bit of the carry output  10  is at logical one state, the first interrupt signal  17  is generated to inform the SAD calculation means  1  that the intermediate SAD value is over the predetermined first threshold value, wherein it is not necessary to continue the calculation of the SAD value between the current block and the reference block. The active state of the first interrupt signal (e.g. logical  1  state) sets the output of the first OR gate  20  to active state. This is coupled to the first control input of an Y data address generator  24  and to an input of the second OR gate  21 , as was mentioned previously in this description. Then, the Y data address generator  24  detects the change of the logical state of the first control input of the Y data address generator to active state and changes the Y data address to point to another, still unexamined, block of the reference frame. Also the pipeline stages P 1 , P 2 , P 3 , P 4  of the SAD calculation means  1  are reset to their initial states. The motion estimation block  16  will then begin to calculate the SAD value between the current block and the next reference block of the reference frame.  
         [0059]    In the above described embodiment the first threshold value is determined by the bit-width of the compression array (calculation accuracy). If the temporary sum of absolute differences value of the compression array  6  exceeds the value of the predetermined first threshold value at some accumulation step, the SAD computation process for the given pair of blocks X (c)  and Y (c,r)  will be terminated. For example, if 8-bit input values are used and the size of the block is 256, the bit-width of the compression array  6  should have to be 15-bits in order to obtain the largest possible SAD value correctly. However, in the preferred embodiment the width ┌log 2 TH 1 ┐ will be used where TH 1  is the first threshold value. This means that if the difference value is greater or equal than 2 |log     2     TH1| , the most significant bit of the carry output is set high. This embodiment has the advantage that no special comparison means are needed. In some other advantageous embodiments comparison means, for example a comparator (not shown), can be used to compare the temporary sum of absolute differences with the first threshold value and to produce the first interrupt signal  17 , if the absolute value of the difference data is greater than the first threshold value.  
         [0060]    It should be noted here that the memory  25  and the X and Y data address generators  23 ,  24  depicted on FIG. 1 may be as internal as well as external to the motion estimation block  16 . The interrupt mechanisms described in this description may be functional in both these cases.  
         [0061]    The SAD calculation means  1  which is described in FIG. 2 is one, non-restrictive, embodiment of the SAD calculation means, but also other kinds of SAD calculation means  1 , for example, those generally depicted on FIG. 6, can be used with the invention. Especially the structure of the first pipeline stage P 1  can vary in different embodiments.  
         [0062]    Yet another advantageous embodiment of the invention is based on the observation that if the temporal value of the current SAD value already exceeds the so far found minimum SAD value for the current X data there is no need to complete computation of the current SAD. A second interrupt signal  18  acting similarly to the first interrupt signal  17  will be used.  
         [0063]    To generate the second interrupt signal the third P 3  and fourth P 4  pipeline stages operate in parallel with the first P 1  and the second P 2  pipeline stages but, possibly, with different clock frequencies C 1 , C 2  since the last two pipeline stages P 3 , P 4  may be slower and need not operate at every operating step . . . With these modifications, partial SAD values will be formed at the output of the adder  12  at the third pipeline stage P 3  every T basic operating steps (corresponding to the clock frequency C 1 ) of the first two pipeline stages P 1 , P 2 , where T is the ratio between the clock frequency C 1  of the first two pipeline stages P 1 , P 2  and the clock frequency C 2  of the last two pipeline stages P 3 , P 4 . The minimum evaluator  13  compares the partial SAD values with the current minimum SAD value every T basic operating steps. At that basic operating step when it is known that the current partial SAD value is, in fact, a final SAD value the minimum SAD value is replaced if it is larger than the current SAD value. Before that clock cycle the minimum SAD value is not replaced even if the partial SAD value is smaller than the minimum value. However, if the partial SAD value is larger than the current minimum SAD value the second interrupt signal  18  is set to active. Similar to the first interrupt signal  17  the second interrupt signal  18  resets the SAD calculation means  1  and activates the Y data address generator  24  in order to start computation of the current X data with the next Y data.  
         [0064]    It should be noted here, that in addition to a clear improvement in execution time when using the above described embodiment, there is also an advantage of power/energy saving due to making the last two pipeline stages to operate with a slower clock frequency.  
         [0065]    In still another advantageous embodiment of the present invention the third interrupt signal  19  may be used to interrupt the SAD calculation process for the current search area. This embodiment is based on the observation that computations of the SAD values between the current X block and the rest of Y blocks are not needed if the SAD value between current X and Y blocks is sufficiently small (smaller than a predetermined second threshold value TH 2 ). To handle such a situation another interrupt signal (the third interrupt signal  19 ) is formed by the fourth pipeline stage P 4 . To generate the third interrupt signal  19  the fourth pipeline stage P 4  advantageously comprises a register (not shown) for the second threshold value TH 2  and a comparator (not shown) to compare the current (final) SAD value with the second threshold value. If the (final) SAD value is smaller than the second threshold value the third interrupt signal  19  will be activated. This third interrupt signal  19  is coupled with the first interrupt signal  17  in the second OR gate  21 , with the second interrupt signal  18  in the first OR gate  20  and with original reset signal  41  in the third OR gate  22  in order to form the new reset signal. The third interrupt signal  19  is also coupled to both X and Y data address generators  23 ,  24  in order to make them sending new data. The new data can comprise e.g. a new (unexamined) block X (ĉ)  of said frame FR 1  to be encoded, which is selected as the current video block comprising data values {{circumflex over (x)} 1 , . . . , {circumflex over (x)} K } (not shown), and a block Y (ĉ,{circumflex over (r)})  of another video frame comprising data values ({ŷ 1 , . . . , ŷ K }) (not shown). An example of these blocks X (ĉ) , Y (ĉ,{circumflex over (r)})  are also shown in FIG. 5.  
         [0066]    Claearly the present invention will lead to significant improvements in gate count, power consumption and execution time. However, quantitative estimation of the savings is difficult since they depend on the video sequence, on motion estimation algorithm, and on the realization of the invention.  
         [0067]    After the comparison, if no interrupt signals were generated, it is examined if all reference blocks have been used for calculating the SAD values for the current block X (c) . If there still exists at least one reference block Y (c,r) , Y (c,r′)  which is not yet used in the calculation of the SAD value for the current block, above described procedures are repeated. Otherwise, the found minimum SAD value will be used in later stages of the video encoding process to determine, if the current block will be encoded as such or motion compensated. The minimum evaluator  13  determines the coordinates of the block which produced the minimum SAD value for the current block and advantageously transfers the coordinate information together with the minimum SAD value to the decision means, e.g. the control unit  26 . In the decision means the minimum SAD value is examined to determine if the current block will be encoded as such or motion compensated. The decision means can, for example, evaluate the amount of information which is needed to transfer the block and the amount of information which is needed to transfer the motion compensated information. Then, the decision means advantageously select that alternative which needs less information transfer capacity.  
         [0068]    In a situation in which the motion compensated information is selected to be transmitted instead of the block itself, transmitted information comprise advantageously at least the coordinate information and motion error information. The coordinate information is used to inform the decoder which previously received and decoded reference block was used to form the motion vector. The motion error information is the difference between respective pixel values of the current block and the reference block. The decoder can then form the image information of the current block by using said reference block corrected by the motion error information.  
         [0069]    Next, a video transmission system according to an advantageous embodiment is described with reference to the block diagram of FIG. 3. The video signal to be transmitted is taken e.g. by the video camera  27  or it can be retrieved from video storing means (not shown) such as video recorder, digital versatile disk (DVD) etc. The video signal is transferred to the encoder  28 , which performs the coding of the video signal including the motion estimation according to the present invention. The encoded video signal is then channel coded in the channel coder  29 , if necessary. The purpose of the channel coding is to transform the coded video signal into a form suitable for transmission via the transmission channel  30 . The details of the channel coding can vary in different implementations of the video coding system and they are known by a skilled person.  
         [0070]    In the receiver the channel coded video signal is channel decoded in channel decoder  31  to retrieve the encoded video signal. After that, the decoder  32  decodes the video signal to produce a video signal which should substantially correspond with the original signal. However, in practice there are some potential error sources which can affect the transferred video signal wherein the decoded video signal may differ from the original video signal. Error correction mechanisms are developed to minimize effects of such transmission errors.  
         [0071]    The decoded video signal can then be displayed on the video monitor  33  and/or it can be stored into the storing means  34 .  
         [0072]    The FIG. 4 presents the video encoding device  35  according to an advantageous embodiment of the invention in a reduced manner. The terminal in question is suitable for both transmitting and receiving, but the invention can also be applied in connection with simplex terminals. In the video encoding devices  35  all the functional features presented in the block diagram of FIG. 4 are not necessarily required, but within the scope of the invention it is also possible to apply simpler video encoding devices  35 , for example without keyboard  36  and audio means  37 . In addition to said keyboard  36  and audio means  37 , the video terminal also comprises video means, such as a video monitor  33 , a video camera  27  or the like.  
         [0073]    To control the functions of the video encoding device  35 , it comprises a control unit  26 , which comprises, for example, a micro controlling unit (MCU), a micro processing unit (MPU), a digital signal processor and/or the like. In addition, the control unit  26  contains memory means  25  e.g. for storing application programs and data, and bus interface means I/O for transmitting signals between the control unit  26  and other functional blocks. The video encoding device  35  also comprises a video codec  38  which perform the encoding/decoding and compression/decompression of the video information. The compression is e.g. based on DCT transform and quantization, wherein in a decompression phase, the received information is dequantized and inverse DCT transformed, known as such. A channel codec  39  performs the channel coding for information to be transmitted and channel decoding of received information. The transmission of the channel coded video signal can be performed by e.g. the mobile communication means  40 .  
         [0074]    Each of the above described embodiments can be applied independently to the SAD calculation unit  1  to improve its performance, so that any of the embodiments can be combined to enhance the effect of the improvement. It should be clear to a skilled person that the presented methods for incorporating early termination mechanisms can also be applied to other iterative accumulation SAD architectures, for example those generally presented on FIG. 6.  
         [0075]    Is should also be noted that the threshold values which are used in comparisons to generate an interrupt signal need not be predetermined but they can also be dynamic, i.e. they can be changed during the operation of the SAD calculation device  1 . For example, the second interrupt signal is generated if the temporal value of the current SAD value already exceeds the so far found minimum SAD value for the current X data. Therefore, the so far found minimum SAD value which is used as a threshold value for the second interrupt may change during the operation of the device  1 .  
         [0076]    It is obvious that the present invention is not limited solely to the above-presented embodiments, but it can be modified within the scope of the appended claims.