Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
1999-03-24
2001-06-12
Boudreau, Leo (Department: 2721)
Image analysis
Image compression or coding
Lossless compression
C382S202000, C382S233000, C358S296000, C345S017000
Reexamination Certificate
active
06246800
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to loss-less compression and decompression of bitmaps, and in particular to a method of compressing a bitmap of a symbol, a compressed bitmap of a symbol, a method of decompressing a compressed bitmap, and a computer for decompressing a compressed bitmap.
BACKGROUND OF THE INVENTION
It is known to compress bitmaps, for example using run-length and outline techniques, so that less space is required to store them and so that less time is required to transmit them at a particular transmission rate. However, compression and decompression take time and processing power. For example, the world-wide-web has generated a need to have a range of large banner fonts. These can be stored and transmitted as outlines, which are compact, but a significant amount of processing power is required to render or decompress them from this form.
SUMMARY OF THE INVENTION
The present invention is concerned with providing high compression ratios of bitmaps, and with providing fast decompression. The invention is more particularly, but not exclusively, concerned with a compression/decompression scheme which enables compressed symbol files to be decompressed with simple or cheap processors and dedicated hardware, thus making the invention particularly useful for world-wide-web/internet browsers or viewers.
In accordance with a first aspect of the present invention, there is provided a method of compressing a bitmap of a symbol, in which the symbol is considered as being made up of a plurality of strokes, and each stroke is considered as being made up of a plurality of continuous lines, and comprising the steps of: run-length encoding each stroke to form a stream of line codes for that stroke; and presenting the streams of the lines codes for the strokes in sequence as a set.
It will therefore be appreciated that the invention provides a development of run-length encoding. However, the separation of the symbol into a plurality of strokes removes the need to encode the white space between those strokes, as it can be inferred to be background. By contrast, with simple run-length encoding, such white space tends to produce long variable-length runs which do not compress well.
In one example of the method, the step of run-length encoding each stroke comprises the steps of: encoding each line or group of lines of that stroke by one of a plurality of encoding methods to form a line code; and presenting the line codes as a stream in the order in which the lines appear in that stroke, at least some of the lines each being encoded in dependence upon their position and length relative to the preceding line in that stroke.
At least one of the encoding methods may produce such a line code comprising: a control code indicative of that encoding method; and at least one parameter value for that control code. Various of these encoding methods may comprise the step of providing, as such parameter values:
(a) a two-dimensional position of one end of the respective line; and the length of that line; or
(b) a two-dimensional position of one end of the respective line; and a one-dimensional position of the other end of that line; or
(c) an offset between one end of the respective line and one end of the preceding line; and a difference between the length of the respective line and that of the preceding line; or
(d) an offset between one end of the respective line and one end of the preceding line; and an offset between the other end of the respective line and the other end of the preceding line; or
(e) a number of repeats of the previous line; or
(f) a number of lines; and for each line in that number an indication of whether or not each end of that line is offset by one pixel in the line direction from the corresponding end of the preceding line (in this case, the encoding method may further include the step of providing, as such a parameter value: an indication of whether the offset (if any) of one end of each of the respective lines is in one direction or in the opposite direction).
At least one of the encoding methods may produce, as such a line code, a parameterless control code. For example, at least some of the parameterless control codes may each be:
(g) a predetermined function of: an offset between one end of the respective line and one end of the preceding line; and a difference between the length of the respective line and that of the preceding line; or
(h) a predetermined function of: an offset between one end of the respective line and one end of the preceding line; and an offset between the other end of the respective line and the other end of the preceding line.
By suitable choice of these methods, specific features of symbols (or parts of them) can be taken into account to produce a compression ratio which is perhaps more than twice that which is achievable using simple run-length encoding. Many symbols have a high degree of correlation between vertically adjacent horizontal pixel rows, and this can be taken advantage of, particularly by methods (c) to (h), to produce high compression ratios.
At least some of these encoding methods may be paired. For example:
(i) in the case of a pair of methods (c) above, the maximum offset and/or difference for one of those two methods may be different to that or those for the other of those two methods; or
(j) in the case of a pair of methods (d) above, the or each maximum offset for one of those two methods may be different to that or those for the other of those two methods; or
(k) in the case of a pair of methods (e) above, the maximum number of repeats for one of those two methods may be different to that for the other of those two methods.
It will therefore be appreciated that, by choosing the method with the smaller maximum, if that is possible, to encode a particular line or group of lines, fewer bits are produced. Preferably the method further comprises the step of adding a header indicative of the number of streams in the set and the length of each stream.
In accordance with a second aspect of the present invention, there is provided a compressed bitmap of a symbol, produced by the method of the first aspect of the invention.
In accordance with a third aspect of the present invention, there is provided a compressed bitmap of a symbol which is considered as being made up of a plurality of strokes each of which is considered as being made up of a plurality of continuous lines, the compressed bitmap comprising: for each of the strokes, a plurality of run-length encoded line codes each for one of the lines or a group of the lines in that stroke, the line codes being arranged as a stream in the order in which the lines appear in that stroke, and the streams of the lines codes for the strokes being arranged in sequence as a set. Preferably, the lines codes are encoded by a plug of encoding methods, at least some of the lines each being encoded in dependence upon their position and length relative to the preceding line in that stroke.
In accordance with a fourth aspect of the present invention, there is provided a method of decompressing a compressed bitmap according to the second or third aspect of the invention, and comprising the steps of: decoding each line code to form a respective line definition; and rendering the line defined by each line definition. Preferably, decoding of at least two of the streams of line codes temporally overlap each other. In the case of decoding a parametered line code as mentioned above, the decoding step may comprise the steps of determining the control code in the parametered line code, determining the or each parameter of that line code, and forming the line definition in accordance with the value of the control code and the value of the or each parameter. In the case of decoding a parameterless line code as mentioned above, the decoding step may comprise the step of forming the line definition in accordance the value of the control code.
In accordance with a fifth aspect of the present invention, there is provided a computer which is programmed by software to perform the method a
Boudreau Leo
Hewlett--Packard Company
Sherali Ishrat
LandOfFree
Loss-less compression and decompression of bitmaps using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Loss-less compression and decompression of bitmaps using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Loss-less compression and decompression of bitmaps using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2513661