Data compression/decompression apparatus and method

• US 8,004,429 B2
• Filed: 09/02/2008
• Issued: 08/23/2011
• Est. Priority Date: 09/07/2007
• Status: Expired due to Fees

• Current Assignee: QURAM Co., Ltd., Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Oh, Sung Jo, Wee, Young Chul
• Primary Examiner(s): JEANGLAUDE, JEAN BRUNER
• Application Number:
  US12/203,114
• Publication Number:
  US 20090070543A1
• Time in Patent Office: 1,085 Days
• Field of Search: 341/50, 341/51, 375/240.16, 345/603, 348/699
• US Class Current: 341/50
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H04N 19/11 among a plurality of spatial predictive coding modes
• CPC Class Codes: H04N 19/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

A data compression/decompression apparatus and method are provided for improving memory utilization. The data compression/decompression apparatus includes a compressor for calculating costs of domain blocks to a range block through forward searching in a search range, for selecting the domain block having the lowest cost to the range block as a reference domain block through backward searching, for generating distance and difference information of the reference domain block, and for encoding the distance and difference information into compressed data of the range block. The data compression/decompression apparatus also includes a decompressor for finding the reference domain block on the basis of the distance and for decoding the compressed data into original data of the range block with reference to the difference information.

Claims

1. A data compression/decompression apparatus, the apparatus comprising:

a compressor for calculating costs of domain blocks to a range block through forward searching in a search range, for selecting the domain block having the lowest cost to the range block as a reference domain block through backward searching, for generating distance and difference information of the reference domain block, and for encoding the distance and difference information into compressed data of the range block; and

a decompressor for finding the reference domain block on the basis of the distance and for decoding the compressed data into original data of the range block with reference to the difference information.

2. The apparatus of claim 1, wherein the compressor comprises:

a searcher for calculating the costs of the domain blocks to the range block through a forward searching in a search range, for selecting the domain block having the lowest cost to the range block as the reference domain block through a backward searching, for generating distance and difference information of the reference domain block, the range block containing data to be compressed; and

a coder for encoding the distance and difference information into the compressed data of the range block.

3. The apparatus of claim 2, wherein the distance information comprises a distance flag and a distance value indicating a number of blocks between the range block and the reference domain block, and the difference information comprises a difference flag and a difference value indicating a difference between the range block and the reference domain block.

4. The apparatus of claim 3, wherein the compressor calculates the difference value by performing an exclusive OR operation on the data of the range block and the reference domain block, and the decompressor recovers the data of the range block by performing exclusive OR operation on the difference value and the data of the reference domain block.

5. The apparatus of claim 4, further comprising a global table for storing difference values between domain blocks and range blocks, wherein the compressor registers the difference values between the range blocks and the domain blocks as indexes of the global table and reads out one of the indexes as the difference value of the difference information, and the decompressor reads out the difference value matched with the index of the global table and recovers the data of the range block by performing the exclusive OR operation on the difference value and the data of the reference domain block.

6. The apparatus of claim 5, wherein the compressor generates, when an index of the global table fails to be created, an exception flag and encodes the exception flag and the data of the range block into the compressed data of the range block, and the decompressor decodes, when detecting the exception flag in the difference information, the data contained in the difference information into the data of the range block.

7. The apparatus of claim 6, wherein the difference values stored in the global table comprise values obtained by performing an exclusive OR operation on the range blocks and domain blocks.

8. The apparatus of claim 6, further comprising an exception handler, wherein, when the exception flag is generated, the exception handler stores the data of the range block without encoding.

9. The apparatus of claim 3, further comprising a global table for storing difference values between the domain blocks and range blocks and a local table for storing difference values that do not exist in the global table but occur during a compression process, wherein the compressor registers the difference value between the range block and the reference domain block to at least one of the global and local table as an index, reads out the index as the difference value of the difference information, registers the difference value which does not exist in the global and local tables to the local table and further wherein the decompressor reads out the difference value matched with the index of the global table and recovers the data of the range block by performing an exclusive or operation on the difference value and the data of the reference domain block.

10. The apparatus of claim 9, wherein the compressor generates, when an index of the table fails to be created, an exception flag and encodes the exception flag and the data of the range block into the compressed data of the range block, and the decompressor decodes, when detecting the exception flag in the difference information, the data contained in the difference information into the data of the range block.

11. The apparatus of claim 10, wherein the difference values stored in the global and local tables are obtained by performing an exclusive OR operation on the range blocks and domain blocks.

12. A data compression/decompression method, the method comprising:

compressing data by calculating costs of domain blocks to a range block through forward searching in a search range, selecting the domain block having the lowest cost to the range block as a reference domain block through backward searching, generating distance and difference information of the reference domain block, and encoding the distance and difference information into compressed data of the range block; and

decompressing the compressed data by finding the reference domain block on the basis of the distance and decoding the compressed data into original data of the range block with reference to the difference information.

13. The method of claim 12, wherein the compressed data comprises the distance information including a distance value indicating a number of blocks between the range block and the reference domain block and the difference information including a difference value indicating difference between the range block and the reference domain block.

14. The method of claim 13, wherein the compressing of the data comprises registering the difference values between the range blocks and the domain blocks as indexes of a global table and reading out one of the indexes as the difference value of the difference information, and further wherein the decompressing of the compressed data comprises reading out the difference value matched with the index of the global table and recovering the data of the range block by performing the exclusive OR operation on the difference value and the data of the reference domain block.

15. The method of claim 14, wherein the compressing of the data comprises generating, when an index of the global table fails to be created, an exception flag and encoding the exception flag and the data of the range block into the compressed data of the range block, and further wherein the decompressing of the compressed data comprises decoding, when detecting the exception flag in the difference information, the data contained in the difference information into the data of the range block.

16. The method of claim 15, wherein the difference values stored in the global and local tables are obtained by performing an exclusive OR operation on the range blocks and domain blocks.

17. The method of claim 15, further comprising storing the data of the range block without encoding.

18. The method of claim 13, wherein the compressing of the data comprises registering the difference value between the range block and the reference domain block to at least one of a global and a local table as an index, reading out the index as the difference value of the difference information, registering the difference value which does not exist in the global and local tables to the local table and further wherein the decompressing of the compressed data comprises reading out the difference value matched with the index of the global table and recovering the data of the range block by performing an exclusive OR operation on the difference value and the data of the reference domain block, the global table storing difference values between the domain blocks and range blocks and the local table storing difference values that do not exist in the global table but occur during compression process.

19. The method of claim 18, wherein the compressing of the data comprises generating, when an index of the table fails to be created, an exception flag and encoding the exception flag and the data of the range block into the compressed data of the range block, and further wherein the decompressing of the compressed data comprises decoding, when detecting the exception flag in the difference information, the data contained in the difference information into the data of the range block.

20. The method of claim 19, wherein the difference values stored in the global and local tables are obtained by performing an exclusive OR operation on the range blocks and domain blocks.

21. A data processing apparatus of a mobile terminal, the apparatus comprising:

a memory;

a compressor for calculating costs of domain blocks to a range block through forward searching in a search range, for selecting the domain block having the lowest cost to the range block as a reference domain block through backward searching, for generating distance and difference information of the reference domain block, and for encoding the distance and difference information into compressed data of the range block;

a decompressor for finding the reference domain block on the basis of the distance and for decoding the compressed data into original data of the range block with reference to the difference information; and

a controller for storing, in a writing mode, the compressed data output by the compressor within the memory and for reading out, in a reading mode, the compressed data to the decompressor.