Fast method and apparatus for filtering compressed images in the DCT domain

• US 5,832,135 A
• Filed: 03/06/1996
• Issued: 11/03/1998
• Est. Priority Date: 03/06/1996
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Bhaskaran, Vasudev, Merhav, Neri
• Primary Examiner(s): Rogers, Scott
• Application Number:
  US08/612,513
• Time in Patent Office: 972 Days
• Field of Search: 382/265, 382/260, 382/268, 382/250, 382/248, 382/278, 358/432, 358/433, 348/403, 348/420, 364/724.17, 364/724.12
• US Class Current: 382/260
• CPC Class Codes: G06T 5/20 using local operators

Abstract

A method is described for filtering compressed images represented in the discrete-cosine-transform (DCT) domain. The filter includes three sparse, vertical submatrices which are sparse versions of the vertical filter components (VFCs) of a desired filter function that have been combined in such a way as to eliminate many of the non-zero elements. The filter also includes three sparse, horizontal transpose submatrices, which, like the vertical submatrices, are sparse versions of the horizontal filter components of the filter function. The sparseness of these sparse submatrices yields a significant reduction in the number of computations required to filter the image in the DCT domain. To take advantage of this discovery, the input DCT data blocks are "butterflied" to retain the relationship between the input data blocks and the filtered output data blocks as a function of these sparse submatrices. The sparseness of the vertical and horizontal submatrices reduces the number of computations required to filter the image. The sparseness of the DCT data blocks can also be used to further reduce the number of computations required.

Claims

1. A filter for a compressed image represented in a discrete cosine transform (DCT) domain and including a plurality of input DCT data blocks organized as:

##EQU20## the filter comprising;

a first computational module having a first input for receiving X_SE, a second input for receiving X_NE, and a third input for receiving X_E, the first computational module further including first, second and third vertical matrix memories for storing first (V_-), second (V₊₊) and third (V_-+) sparse vertical submatrices, respectively, the first computational module also having an output for providing an output z3 that is a predetermined arithmetic combination of the input DCT blocks X_SE, X_NE, and X_E and the sparse vertical submatrices V_-, V₊₊, and V_-+ ;

a first delay memory having an input coupled to the output of the first computational module for receiving the output Z₃ and an output for providing a delayed output Z₂, which is the output Z₃ delayed by a predetermined period;

a second delay memory having an input coupled to the output of the first memory for receiving the delayed output Z₂ and an output for providing a delayed output Z₁, which is delayed output Z₂ delayed by the predetermined period;

a second computational module having a first input coupled to the output of the first computational module for receiving output Z₃, a second input coupled to the output of the first memory for receiving delayed output Z₁, and a third input for receiving delayed output Z₂, the second computational module further including first, second and third horizontal matrix memories for storing first (H_-⁺), second (H₊₊^t) and third (H_-+^t) sparse horizontal transpose submatrices, respectively, the second computational module also having an output for providing an output Y that is a predetermined arithmetic combination of the outputs Z₃, Z₁ and Z₂, and the sparse horizontal submatrices H_-^t, H₊₊^t, and H_-+^t,

whereby the output Y is a filtered version of the image represented by the input DCT data blocks according to a desired filtering output.

2. A filter according to claim 1 wherein the first computational module includes:

a first arithmetic circuit having a first input for receiving X_SE, a second input for receiving X_NE, and a third input for receiving X_E, and having a first output for providing X_E^-, a second output for providing X_E⁺⁺, and a third output for providing X_E^+- ;

a first matrix multiplier having a first input coupled to the first vertical matrix memory for receiving the first sparse vertical submatrix V_-, a second input coupled to the first output of the first arithmetic circuit and an output for producing the product of X_E^- and V_- ;

a second matrix multiplier having a first input coupled to the second vertical matrix memory for receiving the second sparse vertical submatrix V₊₊, a second input coupled to the second output of the first arithmetic circuit and an output for producing the product of X_E⁺⁺ and V₊₊ ; and

a third matrix multiplier having a first input coupled to the third vertical matrix memory for receiving the third sparse vertical submatrix V_-+, a second input coupled to the third output of the first arithmetic circuit and an output for producing the product of X_E^+- and V_-+ ; and

a summer having a first input coupled to the output of the first matrix multiplier, a second input coupled to the output of the second matrix multiplier, a third input coupled to the output of the third matrix multiplier, and an output for providing a sum Z₃ equal to the sum of the outputs of the three matrix multipliers.

3. A filter according to claim 2 wherein the first arithmetic circuit includes:

a first summing circuit having a first input for receiving X_SE, a second input for receiving X_NE, and an output coupled to the second input of the first matrix multiplier for producing a sum X_E^- that is equal to X_NE minus X_SE ;

a second summing circuit having a first input for receiving X_SE, a second input for receiving X_NE, and an output for producing a sum X_NSE that is equal to X_NE plus X_SE ;

a divider circuit having an input coupled to the output of the second summing circuit for receiving X_NSE and an output for providing a result X_E⁺ that is equal to X_NSE divided by two;

a third summing circuit having a first input coupled to the output of the divider circuit for receiving X_E⁺, a second input for receiving X_E, and an output coupled to the second input of the second matrix multiplier for producing a sum X_E⁺⁺ that is equal to X_E⁺ plus X_E ; and

a fourth summing circuit having a first input for receiving X_E⁺, a second input for receiving X_E, and an output coupled to the second input of the third matrix multiplier for producing a sum X_E^+- that is equal to X_E⁺ minus X_E.

4. A filter according to claim 3 wherein the divider circuit and the second summing circuit comprise a shift-and-add circuit.

5. A filter according to claim 1 wherein the second arithmetic circuit includes:

a first arithmetic circuit having a first input coupled to the output of the first computational module for receiving Z₃, a second input coupled to the output of the second delay memory for receiving Z₁, and a third input coupled to the output of the first delay memory for receiving Z₂, and having a first output for providing Z_-, a second output for providing Z₊₊, and a third output for providing Z_+- ;

a first matrix multiplier having a first input coupled to the first horizontal matrix memory for receiving the first sparse horizontal transpose submatrix H_-^t, a second input coupled to the first output of the second arithmetic circuit and an output for producing the product of Z_- and H_-^t ;

a second matrix multiplier having a first input coupled to the second horizontal matrix memory for receiving the second sparse horizontal transpose submatrix H₊₊^t, a second input coupled to the second output of the second arithmetic circuit and an output for producing the product of Z₊₊ and H₊₊^t ; and

a third matrix multiplier having a first input coupled to the third horizontal matrix memory for receiving the third sparse horizontal transpose submatrix H_-+^t, a second input coupled to the third output of the second arithmetic circuit and an output for producing the product of Z_+- and H_-+^t ; and

a summer having a first input coupled to the output of the first matrix multiplier, a second input coupled to the output of the second matrix multiplier, a third input coupled to the output of the third matrix multiplier, and an output for providing a sum Y equal to the sum of the outputs of the three matrix multipliers.

6. A filter according to claim 5 wherein the second arithmetic circuit includes:

a first summing circuit having a first input for receiving Z₃, a second input coupled to the output of the second delay memory for receiving Z₁, and an output coupled to the second input of the first matrix multiplier for producing a sum Z_- that is equal to Z₁ minus Z₃ ;

a second summing circuit having a first input coupled to the output of the summer for receiving Z₃, a second input coupled to the output of the second delay memory for receiving Z₁, and an output for producing a sum Z₁₃ that is equal to Z₁ plus Z₃ ;

a divider circuit having an input coupled to the output of the second summing circuit for receiving Z₁₃ and an output for providing a result Z₊ that is equal to Z₁₃ divided by two;

a third summing circuit having a first input coupled to the output of the divider circuit for receiving Z₊, a second input coupled to the output of the first delay memory for receiving Z₂, and an output coupled to the second input of the second matrix multiplier for producing a sum Z₊₊ that is equal to Z₊ plus Z₂ ; and

a fourth summing circuit having a first input coupled to the output of the divider circuit for receiving Z₊, a second input coupled to the output of the first delay memory for receiving Z₂, and an output coupled to the second input of the third matrix multiplier for producing a sum Z_+- that is equal to Z₊ minus Z₂.

7. A filter according to claim 5 wherein the filter can be described by a vertical matrix V in the DCT domain wherein V can further be represented as:

space="preserve" listing-type="equation">V= V.sub.1, V.sub.2, V.sub.3 !, and

and a horizontal matrix H^t, where H^t is the transpose of a horizontal matrix H, wherein H^t can further be represented as;

space="preserve" listing-type="equation">H.sup.t = H.sub.1.sup.t, H.sub.2.sup.t, H.sub.3.sup.t !.

8. A filter according to claim 7 wherein the first vertical matrix memory includes the first sparse vertical submatrix V_-, wherein the first sparse vertical submatrix can be represented as:

##EQU21## wherein the second vertical matrix memory includes the second sparse vertical submatrix V₊₊, wherein the second sparse vertical submatrix can be represented as;

##EQU22## and wherein the third vertical matrix memory includes the third sparse vertical submatrix V_-+, wherein the third sparse vertical submatrix can be represented as;

##EQU23##

9. A filter according to claim 8 wherein the first sparse vertical submatrix V_- includes 32 nonzero elements and second and third sparse vertical submatrices V₊₊ and V_-+ each include 20 or fewer nonzero elements.

10. A filter according to claim 7 wherein the first horizontal matrix memory includes the first sparse horizontal transpose submatrix H_-^t, wherein the first sparse horizontal transpose submatrix can be represented as:

##EQU24## wherein the second horizontal matrix memory includes the second sparse horizontal transpose submatrix H₊₊^t, wherein the second sparse horizontal transpose submatrix can be represented as;

##EQU25## and wherein the third horizontal matrix memory includes the third sparse horizontal transpose submatrix H_-+^t, wherein the third sparse horizontal transpose submatrix can be represented as;

##EQU26##

11. A method of filtering a compressed image represented in a discrete cosine transform (DCT) domain and including a plurality of DCT data blocks, the method comprising the steps of:

providing a desired filter represented by a vertical component matrix V of a filter matrix and by a transpose horizontal component matrix H^t of the filter matrix, where H^t is a transpose matrix of a horizontal component matrix H, the filter receiving the DCT data blocks as input data and producing filtered data as output represented by an output block Y in the DCT domain;

partitioning the vertical matrix V into vertical submatrices;

combining the vertical submatrices to form sparse vertical submatrices;

partitioning the transpose matrix H_t into horizontal transpose submatrices;

combining the horizontal transpose submatrices to form sparse horizontal transpose submatrices;

combining the DCT data blocks in a predetermined manner to form butterflied DCT data blocks so that the output block Y is expressed only in terms of the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to a reduced expression; and

combining the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to the reduced expression to produced the output block Y, wherein the number of operations required to perform this step is less than required to filter the image in the spatial domain.

12. A method of filtering a compressed image according to claim 11 wherein the step of partitioning the vertical matrix V into vertical submatrices includes partitioning the vertical matrix V into three vertical submatrices V₁, V₂, and V₃, where V = V₁, V₂, V₃ !.

13. A method of filtering a compressed image according to claim 12 wherein the step of combining the vertical submatrices to form sparse vertical submatrices includes combining the vertical submatrices V₁, V₂, and V₃ to form three sparse vertical submatrices V₊₊, V_-+, and V_-, wherein ##EQU27##

14. A method of filtering a compressed image according to claim 13 wherein the DCT data blocks are organized as follows:

##EQU28## wherein the step of combining the DCT data blocks in a predetermined manner to form butterflied DCT data blocks so that the output block Y is expressed only in terms of the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to a reduced expression includes the steps of;

computing X_E^- according to the following formula;

space="preserve" listing-type="equation">X.sub.E.sup.31 =X.sub.NE -X.sub.SE,

computing X_E⁺⁺ according to the following formula;

##EQU29## and computing X_E^+- according to the following formula;

##EQU30##

15. A method of filtering a compressed image according to claim 14 wherein the step of computing X_E⁺⁺ includes the step of computing X_E⁺ according to the following formula:

##EQU31## and computing X_E⁺⁺ according to the following formula;

space="preserve" listing-type="equation">X.sub.E.sup.++ =X.sub.E.sup.+ +X.sub.E.

16. A method of filtering a compressed image according to claim 15 wherein the step of computing X_E^+- includes the step of computing X_E⁺ according to the following formula:

##EQU32## and computing X_E^+- according to the following formula;

space="preserve" listing-type="equation">X.sub.E.sup.+- =X.sub.E.sup.+ -X.sub.E.

17. A method of filtering a compressed image according to claim 16 wherein the step of partitioning the transpose matrix H^t into horizontal transpose submatrices includes partitioning the transpose matrix H^t into three horizontal transpose submatrices H₁^t, H₂^t, and H₃^t, where

18. A method of filtering a compressed image according to claim 17 wherein the step of combining the horizontal transpose submatrices to form sparse horizontal transpose submatrices includes the step of combining the three horizontal transpose submatrices H₁^t, H₂^t, and H₃^t to form three sparse horizontal transpose submatrices H₊₊^t, H_-+^t, and H_-^t,

wherein ##EQU33##

19. A method of filtering a compressed image according to claim 18 wherein the step of combining the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to the reduced expression to produced the filtered to data Y includes the step of computing Z₃ according to the following formula:

space="preserve" listing-type="equation">Z.sub.3 =V.sub.++ X.sub.E.sup.++ +V.sub.-+ X.sub.E.sup.+- +V.sub.- X.sub.E.sup.-.

20. A method of filtering a compressed image according to claim 19 wherein the step of combining the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to the reduced expression to produced the filtered to data Y includes the steps of:

storing Z₃ for one period to produce Z₂ ; and

storing Z₂ for one period to produce Z₁.

21. A method of filtering a compressed image according to claim 19 wherein the step of combining the DCT data blocks to form butterflied DCT data blocks so that the output block Y is expressed only in terms of the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to a reduced expression includes the steps of:

computing Z_- according to the following formula;

space="preserve" listing-type="equation">Z.sub.- =(Z.sub.1 -Z.sub.3),

computing Z₊₊ according to the following formula;

##EQU34## and computing Z_+- according to the following formula;

##EQU35##

22. A method of filtering a compressed image according to claim 21 wherein the step of computing Z₊₊ includes the step of computing Z₊ according to the following formula:

##EQU36## and computing Z₊₊ according to the following formula;

space="preserve" listing-type="equation">Z.sub.++ =(Z.sub.+ +Z.sub.2).

23. A method of filtering a compressed image according to claim 21 wherein the step of computing Z_+- includes the step of computing Z₊ according to the following formula:

##EQU37## and computing Z_+- according to the following formula;

space="preserve" listing-type="equation">Z.sub.+- =(Z.sub.+ -Z.sub.2).

24. A method of filtering a compressed image according to claim 21 wherein the step of combining the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to the reduced expression to produced the filtered to data Y includes the step of combining the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to the following formula:

space="preserve" listing-type="equation">Y=Z.sub.++ H.sub.-+.sup.t +Z.sub.+.sup.- H.sub.-+.sup.t +Z.sub.- H.sub.-.sup.t.

25.

25. A method of filtering a compressed image according to claim 11 wherein the sparse vertical submatrices include nonzero elements and zero elements and wherein the step of combining the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to the reduced expression to produced the filtered to data Y includes the step of combining the butterflied DCT data blocks, only the nonzero elements of the sparse vertical submatrices, and the sparse horizontal transpose submatrices.

26. A method of filtering a compressed image according to claim 11 wherein the sparse horizontal transpose submatrices include nonzero elements and zero elements and wherein the step of combining the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to the reduced expression to produced the filtered to data Y includes the step of combining the butterflied DCT data blocks, sparse vertical submatrices, and only the nonzero elements of the sparse horizontal transpose submatrices.

27. A method of filtering a compressed image according to claim 11 wherein the butterflied DCT data blocks include nonzero elements and zero elements and wherein the step of combining the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to the reduced expression to produced the filtered to data Y includes the step of combining only the nonzero elements of the butterflied DCT data blocks, sparse vertical submatrices, and the sparse horizontal transpose submatrices.

28. A method of filtering a compressed image according to claim 11 further including the step of storing the sparse vertical submatrices and the sparse horizontal transpose submatrices on a general purpose computer.

29. A method of filtering a compressed image according to claim 28 further wherein the steps of combining the DCT data blocks in a predetermined manner to form butterflied DCT data blocks so that the output block Y is expressed only in terms of the butterflied DCT data blocks and combining the butterflied DCT data blocks, the sparse vertical submatrices, and the sparse horizontal transpose submatrices according to the reduced expression to produced the filtered to data Y includes the steps of executing these steps by the general purpose computer programmed according to the reduced expression.

30. A general purpose computer programmed to filter a spatial domain image that has been compressed and is represented in a discrete cosine transform (DCT) domain, the general purpose computer comprising:

a microprocessor;

a storage device coupled to the storage device;

first (V₊₊), second (V_-) and third (V_-) sparse vertical submatrices stored on the storage device, wherein each of the sparse vertical submatrices include a predetermined number of zero and nonzero elements;

first (H₊₊^t), second (H_-^t) and third (H_-^t) sparse horizontal transpose submatrices stored on the storage device, wherein each of the sparse horizontal transpose submatrices include a predetermined number of zero and nonzero elements;

a compressed image stored on the storage device, the compressed image including a plurality of DCT data blocks organized in columns;

computer software stored on the storage device and executable by the microprocessor, the microprocessor performing the following steps under control of the software;

(a) fetching a first column of DCT data blocks from the storage device, the first column including DCT data blocks X₁, X₂ and X₃ ;

(b) computing X₊₊ according to the following formula;

##EQU38## (c) computing X_+- according to the following formula;

##EQU39## (d) computing X_- according to the following formula;

space="preserve" listing-type="equation">X.sub.- =X.sub.1 -X.sub.3,

(e) computing Z₁ according to the following formula;

space="preserve" listing-type="equation">Z.sub.3 =V.sub.++ X.sub.++ +V.sub.-+ X.sub.+- +V.sub.- X.sub.-,

(f) retrieving a variable Z₂ ;

(g) retrieving a variable Z₁ ;

(h) computing Z₊₊ according to the following formula;

##EQU40## (i) computing Z_+- according to the following formula;

##EQU41## (j) computing Z_- according to the following formula;

space="preserve" listing-type="equation">Z.sub.- =Z.sub.1 -Z.sub.3,

(k) computing Y according to the following formula;

space="preserve" listing-type="equation">Y=H.sub.++.sup.t Z.sub.++ +H.sub.-+.sup.t Z.sub.+- +H.sub.-.sup.t Z.sub.-,

where Y is a filtered version of the spatial domain image represented in the DCT domain, whereby the number of computations required to filter the image in the DCT domain is less than that required to filter the image in the spatial domain.

31. A general purpose computer programmed to filter a spatial domain image that has been compressed and is represented in a discrete cosine transform (DCT) domain according to claim 30, the microprocessor further performing the following steps under control of the software:

(1) computing X₃₀ according to the following formula;

##EQU42## and (m) computing X₊₊ according to the following formula;

space="preserve" listing-type="equation">X.sub.++ =X.sub.+ +X.sub.2.

32. A general purpose computer programmed to filter a spatial domain image that has been compressed and is represented in a discrete cosine transform (DCT) domain according to claim 31, the microprocessor further performing the following steps under control of the software:

(n) computing X_+- according to the following formula;

space="preserve" listing-type="equation">X.sub.+- =X.sub.+ -X.sub.2, .

33.

33. A general purpose computer programmed to filter a spatial domain image that has been compressed and is represented in a discrete cosine transform (DCT) domain according to claim 32, the microprocessor further performing the following steps under control of the software:

(o) computing X₊ by performing a shift-and-add function.

34. A general purpose computer programmed to filter a spatial domain image that has been compressed and is represented in a discrete cosine transform (DCT) domain according to claim 30, the microprocessor further performing the following steps under control of the software:

(p) computing Z₊ according to the following formula;

##EQU43## and (q) computing Z_+- according to the following formula;

space="preserve" listing-type="equation">Z.sub.+- =Z.sub.+ -Z.sub.3.

35.

35. A general purpose computer programmed to filter a spatial domain image that has been compressed and is represented in a discrete cosine transform (DCT) domain according to claim 30, the microprocessor further performing the following steps under control of the software:

(r) in steps (b) through (e), ignoring zero elements in the DCT data blocks X₁, X₂ and X₃ in order to further reduce the number of computations required to filter the image.

36. A general purpose computer programmed to filter a spatial domain image that has been compressed and is represented in a discrete cosine transform (DCT) domain according to claim 30, the microprocessor further performing the following steps under control of the software:

(s) in step (e), ignoring zero elements in the first (V₊₊), second (V_-) and third (V_-) sparse vertical submatrices in order to further reduce the number of computations required to filter the image.

37. A general purpose computer programmed to filter a spatial domain image that has been compressed and is represented in a discrete cosine transform (DCT) domain according to claim 30, the microprocessor further performing the following steps under control of the software:

(t) in step (k), ignoring zero elements in the first (H₊₊^t), second (H_-^t) and third (H_-^t) sparse horizontal transpose submatrices in order to further reduce the number of computations required to filter the image.

38. A general purpose computer programmed to filter a spatial domain image that has been compressed and is represented in a discrete cosine transform (DCT) domain according to claim 30, the microprocessor further performing the following steps under control of the software:

(u) storing Z₂ as Z₁ ; and

, then

(v) storing Z₃ as Z₂.