Registers – Coded record sensors – Particular sensor structure
Reexamination Certificate
2001-05-30
2004-11-09
Frech, Karl D. (Department: 2876)
Registers
Coded record sensors
Particular sensor structure
C235S462010, C235S462110, C235S462120
Reexamination Certificate
active
06814289
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to two-dimensional barcodes, and, more particularly, to a spread-spectrum barcode that allows the barcode to be read in its entirety even if a significant fraction or majority of the barcode is obscured.
BACKGROUND
The visual storage of information has been widely deployed in the form of one-dimensional barcodes. Within the past decade, two-dimensional barcodes have emerged to facilitate the dense storage of data. Both one- and two-dimensional barcodes require a registration procedure, normally called “clocking” in the barcode literature, to be able to interpret the visual information. To date, a variety of clocking methods have been patented and put to use. See, for example U.S. Pat. No. 5,091,966 to Bloomberg et al., U.S. Pat. Nos. 5,862,270 and 6,115,508 to Lopresti et al., U.S. Pat. No. 6,082,619 to Ma et al., U.S. Pat. No. 4,948,955 to Lee et al., U.S. Pat. No. 5,974,200 to Zhou et al., U.S. Pat. No. 5,521,368 to Adachi, U.S. Pat. No. 5,835,639 to Honsinger et al., and U.S. Pat. No. 4,435,835 to Sakow et al. The methods currently in use rely upon fiducial marks (including blank space), placed at discrete locations within the image, to determine the position and arrangement of the barcode. If these fiduciaries are obscured, the user data within the barcode may not be recoverable. Furthermore, the user data are encoded in discrete locations within the barcode so that when any portion of the barcode image is obscured user data may be lost. This is the case even when error-correction and data redundancy are employed.
As discussed above, numerous techniques for visually encoding user data have been devised and patented. See, for example, U.S. Pat. No. 5,128,525 to Stems et al., U.S. Pat. No. 5,940,135 to Petrovic et al., and U.S. Pat. Nos. 5,862,270 and 6,115,508 to Lopresti et al. Many of the known techniques utilize two-dimensional formats. Commonly known formats include, “Aztec Code,” “Data Matrix,” “Data Strip Code,” “MaxiCode,” “PDF 417,” “Micro-PDF 417,” and “QR Code.” Each of these conventional formats localizes data in characters or “glyphs” that are designed to facilitate machine reading. As mentioned previously, if part of the barcode is damaged or obscured, some or all of the user data may be lost. There is, therefore, a need for a method to visually encode user data so that it is not affected by damage to the barcode.
The present invention relates to a novel barcode methodology in which the user data is delocalized or distributed across the barcode image. The resulting spread-spectrum barcode may be read in its entirety even if a significant fraction or majority of the barcode is obscured. The present invention also relates to a novel barcode methodology in which the fiducial data is delocalized or distributed across the barcode image. These delocalized fiduciaries are used to register or “clock” the data, facilitating the reading of barcodes applied on curved or warped surfaces from images having significant amounts of rotation, magnification, and perspective. In the new registration methodology, the barcode reader recognizes two signature characteristics of the barcode image: a signature “texture” and a signature “pattern.” These signatures are known by the barcode reader and are present regardless of the contents of user data sets within the barcode. This registration information allows the barcode image to be corrected for imaging distortions such as zoom, rotation, tilt, curvature, and perspective.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a method of recording information on a printed medium that will allow for retrieval of the recorded data even when significant percentage of the recorded data, i.e., greater than approximately 50% and up to approximately 80% of the recording data, is obscured.
It is an additional object of the invention to provide a method of recording information on a printed medium that will allow for accurate retrieval of the recorded data even when topography of the printed recording has been altered by bending, warping, rotation, zooming, etc.
It is another object of the invention to provide a method of recording multiple data sets on a single printed medium wherein the individual data sets may be selectively retrieved.
It is a further object of the invention to provide a method of recording information on a printed medium that can be accurately registered and retrieved without the need of a border or null space.
Additional objects, advantages, and novel features of the invention will be set forth in part in the description that follows, and in part, will become apparent to those skilled in the art upon examination of the following, or may be learned by practice of the invention.
One aspect of the invention is a novel method of recording and visually retrieving user data in a format similar to a conventional two-dimensional barcode. Unlike conventional barcodes, however, user data is spread across the barcode so that the all data can be retrieved even if a significant fraction or majority, i.e., in excess of approximately 50% and up to approximately 80%, of the image is occluded or obscured.
Various methods are available for distributing user data, generally represented as an array of bits, across an image. In one method, each bit individually or in groups is redundantly permuted and repeated at a large number of locations distributed throughout an array of values that will describe the barcode image. The barcode image is then formed, e.g., by printing the image array using a monochrome, grayscale, or color look-up table to transform the values of the image array to pixel tones. The sequence of locations of the bits and the nature of the permutation at each repetition must be known by the reader to recover the user data from the barcode image.
The permutations and location sequences can be generated algorithmically and pseudo-randomly. The locations of bits within the array can be unique, i.e., no two bits are encoded at the same array location, or non-unique, i.e., bits can be superimposed. Multiple data sets can be superimposed on the same image using different location and permutation sequences. Each data set can only be recovered if the precise location and permutation sequences are known. By crafting the permutation and location sequence algorithm, the barcode can be given a signature texture that is substantially independent of the data that is encoded. Moreover, a known pattern of bits can be interspersed, pre-appended, or appended to the user data to provide a signature pattern. The utilities of these signatures will be described later. The data-modulation methodology is analogous to “frequency hopping” data transception in spread-spectrum wireless communications.
In one methodology for forming the barcode that is analogous to “direct-sequence” spread-spectrum data transception, the barcode is produced by first encoding the user data into a spatial representation, referred to herein as an “encoded user data array,” and then modulating this encoded user data array into a modulated data array image using a pseudo-random carrier called a “modulating kernel.” The modulated data array is then formatted and printed onto a printing medium as a barcode. As in conventional spread-spectrum optical encoding and serial communications, multiple data sets can be multiplexed without interference on the same data channel (barcode image) by the use of uncorrelated modulation kernels. See for example, Yamazaki et al. (2001), “Optimization of encrypted holograms in optical security systems,”
Opt. Eng
. 40(1):132-137; Refregier et al. (1995), “Optical image encryption based on input plane and Fourier plane random encoding,”
Opt. Lett
. 90:767-769; Javidi, B. (1997), “Securing information with optical technologies,”
Phys. Today
50:27-32; Yang et al. (1996), “Practical image encryption scheme by real-valued data,”
Opt. Eng
. 35:2473-2478; Javidi et al. (1996), “Experimental demonstration of the random phase encoding technique for image encryption and security
Cummings Eric B.
Even, Jr. William R.
Frech Karl D.
Kim Ahshik
Reed & Eberle LLP
Sandia Corporation
LandOfFree
Self-registering spread-spectrum barcode method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Self-registering spread-spectrum barcode method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-registering spread-spectrum barcode method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3292284