Fourier Domain Quantization:

As described in the specifications, we divide the image into 8x8 pixel segments and work on these pixels. When we examine the characteristic of the Fourier Transformed form of the image, we find out the following properties:
For the real part;
             ·        There exists a unique value, which is quite large, at the top first position of every 8-by-8 block of the entire image
             ·        Every top left 3 values have their corresponding symmetries on the right hand side of the same row according to the 5th element of the row
             ·        Above situation also holds for the first column.
             ·        Every element of the remaining 7x7 part of the block is symmetric with respect to the mid-element of the 8-by-8 block.
      For the imaginary part the similar symmetry conditions are present except the sign difference coming from the conjugate symmetry of the complex numbers.
      Details of the symmetry properties are shown in the appendix.

      Encoding: Due to this results and having the knowledge that the information of an image after Fourier Transformation is mostly focused on the four corners, we rather keep just the values mentioned above, which correspond to the positions of the entire image.
 
0,0 0,1 0,2 0,3        
1,0 1,1 1,2          
2,0 1,2 2,2          
3,0              
               
               
  6,1 6,2          
  7,1 7,2          

In order to be able to store the floating-point values of the transform table, we have to map each value into the range [0,255] of unsigned char using a normalization process by finding the maximum and minimum of these elements. Normalizing process is this:


This operation leads to some loss of data but we try to minimize this effect that mainly depends on the value of coefficient by keeping the coefficient small.
      Again when we examine the transform table, [0][0] entry is a very large positive number (of the order of 10.000) but the remaining elements are respectively small
      ( [ -1000,1000] ) . If we consider [0][0] element in normalization, the coefficient will be a number like 40 and this will cause a very large error during normalization. We overcome this problem by storing the [0][0] element apart from the remaining elements. This optimization decreased the error in the normalization in a perceivable amount.
      We find the minimum and maximum of the selected elements (except [0][0] of real part) of both real and imaginary parts and calculate a common coefficient for all the numbers to be normalized.
      Normalized values and other necessary data are stored in the resulting 8x16 bytes segment is:
 
0,1-re 0,2-re 0,3-re
 (COEFFICIENT)
      
1,0-re 1,1-re 1,2-re 6,1-re 6,2-re      
2,0-re 2,1-re 2,2-re 7,1-re 7,2-re      
3,0-re
(MIN)
(0,0)-RE
      
1,0-im 0,1-im 0,2-im 0,3-im (MARK)      
2,0-im 1,1-im 1,2-im 6,1-im 6,2-im      
3,0-im 2,1-im 2,2-im 7,1-im 7,2-im      
               

      We write only five columns and seven rows of these 8x16 segments to the output image because gathering the empty spaces together results more compression during png conversion.
      To eliminate the similar segments to be stored repeatedly, we calculate the rms values for every consecutive segment pairs while tracing through the image, and compare the results with a specified rms value. If the result is less than the acceptable error amount we only take the information on one of the segments and put a mark on the other segment to indicate that the corresponding values are stored on another segment, which is directed by the two pointers of x and y dimensions. These pointers are situated at positions [4][0]-[4][1] and [4][2]-[4][3] (two bytes each), since we don?t have any other information there in this case. Elsewhere, if rms value is greater than the specified error value, we take both segments into account.
     Instead of using short int we prefer implementing conversion of int to 2 bytes short int and its reverse by hand, not to be machine-dependent. Also instead of using a 4-bytes long float coefficient, we convert the coefficient into fixed-point number of 2-bytes long. Maximum value of coefficient did not exceed 30, a precision of 1/1000 is obtained with 2 bytes.

      Decoding: The reverse process of encoding is followed, calculating the original values form the quantization table entries by the formula:

and then restoring these blocks according to the symmetry properties. After restoring the real and imaginary parts of transform values, inverse Fourier transform is applied and original pixel values of the 8x8 image segment are obtained.
 
Image
Initial Size
Compressed Size
RMS
Compression Rate
Lena
245.805
141.973
4.58
42%
Oguz and selim
155.198
110.959
2.88
26%
Generated 1
25.823
31.421
11.78
- 22%

Back to main page

Hosted by www.Geocities.ws

1