Barcode Decoding in a Camera-Based Scanner: Analysis and Algorithms

University of Minnesota Ph.D. dissertation. June 2015. Major: Mathematics. Advisor: Fadil Santosa. 1 computer file (PDF); 72 pages.In this thesis we present the first rigorous study of resolution requirements in camera- based barcode scanners. The question we wish to address is "What is the resolution needed in the captured image to unambiguously decode a barcode?"� For simplicity, we consider the UPC barcode, which is widely used in retail and commerce. A UPC barcode consists of black and white bars of different widths. The widths of these bars encode a 12-digit number according to a look-up table. We show that the camera model can be completely determined by a set of parameters defining the width of the bars and the shift in the image. These parameters can be determined by utilizing features of the UPC symbology, and the knowledge of these parameters allows us to decode exactly. We show that these two parameters can be recovered from the image data for narrowest bars larger than three-fourths a pixel and in some cases, only half a pixel. We examine two extreme cases and show that unique determination of the digit is possible in these "worst case scenarios,"� even under the presence of noise. Following this rigorous investigation, we illustrate the procedure from start to finish with a numerical example and also examine the performance of the algorithm under noise