Method and device for extracting features from gray-scale image and generating boundaries of document elements

• US 6,041,138 A
• Filed: 07/17/1997
• Issued: 03/21/2000
• Est. Priority Date: 08/05/1996
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Nishida, Hirobumi
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/896,142
• Time in Patent Office: 978 Days
• Field of Search: 382/190, 382/197, 382/198, 382/199, 382/203, 382/200
• US Class Current: 382/197
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18 Extraction of features or characteristics of the image
• CPC Class Codes: G06V 30/182 by coding the contour of the pattern

Abstract

A method of extracting features from a gray-scale image includes the steps of generating polygons which approximate a curved surface represented by the gray-scale image, and extracting features with respect to common edges of adjoining polygons. The method further includes the step of generating boundaries of document elements based on the features.

Claims

1. A method of extracting features from a gray-scale image, said method comprising the steps of:

a) generating polygons which approximate a curved surface represented by said gray-scale image;

b) extracting features with respect to common edges of adjoining polygons; and

c) generating boundaries of document elements based on said features,

wherein said step b) comprises the steps of

b1) cutting said surface by a horizontal plane to generate intersection lines between said horizontal plane and said polygons around each one of said common edges,

b2) extracting directional features with respect to each one of said common edges based on said intersection lines, and

b3) extracting convex/concave features with respect to each one of said common edges based on said intersection lines.

2. The method as claimed in claim 1, wherein said step b2) comprising the step of extracting said directional features so as to indicate a general direction which a corner formed by said intersection lines faces, and said step b3) comprising the step of extracting said convex/concave features so as to indicate whether a given one of said common edges is convex or concave.

3. The method as claimed in claim 1, wherein said step c) comprises the steps of:

c1) finding one or more neighboring edges for each one of said common edges based on said directional features and said convex/concave features, each of said one or more neighboring edges sharing the same intersecting horizontal plane with a corresponding one of said common edges;

c2) selecting one of said one or more neighboring edges to move from one of said common edges to a next one of said common edges so as to successively choose some of said common edges; and

c3) joining together points on said some of said common edges to form one of said boundaries.

4. The method as claimed in claim 3, wherein said step c1) comprises the step of finding a neighboring edge such that a direction indicated by said directional features shows a continuous displacement from a corresponding one of said common edges to said neighboring edge, and such that an evaluation function whose value increases with a decrease in steepness of said neighboring edge as well as an increase in a difference in height between said neighboring edge and said corresponding one of said common edges is less than a predetermined value.

5. The method as claimed in claim 3, wherein said step c2) comprises the steps of:

c2-1) assigning an evaluation function to a transition from a given one of said common edges to said one or more neighboring edges; and

c2-2) selecting said some of said common edges so as to minimize a total value of said evaluation function with regard to all transitions made in selecting said some of said common edges.

6. The method as claimed in claim 5, wherein said step c2-1) defines said evaluation function for a neighboring edge as a function whose value increases with a decrease in steepness of said neighboring edge as well as an increase in a difference in height between said neighboring edge and said given one of said common edges.

7. The method as claimed in claim 1, wherein said step a) comprises the steps of:

a1) generating triangles which approximate said curved surface represented by said gray-scale image; and

a2) integrating adjoining triangles into a polygon with regard to at least some of said triangles so as to generate said polygons.

8. The method as claimed in claim 7, wherein said step a2) integrates said adjoining triangles if said adjoining triangles have normal vectors having directions which fall within the same predetermined range.

9. The method as claimed in claim 1, further comprising the steps of:

classifying each of said boundaries into one of an outer boundary and an inner boundary; and

filling interiors of said document elements based on classification as to whether a given boundary is said outer boundary or said inner boundary.

10. A device for extracting features from a gray-scale image, said device comprising:

approximation means for generating polygons which approximate a curved surface represented by said gray-scale image;

feature-extraction means for extracting features with respect to common edges of adjoining polygons; and

boundary-extraction means for generating boundaries of document elements based on said features, wherein said feature-extraction means comprises,

means for cutting said surface by a horizontal plane to generate intersection lines between said horizontal plane and said polygons around each one of said common edges,

means for extracting directional features with respect to each one of said common edges based on said intersection lines, and

means for extracting convex/concave features with respect to each one of said common edges based on said intersection lines.

11. The method as claimed in claim 10, wherein said boundary-extraction means comprises:

means for finding one or more neighboring edges for each one of said common edges based on said directional features and said convex/concave features, each of said one or more neighboring edges sharing the same intersecting horizontal plane with a corresponding one of said common edges;

means for selecting one of said one or more neighboring edges to move from one of said common edges to a next one of said common edges so as to successively choose some of said common edges; and

means for joining together points on said some of said common edges to form one of said boundaries.

12. A computer usable medium having program code means embodied therein for causing a computer to extract features from a gray-scale image, said program code means comprising:

approximation means for generating polygons which approximate a curved surface represented by said gray-scale image;

feature-extraction means for extracting features with respect to common edges of adjoining polygons; and

boundary-extraction means for generating boundaries of document elements based on said features, wherein

said feature-extraction means comprises,

means for cutting said surface by a horizontal plane to generate intersection lines between said horizontal plane and said polygons around each one of said common edges;

means for extracting directional features with respect to each one of said common edges based on said intersection lines; and

means for extracting convex/concave features with respect to each one of said common edges based on said intersection lines.

13. The computer usable medium as claimed in claim 12, wherein said boundary-extraction means comprises:

means for finding one or more neighboring edges for each one of said common edges based on said directional features and said convex/concave features, each of said one or more neighboring edges sharing the same intersecting horizontal plane with a corresponding one of said common edges;

means for selecting one of said one or more neighboring edges to move from one of said common edges to a next one of said common edges so as to successively choose some of said common edges; and

means for joining together points on said some of said common edges to form one of said boundaries.