Barcode recognition using data-driven classifier

• US 8,523,075 B2
• Filed: 09/30/2010
• Issued: 09/03/2013
• Est. Priority Date: 09/30/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: van der Merwe, Rudolph
• Primary Examiner(s): MARSHALL, CHRISTLE I
• Application Number:
  US12/895,751
• Publication Number:
  US 20120080515A1
• Time in Patent Office: 1,069 Days
• Field of Search: 23546201-46249
• US Class Current: 235/462.25
• CPC Class Codes: G06K 7/1447 extracting optical codes from image or text carrying said optical code

Abstract

A barcode decoding system and method are disclosed that use a data-driven classifier for transforming a potentially degraded barcode signal into a digit sequence. The disclosed implementations are robust to signal degradation through incorporation of a noise model into the classifier construction phase. The run-time computational cost is low, allowing for efficient implementations on portable devices.

Claims

1. A method of recognizing a barcode, comprising:

converting a barcode image into an electronic representation;

extracting symbol feature vectors from the electronic representation to form a symbol feature vector sequence; and

mapping the symbol feature vector sequence into a digit sequence, the mapping including using a classifier trained in a supervised manner from a dataset of simulated noisy symbol feature vectors with a known target class.

2. The method of claim 1, further comprising:

generating a one dimensional intensity profile image from a vertical integration of pixel values in a band cutting through the barcode image.

3. The method of claim 2, further comprising:

prior to generating the intensity profile, converting the pixel values from a first color space to a second color space using a color space mapping.

4. The method of claim 2, extracting symbol feature vectors from the electronic representation, further comprises:

cropping left and right edges of the intensity profile;

identifying positions and values of extrema of the intensity profile;

filtering extrema to remove extraneous detections;

calculating locations of edges of the intensity profile using filtered extrema;

performing edge consistency checking; and

sequentially converting consecutive local edge location measurements into a linear sequence of N symbol feature vectors.

5. The method of claim 4, where cropping left and right edges of the intensity profile further comprises:

detecting barcode endpoints using a differential spatial signal variance ratio (DSSVR) metric.

6. The method of claim 4, where identifying positions and values of extrema of the intensity profile further comprises:

applying a linear search over a sliding window to the cropped intensity profile to find local extrema;

or

applying slope filtering to the cropped intensity profile to determine when a slope of the intensity profile undergoes a polarity change.

7. The method of claim 4, where identifying positions and values of extrema of the intensity profile further comprises:

applying a linear de-trending operation to the cropped intensity profile; and

applying signal amplitude normalization to the cropped and d-trended intensity profile.

8. The method of claim 6, where filtering extrema to remove extraneous detections further comprises:

detecting and removing invalid extrema; and

coalescing multiples of local extrema.

9. The method of claim 8, where detecting invalid extrema further comprises:

applying an adaptive threshold based comparator or an alpha-trimmed outlier detector to the cropped intensity profile.

10. The method of claim 9, calculating locations of edges of intensity profile using filtered extrema further comprises:

calculating edge locations using a linear interpolation of pixel x-coordinates of two intensity profile samples that straddle a mid-value between consecutive maxima and minima extrema.

11. The method of claim 10, calculating locations of edges of intensity profile using filtered extrema further comprises:

calculating edge locations using a linear interpolation of pixel x-coordinates of two intensity profile samples that straddle a mid-value between consecutive maxima and minima extrema.

12. The method of claim 4, where performing edge consistency checking further comprises:

comparing a number of negative and positive edges of the intensity profile with an expected number of negative and positive edges for a given barcode type; and

determining if the edges form a correctly interleaved set.

13. The method of claim 4, where sequentially converting consecutive local edge location measurements into a linear sequence of N symbol feature vectors further comprises:

converting the consecutive local edge location measurements into parameters that encode distances between key fiducial landmarks in the barcode image.

14. The method of claim 1, where the simulated noisy symbol feature vectors are given by {right arrow over ({tilde over (s)}_i={right arrow over (s)}_i+{right arrow over (n)}_i where {right arrow over (s)}_i are the symbol feature vectors and {right arrow over (n)}_i is a corrupting noise-like random variable and i=0, 1, . . . , N−

1, and where N is a positive integer equal to the total number of simulated noisy symbol feature vectors.

15. The method of claim 14, where the simulated noisy symbol feature vectors are given by {right arrow over ({tilde over (s)}_i=[{tilde over (L)}_i, {tilde over (x)}_i,0, {tilde over (x)}_i,1, {tilde over (x)}_i,2, {tilde over (x)}_i,3] and i=0, 1, . . . , N−

1, {tilde over (L)}_i is a noisy symbol length measure from the leading edge of a first bar of a symbol in the barcode image to a corresponding leading edge of a first bar of a next adjacent symbol, {tilde over (x)}₀ is a noisy width of a second dark bar of the symbol, {tilde over (x)}₁ is a noisy width of a first dark bar of the symbol, {tilde over (x)}₂ is a noisy distance between trailing edges of the first and second dark bars, and {tilde over (x)}₃ is a noisy distance between leading edges of the first and second dark bars.

16. The method claim 15, where the noisy symbol feature vectors {right arrow over (s)}_i are transformed into scale invariant noisy symbol feature vectors by normalizing each component of each vector by {tilde over (L)}_i.

17. The method claim 16, where the classifier is a multi-layer neural network that uses hyperbolic tangent nonlinearities in an input layer and a hidden layer, and a one-hot encoded soft-max sigmoid output layer.

18. The method claim 17, where the multi-layer neural network has 4 input units and 20 output units, and real valued outputs of each of the 20 output units are posterior probabilities of a known class conditioned on an input symbol feature vector.

19. The method claim 17, where the classifier is trained in a supervised fashion using a regularized scaled conjugate gradient.

20. The method of claim 17, further comprising:

computing a confidence score for a complete decoding of the barcode image by averaging a maximum per-symbol output probability for the sequence of symbol feature vectors, and comparing the confidence score against a gating threshold to determine the quality of the decoding of the barcode image.

21. A system for recognizing a barcode, comprising:

one or more processors;

memory coupled to the one or more processors and storing instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising;

converting a barcode image into an electronic representation;

extracting symbol feature vectors from the electronic representation to form a symbol feature vector sequence; and

mapping the symbol feature vector sequence into a digit sequence, the mapping including using a classifier trained in a supervised manner from a dataset of simulated noisy symbol feature vectors with a known target class.

22. The system of claim 21, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

generating a one dimensional intensity profile image from a vertical integration of pixel values in a band cutting through the barcode image.

23. The system of claim 22, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

prior to generating the intensity profile, converting the pixel values from a first color space to a second color space using a color space mapping.

24. The system of claim 22, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

cropping left and right edges of the intensity profile;

identifying positions and values of extrema of the intensity profile;

filtering extrema to remove extraneous detections;

calculating locations of edges of intensity profile using filtered extrema;

performing edge consistency checking; and

sequentially converting consecutive local edge location measurements into a linear sequence of N symbol feature vectors.

25. The system of claim 24, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

detecting barcode endpoints using a differential spatial signal variance ratio (DSSVR) metric.

26. The system of claim 24, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

applying a linear search over a sliding window to the cropped intensity profile to find local extrema;

or

applying slope filtering to the cropped intensity profile to determine when a slope of the intensity profile undergoes a polarity change.

27. The system of claim 24, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

applying a linear de-trending operation to the cropped intensity profile; and

applying signal amplitude normalization to the cropped and d-trended intensity profile.

28. The system of claim 26, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

detecting and removing invalid extrema; and

coalescing multiples of local extrema.

29. The system of claim 28, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

applying an adaptive threshold based comparator or an alpha-trimmed outlier detector to the cropped intensity profile.

30. The system of claim 29, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

calculating edge locations using a linear interpolation of pixel x-coordinates of two intensity profile samples that straddle a mid-value between consecutive maxima and minima extrema.

31. The system of claim 30, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

calculating edge locations using a linear interpolation of pixel x-coordinates of two intensity profile samples that straddle a mid-value between consecutive maxima and minima extrema.

32. The system of claim 24, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

comparing a number of negative and positive edges of the intensity profile with an expected number of negative and positive edges for a given barcode type; and

determining if the edges form a correctly interleaved set.

33. The system of claim 24, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

converting the consecutive local edge location measurements into parameters that encode distances between key fiducial landmarks in the barcode image.

34. The system of claim 21, where the simulated noisy symbol feature vectors are given by {right arrow over ({tilde over (s)}_i={right arrow over (s)}_i+{right arrow over (n)}_i where {right arrow over (s)}_i are the symbol feature vectors and {right arrow over (n)}_i is a corrupting noise-like random variable and i=0, 1, . . . , N−

1, and where N is a positive integer equal to the total number of simulated noisy symbol feature vectors.

35. The system of claim 34, where the simulated noisy symbol feature vectors are given by {right arrow over ({tilde over (s)}_i=[{tilde over (L)}_i, {tilde over (x)}_i,0, {tilde over (x)}_i,1, {tilde over (x)}_i,2, {tilde over (x)}_i,3] and i=0, 1, . . . , N−

1, {tilde over (L)}_i is a noisy symbol length measure from the leading edge of a first bar of a symbol in the barcode image to a corresponding leading edge of a first bar of a next adjacent symbol, {tilde over (x)}₀ is a noisy width of a second dark bar of the symbol, {tilde over (x)}₁ is a noisy width of a first dark bar of the symbol, {tilde over (x)}₂ is a noisy distance between trailing edges of the first and second dark bars, and {tilde over (x)}₃ is a noisy distance between leading edges of the first and second dark bars.

36. The system claim 35, where the noisy symbol feature vectors are transformed into scale invariant noisy symbol feature vectors by normalizing each component of each vector by {tilde over (L)}_i.

37. The system claim 36, where the classifier is a multi-layer neural network that uses hyperbolic tangent nonlinearities in an input layer and a hidden layer, and a one-hot encoded soft-max sigmoid output layer.

38. The system claim 37, where the multi-layer neural network has 4 input units, seven hidden units and 20 output units, and real valued outputs of each of the 20 output units are posterior probabilities of a known class conditioned on an input symbol feature vector.

39. The system claim 37, where the classifier is trained in a supervised fashion using a regularized scaled conjugate gradient.

40. The system of claim 37, where the memory stores instructions, which, when executed by the one or more processors, cause the processors to perform operations comprising:

computing a confidence score for a complete decoding of the barcode image by averaging a maximum per-symbol output probability for the sequence of symbol feature vectors, and comparing the confidence score against a gating threshold to determine the quality of the decoding of the barcode image.