Image analysis – Pattern recognition
Reexamination Certificate
1999-12-17
2004-03-30
Patel, Jayanti K. (Department: 2625)
Image analysis
Pattern recognition
C235S494000, C382S310000
Reexamination Certificate
active
06714677
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
This invention relates to self-clocking glyph codes for recording digital information on graphic recording media, such as plain paper. Even more specifically, this invention pertains to techniques for increasing the reliability of decoding that digital information.
II. Background of the Invention
In the most common form of glyph decoding used at present, individual slash-like glyphs are read by performing cross-correlations with two correlation kernels representing two possible states of the glyphs. These states may, for example, be indicated by +45 or −45 degrees of slash rotation. As a region of glyphs is decoded, a two-dimensional matrix is filled. Each element of this matrix corresponds to a determined orientation of a glyph. Logic values (typically “0” and “1”) correspond in a physically direct manner to the glyph image, that is to say to the array of glyphs which are scanned to produce the data. Thus, the matrix of logic values is a direct representation of the orientation information carried by the glyphs. Decoding glyphs by means of correlations is described in U.S. Pat. No. 5,128,525, entitled “Convolutional Filtering for Decoding Self-Clocking Glyph Shape Codes,” which is assigned to the assignee of the present application and is hereby expressly incorporated by reference.
In decoding each individual glyph, cross-correlations of a glyph image in a local region, where each glyph is expected to be, is undertaken with two correlation kernels. The maximum correlation with each kernel is noted. Typically, if the difference between the two maximum correlations is larger than some preset threshold value (a correlation threshold), the glyph is assumed to be present and the value assigned to the glyph is associated with the orientation of the kernel that produced the maximum correlation value.
If the difference between the two maximum correlation values over the region of interest is smaller than the correlation threshold, then an erasure value is reported. This indicates generally that it was not possible to determine the value of the glyph in the image area under consideration.
The correlation threshold thus reflects a compromise in the ability to distinguish the orientation of the glyph in the presence of background image noise or image degradation. Setting the correlation value very high would generally mean that detected glyphs are unlikely to be decoded in error. However, many glyphs will not be unambiguously decoded, but instead will be recorded as erasures. A low correlation threshold conversely will result in more glyphs being decoded, but with greater likelihood of incorrect categorization. It is expected that an optimum value of the correlation threshold may vary depending upon the nature of the glyph image, including the condition of its printing and the condition of the scanning process undertaken.
The present invention is directed toward improving the selection of a threshold so as to maximize correct categorization while minimizing the number of glyphs erroneously decoded.
SUMMARY OF THE INVENTION
Consistent with the principles of the present invention, a method of decoding a plurality of glyphs is provided comprising the steps of: capturing an image of a group of glyphs to form image data for each glyph location; assigning for each location a first value indicative of the likelihood that location contains a glyph in a first state; assigning for each location a second value indicative of the likelihood that location contains a glyph in a second state; determining the difference between the first and second values for each potential glyph location; and decoding the plurality of glyphs based at least in part upon a distribution analysis of the determined differences. More specifically, the step of assigning preferably includes performing cross-correlations for each location with first and second correlation kernels representing the first and second states of the glyphs. In this case the step of decoding preferably includes establishing a threshold value for the minimum determined difference indicative of unambiguous decoding of a glyph state.
In another aspect of the invention, the determined difference values for each location are stored in memory and compared afterwards with the threshold to decode the image data for those locations, without the necessity to rescan those locations. In another aspect of the present invention, a distribution analysis of the determined differences in the form of a histogram is used to establish an optimum threshold value.
REFERENCES:
patent: 5168147 (1992-12-01), Bloomberg
patent: 5221833 (1993-06-01), Hecht
patent: 5245165 (1993-09-01), Zhang
patent: 5449895 (1995-09-01), Hecht et al.
patent: 5449896 (1995-09-01), Hecht et al.
patent: 5453605 (1995-09-01), Hecht et al.
patent: 5521372 (1996-05-01), Hecht et al.
patent: 5572010 (1996-11-01), Petrie
patent: 5576532 (1996-11-01), Hecht
patent: 6256398 (2001-07-01), Chang
patent: 6470096 (2002-10-01), Davies et al.
patent: WO 00/73981 (2000-12-01), None
patent: WO 01/01670 (2001-01-01), None
Goldstein et al., “Using Aggregation and Dynamic Queries for Exploring Large Data Sets,” Human Factors in Computing Systems, 23-29 (1994).
Hecht, “Embeded Data Glyph Technology for Hardcopy Digital Documents,” Proceedings Reprint, 2171:341-352 (1994).
Flores L. Noah
Hecht David L.
Jared David A.
Petrie W. Glen
Stearns Richard G.
Azarian Seyed
Patel Jayanti K.
Xerox Corporation
LandOfFree
Use of correlation histograms for improved glyph decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Use of correlation histograms for improved glyph decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Use of correlation histograms for improved glyph decoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3270847