Pattern matching
View Patent ↗A method of determining whether two patterns having a plurality of homologous regions match, comprising: generating a set of decisions associated with values (k,n) for determining whether the patterns match, where k, is a number of non similar homologous regions from a sample of size, n, of the homologous regions; constraining the decisions so that a probability of providing a false negative decision that there is no match when in fact there is a match is less than or equal to a predetermined upper bound; configuring the association of decisions and pairs (k,n) to minimize running time of a computer programmed to use the set of decisions to determine whether there is a match; and using a computer programmed with the set of decisions to determine if the patterns match.
1. A method of determining whether two images having a plurality of homologous pixels match, comprising:
generating a set of decisions associated with values (k,n) for determining whether the images match, where k, is a number of non similar pixels from a sample of size, n, of the pixels;
constraining the decisions so that a probability of providing a false negative decision that there is no match when in fact there is a match is less than or equal to a predetermined upper bound α and that a Bayesian probability of providing a false positive decision that there is a match, when there is no match, is less than or equal to a predetermined upper bound β;
configuring the association of decisions and pairs (k,n) to minimize a loss function responsive to a running time of a computer programmed to use the set of decisions in a sequential series of statistical hypothesis test to determine whether there is a match, wherein the loss function comprises a sum of an expected running time, a weighted probability of providing a false positive decision.
2. A method according to claim 1 wherein the set of decisions comprises:
a decision, NS, that the images do not match associated with each of a first set of pairs of values (k,n) and having a probability less than or equal to α; and
a decision, C, for each of a second set of pairs of values (k,n) that the sample n must be increased to determine whether the images match.
3. A method according to claim 1 wherein the probability of being wrong and providing a false negative decision is determined responsive to a prior probability for frequency of occurrence of regions that are not similar.
4. A method according to claim 2 wherein the set of decisions comprises a decision, S, associated with a third set of pairs of values (k,n) that the images match.
5. A method according to claim 4 wherein S has a probability of being incorrect and providing a false positive decision that there is a match when in fact there isn't, has a probability less than or equal to a predetermined upper bound β.
6. A method according to claim 5 wherein the probability of a decision S being wrong is determined responsive to a prior probability for frequency of occurrence of pixels that are not similar.
7. A method according to claim 4 and comprising a decision E to determine how many non-similar homologous pixels there are from among all the homologous pixels associated with a fourth set of values (k,n).
8. A method according to claim 7 wherein all the decisions NS, S and E are associated with pairs of values (k,n) having a same n.
9. A method according to claim 1 and comprising a decision E to determine how many non-similar pixels there are from among all the pixels associated with a fourth set of values (k,n).
10. A method according to claim 1 wherein the association of decisions and pairs (k,n) are configured to minimize a loss function responsive to the running time.
11. A method according to claim 10 wherein the loss function comprises a sum of an expected running time, a weighted probability of providing a false negative decision and a weighted probability of providing a false positive decision.
12. A method according to claim 11 wherein the weight for the false negative probability is less than or equal to R E(0) /[αP(D≦t)] where R E(0) is a running time for the computer to determine how many non-similar pixels from among all the pixels and P(D≦t) is a probability that the patterns in fact match.
13. A method according to claim 12 wherein the weight for the false positive probability is less than or equal to R E(0) /[βP(D>t) where P(D>t) is a probability that the patterns in fact do not match.
14. A set of decisions for determining whether first and second images having a plurality of pixels match responsive to a number, k, of non similar pixels from a sample of size, n, of the pixels, the set of decisions comprising:
a computer processor;
a memory;
a decision, NS, that the second images do not match associated with each of a first set of pairs of values (k,n) and having a probability less than or equal to a predetermined upper bound a of being wrong and providing a false negative decision when in fact there is a match; and
a decision, C, for each of a second set of pairs of values (k,n) that the sample n must be increased to determine whether the second images match,
wherein the decisions are constrained so that a Bayesian probability of providing a false negative decision that there is no match when in fact there is a match is less than or equal to a predetermined upper bound α and that a Bayesian probability of providing a false positive decision that there is a match, when there is no match, is less than or equal to a predetermined upper bound β,
wherein the association of decisions and pairs (k,n) is configured to minimize a loss function responsive to a running time of a computer programmed to use the set of decisions in a sequential series of statistical hypothesis test to determine whether there is a match, wherein the loss function comprises a sum of an expected running time, a weighted probability of providing a false positive decision, and
wherein the decisions are stored on the memory and are executed by the computer processor.
15. A set of decisions according to claim 14 and comprising a decision E to determine how many non-similar pixels there are from among all the the pixels associated with a third set of values (k,n).
16. A set of decisions according to claim 15 wherein all the decisions NS, E, and a decision, S that the second images match, associated with a fourth set of pairs of values (k,n), are associated with pairs of values (k,n) having a same n.
17. A set of decisions according to claim 14 wherein the images are images comprised in a temporal sequence of events.
18. A method according to claim 17 wherein the sequence of events comprises an audio stream.
19. A non-transitory computer readable medium containing a set of decisions in accordance with claim 14 for programming a processor to determine if two images match.
20. A non-transitory computer readable medium containing a set of instructions for programming a processor to determine if two images match in accordance with claim 1 .
21. A non-transitory computer readable medium containing a set of instructions for determining if two images match in accordance with claim 1 .