Identifying curves within a scanned image

• US 5,339,367 A
• Filed: 12/02/1992
• Issued: 08/16/1994
• Est. Priority Date: 12/02/1992
• Status: Expired due to Fees

• Current Assignee: National Research Council Canada
• Original Assignee: National Research Council Canada
• Inventors: Roth, Gerhard
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/984,501
• Time in Patent Office: 622 Days
• Field of Search: 382/22, 382/1, 382/54, 382/55, 382/41, 382/60, 382/25
• US Class Current: 382/199
• CPC Class Codes: G06F 18/00 Pattern recognition

Abstract

A method is provided for identifying and locating curves within a digitized image. Digitized images are comprised of points which may represent curves stored as an array of binary coded elements in an memory device. Each addressable memory location in the array represents a single point or pixel. Particular curves within a scanned image are identified by randomly selecting a minimal subset of points which are necessary to generate a general equation for that curve; the equation along with a point on the curve is then used as in input parameter to an incremental curve generation routine which incrementally generates all points which are in a path along that curve. A comparison is made with scanned data to determine how many points exist along the path. This is repeatedly done until the curve with the greatest number of points is located.

Claims

1. A method of identifying a curve represented by points, each of the points being stored in a binary form in a unique, addressable location in a random access memory array, comprising the steps of:

a) sampling the binary data in the random access memory array to obtain a plurality of sampled points;

b) using a minimal subset of the sampled points as seed values for generating an equation for a curve that intersects the sampled points;

c) determining the number of points in the random access memory array that lie on a path of a predetermined width w corresponding to the curve defined by the equation; and

,

d) repeating steps (a) to (c) and selecting the curve lying on the path of width w having the greatest number of corresponding points determined in step (c).

2. A method as defined in claim 1 wherein the sampling step is performed by randomly sampling the binary data.

3. A method as defined in claim 1 wherein the step of determining the location of all the addressable memory locations in the array which lie in a path of width w is performed by a method of incremental curve generation.

4. A method as defined in claim 1 wherein the plurality of samples is comprised of a number corresponding to a minimal number required to define an equation for a particular curve.

5. A method of identifying a curve represented by points, each of the points being stored in a binary form in a unique, addressable location in a memory array, comprising the steps of:

a) generating an equation for a curve using a minimal subset of sampled points;

b) determined the number of points in the random access memory array that lie on a path of a predetermined width w, corresponding to the curve defined by the equation; and

c) repeating steps (a) to (b) and selecting the curve lying on the path of width w having the greatest number of corresponding points determined in step (b).

6. A method of identifying a curve represented by a plurality of numbers, a difference in any two numbers representing a difference in the brightness in the array, each of the numbers being stored in an addressable location in a random access memory array, the method comprising the steps of:

a) generating an equation for a curve;

b) determining the location of all the addressable memory locations in the random access memory array which lie on a path corresponding to the curve defined by the equation;

c) summing the values of the differences in brightness of the points that lie within the path; and

,

repeating steps (a) to (c) and selecting a curve defined by points stored in the random access memory corresponding to the the greatest summed value in step (c).

7. A method of identifying a curve represented by a plurality of numbers, a difference in any two numbers representing a difference in the brightness in the array, each of the numbers being stored in an addressable location in a random access memory array, the method comprising the steps of:

a) generating an equation for a curve;

b) determining the location of all the addressable memory locations in the random access memory array which lie on a path of width w corresponding to the curve defined by the equation, w being a predetermined number;

c) determining the number of points in the array that lie within the path of width w; and

,

repeating steps (a) to (c) and selecting the path with the greatest number of points.

8. A method of identifying a curve represented by points, each of the points being stored in a binary form in a unique, addressable location of a random access memory array, comprising the steps of:

a) sampling the binary data in the random access memory array to obtain a plurality of indicia corresponding to sampled points;

b) generating an equation for a curve which intersects the sampled points;

c) determining the number all the addressable memory locations in the array which lie on the curve defined by the equation, wherein the curve is of a predetermined width w;

d) determining the number of points in the random access memory array that lie on the curve of width w; and

,

comparing the number in step (c) with the number in step (d).

9. A method as defined in claim 8 wherein the comparing in step (d) is done repeatedly until the ratio of the numbers compared are at least a predetermined number.