Image analysis – Image transformation or preprocessing – Measuring image properties
Reexamination Certificate
1998-09-17
2002-12-03
Wu, Jingge (Department: 2623)
Image analysis
Image transformation or preprocessing
Measuring image properties
C382S281000
Reexamination Certificate
active
06490376
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to processing of raster scan images, and more particularly relates to processing of raster scan images of rectilinear symbols such as PDF symbols or bar code symbols.
Optical scanners are widely used for reading data included by symbols on various items. One common application of optical scanning is in reading of bar code symbols such as Universal Product Code (“UPC”) symbols. These scanners typically operate by directing a beam of light from a source such as a laser onto the object bearing the symbol and detecting the intensity of the reflected light. The scanner typically incorporate optical elements which focus the beam of light to a relatively small spot at the object bearing the symbol and can move the optical elements so as to sweep the spot of light across the object in a series of parallel lines referred to as “raster”. These scanners also include a photodetector such as a photodiode or phototransistor which receives the light reflected from the object. As the spot of light moves over the object and encounters light and dark areas on the surface of the object, the amount of light reflected to the photodetector varies and the electrical signal produced by the photodetector varies correspondingly. These variations in the electrical signal from the photodetector typically are converted into digital signals having a first value, (e.g., 0) when the spot of light is focused on a point having high reflectivity and having a second, different value (e.g., 1) when the spot is focused on a point having low reflectivity. Thus, the scanner produces a series of digital values representing the reflectivity of the object at a series of points along each of the lines in the raster. Other scanners use different physical elements to provide a similar series of values for reflectivity along raster scan lines.
This data is then converted into information which represents the data encoded by the symbol using a computer programmed to recognize certain patterns in the data as representing certain information encoded by the symbol. The pattern recognition problem is complicated by the fact that the raster used to scan the symbol may lie at an arbitrary orientation with respect to the horizontal and vertical directions of the symbol. For example, a conventional one-dimensional bar code symbol
10
(
FIG. 1
) has a horizontal direction denoted by X
s
and a vertical direction denoted by the arrow Y
s
. The symbol includes a series of vertical dark and light bars. The information carried by the symbol is encoded in the widths of these bars. For example, a dark bar
12
one unit wide followed by a light bar
14
one unit wide and a dark bar
16
three units wide may denote a numeral “3” whereas other sets of bars having different widths may denote other characters. If the symbol is scanned using a raster having scan lines
18
perfectly parallel to the horizontal direction of the symbol, the widths of the various bars will appear in the data as the lengths of series of ones and zeros representing light and dark areas. For example, bar
12
may appear as a series of 10 ones; light bar
14
may appear as a series of 10 zeros and dark bar
16
may appear as a series of 30 ones in succession. The other bars constituting the symbol will be represented in the same manner. If the horizontal or line direction of the raster is drastically misaligned with the horizontal direction of the symbol, the symbol cannot be read. For example, none of the scanning lines in raster
20
intercepts all of the bars in the symbol. However, if the horizontal direction of the raster is only slightly misaligned with the symbol, the symbol can still be read. For example, scan line
22
a
of raster
22
will intercept all of the bars in the symbol. Thus, the data representing the light and dark regions encountered along line
22
a
still includes the same series of light and dark regions which would be encountered along perfectly aligned scan line
18
. The bars will still be represented by series of ones and zeros and the lengths of these series will still be proportional to the widths of the bar. For example, bar
12
may be represented as a series of 12 ones; light space
14
may appear as a series of 12 zeros and bar
16
may appear as a series of 36 ones. Although the absolute lengths of these series differ from the lengths which would be recorded for a perfectly aligned raster, the proportions of these series relative to one another do not change. Therefore, the computer can accurately decode the symbol based on the data acquired using raster
22
. Typical scanners used for decoding one-dimensional bar codes gather data using rasters arranged at a few different dispositions as, for example, three rasters having their respective horizontal directions at 60 degree angles to one another. One of these rasters will have its horizontal direction aligned well enough with the horizontal direction of the symbol to provide meaningful data. The system discards the useless data generated by the other rasters.
There is a growing trend towards the use of two-dimensional symbols which include plural horizontal rows of light and dark regions. For example, the symbol
25
depicted in
FIG. 2
is a PDF417 symbol having a horizontal direction X
s
and a vertical direction Y
s
, and having nine horizontal rows
27
of light and dark areas. Each horizontal row of light and dark areas includes different information. Such a symbol can carry more information in a given space than a one-dimensional bar code. However, alignment of the horizontal direction of the raster with the horizontal direction of the symbol is far more critical in the case of a two-dimensional code. Thus, where the raster is perfectly aligned with the symbol, it will include at least one scanning line aligned with each horizontal row
27
of the symbol. For example, raster line
26
a
extends through the topmost row
27
a
areas in symbol
24
, but does not extend through any other row of the symbol. Similarly, line
26
b
of the same raster extends through the second row
27
b
of the symbol and so on. Line
28
a
of a misaligned raster, which is skewed with respect to the symbol, will not include the same pattern of light and dark areas as any of the perfectly aligned scan lines
26
. To provide meaningful information from a two-dimensional symbol, a raster must be have its horizontal direction aligned to within a few degrees with the horizontal direction of the symbol. To read a two-dimensional symbol presented at a random orientation using the trial-and-error approach used with one-dimensional symbols, the system would have to generate scores of rasters, and try to decipher data from all of these rasters, in order to be sure of obtaining data from one raster having its horizontal direction aligned well enough with the horizontal direction of the symbol. This typically is not practical.
As described, for example, in Shellhammer et al., U.S. Pat. No. 5,523,552, it has been proposed to scan a two-dimensional rectilinear symbol such as a PDF symbol using a plurality of rasters disposed at different known dispositions. The system calculates the skew angle between the vertical direction of each raster and the vertical direction of the symbol based upon the data found in each scan. From these skew angles, the system determines the disposition of the symbol in the frame of reference of the scanner apparatus. The system then generates a raster having its horizontal direction aligned with the horizontal directions of the symbol, and sweeps the light beam thorough such raster. This approach requires repetitive scanning of the symbol, which in turn limits the speed of operation of the system. Moreover, it requires a scanner which is physically capable of generating a real raster at an arbitrary disposition, which in turn requires a more complex scanning system.
Swartz et al., U.S. Pat. No. 5,637,851 and Wevelseip, U.S. Pat. No. 4,691,367 disclose systems in which data captured by a raster scan is stored as a two-dimensional
Au Ka Man
Zhu Zaioxun
Lerner David Littenberg Krumholz & Mentlik LLP
Metrologic Instruments Inc.
Wu Jingge
LandOfFree
Skew processing of raster scan images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Skew processing of raster scan images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Skew processing of raster scan images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2945822