Model based pattern recognition
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
122 Citations
35 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 26, 27, 28, 29)
-
-
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 ;
andcomparison 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. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 30, 31)
-
-
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. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 32, 33, 34)
-
-
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 Ca,γ
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 Wc,α
is a confirming weight of α and
Wd,α
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.
Specification