Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1998-12-24
2001-03-13
Rogers, Scott (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S001160, C358S451000, C358S426010, C382S237000, C382S244000, C382S270000
Reexamination Certificate
active
06201614
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The invention relates to the compression of digital image data in a computer environment. More particularly, the invention relates to the compression of digital image data during the dithering process in a computer environment.
2. Description of the Prior Art
Digital image rendering involves comparing an array of pixel values of a source image and a threshold array to generate a new array of pixels values, called the dithered image. The pixels in the dithered image usually has less information (bits per pixel) than the pixels in the source image.
The source image must go through several stages such as storage and halftoning before printing. The source image is normally compressed before it is stored on a computer system. This is because the raw data requires a large amount of memory. For example, an 8.5″×11″ letter-sized, full color image normally takes approximately 64 MB to 70 MB of memory (on the hard disk or RAM), uncompressed. Image data are lost during the compression stages whenever a lossy compression technique, e.g., Joint Photographic Experts Group (JPEG), is used to compress the source image.
Many printing devices are not capable of reproducing gray scale images because they are bi-level. As a result, the binary representation of a gray scale image is a necessity in a wide range of applications such as laser printers, facsimile machines, lithography, liquid crystal displays, and plasma panels. Gray scale and color images are typically converted to binary images using halftone techniques. A typical example is halftoning, or dithering, an eight-bit/pixel source image to generate a one bit/pixel “bitmap” for laser printer output.
Halftone generally refers to the process of generating continuous variations of intensity on a printed page using arrays of discrete pixels whose intensity is binary. Halftoning renders the illusion of various shades of gray by using binary levels, black and white, and can be implemented either digitally (laser printers) or optically (newspaper printing).
After an image goes through the halftone process, the halftone image is compressed for storage on the computer system because of memory demands. Compressing a halftone image is usually a challenging task because the pixel values in the dithered image may appear random to a software program and a high compression ratio can be difficult to achieve.
In addition, the threshold array process is considered the major contributor to the loss of information as well as adding noise which makes compression difficult.
Halftoning, or dithering, techniques using dither matrices are described in U.S. Pat. No. 4,760,460 issued to Shimotohno on Jul. 26, 1988, which teaches a method for transmitting a halftone image using a dithering method which divides an image into a plurality of regions corresponding to the dither matrix used. Average density values are calculated to determine addresses for encoding, compression, and transmission.
Typical halftoning techniques such as using blue noise masks are described in U.S. Pat. Nos. 5,708,518 and 5,323,247 issued to Parker et al on Jan. 13, 1998, which teaches a method and system for rendering a halftone image of a gray scale image by utilizing a pixel-by-pixel comparison of the gray scale image against a blue noise mask.
Methods for compressing computer images are described in several publications. U.S. Pat. No. 5,542,031 issued to Douglass et al on Jul. 30, 1996, describes a method for processing computerized data in Postscript format through an interpreter and rasterizer utilizing parallel processing.
U.S. Pat. No. 5,522,898 issued to Deschuytere on Sep. 3, 1996, describes a method using lossy and lossless compression in a raster image processor which generates a compressed bitmap, bitmask, and contone map of an image and reconstructing said image on the fly using said bitmap, bitmask, and contone map.
U.S. Pat. No. 5,359,430 issued to Zhang on Oct. 25, 1994, describes a method for converting continuous-tone images into a first and second halftone image and error image. Scattered pixels in said error image are removed and said error image is compressed and sent to a receiver which reverses the process of creating said error image.
U.S. Pat. No. 5,457,772 issued to Shannon on Oct. 10, 1995, and U.S. Pat. No. 5,548,689 issued to Poppenga et al on Aug. 20, 1996, teach a method for converting source color image data to a rasterized monochrome bit map which involves a conversion cycle for converting source pixels to gray scale values.
However, these methods do not address the problem of image data loss during the storage and halftoning processes.
It would be advantageous to provide a dithered image compression system that limits the amount of image data lost during the storage and halftone processes, yet preserves the visual appearance of the original source image result, thus creating a more efficient image file. It would further be advantageous to provide a dithered image compression system that takes advantage of knowing the amount of data lost during the storage and halftone stages, thereby giving the user the ability to adjust to the desired image quality and compression ratio.
SUMMARY OF THE INVENTION
The invention provides a dithered image compression system. The invention converts a source image into an image that is efficiently compressed and yet preserves the visual image information of the original source image. In addition, the invention provides a system that saves time and memory space on the storage system by eliminating the intermediate compression and halftone stages that gradually decrease the source image size.
A preferred embodiment of the invention removes the image data from the source image that are lost during the normal storage and halftoning stages in one step. Each pixel in the source image is compared to the threshold array values. If the value of the source image pixel is less than the corresponding threshold array pixel, then a zero is placed in that position in the dithered image array. If the value of the source image pixel is greater than the threshold pixel, then a one is placed in the dithered image array.
The dithered image array is then compared with the threshold array. A range array is created where the range of each pixel is determined using the dithered image array values combined with the threshold array values.
A value selection is then made from the range array to create a derived image array. One value is selected from the range that has been established for each pixel. The actual value chosen depends on the desired print quality and/or compression ratio. The result is an image that is much simpler than the source image. The resulting derived array is then compressed, the derived image can be compressed using a lossy or lossless technique without any further loss of information because the amount of data known to be lost has been removed. The derived image will produce the same dithered image using the same threshold array as the original source image in the halftone process.
Other aspects and advantages of the invention will become apparent from the following detailed description in combination with the accompanying drawings, illustrating, by way of example, the principles of the invention.
REFERENCES:
patent: 4193096 (1980-03-01), Stoffel
patent: 4281312 (1981-07-01), Knudson
patent: 4760460 (1988-07-01), Shimotohno
patent: 5323247 (1994-06-01), Parker et al.
patent: 5359430 (1994-10-01), Zhang
patent: 5457772 (1995-10-01), Shannon
patent: 5463703 (1995-10-01), Lin
patent: 5542031 (1996-07-01), Douglass et al.
patent: 5548689 (1996-08-01), Poppenga et al.
patent: 5552898 (1996-09-01), Deschuytere
patent: 5682442 (1997-10-01), Johnston et al.
patent: 5708518 (1998-01-01), Parker et al.
patent: 5917952 (1999-06-01), Noh
patent: 6137589 (2000-10-01), Obrador et al.
patent: 3501830 (1984-01-01), None
patent: 278 548B1 (1993-05-01), None
Electronics For Imaging, Inc.
Glenn Michael A.
Rogers Scott
LandOfFree
Dithered image compression system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dithered image compression system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dithered image compression system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2513366