Patent US6064763A successfully refreshed from Google Patents.
US6064763A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Time-efficient method of analyzing imaged input data to locate two-dimensional machine-readable symbols or other linear images therein
Assignee: Intermec IP Corp
•
Filing: 1996-07-26
•
Granted: 2000-05-16
•
Expires: 2016-07-26
Abstract
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.
Inventors
- 👤 Pavel A. Maltsev
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 21:06
CPC Classifications
G; G06; G06K; G06K7/00; G06K7/10; G06K7/14; G06K7/1404; G06K7/146; G06K7/1478; G06K7/1486; G06V; G06V30/00; G06V30/10; G06V30/14; G06V30/146
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
177 words
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.
Claim 2
Independent Claim
177 words
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.
Claim 3
Dependent Claim
44 words
The method of claim 1 wherein storing an image of the symbol stores an image of a PDF417 symbol and wherein the elongated shapes or spaces are first and second wide bars of start and stop patterns that define opposite ends of the symbol.
Claim 4
Dependent Claim
46 words
The method of claim 1 wherein dividing the stored image 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.
Claim 5
Dependent Claim
42 words
The method of claim 1 wherein dividing the stored image divides the stored image into at least center, top, bottom, left, and right analysis regions, and wherein the sampling samples the center region before sampling the top, bottom, left and right regions.
Claim 6
Dependent Claim
30 words
The method of claim 1 wherein sampling sequentially samples the region along a plurality of approximately linear sampling paths that radially extend from approximately a center point of the region.
Claim 7
Dependent Claim
37 words
The method of claim 1 wherein sampling samples the region along a plurality of approximately linear sampling paths, wherein each of the sampling paths extend from a point in the region to an edge of the region.
Claim 8
Dependent Claim
65 words
The method of claim 1 wherein locating includes: determining a dominant direction of the located first elongated edge based on the analyzed area; and 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.
Claim 9
Dependent Claim
26 words
The method of claim 1, further comprising the step of decoding the information encoded in the symbol based on the located predetermined point of the symbol.
Claim 10
Dependent Claim
63 words
The method of claim 1 wherein determining if the located first elongated edge is an edge of one of the elongated shapes or spaces includes: locating an opposite edge of one of the elongated shapes or spaces; comparing the opposite edge to the first elongated edge; and ignoring the first elongated edge if the first and opposite elongated edges are not approximately parallel.
Claim 11
Dependent Claim
58 words
The method of claim 1 wherein determining includes: determining an X-dimension of the symbol; determining a width of the one shape or space having the located first elongated edge; comparing the determined width to an expected width based on the determined X-dimension; and ignoring the first elongated edge if the determined width substantially differs from the expected width.
Claim 12
Dependent Claim
91 words
The method of claim 1 wherein storing an image of the symbol stores an image of a PDF417 symbol, wherein the elongated shapes or spaces are first and second wide bars of start and stop patterns that define opposite ends of the symbol, and wherein determining includes: sampling along at least one path perpendicular to the located first elongated edge; comparing the sampled perpendicular path to an expected path through the start or stop patterns; and ignoring the first elongated edge if the sampled path substantially differs from the expected path.
Claim 13
Dependent Claim
78 words
The method of claim 1 wherein storing an image of the symbol stores an image of a PDF417 symbol, wherein the elongated shapes or spaces are first and second wide bars of start and stop patterns that define opposite ends of the symbol, and wherein defining includes: identifying pairs of end points at opposite ends of the first and second elongated edges; and defining a bounding box around the symbol based on the identified pairs of end points.
Claim 14
Dependent Claim
48 words
The method of claim 1, further comprising: determining first and second angles of the first and second elongated edges with respect to a selected line; comparing the first and second angles; aborting the method if the first and second angles have a predetermined relationship to a selected value.
Claim 15
Dependent Claim
142 words
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.
Claim 16
Dependent Claim
142 words
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.
Claim 17
Dependent Claim
89 words
The method of claim 14 wherein the stored image includes an image of a machine-readable symbol, wherein the predetermined elongated shapes are first and second bars of start and stop patterns that define opposite ends of the symbol, wherein locating a first elongated edge locates a first elongated edge of the first bar, and wherein the method further includes: identifying a second elongated edge of the second bar; and defining a position and orientation of the image of the symbol based on the located first and second elongated edges.
Claim 18
Dependent Claim
46 words
The method of claim 14 wherein dividing the stored image 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.
Claim 19
Dependent Claim
41 words
The method of claim 14 wherein dividing the stored image divides the stored image into at least center, top, bottom, left, and right analysis regions, and wherein sampling samples the center region before sampling the top, bottom, left and right regions.
Claim 20
Dependent Claim
30 words
The method of claim 14 wherein sampling sequentially samples the region along a plurality of approximately linear sampling paths that radially extend from approximately a center point of the region.
Claim 21
Dependent Claim
37 words
The method of claim 14 wherein sampling samples the region along a plurality of approximately linear sampling paths, wherein each of the sampling paths extend from a point in the region to an edge of the region.
Claim 22
Dependent Claim
66 words
The method of claim 14 wherein the locating includes: determining a dominant direction of the located first elongated edge based on the analyzed area; and 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.
Claim 23
Dependent Claim
43 words
The method of claim 14 wherein determining includes: locating an edge opposite to the first elongated edge; comparing the opposite edge to the first elongated edge; and ignoring the first elongated edge if the first and opposite elongated edges are not approximately parallel.
Claim 24
Dependent Claim
86 words
The method of claim 14 wherein the stored image includes an image of a machine-readable symbol, wherein the predetermined elongated shapes are first and second bars of start and stop patterns that define opposite ends of the symbol, and wherein determining includes: sampling along at least one path perpendicular to the located first elongated edge; comparing the sampled perpendicular path to an expected path through the start or stop patterns; and ignoring the first elongated edge if the sampled path substantially differs from the expected path.
Claim 25
Dependent Claim
94 words
The method of claim 14 wherein the stored image includes an image of a machine-readable symbol, wherein the predetermined elongated shapes are first and second bars of start and stop patterns that define opposite ends of the symbol, and wherein the method further comprising: identifying a second elongated edge of the second bar; determining first and second angles of the first and second elongated edges with respect to a selected line; comparing the first and second angles; aborting the method if the first and second angles have a predetermined relationship to a selected value.
Claim 26
Independent Claim
279 words
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.
Claim 27
Independent Claim
279 words
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.
Claim 28
Independent Claim
327 words
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.
Claim 29
Independent Claim
327 words
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.
Claim 30
Dependent Claim
82 words
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.
Claim 31
Dependent Claim
82 words
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.
Claim 32
Dependent Claim
90 words
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.
Claim 33
Dependent Claim
90 words
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.
Claim 34
Dependent Claim
49 words
The method of claim 27 wherein dividing the stored image includes dividing the surrounding analysis regions into at least top, bottom, left, and right analysis regions, and wherein the center analysis region has an area larger than areas of each of the top, bottom, left and right analysis regions.
Claim 35
Dependent Claim
51 words
The method of claim 27 wherein dividing the stored image divides the stored image into at least center, top, bottom, left, right and corner analysis regions, and wherein sequentially sampling samples the center analysis region first, the top, bottom, left and right analysis regions second, and the corner analysis regions third.
Claim 36
Dependent Claim
50 words
The method of claim 27 wherein dividing the stored image includes dividing the surrounding analysis regions into at least top, bottom, left, and right analysis regions, and wherein sequentially sampling samples the center analysis region first, the top and bottom regions second and the left and right analysis regions third.
Claim 37
Dependent Claim
17 words
The method of claim 27 wherein dividing the stored image divides the stored image into nine regions.
Claim 38
Dependent Claim
46 words
The method of claim 27 wherein analyzing includes: defining a point within at least one of the regions of the stored image; and sampling the region a plurality of approximately linear sampling paths for the predetermined shape, wherein each sampling path extends from the defined point.
Claim 39
Dependent Claim
87 words
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.
Claim 40
Dependent Claim
87 words
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.
Claim 41
Dependent Claim
31 words
The method of claim 33 wherein in dividing the stored image the center region has an area larger than areas of each of the top, bottom, left, right, and corner regions.
Claim 42
Dependent Claim
40 words
The method of claim 33 wherein dividing the stored image divides the stored image into at least center, top, bottom, left, and right analysis regions, and wherein the top and bottom regions are analyzed before the left or right regions.
Claim 43
Dependent Claim
17 words
The method of claim 33 wherein dividing the stored image divides the stored image into nine regions.
Claim 44
Dependent Claim
46 words
The method of claim 33 wherein analyzing includes: defining a point within at least one of the regions of the stored image; and sampling the region a plurality of approximately linear sampling paths for the predetermined shape, wherein each sampling path extends from the defined point.
References Cited (Backward Citations)
US2612994A
Cited
US4013893A
Cited
US4687942A
Cited
US4916298A
Cited
US4874936A
Cited
US4998010A
Cited
US5324923A
Cited
US5635697A
Cited
US5080456A
Cited
US5241166A
Cited
US5189292A
Cited
US5376780A
Cited
US5319181A
Cited
US5276315A
Cited
US5438636A
Cited
US5418862A
Cited
US5373147A
Cited
US5523552A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-16 | 2003-11-15 | 2004-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-16 | 2007-11-15 | 2008-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-16 | 2011-11-15 | 2012-05-16 | $7700.00 | Window Closed / Lapsed |