Image analysis – Image segmentation – Distinguishing text from other regions
Reexamination Certificate
2000-11-09
2001-10-02
Mehta, Bhavesh (Department: 2621)
Image analysis
Image segmentation
Distinguishing text from other regions
C382S209000, C382S260000, C358S462000
Reexamination Certificate
active
06298151
ABSTRACT:
This invention relates generally to a method and apparatus for automatic image segmentation using template matching filters, and more particularly to a method and apparatus for segmenting regions of differing texture or structure within a stored binary image using a template matching filter that is designed to pass at least one texture while removing one or more other textures.
CROSS REFERENCE
The following related applications are hereby incorporated by reference for their teachings:
U.S. Pat. No. 5,293,430 by Shiau (published at EP-A2 0 521 662 on Jan. 7, 1993);
“Method for Design and Implementation of an Image Resolution Enhancement System That Employs Statistically Generated Look-Up Tables,” Loce et al., Ser. No. 08/169,485, filed Dec. 17, 1993, now U.S. Pat. No. 5,696,845.
“Non-Integer Image Resolution Conversion Using Statistically Generated Look-Up Tables,” Loce et al., Ser. No. 08/170,082, filed Dec. 17, 1993, now U.S. Pat. No. 5,389,985.
“Method for Statistical Generation of Density Preserving Templates for Print Enhancement,” Loce et al., Ser. No. 08/169,565, filed Dec. 17, 1993, now U.S. Pat. No. 5,359,423.
“Automated Template Design for Print Enhancement,” Eschbach, Ser. No. 08/169,483, filed Dec. 17, 1993, now U.S. Pat. No. 5,724,455; and
“Image Resolution Conversion Method that Employs Statistically Generated Multiple Morphological Filters,” Loce et al., Ser. No. 08/169,487, filed Dec. 17, 1993, now U.S. Pat No. 5,579,445.
INCORPORATION BY REFERENCE
U.S. Pat. No. 4,194,221 to Stoffel, U.S. Pat. No. 4,811,115 to Lin et al., and U.S. Pat. No. 5,131,049 to Bloomberg et al. are hereby specifically incorporated by reference for their teachings regarding image segmentation.
BACKGROUND AND SUMMARY OF THE INVENTION
The present invention is a novel approach to separating text, halftones, or other image structures in composite images using template-based filtering methods. A key application of the present invention is the segmentation of text regions from halftone regions. In the reproduction of an original document from video image data created, for example, by electronic raster input scanning from an original document, one is faced with the limited resolution capabilities of the reproducing system and the fact that output devices remain predominantly binary. This is particularly evident when attempting to reproduce halftones, lines and continuous tone images. Of course, an image data processing system may be tailored so as to offset the limited resolution capabilities of the reproducing apparatus used, but this is difficult due to the divergent processing needs required by the different image types that may be encountered. In this respect, it should be understood that the image content of the original document may consist entirely of high frequency halftones, low frequency halftones, continuous tones, text or line copy, or a combination, in some unknown degree, of some or all of the above. Optimizing the image processing system for one image type in an effort to offset the limitations in the resolution capability of the reproducing apparatus used, may not be possible, requiring a compromise choice that may not produce acceptable results. Thus, for example, where one optimizes the system for low frequency halftones, it is often at the expense of degraded reproduction of high frequency halftones, or of text or line copy, and vice versa. Beyond the issue of accurate reproduction, segmentation of different image types is key to the successful application of recognition algorithms (e.g., character recognition and glyph recognition) and efficient application of image compression techniques.
As one example of the problems encountered, reproduction of halftoned images with screening tends to introduce moire, caused by the interaction of the original screen frequency and applied screen frequency. Although the use of high frequency line screens can reduce the problem, the artifact can still occur in some images. In a networked environment particularly, it is desirable that the image processing device (e.g., raster input scanner) detect the halftone, and low-pass filter the document image into a continuous tone for subsequent halftone reproduction by printers in the network in accordance with their particular capabilities.
Heretofore, a number of applications, patents and publications have disclosed techniques for segmentation of digital image data, the relevant portions of which may be briefly summarized as follows: U.S. patent application Ser. No. 08/044,479 to Shiau, teaches a particular problem noted in the use of an auto correlation function of the false characterization of a portion of the image as a halftone, when in fact it would be preferable for the image to be processed as a line image. Examples of this defect are noted particularly in the processing of Japanese Kanji characters and small Roman letters. In these examples, the auto correlation function may detect the image as halftones and process accordingly, instead of applying a common threshold through the character image. The described computations of auto correlation are one dimensional in nature, and this problem of false detection will occur whenever a fine pattern that is periodic in the scan line or fast scan direction is detected. In the same vein, shadow areas and highlight areas are often not detected as halftones, and are then processed with the application of a uniform threshold.
U.S. Pat. No. 4,194,221 to Stoffel, issued Mar. 18, 1980, discloses the problem of image segmentation. The problem was addressed by applying a discrimination function instructing the image processing system as to the type of image data present and particularly, an auto correlation function to the stream of pixel data, to determine the existence of halftone image data. Stoffel describes a method of processing automatically a stream of image pixels representing unknown combinations of high and low frequency halftones, continuous tones, and/or lines to provide binary level output pixels representative of the image. The described function is applied to the stream of image pixels and, for the portions of the stream that contained high frequency halftone image data, notes a large number of closely spaced peaks in the resultant signal. The correlator circuits described in Stoffel's embodiment, however, are very expensive, as they must provide a digital multiplication function. Accordingly, as a practical matter, Stoffel requires as a first step, reduction of the amount of data handled, by initially thresholding image data against a single threshold value, to reduce the image to a high contrast black or white image. However, depending on the selection of the threshold as compared to the intensity of the image, significant amounts of information may be lost in the thresholding process. For example, if the threshold level is set to distinguish in the middle of the intensity range, but the image has significant variations through the darker gray levels, the thresholded result does not indicate the variations. This results in an undesirable loss of image information. While it may be possible to vary the threshold value adaptively from original to original and from image area to image area, such algorithms tend to be complicated and work well only for a restricted class of images such as line images.
U.S. Pat. No. 4,811,115 to Lin et al., issued Mar. 7, 1989, teaches an auto correlation function that is calculated for the stream of halftone image data at selected time delays that are predicted to be indicative of the image frequency characteristics, without prior thresholding. The arithmetic function used in that auto correlation system is an approximation of the auto correlation function that employs logical functions and addition, rather than the multiplication function used in U.S. Pat. No. 4,194,221 to Stoffel. Valleys in the resulting auto correlated function are detected to determine whether high frequency halftone image data is present.
U.S. Pat. No. 5,065,437 to Bloomberg, issued Nov. 12, 1991, discloses a method for separating fi
Eschbach Reiner
Jodoin Ronald E.
Loce Robert P.
Basch Duane C.
Dudley Mark Z.
Mehta Bhavesh
Xerox Corporation
LandOfFree
Method and apparatus for automatic image segmentation using... 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 automatic image segmentation using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for automatic image segmentation using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2574944