Time-efficient method of analyzing imaged input data to locate two-dimensional machine-readable symbols or other linear images therein
First Claim
1. A method of locating a machine-readable symbol representing encoded information, the symbol including a plurality of selectively spaced two-dimensional geometric shapes, the symbol having a predetermined orientation pattern of at least two elongated shapes or spaces, the method comprising:
- storing an image of the symbol;
dividing the stored image into a plurality of analysis regions;
sampling at least two regions along a plurality of sampling paths in each region, wherein the plurality of sampling paths begin from a selected point in each region and end at approximately a boundary of region;
locating an edge point;
analyzing an area adjacent to the edge point to locate a first elongated edge;
locating the first elongated edge based on the sampled linear sampling paths;
determining if the located first elongated edge is an edge of one of the elongated shapes or spaces;
identifying a second elongated edge of another of the elongated shapes or spaces; and
defining a position and orientation of the image of the symbol based on the located first elongated edge and the identified second elongated edge.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus locates edges of patterns in a stored image, such as edges of start/stop patterns of machine-readable symbols (e.g., PDF 417 symbols). The present invention first divides the stored image into analysis regions and samples each region using a 16-beam star pattern. The beam patterns are analyzed to detect for edges that may correspond to edges of start/stop patterns of the symbol. Coast lines, or elongated edges, of the detected edges are analyzed for parallelism and minimal length to filter out any spurious detected edges. Thereafter, the coast lines are analyzed to confirm that a start or stop pattern has been located. A second start/stop pattern is thereafter located, boundary points are determined at a periphery of the symbol, and finally the symbol is analyzed for its geometric shape to confirm that the located boundary points conform to an accepted geometry for this symbol.
253 Citations
37 Claims
-
1. A method of locating a machine-readable symbol representing encoded information, the symbol including a plurality of selectively spaced two-dimensional geometric shapes, the symbol having a predetermined orientation pattern of at least two elongated shapes or spaces, the method comprising:
-
storing an image of the symbol; dividing the stored image into a plurality of analysis regions; sampling at least two regions along a plurality of sampling paths in each region, wherein the plurality of sampling paths begin from a selected point in each region and end at approximately a boundary of region; locating an edge point; analyzing an area adjacent to the edge point to locate a first elongated edge; locating the first elongated edge based on the sampled linear sampling paths; determining if the located first elongated edge is an edge of one of the elongated shapes or spaces; identifying a second elongated edge of another of the elongated shapes or spaces; and defining a position and orientation of the image of the symbol based on the located first elongated edge and the identified second elongated edge. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. In a computer system having a processor and a data storage device, a computer implemented method of locating one or more predetermined elongated shapes in an image stored in the data storage device, the stored image possibly including additional elongated shapes, the method comprising:
-
dividing the stored image into a plurality of analysis regions; sampling at least two regions along a plurality of sampling paths in each region, wherein the plurality of sampling paths begin from a selected point in each region and end at approximately a boundary of region; locating a first elongated edge based on the sampled sampling paths; determining if the located first elongated edge is an edge of the predetermined elongated shape; determining a dominant direction of the located first elongated edge; and defining the location of the predetermined elongated shape based on the located first elongated edge. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. An apparatus for decoding a machine-readable symbol representing encoded information, the symbol including a plurality of selectively spaced two-dimensional geometric shapes, the symbol having a predetermined orientation pattern of at least two elongated shapes or spaces, the apparatus comprising:
-
a sensor that receives light that is reflected from the symbol and produces an output signal therefrom that resents the reflectance of the shapes and spaces comprising the symbol; a receiver that receives the output signal and produces a digital signal representing an image of the shapes and spaces of the symbol; a storage device for storing the digital signal; a processor for processing the digital signal and producing a signal indicative of the information encoded in the symbol, wherein the processor (a) divides the image into a plurality of analysis regions, (b) samples at least one region along a plurality of sampling paths, (c) locates a first elongated edge based on the sampled sampling paths, (d) determines if the located first elongated edge is an edge is an edge of one of the elongated shapes or spaces, (e) identifies a second elongated edge of another of the elongated shapes or spaces, (f) defines a position of the image of the symbol based on the located first elongated edge and the identified second elongated edge, and (g) decodes the symbol and producing a signal indicative of the information encoded in the symbol based on the defined position of the symbol; and wherein the processor divides the stored image into at least center, top, bottom, left, and right analysis regions, and wherein the center region has an area larger than areas of each of the top, bottom, left and right regions.
-
-
25. An apparatus for decoding a machine-readable symbol representing encoded information, the symbol including a pluralitv of selectively spaced two-dimensional geometric shapes, the symbol having a predetermined orientation pattern of at least two elongated shapes or spaces, the apparatus comprising:
-
a sensor that receives light that is reflected from the symbol and produces an output signal therefrom that represents the reflectance of the shapes and spaces comprising the symbol; a receiver that receives the output signal and produces a digital signal representing an image of the shapes and spaces of the symbol; a storage device for storing the digital signal; a processor for processing the digital signal and producing a signal indicative of the information encoded in the symbol, wherein the processor (a) divides the image into a plurality of analysis regions, (b) samples at least one region along a plurality of sampling paths, (c) locates a first elongated edge based on the sampled sampling paths, (d) determines if the located first elongated edge is an edge is an edge of one of the elongated shapes or spaces, (e) identifies a second elongated edge of another of the elongated shapes or spaces, (f) defines a position of the image of the symbol based on the located first elongated edge and the identified second elongated edge, and (g) decodes the symbol and producing a signal indicative of the infornation encoded in the symbol based on the defined position of the symbol; and wherein the processor locates the elongated edges by (a) locating an edge point, (b) analyzing an area proximate the located edge point to locate the first elongated edge, (c) determining a dominant direction of the located first elongated edge based on the analyzed area, and (d) applying a vertical searching template for locating a position of the first elongated edge if the dominant direction is horizontal, and applying a horizontal searching template for locating a position of the first elongated edge if the dominant direction is vertical.
-
-
26. In a computer system having a processor and a data storage device, a computer implemented method of analyzing an image stored in the data storage device for a predetermined shape, the method comprising the steps of:
-
defining a point within the stored image, wherein defining defines a point approximately in the center of the stored image; and sampling the stored image along a plurality of approximately linear sampling paths for the predetermined shape, wherein each sampling path extends from the defined point.
-
-
27. In a computer system having a processor and a data storage device, a computer implemented method of analyzing an image stored in the data storage device for one or more predetermined shapes, the method comprising:
-
dividing the stored image into at least a center analysis region and surrounding analysis regions, and wherein the center region has an area larger than areas of the surrounding regions; and sequentially sampling always the center region first, and then sampling the surrounding regions second, until the predetermined shape is located in the stored image. - View Dependent Claims (28, 29, 30, 31, 32)
-
-
33. In a computer system having a processor and a data storage device, a computer implemented method of analyzing an image stored in the data storage device for one or more predetermined shapes, the method comprising:
-
dividing the stored image into at least center, top, bottom, left, right, and corner analysis regions; and analyzing always the center region first, before analyzing the top, bottom, left, and right regions second, and the corner regions third to determine the location of the predetermined shape or shapes in the stored image. - View Dependent Claims (34, 35, 36, 37)
-
Specification