Method and apparatus for determining the fine angular orientation of bar code symbols in two-dimensional CCD images

• US 5,487,115 A
• Filed: 08/17/1993
• Issued: 01/23/1996
• Est. Priority Date: 05/14/1992
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Incorporated
• Inventors: Surka, Stefan
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US08/108,086
• Time in Patent Office: 889 Days
• Field of Search: 382/46, 382/44, 382/22, 382/21, 395/105, 395/117, 358/448, 358/462, 364/518, 345/126, 235/462, 235/467
• US Class Current: 382/296
• CPC Class Codes: G06K 7/1443 locating of the code in an image
• CPC Class Codes: G06K 7/1452 detecting bar code edges
• CPC Class Codes: G06K 7/1456 determining the orientation of the optical code with respect to the reader and correcting therefore
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/25 Determination of region of interest [ROI] or a volume of interest [VOI]
• CPC Class Codes: G06V 30/1478 of characters or characters lines

Abstract

A system for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image. A window is selected from the two-dimensional image for processing. Edge magnitude information and edge direction information are determined for a plurality of pixels in the selected window. For each pixel in the plurality of pixels, the edge magnitude and the edge direction of each pixel is associated with at least one of a plurality of directional ranges if the edge magnitude associated with the pixel exceeds a threshold. For each directional range in the plurality of directional ranges, a density value associated with each directional range is determined in accordance with the number of pixels associated with the directional range, an angular mean value is determined in accordance with the edge directions associated with the directional range, and a noise value is determined in accordance with the edge directions associated with the directional range. At least one candidate directional range is selected in accordance with the associated density values. The fine angular orientation of a bar code symbol is determined in accordance with the edge directions associated with the candidate directional range.

Claims

1. A method for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising the steps of:

(A) selecting a window from said two-dimensional image for processing;

(B) determining an edge magnitude and an edge direction for a plurality of pixels in said selected window;

(C) selecting a pixel from said plurality of pixels;

(D) if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold, then associating said edge magnitude and said edge direction of said selected pixel with at least one of a plurality of directional ranges;

(E) repeating steps (C)-(D) for each pixel in said plurality of pixels;

(F) selecting one directional range from said plurality of directional ranges;

(G) determining a density value associated with said selected directional range in accordance with the number of pixels associated with said selected directional range;

(H) repeating steps (F)-(G) for each of said plurality of directional ranges;

(I) selecting at least one candidate directional range in accordance with said associated density values; and

(J) determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.

2. The method of claim 1, wherein step (G) further comprises the step of determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and wherein said at least one candidate directional range is selected in step (I) in accordance with said associated deviation and density values.

3. The method of claim 2, wherein said deviation value in step (G) is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.

4. The method of claim 3, wherein step (G) further comprises the step of determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and step (I) comprises selecting at least one candidate directional range in accordance with said associated deviation, density and angular mean values.

5. The method of claim 4, wherein said angular mean in step (G) is determined in accordance with the mean of said edge directions associated with said selected directional range.

6. The method of claim 4, wherein step (I) comprises the steps of:

i. selecting one directional range from said plurality of directional ranges;

ii. determining said selected directional range to be a candidate directional range if said density value associated with said selected directional range exceeds a second predetermined threshold, said deviation value associated with said selected directional range is less than a third predetermined threshold, and said angular mean value associated with said selected directional range differs from the angular center of said selected directional range by less than a fourth predetermined threshold;

iii. repeating steps i.-ii. for each of said plurality of directional ranges; and

step (J) comprises the steps of;

i. if a plurality of candidate directional ranges were selected in step (I)ii., then selecting from said plurality of candidate directional ranges the directional range associated with the smallest deviation value and determining said fine angular orientation to be the angular mean value associated with said selected candidate directional range;

ii. if a single candidate directional range was selected in step (I)ii., then determining said fine angular orientation to be the angular mean value associated with said single candidate directional range.

7. The method of claim 6, wherein step (A) comprises the steps of:

i. selecting an object region from said two-dimensional pixel image;

ii. determining the spatial coordinates of the center of mass associated with said selected object region;

iii. selecting a window of pixels centered about said spatial coordinates.

8. The method of claim 7, wherein if no candidate directional range was selected in step (I)ii., then sequentially translating said window about said spatial coordinates and repeating steps (B)-(I) until at least one candidate directional range is selected in step (I)ii.

9. A method for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising the steps of:

(A) selecting a window from said two-dimensional image for processing;

(B) determining an edge magnitude and an edge direction for a plurality of pixels in said selected window;

(C) selecting a pixel from said plurality of pixels;

(D) if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold, then associating said edge magnitude and said edge direction of said selected pixel with at least one of a plurality of directional ranges;

(E) repeating steps (C)-(D) for each pixel in said plurality of pixels;

(F) selecting one directional range from said plurality of directional ranges;

(G) determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range;

(H) repeating steps (F)-(G) for each of said plurality of directional ranges;

(I) selecting at least one candidate directional range in accordance with said associated deviation values; and

(J) determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.

10. The method of claim 9, wherein said deviation value in step (G) is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.

11. The method of claim 9, wherein step (G) further comprises the step of determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and step (I) comprises selecting at least one candidate directional range in accordance with said associated deviation and angular mean values.

12. The method of claim 11, wherein said angular mean in step (G) is determined in accordance with the mean of said edge directions associated with said selected directional range.

13. The method of claim 9, wherein step (A) comprises the steps of:

i. selecting an object region from said two-dimensional pixel image;

ii. determining the spatial coordinates of the center of mass associated with said selected object region;

iii. selecting a window of pixels centered about said spatial coordinates.

14. A method for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising the steps of:

(A) selecting a window from said two-dimensional image for processing;

(B) determining an edge magnitude and an edge direction for a plurality of pixels in said selected window;

(C) selecting a pixel from said plurality of pixels;

(D) if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold, then associating said edge magnitude and said edge direction of said selected pixel with at least one of a plurality of directional ranges;

(E) repeating steps (C)-(D) for each pixel in said plurality of pixels;

(F) selecting one directional range from said plurality of directional ranges;

(G) determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range;

(H) repeating steps (F)-(G) for each of said plurality of directional ranges;

(I) selecting at least one candidate directional range in accordance with said associated angular mean values; and

(J) determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.

15. The method of claim 14, wherein step (G) further comprises the step of determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and wherein said at least one candidate directional range is selected in step (I) in accordance with said associated deviation and angular mean values.

16. The method of claim 15, wherein said deviation value in step (G) is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.

17. The method of claim 14, wherein step (A) comprises the steps of:

i. selecting an object region from said two-dimensional pixel image;

ii. determining the spatial coordinates of the center of mass associated with said selected object region;

iii. selecting a window of pixels centered about said spatial coordinates.

18. An apparatus for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising:

(A) a window selector for selecting a window from said two-dimensional image for processing;

(B) means for determining an edge magnitude and an edge direction for each of a plurality of pixels in said selected window;

(C) a classifier for associating said edge magnitude and said edge direction of a selected pixel with at least one of a plurality of directional ranges if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold;

(D) means for applying said classifier to each of said plurality of pixels;

(E) a calculator for determining a density value associated with a selected directional range in accordance with the number of pixels associated with said selected directional range;

(F) means for applying said calculator to each of said plurality of directional ranges;

(G) a candidate directional range selector for selecting at least one candidate directional range in accordance with said associated density values; and

(H) means for determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.

19. The apparatus of claim 18, wherein said calculator further comprises means for determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and wherein said candidate directional range selector comprises means for selecting said at least one candidate directional range in accordance with said associated deviation and density values.

20. The apparatus of claim 19, wherein said deviation value is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.

21. The apparatus of claim 19, wherein said calculator further comprises means for determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and said candidate directional range selector comprises means for selecting at least one candidate directional range in accordance with said associated deviation, density and angular mean values.

22. The apparatus of claim 21, wherein said angular mean is determined in accordance with the mean of said edge directions associated with said selected directional range.

23. The apparatus of claim 21, wherein said candidate directional ranges selector comprises:

i. means for selecting one directional range from said plurality of directional ranges;

ii. means for determining said selected directional range to be a candidate directional range if said density value associated with said selected directional range exceeds a second predetermined threshold, said deviation value associated with said selected directional range is less than a third predetermined threshold, and said angular mean value associated with said selected directional range differs from the angular center of said selected directional range by less than a fourth predetermined threshold.

24. The apparatus of claim 18, wherein said window selector comprises:

i. an object region selector for selecting an object region from said two-dimensional pixel image;

ii. means for determining the spatial coordinates of the center of mass associated with said selected object region;

iii. means for selecting a window of pixels centered about said spatial coordinates.

25. The apparatus of claim 24, further comprising means for sequentially translating said window about said spatial coordinates until at least one candidate directional range is selected.

26. An apparatus for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising:

(A) a window selector for selecting a window from said two-dimensional image for processing;

(B) means for determining an edge magnitude and an edge direction for each of a plurality of pixels in said selected window;

(C) a classifier for associating said edge magnitude and said edge direction of a selected pixel with at least one of a plurality of directional ranges if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold;

(D) means for applying said classifier to each of said plurality of pixels;

(E) a calculator for determining a deviation value associated with a selected directional range in accordance with said edge directions associated with said selected directional range;

(F) means for applying said calculator to each of said plurality of directional ranges;

(H) a candidate directional range selector for selecting at least one candidate directional range in accordance with said associated deviation values; and

(I) means for determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.

27. The apparatus of claim 26, wherein said deviation value is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.

28. The apparatus of claim 26, wherein said calculator further comprises means for determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and said candidate directional range selector comprises means for selecting at least one candidate directional range in accordance with said associated deviation and angular mean values.

29. The apparatus of claim 28, wherein said angular mean is determined in accordance with the mean of said edge directions associated with said selected directional range.

30. The apparatus of claim 26, wherein said window selector comprises:

i. an object region selector for selecting an object region from said two-dimensional pixel image;

ii. means for determining the spatial coordinates of the center of mass associated with said selected object region;

iii. means for selecting a window of pixels centered about said spatial coordinates.

31. An apparatus for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising:

(A) a window selector for selecting a window from said two-dimensional image for processing;

(B) means for determining an edge magnitude and an edge direction for each of a plurality of pixels in said selected window;

(C) a classifier for associating said edge magnitude and said edge direction of a selected pixel with at least one of a plurality of directional ranges if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold;

(D) means for applying said classifier to each of said plurality of pixels;

(E) a calculator for determining an angular mean value associated with a selected directional range in accordance with said edge directions associated with said selected directional range;

(F) means for applying said calculator to each of said plurality of directional ranges;

(G) a candidate directional range selector for selecting at least one candidate directional range in accordance with said associated angular mean values; and

(H) means for determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.

32. The apparatus of claim 31, wherein said calculator further comprises means for determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and wherein said candidate directional range selector comprises means for selecting said at least one candidate directional range in accordance with said associated deviation and angular mean values.

33. The apparatus of claim 32, wherein said deviation value is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.

34. The apparatus of claim 31 wherein said window selector comprises:

i. an object region selector for selecting an object region from said two-dimensional pixel image;

ii. means for determining the spatial coordinates of the center of mass associated with said selected object region;

iii. means for selecting a window of pixels centered about said spatial coordinates.