Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
1997-10-03
2001-10-16
Lee, Cheukfan (Department: 2722)
Image analysis
Image compression or coding
Lossless compression
C382S244000
Reexamination Certificate
active
06304676
ABSTRACT:
BACKGROUND
This disclosure includes a microfiche appendix. The microfiche appendix includes a total number of 2 fiche and a total number of 104 frames.
COPYRIGHT AUTHORIZATION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by any one of the patent disclosure, as it appears in the U.S. Pat. and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The field of the present invention relates in general to a apparatus and method for data processing. More particularly, the field of the invention relates to an apparatus and method for compression and decompression of data for transmission or storage.
2. Background
A wide variety of methods exist for compressing and decompressing data. Such data generally comprise primitives called characters which represent specific data values. The finite set of primitives constitutes a character set which may also be referred to as an alphabet. For instance, in the ASCII character set, the primitive character “01000110” represents the letter “F”. A string is a sequence of characters within a given character set. A string may be compressed by identifying substrings or characters that appear repetitively. These repetitive substrings or characters may then be replaced with codes based on the frequency of their occurrence within the string. The substrings and characters with the highest frequency may be assigned the shortest codes. A code table (which may take the form of a table, tree, linked list or other data structure) containing the compression codes and the corresponding uncompressed characters and substrings may be stored or sent with the compressed string to allow decompression.
One common method for general purpose data compression is the Huffinan method. The Huffman method involves mapping fixed length substrings into variable length codes based on the frequency of their occurrence. The code table may take the form of a tree, where the codes can be used to traverse the tree and the characters corresponding to the codes are located in leaves of the tree. The characters with the highest frequency and shortest codes are located in higher levels of the tree. However, when a large number of nodes are included within the tree, the overhead required for traversing the tree grows correspondingly.
While a wide variety of compression/decompression methods have been developed, a need exists for improved methods. For instance, increasingly higher rates of compression and faster decompression are desirable for use with the World Wide Web. The large amount of data stored on servers and the low transmission rates for many clients makes it desirable to optimally compress data for storage and transmission. In addition, it is important that the data be decompressed quickly by the client computer to allow immediate viewing or use by the end user, It should be noted that, since most data is compressed and stored on network servers in advance, slower compression techniques with higher compression rates may be used. Such techniques, however, should allow for fast decompression as described above.
SUMMARY OF THE INVENTION
Aspects of the present invention use a competitive process to create an optimized set of variable length bit codes to encode one, two or three dimensional data and a high speed redundant lookup table for decoding the resulting representation in real time.
One aspect of the present invention provides an improved apparatus and method for compressing strings for storage or transmission. In one exemplary embodiment, a computer program executing on a general purpose computer may be used to compress an incoming string. The computer program makes multiple passes through the unencoded string to determine an overall best code set for the given string. The computer program may use multiple coding techniques to analyze the string. During the first pass, the computer program simply enumerates all possible encodings of the data by the coding primitives implemented and creates a Huffinan encoding for the set as if each code were actually used at each possible location. For instance, one set of codes may be assigned based on the frequency of each character in the string. A second set of codes may be assigned based on the number of times that characters or substrings are repeated at certain offsets within the string (e.g. the number of times that the current character or substring is the same as a character or substring that is located previously in the string at a particular offset). Subsequent passes make trial encodings of the data using the shortest codes available from the various code sets and count the number of times each code was actually used, then recalculate the Huffman codes for the relative actual frequencies of the codes used (discarding codes from the code sets that are not used). The trial encoding and recalculation continues until specific criteria are met or the data is not further compressed. A final pass compresses the data using the best code set found and writes it to the output as either a disk file or an evanescent transmission.
Another aspect of the present invention provides an improved apparatus and method for decompressing compressed strings. In one exemplary embodiment, a computer program executing on a general purpose computer processes the code set generated by the encoding phase and builds one or more redundant lookup tables, where each code's entry occurs a sufficient number of times to guarantee that a single lookup using the next n bits of the encoded data stream as index will correctly decode the next code in the stream. This table is then used to interpret the codes in the data stream and exactly reproduce the original data.
The primitives used to encode the data may be any mix of operations that captures the redundancy of the raw data. For graphic applications, specific colors and patterns copied from previously occurring data yield sufficiently high compression ratios, but any likely candidates for high frequency occurrence may be added to the mix. The encoding algorithm will ignore any non-optimal operations and assign them no space in the code set.
REFERENCES:
patent: 4814746 (1989-03-01), Miller et al.
patent: 4899148 (1990-02-01), Sato et al.
patent: 5049881 (1991-09-01), Gibson et al.
patent: 5825830 (1998-10-01), Kopf
patent: 5848195 (1998-12-01), Romriell
Lee Cheukfan
Wilson Sonsini Goodrich & Rosati
LandOfFree
Apparatus and method for successively refined competitive... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for successively refined competitive..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for successively refined competitive... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2612859