Abstract:
A method for determining quantization numbers for each macro block in one video segment having a prescribed capacity is disclosed. The quantization numbers determine how much data will be preserved for that macro block. The method begins by determining a level of complexity for each macro block. Next, initial quantization numbers are chosen for the macro blocks by choosing the largest values possible without exceeding the prescribed capacity of the video segment. Final quantization numbers are selected based on respective ones of the initial quantization numbers proportioned according to the level of complexity for that macro block. The final quantization numbers may be increased or decreased so that the capacity of the video segment is maximized but not exceeded.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention generally relates to compression techniques and more particularly to a method of determining an optimum quantization number for the compression of video data. 
     2. Description of the Related Art 
     There are many standards for the compression and decompression of video data. Some of the standards are the DV-IEC 61834 (“IEC-61834”), DVCPRO 25 and DVCPRO 50 standards. Each of these standards specifies a fixed amount of data for one video frame. Under these standards, as can be seen in  FIG. 1 , the video frame consists of five layers of structure: (1) micro blocks, (2) macro blocks, (3) DIF blocks, (4) video segments, and (5) DIF sequences. 
     For the DV-IEC 61834 and the DVCPRO 25 standards, there are a total of ten digital interface format (DIF) sequences for NTSC and 12 DIF sequences for PAL in one video frame. For the DVCPRO 50 standard, there are twice as many DIF sequences (e.g., 20 DIF sequences for NTSC and 24 DIF sequences for PAL). Referring to  FIG. 2 , there are at least 135 DIF blocks for video data in each DIF sequence. Each video segment of the DIF sequence contains five DIF blocks. Under the DV-IEC 61834, DVCPRO 25 and DVCPRO 50 standards, each DIF block in the video segment has 77 bytes allocated for one macro block. Referring to  FIG. 3B , for the DV-IEC 61834 and the DVCPRO 25 standard, each macro block contains six micro blocks—four blocks for Y data, one block for U data, and one block for V data. As can be seen in  FIG. 3A , for the DVCPRO 50 standard, each macro block contains four micro blocks—two blocks for Y data, one block for U data, and one block for V data. 
     Referring to  FIG. 4 , the structure of the video segment for all the standards is shown. Each of the standards specifies that a video segment has a fixed space of 77×5=385 bytes for compressed video data. An EOB coding is defined for a macro block that has less than 77 bytes in a DIF block. The remaining space can then be used by any of the other four macro blocks in the same video segment. 
     For each of the standards, every macro block in the video segment can be assigned an individual quantization step which is a factor regarding how much data will be preserved for that particular macro block. The quantization step is determined by three factors: (1) the class number; (2) the area number; and (3) the quantization number (QNO). The class number and the area number are defined in the DV-IEC 61834, DVCPRO 25, and the DVCPRO 50 specifications. However, the QNO can vary depending on the amount of compression that the user wishes. The QNO is chosen from 16 values for each of the five macro blocks. It is desired to choose a value of the QNO for each of the five macro blocks such that the maximum amount of information can be preserved without exceeding the 385 byte capacity limit of the video segment. By choosing the optimum value of the QNO, both the best video frame rate and image quality is achieved. The larger the value of the QNO, the finer the quantization step is and hence the more bits are needed for the encoding. 
     For the DVC-IEC 61834 and DVCPRO 25 standards, the video frame consists of 270 video segments for NTSC and 324 video segments for the PAL format. For the DVCPRO 50 standard, the video frame consists of 540 video segments for NTSC and 648 video segments for PAL. The video frame rate is 30 frames per second for NTSC and 25 frames per second for PAL. Accordingly, for the DV-IEC 61834 and DVCPRO 25 standards, the processing time for computing the DCT (Discrete Cosine Transform) and QNO searching for a video segment is approximately 123.4 μsec. For the DVCPRO 50 standard, parallel computation in two groups of 10 DIF sequences for NTSC and 12 DIF sequences for PAL is used to maintain the same 123.4 μsec processing time for a video block. The DCT computation is well known for compressing the video data and usually only takes about ten percent of the 123.4 μsec computing time (i.e. about 12.34 μsec). The remaining time (i.e., 101 μsec) can be allocated for searching the QNO. 
     One method of determining the optimum QNO for each of the five macro blocks in the video segment is to do a full search of all the combinations that are possible. Referring to  FIG. 5 , in step  501 , all of the combinations of the QNO are generated. It will be recognized that for five QNO&#39;s each having 16 values, the total possible number of combinations for the QNO&#39;s is 16 5 =1,048,576 combinations. In this regard, 1,048,576 combinations must be examined in order to preserve the maximum video data while the capacity (i.e., 385 bytes) is not exceeded. 
     In step  502 , each combination of QNO&#39;s is compared to the current best combination to determine if the length of the video segment is closer to the maximum value of 375 bytes. If the combination is better than the best combination, then in step  504 , the best combination is replaced with the newly discovered best combination. However, if the combination is not better than the best combination, then that combination is discarded in step  506 . 
     If all of the combinations have not been tried, then in step  508 , the process returns to step  501  where another of the generated combinations is compared to the best combination. However, if all of the combination have been tried, then the process is finished because the best combination for the QNO&#39;s has been found. 
     A drawback to the method shown in  FIG. 5  is that the time to search all 1,048,576 combinations is long. Only a supercomputer would be able to search all combinations in the 101 μsec allocated for QNO searching. It would not be possible for a desktop computer or other consumer product to search all of the QNO combinations in the allocated time. 
     Another method of determining the QNO&#39;s is to search only pre-selected combinations. Referring to  FIG. 6 , in step  601 , only five pre-selected QNO&#39;s out of sixteen are generated. Accordingly, only 5 5 =3125 combinations need to be examined. 
     In step  602 , the combination is compared to the current best combination to determine if the length of the video segment is closer to 375 bytes. If the combination is not better than the current best, then the combination is discarded in step  606 . However if the combination is better than the current best, the best combination is replaced with this combination in step  604 . If all the combinations have not been tried, then the process in step  608  repeats to step  601  whereby another combination will be compared. However, if all of the 3125 combinations have been tried, then the process is finished. The average search time per combination of QNO&#39;s is about 32 ns which is applicable to the processor inside a desktop computer. 
     The QNO search methods described above do not consider the complexity differences between each macro block of the video segment. The QNO&#39;s are determined to be the greatest length without exceeding the prescribed limit. As a result, it is possible that macro blocks with high AC coefficients from the DCT process get small spaces while most spaces are reserved for macro blocks with small AC coefficients. Accordingly, the compressed image quality is deteriorated. 
     The second problem is the generation of mosquito noise. When a frozen pattern of video for encoding is formatted using the DV-IEC61834, DVCPRO 25 or DVCPRO 50 standard, the digitized video data will have a small variation from frame to frame due to the noise and uncertainty introduced by the analog-to-digital (A/D) converter. Ideally, the same five QNO&#39;s should be chosen for every video segment between video frames. However, because the video data varies slightly from frame to frame, a different combination of the five QNO&#39;s will be assigned using the above-mentioned search techniques. Accordingly, the position of high and low compressed macro blocks, which are usually along sharp edges, will be altered between the video frames thereby causing noticeable distortion of the video image (i.e., mosquito noise). 
     In addition to the foregoing, the method using 5 pre-selected QNO&#39;s shown in  FIG. 6  also has another additional drawback. Specifically, because the pre-selected 5 QNO&#39;s are a subset of sixteen QNO&#39;s, the flexibility in choosing the best combination is limited. As such, the video encoded by this method will have inferior image quality than the video encoded by the full search method. 
     The present invention addresses the above-mentioned deficiencies in the prior art methods of determining the quantization of compression by providing a method whereby the optimum quantization number is chosen. In this regard, the present invention provides an adaptive bit rate allocation that only needs to search a limited number of combinations, but can allocate space according to the complexity of each macro block. Accordingly, this method utilizes all 16 QNO&#39;s without compromise to deliver the best quality available. 
     BRIEF SUMMARY OF THE INVENTION 
     In accordance with the present invention there is provided a method of determining quantization numbers for each macro block in one video segment which has fixed space for compressed video data. The method starts by determining a level of complexity of each individual macro block. Next, an initial quantization number is chosen. A final quantization number is selected based on the initial quantization number that is proportional to the level of complexity of the macro block. 
     In the preferred embodiment of the present invention, the level of complexity of the macro block is indicated by a complex index that is proportional to the summation of all the complex indexes of discrete cosine transform (DCT) blocks. The complex index of each DCT block is calculated by the summation of weight factors of AC components of a DCT block multiplied by the coefficients of the DCT block. The initial quantization numbers are determined by selecting the greatest initial quantization numbers that do not exceed a prescribed capacity of the video segment. The final quantization numbers can be adjusted in order to maximize the allocation space for macro blocks with high complex indexes in the video segment. In the preferred embodiment of the present invention, the final quantization numbers can be incremented or decremented by one individually until the quantization numbers are just less than the maximum capacity of the video segment. 
     In accordance with the present invention, there is provided a compressed data stream having at least one macro block and containing at least one quantization number. The quantization number is calculated by first determining a complex index for the macro block wherein the complex index is based on a weight factor of the compressed data stream. Next, an initial quantization number that does not exceed the maximum capacity of the macro block is determined. The initial quantization number is weighted by the complex index in order to generate a weighted quantization number. Finally, the weighted quantization number is adjusted in order to generate the quantization number for the macro block. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       These as well as other features of the present invention will become more apparent upon reference to the drawings wherein: 
         FIG. 1   a  is a data structure for one video frame for the DVCPRO 50 standard; 
         FIG. 1   b  is a data structure for one video frame for the IEC-61834 standard or the DVCPRO 25 standard; 
         FIG. 2  is a data structure for a DIF sequence; 
         FIG. 3   a  is a macro block structure for the DVCPRO 50 standard; 
         FIG. 3   b  is a macro block structure for the IEC-61834 standard or the DVCPRO 25 standard; 
         FIG. 4  is the structure of a video segment; 
         FIG. 5  is a flowchart showing a first prior art method of searching for the quantization numbers; 
         FIG. 6  is a flowchart showing a second prior art method of searching for the quantization numbers; 
         FIG. 7  is a flowchart showing the adaptive bit rate allocation method of the present invention; 
         FIG. 8  is an 8×8 DCT weight table; 
         FIG. 9  is a 2×4×8 DCT weight table; and 
         FIG. 10  is an IQNO/Qi lookup table. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring to the drawings wherein the showings are for purpose of illustrating a preferred embodiment of the present invention only, and not for purposes of limiting the same,  FIG. 7  is a flowchart showing the adaptive bit rate allocation method of the present invention. Generally, an initial QNO is selected to reach maximum capacity usage. Based on the initial QNO, the QNO of each compressed macro block (CM) is selected in proportion to a complex index (CI). A final adjustment is performed to ensure that an optimized result is reached. 
     Referring to step  1002  of  FIG. 7 , the process begins by calculating the complex index (CI) for each CM. The CI indicates the level of complexity of each CM. The CI for each CM is calculated as follows: 
               CI   i     =       1   16     ·       ∑     k   =   0     KMAX     ⁢     ci   k                 (   1   )             
 
     where Ci k  is the complex index of each DCT block of the CM. For the IEC-61834 and DVCPRO 25 standards, KMAX is 5 (e.g., 6 blocks in total, 4Y blocks, one Cr block and one Cb block). For the DVCPRO 50 standard, KMAX is 3 (4 blocks in total, 2 Y blocks, one Cr block and one Cb block). 
     The complex index of each DCT block ci in equation (1) is calculated as follows: 
             ci   =       ∑     j   =   0     63     ⁢            coef   j          ·     w   j                 (   2   )             
 
     where coef j  is the DCT coefficient with respect to a certain AC component and w j  is the weight factor for the AC component. The weight factor is obtained through table lookup of AC component weights, as is commonly known. For an 8×8 DCT mode, the table of  FIG. 8  is used, but for a 2×4×8 DCT mode the table shown in  FIG. 9  is used. From the tables, it can be seen that for larger AC components, the weight factors are also larger. This ensures that the DCT blocks with more AC components have larger CI&#39;s. 
     According to the DV standards (i.e., IEC-61834, DVCPRO 25, DVCPRO 50), the DCT coefficients are 10-bit signed integers (9-bits for the DC coefficient). Because, only the absolute value of the DCT coefficient is used, it can be considered as a 9-bit unsigned integer. The sum of the 8×8 DCT weights from  FIG. 8  is 176 and the sum of the 2×4×8 DCT weights from  FIG. 9  is 162. Therefore, ci only needs 17 bits (i.e., 9 bits*176). For KMAX=5, the summation of ci needs 20 bits and CI needs 16 bits. For KMAX=3, the summation of ci needs 19 bits and CI needs 15 bits. 
     Referring to  FIG. 7 , as the complex index calculation is being processed, the length of the code is being calculated in step  1004  and the initial QNO is being selected in step  1006 . The initial QNO is selected as the base of the adjustment and is selected in a manner that by applying to all CM&#39;s, the overall length is the longest but does not exceed the capacity. The following subroutine selects the initial QNO: 
     
       
         
               
             
               
               
             
               
             
               
               
             
               
             
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
             
           
               
                   
               
             
             
               
                 select_init_qno ( ) { 
               
               
                 init_qno = 7; 
               
               
                 total_length = CM0[init_qno] + CM1[init_qno] + CM2[init_qno] + 
               
             
          
           
               
                   
                 CM3[init_qno] + CM4[init_qno]; 
               
             
          
           
               
                 If (total_length &lt; Capacity) 
               
             
          
           
               
                   
                 Previous_state = STATE_SMALLER; 
               
             
          
           
               
                 Else 
               
             
          
           
               
                   
                 Previous_state = STATE_LARGER; 
               
             
          
           
               
                 Done = FALSE; 
               
               
                 while (!done) { 
               
             
          
           
               
                   
                 total_length = CM0[init_qno] + CM1[init_qno] + 
               
             
          
           
               
                   
                 CM2[init_qno] + CM3[init_qno] + CM4[init_qno]; 
               
             
          
           
               
                   
                 if(total_length &lt; Capacity) { /* Smaller. Increase init_qno */ 
               
             
          
           
               
                   
                 if(init_qno == MAX_QNO) break; 
               
               
                   
                 if(previous_state == STATE_SMALLER) { 
               
             
          
           
               
                   
                 init_qno++; 
               
               
                   
                 previous_state = STATE_SMALLER; 
               
               
                   
                 } 
               
               
                   
                 else /*Increase init_qno will cause total length to exceed 
               
               
                   
                 capacity. We&#39;re done.*/ 
               
             
          
           
               
                   
                 done = TRUE; 
               
             
          
           
               
                   
                 } 
               
               
                   
                 else if(total_length &gt; num_bits_per_vs) 
               
               
                   
                 { /* Larger. Decrease init_qno */ 
               
             
          
           
               
                   
                 if(init_qno == MIN_QNO) break; 
               
               
                   
                 if(previous_state == STATE_LARGER) { 
               
             
          
           
               
                   
                 init_qno--; 
               
               
                   
                 previous_state = STATE_LARGER; 
               
             
          
           
               
                   
                 } 
               
               
                   
                 else { /*The next smaller init_qno can satisfy the 
               
               
                   
                 capacity limitation*/ 
               
             
          
           
               
                   
                 init_qno--; 
               
               
                   
                 done = TRUE; 
               
             
          
           
               
                   
                 } 
               
             
          
           
               
                   
                 } 
               
               
                   
                 else { /* The size is just the same as the capacity */ 
               
             
          
           
               
                   
                 done = TRUE; 
               
             
          
           
               
                   
                 } 
               
             
          
           
               
                   
                 } 
               
             
          
           
               
                 } 
               
               
                   
               
             
          
         
       
     
     If MAX_QNO (15) or MIN_QNO (0) is used by initial QNO, then the best value has been found and the process stops. However, if MAX_QNO (15) or MIN_QNO (0) is not used as the initial QNO, then the best value has not been found and the process continues to step  1008  in  FIG. 7 . 
     Based on the initial QNO and the CI of each CM, a weighted QNO is used by each CM. The weighted QNO (Q i ) is calculated as follows: 
               Q   i     =     IQNO   ·       5   ⁢     CI   i         ∑   CI                 (   3   )             
 
     where Qi is the weighted QNO of macroblock (i=0 to 4), IQNO is the initial QNO determined from the subroutine, CI i  is the complex index of macroblock i from equation (1) and ΣCI is the sum of all 5 CI&#39;s. As previously explained above, both 5CI i  and ΣCI are stored using 19 bits (i.e., 20 bits−4+3). 
     A design limit exists on the QNO selection so that it is not less than 0.5*IQNO and does not exceed 2*IQNO. If QNO is larger than 2*IQNO, then 2*IQNO is used. If QNO is smaller than 0.5*IQNO, then 0.5*IQNO is used. There are two reasons for the limit. First of all, if the five QNOs in a video segment differ too much, it impairs the resulting image quality by empirical observation. Secondly, by limiting the selection of the QNO to the above-mentioned values, a very good set of QNO values will be chosen in a reasonable amount of time. 
     The arithmetic division in equation (3) is costly to implement in hardware. However, it can be replaced with a series of shift-and-add operations. For example, because QNO cannot exceed 2*IQNO and if 5CI i  is greater than or equal to twice ΣCI, then Q i  is 2*IQNO. To determine if 5CI i &gt;=2*ΣCI, an easy shift-and-compare operation can be performed. Similarly, if 5CI i &lt;=0.5*ΣCI, then Q i  is assigned 0.5*IQNO. 
     For the cases where 5CI i  is between 0.5*ΣCI and 2*ΣCI, then the table of  FIG. 10  can be used. The table of  FIG. 10  is an IQNO/Q i  lookup table and lists all the possible relationships between Q i , IQNO, and 5CI i /ΣCI. For example, if IQNO is 3 and 5CI i /ΣCI is smaller than 1.33 but greater than 1, then Q i  is 4. The locations in the table with an “x” indicate impossible cases wherein Q i  is greater then 2*IQNO or smaller than 0.5*IQNO. The values in the table fall in 24 spaces with the step size being 1/16. Therefore, once you know IQNO, it takes up to 24 steps to find the correct value of Q i . In this case, searching was started from the middle of the searching range and continues to the left or right direction depending if the initial value was larger or smaller. This reduces the maximum search steps to 12. 
     The result of the weighted adjustment allocates each CM according to its complexity, but does not guarantee that that the overall size is the maximum and within the capacity. As such some further adjustment is needed. Referring to  FIG. 7 , in step  1010 , the weighted QNO is adjusted to fulfill size requirements. Specifically, when the overall size of the QNO&#39;s is smaller than capacity, then the smallest QNO is increased by 1. If the size is still smaller, then the second smallest QNO is increased by one. If after increasing all five QNO&#39;s by one, the size is still not at capacity, then the smallest QNO is again increased by one. This procedure is performed until no further increase is possible (i.e., one more increase will make the overall size exceed capacity). If after computing the QNO&#39;s, the overall size is above capacity, then the opposite procedure is performed. Namely, the largest QNO is decreased by 1, then the second largest QNO is decreased by 1, etc. . . . The QNO&#39;s are decreased by 1 until the overall size is within capacity. 
     As will be recognized, the maximum number of iterations for the initial QNO (i.e., IQNO) is 7 (when the initial QNO is 0 or 15). The weighted adjustment needs 12 steps in a worst case scenario for each of the 5 CM&#39;s to perform in parallel. There is also a natural limit for the final adjustment. For instance, it is not possible for all of the QNO&#39;s to be larger or smaller than the initial QNO and that there is a hard limit for the QNO (i.e., the QNO is between 0.5*IQNO and 2*IQNO). For the following worst case example, the weighted adjustment shows: 
     IQNO=14 
     QNO={7, 7, 7, 7, 15} (QNO cannot be less than 7, and not all QNO&#39;s can be smaller than IQNO). 
     The maximum possible result will be QNO={14, 15, 15, 15, 15}. If all QNO&#39;s where to be 15, then IQNO would have been 15. To reach the final result for QNO, thirty-one iterations are needed for the final adjustment process. As stated before, it took 7 iterations for the initial QNO selection and 12 steps for the weighted adjustment. Accordingly, it took 50 steps (7+12+31=50) to determine the final result for the QNO&#39;s in the worst case. As will be recognized, this is greatly reduced from the number of iterations using the prior art methods and achieves a superior result. 
     Additional modifications and improvements of the present invention may also be apparent to those of ordinary skill in the art. Thus, the particular combination of parts describes and illustrated herein is intended to represent only a certain embodiment of the present invention, and is not intended to serve as a limitation of alternative devices within the spirit and scope of the invention.