Identification of object on interactive display surface by identifying coded pattern

• US 7,204,428 B2
• Filed: 03/31/2004
• Issued: 04/17/2007
• Est. Priority Date: 03/31/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wilson, Andrew D.
• Primary Examiner(s): Lee; Michael G.
• Assistant Examiner(s): Haupt; Kristy A.
• Application Number:
  US10/814,577
• Publication Number:
  US 20050240871A1
• Time in Patent Office: 1,112 Days
• Field of Search: 235/494, 235/462.11, 235/462.09, 235/462.1, 235/454
• US Class Current: 235/494
• CPC Class Codes: G06K 19/06009 with optically detectable marking G06K19/063, G06K19/08 take precedence
• CPC Class Codes: G06K 19/06131 the marking comprising a target pattern, e.g. for indicating the center of the bar code or for helping a bar code reader to properly orient the scanner or to retrieve the bar code inside of an image
• CPC Class Codes: G06K 19/06168 the marking being a concentric barcode
• CPC Class Codes: G06K 7/1095 the scanner comprising adaptations for scanning a record carrier that is displayed on a display-screen or the like
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

A coded pattern applied to an object is identified when the object is placed on a display surface of an interactive display. The coded pattern is detected in an image of the display surface produced in response to reflected infrared (IR) light received from the coded pattern by an IR video camera disposed on an opposite side of the display surface from the object. The coded pattern can be either a circular, linear, matrix, variable bit length matrix, multi-level matrix, black/white (binary), or gray scale pattern. The coded pattern serves as an identifier of the object and includes a cue component and a code portion disposed in a predefined location relative to the cue component. A border region encompasses the cue component and the code portion and masks undesired noise that might interfere with decoding the code portion.

Claims

1. A two-dimensional identifier applied to an object for encoding a value so that the value is determinable when the two-dimensional identifier is placed adjacent to a surface sensing system, the two-dimensional identifier comprising:

(a) a cue component comprising a contiguous radial area of a detectable material to which the surface sensing system is responsive and which is approximated as an ellipse when detected by said surface sensing system, said ellipse having axes that indicate an orientation of the two-dimensional identifier relative to a coordinate system of the surface sensing system, the radial area including a sub-area comprising the non-detectable material disposed at a first predefined radius from a center of the radial area, the sub-area representing a start bit that indicates a start location from which the code portion is to be read;

(b) a code portion disposed in a predefined location relative to the cue component, said code portion encoding the value with at least one binary element that is detectable by the surface sensing system; and

(c) a border region that encompasses the cue component and the code portion, the border region comprising a non-detectable material that is not sensed as part of the two-dimensional identifier by the surface sensing system and which functions as an interference mask around the cue component and the code portion, to minimize noise.

2. The two-dimensional identifier of claim 1, wherein the detectable material comprises a reflective material that reflects infrared light to which the surface sensing system responds.

3. The two-dimensional identifier of claim 1, wherein a radial code is used for encoding the value, and wherein

the code portion is configured in a region disposed at a second predefined radius from the center of the radial area, greater than the first predefined radius, so that the code portion generally extends around the cue component.

4. The two-dimensional identifier of claim 1, wherein a variable length linear code is used for encoding the value, and wherein:

(a) the cue component comprises parallel strips of the detectable material that are of substantially equal length and are connected at a first end by a predefined area of the detectable material used as a staff bit, the parallel strips being separated by the non-detectable material at a second end opposite the first end, the non-detectable material at the second end being used as an end bit; and

(b) the code portion comprises a paftern of detectable areas and undetectable areas, each detectable area and each undetectable area being of predefined dimensions and disposed between the parallel strips and between the staff bit and the end bit.

5. The two-dimensional identifier of claim 1, wherein a variable bit-length code is used for encoding the value, and wherein:

(a) the cue component includes a predefined dimension and a variable length dimension, said predefined dimension always being smaller than the variable length dimension, the variable length dimension indicating a reference orientation and indicating an extent of the code portion; and

(b) the code portion begins with a first binary element at a predefined offset from the cue component, and any additional binary elements extend away from the first binary element in at least one of;

(i) a direction generally parallel to the reference orientation of the cue component, to form a row of binary elements that ends at the extent of the code portion indicated by the variable length dimension;

(ii) a direction generally perpendicular to the variable length dimension, to form a matrix of binary elements that end when a row does not include at least one binary element that is detectable by the surface sensing system; and

(iii) predefined directions and predefined distances relative to an immediately preceding binary element, to form a series of binary elements at predefined locations relative to each other.

6. The two-dimensional identifier of claim 1, wherein the value is encoded using a multi-level, variable bit-length code, and wherein:

(a) the cue component is detectable at a binarization threshold, the cue component having a predefined shape with at least one variable length dimension, and the at least one variable length dimension indicates a reference orientation and indicates an extent of the code portion; and

(b) the code portion comprises at least one binary element that is detectable at a gray scale threshold, but is not detectable at the binarization threshold.

7. The two-dimensional identifier of claim 6, wherein the at least one binary element that is detectable at the gray scale threshold is disposed within the cue component such that the cue component is uniform at the binarization threshold, but reveals the at least one binary element at the gray scale threshold.

8. The two-dimensional identifier of claim 6, wherein the code portion begins with a first binary element disposed at a predefined offset from a local origin disposed at a predefined location relative to the cue component, and any additional binary elements extend away from the first binary element in at least one of:

(a) a direction generally parallel to an axis used by the surface sensing system; and

(b) predefined directions and predefined distances relative to an immediately preceding binary element to form a series of binary elements at predefined locations relative to each other such that the code portion comprises a predefined shape.

9. A method for determining a value from a two-dimensional identifier applied to an object when the object is placed adjacent to a surface of a surface sensing system, comprising the steps of:

(a) detecting a cue component of the two-dimensional identifier, the cue component comprising a contiguous area that is detectable by the surface sensing system and is encompassed by a border region that is not sensed by the surface sensing system as being part of the two-dimensional identifier and which functions as an interference mask around the cue component to minimize noise;

(b) approximating the cue component as an ellipse having a major axis and a minor axis, to determine a position and orientation of the cue component relative to the surface sensing system;

(c) locating a beginning of a code portion of the two-dimensional identifier relative to the position and orientation of the cue component, the value being encoded in the code portion by a plurality of binary elements, each of a predefined area and the code portion also being encompassed by the border region, which also functions as an interference mask around the code portion to minimize noise;

(d) detecting the plurality of binary elements at predefined locations relative to one of the beginning of the code portion and to each other, with the surface sensing system;

(e) decoding the value that is encoded as a function of the plurality of binary elements that are detected; and

(f) determining an object identifier associated with the value of the two-dimensional identifier.

10. The method of claim 9, further comprising the steps of:

(a) illuminating the two-dimensional identifier with infrared light; and

(b) detecting infrared light reflected from the cue component and the code portion of the two-dimensional identifier, to detect the orientation of the two-dimensional identifier and to decode the value encoded by the plurality of binary elements.

11. The method of claim 10, further comprising the steps of:

(a) producing a normalized image from the reflection of the infrared light to compensate for a non-uniformity of the infrared light;

(b) producing a binarized image from the normalized image based on a predefined first light intensity threshold;

(c) using the binarized image to determine the cue component; and

(d) using the normalized image to detect the plurality of binary elements based on a second light intensity threshold.

12. The method of claim 9, wherein the value is encoded using a radial code, further comprising the steps of:

(a) determining that the cue component comprises a contiguous radial area;

(b) detecting that a sub-area of the contiguous radial area is missing from the contiguous radial area at a first predefined radius from a center of the radial area, the sub-area representing a start bit that from which the beginning of the code portion is to be located;

(c) locating the beginning of the code portion relative to the sub-area and at a second predefined radius from the center of the radial area, said second predefined radius being greater than the first predefined radius; and

(d) detecting the plurality of binary elements along an arc at the second predefined radius, said arc being generally concentric relative to the cue component.

13. The method of claim 9, wherein the identifier corresponds to spots of a die, further comprising the steps of:

(a) determining that the cue component comprises a square having dimensions that are substantially equal to predefined dimensions of the die;

(b) determining the orientation of the cue component by rotating a square template until the square template generally aligns with the cue component; and

(c) detecting the plurality of binary elements at predefined locations within the cue component, the predefined locations corresponding to a three-by-three square grid of possible spots of the die aligned with the orientation of the cue component.

14. The method of claim 9, wherein the value is encoded using a variable length linear code, further comprising the steps of:

(a) determining that the cue component comprises substantially parallel strips of equal length that are connected at a first end by a predefined area that is used as a start bit, the strips being separated at a second end that is opposite the first end by a second predefined area that is used as an end bit;

(b) locating the beginning of the code portion relative to the predefined area at the first end and between the strips; and

(c) detecting the plurality of binary elements between the start bit and the end bit along a center axis that is generally centrally disposed between the strips and is substantially parallel to the strips.

15. The method of claim 9, wherein the value is encoded using a variable bit-length code, further comprising the steps of:

(a) determining that the cue component has a predefined dimension and a variable length dimension, said predefined dimension being smaller than the variable length dimension, the variable length dimension corresponding to a primary axis of the ellipse that approximates the cue component, which indicates a reference orientation and an extent of the code portion;

(b) determining a maximum possible number of binary elements in a row based on the variable length dimension of the cue component;

(c) locating the beginning of the code portion disposed at a predefined offset from the cue component; and

(d) detecting the plurality of binary elements in at least one of;

(i) a direction generally parallel to the reference orientation of the code component, to form a row of binary elements that ends at the extent of the code portion indicated by the variable length dimension;

(ii) a direction generally perpendicular to the variable length dimension, to form multiple rows of binary elements that end when a row that does not include at least one binary element is detected; and

(iii) predefined directions and predefined distances relative to an immediately preceding binary element, to form a series of binary elements at predefined locations.

16. The method of claim 9, wherein the value is encoded using a multi-level, variable bit-length code, further comprising the steps of:

(a) detecting the cue component at a binarization threshold; and

(b) detecting the code portion at a gray scale threshold that is not detectable at the binarization threshold.

17. The method of claim 16, wherein the code portion that is detectable at the gray scale threshold is disposed within the cue component such that the cue component is uniform at the binarization threshold, but reveals the code portion at the gray scale threshold.

18. The method of claim 16, wherein the cue component includes a predefined dimension and a variable length dimension, further comprising the steps of:

(a) determining that the predefined dimension is smaller than the variable length dimension, the variable length dimension corresponding to a primary axis of the ellipse that approximates the cue component, which indicates a reference orientation and an extent of the code portion;

(b) determining a maximum possible number of binary elements in a row based on the variable length dimension of the cue component;

(c) locating a beginning of the code portion at a predefined offset from the cue component; and

(d) detecting the plurality of binary elements in at least one of;

(i) a direction generally parallel to the reference orientation of the cue component, to form a row of binary elements that ends at an extent of the code portion indicated by the variable length dimension;

(ii) a perpendicular direction to the variable length dimension to form a matrix of binary elements that end when a row does not include at least one binary element that is detectable; and

(iii) predefined directions and predefined distances relative to an immediately preceding binary element to form a series of binary elements at predefined locations.

19. The method of claim 16, further comprising the steps of:

(a) locating a beginning of the code portion at a predefined offset from a local origin, the local origin being disposed at a predefined location relative to the cue component; and

(b) detecting the plurality of binary elements in at least one of;

(i) a direction generally parallel to an axis of the surface sensing system; and

(ii) predefined directions and predefined distances relative to an immediately preceding binary element to form a series of binary elements at predefined locations relative to each other, such that the code portion has a predefined shape.

20. A memory medium having machine readable instructions for carrying out the steps of claim 9.

21. A system for determining a value from a two-dimensional identifier applied to an object, comprising:

(a) an interactive display surface having an interactive side adjacent to which the object can be placed, and an opposite side;

(b) a light source that directs infrared light toward the opposite side of the interactive display surface and through the interactive display surface, to the interactive side;

(c) a light sensor disposed to receive and sense infrared light reflected back from the patterned object through the interactive display surface forming an image that includes the two-dimensional identifier applied to the object;

(d) a processor in communication with the light sensor; and

(e) a memory in communication with the processor, the memory storing data and machine instructions that cause the processor to carry out a plurality of functions, including;

(i) detecting a cue component of the two-dimensional identifier with the light sensor, the cue component comprising a contiguous area that is detectable by the light sensor and is encompassed by a border region that is not sensed by the light sensor as being part of the two-dimensional identifier and which functions as an interference mask around the cue component to minimize noise;

(ii) approximating the cue component as an ellipse having a major axis and a minor axis, to determine a position and orientation of the cue component relative to the interactive display surface;

(iii) locating a beginning of a code portion of the two-dimensional identifier relative to the position and orientation of the cue component, the value being encoded in the code portion by a plurality of binary elements, each of a predefined area and the code portion also being encompassed by the border region, which also functions as an interference mask around the code portion to minimize noise;

(iv) detecting the plurality of binary elements at predefined locations relative to one of the beginning of the code portion and to each other, with the light sensor; and

(v) decoding the value that is encoded as a function of the plurality of binary elements that are detected.

22. The system of claim 21, wherein the machine language instructions further cause the processor to detect infrared light reflected from the cue component and the code portion of the two-dimensional identifier with the light sensor, to detect the orientation of the two-dimensional identifier and to decode the value encoded by the plurality of binary elements.

23. The system of claim 22, wherein the machine language instructions further cause the processor to:

(a) produce a normalized image from the reflection of the infrared light to compensate for a non-uniformity of the infrared light;

(b) produce a binarized image from the normalized image based on a predefined first light intensity threshold;

(c) use the binarized image to determine the cue component; and

(d) use the normalized image to detect the plurality of binary elements based on a second light intensity threshold.

24. The system of claim 21, wherein the machine language instructions further cause the processor to determine an object identifier associated with the value of the two-dimensional identifier.

25. The system of claim 21, wherein the value is encoded using a radial code, and wherein the machine language instructions further cause the processor to:

(a) determine that the cue component comprises a contiguous radial area;

(b) detect that a sub-area of the contiguous radial area is missing from the contiguous radial area at a first predefined radius from a center of the radial area, the sub-area representing a start bit that from which the beginning of the code portion is to be located;

(c) locate the beginning of the code portion relative to the sub-area and at a second predefined radius from the center of the radial area, said second predefined radius being greater than the first predefined radius; and

(d) detect the plurality of binary elements along an arc at the second predefined radius, said arc being generally concentric relative to the cue component.

26. The system of claim 21, wherein the identifier corresponds to spots of a die, and wherein the machine language instructions further cause the processor to:

(a) determine that the cue component comprises a square having dimensions that are substantially equal to predefined dimensions of the die;

(b) determine the orientation of the cue component by rotating a square template until the square template generally aligns with the cue component; and

(c) detect the plurality of binary elements at predefined locations within the cue component, the predefined locations corresponding to a three-by-three square grid of possible spots of the die aligned with the orientation of the cue component.