Methods and apparatus for distinguishing among several visual patterns

• US 6,021,219 A
• Filed: 01/07/1997
• Issued: 02/01/2000
• Est. Priority Date: 01/07/1997
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Singer, Howard M., Andersson, Russell L.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Novik, Dmitry A.
• Application Number:
  US08/782,011
• Time in Patent Office: 1,120 Days
• Field of Search: 382/164, 382/165, 382/190, 382/175, 382/287, 382/292, 382/201, 382/224, 382/225, 382/282, 382/209, 348/587, 348/592
• US Class Current: 382/190
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

A method and apparatus for controlling the operation of a video system such as a video game system through recognition of a visual pattern, or key. For example, the presence and identity of the key may enable and select certain features of the video system. The key may suitably consist of a locator mark and a selector mark, the presence of the locator mark identifying the presence of a key, and the selector mark identifying the particular key present. A key recognition system detects the presence of the locator mark and identifies the selector mark. The locator mark is preferably of a distinctive color, readily distinguishable from background objects. The selector mark may be chosen from a limited set of colors, and the color of the selector mark may then be identified to identify the key being used. In another aspect, the locator mark is located in a particular position within the selector mark and is then used by the key detector to scale a rectangle about the selector mark. The selector mark is reduced by processing within the key detector to a reduced invariant image characterization. This reduced invariant image characterization is then compared against image data characterizations stored in a dictionary to identify the particular selector mark, and thus particular key.

Claims

1. A method for recognizing a visual pattern to control operation of a video system, said pattern consisting of a locator mark and a selector mark, said selector mark being one of a set of possible selector marks, comprising the steps of:

receiving a frame of video data;

detecting said locator mark within said frame of video data;

determining a location of said selector mark based on a known size, position and orientation of said selector mark relative to said locator mark by defining bounds of said selector mark based on the known size, position and orientation of said selector mark relative to said locator mark;

identifying, within said frame of video data, a visual image of said selector mark;

reducing said visual image of said selector mark to a reduced characterization, said reduced characterization being largely invariant to lighting, distortion and orientation;

comparing said reduced characterization against members of a set of stored characterizations, each of said stored characterizations being identified with one of said possible selector marks; and

upon matching said reduced characterization with one of said set of stored characterizations, identifying said possible selector mark as a received selector mark.

2. The method of claim 1, wherein the step of detecting said locator mark within said frame of video data also includes computing an area of said locator mark and further computing a radius of said locator mark from said area of said locator mark.

3. The method of claim 2, wherein the step of identifying, within said frame of video data, a visual image of said selector mark further includes using said radius of said locator mark to construct a rectangle, said rectangle encompassing said selector mark.

4. The method of claim 3, wherein the step of reducing said visual image of said selector mark further includes computing within said rectangle each of a plurality of projection vectors and sorting these plurality of projection vectors into a fixed number of horizontal and vertical bins, said bins being scaled to match a size of said rectangle in pixels.

5. The method of claim 4, wherein the step of reducing said selector mark further includes normalizing each of said bins by a number of pixels in said bin.

6. The method of claim 5, wherein the step of reducing said selector mark further includes:

computing an average value of said projection vectors;

subtracting said average value from each of said projection vectors;

identifying a point in one of said projection vectors having the greatest absolute value; and

scaling each of said points so that said greatest absolute value of said point exactly equals a predetermined value.

7. The method of claim 5, wherein the step of reducing said selector mark further includes applying a band-pass filter.

8. The method of claim 5, in which said frame of video data consists of multiple binary color-keyed images, wherein the step of reducing said selector mark further includes differencing selected pairs of binary images.

9. The method of claim 6, wherein said locator mark is chosen to be of a unique color, and, for each of said possible selector marks, is of a uniform size and position relative to said selector mark, and is of a known shape.

10. The method of claim 8, wherein said locator mark is located within said selector mark.

11. The method of claim 1, wherein said selector mark is chosen from among a limited set of colors, said set of colors not including a color of said locator mark.

12. The method of claim 5 wherein said method is operative within a video game system said video game system being operative to track a passive prop, said prop furnishing inputs for the play of said video game system.

13. The method of claim 2 wherein said visual pattern is printed on a substrate, said substrate being an article of clothing to be worn by a user.

14. The method of claim 13 wherein said article of clothing is a t-shirt.

15. The method of claim 13 wherein said article of clothing is a hat.

16. A key recognition system for controlling the operation of a video system through recognition of a visual pattern detected in a received frame of video data, the system comprising:

a key consisting of a locator mark and a selector mark, said locator mark being adapted to be detected in a frame of video data, detection of said locator mark serving to aid location of said selector mark based on a known size, position and orientation of said locator mark relative to said selector mark and to define bounds of said selector mark based on the known size, position and orientation of said locator mark relative to said selector mark, each of said locator mark and selector mark comprising a visual pattern, said selector mark being one of a set of possible selector marks;

a locator mark detector system for identifying said locator mark; and

a selector mark identifier for computing a location and bounds of said selector mark using previously predetermined information about said size, position and orientation of said locator mark relative to said selector mark, and identifying said selector mark.

17. The system of claim 16 wherein said locator mark is a pattern of a unique color.

18. The system of claim 17 wherein said locator mark and said possible selector marks are chosen such that all of said possible selector marks are of a uniform size and shape and said locator mark is of a uniform size relative to each of said possible selector marks, and is of a uniform shape.

19. The system of claim 18 wherein said locator mark is located within said selector mark, in a uniform position respective to each of said possible selector marks.

20. The system of claim 18 wherein said locator mark detector system includes:

a video frame receiver for receiving frames of video data;

a chroma-key detector for detecting areas of specified color within one or more of said frames of video data, said chroma-key detector being operable to detect said locator mark within one of said frames of video data;

a locator mark processor for;

computing an area of said locator mark;

computing from said area of said locator mark a radius of said locator mark; and

employing said radius of said locator mark to construct a rectangle encompassing said selector mark.

21. The system of claim 20 wherein said selector mark identifier includes a processor to obtain a reduced detected image characterization for a detected selector mark, said processor being operable to:

compute within said rectangle each of a plurality of projection vectors into a fixed number of horizontal and vertical bins, said bins being scaled to match a size of said rectangle in pixels;

normalize each of said bins by a number of pixels in said bin;

compute an average value of said projection vectors;

subtract said average value from each of said projection vectors;

identify a point in one of said projection vectors having the greatest absolute value; and

scale each of said points so that said greatest absolute value of said point exactly equals a predetermined value.

22. The system of claim 21 wherein said selector mark identifier also includes:

a selector mark dictionary including a reduced stored image characterization for each of said possible selector marks;

a comparison processor for;

comparing said reduced detected image against each of said reduced stored image characterizations;

computing a difference between said reduced detected image characterization and each of said reduced stored image characterizations; and

declaring a match between said reduced detected image characterization and said reduced stored image characterization having a least difference with said reduced detected image characterization.

23. The system of claim 22 wherein said comparison processor also compares said difference between said reduced detected image characterization and each of said reduced stored image characterizations against a predetermined criterion, and declaring that no match exists when none of said differences meets said predetermined criterion.

24. The system of claim 16 wherein said locator mark is of a unique color, said selector mark is of a color selected from a set of distinctive colors, each of said colors being distinct from said color of said locator mark, and said locator mark detector is operative to detect said color of said locator mark, and said selector mark identifier is operative to detect said color of said selector mark and further to identify said selector mark by matching said color of said selector mark against said set of distinctive colors.

25. A method for recognizing a visual pattern to control operation of a video system, said pattern consisting of a locator mark and a selector mark, said selector mark being one of a set of possible selector marks, comprising the steps of:

receiving a frame of video data;

detecting said locator mark within said frame of video data by computing an area of said locator mark and further computing a radius of said locator mark from said area of said locator mark;

identifying, within said frame of video data, a visual image of said selector mark by using said radius of said locator mark to construct a rectangle, said rectangle encompassing said selector mark;

reducing said visual image of said selector mark to a reduced characterization by computing within said rectangle each of a plurality of projection vectors and sorting these plurality of projection vectors into a fixed number of horizontal and vertical bins, said bins being scaled to match a size of said rectangle in pixels and normalizing each of said bins by a number of pixels in said bin, said reduced characterization being largely invariant to lighting, distortion and orientation;

comparing said reduced characterization against members of a set of stored characterizations, each of said stored characterizations being identified with one of said possible selector marks; and

upon matching said reduced characterization with one of said set of stored characterizations, identifying said possible selector mark as a received selector mark.

26. The method of claim 25, wherein the step of reducing said selector mark further comprises:

computing an average value of said projection vectors;

subtracting said average value from each of said projection vectors;

identifying a point in one of said projection vectors having the greatest absolute value; and

scaling each of said points so that said greatest absolute value of said point exactly equals a predetermined value.

27. The method of claim 25, wherein the step of reducing said selector mark further comprises applying a band-pass filter.

28. The method of claim 25, in which said frame of video data consists of multiple binary color-keyed images, wherein the step of reducing said selector mark further comprises differencing selected pairs of binary images.

29. The method of claim 26, wherein said locator mark is chosen to be of a unique color, and, for each of said possible selector marks, is of a uniform size and position relative to said selector mark, and is of a known shape.

30. The method of claim 28, wherein said locator mark is located within said selector mark.

31. The method of claim 25, wherein said selector mark is chosen from among a limited set of colors, said set of colors not including a color of said locator mark.

32. The method of claim 25 wherein said method is operative within a video game system said video game system being operative to track a passive prop, said prop furnishing inputs for the play of said video game system.

33. The method of claim 25 wherein said visual pattern is printed on a substrate, said substrate being an article of clothing worn by a user.

34. The method of claim 33 wherein said article of clothing is a t-shirt.

35. The method of claim 33 wherein said article of clothing is a hat.

36. A key recognition system for controlling the operation of a video system through recognition of a visual pattern detected in a received frame of video data, the system comprising:

a key consisting of a locator mark and a selector mark, each of said locator mark and selector mark comprising a visual pattern, said locator mark being a pattern of a unique color and said selector mark being one of a plurality of possible selector marks, said locator mark and said possible selector marks being chosen such that all of said possible selector marks are of a uniform size and shape and said locator mark is of a uniform size relative to each of said possible selector marks and of a uniform shape, said locator mark being located within said selector mark, in a uniform position respective to each of said possible selector marks;

a locator mark detector system for identifying said locator mark, said locator mark detector system including;

a video frame receiver for receiving frames of video data;

a chroma-key detector for detecting areas of specified color within one or more of said frames of video data, said chroma-key detector being operable to detect said locator mark within one of said frames of video data;

a locator mark processor for;

computing an area of said locator mark;

computing from said area of said locator mark a radius of said locator mark; and

employing said radius of said locator mark to construct a rectangle encompassing said selector mark; and

a selector mark identifier for identifying said selector mark.

37. The system of claim 36 wherein said selector mark identifier includes a processor to obtain a reduced detected image characterization for a detected selector mark, said processor being operable to:

compute within said rectangle each of a plurality of projection vectors into a fixed number of horizontal and vertical bins, said bins being scaled to match a size of said rectangle in pixels;

normalize each of said bins by a number of pixels in said bin;

compute an average value of said projection vectors;

subtract said average value from each of said projection vectors;

identify a point in one of said projection vectors having the greatest absolute value; and

scale each of said points so that said greatest absolute value of said point exactly equals a predetermined value.

38. The system of claim 37 wherein said selector mark identifier also includes:

a selector mark dictionary including a reduced stored image characterization for each of said possible selector marks; and

a comparison processor for;

comparing said reduced detected image against each of said reduced stored image characterizations;

computing a difference between said reduced detected image characterization and each of said reduced stored image characterizations; and

declaring a match between said reduced detected image characterization and said reduced stored image characterization having a least difference with said reduced detected image characterization.

39. The system of claim 38 wherein said comparison processor also compares said difference between said reduced detected image characterization and each of said reduced stored image characterizations against a predetermined criterion, and declaring that no match exists when none of said differences meets said predetermined criterion.

40. The system of claim 36 wherein said locator mark is of a unique color, said selector mark is of a color selected from a set of distinctive colors, each of said colors being distinct from said color of said locator mark, and said locator mark detector is operative to detect said color of said locator mark, and said selector mark identifier is operative to detect said color of said selector mark and further to identify said selector mark by matching said color of said selector mark against said set of distinctive colors.