Abstract:
An image processing method and a two-dimension discrete cosine transformation device using the same method are provided. The method includes steps of reading an image pixel data block, converting the data of the image pixel data block in the form of a frequency domain, limiting the converted data in the form of the frequency domain into a first predetermined number of bits, rearranging original DC values and original AC values, distributing the number of bits of the original DC values and the original AC values, quantifying the original DC values and the original AC values, and storing the quantified DC values and AC values into a memory. The device using the aforementioned method includes a first one-dimension cosine transformation unit connected to a transformation register further connected to a second one-dimension cosine transformation unit and a multiplier unit for receiving outputs from the second one-dimension cosine transformation unit.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to an image processing method, and more particularly, to an image processing method using the discrete cosine transformation and quantification procedure.  
         [0003]     2. Description of Prior Arts  
         [0004]     MPEG image compression method is directed at reducing the size of a segment of a clip consisted of a series of images. Because of the similarities between adjacent images (i.e. there are some correlations between these images), the first step of this specific compression method is to look for images with correlations (similarities). Once these images with correlations are found the method will delete correlation parts in terms of time between images or the correlation part in terms of space in any given image, in order to reduce the size of the data. Then the method would weed out part of images insensible to ordinary human eyes, thereby further reducing the size of the data. MPEG data compression method is carried out by discarding the data insensible to human eyes along with the playing of the clip, therefore the entire image quality would stay unaffected.  
         [0005]     MPEG compression integrates the motion compensation-based time-axis compression and the frequency coefficient, which is generated by discrete cosine transform (DCT), encoding and quantification-based spatial-axis compression. As for the time-axis compression, three pictures including intra-coded picture (I-Picture), predictive-coded picture (P-Picture), and bi-directionally predictive-coded picture (B-Picture) would be generated. I-Picture represents the primary part of the image and records the entire information of the image while P-Picture and B-Picture are for recording the difference of pictures only by having P-Picture compare with I-Picture and B-Picture compare with I-Picture and P-Picture.  
         [0006]     However, MPEG compression would delete duplicated image blocks in terms of time domain while corresponding motion vectors of P-Pictures or B-Pictures would bring image blocks from decompressed images back and add them up, meaning three or four frame buffers for the motion compensation purpose would be required in the chip.  
         [0007]     Unfortunately, with more frame buffers placed inside a chip the chip would take more space, which is not consistent with the current trend of chip size reduction. As the result, if we can have one image compression performed on the image data before they are written to frame buffers and one image decompression performed for these image data before having the motion compensation executed the entire size of the chip would be somewhat reduced while the total amount of inputted/outputted data of the memory would be reduced as well, therefore making the entire chip more power efficient.  
         [0008]     Adaptive Differential Pulse Code Modulation (ADPCM) tried to take advantage of the characteristic of continuity of images in any given clip. Any pixel and pixels around theoretically posses a certain degree of similarity, and therefore ADPCM subtracted pixels in the neighborhood, camp up with differences of these pixels, and then quantified these differences. Assume we have pixel A and pixel B in the neighborhood of pixel A, ADPCM subtracted A from B (or vice versa) to obtain the difference between pixels A and B, considered pixels A and B as one set of pixels and stored this set of pixels in terms of pixel A (if ADPCM subtracted pixel A from pixel B) or pixel B (if vice versa), a quantification index, and the quantified difference between pixels A and B, into the memory. When it comes to decoding, the quantification index and either pixel A or B (depend on which one is subtracted) would be retrieved first and the quantified difference would be added back to pixel A or B. ADPCM was relatively simple but tits efficiency of data compression was compromised and some high distortion would take place especially in the case of non-continuous images.  
         [0009]     One-dimension MHT was an alternative to MPEG compression. After having DC values and AC values, a built-in quantification table would be used to quantify these DC and AC values. However the efficiency of one-dimension MHT method was very similar to that of ADPCM, meaning high distortions would take place at non-continuous junctures of images.  
       SUMMARY OF INVENTION  
       [0010]     It is therefore a primary objective of the present invention to provide an image processing method for reducing the number of placement of frame buffers.  
         [0011]     In accordance with claimed invention, the present image processing method includes steps of reading an image pixel data block, converting the data of the image pixel data block in the form of a frequency domain, limiting the converted data in the form of the frequency domain into a predetermined number of bits, rearranging original DC values and original AC values, distributing the number of bits of the original DC values and the original AC values, quantifying the original DC values and the original AC values, and storing the quantified DC values and AC values into a memory.  
         [0012]     The present invention further provides a two-dimension discrete cosine transformation device using the above image compression method. The device includes a first one-dimension discrete cosine transformation operation unit, a transformation register connected to the first one-dimension discrete cosine transformation unit for storing outputs from the first one-dimension cosine transformation unit, a second one-dimension discrete cosine transformation unit connected to the transformation register for reading data from the transformation register, and a multiplier units having four multipliers for receiving four outputs respectively from the second one-dimension discrete cosine transformation unit.  
         [0013]     These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]      FIG. 1  is a schematic diagram showing a hardware structure of a one-dimension cosine transformation unit according to the present invention.  
         [0015]      FIG. 2  is a schematic diagram showing a hardware structure implementing the two-dimension discrete cosine transformation according to the present invention.  
         [0016]      FIG. 3  is a schematic diagram showing a preferred embodiment zigzag-scanning table according to the present invention.  
         [0017]      FIG. 4  is a flow chart showing an image compression process according to the present invention.  
         [0018]      FIG. 5  is a flow chart showing an image decompression process according to the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0019]     H. 264-defined 4×4 two-dimension discrete cosine transformation (DCT) has the result similar to that of float point discrete cosine transformation and significantly reduces the number of bits required in performing DCT image compression. As the result, hardware for implementing 4×4 two-dimension DCT could be reduced in size. With this characteristic, dividing every image going to be written into the frame buffer to several 4×4 pixel blocks and then performing discrete cosine transformation on these 4×4 pixel blocks would be a viable alternative to aforementioned prior art methods.  
         [0020]     H. 264-defined discrete cosine transformation formula is as formula (1):  
       Y   =         C   f     ⁢       XC   f   T     ⊗     E   f         =     (           [         1       1       1       1           2       1         -   1           -   2             1         -   1           -   1         1           1         -   2         2         -   1           ]     ⁡     [   X   ]       ⁡     [         1       2       1       1           1       1         -   1           -   2             1         -   1           -   1         2           1         -   2         1         -   1           ]       ⊗     [           a   2           ab   2           a   2           ab   2               ab   2             b   4     4           ab   2             b   4     4               a   2           ab   2           a   2           ab   2               ab   2             b   4     4           ab   2             b   4     4           ]       )           
 
 Matrix X is a timing signal of the image pixel data block, and matrix C f  is a parameter matrix. An inverse discrete cosine transformation formula defined in H. 264 is as formula (2):  
         Y   ′     =           C   i   T     ⁡     (     Y   ⊗     E   i       )       ⁢     C   i       =             [         1       1       1         1   2             1         1   2           -   1           -   1             1         -     1   2             -   1         1           1         -   1         -         -     1   2             ]     ⁢       (       [   X   ]     ⊗     [           a   2         ab         a   2         ab           ab         b   2         ab         b   2               a   2         ab         a   2         ab           ab         b   2         ab         b   2           ]       )     ⁡     [         1       1       -       1           1         1   2           -     1   2             -   1             1         -   1           -   1         -             1   2           -   1         1         -     1   2             ]                 
 
 wherein a=1/2, b=(2/5)  1/2 , E i  is a pure number matrix for insuring the absolute value of the inverse discrete cosine transformation is equal to 1. With the setting of the matrix E i  the number of multipliers would be reduced while Y′ is substantially equal to X. 
 
         [0021]     After having the discrete cosine transformation and before performing the inverse cosine discrete cosine transformation, inner products are necessary (from the standpoint of formulas (1) and (2)). Matrix E i  and E f  have all values therein less than 1 and after having inner products performed the outcome of inner products would become smaller which achieves the goal of minimizing values to be written into frame buffers. As the result, the compression rate would be more efficient. If combining E i  and E f  together into one single matrix E m  which could be defined as formula (3) as follows:  
         E   m     =     [           1   4             1   2     ⁢     b   2             1   4             1   2     ⁢     b   2                   1   2     ⁢     b   2             b   4             1   2     ⁢     b   2             b   4               1   4             1   2     ⁢     b   2             1   4             1   2     ⁢     b   2                   1   2     ⁢     b   2             b   4             1   2     ⁢     b   2             b   4           ]         
 
 Then the inverse cosine transformation could be rewritten as formula (4):  
               Y   4     =     ⁢                 ⁢     C   f     ⁢       XC   f   T     ⊗     E   m         =     (           [         1       1       1       1           2       1         -   1           -   2             1         -   1           -   1         1           1         -   2         2         -   1           ]     ⁡     [   X   ]       ⁡     [         1       2       1       1           1       1         -   1           -   2             1         -   1           -   1         2           1         -   2         1         -   1           ]       ⊗     [           1   4             1   2     ⁢     b     2   ⁢                       1   4             1   2     ⁢     b     2   ⁢                             1   2     ⁢     b     2   ⁢                       b   4             1   2     ⁢     b     2   ⁢                       b   4               1   4             1   2     ⁢     b     2   ⁢                       1   4             1   2     ⁢     b     2   ⁢                             1   2     ⁢     b     2   ⁢                       b   4             1   2     ⁢     b     2   ⁢                       b   4           ]       )         
 
 As the result, at the time of performing discrete cosine transformation the presence of E m  (for the purpose of inner products) would help minimize values and therefore they could be stored to frame buffers smaller in size. On the other hand, no E m  is required when the inverse discrete cosine transformation is performed. After having inner products performed with matrix E m  the present compression method restricts the outcome between −256 and 255 (i.e. 9 bits are sufficient to represent every value), leading to small differences between quantified and non-quantified values. 
 
         [0022]     Please refer to  FIG. 1  of a schematic diagram showing a hardware structure of the present invention one-dimension discrete cosine transformation unit for executing matrix operations with adders, subtractors, and displacement elements. On the basis of  FIG. 1 , ordinary skilled in the art would be able to come up with a schematic diagram (as shown in  FIG. 2 ) of implementing a two-dimension discrete cosine transformation. As having original image values enter into the first discrete cosine transformation unit  201 , the present invention method writes the outcome into the transformation register  203  in a horizontal manner and has the second discrete cosine transformation unit  205  read the outcome out of the transformation register  203  in a vertical manner. The transformation register  203  preferably is a 4×4 register. The second discrete cosine transformation unit  205  outputs  4  values at once to the respective multipliers of the multiplier unit  207 . The multiplier each leftward shifts outputs from the second discrete cosine transformation unit  205 , deletes the decimal fraction part after the shifting, and adds the remaining integer part in terms of binary form. For example, b 2  /2=0.2, in hardware implement, the value would be shift left to integer value. If we shift left 10 bit, the value is 204.8, truncate to integer value  205 . So the  205 =128+64+8+4+1. The multiply could be decrease to 5 adder. Outputs from the multipliers would be limited between −256 and 255 by the clamp unit  209 , meaning only 9 bits would be necessary to represent these outputs (in terms of binary form).  
         [0023]     4×4 two-dimension discrete cosine transformation converts the image data from the time domain to the frequency domain and then zigzag scanning will be used to rearrange the rank of all frequencies in order to distinguish AC values with higher or lower frequencies. A preferred embodiment of a zigzag-scanning table as shown in  FIG. 3  has a DC value placed the top left corner thereof and AC values arranged from ACI representing the AC value with lowest frequency to AC  15  representing the AC value with highest frequency so as to distribute certain number of bits to AC values. One zigzag-scanning table has 16 entries (128 bits in total) and if the frame buffer is going to have a 64-bit storage (with 50 percent compression rate) and the standing alone DC value is quantified directly in terms of a 7-digit value without any compression, plus one 3-digit quantification index, only 54 (64 minus 7 minus 3) would be left for AC values. AC values with lower frequencies are going to be distributed more digits, AC values with higher frequencies are going to be distributed less digits, and the AC value with highest frequency will be deleted.  
         [0024]     Preferably, there are six quantification tables for quantifying the converted AC values in order to have corresponding quantified AC values and the entire process starts with the first quantification table. If the first quantification table fails to quantify all AC values into the quantified form suitable to be stored into the memory, the present invention image compression method will turn to next quantification table and so on if failures continue to take place. The final quantification table is designed to place all quantified AC values into the memory. The original DC value is simply rightward shifted into a 7-digit form. Thereafter, quantified DC and AC values plus one quantification index serving as an index signal for assigning quantification tables are written into the memory to complete the entire compression process.  
         [0025]     The entire compression process is shown in  FIG. 4  illustrating an image compression flow chart according to the present invention. S 401  reads the original image pixel data block, S 403  converts the original image pixel data block from the time domain to the frequency domain by executing 4×4 two-dimension discrete cosine transformation and limits the converted image pixel data in the form of frequency domain into the first predetermined number of bits wherein the first predetermined number is nine (9); S 405  rearranges the rank of all frequencies of converted DC and AC values by zigzag scanning and distributing more digits to AC values with lower frequencies and fewer digits to AC values with higher frequencies; S 407  provides built-in quantification tables to quantify these converted AC values and starts with the first quantification table and if fails to advance the purpose of quantifying all AC values suitable to be stored into the memory the process turns to next quantification tables in the sequence in hope to place all quantified AC values into the memory while the last quantification table is designed to be able to place all quantified AC values into the memory; S 409  checks if all quantified AC values have been written into the memory and returns to S 407  if not all quantified AC values are placed into the memory; and S 411  writes quantified AC and DC values plus the quantification index into the memory to finish the whole compression process.  
         [0026]     The decompression process could be regarded as a mirror image of its compression counterpart. Please refer to  FIG. 5  of a flow chart showing a preferred embodiment of image decompression process according to the present invention. S 501  reads AC and DC values and the quantification index in the memory; S 503  decodes AC and DC values and the quantification index in order to bring original AC values back on the basis of decoded quantification index; S 505  leftward shifts the stored DC value in order to have its original counterpart; and S 507  executes a 4×4 two-dimension inverse discrete cosine transformation so as to convert the data from frequency domain to the time domain to complete the entire decompression process.  
         [0027]     Those skilled in the art will readily observe that numerous modifications and alterations of the device may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.