Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-08-14
2004-08-31
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Lossless compression
C382S239000, C358S001150
Reexamination Certificate
active
06785424
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an encoding method for compressing a data structure having two or more dimensions, as in the case of image data, a decoding method for decoding the data that has been encoded, apparatus for executing these methods, and a computer-readable storage medium storing programs for executing these methods by computer.
BACKGROUND OF THE INVENTION
An example of a method of compressing image data available in the art is one which uses run-length encoding. If the same data repeats itself, run-length encoding is used to encode the repeating lengths and data. By writing software efficiently, encoding can be performed at a fairly high speed.
Another example of an available method is one which uses delta row coding. If one line of data is followed directly by an identical line of data, delta low coding encodes the length of the succeeding line.
Yet another method which can be used is Huffman coding. This method of encoding investigates the distribution of data and encodes data having a high frequency of occurrence into short codes.
However, with the method that relies upon run-length encoding, even if there is correlation in both the horizontal and vertical directions, as in the case of image data, only correlation in the horizontal direction contributes to compression. If there is correlation only in the vertical direction, there is no contribution to compression. As a consequence, it is difficult to achieve a high compression rate overall with this method.
Delta row coding is capable of performing encoding at high speed by use of software. However, even if there is correlation in both the horizontal and vertical directions, as in the case of image data, only correlation in the vertical direction contributes to compression. If there is correlation only in the horizontal direction, there is no contribution to compression and it is difficult to achieve a high compression rate.
With Huffman coding, even if there is correlation in both the horizontal and vertical directions, as in the case of image data, correlation in neither direction contributes to compression and, hence, it is difficult to achieve a high compression rate.
Various other encoding methods such as LZ77, LZ78 and JBIG encoding have been proposed. With these methods, however, it is necessary to investigate data other than data immediately to the left and data immediately above, where the horizontal and vertical correlations are most conspicuous. As a result, encoding requires a large amount of calculation. In a case where encoding is performed by software, the encoding takes considerable time. In instances where decoding is performed by hardware, a decoder of large scale is required.
Further, in a conventional printing system, the printer driver program of a host computer creates bitmap data, which allows the printer to perform printing, based upon a print instruction issued from an application program, encodes (compresses) the bitmap data by an encoding procedure of the kind described above, and outputs the encoded bitmap data, together with control data necessary for printing control, to the printer as print data. The printer, which does not have enough memory for one page, controls printing on the basis of the control data in the print data received from the host computer, decodes (expands) the encoded bitmap data and prints the results on printing paper.
The conventional printing system, which generates bitmap data in the host computer and transmits the bitmap data to the printer, is such that the host computer and the printer are connected by a local interface. Transfer time needed to transfer data from the host computer to the printer is fixed. As a result, even though the printer memory does not have enough capacity for one page, and even though print processing is executed starting from print data received previously, reception of print data that follows this page can be processed in time for ejection of the printing paper. This makes it possible to prevent overrun error.
With modern networks, one printer can be shared by a plurality of host computers. Accordingly, in a case where PDL (Page Description Language) is generated in a host computer and is expanded and printed by the printer, overrun error will not occur regardless of how long transfer time is in the network. However, if bitmap data is generated in the host computer and bitmap print data (which does not contain PDL) is subjected to print processing by the printer, print processing is started before reception of one page of print data ends. If data transfer takes too much time, therefore, there is the possibility that overrun error will occur. For this reason, a printer which relies upon data expansion by the host computer is not used by being connected directly to the network.
Accordingly, it has been contemplated to encode bitmap data in order to hold data transfer time below a fixed value. However, print instructions issued from an application are of a variety of types, and the encoding rate (decompression rate) differs depending upon the type of document, as in a case where a document contains much text or a case where a document contains many images. If a code expression suited to text is used, therefore, almost no compression can be performed in case of a document containing many images, a great deal of time is required to transfer the print data and overrun error occurs. Similarly, encoding suited to an image is not appropriate for a document containing a large quantity of text.
Accordingly, consideration has been given to having a printer driver support a plurality of code expressions, analyze the print instruction issued from the application and select the suitable code expression. If this is done, however, a plurality of code expressions must be supported. This means high cost in case of support by hardware and slow processing and reduced throughput in case of support by software. Further, when a print instruction issued from an application is analyzed one time, throughput declines by an amount approximately equivalent to a code representation of two passes.
An object of the present invention, therefore, is to provide a single-pass code expression suited to the encoding of bitmap data created by a host computer in a printing system in which a host computer and a printer communicate via a network.
SUMMARY OF THE INVENTION
The present invention has been proposed to solve the problems of the prior art and an object thereof is to provide an encoding method and apparatus, a decoding method and apparatus and a storage medium therefor, wherein a high compression rate is obtained by utilizing correlations in both the horizontal and vertical directions to encode a data structure having two or more dimensions, as in the case of image data, and wherein the amount of computation can be reduced by investigating only data immediately to the left and data immediately above, where the horizontal and vertical correlations are most conspicuous, thereby shortening the required encoding time when encoding is performed by software.
Another object of the present invention is to raise encoding efficiency by encoding at least two of three types of operations used when correlations in both the horizontal and vertical directions are utilized, namely repeating, copying and raw-data substitution operations, simultaneously (i.e., by encoding a combination of any two of these).
According to the present invention, the foregoing objects are attained by providing a decoding method and apparatus, an encoding method and apparatus and a storage medium for executing these methods by computer, the characterizing features of which are as described below.
Specifically, a decoding method according to the present invention comprises the steps of: determining, based upon a received code sequence, to which of repetition, copying and raw-data the code sequence applies; decoding the code sequence, in accordance with the determination, by a combination of at least two conversion operations from among repetition, copying and raw-data substituti
LandOfFree
Encoding method and apparatus for compressing a 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 Encoding method and apparatus for compressing a data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding method and apparatus for compressing a data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3311956