Apparatus and method for segmenting and classifying image data

• US 5,850,474 A
• Filed: 07/26/1996
• Issued: 12/15/1998
• Est. Priority Date: 07/26/1996
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Fan, Zhigang, Revankar, Shriram, Shiau, Jeng-Nan, Ryall, Kathy
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Novik, Dmitry A.
• Application Number:
  US08/686,803
• Time in Patent Office: 872 Days
• Field of Search: 382/180, 382/176, 382/173, 382/243, 382/245, 382/318, 382/319, 382/224, 358/462, 358/464, 358/467, 358/453
• US Class Current: 382/173
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

A method and apparatus for segmenting image data into windows and for classifying the windows as typical image types includes making two passes through the image data. The method includes a step of making a first pass through the image data to identify windows and to record the beginning points and image types of each of the windows, and a step of making a second pass through the image data to label each of the pixels as a particular image type. The invention also includes a macro-detection method and apparatus for separating a scanline of image data into edges and image runs and for classifying each of the edges and image runs as standard image types. In the macro-detection method, image runs and edges are classified based on micro-detection results and based on image types of adjacent image runs.

Claims

1. A computer implemented method of segmenting and classifying image data, the image data comprising a plurality of scanlines of pixel data, comprising the steps of:

performing a first pass through the image data to identify at least one window and to determine an image type of the image data within each at least one window, including

performing micro-detection to identify intensity edge pixels,

performing macro-detection to identify at least one image run in each scanline,

identifying at least one window comprising image runs of at least two scanlines, and

classifying each at least one window as containing a single image type or as containing mixed image types;

recording solely the beginning point and the image type of each at least one window; and

performing a second pass through the image data to label each pixel of the image data as being a particular image type.

2. The method of claim 1, wherein the step of performing a second pass through the image data comprises the steps of:

performing micro-detection to identify intensity edge pixels;

performing macro-detection to identify at least one image run in each scanline;

identifying at least one window comprising image runs of at least two scanlines; and

determining, based on results of micro-detection and macro-detection steps performed during the second pass, the image type of any portions of the image data that are within a window classified as containing mixed image types during the first pass.

3. An apparatus for segmenting and classifying image data, the image data comprising a plurality of scanlines of pixel data, the apparatus comprising:

means for performing a first pass through the image data to identify at least one window and to determine an image type of the image data within each at least one window, including

means for performing micro-detection to identify any intensity edge pixels,

means for performing macro-detection to identify at least one image run in each scanline,

means for identifying at least one window comprising image runs of at least two scanlines, and

means for classifying each at least one window as containing a single image type or as containing mixed image types;

memory means for recording solely the beginning point and the image type of each at least one window and for recording solely an image type of each pixel of the image data; and

means for performing a second pass through the image data to label each pixel of the image data as being a particular image type.

4. The apparatus of claim 3, wherein the means for performing a second pass through the image data comprises:

means for performing micro-detection to identify intensity edge pixels;

means for performing macro-detection to identify at least one image run in each scanline;

means for identifying at least one window comprising image runs of at least two scanlines; and

means for determining, based on results of micro-detection and macro-detection steps performed during a second pass, the image type of any portions of the image data that are within a window classified as containing mixed image types during the first pass.