Barcode recognition using data-driven classifier
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.
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)} 0 is a noisy width of a second dark bar of the symbol, {tilde over (x)} 1 is a noisy width of a first dark bar of the symbol, {tilde over (x)} 2 is a noisy distance between trailing edges of the first and second dark bars, and {tilde over (x)} 3 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)} 0 is a noisy width of a second dark bar of the symbol, {tilde over (x)} 1 is a noisy width of a first dark bar of the symbol, {tilde over (x)} 2 is a noisy distance between trailing edges of the first and second dark bars, and {tilde over (x)} 3 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.