Image analysis – Image segmentation
Reexamination Certificate
1996-04-02
2003-04-15
Chang, Jon (Department: 2623)
Image analysis
Image segmentation
C382S228000
Reexamination Certificate
active
06549656
ABSTRACT:
The present invention relates generally to a system for processing document images to identify image types therein, and more particularly to an improved method of automatically segmenting a document image by classifying each type of imagery with some probability.
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. patent application Ser. No. 08/004,479 by Shiau et al. now U.S. Pat. No. 5,293,430 (published at EP-A2 0 521 662 on Jan. 7, 1993) are herein specifically incorporated by reference for their teachings regarding image segmentation.
BACKGROUND OF THE INVENTION
In the reproduction of copies 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 are mostly binary or require compression to binary for storage efficiency. 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 types of image which may be encountered. In this respect, it should be understood that the image content of the original document may consist entirely of multiple image types, including high frequency halftones, low frequency halftones, continuous tones, line copy, error diffused images, etc. or a combination, in some unknown degree, of some or all of the above or additional image types. In the face of these possibilities, optimizing the image processing system for one image type in an effort to offset the limitations in the resolution and the depth capability of the reproducing apparatus used (e.g. a device resolution of K pixels per unit length by L pixels per unit length (K×L) and each pixel defined at a depth b representing one of b optical densities), may not be possible, requiring a compromise choice which 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 line copy, and vice versa.
Automatic segmentation serves as a tool to identify different image types or imagery, and identify the correct processing of such image types. In U.S. Pat. No. 4,194,221 to Stoffel, the problem of image segmentation was addressed by applying a 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. Such a function is expressed as:
A
(
n
)
=
∑
t
=
Last
t
=
0
[
p
(
t
)
×
p
(
t
+
n
)
]
(
1
)
where
n=the bit or pixel number;
p=the pixel voltage value; and
t=the pixel position in the data stream.
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.
In U.S. Pat. No. 4,811,115 to Lin et al, the auto correlation function is calculated for the stream of halftone image data at selected time delays which 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 using 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. patent application Ser. No. 08/004,479 by Shiau et al now U.S. Pat. No. 5,293,430 is directed to the particular problem noted in the use of the 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.
Great Britain Patent Publication No. 2,153,619A provides a similar determination of the type of image data. However in that case, a threshold is applied to the image data at a certain level, and subsequent to thresholding the number of transitions from light to dark within a small area is counted. The system operates on the presumption that data with a low number of transitions after thresholding is probably a high frequency halftone or continuous tone image. The thresholding step in this method has the same undesirable effect as described for Stoffel.
Of background interest in this area are U.S. Pat. No. 4,556,918 to Yamazaki et al. showing an arrangement assuming a periodicity of an area of halftone dots which are thresholded against an average value derived from the area to produce a density related video signal; U.S. Pat. No. 4,251,837 to Janeway, III which shows the use of a three decision mode selection for determining threshold selection based on gradient constants for each pixel; U.S. Pat. No. 4,578,714 to Sugiura et al. which shows random data added to the output signal to eliminate pseudo-outlines; U.S. Pat. No. 4,559,563 to Joiner, Jr. which suggests an adaptive prediction for compressing data based on a predictor which worked best for a previous pixel block; and U.S. Pat. No. 3,294,896 to Young, Jr. which teaches the usefulness of thresholding in producing an image from a binary digital transmission system; and U.S. Pat. No. 4,068,266 to Liao discloses a method for carrying out resolution conversion with minimum statistical error.
Also background of interest in this area are U.S. Pat. No. 4,509,195 to Nadler which describes a method for binarization of a pattern wherein two concentric rings around a pixel are evaluated to determine contrast values, and the contrast values are used then to determine whether the pixel and the surrounding areas have a light or dark quality, and U.S. Pat. No. 4,547,811 to Ochi et al. which teaches a method of processing gray level values, depending on the density level of blocks of pixels, and their difference from a minimum or maximum value. The blocks can then be processed by a halftone processing matrix depending on the difference value, U.S. Pat. No. 4,730,221 to Roetling discloses a screening technique where values of gray over an image are evaluated to determine a minimum and maximum level, in order to determine constant levels of gray. U.S. Pat. No. 4,736,253 to Shida discloses a method of producing a halftone dot by selectively comparing image signals with highlight and shadow reference values, for determination of the binarization process.
Although, significant work has been done in the automatic image segmentation area, with efforts, particularly characterized by U.S. patent application Ser. No. 08/004,479 by Shiau et al. now U.S. Pat. No. 5.293,430, to reduce the incorrect characterization of one image type as another, the problem continues to present diff
Basch Duane C.
Chang Jon
Nickerson Michael J.
Xerox Corporation
Zell Thomas B.
LandOfFree
Fuzzy image segmentation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fuzzy image segmentation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fuzzy image segmentation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3094834