Image analysis – Color image processing – Compression of color images
Reexamination Certificate
1998-12-21
2002-05-07
Au, Amelia M. (Department: 2623)
Image analysis
Color image processing
Compression of color images
C382S266000
Reexamination Certificate
active
06385337
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to image processing and more specifically to selecting colors for pixels in blocks for use in a block truncation coding image compression technique.
BACKGROUND OF THE INVENTION
Data reduction is required in data handling processes, where too much data is present for practical applications that use it. Digital images images that have been discretized in both spatial coordinates and in brightness levels such as those acquired by scanning—are often very large, and thus make desirable candidates for at least one form of data reduction. This is true not only to allow for data to be processed at faster speeds, thereby causing less inconvenience to the user, but to enable more complex data to be processed without drastically increasing the image processing time. For example the number of bits required to accurately describe a detailed halftoned image will be many times more than that of a simple sheet of black text on a white page. By the same token, accurately describing a color image will require an even larger volume of data than its greatly detailed halftoned counterpart. If some form of data reduction does not take place, processing of documents that contain halftone and color images can take an unacceptably long period of time.
Digital color images may be described in terms of the chrominance and luminance values for each pixel contained therein. It is obviously desired to reproduce color images such that the colors in the copy exactly, or at least closely match the corresponding colors in the original image. Since image input and output devices are often quite different, reproducing an accurate color image often requires some form of estimation between color spaces or color correction to be applied to the chrominance and luminance data before it is output.
Block Truncation Coding (BTC) is an image processing technique for encoding and decoding digital image data. BTC typically includes dividing an image into a matrix of blocks, and then sub-dividing each block into a matrix of picture elements or “pixels.” A pixel map is one in which each discrete location on the page contains a pixel that emits a light signal with a value that indicates the color or, in the case of gray scale documents, how light or dark the image is at that location. As those skilled in the art will appreciate, most pixel maps have values that are taken from a set of discrete, non-negative integers.
Color images are typically described as being divided into “separations.” Color output devices such as printers and computer monitors typically output data using only a few independent color sources. Colorants or color signals obtained from these sources are then blended together in appropriate ways in order to produce the full gamut of colors that may be represented using the device. In a device dependent printer color space, Cyan, Magenta, Yellow and black are the individual colorants that are most often used in color printers. These colorant separations are typically labeled C, M, Y and K. Many device-independent color spaces also exist, such as CIE L*a*b*, in which the separations are Lightness, labeled L*, relative amount of red vs. green, labeled a*, and relative amount of yellow vs. blue, labeled b*.
In a pixel map for a color document, individual separations are often represented as digital values, often in the range 0 to 255, where 0 represents no colorant (i.e. when CMYK separations are used), or the lowest value in the range when luminance-chrominance separations are used. In an L*a*b* luminance-chrominance color space a 0 L* value means that no light is present (i.e. the location is completely black), while a*=0 means no red or green is present and b*=0 means that the spot is neither blue nor yellow. Both a*=0 and b*=0 means that the spot is gray, (somewhere between black and white). When represented in an integer space, L*, a*, and b* are typically scaled and translated to fit the range of representable values. In this case a*=b*=0 is actually represented with these values at the midpoint of their ranges, while a*=0 is used to represent green, and b*=0 is used to represent blue.
Consequently 255 represents the maximum amount of colorant (for CMYK) or the highest value in the range (maximum light/white, red and yellow respectively for L*a*b*). In a gray-scale pixel map this typically translates to pixel values which range from 0, for black, to 255, for the whitest tone possible. The pixel maps of concern in the currently preferred embodiment of the present invention are representations of “scanned” images. That is, images which are created by digitizing light reflected off of physical media using a digital scanner. The term bitmap is used to mean a binary pixel map in which pixels can take one of two values, 1 or 0.
Once the block has been divided into pixels, the image is encoded, stored or transmitted to another location, and then decoded upon retrieval or receipt for subsequent processing. A primary goal of a BTC technique is to minimize the number of bits required to encode each pixel while retaining as much quality and detail in the output image that can be generated from the decoded data.
BTC techniques typically require storing several different colors in a color map, with each color being stored at a different address in memory. Two colors are then selected for each block in the image, and a bit map is generated for the block to indicate which color is assigned to each pixel. Binary numbers that represent the addresses of the color designated for each pixel are read from the color map memory location in response to the bitmap value for that pixel. In other words, every pixel in a given block must have one of the two colors that have been designated for that particular block. Consequently, the color of each pixel can be represented by only a single data bit—either a “1” or a “0”—in combination with two binary numbers per block which represent the color map memory addresses for the two colors selected for each block. The information obtained from the color map memory is used to generate an output image made up of pixels that have the selected colors as specified by that data.
By confining the choice of colors to a preselected group of colors, a BTC system can enable a large amount of image information to be represented by a relatively small number of bits, thereby permitting relatively complex images to be displayed in great detail, and animated, from a relatively small amount of encoded data. More specifically, the information needed to accurately display of any one of the preselected colors is stored in the color map memory. Thus the only information required to be encoded is the memory address for the desired color for the various pixel locations.
As indicated earlier, all pixels in each block must be represented by one of only two colors that have been assigned to the block. If the two colors that are selected to represent each block are not selected carefully, the colors in the final decoded output image will not accurately represent those in the original image. The present invention discloses a method and apparatus for selecting the colors that will be assigned to a two color block and subsequently assigning colors to the pixels in the block in order to accurately reproduce a color image.
Known methods of selecting colors for the block attempt to find the two extreme colors in a single pass. The extreme colors obtained from this pass are the two colors that will be assigned to the block. Each pixel in the block is then assigned to the color that is closest to the actual color of that pixel. This scheme is acceptable for the most common scenario, the case in which a block contains two colors and a clear boundary between them. Intermediate colors appear along the boundary and properly, they are not used to find the colors that will be selected to represent the block since the extreme colors will give the most realistic appearance. But problems arise when there are more than two pri
Au Amelia M.
Dudley Mark Z.
Nixon & Peabody LLP
Wu Jingge
Xerox Corporation
LandOfFree
Method of selecting colors for pixels within blocks 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 of selecting colors for pixels within blocks for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of selecting colors for pixels within blocks for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2907049