Method and apparatus for locating a two-dimensional symbol using a double template

• US 6,122,410 A
• Filed: 12/30/1994
• Issued: 09/19/2000
• Est. Priority Date: 03/01/1993
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Lai, Jiansu, Zheng, Joe
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/367,683
• Time in Patent Office: 2,090 Days
• Field of Search: 382/317, 382/306, 382/291, 382/209, 235/494, 356/392, 356/393
• US Class Current: 382/291
• CPC Class Codes: G06K 19/06168 the marking being a concentric barcode
• CPC Class Codes: G06K 7/1092 sensing by means of TV-scanning
• 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/1417 2D bar codes
• CPC Class Codes: G06K 7/1421 Circular bar codes
• CPC Class Codes: G06K 7/1443 locating of the code in an image

Abstract

In a method and apparatus for locating the acquisition target of a two-dimensional symbol in a pixel image, the image is convolved with a double template. The position with the greatest correlation coefficient between the double template and the image is selected as the location of the acquisition target. The double template comprises two identical parallel one-dimensional single templates corresponding to two lines that cross the symmetrical acquisition target at equal distances from the center of the acquisition target. Using a double template instead of only a single template reduces the possibility of finding false positive locations of the acquisition target. Since the double template comprises two identical halves, the image is preferably convolved with only one half of the double template and the double-template correlation coefficients are then generated from these intermediate single-template correlation results. In a preferred embodiment, a binary pixel image is run-length encoded prior to being convolved with a run-length-encoded template.

Claims

1. A computer-implemented method for locating the position of an imaged acquisition target in a pixel image, comprising the following steps:

(a) generating image signals corresponding to said image with a camera, said image comprising said imaged acquisition target;

(b) comparing said image signals with template signals corresponding to a double template at a plurality of positions within said image using a processor, said double template corresponding to an ideal acquisition target, wherein said double template comprises two identical halves; and

(c) locating the position of said imaged acquisition target in said image using the processor in accordance with said comparisons of step (b).

2. The method of claim 1, further comprising the step of decoding a two-dimensional symbol corresponding to said located imaged acquisition target using the processor.

3. The method of claim 1, further comprising the step of characterizing the quality of at least a portion of said image using the processor.

4. The method of claim 1, wherein step (b) comprises the step of calculating a plurality of correlation coefficients between said double template and said image at said plurality of positions within said image using the processor, and step (c) comprises the step of locating said imaged acquisition target in said image in accordance with said plurality of correlation coefficients using the processor.

5. The method of claim 4, wherein step (c) comprises the step of selecting the position corresponding to the greatest correlation coefficient of said plurality of correlation coefficients as the location of said imaged acquisition target in said image using the processor.

6. The method of claim 1, wherein said ideal acquisition target comprises a series of concentric rings.

7. The method of claim 6, wherein said ideal acquisition target is associated with a two-dimensional symbol having a plurality of polygonal cells.

8. The method of claim 1, wherein said double template corresponds to two rows of said ideal acquisition target.

9. The method of claim 1, wherein said ideal acquisition target is symmetric about its center, and said double template comprises two identical single templates, wherein said two single templates correspond to two identical rows of said ideal acquisition target.

10. The method of claim 9, wherein step (b) comprises the steps of:

(1) calculating a plurality of single-template correlation coefficients between one of said two single templates and said image at a plurality of positions within said image using the processor; and

(2) calculating a plurality of double-template correlation coefficients in accordance with said plurality of single-template correlation coefficients using the processor;

and step (c) comprises the step of locating said imaged acquisition target in said image in accordance with said plurality of double-template correlation coefficients using the processor.

11. The method of claim 1, wherein step (b) comprises the steps of:

(1) run-length encoding said image to generate a run-length-encoded image using the processor; and

(2) comparing said run-length-encoded image with a run-length-encoded double template corresponding to said ideal acquisition target at a plurality of positions within said run-length-encoded image using the processor.

12. An apparatus for locating the position of an imaged acquisition target in a pixel image, comprising:

(a) a camera for generating image signals corresponding to said image, said image comprising said imaged acquisition target; and

(b) a processor for comparing said image signals with template signals corresponding to a double template at a plurality of positions within said image, said double template corresponding to an ideal acquisition target, wherein said double template comprises two identical halves; and

for locating the position of said imaged acquisition target in said image in accordance with said comparisons.

13. The apparatus of claim 12, wherein the processor decodes a two-dimensional symbol corresponding to said located imaged acquisition target.

14. The apparatus of claim 12, wherein the processor characterizes the quality of at least a portion of said image.

15. The apparatus of claim 12, wherein the processor calculates a plurality of correlation coefficients between said double template and said image at said plurality of positions within said image, and the processor locates said imaged acquisition target in said image in accordance with said plurality of correlation coefficients.

16. The apparatus of claim 15, wherein the processor selects the position corresponding to the greatest correlation coefficient of said plurality of correlation coefficients as the location of said imaged acquisition target in said image.

17. The apparatus of claim 12, wherein said ideal acquisition target comprises a series of concentric rings.

18. The apparatus of claim 17, wherein said ideal acquisition target is associated with a two-dimensional symbol having a plurality of polygonal cells.

19. The apparatus of claim 12, wherein said double template corresponds to two rows of said ideal acquisition target.

20. The apparatus of claim 12, wherein said ideal acquisition target is symmetric about its center, and said double template comprises two identical single templates, wherein said two single templates correspond to two identical rows of said ideal acquisition target.

21. The apparatus of claim 20, wherein the processor:

(1) calculates a plurality of single-template correlation coefficients between one of said two single templates and said image at a plurality of positions within said image;

(2) calculates a plurality of double-template correlation coefficients in accordance with said plurality of single-template correlation coefficients; and

(3) locates said imaged acquisition target in said image in accordance with said plurality of double-template correlation coefficients.

22. The apparatus of claim 12, wherein the processor:

(1) run-length encodes said image to generate a run-length-encoded image; and

(2) compares said run-length-encoded image with a run-length-encoded double template corresponding to said ideal acquisition target at a plurality of positions within said run-length-encoded image.

23. A computer-implemented method for locating the position of an imaged acquisition target in a pixel image, comprising the following steps:

(a) generating image signals corresponding to said image with a camera, said image comprising said imaged acquisition target;

(b) comparing said image signals with template signals corresponding to a double template at a plurality of positions within said image using a processor, said double template corresponding to an ideal acquisition target, wherein at least one half of said double template does not correspond with a center of said ideal acquisition target; and

(c) locating the position of said imaged acquisition target in said image using the processor in accordance with said comparisons of step (b).

24. The method of claim 23, further comprising the step of decoding a two-dimensional symbol corresponding to said located imaged acquisition target using the processor.

25. The method of claim 23, further comprising the step of characterizing the quality of at least a portion of said image using the processor.

26. The method of claim 23, wherein step (b) comprises the step of calculating a plurality of correlation coefficients between said double template and said image at said plurality of positions within said image using the processor, and step (c) comprises the step of locating said imaged acquisition target in said image in accordance with said plurality of correlation coefficients using the processor.

27. The method of claim 26, wherein step (c) comprises the step of selecting the position corresponding to the greatest correlation coefficient of said plurality of correlation coefficients as the location of said imaged acquisition target in said image using the processor.

28. The method of claim 23, wherein said ideal acquisition target comprises a series of concentric rings.

29. The method of claim 28, wherein said ideal acquisition target is associated with a two-dimensional symbol having a plurality of polygonal cells.

30. The method of claim 23, wherein said double template corresponds to two rows of said ideal acquisition target.

31. The method of claim 23, wherein said ideal acquisition target is symmetric about its center, and said double template comprises two identical single templates, wherein said two single templates correspond to two identical rows of said ideal acquisition target.

32. The method of claim 31, wherein step (b) comprises the steps of:

(1) calculating a plurality of single-template correlation coefficients between one of said two single templates and said image at a plurality of positions within said image using the processor; and

(2) calculating a plurality of double-template correlation coefficients in accordance with said plurality of single-template correlation coefficients using the processor;

and step (c) comprises the step of locating said imaged acquisition target in said image in accordance with said plurality of double-template correlation coefficients using the processor.

33. The method of claim 23, wherein step (b) comprises the steps of:

(1) run-length encoding said image to generate a run-length-encoded image using the processor; and

(2) comparing said run-length-encoded image with a run-length-encoded double template corresponding to said ideal acquisition target at a plurality of positions within said run-length-encoded image using the processor.

34. An apparatus for locating the position of an imaged acquisition target in a pixel image, comprising:

(a) a camera for generating image signals corresponding to said image, said image comprising said imaged acquisition target; and

(b) a processor;

for comparing said image signals with template signals corresponding to a double template at a plurality of positions within said image, said double template corresponding to an ideal acquisition target, wherein at least one half of said double template does not correspond with a center of said ideal acquisition target; and

for locating the position of said imaged acquisition target in said image in accordance with said comparisons.

35. The apparatus of claim 34, wherein the processor decodes a two-dimensional symbol corresponding to said located imaged acquisition target.

36. The apparatus of claim 34, wherein the processor characterizes the quality of at least a portion of said image.

37. The apparatus of claim 34, wherein the processor calculates a plurality of correlation coefficients between said double template and said image at said plurality of positions within said image, and the processor locates said imaged acquisition target in said image in accordance with said plurality of correlation coefficients.

38. The apparatus of claim 37, wherein the processor selects the position corresponding to the greatest correlation coefficient of said plurality of correlation coefficients as the location of said imaged acquisition target in said image.

39. The apparatus of claim 34, wherein said ideal acquisition target comprises a series of concentric rings.

40. The apparatus of claim 39, wherein said ideal acquisition target is associated with a two-dimensional symbol having a plurality of polygonal cells.

41. The apparatus of claim 34, wherein said double template corresponds to two rows of said ideal acquisition target.

42. The apparatus of claim 34, wherein said ideal acquisition target is symmetric about its center, and said double template comprises two identical single templates, wherein said two single templates correspond to two identical rows of said ideal acquisition target.

43. The apparatus of claim 42, wherein the processor:

(1) calculates a plurality of single-template correlation coefficients between one of said two single templates and said image at a plurality of positions within said image;

(2) calculates a plurality of double-template correlation coefficients in accordance with said plurality of single-template correlation coefficients; and

(3) locates said imaged acquisition target in said image in accordance with said plurality of double-template correlation coefficients.

44. The apparatus of claim 34, wherein the processor:

(1) run-length encodes said image to generate a run-length-encoded image; and

(2) compares said run-length-encoded image with a run-length-encoded double template corresponding to said ideal acquisition target at a plurality of positions within said run-length-encoded image.