Model based pattern recognition

• US 5,123,057 A
• Filed: 06/21/1991
• Issued: 06/16/1992
• Est. Priority Date: 07/28/1989
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Williams, Bryan, Delanoy, Richard L., Verly, Jacques G.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/719,642
• Time in Patent Office: 361 Days
• Field of Search: 382/14, 382/15, 382/36, 382/37, 382/38, 382/39, 364/274.4, 364/275.9
• US Class Current: 382/156
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• CPC Class Codes: Y10S 706/90 Fuzzy logic

Abstract

A matching machine is provided for use in model-based entity recognition systems. Input to the matching machine includes a detected data event separated into portions and a set of predefined hierarchical models of desired entities. The matching machine employs recursive procedures to match data event portions against model parts, and records in list structures matches between event portions and model parts. For each match, a degree of match is calculated according to a function defining the involved model part. An essential feature of calculating a degree of match is the accumulation of working degrees of match (i.e. figures of merit reflecting the strength of match of a subset of data event portions to a subset of model parts and the degree to which the relationship of portions matches the predefined relationship of model parts in arbitrarily complex models). The degree of match is recorded in the list structures. From the highest degrees of match in the list structures, a best match between one of the models and the detected data event is determined.

Claims

1. Apparatus for matching sensory data to predetermined models of desired entities, each model having a plurality of model parts, the apparatus comprising:

processor means for determining for each model matches between different portions of sensory data of interest and different parts of the predetermined model by establishing for each model and each model part a list of processor calculated degrees of match for matches between sensory data portions and model parts of the model, different degrees of match in the list corresponding to different sensory data portions matched against different model parts of the model, in each match the different sensory data portions being matched against the model parts being related to each other in a similar manner that the different model parts are related to each other and the model, each list of degrees of match having degrees of match of various permutations of a subset of sensor data portions being matched to the model parts, each degree of match being calculated

(i) according to a weighted aggregation of working degrees of match between subsets of the sensory data portions associated with the degree of match and subsets of the model parts associated with the degree of match, the weighted aggregation including weights for indicating relative importance of a match between subsets of sensory data portions and subsets of model parts with respect to other matches, the weights being predefined for each model part in each model in a manner which enables scaling of matches between subsets of sensory data portions and subsets of model parts and enables matches to certain model parts to be deterministic of the sensory data, and

(ii) by taking into account at least one of;

(a) indications in the model parts of expected presence and absence of each model part in each match between subsets of sensory data portions and subsets of model parts,

(b) a predetermined reference degree of match for a model part, the reference degree of match being a neutral degree of match, and

(c) a set of predetermined values for the weights of each model part, the weight values indicating that portion of deviation of the working degree of match from a predetermined reference degree of match, to be included in the aggregation of working degrees of match; and

comparison processing means coupled to the processor means for determining a best match between the sensory data and one of the predetermined models by (i) establishing for each model a quantitative indication of belief of a match between the sensory data and that model based on at least a highest degree of match in the list of the processor calculated degrees of match of the model, and (ii) comparing the quantitative indications of the models to each other according to a predefined rule to determine one of the models to be the best match for the sensory data.

2. Apparatus as claimed in claim 1 wherein the processor means calculates a working degree of match between a sensory data portion and a model part according to functions defining the model part.

3. Apparatus as claimed in claim 1 wherein the comparison processing means compares the quantitative indications according to a predefined rule that determines the model with a greatest quantitative indication to be the best match for the sensory data.

4. Apparatus as claimed in claim 1 wherein for each degree of match in the list, the processor means calculates the degree of match according to a weighted aggregation of respective working degrees of match by (i) defining for each respective working degree of match a corresponding total degree of confidence, and (ii) combining the total degrees of confidence.

5. Apparatus as claimed in claim 4 wherein the processor means defines a total degree of confidence c'"'"' from a working degree of match according to the relationship ##EQU15## where γ

is a subset of model parts;

α

is in the set of parts or constraints of γ

;

x is a vector representation of model parts and sensory data portions being matched against each other;

PC.sub.γ

is the set of parts and constraints of γ

;

P.sub.γ

U C.sub.α

,γ

is the set of parts of γ and

active constraints of γ

;

space="preserve" listing-type="equation">c'"'"'.sub.γ

,max =Σ

W.sub.c,α

;

space="preserve" listing-type="equation">and

space="preserve" listing-type="equation">c'"'"'.sub.γ

, min=-Σ

W.sub.d,α

where W_c,α

is a confirming weight of α and

w_d,α

is a disconfirming weight of α

; and

##EQU16## where c.sub.α

is the normalized degree of confidence defined by ##EQU17## where n.sub.α

is a neutral degree of match which serves as the predetermined reference of degree of match and ##EQU18## and m.sub.α

is the degree of match of α and

defined for internal part γ

with a total degree of confidence c'"'"'.sub.γ

by ##EQU19##

6. Apparatus as claimed in claim 5 wherein the comparison processing means establishes a quantitative indication of belief of match between the sensory data portions and a predetermined model according to the Dempster-Shafer theory using the ratings r.sub.α

.

7. Apparatus as claimed in claim 1 wherein the processor means determines a subset of the models from which to match model parts to sensory data portions.

8. Apparatus as claimed in claim 1 wherein the model parts include constraints between other model parts;

and

the processor means calculates a degree of match for matches between sensory data portions and a subset of model parts having a constraint therebetween according to a weighted aggregation or working degrees of match between subsets of sensory data portions associated with the degree of match and the subsets of model parts having the constraint therebetween including an indication of satisfaction of the constraint for the matches between the sensory data portions and the model parts having the constraint therebetween.

26. Apparatus as claimed in claim 1 wherein the comparison processing means establishes a quantitative indication of belief of match between the sensory data portion and a predetermined model according to an evidence collection theory.

27. Apparatus as claimed in claim 1 wherein the processor means employs in each model part a confirming weight and a disconfirming weight as the weights included in the weighted aggregation to calculate the weighted aggregation of working degrees of match.

28. Apparatus as claimed in claim 8 wherein for each subset of model parts, the processor means includes in the weighted aggregation of corresponding working degrees of match, a factor indicating contribution of unmatched constraints for the subset of model parts.

29. Matching apparatus as claimed in claim 1 wherein the comparison processing means establishes a quantitative indication of belief of a match between an input event and a predetermined model according to Dempster-Shafer theory of evidence using a rating.

9. In an entity recognition system, apparatus for matching an input sensory data event having determined portions to predetermined models of entities desired to be recognized, each predetermined model having a plurality of model parts, the matching apparatus comprising:

processor means for determining for each predetermined model, matches between different event portions of the input sensory data event and different parts of the model by establishing a list or processor calculated degrees of match for matches between certain event portions and certain model parts of the model, different degrees of match in the list corresponding to different event portions matched against different model parts of the model, in each match the different event portions being matched against the model parts being related to each other in a similar manner that the different model parts are related to each other and the model, the list including degrees of matches for various permutations of a subset of event portions being matched to the model parts, each degree of match being calculated according to

(i) a weighted aggregation of working degrees of match between subsets of the event portions associated with the degree of match and subsets of the model parts associated with the degree of match, the weighted aggregation including weights for indicating relative importance of a match between subsets of event portions and subsets of model parts with respect to other matches, the weights being predefined for each model part in each model in a manner which enables scaling of matches between subsets of event portions and subsets of model parts and enables matches to certain model parts to be deterministic of the sensory data event, and

(ii) at least one of

(a) indications in each model part of expected presence and absence of the model part in each match between subsets of event portions and subsets of model parts,

(b) a predetermined reference degree of match for model part, the reference degree of match being a neutral degree of match, and

(c) a set of predetermined values for the weights of each model part, the weight values indicating that portion of deviation of the working degree of match from a predetermined reference degree of match, to be included in the aggregation of working degrees of match ;

and

comparison processing means coupled to the processor means for determining a best match between the input sensory data event and one of the predetermined models by (i) establishing for each model a quantitative indication of belief of a match between an input event and that model based on at least a highest degree of match in the list of processor calculated degrees of match of the model, and (ii) comparing the quantitative indications of the models to each other according to a predefined rule to determine one of the models to be the best match for the input event, the comparison processing means providing an indication of the one model to the entity recognition system such that the entity recognition system identifies the input event to be of an entity corresponding to the entity of the one model.

10. Matching apparatus as claimed in claim 9 wherein the processing means calculates a working degree of match according to functions defining the model parts.

11. Apparatus as claimed in claim 9 wherein the comparison processing means establishes a quantitative indication of belief of match between the sensory data event and a predetermined model according to an evidence collection theory.

12. Matching apparatus as claimed in claim 9 wherein the comparison processing means compares the quantitative indications according to a predefined rule that determines the model with a greatest quantitative indication to be the best match for an input event.

13. Matching apparatus as claimed in claim 9 wherein for each degree of match in the list, the processor means calculates the degree of match according to a weighted aggregation of respective working degrees of match by (i) defining for each respective working degree of match a corresponding rating, and (ii) combining the ratings.

14. Matching apparatus as claimed in claim 9 wherein the processor means recursively determines matches between different event portions and different model parts.

15. Matching apparatus as claimed in claim 9 wherein the processor means determines a subset of models from which to match model parts to event portions.

16. Apparatus as claimed in claim 9 wherein the model parts include constraints between model parts;

and

the processor means calculates a degree of match for a match between a subset of event portions and a subset of model parts having a constraint between certain ones of the model parts according to a weighted aggregation of working degrees of match between the vent portions and the model parts including an indication of satisfaction of the constraint for the matches between the event portions and the certain ones of the model parts.

30. Apparatus as claimed in claim 9 wherein for each model the processor means employs a confirming weight and a disconfirming weight as the weights included in the weighted aggregation to calculate the weighted aggregation of working degrees of match.

31. Apparatus as claimed in claim 16 wherein for each subset of model parts, the processor means includes in the weighted aggregation of corresponding working degrees of match, a factor indicating contribution of unmatched constraints for the subset of model parts.

17. A pattern recognition system comprising:

a plurality of models of entities of interest, the models being held in a model library, each model having a plurality of parts arranged in a hierarchy;

a source of data events of detected entities to be identified by the system;

a matching module adapted to receive a data event from the source and models from the model library to match the event to a model, the matching module having;

a) processor means for recursively determining, for each predetermined model, matches between different event portions of the data event and different parts of the model by establishing a list or processor calculated degrees of match between certain event portions and certain model parts of the model, different degrees of match in the list corresponding to different event portions matched against different parts of the model, in each match the different event portions being matched against the model parts being related to each other in a similar manner that the different model parts are related to each other and the model, the list of degrees of match having degrees of matches of various permutations of a subset of event portions being matched to the model parts, each degree of match being calculated according to

(i) a weighted aggregation of working degrees of match between subsets of the vent portions associated with the degree of match and subsets of the model parts associated with the degree of match, the weighted aggregation including weights for indicating relative importance of a match between subsets of event portions and subsets of model parts with respect to other matches, the weights being predefined for each model part in each model in a manner which enables scaling of matches between subsets of event portions and subsets of model parts and enables matches to certain model parts to be deterministic of the data event, and

(ii) at least one of

(A) indications in each model part of expected absence and presence of the model art in each match between subsets of event portions and subsets of model parts,

(B) a predetermined reference degree of match for a model part, the reference degree of match being a neutral degree of match, and

(C) a set of redetermined values for the weights of each model part, the weight value indicating that portion of deviation of the working degree of match from a predetermined reference degree of match, to be included in the aggregation working of degrees of match; and

b) comparison processing means coupled to the processor means for determining a best match between the data event and one of the models by (i) establishing for each model a quantitative indication of belief of a match between the vent and that model based on at least a highest degree of match in the list of processor calculated degrees of match of the model, and (ii) comparing the quantitative indications of the models to each other according to a predefined rule to determine one of the models to be the best match for the event; and

an output member coupled to the matching module for receiving from the comparison processing means an indication of the one model determined to be the best match for the data event from the source, the output member providing an indication of the entity corresponding to the one model to identify the detected entity of the event.

18. A system as claimed in claim 17 wherein the models are contour-based models.

19. A system as claimed in claim 17 wherein the models are region-based models.

20. A system as claimed in claim 17 wherein the processor means calculates a working degree of match between an event portion and a model part according to a function defining the model part.

21. A system as claimed in claim 17 wherein the comparison processing means compares the quantitative indications according to a predefined rule that determines the model with a greatest quantitative indication to be the best match for the data event.

22. A system as claimed in claim 17 wherein the processor means determines a subset of models from which to match model parts to event portions.

23. A system as claimed in claim 17 wherein for each degree of match in the list, the processor means calculates the degree of match according to a weighted aggregation of respective working degrees of match by (i) defining for each respective working degree of match a corresponding rating, and (ii) combining the ratings.

24. A system as claimed in claim 17 wherein the model parts include constraints between other model parts.

32. Apparatus as claimed in claim 17 wherein the comparison processing means establishes a quantitative indication of belief of match between a data event and a predetermined model according to an evidence collection theory.

33. Apparatus as claimed in claim 17 wherein for each model part the processor means employs confirming and disconfirming weights as the weights included in the weighted aggregation to calculate the weighted aggregation of working degrees of match.

34. Apparatus as claimed in claim 24 wherein for each subset of model parts, the processor means includes in the weighted aggregation of corresponding working degrees of match, a factor indicating contribution of unmatched constraints for the subset of model parts.

25. A method of matching sensory data to predetermined models of desired entities, each model having a plurality of model parts, the method comprising the steps of:

determining for each model matches between different portions of sensory data of interest and different parts of the predetermined model by establishing for the model a list or processor calculated degrees of match between sensory data portions and model parts of the model, different degrees of match in the list corresponding to different sensory data portions matched against different model parts of the model, in each match the different sensory data portions being match against the model parts being related to each other in a similar manner that the different model parts are related to each other and the model, the list of degrees of match having degrees of match of various permutations of a subset of sensory data portions being matched to the model parts, each degree of match being calculated according to

(i) a weighted aggregation of working degrees of match between subsets of the sensory data portions associated with the degree of match and subsets of the model parts associated with the degree of match, the weighted aggregation including weights for indicating relative importance of a match between subsets of sensory data portions and subsets of model parts with respect to other matches, the weights being predefined for each model part in each model in a manner which enables scaling of matches between subsets of sensory data portions and subsets of model parts and enables matches to certain model parts to be deterministic of the sensory data, and

(ii) at least one of (a) indications in each model part of expected presence and absence of the model part in each match between subsets of sensory data portions and subsets of model parts,

(b) a predetermined reference degree of match for a model part, the reference degree of match being a neutral degree of match; and

(c) a set of predetermined values for the weights of each model part, the weight values indicating that portion of deviation of the working degree of match from a predetermined reference degree of match, to be included in the aggregation of working degrees of match; and

determining a best match between the sensory data and one of the predetermined models by (i) establishing for each model a quantitative indication of belief of a match between the sensory data and that model based on at least a highest degree of match in the list of the processor calculated degrees of match of the model, and (ii) comparing the quantitative indications of the models to each other according to a predefined rule to determine one of the models to be the best match for the sensory data.

35. Apparatus for matching sensory data to predetermined models of desired entities comprising:

(a) processor means for determining for each model matches between different portions of sensory data of interest and different parts of the predetermined model by establishing for each model a list of processor calculated degrees of match between sensory data portions and model parts of the model, different degrees of match in the list corresponding to different sensory data portions matched against different model parts of the model, each degree of match being calculated according to an aggregation of working degrees of match between subsets of the sensory data portions associated with the degree of match and subsets of the model parts associated with the degree of match, in each match the different model parts being related to each other and the model in a similar manner that the different sensory data portions being matched against the model parts are related to each other and the whole sensory data, and each degree of match being calculated according to an aggregation of respective working degrees of match by (i) defining for each respective working degree of match a corresponding total degree of confidence c'"'"' according to the relationship ##EQU20## where is a subset of model parts;

is in the set of parts or constraints of γ

;

x is a vector representation of model parts and sensory data portions being matched against each other;

PC.sub.γ

is the set of parts and constraints of γ

;

P.sub.γ

U C_a,γ

is the set of parts of γ and

active constraints of γ

;

space="preserve" listing-type="equation">c'"'"'.sub.γ

,max =Σ

W.sub.c,α

;

space="preserve" listing-type="equation">and

space="preserve" listing-type="equation">c'"'"'.sub.γ

,min =-Σ

W.sub.d,α

where W_c,α

is a confirming weight of α and

W_d,α

is a disconfirming weight of α

; and

##EQU21## and (ii) combining the total degrees of confidence; and

(b) comparison processing means coupled to the processor means for determining a best match between the sensory data and one of the predetermined models by (i) establishing for each model a quantitative indication of belief of a match between the sensory data and that model based on at least a highest degree of match in the list of the processor calculated degrees of match of the model, and (ii) comparing the quantitative indications of the models to each other according to a predefined rule to determine one of the models to be the best match for the sensory data.