Embedded interaction code recognition

• US 7,599,560 B2
• Filed: 04/22/2005
• Issued: 10/06/2009
• Est. Priority Date: 04/22/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dang, Yingong, Wang, Qiang, Wu, Jiang, Wang, Jian, Chen, Liyong
• Primary Examiner(s): Strege; John B
• Application Number:
  US11/112,604
• Publication Number:
  US 20060242622A1
• Time in Patent Office: 1,628 Days
• Field of Search: 382/187, 382/188, 382/190, 382/192, 382/289, 382/291
• US Class Current: 382/192
• CPC Class Codes: G06F 3/0321 by optically sensing the absolute position with respect to a regularly patterned surface forming a passive digitiser, e.g. pen optically detecting position indicative tags printed on a paper sheet constructional details of pen-shaped pointing devices G06F3/03545, G06F3/03542, G06F3/037
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1456 determining the orientation of the optical code with respect to the reader and correcting therefore

Abstract

In accordance with embodiments of the invention, embedded interaction code (EIC) symbols are recognized. EIC dots are generated based on effective EIC symbols, which have been generated by processing an image containing the EIC symbols, by obtaining graylevels of selected positions of the EIC-symbols. Rotated EIC dots are generated based on the EIC dots by determining which grid cells correspond to the EIC symbols and by determining which direction is a correct orientation of the EIC symbols. A homography matrix is updated with orientation information based on the EIC dots. EIC bits are extracted from the rotated EIC dots based on graylevels of selected positions of the rotated EIC dots.

Claims

1. A method in a computer system for identifying a location of an embedded interaction code (EIC) symbol on a surface, the method comprising using a computer to carry out the steps of:

capturing an image of the surface containing a portion of an EIC pattern having a plurality of grid cells formed by a plurality of grid lines, each grid line having a plurality of data dot positions and orientation dot positions;

for each of a plurality of grid cells within the captured image,

for each grid line portion associated with the grid cell,

determining a graylevel for each of a plurality of data dot positions, and

determining positions of black data dots by comparing the determined graylevels of the data dot positions;

for each of a plurality of orientations of the grid cells, determining the number of black data dots at orientation dot positions;

determining a correct orientation for the EIC pattern and which grid cells correspond to EIC symbols based on which rotated position of the grid cells contains the fewest number of black dots at orientation dot positions;

orienting the EIC pattern based on the determined correct orientation for the EIC pattern;

identifying an EIC symbol in the EIC pattern with the corrected orientation, the EIC symbol having an associated grid cell with edges; and

extracting bits from at least one edge of the grid cell associated with the identified EIC symbol based on the position of a black data dot on the at least one edge

wherein the extracted bits are used to determine the position of the identified EIC symbol relative to the surface.

2. The method of claim 1, wherein the extracted bits are selected based on whether a predetermined number of neighboring dots of the black dot on the at least one edge are valid.

3. The method of claim 1, further comprising:

updating a homography matrix based on the determined correct orientation for the EIC pattern, the homography matrix for transforming from the coordinate system of the EIC pattern to the coordinate system of the image,

wherein the homography matrix is used in the process of identifying grid lines.

4. The method of claim 1, further comprising:

producing confidence values that correspond to the extracted bits.

5. The method of claim 1 wherein determining positions of black data dots includes:

identifying the darkest data dot position based on the determined graylevels;

identifying the second darkest data dot position based on the determined graylevels; and

when the difference between the graylevels of the darkest data dot position and the second darkest data dot position exceeds a threshold, designating the darkest data dot position as a black dot.

6. The method of claim 1 wherein each grid line portion associated with each grid cell includes four data dot positions and one orientation dot position.

7. The method of claim 6, further comprising:

when a first data dot position is black, the extracted bits are 00,

when a second data dot position is black, the extracted bits are 01,

when a third data dot position is black, the extracted bits are 11, and

when a fourth data dot position is black, the extracted bits are 10.

8. A computer-readable storage medium containing instructions for executing a method for identifying a location of an embedded interaction code (EIC) symbol on a surface, the method comprising:

capturing an image of the surface containing a portion of an EIC symbol array having a plurality of grid cells formed by a plurality of grid lines, each grid line having a plurality of data dot positions and orientation dot positions;

for each of a plurality of grid cells within the captured image,

determining a graylevel for each of a plurality of data dot positions located on each grid line portion associated with the grid cell, and

determining positions of black data dots by comparing the determined graylevels of the data dot positions;

for each of a plurality of orientations of the grid cells, determining the number of black data dots at orientation dot positions;

determining a correct orientation for the EIC symbol array and which grid cells correspond to EIC symbols based on which rotated position of the grid cells contains the fewest number of black dots at orientation dot positions;

orienting the EIC symbol array based on the determined correct orientation for the EIC symbol array;

identifying an EIC symbol in the EIC pattern with the corrected orientation, the EIC symbol having an associated grid cell;

extracting bits from at least one edge of the grid cell associated with the identified EIC symbol based on the position of a black data dot on the at least one edge; and

determining the position of the identified EIC symbol relative to the surface based at least in part on the extracted bits.

9. The computer-readable storage medium of claim 8, wherein the extracted bits are selected based on whether a predetermined number of neighboring dots of the black dot on the at least one edge are valid.

10. The computer-readable storage medium of claim 8, further comprising:

updating a homography matrix based on the determined correct orientation for the EIC symbol array, the homography matrix for transforming from the coordinate system of the EIC symbol array to the coordinate system of the image,

wherein the homography matrix is used in the process of identifying grid lines.

11. The computer-readable storage medium of claim 8, further comprising:

producing confidence values that correspond to the extracted bits.

12. The computer-readable storage medium of claim 8 wherein determining positions of black data dots includes:

identifying the darkest data dot position based on the determined graylevels;

identifying the second, darkest data dot position based on the determined graylevels; and

when the difference between the graylevels of the darkest data dot position and the second darkest data dot position exceeds a threshold, designating the darkest data dot position as a black dot.

13. The computer-readable storage medium of claim 8 wherein each grid line portion associated with each grid cell includes four data dot positions and one orientation dot position.

14. The computer-readable storage medium of claim 13, further comprising:

when a first data dot position is black, the extracted bits are 00,

when a second data dot position is black, the extracted bits are 01,

when a third data dot position is black, the extracted bits are 11, and

when a fourth data dot position is black, the extracted bits are 10.

15. A system for identifying a location of an embedded interaction code (EIC) symbol on a surface, the system comprising:

a component that captures an image of the surface containing a portion of an EIC symbol array having a plurality of grid cells formed by a plurality of grid lines, each grid line having a plurality of data dot positions and orientation dot positions;

a component that, for each of a plurality of grid cells within the captured image,

determines a graylevel for each of a plurality of data dot positions located on each grid line portion associated with the grid cell, and

determines positions of black data dots by comparing the determined graylevels of the data dot positions;

a component that, for each of a plurality of orientations of the grid cells, determines the number of black data dots at orientation dot positions;

a component that determines a correct orientation for the EIC symbol array and which grid cells correspond to EIC symbols based on which rotated position of the grid cells contains the fewest number of black dots at orientation dot positions;

a component that orients the EIC symbol array based on the determined correct orientation for the EIC symbol array;

a component that identifies an EIC symbol in the EIC pattern with the corrected orientation, the EIC symbol having an associated grid cell;

a component that extracts bits from at least one edge of the grid cell associated with the identified EIC symbol based on the position of a black data dot on the at least one edge; and

a component that determines the position of the identified EIC symbol relative to the surface based at least in part on the extracted bits.

16. The system of claim 15, wherein the extracted bits are selected based on whether a predetermined number of neighboring dots of the black dot on the at least one edge are valid.

17. The system of claim 15, further comprising:

a component that updates a homography matrix based on the determined correct orientation for the EIC symbol array, the homography matrix for transforming from the coordinate system of the EIC symbol array to the coordinate system of the image,

wherein the homography matrix is used in the process of identifying grid lines.

18. The system of claim 15, further comprising:

producing confidence values that correspond to the extracted bits.

19. The system of claim 15 wherein the component that determines positions of black data dots includes:

a component that identifies the darkest position based on the determined graylevels;

a component that identifies the second darkest position based on the determined graylevels; and

a component that, when the difference between the graylevels of the darkest position and the second darkest position exceeds a threshold, designates the darkest position as a black dot.

20. The system of claim 15 wherein each grid line portion associated with each grid cell includes four data dot positions and one orientation dot position and wherein the orientation dot position is always white.