Image analysis – Image transformation or preprocessing – Measuring image properties
Reexamination Certificate
1999-09-21
2004-01-06
Couso, Yon J. (Department: 2723)
Image analysis
Image transformation or preprocessing
Measuring image properties
C382S199000, C382S306000
Reexamination Certificate
active
06674919
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to an improved method for determining the skew angle of a two-dimensional barcode printed within an image.
BACKGROUND OF THE INVENTION
As fully described in U.S. Pat. Nos. 5,625,721 and 5,703,972 to Lopresti et al. which are both entitled “Certifiable Optical Character Recognition” and in U.S. Pat. No. 5,748,807 entitled .“A Method and Means For Enhancing Optical Character Recognition of Printed Documents”, the contents of which are all explicitly incorporated by reference herein, information about the contents, layout, generation and retrieval of a document can be encoded by a computer when initially generating the document or upon subsequent computer processing thereof. The encoded document information can then be provided via a two-dimensional barcode, generated on the face of a printed version of the document. For example,
FIG. 1A
shows a two-dimensional barcode
10
printed in the lower right comer of a document
11
containing mostly text
12
, and
FIG. 1B
shows an example of a two-dimensional barcode
20
comprising a plurality of black and white bits
23
arranged in a 20 bit×20 bit array of data.
Advanced encoding and print resolution capabilities presently available can accommodate up to 30,000 bits of information in a single square inch of space. Therefore, as taught by the above-referenced patents, one can theoretically encode the entire document contents, limited only by the amount of space on the document face that one is willing to sacrifice to the two-dimensional barcode. A barcode scanner, in conjunction with or wholly separate from an optical page scanner, can scan the two-dimensional barcode and provide the information to an associated system equipped with the appropriate recognition and decoding software. The decoded information can then be used by the scanning system to create a new version of the document or to enhance the recognition, reproduction and error correction for the scanned document. To decode the two-dimensional barcode, it is not required that such barcode scanner and scanning system know the printing resolution of the two-dimensional barcode, provided that the scanning resolution of the scanner is able to establish at least a 3×3 pixel matrix for each logical bit of the two-dimensional barcode.
However, difficulties are encountered when attempting to read a two-dimensional barcode on a document which was not properly aligned when scanned, because of the resulting skew angle of the two-dimensional barcode (i.e., the angle between the page as scanned and the ideal alignment). Several methods have been proposed for correcting the skew angle of a scanned two-dimensional barcode, but each has certain drawbacks, as discussed below.
U.S. Pat. No. 5,862,270 discloses a method for deskewing a two-dimensional barcode that relies on, and therefore requires, the presence of a border on at least one side of the barcode, and which is only effective for barcodes scanned at “slight” offset angles.
In U.S. patent application Ser. No. 09/088,189 (“the '189 Application”), the contents of which are hereby incorporated by reference, two alternate methods are presented for deskewing a two-dimensional barcode. The first method presented in the '189 Application is a template matching procedure which requires that the barcode include comer bits (also called anchor bits) which are all the same color and contrast with the background color of the document. The second method disclosed in the '189 Application does not require comer bits in the two-dimensional barcode, and is a two-step process which first creates an edge image containing all edge pixels within the two-dimensional barcode (either horizontal edge pixels or vertical edge pixels) by applying edge masks, as described in detail in the '189 Application. The edge pixels represent the “edges” between data bits of a first color (e.g., black) and data bits of a second color (e.g., white). The Hough Transform is then applied to the edge image to determine the dominant straight line in the edge image. The skew of the two-dimensional barcode is the angle between this dominant straight line and a horizontal or vertical line. Although the method of the '189 Application produces reliable results, the processing required by application of the edge masks to the two-dimensional barcode was less than optimal.
In U.S. patent application Ser. No. 09/212,243 (“the '243 Application”), the contents of which are hereby incorporated by reference, a finite state recognizer is used to create the edge image, which greatly reduces the processing time over the edge mask step of the '189 Application since each pixel within the two-dimensional barcode is examined only once. In addition, the edge image is divided into a number of regions, and the Hough Transform is applied to each region, with the skew angle being selected by a voting scheme among the angles found in each region to determine the proper skew angle. This approach reduces the effect of drawn line noise across the two-dimensional barcode. The method of the '243 Application reduces the processing time over the method of the '189 Application and reduces errors caused by drawn line noise on the two-dimensional barcode. However the processing time required to perform the Hough Transform was such that only a small range of skew angles could be considered while maintaining a reasonable processing speed.
It is therefore an object of the present invention to provide an improved method of calculating the skew angle of a two-dimensional barcode printed on a printed medium.
It is an additional object of this invention to provide a method of calculating the skew angle of a two-dimensional barcode printed on a printed medium which reduces the processing time required for the edge image.
It is yet another object of this invention to provide a method of calculating the skew angle of a two-dimensional barcode printed on a printed medium which increases the range of skew angles located within a reasonable processing time.
It is yet a further object of this invention to provide a method of calculating the skew angle of a two-dimensional barcode printed on a printed medium which greatly reduces the effect of drawn line noise on the barcode.
Various other objects, advantages and features of the present invention will become readily apparent from the ensuing detailed description and the novel features will be particularly pointed out in the appended claims.
SUMMARY
The present invention is directed to a method of calculating a skew angle for a bitmap of rows and columns of data pixels, such as a two-dimensional barcode. This method first locates the horizontal or vertical edges within the bitmap and generates an edge array identifying the honzontal or vertical edges. Next, the edge lines within the edge array are identified and traced, and then, preferably, any segments of the edge lines within the edge array which are perpendicularly connected are separated. The slope for each edge line within the edge array is calculated and, in the preferred embodiment, a discrete histogram of the slopes is generated. Finally the skew angle is set as the highest value within the discrete histogram. Since the slope is calculated for a plurality of lines within the edge image derived from the bitmap, the effect of drawn line noise is greatly diminished, since its contribution to the histogram will be much less than the edge lines.
In the preferred embodiment, a finite-state recognizer is used to locate the horizontal or vertical edges and create the edge array. Also, edge lines within the edge array which are located within a first predetermined threshold of each other are merged after the edge lines have been identified and traced. In addtion, edge lines within the edge array having a length less than a second predetermined threshold are eliminated to improve processing time and to ensure accuracy of the calculated skew angle. Finally, the slope of each edge line in the edge array is calculated us
Guo Jinhong
Ma Yue
Amster Rothstein & Ebenstein LLP
Couso Yon J.
Matsushita Electric - Industrial Co., Ltd.
LandOfFree
Method for determining the skew angle of a two-dimensional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for determining the skew angle of a two-dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining the skew angle of a two-dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3231802