Method and apparatus for optimizing a JPEG image using regionally variable compression levels
View Patent ↗A method of JPEG compression of an image frame divided up into a plurality of non-overlapping, tiled 8×8 pixel blocks X i . A global quantization matrix Q is determined by either selecting a standard JPEG quantization table or selecting a quantization table such that the magnitude of each quantization matrix coefficient, Q[m,n] is inversely proportional to the aggregate visual importance in the image of the corresponding DCT basis vector. Next a linear scaling factor S i is selected for each block, bounded by user selected values S min and S max . Transform coefficients, Y i , obtained from a digital cosine transform of X i , are quantized with global table S min Q while emulated the effects of quantization with local table S i Q and the quantized coefficients T i [m,n] and global quantization table S min Q are entropy encoded , where S min is a user selected minimum scaling factor, to create a JPEG Part 1 image file. The algorithm is unique in that it allows for the effect of variable-quantization to be achieved while still producing a fully compliant JPEG Part 1 file.
1. A method of JPEG compression of an image frame divided up into a plurality of non-overlapping, tiled 8×8 pixel blocks X i comprising:
(a) forming a discrete cosine transform (DCT) of each block X i of the image frame to produce a matrix of blocks of transform coefficients Y i ;
(b) calculating a visual importance, I i , for each block of the image, based upon assigning zeros for flat features and values approaching unity for sharply varying features;
(c) forming a global quantization matrix Q by one of
(i) selecting a standard JPEG quantization table and
(ii) selecting a quantization table such that the magnitude of each quantization matrix coefficient Q[m,n] is inversely proportional to the aggregate visual importance in the image of a corresponding DCT basis vector; and
(d) calculating linear scaling factors S i defining bounds over which the image is to be variably quantized;
(e) approximating variable quantization of the transform coefficients, Y i [m,n], using the local quantization table S i Q while actually producing coefficients T i [m,n] that have been quantized using global quantization table S min Q where S min is a scaling value used in compressing the image that defines the quality bounds over which the image will be variably quantized; and
(f) entropy encoding quantized coefficients T i [m,n] and global quantization table S min Q to create a JPEG Part 1 image file.
2. A method according to claim 1 , wherein step (e) includes rounding Y i [m,n]/(S min Q[m,n]) to the nearest integer to form quantized DCT transformed coefficients T i [m,n];
(f) setting T i [m,n]=0 if round (Y i [m,n]/(S i Q[m,n]))=0; and
(g) setting T i [m,n]=sign(T i [m,n]) P(T i [m,n]) if Ernd i [m,n] is less than or equal to Evq i [m,n] wherein P(x)=2 floor(lg(x)) −1 and T i [m,n] and wherein Ernd i (m,n) is the error introduced by rounding down the coefficient T i (m,n) to the nearest smaller integer of the form 2 k −1 and wherein Evg(m,n) is the error that would be introduced to the coefficient Y[m,n] by uniform quantization with a local quantization matrix S i Q.
3. A method according to claim 1 , including calculating a linear scaling factor S i equal to I i *(S max −S min )+S min where S min and S max are user specified to define bounds over which the image will be variably quantized.
4. The method according to claim 1 , where I i is determined by discrete edge detection and summation of transform coefficients.
5. The method according to claim 1 , wherein I i is determined by creating a 24×24 matrix of image pixels of DCT coefficients centered on a block X i , convolving said 24×24 matrix with an edge tracing kernel to produce a convolved matrix, summing center 10×10 matrix values of said convolved matrix to produce a summed value, and normalizing said summed value to produce a visual importance, I i .
6. The method according to claim 1 , wherein the global quantization matrix Q of item c (ii) is formed by calculating an 8×8 matrix A by calculating matrix elements A[m,n] of said A according to the formula
A
[
m
,
n
]
=
∑
all
i
I
i
Y
i
[
m
,
n
]
calculating elements Q min of said Q according to the formula
Q[m,n ]=max(entries of A)/ A[m,n]
and scaling coefficients of Q by a constant factor a for all values of (m,n) except (0,0) in order to minimize an error between Q and a standard JPEG quantization matrix.
7. A method of JPEG compression of an image frame divided up into a plurality of non-overlapping, tiled 8×8 pixel blocks X i , comprising:
(a) forming a discrete cosine transform (DCT) of each block X i of the image frame to produce a matrix of blocks of transform coefficients Y i ;
(b) calculating a visual importance, I i , for each block of the image, based upon assigning zeros for flat features and values approaching unity for sharply varying features;
(c) forming a global quantization matrix Q by one of
(i) selecting a standard JPEG quantization table and
(ii) selecting a quantization table such that the magnitude of each quantization matrix coefficient Q[m,n] is inversely proportional to the aggregate visual importance to the image of a corresponding DCT basis vector; and
(d) selecting a linear scaling factor S i defining bounds over which the image is to be variably quantized wherein S i =I i (S max −S min )+S min where S max and S min are user selected;
(e) quantizing the transform coefficients, Y i [m,n], to produce quantized blocks T i [m,n] as follows:
(i) T i [m,n]=round(Y i [m,n]/(S min Q[m,n])), where round denotes rounding to the nearest integer;
(ii) setting T i [m,n]=0 if round (Y i [m,n]/(S i Q[m,n]))=0; and
(iii) setting T[m,n]=sign(T i [m,n]) P(abs(T i [m,n])) if Ernd i [m,n] is less than or equal to Evq i [m,n] wherein P(x)=2 floor(lg(x)) −1 and T i [m,n] and wherein Ernd i (m,n) is the error introduced by rounding down the coefficient T i (m,n) to the nearest smaller integer of the form 2 k −1 and wherein Evq(m,n) is the error that would be introduced to the coefficient Y[m,n] by uniform quantization with a local quantization matrix S i Q;
(f) entropy encoding quantized coefficients T i [m,n] and global quantization matrix S min Q, to create a JPEG Part 1 image file.
8. A method of JPEG compression of a colour image represented by channels Y for greyscale data, and U and V each for colour, comprising:
(a) subsampling the colour channels U and V by an integer fraction of their size;
(b) forming a discrete cosine transform (DCT) Y i for each block X i of each of channels Y, U and V;
(c) calculating a visual importance, I i , for each Y channel block of each image arid setting I i =max{I i values for corresponding Y channel blocks} for blocks in the U and V channels;
(d) forming a global quantization matrix Q for the Y channel block and one for channels U and V combined such that a magnitude of each quantization matrix coefficient Q[m,n] is inversely proportional to the aggregate visual importance in the image of a corresponding DCT basis vector; and
(e) approximating variable quantization of the transform coefficients, Y i [m,n], using the local quantization table S i Q while actually producing coefficients T i [m,n] that have been quantized using global quantization table S min Q, where Q is the global quantization table for the associated channel being quantized; and
(f) entropy encoding quantized coefficients T i [m,n] and global quantization table S min Q, where S min is a user selected minimum scaling factor for each of channels Y, U, and V, to create a JPEG Part 1 image file for each of channels Y, U and V.
9. The method of claim 8 wherein the subsampling factor is 2.
10. Apparatus for JPEG compression of an image frame divided up into a plurality of non-overlapping, tiled 8×8 pixel blocks X i comprising:
(a) a discrete cosine transformer (DCT) operative to form the discrete cosine transform of each block X i of the image frame to produce blocks of transform coefficients Y i ;
(b) a visual importance calculator operative to calculate the visual importance, I i , for each block of the image, based upon assigning zeros for flat features and values approaching unity for sharply varying features;
(c) a global quantization matrix calculator operative to calculate the global quantization matrix, Q, by one of
(i) selecting a standard JPEG quantization table and
(ii) selecting a quantization table such that the magnitude of each quantization matrix coefficient Q[m,n] is inversely proportional to the aggregate visual importance in the image of a corresponding DCT basis vector; and
(d) a linear scaling factor calculator operative to determine a linear scaling factor, S i , defining bounds over which the image is to be variably quantized based on user established values of S max and S min ;
(e) a variable quantization calculator operative to approximate variable quantization of the transform coefficients, Y i [m,n], using the local quantization table S i Q while actually producing coefficients T i [m,n] that have been quantized using global quantization table S min Q, where S min is a user selected minimum scaling factor; and
(f) an entropy encoder operative to encode the quantized coefficients T i [m,n] and global quantization table S min Q to create a JPEG Part 1 image file.
11. Apparatus according to claim 10 , wherein said quantizer rounds/(S min *Q) Y i [m,n]/(S min Q[m,n] to the nearest integer to form quantized DCT transformed coefficients T i [m,n] and
(f) sets T i [m,n]=0 if round (Y i [m,n]/(S i Q[m,n]))=0; and
(g) sets T i [m,n]=sign(T i [m,n]) P(abs(T i [m,n])) if Ernd i [m,n] is less than or equal to Evq i [m,n] wherein P(x)=2 floor(lg(x)) −1 and T i [m,n] and wherein Ernd i (m,n) is the error introduced by rounding down the coefficient T i (m,n) to the nearest smaller integer of the form 2 k −1 and wherein Evg(m,n) is the error that would be introduced to the coefficient Y[m,n] by uniform quantization with a local quantization matrix S i Q.
12. Apparatus according to claim 10 , wherein said linear scaling factor calculator determines a linear scaling factor S i equal to I i (S max −S min where S min and S max are user specified to define bounds over which the image will be variably quantized.