Binary image processing for decoding self-clocking glyph shape codes

• US 5,168,147 A
• Filed: 07/31/1990
• Issued: 12/01/1992
• Est. Priority Date: 07/31/1990
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Bloomberg, Dan S.
• Primary Examiner(s): LaRoche, Eugene R.
• Assistant Examiner(s): KESSELL, MICHAEL
• Application Number:
  US07/560,659
• Time in Patent Office: 854 Days
• Field of Search: 235/494, 235/454, 235/456, 364/18, 364/19, 364/728.01, 382/8, 382/9, 382/13, 382/23, 382/34
• US Class Current: 235/456
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 7/0166 by means of clock-signals derived from the code marks, e.g. self-clocking code
• CPC Class Codes: G06K 7/143 Glyph-codes
• CPC Class Codes: G06V 30/224 of printed characters having additional code marks or containing code marks

Abstract

Binary image processing techniques are provided for decoding bitmap image space representations of self-clocking glyph shape codes of various types (e.g., codes presented as original or degraded images, with one or a plurality of bits encoded in each glyph, while preserving the discriminability of glyphs that encode different bit values) and for tracking the number and locations of the ambiquities (sometimes referred to herein as "errors") that are encountered during the decoding of such codes. A substantial portion of the image processing that is performed in the illustrated embodiment of this invention is carried out through the use of morphological filtering operations because of the parallelism that is offered by such operations. Moreover, the error detection that is performed in accordance with this invention may be linked to or compared against the error statistics from one or more alternative decoding process, such as the convolution filtering process that is disclosed herein, to increase the reliability of the decoding that is obtained.

Claims

1. A process for decoding a bitmap image space representation of a self-clocking glyph shape code composed of glyphs having shapes that encode digital data values, such that every distinct data value that is encoded by said code is represented by the shape of a respective glyph;

said glyphs being selected from a set of n permissible glyph shapes, with each of said glyph shapes being preassigned to the encoding of a predetermined digital data value;

said glyphs being spatially distributed in said bitmap image space in substantial accordance with a spatial formatting rule;

said process comprising the steps of

locating at least three non-colinear reference points in said bitmap image space, said reference points having a predetermined nominal spatial relationship to each other;

determining the spatial relationship of said reference points in said bitmap image space;

calculating a skew correction factor from the spatial relationship of said reference points in said bitmap image space;

determining an X scale correction factor and a Y scale correction factor for said bitmap image space representation of said glyph code;

calibrating said spatial formatting rule in accordance with said skew and scale correction factors;

identifying an approximate center position of a first of said glyphs in said bitmap image space;

filtering said bit map image space representation of said glyph code in accordance with a finite number of shape matching discrimination filters for each of said n permissible images, thereby providing at least n filtered representations of said glyph code;

spatially sampling all of said filtered representations of said glyph code in substantial accordance with said calibrated spatial formatting rule to obtain relative filter correlated match strength values for each glyph of said glyph code as filtered by each of said filters, said sampling starting at the approximate center position of a predetermined one of said glyphs and continuing from there, approximate glyph center position-to-approximate glyph center position, in substantial accordance with said calibrated spatial formatting rule

comparing the filter correlated match strength values of each of said glyphs, glyph-by-glyph for all of said filters, to classify said glyphs by their shapes; and

assigning decoded data values to said shape classified glyphs in accordance with the data values preassigned to said glyph shapes.

2. The decoding process of claim 1 further including the step of positionally re-referencing said calibrated spatial formatting rule at each of said approximate glyph center positions to that respective approximate glyph center position.

3. The decoding process of claim 1 wherein said X scale and Y scale correction factors also are calculated from the spatial relationship of said reference points in said bitmap image space.

4. The decoding process of any of claims 1-3 wherein said filtering step is performed by morphologically ERODING said bitmap image space representation of said glyph code in accordance with at least n different hit-miss filters that are matched to respective ones of said glyph shapes, where n is a counting number.

5. The decoding process of claim 4 wherein said reference points are approximate centers of glyphs residing at corners of said bitmap image space representation of said glyph code.

6. The decoding process of any of claims 1-3 further including the steps of

morphologically OPENING said bitmap image space representation of said glyph code with a plurality of hit-miss filters, each of which is weakly matched to a respective one of said glyph shapes, thereby providing respective OPENED versions of said bitmap image space representation of said glyph code;

Bit-ORing the OPENED versions of said bitmap image space representation of said glyph code to shrink said glyphs; and

identifying a single pixel proximate the center of each of said glyphs to establish the approximate center position thereof.

7. The decoding process of claim 6 wherein said reference points are approximate centers of glyphs residing at corners of said bitmap image space representation of said glyph code.

8. The decoding process of any of claims 1-3 wherein said bitmap image space representation of said glyph code has substantial spatial periodicity vertically and horizontally, said process further including the steps of

morphologically OPENING said bitmap image space representation of said glyph code with verically oriented and horizontally oriented hit-miss filters which are matched to the vertical and horizontal spatial periodicity, respectively, of said bitmap image space representation of said glyph codes, thereby providing respective OPENED versions of said bitmap image space representation of said glyph code;

Bit-ANDing the OPENED versions of said bitmap image space representation of said glyph code to shrink said glyphs; and

identifying a single pixel proximate the center of each of said glyphs to establish the approximate center position thereof.

9. The decoding process of claim 8 wherein said reference points are approximate centers of glyphs residing at corners of said bitmap image space representation of said glyph code.