Marker and method for detecting said marker

• US 7,769,236 B2
• Filed: 10/31/2006
• Issued: 08/03/2010
• Est. Priority Date: 10/31/2005
• Status: Active Grant

• Current Assignee: Millennium Three Technologies Inc
• Original Assignee: National Research Council Canada
• Inventors: Fiala, Mark
• Primary Examiner(s): Mariam; Daniel G
• Application Number:
  US11/589,726
• Publication Number:
  US 20070098234A1
• Time in Patent Office: 1,372 Days
• Field of Search: 382/103, 382/181, 382/182, 382/184, 382/190, 382/199, 382/201, 382/225
• US Class Current: 382/225
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30208 Marker matrix
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit

Abstract

This invention discloses marker detectable by visual means comprising; a polygonal border having of at least four non collinear salient points. The marker has on it a pattern in binary digital code. The binary code data contains information data, checksum and error correction. The binary code data is on two levels; a first level of binary code readable at a first given distance, a second level of binary code readable at a second given distance, where the second given distance is less than the first given distance and the second level binary code is smaller in size than the first level binary code. The second level of binary code does not interfere with the reading of the first level binary code. It also discloses a method for detecting a marker comprising the steps of detecting an image, using an edge detector to detect an edge in said image, grouping more than one edge into a polygon having salient points, calculating homography from polygon salient points, generating a list of homographies, extracting binary data from input image having homographies, identifying and verifying binary data.

Claims

1. A marker detectable by visual means comprising:

a. a polygonal border comprising of at least four non collinear salient points;

b. a binary digital code on said marker;

c. the binary digital code comprising information data, checksum and error correction;

d. a first level of binary digital code readable at a first given distance;

e. a second level of binary digital code readable at a second given distance;

f. where said second given distance is less than said first given distance; and

g. where said second level binary digital code is smaller in size than the first level binary digital code and does not interfere with the reading of said first level binary digital code.

2. The marker of claim 1 where the binary digital code is located inside the polygonal border.

3. The marker of claim 2 where the information data comprises unique identification information to link to a web site.

4. The marker of claim 2 where the border is a quadrilateral.

5. The marker of claim 1 where the first level of binary digital code is a NXM array of cells and the second level of binary digital code is located along the borders of the cells between the cells.

6. The marker of claim 5 where the first level of binary digital code is an NXN array of cells containing white or black patterns and the second level of binary digital code is an MXM array of cells also containing black or white patterns.

7. The marker of claim 6 where N is one of 4, 5, 6, 7, 8, 9, 10, 11, 12, or 13, and where M is 4, 5, 6, 7, 8, 9, 10, 11, 12, or 13.

8. The marker of claim 1 where the binary digital code is selected so as to have a minimal hamming distance from all other markers in all four possible rotation positions, mirrored position and from itself rotated in all four positions.

9. The marker of claim 1 where the first level of binary digital code is an 6=6 array of cells and second level of binary digital code is a smaller set of cells in the corners or between the first level cells and on the line bordering two first level cells.

10. The marker of claim 9 where the first level of binary digital code carries 26 bits of information data and 10 bits for checksum and error correction, and the second level of binary digital code comprises four quadrants, each quadrant comprising 31 cells, where the 31 cells carry 16 bits of information data, 5 bits of checksum and 10 bits of error correction.

11. The marker of claim 10 where two of the four quadrants contain redundant information.

12. A method for detecting a marker comprising the steps:

a. detecting an image to be evaluated using an image sensor;

b. using an edge detector to detect an edge in said image;

c. grouping more than one edge into a polygon having salient points;

d. calculating homography from polygon salient points;

e. generating a list of homographies;

f. extracting binary data from input image having homographies;

q. verifying if the image is a marker by performing check sum and error correction functions;

h. if the image is a marker, identify as a marker and verify binary data.

13. The method of claim 12 where there is an additional step of processing the marker in all possible rotation positions.

14. The method of claim 12 where there is an additional step of identifying and verifying a 2^nd level of binary digital code.

15. A method for identifying a marker comprising:

a. detecting a potential marker to be evaluated using an image sensor;

b. detecting edgels using an edge detector;

c. grouping edgels into line segments;

d. making a list of line segments;

e. grouping line segments into polygons;

f. making a list of polygons.

16. The method of claim 15 where the detection of the potential marker is made at different resolutions.

17. The method of claim 16 where the different resolutions are full resolution, half resolution and quarter resolution.

18. The method of claim 15 where the polygons of step e) are evaluated based on the following five heuristic rules;

a. when the border can be found by joining the line segments,

b. when the border is found when one or more corners are missing but the border lies entirely within the image,

c. when a line segment is broken when the border lies entirely within the image,

d. when one or more corners are missing in the detected image

e. when one or more line segments are missing in the detected image.