Image analysis – Color image processing – Image segmentation using color
Reexamination Certificate
2000-10-23
2004-03-16
Johns, Andrew W. (Department: 2621)
Image analysis
Color image processing
Image segmentation using color
C382S166000, C382S224000, C382S245000, C382S248000
Reexamination Certificate
active
06707939
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of the Invention
The invention relates to the art of digital image processing, and to a method for compressing image data of a digitally produced or stored image to a reduced data set. Compression methods for image data are used in many fields of application of digital image processing so that, as a consequence of the reduced data set that results therefrom, storage space, data transmission time, processing time and resultant costs are reduced.
An important field of application is electronic reproduction technology, in which very large image data sets are processed. In reproduction technology, printing originals are produced for printed pages which contain all the page elements to be printed, such as texts, graphics and images. In the case of the electronic production of the printing originals, these elements are present in the form of digital data. The data are produced for an image, for example, by scanning the image in a scanner by point and line, decomposing each pixel into color components and digitizing the color values of these components. The data for texts and graphics are generally produced directly in a computer by text-processing and drawing programs. Depending upon the subsequently employed output process, for example outputting on a color printer or printing in a conventional printing machine, the data for the page elements are produced and stored in the color components of red, green and blue (RGB) or in the printing inks of four-color printing, specifically cyan, magenta, yellow and black (CMYK).
In the further operating sequence, the digitized texts, graphics and images are electronically assembled at a processing station under visual control on a color monitor or automatically in accordance with stored layout stipulations, i.e., the page elements are assembled, for example, in a storage area of the processing station in accordance with the layout to form a printed page. The finished printed page is converted, in this regard, into a data format suitable for outputting, and stored. The printed-page data for each of the printing inks (RGB or CMYK) are denoted as color separation data. The color separation data are used to produce printing plates for a conventional printing machine, or are transmitted directly to a fast color printer or to a digital printing machine and printed out thereat. For example, 24 pixels/mm (600 pixels/inch), constitute a sufficient resolution for the color separation data of the printed pages. If four color values are stored per pixel (CMYK), and the densities of the color values are digitized using 8 bits (=1 byte), respectively, the result for a printed page of size DIN A
4
is a data set of 210 mm×297 mm×24×24×4=143, 700, 480 bytes, (1) i.e., approximately 144 megabytes. This data set is further multiplied by the number of pages in a printed product. It is therefore necessary to process very large data sets in accordance with electronic reproduction technology. Consequently, an important role is played by methods for effectively compressing these data sets.
It is possible to distinguish areas having two types of image data on printed pages: firstly, areas containing a great many different colors changing from pixel to pixel, for example, scanned images, and secondly, areas containing only two colors, for example, text or graphics. Even in areas containing more than two colors, for example, colored graphics, there are frequently subareas with only two colors. Different compression methods have become known heretofore for the two types of image data, and they are optimized for the respective type, i.e., they attain a compression factor which is as high as possible, and do not at all or only slightly falsify the image information.
Methods of transformational coding have become known heretofore for compressing the image data in areas with many different colors. In this regard, the image data are divided into blocks of, for example, 8×8 pixels, the blocks are transformed into a frequency representation (similar to the Fourier transformation) and only the frequency components relevant to the image information are stored in coded form. Such an expanded method is known by the designation JPEG (Joint Photographic Engineers Group) and has been internationally standardized.
The published European Patent Application EP-A-0 491 556 describes an extended transformation coding wherein image data blocks are additionally detected which have a uniform color, for example, the background color white. Such blocks are not subjected to transformational coding, but the positions thereof are coded with the aid of arithmetic coding, and inserted into the transformationally coded data of the remaining blocks. Moreover, an edge detector is used to detect pixels which are situated at the edges of graphic characters, and the color and position thereof are likewise coded by arithmetic coding.
Methods of run length coding wherein the position and the length-of-line sections with pixels of the same color are coded have become known heretofore for the purpose of compressing the image data in areas with two colors. There are run length codings which operate in one dimension and in two dimensions. In the case of the one-dimensional methods, pixels of the same color which are consecutive in a scanning line are counted, and these run lengths are stored as code words. In the case of the two-dimensional methods, the deviations of the run lengths in the current scanning line from the corresponding run lengths of the preceding scanning line are coded. For both types of run length coding, there are methods which are very widespread and standardized in facsimile transmission technology. A further method which is suitable for compressing image data with two colors has become known by the designation LZW (Lempel, Ziv, Welch). In this case, repeating sequences of pixels, which need not all be of the same color, are coded.
U.S. Pat. No. 5,267,333 describes a method for image data compression wherein images and partial images are sorted manually according to categories of text, background image and foreground image. Different compression methods are applied, respectively, for the three categories, both transformational codings and the standardized facsimile codings. The heretofore known methods for compressing image data with two colors have the disadvantage in that they cannot be combined in a simple manner with a transformational coding for image data with many colors. Moreover, the compression of the heretofore known methods for two-color image data is not effective enough in the case of the high resolutions which are used in electronic reproduction technology. Basically, the transformational coding could also be applied to the entire printed page. However, the compression factor then attainable in the two-color image areas would be low, and the decompressed image data would furthermore be affected by intolerable errors. Conversely, it would also be possible, for example, to apply the LZW method to the entire printed page. The attainable compression factor would then be low in the multicolor image areas.
SUMMARY OF THE INVENTION
It is therefore an object of the invention of the instant application to avoid the disadvantages of the heretoforeknown methods for compressing two-color image data by providing a method for compressing two-color image data without errors, which is effective and relatively easy to implement, and which is suitable for combination with a transformational coding for the purpose of compressing multicolor image data.
With the foregoing and other objects in view, there is provided, in accordance with the invention, a method for compressing digital image data present as a matrix of M×N pixels, to a reduced data set, which comprises dividing the matrix of M×N pixels into blocks of u×v pixels, classifying the blocks of u×v pixels into blocks containing only pixels of one block color or single-color blocks, blocks containing pixels of a foreground color and pixel
Siemsen Eike
Weinholz Peter
Alavi Amir
Greenberg Laurence A.
Heidelberger Druckmaschinen AG
Johns Andrew W.
Mayback Gregory L.
LandOfFree
Method for image data compression for two-color images 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 for image data compression for two-color images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for image data compression for two-color images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3274958