Image analysis – Image transformation or preprocessing – Image storage or retrieval
Reexamination Certificate
1998-08-31
2001-03-27
Lee, Thomas D. (Department: 2724)
Image analysis
Image transformation or preprocessing
Image storage or retrieval
C382S232000, C235S494000, C235S462100
Reexamination Certificate
active
06208771
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
This invention relates to the construction of multi-dimensional address spaces and, more particularly, to self-clocking and address carpet glyph instantiations of such address spaces and disambiguation techniques for address carpets.
B. Background of the Invention
Self-clocking glyph codes, such as Xerox DataGlyphs, are attractive for embedding machine readable digital information in images of various types, including ordinary hardcopy documents. These codes have substantial tolerance to image distortion and noise because the digital information they encode is embedded in and fully defined by explicit machine readable marks (i.e., “glyphs”). These glyphs not only encode the information that is embedded in the code, but also define the sample clock that is employed to extract that information from the code, so they are responsible for the “self-clocking” property of the code as well as the distortion and noise tolerance.
Another known advantage of self-clocking glyph codes is that they ordinarily have an unobtrusive visual appearance. This is especially so of codes which are composed of glyphs which are written on a two dimensional spatially periodic pattern of centers, such as a regular lattice-like pattern of centers, because the spatial periodicity of the glyphs causes the code to have a more or less uniformly textured appearance. For example, logically ordered single bit digital quanta typically are encoded by respective elongated slash-like glyphs which are written on a two dimensional, spatially periodic pattern of centers in accordance with a predetermined spatial formatting rule, with the individual glyphs being tilted to the left and right of vertical by approximately +45° and −45° for encoding logical “0's” and “1's”, respectively. The mutual orthogonality of the glyph encodings for the two logical states of these single bit digital quanta enhances the discriminability of the code sufficiently to enable the embedded information to be recovered, even when the code pattern is written on a sufficiently fine grain pattern of center to cause the code pattern to have a generally uniform grayscale appearance. It, however, is to be noted that it also has been shown that self-clocking glyph codes can be designed to encode multi-bit digital quanta in the glyphs.
Prior proposals have dealt with the general subject of constructing address spaces in the image domain by encoding cyclical pseudo-noise digital bit sequences (sometimes referred to as “PN sequences”) and other types of maximal length-like digital bit sequences (i.e., sequences of length, L, in which every N-bit long subsequence is unique) in two dimensional spatially periodic self-clocking glyph code patterns. One of the unifying themes of these prior proposals is that they recommend constructing two dimensional address spaces by mapping at least two bit sequences of the foregoing type into such a code pattern so that these bit sequences are encoded to propagate in predetermined directions along respective non-parallel lines of glyphs.
While it has been shown that the bit sequences need not be mapped into the code pattern in alignment with the principal axes thereof, it often is desirable to employ such mappings to reduce the computations that are required to determine the relative addresses of the glyphs in standard Cartesian coordinates (i.e., “x” and “y” parameters expressed in units of glyphs). Furthermore, it is known that the encodings of these bit sequences may completely or partially span the glyph code pattern, so it is to be understood that the addressing that is afforded by them is effective only within that portion of the glyph code pattern that projects onto both of the encodings. Moreover, the aforementioned bit sequences may be mapped into the glyphs on these non-parallel lines at unitary or fractional duty ratios, but it has been recognized that mappings preferably are spatially cyclical for applications in which it is desired to compute relative addresses for glyphs within the address space.
Every bit in a maximal bit length sequence resides at a predetermined uniquely determinable logical position within the sequence. Accordingly, an ordered index of integers is commonly employed to distinguish those bits from each other on the basis of their respective ordinal logical positions within the sequence. These positionally dependent index numbers can, of course, be employed for selectively addressing the glyphs which encode the bits of such a sequence. However, addressing information in at least one additional dimension is required to uniquely identify the spatial locations of those glyphs or any other glyphs that are included within a two dimensional glyph code pattern. These unique identifiers of the individual glyphs are referred to as “absolute addresses” because they identify the unique locations at which the individual glyphs reside within the glyph code pattern.
As is known, the spatial address (i.e., the absolute address) of almost any given glyph in an address space of the foregoing type is identifiable, at least to a first approximation, by a metric which specifies the offset distances (if any) between the nominal center of the given glyph and the non-parallel lines of glyphs that encode the respective maximal length bit sequences, where these offsets are measured parallel to the principal axes of the code pattern and are expressed in units of glyphs. In applications where the maximal length sequences are encoded by glyphs on orthogonal lines which align with the principal axes of a self-clocking glyph code pattern that is written on a regular rectangular lattice of centers, the above-described metric reduces to an x/y coordinate pair which identifies the spatial location of the given glyph with substantial precision in a standard Cartesian coordinate system. Unfortunately, however, the intersections of the lines on which these maximal bit length sequences are encoded tend to restrict the freedom of design choice if there are glyphs at any of these intersections.
It has been shown that this unwanted limitation on the explicit spatial addressing of glyphs in self-clocking glyph code patterns can be avoided if the glyphs are written on a lattice of centers of predetermined width and/or height, so that there are a known or determinable fixed number of glyphs on every line of the code pattern along at least one of those dimensions. More particularly the solution that has been proposed for this special class of code patterns is to encode a maximal length bit sequence (or a combination of interleaved, relatively prime maximal length bit sequences) in the glyphs in a raster-like pattern which is selected to cause the logically ordered bits of the sequence to spatially propagate from side-to-side along a known dimension (say, the width) of the code pattern which more gradually propagating along the other (e.g., the height) of the code pattern in, say, top-to-bottom order. This raster encoding of the maximal length bit sequence effectively “folds” the bit sequence into the code pattern module a known or computable number of glyphs (i.e., the number of glyphs that the code pattern contains along its known dimension). Accordingly, the spatial address of any given glyph within the code pattern can be computed in x/y coordinate space from the sequence index number of the bit that is encoded by the glyph by dividing the sequence index number of the bit by the known glyph count/line modules.
Unfortunately, this raster encoding style solution to the spatial addressing problem is not only limited to a constrained class of code patterns, but also tends to be computationally costly. The computational costs of this approach are elevated because the subsequence bit length, N, over which the maximal length bit sequence must be unique scales as a function of the square root of the address space that is being served. This scaling is an inherent consequence of the fact that the number of unique phases (or “bit index positions”) of a maximal lengt
Chang Kenneth H. P.
Flores L. Noah
Hecht David L.
Jared David A.
Stearns Richard G.
Chen Wenpeng
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Lee Thomas D.
Xerox PARC
LandOfFree
Methods and apparatus for robust decoding of glyph address... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for robust decoding of glyph address..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for robust decoding of glyph address... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2541200