Registers – Coded record sensors – Particular sensor structure
Reexamination Certificate
1997-04-16
2001-01-16
Tremblay, Mark (Department: 2876)
Registers
Coded record sensors
Particular sensor structure
C235S462080, C235S462410
Reexamination Certificate
active
06173893
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to data scanners and to video imaging techniques used with data scanners. More particularly, the invention relates to a finding process, wherein a scanner is used to locate a symbology within a field of view of the scanner.
BACKGROUND OF THE INVENTION
An “over-the-belt” barcode scanner system is a system in which a camera or other imaging device is positioned over or adjacent a pathway, such as a conveyer belt, to scan items which pass through a field of vision of the imaging device. Such a system is primarily designed to read any bar code in a wide field of view. The width of the searching area for over-the-belt scanner systems is typically from 30 cm up to 150 cm.
If the imager is positioned over the belt, the width of the belt defines the number of sensing elements necessary to achieve the desired resolution. For example, if the scanner system needs to read a bar code symbology with a 0.125 mm. (0.005 in) “x” dimension in a 75 cm wide field of view, then the minimum resolution has to be at least one pixel per element or, in this case, one pixel per 0.125 mm. The total number of required sensing elements in this case will be 750/0.125=6000 pixels. As we can see from this example, the width of the searching area in many practical applications is extremely large. The situation is significantly aggravated for two dimensional bar code symbologies such as Data Matrix.
Prior to reading a symbology, it is necessary to locate the symbology. In some cases, the symbology is not aligned with a specific scanner location, so that it is necessary to locate the symbology within a large field of view. The process of locating the symbology for subsequent reading of the symbology is called “finding.” Early finding techniques included attempting to scan symbologies until a predetermined beginning or ending sequence of leading edges was detected, followed by further sequences which match a predetermined pattern. This technique is particularly well adapted to data scans of bar codes in similar one-dimensional symbologies. In the case of two-dimensional symbologies, such a scan is inadequate.
Various techniques have been used to find two-dimensional symbologies. These techniques include scanning for characteristics that are added to the symbology to identify a position of the symbology. Typical characteristics of this type include starting bars, center targets and finder patterns. For example, to identify the location of Data Matrix symbology, an L-shaped finder pattern is used to locate the symbology in the field of view of a video imager. Any straight line within the field of view is a candidate for the “L” searching algorithm. This means that in order to find the symbology, we must trace every straight line in an attempt to find another straight line which is perpendicular to the first line. A goal of the present invention is to provide a method of filtering the image in real time in order to eliminate all features which are distinguishable from the symbology.
It would be advantageous if one could efficiently and quickly perform the “finding” operation. Since the code itself need not be read, it would be advantageous if finding were accomplished in a different and simpler manner from the process of reading the code.
SUMMARY OF THE INVENTION
The present invention intends to exploit the general nature of the symbology itself, rather than attempt to make use of a separate locator pattern. This has the advantage of identifying the location of a symbology by looking for features which are characteristic of the symbology itself.
In its basic form, the method of the invention comprises scanning a field of view to find a pattern of high incidence of image changes characteristic of the scan passing a symbology as distinguished from image changes characteristic of background imagery. This is preferably accomplished by identifying the symbology without attempting to fully interpret the symbology itself.
The field of view is a region scanned by a video imager such as a video camera, a laser scanner or other video imaging device in order to generate a bit map of an image. In the case of a video camera, the field of view is usually determined by lens optics and an internal image receiver such as a charge coupled device, but it is also possible to move the imager to complete the field of view. As used in this description, “field of view,” means the entire expanse of space visible to an observer (scanner) at a given instant. In the case of a video camera, this means the entire expanse of space visible to the camera at a given instant without moving the camera. If the position of an imager is above a belt, the field of view is horizontal. If it is alongside the belt, the field of view is vertical. Similar spatial considerations apply in either case.
The method of the invention exploits the features of the pattern structure of two-dimensional symbologies by attempting to obtain, but not read, a pattern which is characteristic of a two-dimensional symbology. Two-dimensional symbologies typically have regularly-shaped data patterns, such as the checkerboard structure characteristic of the Data Matrix symbology, or the hexagonal shapes characteristic of the Maxi Code symbology.
In the operation of the invention, it is not necessary that the finding algorithm scan an entire field in order to locate a starting code or target feature of the symbology. Instead, an image is scanned in order to locate characteristics of the symbology without attempting to read the symbology during the finding process. Preferably, the scanning is accomplished by scanning an image in a field of view in multiple scan lines which are in close proximity to each other. The scanned lines are reduced to reference coordinates of points where a brightness of the image changes in value, for example, from white to black. The changes in value are referred to as edge points. The coordinates of the edge points are stored and compared with the coordinates of edge points on adjacent scan lines.
When an edge point is found, the coordinates above and below the edge point are analyzed to determine an edge crossing angle. The scanning of a portion of a symbology results in characteristic angles between sequential edge points. A “hit” is obtained when a change in the angles of sequential edge points meets a predetermined criterion which matches that of a symbology. The symbology is considered to be at the location where a high incidence of hits occurs.
In accordance with the preferred embodiment of the invention, a plurality of processors are used in order to scan across scan lines which are separated by a small distance. The outputs of the processors are compared, so that when there is a redundancy of hits, the detection of a symbology is confirmed. By the use of multiple processors, it is possible to perform scans of the entire field of view and to process the scans without a requirement that real time processing occur between sequential scans. The outputs of multiple scanning processors are provided to a decoding processor, and the decoding processor correlates the data from the scanning processors to determine the location of the symbology.
In accordance with a further aspect of the invention, a scanner for finding a symbology includes an imager, a bit map memory and at least one finding processor. The finding processor is capable of scanning the bit map in order to find a pattern of image changes corresponding to a scan pattern passing the symbology, as distinguished from image changes corresponding to background imagery. This is done without reading the data in the symbology. If the pattern of image changes meets a predetermined criterion, this provides an indication of a location of a symbology.
In accordance with a further aspect of the invention, an apparatus includes an imager which provides image data to a bit map. A group of scan lines, in close proximity to each other, is established from the bit map. A group of processors each reads lines within the group. Each of the processors use closely-
Maltsev Pavel
Penn Richard
Intermec Corporation
Pauly Joan H.
Tremblay Mark
LandOfFree
Fast finding algorithm for two-dimensional symbologies does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast finding algorithm for two-dimensional symbologies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast finding algorithm for two-dimensional symbologies will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2524038