Self-clocking glyph code for encoding dual bit digital values robustly

A self-clocking glyph code is provided for encoding dual bit digital values in the cardinal rotations (0.degree., 90.degree., 180.degree. and 270.degree.) of a logically ordered sequence of wedge-shaped glyphs that are written, printed, or otherwise recorded on a hardcopy recording medium in accordance with a predetermined spatial formatting rule. For example, these wedge-shaped glyphs suitably are essentially identical right triangles. The widths of such glyphs vary unidirectionally as a function of their height, so they can be decoded reliably, even when they are degraded by scan errors, dropped scan lines and/or random noise patterns. The decoding can be carried out in a variety of different ways, including by means of a bounding box analysis of the glyphs to determine whether the center of mass of each glyph is in the upper right, upper left, lower right or lower left quadrant of its bounding box; or by means of a bounding box analysis of the glyphs to determine whether the inclined surface of each wedge is on its right-hand side or its left-hand side and tilted to the right or left; or by means of a comparative run length analysis of each of the glyphs to determine whether its shortest run of adjacent ON pixels is spatially located above or below, and to the right or left of center of, its longest run of adjacent ON pixels.

FIELD OF THE INVENTION 
This invention relates to self-clocking glyph codes for encoding machine 
readable digital information on hardcopy recording media and, more 
particularly, to self-clocking glyph codes for graphically encoding dual 
digital values compactly and robustly. 
BACKGROUND OF THE INVENTION 
Self-clocking glyph codes are suitable for transferring digital values of 
various types (e.g., machine control instructions, data values, memory 
pointers, and executable binaries) back and forth synchronously between 
the electronic and hardcopy domains. They, therefore, are a promising 
interface technology for integrating hardcopy documents and computer 
controlled electronic document processing systems more or less seamlessly. 
A self-clocking glyph code typically is generated by mapping logically 
ordered digital input values of predetermined bit length, n, into a 
predefined set of 2.sup.n graphically unique symbols (i.e., "glyphs"), 
each of is preassigned to the encoding of a different one of the 
permissible input values. Thus, each of the input values is transformed 
into and encoded by a corresponding glyph. These glyph encodings, in turn, 
are written on a hardcopy recording medium in accordance with a 
predetermined spatial formatting rule, thereby producing a glyph code that 
encodes the input values and preserves their logical ordering. 
As will be appreciated, a code of the foregoing type carries the clock 
signal that is required for transferring the encoded digital values from 
the hardcopy domain to the electronic domain synchronously. Every input 
value is represented by a corresponding glyph, so the clock is embedded in 
the spatial distribution of the logically ordered glyphs. This is why 
these codes are referred to as "self-clocking" glyph codes. As will be 
appreciated, the self-clocking characteristic of these codes increases 
their tolerance to the degradation (i.e., image distortion and background 
noise) they may suffer when they are reproduced by photocopying and/or 
facsimile transmission. See a copending and commonly assigned Bloomberg et 
al. U.S. patent application that was filed Jul. 31, 1990 under Ser. No. 
07/560,514 on "Self-Clocking Glyph Shape Codes" (D/89194), which hereby is 
incorporated by reference. 
Prior self-clocking glyph codes are especially well suited for encoding 
signle bit digital values ("1" or "0"). Some of these codes also are 
useful for encoding short (e.g., two bit long) multi-bit values, but the 
cost and complexity of decoding these known codes tend to increase 
exponentially as a function of the bit lengths of the digital values that 
are encoded in their glyphs. This follows from the general rule that 
2.sup.n filtering steps are required for decoding a glyph code encoding of 
n-bit long digital values when n&gt;1. Moreover, these existing glyph codes 
tend to become less robust when they are used for encoding multi-bit 
values because their per glyph encoding capacity is increased by reducing 
the graphical distinctions between their glyphs. Accordingly, there is a 
need for self-clocking glyph codes for encoding dual bit digital values 
more robustly. 
SUMMARY OF THE INVENTION 
In response to the above-defined need, this invention provides a 
self-clocking glyph code for encoding dual bit digital values in the 
cardinal rotations (0.degree., 90.degree., 180.degree. and 270.degree.) of 
a logically ordered sequence of wedge-shaped glyphs that are written, 
printed, or otherwise recorded on a hardcopy recording medium in 
accordance with a predetermined spatial formatting rule. For example, 
these wedge-shaped glyphs suitably are essentially identical right 
triangles. The widths of such glyphs vary unidirectionally as a function 
of their height, so they can be decoded reliably, even when they are 
degraded by scan errors, dropped scan lines and/or random noise patterns. 
The decoding can be carried out in a variety of different ways, including 
by means of a bounding box analysis of the glyphs to determine whether the 
center of mass of each glyph is in the upper right, upper left, lower 
right or lower left quadrant of its bounding box; or by means of a 
bounding box analysis of the glyphs to determine whether the inclined 
surface of each wedge is on its right-hand side or its left-hand side and 
tilted to the right or left; or by means of a comparative run length 
analysis of each of the glyphs to determine whether its shortest run of 
adjacent ON pixels is spatially located above or below, and to the right 
or left of center of, its longest run of adjacent ON pixels.

DETAILED DESCRIPTION OF THE ILLUSTRATED EMBODIMENT 
While the invention is described in some detail hereinbelow with specific 
reference to an illustrated embodiment, it is to be understood that there 
is no intent to limit it to that embodiment. On the contrary, the aim is 
to cover all modifications, alternatives and equivalents falling within 
the spirit and scope of the invention as defined by the appended claims. 
Turning now to the drawings, and at this point especially to FIG. 1, the 
operating environment for modern electronic document processing systems is 
becoming a hybrid environment in which human readable and machine readable 
information are transferred back and forth between an electronic domain 11 
and a hardcopy domain 12. For example, a printed form 13 containing human 
readable and machine readable digital information (see FIG. 2) may read 
into an electronic document processing system 14 through the use of a 
remote facsimile terminal 15. The document processing system 14 may or may 
not capture the human readable content of the form 13, but it generally is 
intended to capture the machine readable digital content of the form 13 
reliably. 
To that end, in accordance with this invention, the machine readable 
content of the form 13 is written in a self-clocking glyph code 21 that 
has wedge-shaped glyphs 22a-22d for encoding respective dual bit digital 
values. These dual bit values are encoded in the relative rotations of the 
glyphs 22a-22d; typically by preassigning each of the cardinal rotations 
(0.degree., 90.degree., 180.degree. and 270.degree.) of a desired wedge 
shape to the encoding of respective ones of the permissible dual bit 
digital values (see FIG. 3). For example, as isosceles right triangle that 
has its right angle essentially aligned with the vertical and horizontal 
axes of the form 13 may be employed as a canonical glyph shape, with the 
rotations that are used for encoding the different dual bit values being 
rotations of this canonical shape about one or both of its shorter sides. 
As will be appreciated, this produces a glyph set 22a-22d that is composed 
of essentially identical right triangles. 
The glyph code 21 may be degraded significantly while being reproduced in 
hardcopy form (by means not shown) and/or while being read into the 
document processing system 14 by the facsimile terminal 15. For example, 
facsimile transmission of the glyph code 21 may introduce scan errors into 
the glyphs (FIG. 4a), truncate the glyphs or otherwise drop out some of 
the scan lines that define them (FIG. 4b), and/or superimpose a random 
noise pattern on the glyphs (FIG. 4c). However, the widths of the 
wedge-shaped or right triangular glyphs 22a-22d that are used to carry out 
this invention vary unidirectionally as a function of their heights, so 
various relatively straightforward image processing techniques can be 
employed for decoding them reliably, even if they are degraded. 
More particularly, to carry out the decoding, the document processing 
system 14 can generate a bounding box for each of the glyphs that is read 
into it and then determine whether the center of mass of each glyph is in 
the upper right-hand, upper left-hand, lower right-hand or lower left-hand 
guadrant of its bounding box (see FIG. 5a). Or, the document processing 
system 14 can generate a bounding box for each of the glyphs and then 
determine, for each glyph, (a) whether its longest side (i.e., its 
hypotenuse in the case of a right triangular glyph) is on the right-hand 
or left-hand side of the glyph and (b) whether it is tilted to the left or 
right (FIG. 5b). Still another alternative for the decoding of the glyph 
code 21 (see FIG. 5c) is to have the document processing system 14 examine 
a pixel map image of the glyphs it receives to determine, for each of 
them, whether the image of the glyph has its shortest run of ON pixels 
spatially located (a) above or below its longest run of ON pixels and (b) 
to the left or right of center of that longest run (as used herein, a 
"run" is a string of adjacent pixels that are aligned in the line scanning 
direction). 
One of the advantages of using right triangular glyphs shapes is that each 
of them fills approximately one-half of a square bounding box, so there 
are substantially equal numbers of ON pixels and OFF pixels within such a 
bounding box. The glyphs 22a-22d, therefore, may be printed on the a 
recording medium in a tiled array of such bounding boxes to provide a 
self-clocking glyph code that has a substantially uniformly textured 
appearance. That same result can be achieved by encoding the dual bit 
digital input values in the cardinal rotations of a set of glyphs (not 
shown) that have essentially identical, equilateral triangular shapes. 
Moreover, a code composed of these equilateral triangular glyphs can be 
decoded, for example, by a modified form of the comparative run length 
decoding that is shown in FIG. 5c. Specifically, equilateral triangular 
glyphs can be decoded by determining whether they have a generally 
horizontal (laterally extending) or a generally vertical (longitudinal 
extending) side, and by then determining whether that side is spatially 
located either above or below (in the case of glyph having a generally 
horizontal side) the apex of the opposite angle, or (in the case of glyph 
having a generally vertical side) to the right or left of the apex of that 
angle. 
As will be appreciated, the document processing system 14 may be configured 
to carry out a variety of different functions. As illustrated, it might be 
employed as a fax server, but that merely is one example of a function 
that the document processing system 14 might be designed to perform. 
CONCLUSION 
In view of the foregoing, it will now be understood that the present 
invention provide a self-clocking glyphs code that is especially well 
suited for transferring machine readable dual bit values back and forth 
between the hardcopy domain and the electronic domain. Furthermore, it 
will be evident that various decoding techniques can be used for reading 
this glyph code, even if the code is degraded significantly.