Abstract:
A method for use in a real-time video encoder based on two processing means to optimise the use of computing power of the processing means. This is achieved by dynamically load-balancing between two processing means. The load pattern is determined with measures for the progress of motion estimation in one processing means and the idle time in the other. Adaptive adjustment of load balancing is fulfilled via making a decision on whether the DCT/IDCT/Quantization/Dequantization sub-process is skipped for a macroblock. The invention is not constrained to particular motion estimation techniques.

Description:
TECHNICAL FIELD 
     The present invention relates to real-time video compression and coding with multiple processors, and more specifically relates to a method for optimum use of the computing power available for the improvement of the performance of such systems. 
     BACKGROUND TO THE INVENTION 
     The most successful techniques for video compression and coding, including the international standards for moving images H.261/3 and MPEG-1/2/4, are based on motion estimation (ME), discrete cosine transform (DCT) and quantisation. FIG. 1 shows the basic procedure by which this is performed. The video input undergoes a series of processes including discrete cosine transform (DCT)  10 , quantization (Q)  11 , inverse quantization (Q −1 )  12 , inverse discrete cosine transform (IDCT)  13 , frame store (FS)  14 , interpolation  15 , motion estimation (ME)  16 , motion compensation (MC)  17 , source coding (SC)  18  and buffering  19 . The intensive computation involved in these techniques poses challenges to real-time implementation. 
     Performance with a single processor is limited by silicon technology. Parallel processing is the way to achieve the necessary speedup for video coding with existing algorithms and computing power. However, load balancing among processors is difficult because of the data dependent nature of video processing. Imbalance in load results in a waste of computing power. 
     The load-balancing problem has been tackled with block-, MB (macroblock)—or GOB (group of blocks)—based approaches due to the inherent data dependency in an image neighbourhood. This is described in, for example, T. Fujii and N. Ohata, “A load balancing technique for video signal processing on a multicomputer type DSP”, Proc. IEEE Int&#39;l Conf. Acoustics, Speech, Image Processing, USA, 1988, pp.1981-1984, and K.Asano et al, “An ASIC approach to a video coding processor”, Proc. Int&#39;l Conf. Image Processing and its Applications, London, 1992, pp.127-130. Such an approach has various disadvantages: (1) the computational complexity for adjoining MBs/GOBs may not be similar, especially when they are coded (inter- or intra- ) differently or lie on the border of motion; (2) extra computation and storage are required in GOB-based approaches because source coding (e.g., VLC, SAC) is sequential; (3) larger programs and working memory (very often on-chip memory space) are usually needed in real-time implementation because of the need of dedicated code for each processor; (4) some approaches require measurement of timing for every block&#39;s processing, and this is not feasible in real-time implementation; (5) there is no opportunity for dynamic load-balancing (the actual amount of computation depends on input pictures). 
     In the case of two processors, in order to avoid or at least alleviate the problems (1) to (3) listed above, the encoding process for an MB can be divided. This is described in, for example, W. Lin, K. H. Goh, B. J. Tye, G. A. Powell, T. Ohya and S. Adachi, “Real time H.263 video codec using parallel DSP”, Proc. IEEE Int&#39;l Conference Image Processing, USA, 1997, pp586-589, also in B. J. Tye, K. H. Goh, W. Lin, G. A. Powell, T. Ohya and S. Adachi, “DSP implementation of very low bit rate videoconferencing system”, Proc. Int&#39;l Conf. Information, Communications and Signal Processing, Singapore, 1997, pp1275-1278, and in K. H. Goh, W. Lin, B. J. Tye, G. A. Powell, T. Ohya and S. Adachi, “Real time full-duplex H.263 video codec system”, Proc. IEEE First Workshop on Multimedia Signal Processing, USA, 1997, pp445-450. The division of the encoding process is as follows: 
     Processor  1  (p 1 )—interpolation, ME, and all auxiliary processing before ME 
     referred to as ME sub-process hereafter for convenience; 
     Processor  2  (p 2 )—DCT, IDCT, Quant, Dequant, source coding (SC), and all auxiliary processing after SC 
     referred to as DCT-Q-SC sub-process hereafter for convenience. 
     The ME sub-process in p is carried out independently, regardless of the progress in p 2 , until the end of a frame. The DCT-Q-SC sub-process in P 2  is also carried out independently provided that there are ME-completed MBs waiting for DCT processing. FIG. 2 depicts a status table for a QCIF Frame with 99 macroblocks showing the progress of p 1  and P 2 . A frame  20  consists of a series of macroblocks (MBs)  21 . In this example, the first twelve MBs  22  have had DCT-Q-SC completed. ME but not DCT has been completed on a further seven MBs  23 , so the total number of MBs which have had ME completed is nineteen. The rest of the MBs  24  have not yet had ME completed. 
     In real-time applications, motion search can be performed in an efficient way, such as the 3-stage search or a pruning approach (described in Lin et al, Tye et al and Goh et al mentioned above) to meet the frame-rate requirement. The amount of computation for the DCT-Q-SC sub-process can be controlled in P 2  as shown in FIG.  3 . When the minimum SAD (sum of absolute difference) for an MB is less than T dct  (a threshold to be determined), the DCT-Q will be skipped. The reasoning for this is that when the sum of grey-level difference for an MB against its match in the previous frame is less than a certain value, it is acceptable to code just motion vectors and no DCT coefficients need be processed. 
     SUMMARY OF THE INVENTION 
     The object of the invention is to provide a simple and yet effective method to achieve load balance dynamically and adaptively while processing time is minimised, at the same time maintaining reasonable image quality and bit count, or image quality is optimised, at the same time maintaining processing time and bit count. 
     In general, more than one processor can be used to implement each of the sub-processes for an MB: Processing means  1  (P 1 )—ME sub-process; Processing means  2  (P 2 )—DCT-Q-SC sub-process. 
     In real-time applications, the processing time and coded bit length are major considerations if image quality is acceptable. The invention provides that when the strategy of ME in P 1  is set, the DCT-Q-SC subprocess can be adjusted for optimum use of P 2 &#39;S computing power. 
     According to the invention, the amount of computation in P 2  should be reduced when P 1  progresses faster than P 2 ; otherwise the amount of computation in P 2  should be increased. The amount of computation in P 1  is determined by the ME strategy adopted, and is therefore kept largely constant for similar images, except for some small variation due to the effect in DCT/IDCT/Quantisation/Dequantisation. 
     The amount of computation in P 2  may be controlled by T dct . T dct  is therefore decided adaptively for each MB in order to optimise the performance of the system, according to the dynamic load pattern between P 1  and P 2 . Determination of load pattern should not introduce significant additional computation to the video encoding process. Preferably, therefore, measures for the idle time in P 2  and the progress of ME in P 1  may be used. 
     The invented method balances the workload for video encoding with multi-processors according to dynamic load pattern, rather than dividing the task according to predetermined statistical information. The control is therefore more effective, aiming at optimum use of the computing resources for best performance. An additional advantage is that the additional computation brought to the video encoder by this load balancing method is negligible. 
    
    
     Other objects and advantages of the present invention will become apparent from the following description of preferred embodiments taken in conjunction with the accompanying drawings. 
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows a sequence for video compression and coding based on motion estimation (ME), discrete cosine transform (DCT) and quantization; 
     FIG. 2 illustrates a status table for the progress of ME/DCT for a QCIF Frame with 99 macroblocks in the sequence of FIG. 1; 
     FIG. 3 shows an algorithm to determine whether or not DCT, IDCT, quantization and dequantization are performed; 
     FIGS. 4A and 4B illustrate a first example of the processing time for frames with and without load balancing; 
     FIGS. 5A and 5B show the load pattern for a frame before balancing in the first example; 
     FIG. 6 shows the change in T dct  during a frame with balancing for the first example; 
     FIGS. 7A-7C show the load pattern and change in T dct  for a frame with balancing for the first example; 
     FIGS. 8A and 8B illustrate a second example of timing of frames with and without load balancing; 
     FIGS. 9A and 9B show the load pattern for a frame before balancing for the second example; 
     FIG. 10 shows the change in T dct  during a frame with balancing for the second example; 
     FIGS. 11A-11C show the load pattern and change T dct  in for a frame with balancing for the second example; and 
     FIGS. 12A-12C show a comparison of overall performance with and without load balancing. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     As shown in FIG. 2, each frame  20  of a video sequence is divided into macroblocks (MBs)  21 . The actions to be performed on each MB are shown in FIG.  1 . The processing is divided between two groups of processors, P 1  and P 2 , where P 1  performs the ME sub-process and P 2  performs the DCT-Q-SC sub-process as described above. 
     Before performing DCT in P 2  with the m th  MB in a frame/VOP (Video Object Plane), n me  is the number of MBs which have completed ME; n dct  is the number of MBs which have completed DCT-Q-SC, and n dct ≦n me ; p is the number of MBs which have completed ME but not yet completed DCT-Q-SC, i.e., p=n me −n dct  and p=0, 1, 2, . . . , N (N is the total number of MBs in a frame/VOP); t w  (&gt;0) is the idle time interval in P 2  while p=0, and is measured simply by counting the number of “no operations” while P 2  is waiting for the completion of ME in P 1 ; and T dct   min ≦T dct &lt;T dct   max . In FIG. 2, N=99, n me =19, n dct =12, and p=7. 
     MB-level control 
     When P 2  is idle (p=0 and t w &gt;0), T dct  (m)=T dct  (m−1)−t w /Q 1  where Q 1  is an integer to control the decrease rate of T dct . T dct  is clamped at T dct   min . Since T dct  is reduced, more MBs are likely to undertake DCT/IDCT/Quantisation/Dequantisation so that the IDCT-Q-SC sub-process is slowed down. 
     When the progress in P 1  is faster (p≧1 and t w =0), T dct  (m)= 
     T dct  (m−1)−p/Q 2  if 1≦p&lt;n 0    
     T dct  (m−1)+t w /Q 3  if n 0 ≦p≦n 1  and p(m)≧p(m−1) 
     T dct  (m−1)+t w /Q 4  if n 0 ≦p≦n 1  and p(m)&lt;p(m−1) 
     where n 1  (≧0) is a small positive integer (e.g. less than 4) to keep the progress in P 1  slightly faster than that in P 2 ; n 1  (≦N) is a positive integer close to N to avoid the adjustment of T dct  being applied to the last few MBs in each frame/VOP; Q 2 , Q 3  and Q 4  are three other integers to control the change rate of T dct  in different situations, and Q 4 &gt;Q 3 . T dct  cannot exceed T dct   max . As T dct  is increased, fewer MBs are likely to undertake DCT/IDCT/Quantisation/Dequantisation so that the DCT-Q-SC sub-process is speeded up. 
     At the start of the t th  frame/VOP, T dct   {t} (l)=Σ m=1,N T dct   {t−1} (m)/N, except for the first frame/VOP in which T dct   {i} (l) is the initial value set by the user. 
     Frame/VOP-level Control 
     A simpler scheme is to control T dct  at the frame/VOP level. At the t th  frame/VOP T dct   {t} =Σ m=1,N T dct   {t−1} (m)/N for all MBs. The value of T dct  is kept constant for the whole frame/VOP, and updated at the start of a frame/VOP. The control is not as effective and timely as that at MB-level. 
     Some examples of the use of load balancing will now be shown with reference to FIGS. 4A to  12 C. An H.263 video encoder, as described in Lin et al, Tye et al and Goh et al mentioned above, implemented on two parallel processors of Texas Instruments&#39; TMS320C80 is used to evaluate the invented method. It runs au about 7 QCIF frames per second. Tests show that the method balances the workload dynamically between two Processors in real-time applications. 
     FIG. 4A shows the processing time of each frame for the test sequence of “Susie” when T dct =1000 without load balancing. In this case, the ME sub-process is significantly faster than the DCT-Q-SC one, therefore the processing time for a whole frame is much longer than that for the ME sub-process. The case is further illustrated within a frame in FIGS. 5A and 5B, in which the progress of ME in P 1  (measured as p) is faster and the idle time in P 2  (measured as t w ) is zero, except for two MBs when no load balancing is applied. When the load balancing method is applied, T dct  increases from the initial value of 1000 to around 1600 by the end of the first frame, as shown in FIG. 6, and in consequence the DCT-Q-SC sub-process has been accelerated. T dct  is adjusted constantly in the following frames to keep load-imbalance between P 1  and P 2  minimum. The load balancing effect can be seen when FIGS. 5A and 5B are compared with FIGS. 7A and 7B, which show the load pattern for the same frame when load balancing has been applied. 
     FIG. 7C shows the change of T dct  for this frame. The timing improvement is obvious when comparing FIGS. 4A and 4B. Load balancing brings the processing time for the whole process close to that of ME. 
     FIG. 8A shows a case where the DCT-Q-SC sub-process is carried out faster (T dct =3500) before balancing. The total processing time is close to the ME time in P 1  for each frame although P 2  is idle most of the time, as shown in FIGS. 9A and 9B. When the load-balancing algorithm is applied, since the idle time in P 2  is significant, T dct  is adjusted from its initial value of 3500 to 3175 at the end of the 1st frame as shown in FIG.  10 . The adjustment continues in the following frames until approximate balance is reached as shown in FIGS. 11A-11C. The timing with and without load balancing is similar, as can be seen from FIGS. 8A and 8B, but the computing power in P 2 , lying idle when no load-balancing is applied, has been used for image quality improvement. 
     FIGS. 12A-12C show the comparison for the picture quality, mean bit count and average processing time, with and without load balancing, on different initial T dct  values. Without load balancing, both image quality as measured by SNR (FIG. 12A) and mean bit count (FIG. 12B) are reduced with the increase of T dct . This is reasonable because a larger T dct  means that fewer DCT coefficients are coded. Average processing time at the lower end of T dct  is much higher, since the DCT-Q-SC sub-process in P 2  takes significantly longer to be completed. With load balancing, SNR, mean bit count, and processing time per frame are all kept approximately constant for different initial T dct  values. At the lower end of the initial T dct  values, the invented method is capable of reducing the processing time and the bit count per frame (the speedup being 2.5 when initial T dct =500 in FIG.  6 ( c )) by raising T dct , without unduly compromising image quality. 
     At the higher end of the initial T dct  values, the algorithms maintain the same processing time but result in higher image quality by lowering T dct , with some small increase in bitstream length.