Detection of the presence and location of a barcode within a document is generally the first step in the well known task of reading barcodes. Commonly assigned U.S. Pat. No. 4,948,955 to Lee et al., entitled “Barcode Location Determination,” describes detecting a barcode of a known size and orientation by producing a reduced resolution map of candidate regions in the document via connected component analysis and testing each candidate region by computing moment-based features such as centroid location, area, major axis length and minor axis length. The problems with this approach are the inability to detect barcodes of unknown sizes and orientations and the complexity of the image processing operations performed, e.g., connected component analysis, requiring extensive computational resources. Commonly assigned U.S. Pat. No. 4,988,852 to Krishnan, entitled “Bar Code Reader,” produces candidate barcode regions within the document by detecting areas of one-dimensional black to white transitions appropriate for barcodes. The boundaries of the candidate regions are subsequently refined using morphological operations. The problem with this approach is the inability to detect two-dimensional barcode types that do not exhibit the long solid bars and spaces typical of one-dimensional barcode types. Commonly assigned U.S. Pat. No. 5,304,787 to Wang, entitled “Locating 2-D Bar Codes,” is representative of the approach of searching the document for the presence of specific start and stop codes associated with a particular barcode type. The problems with this approach are that only the barcode types associated with the given start and stop codes can be determined and that the search for start and stop codes is very sensitive to the scale (size) of the barcode, requirement multiple searches of the document using a variety of scale factors. These multiple passes significantly increases the execution time of the barcode detection process. Commonly assigned U.S. Pat. No. 5,974,200 to Zhou et al., entitled “Method of Locating a Machine Readable Two Dimensional Barcode within an Image,” produces candidate barcode regions within the document by detecting areas of two-dimensional black to white checkerboard-like patterns appropriate for barcodes. The problem with this approach is the inability to detect barcode types that do not contain such checkerboard features.
USPTO Backgrounds
USPTO Backgrounds