Pattern recognition system employing unlike templates to detect objects having distinctive features in a video field

• US 5,627,915 A
• Filed: 01/31/1995
• Issued: 05/06/1997
• Est. Priority Date: 01/31/1995
• Status: Expired due to Term

• Current Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Original Assignee: Princeton Video Image, Inc. (Gabriel Technologies Corporation)
• Inventors: Rosser, Roy, von Kaenel, Peter, Tan, Yi, Das, Subhodev
• Primary Examiner(s): JOHNS, ANDREW W
• Application Number:
  US08/381,088
• Time in Patent Office: 826 Days
• Field of Search: 382/190, 382/195, 382/209, 382/219, 382/226, 382/227, 382/278
• US Class Current: 382/219
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: H04N 5/2723 Insertion of virtual advertisement; Replacing advertisements physical present in the scene by virtual advertisement data processing systems or methods specially adapted for marketing G06Q30/02

Abstract

A system for inserting images into live video fields includes a method for rapidly and efficiently identifying landmarks and objects. Initially a first template, having a first pattern similar to one of the distinctive features of the object, is passed over the video field and compared to it in order to preliminarily identify at least one possible distinctive feature as a candidate. A second template is then created by taking one of the major elements of the distinctive feature candidate and extending that element all the way across the second template and then comparing it to the distinctive feature candidate. This eliminates one or more possible falsely identified features. A third template is then created having a pattern formed from another major element of said distinctive feature and extending it all the way across the third template. The third template is then likewise passed over the distinctive feature candidate and compared therewith in order to eliminate still further falsely identified features. The method is continued until all possible false alarm candidates have been eliminated. The process is then repeated in order to preliminarily identify two or three landmarks of the target object. The locations of those objects are then compared to a geometric model to further verify if the object has been correctly identified. The methodology can be tested against a video taped program to determine if it accurately identifies objects.

Claims

1. A pattern recognition method for recognizing an object having distinctive features as imaged in a video field, said method comprising the steps of:

(a) passing a first template having a first pattern similar to one of said distinctive features over said video field and comparing the same in order to preliminarily identify at least one possible distinctive feature of said object which could either be a correctly identified distinctive feature or one of a plurality of incorrectly identified features;

(b) passing a second template having a second pattern different from said first template pattern over said possible distinctive feature and comparing the same in order to determine if said possible distinctive feature is at least one of said incorrectly identified features;

(c) passing a third template having a third pattern different from said first and second template patterns over said possible distinctive feature and comparing the same in order to determine if said possible distinctive feature is at least another of said incorrectly identified features;

(d) repeating steps (b) and (c) above until all possible likely falsely identified features have been eliminated as possible candidates for said distinctive feature;

(e) selecting said second pattern, wherein said second pattern includes a first element of said distinctive feature which extends substantially completely across said second template,

wherein said correctly identified feature is accurately identified by process of elimination.

2. The method of claim 1 further comprising the step of:

(f) Selecting said third pattern, wherein said third pattern includes a second element of said distinctive feature which extends substantially completely across third template.

3. The method of claim 2 further comprising the steps of:

(g) repeating steps (a)-(f) above to locate at least two potential distinctive features of said object; and

,

(h) geometrically comparing the location of said at least two potential distinctive features of said object against a geometric model of said object to further determine if said object has been correctly identified.

4. The method of claim 3 further comprising the step of:

(i) recording a series of consecutive video frames and verifying the accuracy of said method for recognizing an object by testing it against said series of video frames over a period of time to determine if it has correctly identified said object.

5. The method of claim 4 further comprising the step of:

(j) determining the sub-pixel maximum value of at least a first, second and third pixel each having a top with a midpoint and all having a common baseline by forming a first line through the midpoint of the top of said first and second pixels, said first line forming an angle α

with respect to said common baseline and subsequently drawing a second line through the top midpoint of said third pixel, said second line having an angle 180°

--α

with respect to said common baseline,

wherein the triangular intersection of said first and second lines approximates the location of the maximum value of said three pixels.

6. The method of claim 5 further comprising the step of:

(k) inserting an always fail flag into the end of each frame tested in step (i) thereby forcing the method to repeat steps (a)-(f) at least once per field,

wherein an effort is made to recognize said object once each frame.

7. The method of claim 6 further comprising the step of:

(l) inserting an alternative image in place of said object in said video field.

8. The method of claim 1 wherein at least two templates are employed and a distinctive feature is determined to exist when the following total function T is maximized:

space="preserve" listing-type="equation">TΣ

(Σ

Pα

.sub.i (m,n)±

Σ

Pα

.sub.i (m+v,n+h))=maximum

where T=Total or Sum of function

P=a given line

α

_i =angle of a given line P to abscissa

i=2 or more

m=location of at least a first search template on the vertical, i.e., ordinate, axis

n=location of at least a first search template on the horizontal, i.e., abscissa, axis.

v=vertical offset of at least a second search template from point m

h=horizontal offset of at least a second search template from point n.

9. The method of claim 8 wherein said distinctive feature is located at the intersection of two orthogonal straight lines by maximizing the function:

space="preserve" listing-type="equation">T=Σ

(Σ

P(col,90,n,m+v)-Σ

P(row,O,n-h,m)+Σ

P(row,O,n+h,m)-Σ

P(col,90,n,m-v))=maximum.

10.

10. A pattern recognition method for recognizing an object having landmark features as imaged in a video field, said method comprising the steps of:

(a) correlating a first template having a first pattern similar to one of said landmark features with respect to said video field and generating a first correlation surface to preliminarily identify at least one candidate landmark feature of said object which could be either a correctly identified landmark feature or one of a plurality of falsely identified landmark features;

(b) correlating a second template having a second pattern with unlike feature correlation with respect to said first template pattern to said candidate landmark feature and generating a second correlation surface to determine if said candidate landmark feature is at least one of said falsely identified landmark features;

(c) correlating a third template having a third pattern with unlike feature correlation with respect to said first and second template patterns over said candidate landmark feature and generating a third correlation surface in order to determine if said candidate landmark feature is at least another of said falsely identified landmark features;

(d) repeating steps (b) and (c) above until all possible likely falsely identified landmark features have been eliminated,

(e) selecting said second pattern, wherein said second pattern includes a first element of said landmark feature which extends substantially completely across said second template,

wherein said correctly identified landmark feature is accurately identified by process of elimination of said falsely identified landmark features.

11. The method of claim 10 further comprising the step of:

(f) Selecting said third pattern, wherein said third pattern includes a second element of said landmark feature which is extended substantially completely across said third template.

12. The method of claim 11 further comprising the step of:

(g) repeating steps (a)-(f) above to locate at least two potential landmark features of said object; and

,

(h) geometrically comparing the location of said at least two potential landmark features of said object against a geometric model of said object to further determine if said object has been correctly identified.

13. The method of claim 12 further comprising the step of:

(i) recording a series of consecutive video frames and verifying the accuracy of said method for recognizing an object by testing it against said series of consecutive video frames over a period of time to determine if it has correctly identified said object.

14. The method of claim 13 further comprising the step of:

(j) determining the sub-pixel maximum value of at least a first, second and third pixel each having a top with a midpoint and each having a common baseline by forming a first line through the midpoint of the top of said first and second pixels, said first line forming an angle α

with respect to said common baseline and subsequently drawing a second line through the top of the midpoint of said third pixel and having an angle 180°

--α

with respect to said common baseline,

wherein the triangular intersection of said first and second lines approximates the location of the maximum value of said three pixels.

15. The method of claim 14 further comprising the step of:

(k) inserting an always fail flag into the end of each frame tested in step (i) above thereby forcing the method to repeat steps (a)-(f) at least once per frame,

wherein an effort is made to recognize said object once each field.

16. The method of claim 15 further comprising the step of:

(l) inserting an alternative image in place of said object in said video field.

17. The method of claim 10 wherein at least two correlation surfaces are generated and a landmark feature is determined to exist when the following total function is maximized:

space="preserve" listing-type="equation">T=Σ

(Σ

Pα

.sub.i (m,n)±

Σ

Pα

.sub.i (m+v,n+h))=maximum

where T=Total or Sum of function

P=a given line

α

_i =angle of a given line P to abscissa

i=2 or more

m=location of at least a first search template on the vertical, i.e., ordinate, axis

n=location of at least a first search template on the horizontal, i.e., abscissa, axis.

v=vertical offset of at least a second search template from point m

h=horizontal offset of at least a second search template from point n.

18. The method of claim 17 wherein said landmark feature is located at the intersection of two orthogonal straight lines by maximizing the function:

space="preserve" listing-type="equation">T=Σ

(Σ

P(col,90,n,m+v)-Σ

P(row,O,n-h,m)+Σ

P(row,O,n+h,m)-Σ

P(col,90,n,m-v))=maximum.

19.

19. A pattern recognition method for recognizing an object having distinctive features as imaged in a video field, said method comprising the steps of:

(a) passing a first template having a first pattern similar to one of said distinctive features over said video field and comparing the same in order to preliminarily identify at least one possible distinctive feature of said object which could be either a correctly identified distinctive feature or one of a plurality of incorrectly identified features; and

,

(b) passing a second template having a second pattern different from said first template pattern over said possible distinctive feature and comparing the same in order to determine if said possible distinctive feature is at least one of said incorrectly identified features,

wherein said second pattern includes a first element of said distinctive feature which extends substantially completely across said second template.

20. A pattern recognition method for recognizing an object having landmark features as imaged in a video field, said method comprising the steps of:

(a) correlating a first template having a first pattern similar to one of said landmark features with respect to said video field and generating a first correlation surface to preliminarily identify at least one candidate landmark feature of said object which could be either a correctly identified landmark feature or one of a plurality of falsely identified landmark features; and

,

(b) correlating a second template having a second pattern with unlike feature correlation with respect to said first template pattern to said candidate landmark feature and generating a second correlation surface to determine if said candidate landmark feature is at least one of said falsely identified landmark features,

wherein said second pattern includes a first element of said landmark feature which extends substantially completely across said second template.

21. A system for recognizing an object having landmark features as imaged in a video field, said system comprising:

scanning means for scanning said object and forming a series of video fields; and

,

correlating means for correlating a first template having a first pattern similar to one of said landmark features with respect to said video field and generating a first correlation surface to preliminarily identify at least one candidate landmark feature of said object which could be either a correctly identified landmark feature or one of a plurality of falsely identified landmark features and for correlating a second template having a second pattern with unlike feature correlation with respect to said first template pattern to said candidate landmark feature and generating a second correlation surface to determine if said candidate landmark feature is at least one of said falsely identified landmark features,

wherein said second pattern includes a first element of said landmark feature which extends substantially completely across said second template and wherein said correctly identified landmark feature is identified by process of eliminating possible falsely identified landmark features.

22. The system of claim 21 further comprising:

insertion means for inserting an alternative image in place of said object in said video field.

23. A pattern recognition method for recognizing an object having distinctive features as imaged in a video field, said method comprising the steps of:

(a) passing a first template having a first pattern similar to one of said distinctive features over said video field and comparing the same in order to preliminarily identify at least one possible distinctive feature of said object which could be either a correctly identified distinctive feature or one of a plurality of incorrectly identified features;

(b) passing a second template having a second pattern different from said first template pattern over said possible distinctive feature and comparing the same in order to determine if said possible distinctive feature is at least one of said incorrectly identified features;

(c) passing a third template having a third pattern different from said first and second template patterns over said possible distinctive features and comparing the same in order to determine if said possible distinctive feature is at least another of said incorrectly identified features,

wherein at least two templates are employed and a distinctive feature is determined to exist when the following total function T is maximized;

space="preserve" listing-type="equation">T=Σ

[Σ

Pα

.sub.i (m,n)±

Σ

Pα

.sub.i (m+v,n+h)]=maximum

where T=Total or Sum of function

P=a given line

α

_i =angle of a given line P to abscissa

i=2 or more

m=location of at least a first search template on the vertical, i.e., ordinate, axis

n=location of at least a first search template on the horizontal, i.e., abscissa, axis.

v=vertical offset of at least a second search template from point m

h=horizontal offset of at least a second search template from point n.

24. A pattern recognition method for recognizing an object having landmark features as imaged in a video field, said method comprising the steps of:

(a) correlating a first template having a first pattern similar to one of said landmark features with respect to said video field and generating a first correlation surface to preliminarily identify at least one candidate landmark feature of said object which could be either a correctly identified landmark feature or one of a plurality of falsely identified landmark features;

(b) correlating a second template having a second pattern with unlike feature correlation with respect to said first pattern to said candidate landmark feature and generating a second correlation surface to determine if said landmark feature is at least one of said falsely identified landmark features;

(c) correlating a third template having a third pattern with unlike feature correlation with respect to said first and second template patterns over said candidate landmark feature and generating a third correlation surface in order to determine if said candidate landmark feature is at least another of said falsely identified landmark features,

wherein at least two correlation surfaces are generated and a landmark feature is determine to exist when the following total function is maximized;

space="preserve" listing-type="equation">T=Σ

[Σ

Pα

.sub.i (m,n)±

Σ

Pα

.sub.i (m-v,n+h)]=maximum

where T=Total or Sum of function

P=a given line

α

_i =angle of a given line P to abscissa

i=2 or more

m=location of at least a first search template on the vertical, i.e., ordinate, axis

n=location of at least a first search template on the horizontal, i.e., abscissa, axis.

v=vertical offset of at least a second search template from point m

h=horizontal offset of at least a second search template from point n.

25. A pattern recognition method for recognizing an object having distinctive features as imaged in a video field, said method comprising the steps of:

(a) passing a first template having a first pattern similar to one of said distinctive features over said video field and comparing the same in order to preliminarily identify at least one possible distinctive feature of said object which could be either a correctly identified distinctive feature or one of a plurality of incorrectly identified features;

(b) passing a second template having a second pattern different from said first template pattern over said possible distinctive feature and comparing the same in order to determine if said possible distinctive feature is at least one of said incorrectly identified features,

wherein said second pattern does not match any distinctive feature sought to be recognized and includes at least one extended element different from said first pattern in order to more rapidly distinguish said distinctive features.

26. A pattern recognition method for recognizing an object having landmark features as imaged in a video field, said method comprising the steps of:

(a) correlating a first template having a first pattern similar to one of said landmark features with respect to a video field and generating a first correlation surface to preliminarily identify at least one candidate landmark feature of said object which could be either a correctly identified landmark feature or one of a plurality of falsely identified landmark features; and

,

(b) correlating a second template having a second pattern with unlike feature correlation with respect to said first template pattern to said candidate landmark feature and generating a second correlation surface to determine if said candidate landmark feature is at least one of said falsely identified landmark features,

wherein said second pattern does not match any landmark feature sought to be recognized and includes at least one extended element different from said first pattern in order to more rapidly distinguish said landmark features.

27. A system for recognizing an object having landmark features as imaged in a video field, said system comprising:

scanning means for scanning said object and forming a series of video fields; and

,

correlating means for correlating a first template having a first pattern similar to one of said landmark features with respect to said video field and generating a first correlation surface to preliminarily identify at least one candidate landmark feature of said object which could be either a correctly identified landmark feature or one of a plurality of falsely identified landmark features and for correlating a second template having a second pattern with unlike feature correlation with respect to said first template pattern to said candidate landmark feature and generating a second correlation surface to determine if said candidate landmark feature is at least one of said falsely identified landmark features,

wherein said second pattern does not match any landmark feature sought to be recognized and includes at least one extended element different from said first pattern in order to more rapidly distinguish said landmark features.