Computer apparatus and method for fuzzy template shape matching using a scoring function

• US 5,222,155 A
• Filed: 06/15/1992
• Issued: 06/22/1993
• Est. Priority Date: 03/26/1991
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Delanoy, Richard L., Verly, Jacques G.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US07/899,107
• Time in Patent Office: 372 Days
• Field of Search: 382/30, 382/34, 382/41, 382/48
• US Class Current: 382/215
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
• CPC Class Codes: Y10S 706/90 Fuzzy logic

Abstract

Computer apparatus and method in a computer system provides shape matching. A template of a desired shape is matched to a subset of points in a subject image. The matching is determined according to an arbitrarily complex function of image point values and template point values followed by an arbitrary operation on the plurality of results of the arbitrarily complex function. In the case of fuzzy template matching, the operation is the average preferably followed by clipping to the range [0, 1] for defining fuzzy membership values. The arbitrarily complex function may be formed of a discrete array of single variable functions or single variable lookup tables.

Claims

1. Computer apparatus for shape matching comprising:

a digital processor;

a template coupled to the digital processor and indicative of a desired shape, the template having a plurality of points, each point having a predetermined value;

a working memory area coupled to the digital processor for holding a subject image formed of a plurality of points, each point of the image having a respective measurement value; and

processor means executable by the digital processor for matching the template to a subset of points of the subject image held in the working memory area and generating an output image having a plurality of points with each output image point having a respective output image value, for each point in the subject image, the processor means determining the output image value at a corresponding point in the output image according to a scoring function that operates on measurement values of a subset of points in the subject image and predetermined values of points in the template, the measurement values of a subset of the points for the subject image being derived from a first function and the predetermined values of points in the template being derived from a second function, the values derived from the first function and the second function being used in pairs as inputs to the scoring function that encodes physical characteristics of the desired shape indicated by the template and that returns a numeric score reflecting a degree of correlation between the subject image and the template.

2. Computer apparatus as claimed in claim 1 wherein the template further provides, for each template point, an arbitrarily complex function used by the processor means as an input to the scoring function to determine the values at the output image points.

3. Computer apparatus as claimed in claim 1 wherein the scoring function is formed of a plurality of one variable functions.

4. Computer apparatus as claimed in claim 3 wherein the plurality of one variable functions includes one function for each possible predetermined value of a template point.

5. Computer apparatus as claimed in claim 1 wherein the processor means further determines the output image value at a corresponding output image point according to an arbitrarily complex operation on a multiplicity of results from the scoring function.

6. Computer apparatus as claimed in claim 5 wherein the operation (a) includes an average of the results from the scoring function over the number of points in the template, and (b) generates an output image point value in one of the rang e0 to 1 and a set of values mapped to the range 0 to 1.

7. Computer apparatus as claimed in claim 5 wherein:

for each point in the subject image, a multiplicity of templates are used by the processor means, each template (i) having a plurality of points with respective predetermined values, and (ii) providing a respective scoring function of measurement values of a subset of subject image points and predetermined values of points in the template; and

the operation includes a merge of operation results across the multiplicity of templates.

8. Computer apparatus as claimed in claim 1 wherein for each, point in the subject image, the template and scoring function are defined according to the subject image point.

9. Computer apparatus as claimed in claim 1 wherein for each point in the subject image, the template and scoring function are defined according to values of image points neighboring the subject image point.

10. Computer apparatus as claimed in claim 1 wherein:

the template includes (i) a first template indicative of shape of a main part of the subject image, and (ii) a second template indicative of shape of a pivotal part that pivots from a point in the main part in the subject image; and

the processing means matches shape of the first template to a subset of points of the subject image to determine a pivot point in the subject image, and matches shape of the second template to subsets of points of the subject image within pivoting range from the determined pivot point to determine articulating portions of the subject image.

11. In a computer system having (i) a digital processor, (ii) a template coupled to the digital processor for indicating a desired shape and having a plurality of points, each point having a predetermined value, and (iii) a working memory area coupled to the digital processor for holding a subject image formed of a plurality of points, each image point having a respective measurement value, computer apparatus comprising:

processor means executable by the digital processor for matching the template to a subset of points of the subject image held in the working memory area and generating an output image having a plurality of points with each output image point having a respective output image value, for each point in the subject image, the processor means determining the output image value at a corresponding point in the output image according to a scoring function that operates on measurement values of a subset of points in the subject image and predetermined values of points in the template, the measurement values of a subset of points for the subject image being derived from a first function and the predetermined values of points in the template being derived from a second function, the values derived from the first function and the second function being used in pairs as inputs to the scoring function that encodes physical characteristics of the desired shape indicated by the template and that returns of numeric score reflecting a degree of correlation between the subject image and the template.

12. Computer apparatus as claimed in claim 11 wherein the scoring function is formed of a plurality of one variable functions.

13. Computer apparatus as claimed in claim 12 wherein the plurality of single variable functions include one function for each possible predetermined value of a template point.

14. Computer apparatus as claimed in claim 11 wherein the processor means further determines output image value at a corresponding output image point according to an arbitrarily complex operation on a multiplicity of results from the scoring function.

15. Computer apparatus as claimed in claim 14 wherein the operation (a) includes an average of the results from the scoring function over the number of points in the template, and (b) generates an output image point value in one of the range 0 to 1 and a set of values mapped to the range 0 to 1.

16. Computer apparatus as claimed in claim 14 wherein the template includes a multiplicity of templates and the operation includes a merge of operation results across templates.

17. Computer apparatus as claimed in claim 11 wherein for each point in the subject image, the template and scoring function are defined according to the subject image point.

18. Computer apparatus as claimed in claim 11 wherein for each point in the subject image, the template and scoring function are defined according to values of image points neighboring the subject image point.

19. Computer apparatus as claimed in claim 11 wherein:

the template includes (i) a first template indicative of shape of a main part of the subject image, and (ii) a second template indicative of shape of a pivotal part that pivots from a point in the main part in the subject image; and

the processing means matches shape of the first template to a subset of points of the subject image to determine a pivot point in the subject image, and matches shape of the second template to subsets of points of the subject image within pivoting range from the predetermined pivot point to determine articulating portions of the subject image.

20. In a computer system having a processor, a method for shape matching comprising the steps of:

providing to the processor at least one template of a desired shape, the template having a plurality of points each point having a predetermined value;

holding in a working memory area of the processor, a subject image formed of a plurality of points, each image point having a respective measurement value;

determining for each point in the subject image a value at a corresponding point in an output image according to a scoring function that operates on measurement values of a subset of image points and the predetermined values of points in the template, the measurement values of a subset of points for the subject image being derived from a first function and the predetermined values of points in the template being derived from a second function, the values derived from the first function and the second function are used in pairs as inputs to the scoring function that encodes physical characteristics of the desired shape indicated by the template and that returns a numeric score reflecting a degree of correlation between the subject image and the template;

applying a mathematical operation of the numeric scores generated from the scoring function;

matching the shape of the template to a subset of points of the subject image held in the working memory area according to the mathematical operation and the scoring function; and

generating the output image having a plurality of points, each output image point having the respective value determined by the scoring function and mathematical operation.

21. A method as claimed in claim 20 wherein the step of determining values of a corresponding point in the output image includes:

using a plurality of one variable functions to define the scoring function.

22. A method as claimed in claim 20 wherein the step of mathematically operating on results includes (1) averaging the results from the scoring function over the number of points in the template, and (2) clipping the average to a value in the range 0 to 1 to define a corresponding output image point value.

23. A method as claimed in claim 22 wherein:

the step of providing at least one template includes providing a multiplicity of templates, each template (i) having a plurality of points with respective predetermined values, and (ii) providing a respective arbitrarily complex function of measurement values of a subset of subject image points and predetermined values of points in the template; and

the step of determining value at a corresponding point includes merging operation results across the templates.

24. A method as claimed in claim 20 wherein:

the step of providing a template includes providing (i) a first template indicative of shape of a main part of the subject image, and (ii) a second template indicative of shape of a pivotal part that pivots from a point in the main part in the subject image; and

the step of determining includes matching shape of the first template to a subset of points of the subject image to determine a pivot point in the subject image, and matching shape of the second template to subsets of points of the subject image within pivoting range from the determined pivot point to determine articulating portions of the subject image.

25. Computer apparatus for shape matching comprising:

a digital processor;

a template coupled to the digital processor and indicative of a desired shape, the template having a plurality of points wherein each point has a predetermined value, the template including (i) a first template indicative of a shape of a main part of the subject image, and (ii) a second template indicative of a shape of a pivotal part that pivots from a point in the main part in the subject image;

a working memory area coupled to the digital processor for holding a subject image formed of a plurality of points, each point of the image having a respective measurement value; and

processor means executable by the digital processor for matching a the template to a subset of points of the subject image held in the working memory area, the processing means matching the shape of the first template to a subset of points of the subject image to determine a pivot point in the subject image, and matching the shape of the second template to subsets of points of the subject image within pivoting range from the determined pivot point to determine articulating portions of the subject image, said matching generating an output image having a plurality of points and each output image point having a respective output image value, for each point in the subject image, the processor means determining the output image value at a corresponding point in the output image according to a scoring function that operates on measurement values of a subset of points in the subject image and predetermined values of points in the template.

26. In a computer system having (i) a digital processor for indicating a desired shape and having a plurality of points, each point having a predetermined value, the template including a first template indicative of a shape of a main part of the subject image, and a second template indicative of a shape of a pivotal part that pivots from a point in the main part in the subject image and (iii) a working memory area coupled to the digital processor for holding a subject image formed of a plurality of points, each image point having a respective measurement value, computer apparatus comprising:

processor means executable by the digital processor for matching the template to a subset of points of the subject image held in the working memory area, the processor matching the shape of the first template to a subset of points of the subject image to determine a pivot point in the subject image, and matching the shape of the second template to subset of points of the subject image within pivoting range from the determined pivot point to determine articulating portions of the subject image, said matching generating an output image having a plurality of points, each output image points having a respective output image value, for each point in the subject image, the processor means determining the output image value at a corresponding point in the output image according to a scoring function that operates on measurement values of a subset of points in the in the template, measurement values of a subset of points for the subject image being defined by a first function having at least one variable, and the predetermined values of points in the template being defined by a second function having a variable in common with one of the variables of the first function, the first function and the second function being operands, respectively, for the scoring function.

27. In a computer system having a processor, a method for shape matching comprising the steps of:

providing to the processor at least one template of a desired shape, the template having a plurality of points each point having a predetermined value, the template including a first template indicative of a shape of the subject image, and a second template indicative of a shape of a pivotal part that pivots from a point in the main part in the subject image;

holding in a working memory area of the processor, a subject image formed of a plurality of points, each image point having a respective measurement value;

determining for each point in the subject image a value at a corresponding point in an output image according to a scoring function that operates on measurement values of a subset of image points and the predetermined values of points in the template, measurement values of a subset of points for the subject image being defined by a first function having at least one variable, and the predetermined values of points in the template being defined by a second function having a variable in common with one of the variables of the first function, the first function and the second function being used as operands, of the scoring function;

matching the shape of the template to a subset of points of the subject image held in the working memory area, the shape of the first template is matched to a subset of points of the subject image to determine a pivot point in the subject image, and the shape of the second template is matched to a subset of points of the subject image within pivoting range from the determined pivot point to determine articulating portions of the subject image; and

generating the output image having a plurality of points, each output image point having the respective value determined by the scoring function.

28. Computer apparatus for shape matching comprising:

a digital processor;

a template coupled to the digital processor and indicative of a desired shape, the template having a plurality of points, each point having a predetermined value;

a working memory area coupled to the digital processor for holding a subject image formed of a plurality of points, each point of the image having a respective measurement value; and

processor means executable by the digital processor for matching the template to a subset of points of the subject image held in the working memory area and generating an output image having a plurality of points with each output image point having a respective output image value, for each point in the subject image, the processor means determining the output image value at an output image point corresponding to a subject image point, the output image values reflecting a degree of match between values of the subset of points in the subject image and values of points in the template, wherein each point in the subset of points in the subject image corresponds to a point in the template, the degree of match being obtained by applying an arbitrary operation to a set of numeric scores generated by a scoring function, said scoring function operating on the measurement values of the subset of points in the subject image and the predetermined values of points in the template to produce a numeric score reflecting a degree of correlation between subset of points in the template and corresponding points in the subject image, the measurement values of the subset of points for the subject image being derived from a first function and the predetermined values of points in the template being derived from a second function, the values derived from the first function and the second function being used in pairs as inputs to the scoring function for encoding expectations of measurement values for points in the subject image corresponding to subset of points in the template.