Reordering of compressed data

• US 7,146,053 B1
• Filed: 05/10/2000
• Issued: 12/05/2006
• Est. Priority Date: 05/10/2000
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Rijavec, Nenad, Mitchell, Joan LaVerne
• Primary Examiner(s): DANG, DUY M
• Application Number:
  US09/569,573
• Time in Patent Office: 2,400 Days
• Field of Search: 382/233, 382/235, 382244-248, 382/297, 382/240, 382/232, 375/240.11, 375/240.19
• US Class Current: 382/233
• 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/60 using transform coding
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards

Abstract

Apparatus and methods are provided for encoding independently decodable pieces of compressed data to accommodate reordering of the pieces of compressed data before or after manipulation. Encoding can occur before or after manipulation of the source information. For example, in the context of a JPEG image, MCUs can be rotated and promptly compressed with restart markers without extra buffering to put the MCUs in the correct rotated order. Later, the order of the independently decodable pieces can be changed to accommodate proper output. Alternatively, pointers to the independently decodable pieces can be used to present the data to the decoder in the proper order. Additional reentry information within the independently decodable pieces of compressed data can allow initiation of decoding at other than the independently decodable points. Such reentry information preferably would include bit-level pointers and sufficient state information to initialize the decoder properly. For example, in the context of a JPEG image, in addition to the typical information available to the decoder that has been passed in earlier markers, the reentry information for a given MCU boundary may include: a bit-level pointer to the first block'"'"'s DC Huffman code, the position of the output, and a DC predictor for each component of the MCU.

Claims

1. A method comprising:

receiving data;

encoding independently decodable pieces of the data to produce a compressed data stream in an input order;

rotating the independently decodable pieces of data, each by the same amount; and

reordering the rotated independently decodable pieces into an output order suited to the rotation.

2. The method of claim 1, wherein the data comprises source data.

3. The method of claim 2, wherein source data corresponding to the compressed data stream comprises video data.

4. The method of claim 3, wherein the video data is compressed according to one of the Moving Pictures Expert Group (MPEG) standards.

5. The method of claim 4, wherein the independently decodable pieces of data start at slice boundaries.

6. The method of claim 1, wherein the data comprises intermediate data.

7. The method of claim 1, wherein said rotating the data comprises rotating the data in the transform domain.

8. The method of claim 1, wherein source data corresponding to the compressed data stream comprises image data.

9. The method of claim 8, wherein the image data compression technique is transform based.

10. The method of claim 9, wherein the image data compression technique is discrete cosine transform (DCT) based.

11. The method of claim 10, wherein the image data is compressed according to one of the Joint Photographic Experts Group (JPEG) standards.

12. The method of claim 11, wherein the independently decodable pieces of data include one or more restart markers.

13. The method of claim 12, further comprising updating modulo counters embedded within the one or more restart markers to reflect the correct output order.

14. The method of claim 1, wherein source data corresponding to the compressed data stream comprises audio data.

15. The method of claim 14, wherein the audio data is compressed according to one of the Moving Pictures Expert Group (MPEG) standards.

16. The method of claim 1, further comprising generating reentry information to identify the independently decodable pieces within the compressed data stream.

17. The method of claim 16, further comprising generating additional reentry information to identify pieces of compressed data that are not independently decodable.

18. The method of claim 1, wherein the data comprises image data received from a scanner, and the method further comprises rotating regions of the image data thereby requiring less than a full image buffer.

19. A method comprising:

receiving a compressed data stream;

decoding desired information from the compressed data stream;

manipulating the decoded information by rotating independent pieces of decoded data, each by the same amount;

encoding the rotated independent piece of data into independently decodable pieces of compressed data to produce a compressed data stream in an order that differs from the correct output order; and

sorting the independently decodable, rotated pieces of compressed data into the correct output order suited to the rotation.

20. The method of claim 19, further comprising processing the independently decodable pieces of compressed data in an order that is appropriate for producing reconstructed data associated with the compressed data stream.

21. The method of claim 19, further comprising transcoding the correctly ordered independently decodable pieces of compressed data into a new compressed data stream.

22. The method of claim 21, wherein the received compressed data stream does not include independently decodable pieces of compressed data.

23. The method of claim 19, wherein the rotated independently decodable pieces of compressed data can not be decoded by a traditional decoder, before sorting into the correct output order.

24. The method of claim 23, wherein sorting the compressed data comprises transcoding the out of order independently decodable pieces of compressed data into a new compressed data stream that is correctly ordered and decodable by a traditional decoder.

25. A method of rotating Joint Photographic Experts Group (JPEG) compressed data comprising:

receiving Joint Photographic Experts Group (JPEG) compressed data;

entropy decoding desired information from the JPEG compressed data;

performing rotation in the transform domain by transposing coefficients of minimum coded units (MCUs) in the decoded information and appropriately negating certain coefficients'"'"' signs of the MCUs; and

entropy encoding the rotated information into independently decodable pieces of compressed data to produce a compressed data stream in an order that differs from the correct output order; and

reordering the independently decodable pieces of compressed data into the correct output order, suited to the rotation.

26. The method of claim 25, wherein reordering the independently decodable pieces comprises selectively decoding the independently decodable pieces of compressed data in the correct output order.

27. A machine-readable medium having stored thereon data representing sequences of instructions, said sequences of instructions, when executed by a processor, causing said processor to:

receive data;

encode independently decodable pieces of the data to produce a compressed data stream in an input order;

rotate the independently decodable pieces of data, each by the same amount; and

reorder the rotated independently decodable pieces into an output order suited to the rotation.

28. The medium of claim 27, wherein:

said received compressed data stream comprises Joint Photographic Experts Group (JPEG) compressed data;

said decode desired information comprises entropy decode desired information from the JPEG compressed data;

said rotate the independently decodable pieces comprises perform rotation in the transform domain by transposing coefficients of minimum coded units (MCUs) in the decoded information and appropriately negating certain coefficients'"'"' signs of the MCUs; and

wherein said instructions further cause said processor to entropy encode the rotated information into independently decodable pieces of compressed data to produce a compressed data stream in an order that differs from the correct output order.

29. A method comprising:

receiving data;

encoding independently decodable pieces of the data to produce a compressed data stream in an order that differs from a correct output order, wherein the independently decodable pieces of data include one or more restart markers, wherein source data corresponding to the compressed data stream comprises image data, and wherein the image data is compressed according to one of the Joint Photographic Experts Group (JPEG) discrete cosine transform (DCT) based standards;

updating modulo counters embedded within the one or more restart markers to reflect the correct output order; and

reordering the independently decodable pieces into the correct output order.

30. The method of claim 29, wherein the data comprises intermediate data.

31. The method of claim 29, further comprising manipulating the data.

32. The method of claim 31, wherein said manipulating the data comprises rotating the data.

33. The method of claim 31, wherein said manipulating the data comprises mirroring the data.

34. The method of claim 31, wherein said manipulating the data comprises transposing the data.

35. The method of claim 31, wherein source data corresponding to the compressed data stream comprises audio data.

36. The method of claim 35, wherein the audio data is compressed according to one of the Moving Pictures Expert Group (MPEG) standards.

37. The method of claim 29, wherein the independently decodable pieces of data start at slice boundaries.

38. The method of claim 29, further comprising generating reentry information to identify the independently decodable pieces within the compressed data stream.

39. The method of claim 38, further comprising generating additional reentry information to identify pieces of compressed data that are not independently decodable.

40. The method of claim 29, wherein the data comprises image data received from a scanner, and the method further comprises rotating regions of the image data thereby requiring less than a full image buffer.

41. A method comprising:

receiving a compressed data stream, wherein source data corresponding to the compressed data stream comprises image data compressed according to one of the Joint Photographic Experts Group (JPEG) discrete cosine transform (DCT) based standards;

decoding desired information from the compressed data stream;

manipulating the decoded information; and

encoding the manipulated information into independently decodable pieces of compressed data to produce a compressed data stream in an order that differs from the correct output order, wherein the independently decodable pieces of data include one or more restart markers having embedded modulo counters to reflect the correct output order.

42. The method of claim 41, further comprising processing the independently decodable pieces of compressed data in an order that is appropriate for producing reconstructed data associated with the compressed data stream.

43. The method of claim 41, further comprising sorting the independently decodable pieces of compressed data into the correct output order.

44. The method of claim 41, further comprising transcoding the correctly ordered independently decodable pieces of compressed data into a new compressed data stream.

45. The method of claim 41, further comprising transcoding the out of order independently decodable pieces of compressed data into a new compressed data stream that is correctly ordered and decodable by a traditional decoder.

46. A machine-readable medium having stored thereon data representing sequences of instructions, said sequences of instructions which, when executed by a processor, cause said processor to:

receive data;

encode independently decodable pieces of the data to produce a compressed data stream in an order that differs from a correct output order, wherein the independently decodable pieces of data include one or more restart markers, wherein source data corresponding to the compressed data stream comprises image data, and wherein the image data is compressed according to one of the Joint Photographic Experts Group (JPEG) discrete cosine transform (DCT) based standards;

update modulo counters embedded within the one or more restart markers to reflect the correct output order; and

reorder the independently decodable pieces into the correct output order.

47. The medium of claim 46, wherein the sequences of instructions further cause said processor to rotate the data.

48. The medium of claim 46, wherein said sequences of instructions cause said processor to transpose the data.

49. The medium of claim 46, wherein source data corresponding to the compressed data stream comprises audio data.