Method and apparatus for automatic discriminating and locating patterns such as finder patterns, or portions thereof, in machine-readable symbols
First Claim
1. In a symbol reading apparatus capable of storing an image of a data collection symbol, the stored image being comprised of a plurality of pixels and the symbol having a predetermined pattern of geometric shapes, a method of locating portions of the shapes within the stored image, the method comprising:
- locating a stalking pixel of a shape of the symbol within the stored image;
sequentially identifying adjacent pixels along an edge of the shape within the stored image from the starting pixel;
performing at least one distortion compensating subroutine selected from a plurality of distortion compensating subroutines if an adjacent pixel cannot be located, wherein at least one of the plurality of distortion compensating subroutines does not fill in the adjacent pixel;
selecting at least one linked pixel in the stored image based on the performing;
repeating the sequentially identifying, performing and selecting;
producing a set of pixels that identify at least a portion of the shape based on the repeating;
determining if the set of pixels contains representations of one of several selected patterns of geometric portions for corresponding data collection symbology types, a first selected pattern corresponding to the predetermined pattern of geometric shapes of the data collection symbol, wherein the selected patterns of geometric portions include lines and curves represented by a series of substantially adjacent pixels, and wherein the selected patterns do not represent widths of a plurality of shapes as measured along an intersecting sampling path; and
identifying the data collection symbol in the stored image if the detected geometric portions correspond to the first selected pattern.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for locating geometric shapes or edges thereof in data collection symbols initially samples and stores an image of light reflected from the symbol. Thereafter, two routines are performed. A first routine performs low level vision processing by identifying linked points along edges, lines, curves or within shapes. A rapid pixel linking subroutine identifies edge pixels in symbol images lacking distortion. If the edge or shape suffers from distortions, then one or more distortion compensating subroutines locate sequential linked pixels despite such distortions. The resulting coordinates of linked points, which represent lines, curves and other geometric shapes, are then employed by a second routine which identifies patterns within the identified lines/curves. Based on these identified patterns, types of symbols from various symbologies can be identified and located within the stored image.
229 Citations
29 Claims
-
1. In a symbol reading apparatus capable of storing an image of a data collection symbol, the stored image being comprised of a plurality of pixels and the symbol having a predetermined pattern of geometric shapes, a method of locating portions of the shapes within the stored image, the method comprising:
-
locating a stalking pixel of a shape of the symbol within the stored image; sequentially identifying adjacent pixels along an edge of the shape within the stored image from the starting pixel; performing at least one distortion compensating subroutine selected from a plurality of distortion compensating subroutines if an adjacent pixel cannot be located, wherein at least one of the plurality of distortion compensating subroutines does not fill in the adjacent pixel; selecting at least one linked pixel in the stored image based on the performing; repeating the sequentially identifying, performing and selecting; producing a set of pixels that identify at least a portion of the shape based on the repeating; determining if the set of pixels contains representations of one of several selected patterns of geometric portions for corresponding data collection symbology types, a first selected pattern corresponding to the predetermined pattern of geometric shapes of the data collection symbol, wherein the selected patterns of geometric portions include lines and curves represented by a series of substantially adjacent pixels, and wherein the selected patterns do not represent widths of a plurality of shapes as measured along an intersecting sampling path; and identifying the data collection symbol in the stored image if the detected geometric portions correspond to the first selected pattern. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer implemented method of locating an image of a data collection symbol in a two-dimensional stored image, the two-dimensional stored image being represented by a plurality of points and the data collection symbol having a predetermined pattern of geometric shapes, the method comprising:
-
detecting geometric portions of the data collection symbol in the two-dimensional stored image based on groups points in the plurality of points; determining, if the detected geometric portions correspond to one of several selected patterns of geometric portions for corresponding data collection symbology types, a first selected pattern corresponding, to the predetermined pattern of geometric shapes of the data collection symbol wherein the selected patterns of geometric portions includes lines and curves represented by a series of substantially adjacent pixels, and wherein the selected patterns do not represent widths of a plurality of shapes as measured along an intersecting sampling path; and identifying the data collection symbol in the two-dimensional stored image if the detected geometric portions correspond to the first selected pattern. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. In a symbol reading apparatus capable of storing an image of a data collection symbol, the stored image being comprised of a plurality of pixels and the symbol being comprised of a plurality of geometric shapes, a method of locating portions of the shapes within the stored image, the method comprising:
-
sequentially identifying adjacent pixels along an edge of the shape within the stored image; performing at least one distortion compensating subroutine selected from a plurality of distortion compensating subroutines if an adjacent pixel cannot be located, wherein at least one of the plurality of distortion compensating subroutines does not fill in the adjacent pixel; selecting at least one linked pixel in the stored image based on the performing; producing a set of pixels that identify at least a portion of the shape based on the sequentially identifying and selecting; and identifying a selected geometric shape from a set of shapes within the stored image based on the set of pixels, wherein the set of shapes includes lines and curves defined approximately by substantially adjacent pixels, and wherein the selected patterns do not represent widths of a plurality of shapes as measured along an intersecting sampling path. - View Dependent Claims (21, 22, 23, 24, 25)
-
-
26. In a symbol reading apparatus capable of storing an image of a data collection symbol, the stored image being comprised of a plurality of pixels and the symbol having a predetermined pattern of geometric shapes, a method of locating portions of the shapes within the stored image, the method comprising:
-
sequentially identifying adjacent pixels along an edge of the shape within the stored image from a starting pixel to produce a set of pixels that identify at least a portion of the shape; and determining if the set of pixels contains representations of one of several selected patterns of geometric portions, which includes; determining if the set of pixels contains at least two parallel lines, and if so, determining that the data collection symbol is a Code One symbol; determining if the set of pixels contains at least two lines having ends intersecting at approximately 90°
, and if so, determining that the data collection symbol is a Data Matrix; anddetermining if the set of pixels contains at least a partially enclosed curve, and if so, determining that the data collection symbol is a MaxiCode symbol.
-
-
27. A computer implemented method of locating an image of a data collection symbol in a two-dimensional stored image, the two-dimensional stored image being represented by a plurality of points and the data collection symbol having a pattern of geometric shapes, the method comprising:
-
detecting geometric portions of the data collection symbol in the two-dimensional stored image based on groups of points in the plurality of points, including; determining a cross-sectional length of at least one of the geometric shapes; locating a center point of the cross-sectional length; selecting a new point based on the center point; determining a new cross-sectional length of the geometric shape at the new point; and repeating the locating, selecting and determining a new cross-sectional length, for at least one iteration; and identifying the data collection symbol in the two-dimensional stored image.
-
-
28. A computer implemented method of locating an image of a data collection symbol in a two-dimensional stored image, the two-dimensional stored image being represented by a plurality of points and the data collection symbol having a predetermined pattern of geometric shapes, the method comprising:
-
detecting geometric portions of the data collection symbol in the two-dimensional stored image based on groups of points in the plurality of points; determining if the detected geometric portions correspond to at least a partially enclosed curve that corresponds to one of several selected patterns of geometric portions; and identifying the data collection symbol in the two-dimensional stored image as a MaxiCode symbol if the detected geometric portions include at least the partially enclosed curve.
-
-
29. In a symbol reading apparatus capable of storing an image of a data collection symbol, the stored image being comprised of a plurality of pixels and the symbol being comprised of a plurality of geometric shapes, a method of locating portions of the shapes within the stored image, the method comprising:
performing at least one distortion compensating subroutine selected from a plurality of distortion compensating subroutines if an adjacent pixel cannot be located, wherein at least one of the plurality of distortion compensating subroutines does not fill in the adjacent pixel, including; determining a cross-section of at least one of the geometric shapes; locating a center point of the cross-section; selecting a pixel in a forward direction; determining a new cross-section of the determined shape at the selected pixel in the forward direction; and repeating the locating, selecting and determining a new cross-section for a selected number of iterations; and identifying a selected geometric shape within the stored image.
Specification