US 7366357 B2
The image data is processed into a background plane and a plurality of foreground planes. Holes are inserted onto the background plane, in regions which are assigned to a foreground plane. The background plane is sub-sampled, and holes remaining in the sub-sampled image are filled with the average color of the non-zero sub-sampled pixels over pre-determined blocks such as JPEG blocks. If a block is entirely made of holes, the block is filled with a constant color that is propagated from the average color of a previous block. The resulting background plane is far smoother than the original image data and thus can be effectively sub-sampled and highly compressed without adverse deterioration in reconstructed image quality.
1. A method for processing an image comprising:
identifying pixels in the image which are less critical;
substituting data into identified pixels, the data being chosen to provide a desired characteristic for processing the image;
generating a hole-image by setting to zero pixel values of pixels identified to be less critical to the image;
sub-sampling the hole-image, by averaging only non-zero pixel values in pixel neighborhoods to obtain sub-sampled pixel values for the sub-sampled hole-image, wherein each of the sub sampled pixel values has a non-zero value if a corresponding neighborhood has at least one non-zero pixel value, or a zero value if the corresponding neighborhood has all zero pixel values;
averaging the non-zero sub-sampled pixel values of the sub-sampled hole-image to obtain an avenge value; and
setting the sub-sampled pixel values of zero to the average value of the non-zero sub-sampled pixel values.
2. The method of
3. The method of
4. A method for processing an image to form a background plane and N-binary foreground planes, comprising:
inserting zeroes into pixel data for pixels in the background plane corresponding to areas which have been placed into one of the N-binary foreground planes, to generate a hole-image;
sub-sampling the hole-image to obtain one or more blocks of sub-sampled pixel values, each of the sub-sampled pixel values having a non-zero value if a corresponding neighborhood has at least one non-zero pixel value, or a zero value if the corresponding neighborhood has all zero pixel values;
averaging color values of only non-zero sub-sampled pixel values in each of the blocks to obtain a block average color value for each of the blocks; and
substituting sub-sampled pixel values of each of the blocks that are equal to zero to the block average color value of each of the blocks.
5. The method of
identifying a previous block based on a predetermined criterion; and
substituting an average color value of the previous block for sub-sampled pixel values in a block in which all of the sub-sampled pixel values are zero.
6. The method of
7. The method of
adjusting the image according to predefined requirements; and
setting a chroma value of a pixel to a midpoint in its allowed range when a luminance value of the pixel is at a maximum of its allowed range.
8. Tire method of
averaging one or more pixel values within a neighborhood of pixels to obtain a sub-sampled pixel value that corresponds to the neighborhood.
9. The method of
summing the pixel values within the neighborhood of pixels; and
dividing the sum of pixel values by a number of only non-zero pixel values, to obtain the sub-sampled pixel value.
10. The method of
11. An apparatus that processes an image, comprising:
a memory that stores image data and selector data, wherein the selector data identifies less critical portions of the image data;
a processor that sets less critical portions of the image data to zero based on the selector data:
a sub-sampling processor that sub-samples hole-image data and averages only the non-zero data values in a block of the sub-sampled hole-image data to obtain a block average valet; and
a pixel substitutor which substitutes the block average value of only the non-zero data values for the zero values in the sub-sampled hole-image data.
12. The apparatus of
13. The apparats of
a hole-filler that identifies previous blocks based on predefined criteria, and replaces zero values of the blocks of sub-sampled hole-image data with a previous block average value, when the blocks of sub-sampled hole-image data consist entirely of zeroes.
14. The apparatus of
15. A computer-readable medium having computer-readable program code embodied therein, the computer-readable program code performing the method of
16. A xerographic marking device using the method of
17. A digital photocopier using the method of
This invention is related to U.S. patent applications Ser. Nos. 10/776,515, 10/776,514, 10/776,608, 10/776,602, 10/776,620, 10/776,509, 10/776,508, 10/776,516 and 10/776,612 filed on an even date herewith and incorporated by reference in their entireties.
1. Field of Invention
This invention is directed to generating high compression data files from uncompressed image data. In particular, this invention is directed to organizing image data into different binary and contone planes which are highly compressible.
2. Related Art
Documents scanned at high resolutions typically require very large amounts of storage space. Furthermore, a large volume of image data requires substantially more time and bandwidth to manipulate, such as transferring over a local or wide area network, over an intranet, an extranet or the Internet, or other distributed networks.
Documents, upon being scanned using a scanner or the like, are typically defined using an RGB color space, i.e., in raw RGB format. However, rather than being stored in this raw scanned RGB format, the document image data is typically subjected to some form of data compression to reduce its volume, thus avoiding the high costs of storing such scanned RGB document image data.
Lossless run-length compression schemes, such as Lempel-Ziv (LZ) or Lempel-Ziv-Welch, (LZW), do not perform particularly well on scanned image data or, in general, image data having smoothly varying low-spatial frequencies such as gradients and/or natural pictorial data, while lossy methods such as JPEG, work fairly well on smoothly varying continuous tone (contone) image data. However, lossy methods generally do not work particularly well on binary text and/or line art image data, or, in general, on any high spatial frequency image data containing sharp edges or color transitions, for example.
A new approach to satisfying the compression needs of data, such as the different types of image data described above, is to use an encoder pipeline that uses a mixed raster content (MRC) format to describe the data. The image data, such as for example, image data defining a composite image having text intermingled with color and/or gray-scale information, is segmented into two or more planes. These planes are generally referred to as the background plane and the foreground planes. A selector plane is generated to indicate, for each pixel in the composite image, which of the image planes contains the actual image data that should be used to reconstruct the final output image. Segmenting the image data into planes in this manner tends to improve the overall compression of the image, because the data can be arranged into different planes such that each of the planes are smoother and more readily compressible than is the original image data. Segmentation also allows different compression methods to be applied to the different planes. Thus, the most appropriate compression technique for the type of data in each plane can be applied to compress the data of that plane.
Unfortunately, some image document formats, such as the portable document format (PDF), do not currently fully support such three-layer mixed raster content decompositions of an original document. As a result, when attempting to print or otherwise render a document that has been compressed and stored as a mixed raster content image data file using such image document formats, the document either cannot be rendered at all, or contains objectionable artifacts upon rendering.
Systems and methods are provided for converting a document to a mixed raster content format having a plurality of binary foreground planes. After scanning the document, the image data is analyzed to identify regions having similar image characteristics. Each of the regions is then lifted into one of the plurality of binary foreground planes. The lifting of the regions leaves holes in the background layer, which will be overwritten upon reproduction of the compressed image from the binary foreground planes. Thus, the hole areas in the background layer may contain data which is not critical to the proper reproduction of the original document image. These hole areas can be filled with data to enhance various properties of the background layer. For example, the hole areas may be filled with the average color of the nearby pixels, thereby improving the compression characteristics of the background layer.
While multiple binary foreground plane image data is discussed here as an example, the invention can be used wherever regions of less critical data can be identified in an image. Other such situations may include regions which are outside the printable area of the image, or regions which will be overwritten by other data not part of the original image data. In such cases, the data in the identified region may be substituted with data that enhances certain other image properties, such as compressibility of the image.
The invention is described, with reference to the following figures, wherein:
An image processing system is presented which separates regions in an image into a contone background plane and a plurality of foreground planes. Pixels in the image which share certain features, such as color and spatial proximity properties, are grouped together and represented by one of N binary foreground planes, in order to improve image processing, such as more effective compression of the image data. Pixels not represented by any of the foreground planes are left in the contone background plane. Each plane is then independently compressed using an appropriate standard compression method such as JPEG for the contone background plane and CCITT G4 for a binary plane. When reproducing the image, some regions in the background plane are overwritten by data in the foreground plane. Thus, these regions in the background plane are less critical to the proper reproduction of the document image. Therefore, the data in these regions can be replaced with data which improves a characteristic of the background plane, such as its compression ratio. For example, these regions can be replaced with data which is an average color value of the neighboring regions, such that the boundary between the replaced regions and the remaining background pixels is more gradual than would otherwise be.
For ease of discussion, the following uses compression characteristics as an example. However, improvement in other image characteristics may be implemented, such as encoding characteristics.
For example, the image data may contain regions 220′-270′ having similar color data that could be separated into six distinct color values. Each of the six color values may be associated with a particular one of the multiple binary foreground planes 220-270. Binary mask data of each of the binary foreground planes 220-270 define the spatial extents of the areas 220′-270′ corresponding to each of those six colors.
When reproducing the original image, regions in the background plane 210 that correspond to the binary mask bits that are turned on (i.e., selected) in each of areas 270′, 260′, 250′, 240′, 230′, and 220′ in the foreground planes, may be overwritten by these areas of the foreground planes. Therefore, these regions in the background plane 210 are called holes because the data placed in them do not contribute to the quality of the reproduced image. Thus, the data in these holes may be generated in such manner as to improve desirable characteristics such as enhancing the compression characteristics of the background layer, without affecting the output image quality.
The N-layer generating module 600 analyzes the input image and detects regions which share certain characteristics, such as similar color values. The N-layer generating module 600 then combines the detected regions into larger regions which share similar color characteristics and overlap spatially. The N-layer generating module 600 then assigns the combined larger regions to one of N foreground planes, depending on the color value of the combined region. The remaining image data which is not included in a foreground plane, is included in a background plane. The background plane generated by the N-layer generating system is input to the image plane adjustment system 700, which adjusts the data in the background plane to improve the compression characteristics of the background plane. The foreground and background planes are then compressed by the compression module 800, using JPEG algorithm for the contone background plane and CCITT G4 for binary foreground planes, for example, before being output to a file such as a PDF or TIFF file.
The image plane adjustment system 700 prepares the background plane for compression. The input/output interface 760 receives the inputs to the image plane adjustment system 700, which may be stored in memory 750, or which may be acted upon as they are received. The following modules act upon the input data: the input image adjustment module 720, the pixel substitution module 730, and the averaging module 740, each of which is discussed in detail below.
A flow of the image data processing is shown in
The sub-sampling module 725 performs a 2:1 sub-sampling of luminance data by generating one 16ื16 block of data for every contiguous and non-overlapping 32ื32 block of image data. Each 32ื32 block is divided into 256 2ื2 blocks for the 2:1 sub-sampling. All the pixels in the 2ื2 blocks are averaged to generate one sub-sampled data point for each corresponding 16ื16 block. The chroma data may be further sub-sampled by another factor of 2:1 relative to the luminance data (4:1 total). For the 4:1 chroma components, the 32ื32 block is divided into 64 4ื4 blocks. The data of each 4ื4 block is averaged for one data point of the 8ื8 sub-sampled block.
The averaging module 740 averages the color content of a neighborhood of pixels by summing the color value of the pixels within the neighborhood, and dividing by the number of non-zero pixels in the neighborhood, which contributed to the sum. Because some neighborhoods consist entirely of zeroes, or holes, their value will remain 0 even after the sub-sampling operation.
After performing the sub-sampling, the averaging module 740 then calculates the average color of an 8ื8 block of sub-sampled data. The hole-filler 745 then replaces the 0 indicating a hole in the sub-sampled image, with the average value of the 8ื8 block of sub-sampled pixels, thereby filling the hole with the average data.
The background image data after insertion of holes and filling the holes with average color data is expected to be much smoother relative to the original data, and therefore can be further sub-sampled to improve compression and processing speed without adverse impact on reproduction quality. The output of the image plane adjustment system 700 is the adjusted, sub-sampled, and filled background plane (BGA), ready for compression.
The operation of each module indicated in
After the ENH is input to the image plane adjustment system 700, final adjustments such as color adjustment and/or gamma correction curve may be made to the image before sub-sampling by the averaging module 740 and compression by the compression module 800. The gamma correction may be applied to exploit a property of the human eye, which is more responsive to brightly lit areas than dimly lit areas. The adjustments may be applied using, for example, three one-dimensional tone reproduction curves (TRCs) to adjust the color characteristics of the input image contained in the ENH from the N-layer generating module 600. A typical tone reproduction curve is shown in
The input image adjustment module 720 can also be used to apply color suppression to the background layer, or other preferences such as darker-lighter, contrast, color saturation, etc., prior to compression. The input image adjustment module 720 also serves to limit each of the incoming ENH luminance and chroma data to the range of 1 to 255. In this example, the zero value is specifically excluded because this value is convenient to indicate the locations of holes, as will be described further below. Therefore, if the value of 0 occurs in the luminance or chroma channels, the input image adjust module maps it to one.
Lastly, the input image adjustment module 720 may also be responsible for setting the chroma to a neutral midpoint (Cb=Cr=128) when the luminance is 255. This operation ensures that no toner is used for rendering a white neighborhood (Y=255). Otherwise, if Cb or Cr is allowed to be non-neutral, a residue toner amount may be emitted in the YCC conversion to the printer color space of cyan-magenta-yellow-black (CMYK) due to color interpolation accuracy errors in non-neutral areas.
The output of the input image adjustment module 720 is sent to the insert holes module 715. This module reads in the binary selector plane data (SEL) from the N-layer generating module 600, which identifies ENH pixels which are less critical to the proper reproduction of the image, because they may be overwritten by regions assigned to one or more of the binary foreground layers, for example.
The SEL, shown as 640 in
Since the ENH pixel values corresponding to the regions 220′-210′ in
The process of inserting the holes in the ENH is illustrated in
The image data may be sub-sampled at this stage, to reduce the number of pixels in the image data, and thereby reduce the computation burden on the downstream processes.
The sub-sampling is performed by the sub-sampling module 725, using the averaging module 740, which averages, for example, a 2ื2 pixel luminance neighborhood of the ENZ to output 2:1 sub-sampled data, and further averages a 4ื4 pixel neighborhood of the chroma data to generate 4:1 sub-sampled data. The averaging module 740 may work in raster order, from left to right and from top to bottom, for example. The averaging module calculates a sum over a particular set (i.e. neighborhood) of pixels, and divides the sum by the count of pixels in the neighborhood.
For example, to perform the sub-sampling, the luminance data of a contiguous non-overlapping 2ื2 neighborhood of pixels is summed, and the sum is divided by the number of valid pixels in the neighborhood. If all four pixels are valid, the sum is divided by four, to generate a single sub-sampled output pixel. Therefore, each 2ื2 pixel array of the ENZ luminance channel is mapped to one luminance pixel output. According to this process, each 32ื32 block of ENZ yields four 8ื8 blocks of sub-sampled luminance data 741′. Similarly, the ENZ chroma data 748 and 749 are further sub-sampled by 2ื (4ื total), to produce a single block of 8ื8 pixels each, 748′ and 749′. Therefore, each 4ื4 neighborhood of the ENZ chrominance data is mapped to one Cr or Cb pixel output. Each output pixel value is obtained by averaging the corresponding neighborhood area over valid pixels only.
The output of the averaging module 740 is therefore comprised of 4 luminance blocks 741′ and one each Cb and Cr blocks 747′ and 748′, with each block being made up of 8ื8 pixels. This unit of six 8ื8 blocks forms exactly one JPEG minimum coded unit (MCU) in (4:2:0) mode.
Since the holes are conveniently coded as zeros, the neighborhood sum of pixel values is the same, with or without the holes. However, the number of valid (non-zero) pixels can be different and therefore must be counted for each neighborhood, as described above. The neighborhood pixel sum is normalized by the sum of valid (non-zero) pixel values. To avoid costly divisions, the division may be implemented using a predetermined multiplication table (a lookup table) and round right shift operation.
In order to fill the holes, the average sub-sampled image module 735 calculates a fill color from the average of each 8ื8 block of sub-sampled pixels, counting only non-zero pixels and not the remaining holes in the sub-sampled data. Since the holes have a value of zero, the sum of block pixel values is the same with or without the holes. However, the number of valid (non-zero) pixels may be different and therefore must be counted for each block. The average block color is obtained by normalizing the sum of pixel values by the number of valid pixels. To avoid costly divisions, the division may again be implemented via lookup table and right shift operation. Since there are 4 luminance blocks and one each of Cr and Cb blocks, a total of six average numbers (one per block) are produced. Each average is an 8-bit monochrome number. Therefore, for the 2ื2 sub-sampled block shown in
The exemplary method of calculating the average block color is similar to the method for sub-sampling, with the exception of the count size. Therefore, both the sub-sampling and the block color averaging may be performed by the averaging module 740. In the case of the sub-sampling, the count size is generally either 2ื2 (luminance) or 4ื4 (chroma), depending on the number of non-zero pixels. For the average block color calculation, the count size is generally 8ื8, depending on the number of non-zero pixels.
Finally, the fill holes module 745 processes each 8ื8 block at a time, using the pixel substitution module 730. It replaces the zero content for all hole pixels in each block with the average color of that block.
In some instances, the entire block of 32ื32 pixels of either luminance or chroma data may consist entirely of holes, yielding sub-sampled Y, Cb and Cr blocks which are also all zeroes. Such blocks are filled with a constant color to improve compression. The particular constant color value is obtained from the average color of a temporally or spatially previous block. The previous block may be defined in accordance with the JPEG order of blocks within the MCU as indicated in
The process ensures a more desirable fill color for compression for each block. This reduces compression ringing artifacts by filling in the hole pixels with the block average. This completes the filling of the background layer.
If the resulting data is to be compressed, the image plane adjustment system 700 then sends the filled background plane to the compress module 800 for compression. As described earlier, the N-layer generating module 600 sends the other N-layer planes to the compress module for compression as well. Because the holes in the background plane have been filled by the background adjust module 700 with the average color of the other pixels in the background, the compress module 800 can compress the background plane more effectively, with fewer artifacts and less ringing of the boundaries between the filled holes and the remaining background. The compress module 800 may send the compressed background plane to a combiner which combines the compressed foreground layers with the compressed background plane into an n-layer PDF or TIFF file, for example, that is output to a downstream process.
Although the invention has been described in a hardware embodiment, the invention may also be practiced using a software implementation. In this case, software such as, for example, a computer program, may execute the steps of the method. The software can be executed by a suitably programmed microprocessor or ASIC, or it may be performed by some combination of software and hardware. The overall process exemplified by
In step S500, the average color value for the sub-sampled pixels in the sub-sampled image is obtained. In various exemplary embodiments, the average color value is obtained by adding all the non-zero pixels, and dividing by the number of non-zero pixels. In various exemplary embodiments, the division is accomplished by consulting a lookup table for an appropriate multiplier, and then right shifting the resulting bits. In step S600, the holes that were inserted in step S300, are filled by applying the average pixel value for the sub-sampled image, to the pixel value for the holes, which was previously set to zero by the hole insertion step S300. The process ends in step S700.
If the pixel is the last pixel in the neighborhood, control continues to step S470, wherein a value for the sub-sampled pixel is, set to the average color value, which is the SUM value divided by the COUNT. In various exemplary embodiments, the division may be accomplished by finding an appropriate multiplier in a lookup table, and right-shifting the product of the multiplier and SUM. The process then proceeds to step S480, wherein a determination is made whether the neighborhood is the last neighborhood in the image. If not, control jumps back to step S410, to select the next neighborhood. If the neighborhood is the last in the image, the process ends in step S490.
While the invention has been described in conjunction with various exemplary embodiments, these embodiments should be viewed as illustrative, not limiting. Various modifications, substitutes, or the like are possible within the spirit and scope of the invention. For example, instead of improving the compression characteristics of the image plane, data may be used which simply causes the compression algorithm to perform in a desired way. Also, other criteria may be used to select the type of data to substitute in the image plane, rather than compression characteristics. For example, data may be chosen which will alter the encoding characteristics of the image plane, or which will produce ringing artifacts of an advantageous or desirable type. Data may also be used which provides a security key for the data, to prevent unauthorized copying, such as a watermark.