Method for fast image identification and categorization of multimedia data

• US 5,887,081 A
• Filed: 12/07/1995
• Issued: 03/23/1999
• Est. Priority Date: 12/07/1995
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation (NCR Voyix Corporation)
• Inventors: Bantum, Michael G.
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/568,900
• Time in Patent Office: 1,202 Days
• Field of Search: 382/199, 382/203, 382/256, 382/173, 382/176, 382/177, 382/175, 382/180, 382/179, 382/257, 382/204, 382/282, 382/283, 358/453, 358/462, 358/464, 345/434
• US Class Current: 382/173
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

A method for combining multiple digital shape objects contained within a digitized document to obtain a distinct shape or hull dependent on the shapes of the original objects. This shape may thereafter be utilized to simplify storage, recognition, and classification of the digitized documents. The method for combining multiple digital images includes the steps of forming a connected, one-pixel thick boundary around the shape objects contained within a document; and collapsing the boundary around the contained digital objects, the boundary thereby attaining a distinct shape or hull dependent upon the shapes of the digital objects contained within the document. When necessary, pixels are deleted from the boundary to "shrink-wrap" or make taut the boundary around the contained objects.

Claims

1. A method for combining multiple digital objects contained within a digitized image, wherein said digitized image including said digital objects comprises an array of pixels, each pixel having an intensity value associated therewith;

the method comprising the steps of;

forming a boundary around said digital objects, said boundary being formed of a plurality of eight-connected pixels;

collapsing said boundary around said contained digital objects, said boundary attaining a distinctive hull having a shape dependent upon said contained digital objects, said step of collapsing said boundary including the steps of;

examining each pixel in said boundary, and moving each examined boundary pixel one pixel location closer to said contained digital objects, said movement being permitted only when;

said examined boundary pixel does not overlap pixels included within said contained digital objects;

said examined boundary pixel does not collide with another boundary pixel location; and

a section of said boundary containing said examined boundary pixel does not violate a predetermined tautness condition; and

repeating said step of examining each pixel contained within said boundary until the location of each pixel within said boundary becomes fixed.

2. The method in accordance with claim 1, further including the step of:

converting said contained digital objects into to bi-level images prior to said step of collapsing said boundary around said contained objects, said bi-level images comprising pixels having one of two intensity values.

3. The method in accordance with claim 1, wherein said step of collapsing said boundary around said contained objects includes the step of:

deleting said examined pixel from said boundary when the two pixels contained within said boundary which neighbor said examined pixel are adjacent to each other.

4. The method in accordance with claim 3, wherein said boundary has a thickness of one pixel.

5. A method for simplifying storage, recognition classification and retrieval of a digitized document containing multiple digital objects, said digitized document and said digital objects comprising an array of pixels each pixel having an intensity value associated therewith, the method comprising the steps of:

identifying the location of said multiple digital objects;

forming a single boundary around said multiple digital objects;

collapsing said boundary around said contained digital objects, said boundary attaining a distinct hull having a shape dependent upon said contained digital objects wherein said boundary is formed of a plurality of eight-connected pixels;

said step of collapsing said boundary including the steps of;

examining each pixel contained within said boundary, and moving each examined boundary pixel one pixel location closer to said contained digital objects, said movement being permitted only when;

said examined boundary pixel does not overlap with said contained digital objects;

said examined boundary pixel does not collide with another boundary pixel; and

a section of said boundary containing said examined boundary pixel does not violate a predetermined tautness condition; and

repeating said step of examining each pixel in said boundary until the location of each pixel in said boundary becomes fixed; and

classifying the hull shape attained by said boundary, said classified hull shape being utilized for storage, recognition, classification and retrieval of said digitized document.

6. The method in accordance with claim 5, wherein said step of collapsing said boundary around said contained images includes the steps of:

deleting said examined pixel from said boundary when the two pixels contained within said boundary which neighbor said examined pixel are adjacent to each other.