Faster lossless rotation of JPEG images

• US 20030048956A1
• Filed: 07/02/2001
• Published: 03/13/2003
• Est. Priority Date: 07/02/2001
• Status: Active Grant

• Current Assignee: Pendragon Networks LLC (Pendrell Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Rijavec, Nenad, Mitchell, Joan L.
• Granted Patent: US 6,819,803 B2
• Time in Patent Office: Days
• US Class Current: 382/250
• CPC Class Codes: G06T 3/60 Rotation of whole images or parts thereof

Abstract

Image rotations of 90°, 180° and 270° and horizontal and vertical mirroring image transformations are performed losslessly and with greatly enhanced speed by processing orthogonal transform coefficients in a zig-zag order with direct storage of S (size) values, reassociated R (run of zero valued coefficients) from an adjacent coded orthogonal transform value and a non-zero valued transformation coefficient in reverse zig-zag order. Cache misses are avoided by processing values which are not widely separated in the coded data and other features of the technique and memory accesses are reduced to accelerate processing while extremely little computation is required. These effects are substantially augmented when intermediate codes having certain attributes including coding of zero valued coefficients and flagging certain code features are employed.

Claims

1. A method of lossless image rotation by operation on compressed data including steps of

associating an R value of a run length of zero-values preceding a non-zero orthogonal transformation coefficient in a zig-zag order with an S value corresponding to an adjacent, following, non-zero orthogonal transformation coefficient in a reverse zig-zag order in a matrix of orthogonal transformation coefficient, and

outputting said R value and said S value with said orthogonal transformation coefficient.

2. A method as recited in claim 1, wherein said method is performed using a packed block data structure including

an R/S byte,

an orthogonal transform coefficient adjacent said R/S byte, and

an end of block indicator.

3. A method as recited in claim 1, wherein said method is performed using a packed data block structure including

a first pair of bytes representing a block number, a Klast value and at least one flag indicating if all said coefficient values in said block are coded in eight bits or fewer or if any requires more than eight bits to be uniquely coded,

a second pair of bytes respectively representing an R/S value and a coefficient value.

4. A method as recited in claim 3, wherein said packed block data structure further includes

at least one additional pair of bytes including a EOB byte and a padding byte.

5. A data format as recited in claim 3, wherein said first pair of bytes further includes

another flag indicating if any runs of consecutive zero-valued coefficients greater than sixteen are present in said block.

6. A method as recited in claim 1, including further steps of

testing for coefficient values requiring more than eight bits to be uniquely coded, and

using a flag in at least one block of data to indicate if all said coefficient values in said block are coded in eight bits or fewer or if any requires more than eight bits to be uniquely coded.

7. A method as recited in claim 6 wherein said coefficient values are DCT coefficients.

8. A method as recited in claim 7 wherein said DCT coefficients are AC DCT coefficients.

9. A method as recited in claim 2, wherein said testing step is performed once per image.

10. A method as recited in claim 2, wherein said testing step is performed once per block.

11. A method as recited in claim 2 including the further step of using another flag in a block of data to indicate if any ZRLs are present.

12. A method of performing lossless rotations of image data including the steps of

rearranging or maintaining orthogonal transform coefficient zig-zag order, depending on rotation angle,

altering signs of said orthogonal transform coefficients by an exclusive OR operation inverting binary values of said orthogonal transform coefficients, and

storing an R value with an adjacent S value and orthogonal transform coefficient value in reverse zig-zag order if said zig-zag order is rearranged.

13. A method as recited in claim 12, wherein said method is performed using a packed block data structure including

an R/S byte,

an orthogonal transform coefficient adjacent said R/S byte, and

an end of block indicator.

14. A method as recited in claim 12, wherein said method is performed using a packed data block structure including

a first pair of bytes representing a block number, a Klast value and at least one flag indicating if all said coefficient values in said block are coded in eight bits or fewer or if any requires more than eight bits to be uniquely coded,

a second pair of bytes respectively representing an R/S value and a coefficient value.

15. A method as recited in claim 14, wherein said packed block data structure further includes

at least one additional pair of bytes including a EOB byte and a padding byte.

16. A data format as recited in claim 14, wherein said first pair of bytes further includes

another flag indicating if any runs of consecutive zero-valued coefficients greater than sixteen are present in said block.

17. A method as recited in claim 12, including further steps of

testing for coefficient values requiring more than eight bits to be uniquely coded, and

using a flag in at least one block of data to indicate if all said coefficient values in said block are coded in eight bits or fewer or if any requires more than eight bits to be uniquely coded.

18. A method as recited in claim 17 wherein said coefficient values are DCT coefficients.

19. A method as recited in claim 18 wherein said DCT coefficients are AC DCT coefficients.

20. A method as recited in claim 19, wherein said testing step is performed once per image.

21. A method as recited in claim 19, wherein said testing step is performed once per block.

22. A method as recited in claim 19 including the further step of using another flag in a block of data to indicate if any ZRLs are present.