BarcodeLocalizer

Algorithm for linear barcodes

The concept is that barcode regions have a high density of gradients that are all in the same direction whereas regions containing text or other pictures will have gradients in different directions. Looking for gradients in the same direction allows for the fact that, regardless of whether the barcode is horizontal or not, all of its gradients will be in the same direction relative to each other.

Steps

• First, preprocess the image by scaling it down if it is large - this improves processing speed. Then convert to grayscale and apply morphological black hat to improve contrast



Find candidates with the following steps

• Calculate first-order Scharr x and y derivatives on the preprocessed image and use that to calculate magnitude and angle of gradients at each point


• Convert the gradient directions so that opposite directions show up as the same i.e. 20 deg. and 200 deg. are the same gradient direction


• Calculate the variance of gradient directions in a window around each pixel. We do this by setting the gradient direction to 0 at all points with no gradient(so that the calculations are not affected by noise at points where there is no gradient). Then calculate integral images to get sum and sum of squares of the gradient directions and use this to calculate the variance around each point.


• Normalize the variances above and then convert it into a binary image based on an experimentally determined threshold for minimum variance


• At the end of the previous step, the image marks pixels according to the variance of gradiance directions near them. We now connect large components in this image by applying a morphological close followed by a morphological open. Though we are searching for rectangular shapes, elliptical structuring elements appear to do a better job of connecting components.


• Next we use openCV's contour-finding to draw contours around connected components. We eliminate those that are too small relative to image size or are not rectangular as being unlikely barcode candidates.


• The final step is to normalize the result by looking at the gradient angles within the candidate region and rotating/de-skewing it to be closer to horizontal. The steps above also have a tendency to skip the edges of the barcode so we go through the area around the captured region pixel-by-pixel to expand it and capture the quiet zone and border region around the barcode.


• The above steps can result in 0, 1 or more than one candidate region per image. These are returned as a list of java BufferedImage classes. Any program that uses this library can then pass those images to a barcode decoder to decode the images to see if they contain readable barcodes.



Algorithm for Matrix barcodes

The concept here is that regions with matrix barcodes have a high density of gradients perpendicular with each other. This does not work for MaxiCodes that use spirals but works well for QR codes, Data Matrix, PDF417 and other formats that use perpendicular lines in their coding.

The algorithm is largely the same as for linear codes except for the steps involving calculating variances.

Instead of variances, we calculate histograms of gradient direction in a window around the pixels and find pixels which primarily have gradients around them that are perpendicular to each other.[4]

This is less computationally intensive than it might appear because we only need to calculate histograms for approximately every 10th pixel and this is *after* large images have been scaled down to a standard size. This histogram is then dilated and we continue as in the algorithm for linear barcodes by thresholding, contour-finding and normalizing any results.

References

[1] X. Qi, James Juett, “Barcode localization using bottom-hat filter,” NSF Research Experience for Undergraduates, 2005.

[2] L. Fang, C. Xie, "1-D barcode localization in complex background," in Int. Conf. on Computational Intelligence and Software Engineering (CiSE). Dec. 2010, pp. 1-3.

[3] M. Katona and L. G. Nyúl, "A novel method for accurate and efficient barcode detection with morphological operations," in The 8th International Conference on Signal Image Technology (SITIS 2012)

[4] Szentandrási István, Herout Adam and Dubská Markéta. Fast Detection and Recognition of QR codes in High-Resolution Images. In: Proceedings of 28th Spring conference on Computer Graphics. Bratislava: Comenius University in Bratislava, 2012, pp. 1-8.