Image transformations in the compressed domain

• US 6,298,166 B1
• Filed: 03/30/1998
• Issued: 10/02/2001
• Est. Priority Date: 03/30/1998
• Status: Expired due to Term

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Bhaskaran, Vasudev, Ivashin, Victor, Ratnakar, Viresh
• Primary Examiner(s): Tran, Phouc
• Assistant Examiner(s): Alavi, Amir
• Application Number:
  US09/052,039
• Time in Patent Office: 1,282 Days
• Field of Search: 382/232, 382/233, 382/234, 382/235, 382/236, 382/237, 382/238, 382/239, 382/240, 382/241, 382/242, 382/243, 382/244, 382/245, 382/246, 382/248, 382/276, 382/295-297, 348/207, 358/133, 358/432, 708/203, 708/400
• US Class Current: 382/248
• CPC Class Codes: G06T 3/60 Rotation of whole images or parts thereof
• CPC Class Codes: H04N 19/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

Image processing techniques which involve direct manipulation of the compressed domain representation of an image to achieve the desired spatial domain processing without having to go through a complete decompression and compression process. The techniques include processing approaches for performing the eight operations in D₄ (the dihedral group of symmetries of a square) on JPEG images using the discrete cosine transform (DCT) domain representation of the images directly. For a task such as image rotation by 90° (an operation in D₄), DCT-domain based methods can yield nearly a five-fold increase in speed over a spatial-domain based technique. These simple compressed-domain based processing techniques are well suited to the imaging tasks that are needed in a JPEG-based digital still-camera system.

Claims

1. A method for performing a dihedral symmetry operation on a spatial domain representation of a digital image by manipulating a linear transform domain representation of the digital image, said method comprising the steps of:

parsing compressed image data of the digital image to extract an offset value and a DC value for each of a plurality of linear-transform-based coded data blocks, wherein elements of the data blocks were previously coded as a sequence of symbol trios so that the steps of said method are performed without de-zigzagging and zigzagging the elements of each data block;

accessing each of the plurality of linear-transform-based coded data blocks by using the corresponding offset value;

extracting a sequence of non-zero elements from each of the plurality of linear-transform-based coded data blocks;

transposing the sequence of non-zero elements within each data block without expanding into a full data block; and

coding the transposed sequence of non-zero elements of each data block;

wherein the spatial domain representation of the digital image undergoes a dihedral symmetry operation.

2. The method as recited in claim 1, wherein the step of transposing the sequence of non-zero elements within each of the data blocks further comprises the steps of:

sequentially examining the sequence of non-zero elements of each of the plurality of data blocks;

determining the non-zero elements that are positioned within a same one of a plurality of cross-diagonals of each data block; and

reversing the order of non-zero elements positioned within the same cross-diagonal.

3. The method as recited in claim 1, wherein the dihedral symmetry operation comprises flipping the digital image over its main diagonal.

4. The method as recited in claim 1, further comprising the step of applying sign-changes to the sequence of non-zero elements within each data block wherein the dihedral symmetry operation comprises flipping the digital image over its main cross-diagonal axis.

5. The method as recited in claim 1, further comprising the step of applying sign-changes to the sequence of non-zero elements within each data block wherein the dihedral symmetry operation comprises rotating the digital image 90°

clockwise.

6. The method as recited in claim 1, further comprising the step of applying sign-changes to the sequence of non-zero elements within each data block wherein the dihedral symmetry operation comprises rotating the digital image 90°

counterclockwise.

7. The method as recited in claim 4, wherein, after transposing the sequence of non-zero elements within each data block, sign-reversing every other non-zero element within each data block without expanding into a full data block.

8. The method as recited in claim 5, wherein, after transposing the sequence of non-zero elements within each data block, sign-reversing the odd-column non-zero elements within each data block without expanding into a full data block.

9. The method as recited in claim 6, wherein, after transposing the sequence of non-zero elements within each data block, sign-reversing the odd-row non-zero elements within each data block without expanding into a full data block.

33. The method as recited in claim 1, wherein the symbol trio comprises first, second and third symbols, the first symbol representing the number of consecutive zeros in a zigzag ordering of the corresponding data block, and the next non-zero element has a value x such that:

10. A digital camera, comprising:

a sensor for capturing light and converting the light into an analog image signal;

an analog-to-digital converter for converting the analog image signal to a digital image in spatial domain; and

a digital image processor for compressing the digital image from a spatial domain representation of the digital image to a linear transform domain representation of the digital image defined by a plurality of linear-transform-based coded data blocks, wherein elements of the data blocks are coded as a sequence of symbol trios during the compressing, wherein said digital image processor parses compressed image data of the digital image to extract an offset value and a DC value for each of the plurality of linear-transform-based coded data blocks, accesses each of the plurality of linear-transform-based coded data blocks by using the corresponding offset value, extracts a sequence of non-zero elements of each of the plurality of linear-transform-based coded data blocks, transposes the sequence of non-zero elements within each data block without expanding into a full data block, applies sign change to non-zero elements within each data block and codes the sequence of non-zero elements of each data block, without de-zigzagging and zigzagging the elements of each data block, to perform a dihedral symmetry operation on the spatial domain representation of the digital image.

11. The digital camera as recited in claim 10, wherein the dihedral symmetry operation comprises rotating the digital image 90°

clockwise.

12. The digital camera as recited in claim 10, wherein the dihedral symmetry operation comprises flipping the digital image over its main cross diagonal.

13. The digital camera as recited in claim 10, wherein the dihedral symmetry operation comprises rotating the digital image 90°

counterclockwise.

14. The digital camera as recited in claim 11, wherein, after said digital image processor transposes the sequence of non-zero elements within each data block, said digital image processor sign-reverses the odd-column non-zero elements within each data block without expanding into a full data block.

15. The digital camera as recited in claim 12, wherein, after said digital image processor transposes the sequence of non-zero elements within each data block, said digital image processor sign-reverses every other non-zero element within each data block without expanding into a full data block.

16. The digital camera as recited in claim 13, wherein, after said digital image processor transposes the sequence of non-zero elements within each data block, said digital image processor sign-reverses the odd-row non-zero elements within each data block without expanding into a full data block.

34. The digital camera as recited in claim 10, wherein the symbol trio comprises first, second and third symbols, the first symbol representing the number of consecutive zeros in a zigzag ordering of the corresponding data block, and the next non-zero element has a value x such that:

17. A computer system having a computer-readable program code embodied therein for causing the computer system to geometrically transform a digital image in spatial domain by performing the steps of:

processing the digital image to obtain a linear transform domain representation of the digital image defined by a plurality of linear-transform-based coded data blocks, wherein elements of the data blocks are coded as a sequence of symbol trios so that the steps are performed without de-zigzagging and zigzagging the elements of each data block;

parsing the compressed image data to extract an offset value and a DC value for each of the plurality of linear-transform-based coded data blocks;

accessing each of the plurality of linear-transform-based coded data blocks by using the corresponding offset value;

extracting a sequence of non-zero elements from each of the plurality of linear-transform-based coded data blocks;

transposing the sequence of non-zero elements within each data block without expanding into a full data block; and

coding the transposed sequence of non-zero elements of each data block;

wherein the spatial domain representation of the digital image undergoes a dihedral symmetry operation.

18. The computer system as recited in claim 17, wherein the step of transposing the sequence of non-zero elements within each of the data blocks further comprises the steps of:

sequentially examining the sequence of non-zero elements of each of the plurality of data blocks;

determining the non-zero elements that are positioned within a same one of a plurality of cross-diagonals of each data block; and

reversing the order of non-zero elements positioned within the same cross-diagonal.

19. The computer system as recited in claim 17, wherein the dihedral symmetry operation comprises flipping the digital image over its main diagonal.

20. The computer system as recited in claim 17, further comprising the step of applying a sign change to non-zero elements wherein the dihedral symmetry operation comprises rotating the digital image over its main cross-diagonal axis.

21. The computer system as recited in claim 17, further comprising the step of applying a sign change to non-zero elements wherein the dihedral symmetry operation comprises rotating the digital image 90°

clockwise.

22. The computer system as recited in claim 17, further comprising the step of applying a sign change to non-zero elements wherein the dihedral symmetry operation comprises rotating the digital image 90°

counterclockwise.

23. The computer system as recited in claim 20, wherein, after transposing the sequence of non-zero elements within each data block, sign-reversing every other non-zero element within each data block without expanding into a full data block.

24. The computer system as recited in claim 21, wherein, after transposing the sequence of non-zero elements within each data block, sign-reversing the odd-column non-zero elements within each data block without expanding into a full data block.

25. The computer system as recited in claim 22, wherein, after transposing the sequence of non-zero elements within each data block, sign-reversing the odd-row non-zero elements within each data block without expanding into a full data block.

35. The computer system as recited in claim 17, wherein the symbol trio comprises first, second and third symbols, the first symbol representing the number of consecutive zeros in a zigzag ordering of the corresponding data block, and the next non-zero element has a value x such that:

 

S=┌

log₂(|x|+1),

26. A method for performing a dihedral symmetry operation on a spatial domain representation of a digital image by manipulating a linear transform domain representation of the digital image, said method comprising the steps of:

parsing compressed image data of the digital image to extract an offset value and a DC value for each of a plurality of linear-transform-based coded data blocks, wherein elements of the data block were previously coded as a sequence of symbol trios so that the steps of said method are performed without de-zigzagging and zigzagging the elements of each data block;

accessing each of the plurality of linear-transform-based coded data blocks by using the corresponding offset value;

extracting a sequence of non-zero elements from each of the plurality of linear-transform-based coded data blocks;

applying sign-changes to the sequence of non-zero elements within each data block without expanding into a full data block; and

coding the resulting sequence of non-zero elements of each data block;

wherein the spatial domain representation of the digital image undergoes a dihedral symmetry operation.

27. The method as recited in claim 26, wherein the dihedral symmetry operation comprises rotating the digital image over its middle-horizontal axis.

28. The method as recited in claim 26, wherein the dihedral symmetry operation comprises rotating the digital image over its middle-vertical axis.

29. The method as recited in claim 26, wherein the dihedral symmetry operation comprises rotating the digital image 180°

.

30. The method as recited in claim 27, wherein the step of applying sign-changes is applied to sign-reverse the odd-column elements within each data block without expanding into a full data block.

31. The method as recited in claim 28, wherein the step of applying sign-changes is applied to sign-reverse the odd-row elements within each data block without expanding into a full data block.

32. The method as recited in claim 29, wherein the step of applying sign-changes is applied to sign-reverse every other element within each data block without expanding into a full data block.

36. The method as recited in claim 26, wherein the symbol trio comprises first, second and third symbols, the first symbol representing the number of consecutive zeros in a zigzag ordering of the corresponding data block, and the next non-zero element has a value x such that: