Method and apparatus for determining the vertices of a character in a two-dimensional barcode symbol

• US 20060043189A1
• Filed: 08/31/2004
• Published: 03/02/2006
• Est. Priority Date: 08/31/2004
• Status: Abandoned Application

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Clarke, Ian, Thiyagarajah, Mohanaraj, Agrawal, Sachin, Kwok, Derek
• Application Number:
  US10/930,596
• Publication Number:
  US 20060043189A1
• Time in Patent Office: Days
• US Class Current: 235/462.80
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence

Abstract

A method of determining the vertices of a character in a two-dimensional barcode symbol image includes tracing a contour around a character. The contour is examined and pixels therealong believed to be vertices of the character are determined. The relative positions of the determined pixels are compared to determine if they satisfy a threshold. If the relative positions of the determined pixels satisfy the threshold, the determined pixels are designated as the vertices of the character. If the relative positions of the determined pixels satisfy the threshold, the determined pixels are designated as the vertices of the character. If the relative positions of the determined pixels do not satisfy the threshold, new pixels along the contour are selected using geometric relationships between the determined pixels to replace determined pixels that are not vertices of the character.

Claims

1. A method of determining the vertices of a character in a two-dimensional barcode symbol image comprising:

tracing a contour around said character;

examining the contour and determining pixels therealong believed to be vertices of said character;

comparing the relative positions of the determined pixels to determine if they satisfy a threshold;

if the relative positions of the determined pixels satisfy the threshold, designating the determined pixels as the vertices of said character; and

if the relative positions of the determined pixels do not satisfy the threshold, selecting new pixels along said contour using geometric relationships between the determined pixels to replace determined pixels that are not vertices of said character.

2. The method of claim 1 wherein during said examining, pixels believed to be vertices of said character are determined in pairs.

3. The method of claim 2 wherein during said examining, a first pair of determined pixels representing one set of vertices of said character is initially determined and thereafter, a second pair of determined pixels believed to represent another set of vertices of said character is estimated.

4. The method of claim 3 wherein during selecting, the determined pixels of said second pair are replaced.

5. The method of claim 4 further comprising, after said comparing has determined that the relative positions of the determined pixels satisfy the threshold, performing fine-tuning to select new pixels along said contour to replace determined pixels of the second pair that are near to but are not vertices of the character.

6. The method of claim 4 wherein said examining comprises:

comparing the distance between each pair of pixels along the contour to locate the pair of pixels having the greatest distance therebetween thereby to locate said first pair of determined pixels; and

determining the two pixels along said contour on opposite sides of a line joining the determined pixels of said first pair that are furthest from said line thereby to locate said second pair of determined pixels.

7. The method of claim 6 wherein comparing the relative positions of determined pixels comprises:

determining the perpendicular distance between each determined pixel of said second pair to said line; and

comparing the determined distances to determine if they vary beyond said threshold.

8. The method of claim 7 wherein the determined distances are determined to vary beyond said threshold if the determined distances vary by a factor of two or more.

9. The method of claim 8 wherein when the determined distances vary beyond said threshold, said selecting comprises:

determining the pixel along the contour that is furthest from a line joining one of the determined pixels of said first pair and the determined pixel of said second pair that is furthest from the line joining the determined pixels of said first pair; and

determining the pixel along the contour that is furthest from a line joining the other of the determined pixels of said first pair and the determined pixel of said second pair that is furthest from the line joining the determined pixels of said first pair.

10. The method of claim 9 wherein said fine-tuning comprises:

for each pixel along the contour joining the determined pixels of the first pair in a first direction;

calculating the distance between the pixel and the line joining the determined pixels of the first pair;

calculating the distance between the pixel and the furthest determined pixel of the second pair; and

summing calculated distances to yield a first resultant sum;

determining the pixel yielding the greatest first resultant sum thereby to select a new vertex of said character;

for each pixel along the contour joining the determined pixels of the first pair in a second opposite direction;

calculating the distance between the pixel and the line joining the determined pixels of the first pair;

calculating the distance between the pixel and the furthest determined pixel of the second pair; and

summing calculated distances to yield a second resultant sum;

determining the pixel yielding the greatest second resultant sum thereby to select a new vertex of said character.

11. The method of claim 5 wherein said fine-tuning comprises:

for each pixel along the contour joining the determined pixels of the first pair in a first direction;

calculating the distance between the pixel and the line joining the determined pixels of the first pair;

calculating the distance between the pixel and the furthest determined pixel of the second pair; and

summing calculated distances to yield a first resultant sum;

determining the pixel yielding the greatest first resultant sum thereby to select a new vertex of said character;

for each pixel along the contour joining the determined pixels of the first pair in a second opposite direction;

calculating the distance between the pixel and the line joining the determined pixels of the first pair;

calculating the distance between the pixel and the furthest determined pixel of the second pair; and

summing calculated distances to yield a second resultant sum;

determining the pixel yielding the greatest second resultant sum thereby to select a new vertex of said character.

12. The method of claim 1 wherein said character is generally rectangular in shape.

13. The method of claim 12 wherein said character forms part of a designated pattern in said two-dimensional barcode symbol.

14. The method of claim 13 wherein said designated pattern is one of a start and stop pattern forming part of a PDF417 barcode symbol.

15. The method of claim 14 wherein said character is a thick bar in said pattern.

16. The method of claim 15 wherein during said examining, pixels believed to be vertices of said character are determined in pairs.

17. The method of claim 16 wherein during said examining, a first pair of determined pixels representing one set of vertices of said character is initially determined and thereafter, a second pair of determined pixels believed to represent another set of vertices of said character is estimated.

18. The method of claim 17 wherein during selecting, the determined pixels of said second pair are replaced.

19. The method of claim 18 further comprising, after said comparing has determined that the relative positions of the determined pixels satisfy the threshold, performing fine-tuning to select new pixels along said contour to replace determined pixels of the second pair that are near to but are not vertices of the character.

20. The method of claim 19 wherein said examining comprises:

comparing the distance between each pair of pixels along the contour to locate the pair of pixels having the greatest distance therebetween thereby to locate said first pair of determined pixels; and

determining the two pixels along said contour on opoposite sides of the line joining the determined pixels of said first pair that are furthest from said line thereby to locate said second pair of determined pixels.

21. The method of claim 20 wherein comparing the relative positions of determined pixels comprises:

determining the perpendicular distance between each determined pixel of said second pair to said line; and

comparing the determined distances to determine if they vary beyond said threshold.

22. The method of claim 21 wherein the determined distances are determined to vary beyond said threshold if the determined distances vary by a factor of two or more.

23. The method of claim 22 wherein when the determined distances vary beyond said threshold, said selecting comprises:

determining the pixel along the contour that is furthest from a line joining one of the determined pixels of said first pair and the determined pixel of said second pair that is furthest from the line joining the determined pixels of said first pair; and

determining the pixel along the contour that is furthest from a line joining the other of the determined pixels of said first pair and the determined pixel of said second pair that is furthest from the line joining the determined pixels of said first pair.

24. The method of claim 23 wherein said fine-tuning comprises:

for each pixel along the contour joining the determined pixels of the first pair in a first direction;

calculating the distance between the pixel and the line joining the determined pixels of the first pair;

calculating the distance between the pixel and the furthest determined pixel of the second pair; and

summing calculated distances to yield a first resultant sum;

determining the pixel yielding the greatest first resultant sum thereby to select a new vertex of said character;

for each pixel along the contour joining the determined pixels of the first pair in a second opposite direction;

calculating the distance between the pixel and the line joining the determined pixels of the first pair;

calculating the distance between the pixel and the furthest determined pixel of the second pair; and

summing calculated distances to yield a second resultant sum;

determining the pixel yielding the greatest second resultant sum thereby to select a new vertex of said character.

25. The method of claim 19 wherein said fine-tuning comprises:

for each pixel along the contour joining the determined pixels of the first pair in a first direction;

calculating the distance between the pixel and the line joining the determined pixels of the first pair;

calculating the distance between the pixel and the furthest determined pixel of the second pair; and

summing calculated distances to yield a first resultant sum;

determining the pixel yielding the greatest first resultant sum thereby to select a new vertex of said character;

for each pixel along the contour joining the determined pixels of the first pair in a second opposite direction;

calculating the distance between the pixel and the line joining the determined pixels of the first pair;

calculating the distance between the pixel and the furthest determined pixel of the second pair; and

summing calculated distances to yield a second resultant sum;

determining the pixel yielding the greatest second resultant sum thereby to select a new vertex of said character.

26. An apparatus for determining the vertices of a character in a two-dimensional barcode symbol image comprising:

a contour tracer for tracing a contour around the character;

a vertices determiner examining the contour and determining pixels along the contour believed to be vertices of the character; and

a vertices corrector comparing the relative positions of the determined pixels to determine if they satisfy a threshold, if the relative positions of the determined pixels satisfy the threshold, said vertices corrector designating the determined pixels as the vertices of the character and if the relative positions of the determined pixels do not satisfy the threshold, the vertices corrector selecting new pixels along the contour using geometric relationships between the determined pixels to replace determined pixels that are not vertices of the character thereby to correct the vertices.

27. An apparatus according to claim 26 wherein if the relative positions of the determined pixels satisfy the threshold, the vertices corrector performs fine-tuning to select new pixels along the contour to replace determined pixels that are near to but are not vertices of the character.

28. An apparatus according to claim 27 wherein said character is generally rectangular and forms part of a PDF417 barcode symbol image.

29. An apparatus according to claim 28 wherein said character is the thick bar in a start or stop pattern.

30. A method of determining the vertices of a generally rectangular character in a two-dimensional barcode symbol comprising:

examining said character to determine a first pair of vertices of said character;

using the determined pair of vertices to estimate a second pair of vertices of said character;

comparing the relative positions of the determined and estimated vertices to determine if the estimated vertices are accurate; and

if the estimated vertices are inaccurate, re-estimating the second pair of vertices using geometric relationships between the determined and estimated vertices.

31. The method of claim 30 wherein the first pair of vertices are determined by detecting the two points along the perimeter of the character that have the greatest distance therebetween.

32. The method of claim 31 wherein the second pair of vertices are estimated by detecting the two points that are on opposite sides of and furthest from a line joining the vertices of said first pair.

33. The method of claim 32 wherein if the estimated vertices are accurate, the positions of the estimated vertices are verified and re-adjusted, if necessary.

34. The method of claim 33 wherein the estimated vertices are deemed to be accurate if the distances between the two points and the line are within a threshold.

35. A method of decoding a two-dimensional barcode symbol in a captured image comprising:

locating start and stop patterns forming part of the barcode symbol;

tracing a contour around at least a portion of each of the located start and stop patterns;

determining the vertices of the traced contours, said determining comprising;

examining each traced contour to determine a first pair of vertices;

using the determined pair of vertices to estimate a second pair of vertices;

comparing the relative positions of the determined and estimated vertices to determine if the estimated vertices are accurate; and

if the estimated vertices are inaccurate, re-estimating the second pair of vertices using geometric relationships between the determined and estimated vertices;

using the determined vertices to re-orient the barcode symbol; and

reading the re-oriented barcode symbol to extract the data therein.

36. The method of claim 35 wherein the contours are traced around a designated character of the located start and stop patterns.

37. The method of claim 36 wherein the determined vertices that positioned at the ends of the barcode symbol are used to re-orient the barcode symbol.

38. The method of claim 37 further comprising conditioning the image prior to locating the start and stop patterns.

39. The method of claim 38 wherein said conditioning includes at least one of image sharpening, image thresholding and noise removing.

40. The method of claim 39 wherein said conditioning includes each of image sharpening, image thresholding and noise removing.