Fault-Aware Matched Filter and Optical Flow

• US 20110116584A1
• Filed: 05/27/2010
• Published: 05/19/2011
• Est. Priority Date: 05/27/2009
• Status: Active Grant

• Current Assignee: Prioria Robotics
• Original Assignee: Prioria Robotics
• Inventors: Hunt, Walter Lee Jr.
• Granted Patent: US 8,977,665 B2
• Time in Patent Office: Days
• US Class Current: 375/350
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06V 10/98 Detection or correction of errors, e.g. by rescanning the pattern or by human intervention; Evaluation of the quality of the acquired patterns
• CPC Class Codes: H03H 17/0248 Filters characterised by a particular frequency response or filtering method
• CPC Class Codes: H03H 17/0254 Matched filters

Abstract

In one embodiment, a fault-aware matched filter augments the output of a component matched filter to provide both fault-aware matched filter output and a measure of confidence in the accuracy of the fault-aware matched filter output. In another embodiment, an optical flow engine derives, from a plurality of images, both optical flow output and a measure of confidence in the optical flow output. The measure of confidence may be derived using a fault-aware matched filter.

Claims

1. A method comprising:

(A) applying a first filter to a data vector and a set R, the set R containing at least one reference vector, to produce first filter output representing a measure of similarity of the data vector to at least one reference vector in the set R;

(B) applying a second filter to second filter inputs to produce second filter output, wherein the first filter has at least one failure mode not shared by the second filter;

(C) deriving, from the first filter output and the second filter output, confidence estimate output representing a degree of confidence in the correctness of the first filter output.

2. The method of claim 1, further comprising:

(D) applying an output transformation function to the first filter output to produce a third filter output, wherein the confidence estimate output represents a degree of confidence in the correctness of the third filter output; and

(E) providing the third filter output and the confidence estimate output as output.

3. The method of claim 1, wherein the first filter inputs are the same as the second filter inputs.

4. The method of claim 1, wherein the second filter inputs are disjoint from the first filter inputs.

5. The method of claim 1, wherein the second filter inputs include both the first filter inputs and additional filter inputs not contained within the first filter inputs.

6. The method of claim 1, wherein the set R contains a plurality of reference vectors, and wherein the first filter output comprises a first plurality of measures of similarity specifying, for each reference vector V in the set R, a strength of a match between the data vector and the reference vector V, and

wherein (C) comprises selecting a first one of the first plurality of measures of similarity and deriving the confidence estimate output from the first one of the first plurality of measures of similarity and the second filter output.

7. The method of claim 6, wherein the set R contains a plurality of reference vectors, and wherein the second filter output comprises a second plurality of measures of similarity specifying, for each reference vector V in the set R, a strength of a match between the data vector and the reference vector V, and

wherein (C) comprises selecting a second one of the plurality of measures of similarity and deriving the confidence estimate output from the first one of the first plurality of measures of similarity and the second one of the second plurality of measures of similarity.

8. The method of claim 6, wherein (C) comprises:

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity;

(C)(2) identifying a second-highest match strength PK2 among the first plurality of measures of similarity;

(C)(3) identifying a quotient PK1/PK2; and

(C)(4) identifying the confidence estimate output based on PK1 and PK1/PK2.

9. The method of claim 6, wherein (C) comprises:

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity;

(C)(2) identifying a second-highest match strength PK2 among the first plurality of measures of similarity;

(C)(3) identifying a difference PK1-PK2; and

(C)(4) identifying the confidence estimate output based on PK1 and PK1-PK2.

10. The method of claim 6, wherein (C) comprises:

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity;

(C)(2) identifying an average AVG of the first plurality of measures of similarity;

(C)(3) identifying a quotient PK1/AVG; and

(C)(4) identifying the confidence estimate output based on PK1 and PK1/AVG.

11. The method of claim 6, wherein (C) comprises:

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity;

(C)(2) identifying an average AVG of the first plurality of measures of similarity;

(C)(3) identifying a difference PK1-AVG; and

(C)(4) identifying the confidence estimate output based on PK1 and PK1-AVG.

12. The method of claim 6, wherein (C) comprises:

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity;

(C)(2) identifying an average AVG of the first plurality of measures of similarity;

(C)(3) identifying a standard deviation DEV of the first plurality of measures of similarity;

(C)(3) identifying a quotient PK1/(AVG+k*DEV), wherein k is a constant; and

(C)(4) identifying the confidence estimate output based on PK1 and (PK1/(AVG+k*DEV)).

13. The method of claim 6, wherein (C) comprises:

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity;

(C)(2) identifying an average AVG of the first plurality of measures of similarity;

(C)(3) identifying a standard deviation DEV of the first plurality of measures of similarity;

(C)(3) identifying a difference PK1−

(AVG+k*DEV), wherein k is a constant; and

(C)(4) identifying the confidence estimate output based on PK1 and (PK1−

(AVG+k*DEV)).

14. The method of claim 6, wherein MSV[i] indicates a match strength at index i within the match strength vector, wherein R[i] indicates a reference vector at index i within the plurality of ordered reference vectors, and wherein (C) comprises:

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity, wherein PK1 is the match strength of MSV[j];

(C)(2) identifying a match strength PK_L, wherein PK_L is the maximum of match strengths MSV[j+RAD+1] and MSV[j−

RAD−

1], for a predetermined value of RAD;

(C)(3) identifying a quotient PK1/PK_L; and

(C)(4) identifying the confidence estimate output based on PK1 and PK1/PK_L.

15. The method of claim 6, wherein MSV[i] indicates a match strength at index i within the match strength vector, wherein R[i] indicates a reference vector at index i within the plurality of ordered reference vectors, and wherein (C) comprises:

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity, wherein PK1 is the match strength of MSV[j];

(C)(2) identifying a match strength PK_L, wherein PK_L is the maximum of match strengths MSV[j+RAD+1] and MSV[j−

RAD−

1], for a predetermined value of RAD;

(C)(3) identifying a difference PK1-PK_L; and

(C)(4) identifying the confidence estimate output based on PK1 and PK1-PK_L.

16. The method of claim 6, wherein MSV[i] indicates a match strength at index i within the match strength vector, wherein R[i] indicates a reference vector at index i within the plurality of ordered reference vectors, wherein 0≦

i<

N, and wherein (C) comprises;

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity, wherein PK1 is the match strength of MSV[j];

(C)(2) determining whether j>

0;

(C)(3) determining whether j<

N−

1; and

(C)(4) identifying the confidence estimate output based on PK1 and whether j>

0 and whether j<

N−

1.

17. The method of claim 6, wherein MSV[i] indicates a match strength at index i within the match strength vector, wherein R[i] indicates a reference vector at index i within the plurality of ordered reference vectors, wherein 0≦

i<

N, and wherein (C) comprises;

(C)(1) identifying a peak match strength PK1 among the first plurality of measures of similarity, wherein PK1 is the match strength of MSV[j];

(C)(2) determining whether j>

RAD, for a predetermined value of RAD>

0;

(C)(3) determining whether j<

N−

RAD−

1; and

(C)(4) identifying the confidence estimate output based on PK1 and whether j>

RAD and whether j<

N−

RAD−

1.

18. The method of claim 1, wherein the first filter comprises a plurality of filters.

19. The method of claim 1, wherein the second filter comprises a plurality of filters.

20. The method of claim 1, wherein (C) comprises:

(C)(1) selecting a first one of the first filter output and the second filter output as a first intermediate filter output;

(C)(2) selecting a second one of the first filter output and the second filter output as a second intermediate filter output, wherein the first and second intermediate filter outputs differ from each other;

(C)(3) deriving the confidence estimate output from the first intermediate filter output and the second intermediate filter output;

(C)(4) applying an output transformation function to the first intermediate filter output to produce a third filter output, wherein the confidence estimate output represents a degree of confidence in the correctness of the third filter output; and

(C)(5) providing the third filter output and the confidence estimate output as output.

21. The method of claim 20:

wherein (C)(1) comprises selecting the first intermediate filter output based on at least one input other than the data vector and the set R; and

wherein (C)(2) comprises selecting the second intermediate filter output based on the at least one input other than the data vector and the set R.

22. A system comprising:

a first filter comprising means for producing first filter output representing a measure of similarity of a data vector to at least one reference vector in a set R, wherein the set R contains at least one reference vector;

a second filter comprising means for producing second filter output based on second filter inputs, wherein the first filter has at least one failure mode not shared by the second filter; and

confidence estimate output means for deriving, from the first filter output and the second filter output, confidence estimate output representing a degree of confidence in the correctness of the first filter output.

23. The system of claim 22, further comprising:

output transformation means for applying an output transformation function to the first filter output to produce a third filter output, wherein the confidence estimate output represents a degree of confidence in the correctness of the third filter output; and

output provision means for providing the third filter output and the confidence estimate output as output.

24. The system of claim 22, wherein the first filter inputs are the same as the second filter inputs.

25. The system of claim 22, wherein the second filter inputs are disjoint from the first filter inputs.

26. The system of claim 22, wherein the second filter inputs include both the first filter inputs and additional filter inputs not contained within the first filter inputs.

27. The system of claim 22, wherein the set R contains a plurality of reference vectors, and wherein the first filter output comprises a first plurality of measures of similarity specifying, for each reference vector V in the set R, a strength of a match between the data vector and the reference vector V, and

wherein the confidence estimate output means comprises means for selecting a first one of the first plurality of measures of similarity and means for deriving the confidence estimate output from the first one of the first plurality of measures of similarity and the second filter output.

28. The system of claim 27, wherein the set R contains a plurality of reference vectors, and wherein the second filter output comprises a second plurality of measures of similarity specifying, for each reference vector V in the set R, a strength of a match between the data vector and the reference vector V, and

wherein the confidence estimate output means comprises selecting a second one of the plurality of measures of similarity and means for deriving the confidence estimate output from the first one of the first plurality of measures of similarity and the second one of the second plurality of measures of similarity.

29. The system of claim 27, wherein the confidence estimate output means comprises:

means for identifying a peak match strength PK1 among the first plurality of measures of similarity;

means for identifying a second-highest match strength PK2 among the first plurality of measures of similarity;

means for identifying a quotient PK1/PK2; and

means for identifying the confidence estimate output based on PK1 and PK1/PK2.

30. The system of claim 27, wherein the confidence estimate output means comprises:

means for identifying a peak match strength PK1 among the first plurality of measures of similarity;

means for identifying a second-highest match strength PK2 among the first plurality of measures of similarity;

means for identifying a difference PK1-PK2; and

means for identifying the confidence estimate output based on PK1 and PK1-PK2.

31. The system of claim 27, wherein the confidence estimate output means comprises:

means for identifying a peak match strength PK1 among the first plurality of measures of similarity;

means for identifying an average AVG of the first plurality of measures of similarity;

means for identifying a quotient PK1/AVG; and

means for identifying the confidence estimate output based on PK1 and PK1/AVG.

32. The system of claim 27, wherein the confidence estimate output means comprises:

means for identifying a peak match strength PK1 among the first plurality of measures of similarity;

means for identifying an average AVG of the first plurality of measures of similarity;

means for identifying a difference PK1-AVG; and

means for identifying the confidence estimate output based on PK1 and PK1-AVG.

33. The system of claim 27, wherein the confidence estimate output means comprises:

means for identifying a peak match strength PK1 among the first plurality of measures of similarity;

means for identifying an average AVG of the first plurality of measures of similarity;

means for identifying a standard deviation DEV of the first plurality of measures of similarity;

means for identifying a quotient PK1/(AVG+k*DEV), wherein k is a constant; and

means for identifying the confidence estimate output based on PK1 and (PK1/(AVG+k*DEV)).

34. The system of claim 27, wherein the confidence estimate output means comprises:

means for identifying a peak match strength PK1 among the first plurality of measures of similarity;

means for identifying an average AVG of the first plurality of measures of similarity;

means for identifying a standard deviation DEV of the first plurality of measures of similarity;

means for identifying a difference PK1−

(AVG+k*DEV), wherein k is a constant; and

means for identifying the confidence estimate output based on PK1 and (PK1−

(AVG+k*DEV)).

35. The system of claim 27, wherein MSV[i] indicates a match strength at index i within the match strength vector, wherein R[i] indicates a reference vector at index i within the plurality of ordered reference vectors, and wherein the confidence estimate output means comprises:

means for identifying a peak match strength PK1 among the first plurality of measures of similarity, wherein PK1 is the match strength of MSV[j];

means for identifying a match strength PK_L, wherein PK_L is the maximum of match strengths MSV[j+RAD+1] and MSV[j−

RAD−

1], for a predetermined value of RAD;

means for identifying a quotient PK1/PK_L; and

means for identifying the confidence estimate output based on PK1 and PK1/PK_L.

36. The system of claim 27, wherein MSV[i] indicates a match strength at index i within the match strength vector, wherein R[i] indicates a reference vector at index i within the plurality of ordered reference vectors, and wherein the confidence estimate output means comprises:

means for identifying a peak match strength PK1 among the first plurality of measures of similarity, wherein PK1 is the match strength of MSV[j];

means for identifying a match strength PK_L, wherein PK_L is the maximum of match strengths MSV[j+RAD+1] and MSV[j−

RAD−

1], for a predetermined value of RAD;

means for identifying a difference PK1-PK_L; and

means for identifying the confidence estimate output based on PK1 and PK1-PK_L.

37. The system of claim 27, wherein MSV[i] indicates a match strength at index i within the match strength vector, wherein R[i] indicates a reference vector at index i within the plurality of ordered reference vectors, wherein 0≦

i<

N, and wherein the confidence estimate output means comprises;

means for identifying a peak match strength PK1 among the first plurality of measures of similarity, wherein PK1 is the match strength of MSV[j];

means for determining whether j>

0;

means for determining whether j<

N−

1; and

means for identifying the confidence estimate output based on PK1 and whether j>

0 and whether j<

N−

1.

38. The system of claim 27, wherein MSV[i] indicates a match strength at index i within the match strength vector, wherein R[i] indicates a reference vector at index i within the plurality of ordered reference vectors, wherein 0≦

i<

N, and wherein the confidence estimate output means comprises;

means for identifying a peak match strength PK1 among the first plurality of measures of similarity, wherein PK1 is the match strength of MSV[j];

means for determining whether j>

RAD, for a predetermined value of RAD>

0;

means for determining whether j<

N−

RAD−

1; and

means for identifying the confidence estimate output based on PK1 and whether j>

RAD and whether j<

N−

RAD−

1.

39. The system of claim 22, wherein the first filter comprises a plurality of filters.

40. The system of claim 22, wherein the second filter comprises a plurality of filters.

41. The system of claim 22, wherein the confidence estimate output means comprises:

first selection means for selecting a first one of the first filter output and the second filter output as a first intermediate filter output;

second selection means for selecting a second one of the first filter output and the second filter output as a second intermediate filter output, wherein the first and second intermediate filter outputs differ from each other;

means for deriving the confidence estimate output from the first intermediate filter output and the second intermediate filter output;

means for applying an output transformation function to the first intermediate filter output to produce a third filter output, wherein the confidence estimate output represents a degree of confidence in the correctness of the third filter output; and

means for providing the third filter output and the confidence estimate output as output.

42. The system of claim 41:

wherein the first means for selecting comprises means for selecting the first intermediate filter output based on at least one input other than the data vector and the set R; and

wherein the second means for selecting comprises selecting the second intermediate filter output based on the at least one input other than the data vector and the set R.

43. A method comprising:

(A) receiving a first image input in an image input sequence;

(B) receiving a second image input in the image input sequence, wherein the second image input has a relative position subsequent to the first image input in the image input sequence;

(C) applying a frame sample filter to the first image input to produce a sample pattern comprising at least one sample;

(D) applying a sample registration filter to the second image input and the sample pattern to identify;

(1) an unfiltered flow sample set comprising at least one optical flow sample, wherein the unfiltered flow sample set defines a coregistration between the first image input and the second image input;

(2) at least one fault warning representing a degree of confidence in the coregistration;

(E) removing, from the unfiltered flow sample set, at least one sample specified by the at least one fault warning as in-fault, to produce a filtered flow sample set; and

(F) generating optical flow confidence estimate output based the filtered flow sample set.

44. The method of claim 43, wherein (F) comprises generating the optical flow confidence estimate output based on the filtered flow sample set and at least one of:

(1) a third input not contained within the first image input or the second image input;

(2) the sample pattern; and

(3) the at least one fault warning.

45. The method of claim 43, wherein (F) comprises generating the optical flow confidence estimate output based on the filtered flow sample set and the third input.

46. The method of claim 43, wherein (C) comprises applying a matched filter to the first image input to produce the sample pattern.

47. The method of claim 43, wherein (D) comprises applying a matched filter to the second image input and the sample pattern to identify the unfiltered flow sample and the at least one fault warning.

48. The method of claim 43, wherein (C) comprises applying the frame sample filter to the first image input and the third input to produce the sample pattern.

49. The method of claim 43, wherein (E) comprises determining which of the samples in the unfiltered flow sample set to remove from the unfiltered flow sample set based on the third input and the at least one fault warning.

50. The method of claim 43, wherein the first matched filter comprises a correntropy matched filter.

51. The method of claim 43, wherein the second matched filter comprises a correntropy matched filter.

52. A system comprising:

means for receiving a first image input in an image input sequence;

means for receiving a second image input in the image input sequence, wherein the second image input has a relative position subsequent to the first image input in the image input sequence;

a frame sample filter comprising means for producing, based on the first image input, a sample pattern comprising at least one sample;

a sample registration filter comprising means for identifying, based on the second image input and the sample pattern;

(1) an unfiltered flow sample set comprising at least one optical flow sample, wherein the unfiltered flow sample set defines a coregistration between the first image input and the second image input;

(2) at least one fault warning representing a degree of confidence in the coregistration;

a flow sample fault filter comprising means for removing, from the unfiltered flow sample set, at least one sample specified by the at least one fault warning as in-fault, to produce a filtered flow sample set; and

an optical flow confidence estimate generator to generate optical flow confidence estimate output based the filtered flow sample set.

53. The system of claim 52, wherein the optical flow confidence estimate generator comprises means for generating the optical flow confidence estimate output based on the filtered flow sample set and at least one of:

(1) a third input not contained within the first image input or the second image input;

(2) the sample pattern; and

(3) the at least one fault warning.

54. The system of claim 53, wherein the optical flow confidence estimate generator comprises means for generating the optical flow confidence estimate output based on the filtered flow sample set and the third input.

55. The system of claim 52, wherein the frame sample filter comprises a matched filter.

56. The system of claim 52, wherein the sample registration filter comprises a matched filter.

57. The system of claim 52, wherein the frame sample filter comprises means for producing the sample pattern based on the first image input and the third input.

58. The system of claim 52, wherein the flow sample fault filter comprises means for determining which of the samples in the unfiltered flow sample set to remove from the unfiltered flow sample set based on the third input and the at least one fault warning.

59. The system of claim 52, wherein the first matched filter comprises a correntropy matched filter.

60. The system of claim 52, wherein the second matched filter comprises a correntropy matched filter.

61. A method comprising:

(A) receiving a first image input in an image input sequence;

(B) receiving a second image input in the image input sequence, wherein the second image input has a relative position subsequent to the first image input in the image input sequence;

(C) applying a frame sample filter, including a first matched filter, to the first image input to produce a sample pattern comprising at least one sample;

(D) applying a sample registration filter, including a second matched filter, to the second image input and the sample pattern to identify;

(1) an unfiltered flow sample set comprising at least one optical flow sample, wherein the unfiltered flow sample set defines a coregistration between the first image input and the second image input; and

(2) at least one fault warning representing a degree of confidence in the coregistration; and

(E) removing, from the unfiltered flow sample set, at least one sample specified by the at least one fault warning as in-fault, to produce a filtered flow sample set.

62. The method of claim 61, further comprising:

(F) generating optical flow confidence estimate output based the filtered flow sample set and at least one of;

(1) a third input not contained within the first image input or the second image input;

(2) the sample pattern; and

(3) the at least one fault warning.

63. The method of claim 61, wherein (C) comprises applying the frame sample filter to the first image input and the third input to produce the sample pattern.

64. The method of claim 61, wherein (E) comprises determining which of the samples in the unfiltered flow sample set to remove from the unfiltered flow sample set based on the third input and the at least one fault warning.

65. The method of claim 61, wherein the first matched filter comprises a correntropy matched filter.

66. The method of claim 61, wherein the second matched filter comprises a correntropy matched filter.

67. A system comprising:

means for receiving a first image input in an image input sequence;

means for receiving a second image input in the image input sequence, wherein the second image input has a relative position subsequent to the first image input in the image input sequence;

a frame sample filter comprising a first matched filter, the matched filter comprising means for producing, based on the first image input, a sample pattern comprising at least one sample;

a sample registration filter comprising means for identifying, based on the second image input and the sample pattern;

(1) an unfiltered flow sample set comprising at least one optical flow sample, wherein the unfiltered flow sample set defines a coregistration between the first image input and the second image input; and

(2) at least one fault warning representing a degree of confidence in the coregistration; and

a flow sample fault filter comprising means for removing, from the unfiltered flow sample set, at least one sample specified by the at least one fault warning as in-fault, to produce a filtered flow sample set.

68. The method of claim 67, further comprising:

an optical flow confidence estimate generator to generate optical flow confidence estimate output based the filtered flow sample set and at least one of;

(1) a third input not contained within the first image input or the second image input;

(2) the sample pattern; and

(3) the at least one fault warning.

69. The system of claim 67, wherein the frame sample filter comprises means for producing the sample pattern based on the first image input and the third input.

70. The system of claim 67, wherein the flow sample filter comprises means for determining which of the samples in the unfiltered flow sample set to remove from the unfiltered flow sample set based on the third input and the at least one fault warning.

71. The system of claim 67, wherein the first matched filter comprises a correntropy matched filter.

72. The system of claim 67, wherein the second matched filter comprises a correntropy matched filter.