Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-05-25
2004-05-25
Lee, Thomas D. (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S426010, C382S232000, C382S239000
Reexamination Certificate
active
06741368
ABSTRACT:
BACKGROUND
The present invention relates generally to the storage of data in a device, and more particularly to a method and apparatus for reducing memory storage requirements in an output display device.
A computer system can output data to a wide variety of output display devices. Output display devices such as laser printers, plotters, and other printing devices produce an image or “visual representation” onto a sheet of paper or the like, while output display devices such as computer monitors develop visual representations on a computer screen.
Many output display devices receive display data in the form of a “bitmap” or “pixel map” and generate visual representations from the display data. A pixel is a fundamental picture element of a visual representation generated by a display device, and a bitmap is a data structure including information concerning a number of pixels of the representation. Bitmaps that contain more than on/off information are often referred to as “pixel maps.” As used herein, both bitmaps and pixel maps are referred to as “bitmaps.”
A printer can print dots on a piece of paper corresponding to the information of a bitmap. Alternatively, a computer monitor can illuminate pixels based upon the information of the bitmap. A “raster” output device creates a visual representation by displaying the array of pixels arranged in rows and columns from the bitmap. Many output devices are raster output devices. Typically, a “page” of pixels corresponding to a printed or displayed page is received and stored in memory before the pixels are displayed by the output display device.
A visual representation can contain a number of image types, including text, graphics, photographic images, and so on. Data of these types can be efficiently stored in files with other image information as high level “objects.” An “object,” as referred to herein, is the data and attributes defining a particular visual representation. The objects can be edited or otherwise manipulated using an application program (“software”) running on a computer. When displaying the objects with an output display device such as a printer or display screen, the objects are typically first rasterized (or “rendered”) into bitmaps. The output display device stores display bitmap data in memory before displaying a page of data.
A problem in the prior art methods of providing bitmaps to output display devices is that a large amount of storage space is required to store the bitmap before it is displayed. Storage space requirements have increased as the demand for high-resolution representations with more realistic attributes has become more prominent. For example, using a laser printer capable of printing black-and-white bitmaps at a resolution of 600 dots per inch (dpi), a typical displayed page (8.5×11 inches) requires about 3.8×10
6
bytes of memory. When printing a page of color pixels, for example, having 4 colors per pixel and 8 bits per color, the memory requirement increases to about 121×10
6
bytes of memory. With such memory requirements, a significant portion of the cost of manufacturing an output display device capable of processing one or more pages such as a laser printer is the cost of the required memory.
A method that has been used to reduce the memory requirements for displaying high-resolution images involves the compression of the bitmap data according to a compression method or algorithm. A compression algorithm can significantly reduce the space needed to store bitmaps by removing redundancy. Some compression algorithms are “lossless,” meaning that they compress data and reduce storage requirements with no loss of information. This type of compression is often used with text objects and the like, since bitmaps of text objects typically contain considerable redundancy allowing for significant compression. Lossless compression techniques are ideal for text objects because any loss of information during the compression and subsequent decompression processes would adversely affect appearance and legibility of the text. Other types of compression algorithms are “lossy,” meaning that they compress data with some loss of information. These types of compression algorithms are typically used with image bitmap data, photographs and the like, since the loss of information can often be unnoticeable in a high resolution image.
When the compressed bitmap is to be displayed, it is decompressed using a corresponding decompression algorithm and sent to a print engine, monitor, or other output display device.
SUMMARY
The present invention provides a method and apparatus for compressing a two-dimensional image. A method of compressing a two-dimensional image represented as a raster of pixels. The method includes receiving a sequence of the pixels in raster order; and defining a first match pixel location and a second match pixel location relative to a current pixel location in the raster, a first match pixel being the pixel at the first match pixel location relative to the current pixel, a second match pixel being the pixel at the second match pixel location relative to the current pixel, where the first pixel location and the second pixel location are not contiguous in the sequence. Each pixel in the sequence is considered in turn as the current pixel. The method then includes comparing the current pixel only to the first match pixel and the second match pixel and then encoding the value of the current pixel if the value of the current pixel does not match the value of the first match pixel or the value of the second match; and otherwise if the value of the current pixel matches the value of the first match pixel then encoding the current pixel as a first token where the first token includes a reference to the first match pixel and a length and where the length is determined based on a number of consecutive pixels relative to the current pixel whose values match the values of similarly located pixels relative to the first match pixel; or if the value of the current pixel matches the value of the second match pixel then encoding the current pixel as a second token where the second token includes a reference to the second match pixel and a length and where the length is determined based on a number of consecutive pixels relative to the current pixel whose values match the values of similarly located pixels relative to the second match pixel.
Aspects of the invention can include one or more of the following features. The previous pixel can be the pixel immediately previous in the current scan line or a last pixel in an immediately previous scan line if the current pixel is the first pixel in the current scan line. The located pixel can be positioned in an immediately previous scan line above the current scan line and directly above the current pixel or positioned adjacent to a pixel in the immediately previous scan line and above the current pixel.
The length can be unbounded.
The method can include encoding the length including storing a code and a value. The code can be representative of a range of length values that are encoded and the value indicative of an exact length value within the range. The method can include gathering statistical data during the compression process and re-encoding the image. Tokens can be classified into groups and statistical data can be gathered on how often each token group type is used.
The method can include gathering statistical data for a number of encoded tokens having lengths falling within each of a number of predetermined ranges of lengths.
The pixel value can be encoded as a literal if the pixel value does not match the previous or located pixel value. The encoding of a literal can include encoding the value of the current pixel in accordance with a predefined mathematical algorithm operating on the value of the current pixel value. The mathematical algorithm can include determining a distance between the current pixel value and a value of a pixel immediately preceding the current pixel in the current scan line and encoding the distance.
In another aspec
Adobe Systems Incorporated
Fish & Richardson P.C.
Lee Thomas D.
LandOfFree
Method and apparatus for reducing storage requirements for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reducing storage requirements for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing storage requirements for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3215426