Efficient finder patterns and methods for application to 2D machine vision problems

• US 20060269136A1
• Filed: 05/23/2006
• Published: 11/30/2006
• Est. Priority Date: 05/23/2005
• Status: Active Grant

• Current Assignee: Nextcode Corporation
• Original Assignee: Nextcode Corporation
• Inventors: Squires, Sanford R., Levinger, James K.
• Granted Patent: US 7,412,089 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• CPC Class Codes: G06K 19/06028 using bar codes
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• 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 7/1443 locating of the code in an image
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

The invention relates to a finder pattern for detection and location of at least one target feature in a target object. The finder pattern includes at least two triads arranged in predetermined locations in the target object, wherein each triad includes a first blob, a second blob, and a third blob, wherein each blob has substantially the same area and is positioned in a predetermined location in the target object. The locations of the first and second blobs are substantially equidistant from the third blob, and the locations of the first, second, and third blobs are not collinear. The invention further relates to a method for detecting a finder pattern in a target object, and a computer readable medium having instructions stored therein for detecting a finder pattern in a target object, which, when executed by a processor of a computing device, cause the computing device to carry out the steps of the method.

Claims

1. A finder pattern for detection and location of at least one target feature in a target object, comprising:

at least two triads arranged in predetermined locations in the target object, wherein each triad includes a first blob, a second blob, and a third blob,

wherein each blob has substantially the same area and is positioned in a predetermined location in the target object,

wherein the locations of the first and second blobs are substantially equidistant from the third blob, and

wherein the locations of the first, second, and third blobs are not collinear.

2. The finder-pattern of claim 1, further comprising at least one solo arranged in a predetermined location in the target object, wherein each solo includes a single blob having a predetermined location in the target object relative to the triads.

3. The finder pattern of claim 1, wherein at least two of the triads are linked with a linking vector.

4. The finder pattern of claim 2, wherein at least one of the triads and at least one solo are linked with a linking vector.

5. The finder pattern of claim 1, wherein the target object has at least one detectable characteristic selected from the group consisting of a machine readable code, a color pattern, a radiation pattern, one or more raised surface elements, and one or more holes.

6. The finder pattern of claim 1, wherein the first, second, and third blobs have substantially the same shape.

7. The finder pattern of claim 1, wherein each blob is geometrically shaped.

8. The finder pattern of claim 1, wherein the finder pattern is arranged on a two-dimensional planar surface or a curved surface.

9. The finder pattern of claim 1 or claim 2, wherein the triad and solo locations form corner positions of at least one of a L-type shape, a triangle-type shape, a regular polygon-type shape, a irregular polygon-type shape, and an oval-type shape.

10. The finder pattern of claim 1, wherein the target feature comprises at least one of graphical elements, detectable visual characteristics, and machine readable code including data.

11. A finder pattern for detection and location of target features in a target object, comprising at least two triads arranged in predetermined locations in the target object, wherein the triads are linked with a linking vector.

12. The finder pattern of claim 11, further comprising at least one solo arranged in a predetermined location in the target object.

13. The finder pattern of claim 12, wherein at least two of the triads and at least one solo are linked with one or more linking vectors.

14. The finder pattern of claim 11, wherein each of the triads includes a first blob, a second blob, and a third blob having substantially the same area, wherein the locations of the first and second blobs are substantially equidistant from the location of the third blob, and wherein the locations of the first, second, and third blobs are not collinear.

15. A method for detecting a finder pattern in a target object, the method comprising the steps of:

processing an image of a target object;

identifying six or more blobs in the image;

identifying two or more potential triads in the image using the six or more identified blobs;

determining information about one or more characteristics of the two or more potential triads; and

determining whether the information about the characteristics of two or more of the potential triads corresponds to information about one or more characteristics of two or more target triads in a finder pattern specification, wherein the finder pattern specification includes information about the characteristics of the two or more target triads.

16. The method of claim 15, wherein the information about the characteristics of the two or more target triads in the finder pattern specification includes at least one of positional information about the target triads and information about the visual characteristics of the target triads.

17. The method of claim 15, wherein the information about the characteristics of the two or more potential triads in the finder pattern specification includes at least one of positional information about the potential triads and information about the visual characteristics of the potential triads.

18. The method of claim 15, further comprising a step of sensing the target object prior to the step of processing the image, wherein the step of sensing comprises reading the target object with a sensor.

19. The method of claim 18, wherein the sensor is selected from the group consisting of a scanner, a camera, and a range finder.

20. The method of claim 15, further comprising a step of generating a list of attributes of at least one of the potential triads by performing at least one of a binarization technique, a flat fielding technique, a creation of contour boundaries technique, or an edge detection and linking of edge boundaries around blobs technique.

21. The method of claim 15, further comprising the step of reducing the image noise with a noise reduction filter prior to the step of identifying the six or more blobs in the image.

22. The method of claim 15, further comprising the step of eliminating blobs having one or more attributes that do not meet a predetermined criterion prior to the step of identifying the two or more potential triads.

23. The method of claim 15, further comprising the step of processing the finder pattern specification using a computing device prior to the step of determining whether the information about the characteristics of two or more of the potential triads corresponds to information about one or more characteristics of two or more target triads in the finder pattern specification.

24. A computer readable medium having instructions stored therein for detecting a finder pattern in a target object, which, when executed by a processor of a computing device, cause the computing device to carry out the steps of:

processing an image of a target object;

identifying six or more blobs in the image;

identifying two or more potential triads in the image using the six or more identified blobs;

determining information about one or more characteristics of the two or more potential triads; and

determining whether the information about the characteristics of two or more of the potential triads corresponds to information about one or more characteristics of two or more target triads in a finder pattern specification, wherein the finder pattern specification includes information about the characteristics of the two or more target triads.

25. The computer readable medium of claim 24, wherein the information about the characteristics of the two or more target triads in the finder pattern specification includes at least one of positional information about the target triads and information about the visual characteristics of the target triads.

26. The computer readable medium of claim 24, wherein the information about the characteristics of the two or more potential triads in the finder pattern specification includes at least one of positional information about the potential triads and information about the visual characteristics of the potential triads.

27. The computer readable medium of claim 24, further comprising instructions for sensing the target object prior to the step of processing the image, wherein the step of sensing comprises reading the target object with a sensor.

28. The computer readable medium of claim 27, wherein the sensor is selected from the group consisting of a scanner, a camera, and a range finder.

29. The computer readable medium of claim 24, further comprising instructions for generating a list of attributes of at least one of the potential triads by performing at least one of a binarization technique, a flat fielding technique, a creation of contour boundaries technique, or an edge detection and linking of edge boundaries around blobs technique.

30. The computer readable medium of claim 24, further comprising instructions for reducing the image noise with a noise reduction filter prior to the step of identifying the six or more blobs in the image.

31. The computer readable medium of claim 24, further comprising instructions for eliminating blobs having one or more attributes that do not meet a predetermined criterion prior to the step of identifying the two or more potential triads.

32. The computer readable medium of claim 24, fuirther comprising instructions for processing the finder pattern specification using a computing device prior to the step of determining whether the information about the characteristics of two or more of the potential triads corresponds to information about one or more characteristics of two or more target triads in the finder pattern specification.