Image analysis – Image compression or coding – Adaptive coding
Utility Patent
1996-08-05
2001-01-02
Couso, Jose L. (Department: 2721)
Image analysis
Image compression or coding
Adaptive coding
Utility Patent
active
06169820
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to processes for compressing data and to corresponding systems. The data to be compressed may here be analog or digital speech and image data, or may be any data provided by computers.
Data compression methods are used for eliminating or reducing redundancies in data streams that are to be transmitted or stored, whereby data streams can be stored with the required memory area being reduced, or whereby the streams can be transmitted with smaller bandwidths or at increased speeds.
Known compression methods which are presently employed for transmitting data on data or telephone lines are normally based on the so-called LZW (Lempel, Ziv, Welch) algorithm or the so-called Huffman algorithm, which is especially used in facsimile transmissions.
Simply speaking, the LZW algorithm is based on the measures that a transmission data stream is analyzed for the presence of elementary data groups contained therein and that a location is assigned to the determined data groups in a tree representing the individual data groups.
The determined data groups can then be transmitted—by corresponding agreement with the receiver side and instead of their Information content proper—by means of codes that represent their position within the tree, whereby good compression results become achievable, especially in the case of data streams with constantly recurring patterns.
Since the memory area which is required for learning elementary data groups that appear in the data stream is limited, i.e. the ramification of the tree cannot exceed a predetermined degree, the “built tree” must be renewed from time to time to adjust or adapt it to a changed structure of the transmission data as compared to the structure that existed during the learning process.
When a new “tree” is built, the learnt structural interrelationships, which might also be valid for the new data, are lost. Until the construction of a new tree the data will be compressed less efficiently, at least for some time, resulting in a reduction of the achievable compression factor on the whole.
Especially in synchronous systems, this reduced compression efficiency is disadvantageous because a transmission will only be possible within predetermined time slots. In contrast to asynchronous systems, a decrease in the achievable compression might thus lead to a superproportional increase in the time needed for transmission.
It is the object of the present invention to provide processes for efficiently compressing data as well as systems suited therefor.
This object is achieved in an inventive manner through the subject matters of patent claims
1
,
5
,
20
, and
23
.
Preferred embodiments are outlined in the subclaims.
SUMMARY OF THE INVENTION
One aspect of the present invention is based on the finding that compression methods which have so far been employed do not work efficiently for the reason that they just determine predominantly short-time variations in the data streams by means of the used compression algorithms and take these variations into account for the compression. For instance, when an LZW algorithm is used in a synchronous environment, it is just the variations within a data block (frame) that are normally taken into account for compression. Basic repetitions and structures within a specific type of data are thus not sufficiently taken into account for compression.
The compression process is therefore performed in two stages in accordance with the above-mentioned first aspect of the present invention:
a first stage in which the structures, interrelationships or patterns which have been learnt over a long period of time and which arise within a specific type of data are taken into account for the compression of an instantaneous data stream; and
a second stage in which short-time variations of the compression data stream are taken into account, as is e.g. the case with the above-mentioned LZW algorithm.
The said process is especially advantageous for the reason that the compression operation in the second stage which, as mentioned, can be implemented by conventional compression methods is improved as to its efficiency because it receives precompressed data as input data that consist of data groups having small input lengths, with respect to which the LZW algorithm, for example, can operate more efficiently, i.e. closer to its theoretically achievable optimum compression capacities.
Frequency distributions of elementary data groups within the compression data stream, as have been determined for the corresponding type of data over a long period of time, are preferably taken Into account for compression purposes within the first stage, i.e. precompression. The thus determined elementary data groups which constantly recur even over long periods of time, for example specific speech patterns, specific combinations of numbers, or specific image sections, are preferably arranged in the order of their frequency so that the most frequently occurring data groups are represented by correspondingly short codes and less frequently occurring data groups, which have nevertheless been data groups taken into account in the precompression stage, are represented by correspondingly longer codes.
Another aspect of the present invention according to patent claim
1
regards a compression process which can be performed in a single stage and is based on the measure that elementary data groups which are frequently repetitive over a longer period of time are “learnt” for a compression data stream and stored in a storage device. The instantaneous compression data stream is analyzed for the presence of said learnt elementary data groups and correspondingly learnt data groups are subsequently replaced by codes which represent the position of the learnt data groups within the storage device or within a table. As a consequence, the data stream compressed in this manner can again be decompressed when being read out from a memory, or at the receiver side, by looking it up in the table.
The codes as used preferably correspond to the addresses of the learnt and replaced data groups within the table, the address agreement being possibly also such that only address differences between two successive replaced data groups are used for coding.
The process according to claim
1
can preferably be combined again with a second compression stage, in accordance with the first aspect of the present invention.
Other aspects of the present invention regard data compression devices or transmission devices which achieve a data compression in accordance with the above process.
Preferred embodiments of the present invention are now explained in detail with reference to the enclosed drawing.
REFERENCES:
patent: 4813056 (1989-03-01), Fedele
patent: 4839724 (1989-06-01), Keesen et al.
patent: 5138673 (1992-08-01), Yoshida et al.
patent: 5319724 (1994-06-01), Blonstein et al.
patent: 5379355 (1995-01-01), Allen
patent: 5432870 (1995-07-01), Schwartz
patent: 5532694 (1996-07-01), Mayers et al.
patent: 5539842 (1996-07-01), Schwartz
patent: 5615287 (1997-03-01), Fu et al.
patent: 5717787 (1998-02-01), Feo et al.
patent: 5892847 (1999-04-01), Johnson
patent: 0582907 (1994-02-01), None
Sutsch Arthur G.
Wade Michael R.
Couso Jose L.
Majestic, Parsons, Siebert & Hsue P.C.
TECOMAC AG
LandOfFree
Data compression process and system for compressing data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression process and system for compressing data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression process and system for compressing data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2523065