Image analysis – Image segmentation
Reexamination Certificate
1998-06-18
2001-05-29
Tran, Phuoc (Department: 2621)
Image analysis
Image segmentation
C382S180000, C382S224000
Reexamination Certificate
active
06240205
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to methods and apparatus for segmenting a page of image data into windows and for classifying the image data within each window as a particular type of image data.
2. Related Art
Image data is often stored in the form-of multiple scanlines, each scanline comprising multiple pixels. When processing this type of image data, it is helpful to know the type of image represented by the data. For instance, the image data could represent graphics, text, a halftone, condone, or some other recognized image type. A page of image data could be all one type, or some combination of image types.
It is known in the art to take a page of image data and to separate the image data into windows of similar image types. For instance, a page of image data may include a halftone picture with accompanying text describing the picture. In order to efficiently process the image data, it is known to separate the page of image data into two windows, a first window representing the halftone image, and a second window representing the text. Processing of the page of image data can then be efficiently carried out by tailoring the processing to the type of image data being processed.
It is also known to separate a page of image data into windows and to classify and process the image data within the windows by making either one or two passes through the page of image data. The one pass method is quicker, but it does not allow the use of “future” context to correct information that has already been generated. In a two pass method, information obtained for a third or fourth scanline can be used to generate or correct information on a first or second scanline. In other words, future context can be used.
In a two pass method, during the first pass, the image is separated into windows, and a judgment is made about the type of image data in each window. At the end of the first pass, the image type for each pixel is recorded in memory. During the second pass, the information from the first pass, i.e., the image type data, is used to process the image data. Unfortunately, storing image type information for each pixel of a page of image data requires a great deal of memory, which increases the cost of an apparatus for performing this method.
SUMMARY OF THE INVENTION
The invention is an improved two pass method and apparatus for separating image data into windows and for classifying the image data within each window.
In the method, during the first pass through the image data, micro-detection and macro-detection are performed to separate each scanline of data into edge sections and image run sections. During micro-detection, the image type of each pixel is determined by examining neighboring pixels. During macro-detection, the image type of image runs of a scanline are determined based on the results of the micro-detection step. Known micro-detection methods can be used to accomplish these functions, such as the micro-detection methods described in U.S. Pat. No. 5,293,430 to Shiva et at., the disclosure of which is hereby incorporated by reference.
Next, the image run sections of the scanlines are combined to form windows. This is done by looking for portions of the image that are “white.” Such areas are commonly called “gutters.” The gutters typically separate different portions of a page of images. For instance, a white gutter region would exist between a half toned image and text describing the image. A horizontal gutter might exist between different paragraphs of a page of text. Likewise, a vertical gutter might exist between two columns of text.
Statistics on the macro-detection results within each window are then compiled and examined. Based on the statistics, each window is classified, if possible, as a particular image type. At the end of the first pass, the beginning point of each window is recorded in memory. If a window appears to contain primarily a single type of image data, the image type is also recorded. If a window appears to contain more than one image type, the window is identified as a “mixed” window.
During a second pass through the image data, the micro-detection, macro-detection and windowing steps are repeated. Those pixels within windows that were labeled as single image type during the first pass are simply labeled with the known image type. Those pixel Is that are within a window that was labeled as “mixed” during the first pass, are labeled based on the results of the micro-detection, macro-detection and windowing steps performed during the second pass. Once a pixel has been labeled as a particular image type, further processing of the image data may also occur during the second pass.
Because the same hardware is used to perform both the first and second passes, there is no additional cost for the second pass. In addition, because the image type classification of each pixel is not recorded at the end of the first pass, the memory requirements and thus the cost of an apparatus for performing the method are reduced.
In the method according to the invention, a macro-detection step for examining a scanline of image data may include the steps of separating a scanline into edge portions and image runs and classifying each of the image runs based on statistics for the image data within each image run. The macro-detection step could also include clean up steps wherein each of the edge sections of the scanline are also classified based on 1) the image data of the edge sections, and 2) the classification of surrounding image runs. The clean up steps might also include reclassifying image runs based on the classification of surrounding image runs.
REFERENCES:
patent: 5073953 (1991-12-01), Westdijk
patent: 5280367 (1994-01-01), Zuniga
patent: 5285504 (1994-02-01), Pavlidis
patent: 5293430 (1994-03-01), Shiau et al.
patent: 5359673 (1994-10-01), De La Beaujardiere
“Automatic Document Segmentation,” IBM Technical Disclosure Bulletin, vol. 31, No. 7, Dec. 1988, pp. 73-74.
“Rule-Based System for Chinese Newspaper Segmentation,” Signal Processing VI: Theories and Applications, vol. 1, No. Conf. 6, Aug. 1992, pp. 615-618.
“A Tool Classifying Office Documents,” Proc. of the 1993 IEEE Int'l Conference on Tools with AI, No. 5, Nov. 1993, pp. 427-434.
Fan Zhigang
Revankar Shriram
Ryall Kathy
Shiau Jeng-Nan
Oliff & Berridg,e PLC
Tran Phuoc
Xerox Corporation
LandOfFree
Apparatus and method for segmenting and classifying image data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for segmenting and classifying image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for segmenting and classifying image data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2549952