Locating 2-D bar codes

• US 5,304,787 A
• Filed: 06/01/1993
• Issued: 04/19/1994
• Est. Priority Date: 06/01/1993
• Status: Expired due to Term

• Current Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Original Assignee: Metamedia Corporation
• Inventors: Wang, Ynjiun P.
• Primary Examiner(s): Hajec, Donald
• Assistant Examiner(s): Chin, Esther
• Application Number:
  US08/069,546
• Time in Patent Office: 322 Days
• Field of Search: 235/462, 235/467, 235/472, 235/470, 235/494, 235/440, 235/463
• US Class Current: 235/462.09
• CPC Class Codes: G06K 19/06056 the marking comprising a further embedded marking, e.g. a 1D bar code with the black bars containing a smaller sized coding
• CPC Class Codes: G06K 7/1093 sensing, after transfer of the image of the data-field to an intermediate store, e.g. storage with cathode ray tube
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06K 7/1434 Barcodes with supplemental or add-on codes
• CPC Class Codes: G06K 7/1443 locating of the code in an image

Abstract

After a two-dimensional bar code is scanned to provide a stored image, the location (i.e., bounds, including orientation) of the bar code image within the scanned area image must be determined to enable decoding. Methods for locating the bar code image include the steps of sampling the stored image, identifying sampling traversals of bar code start and stop patterns, and correlating the identified start and stop pattern traversals to a common bar code image. The correlating data is then used to identify a nominally rectangular area bounding the bar code image. A bounding box may be identified as the smallest area capable of encompassing all of the start and stop pattern traversals related to a common bar code image. Output location data may specify the coordinates of the four corners of a bounding box for use in subsequent decoding. Related systems are described.

Claims

1. A method for locating and determining the bounds of a two-dimensional bar code image including identifiable start and stop patterns, comprising the steps of:

(a) providing a stored image representing a scanned image area which may include said two-dimensional bar code image;

(b) sampling said stored image along spaced parallel scan lines in a first direction across a potential bar code image location included in said image area, to provide scan line samplings;

(c) repeating said step (b) sampling in at least one additional direction having an angular separation from said first direction, to provide additional scan line samplings;

(d) analyzing scan line samplings provided in steps (b) and (c) to identify bar code start and stop pattern traversals where said samplings cross said patterns;

(e) correlating said bar code start and stop patterns as representative of a common bar code image (i) when two start patterns, or two stop patterns, are identified in scan line samplings taken along parallel scan lines having not more than a predetermined lateral spacing, and (ii) when a start pattern and a stop pattern are identified in the same scan line sampling with said start and stop patterns having not more than a predetermined separation, to identify correlated start and stop pattern traversals representative of said bar code image;

(f) utilizing said correlated start and stop pattern traversals representative of said bar code image to identify a nominally rectangular area bounding said bar code image; and

(g) making available data representative of the location of said nominally rectangular area within said scanned image area.

2. A method as in claim 1, wherein said step (a) comprises providing said stored image as a two-dimensional array of pixel data capable of being sampled in a plurality of directions having angular separations.

3. A method as in claim 1, wherein step (c) comprises repeating said step (b) three times at successive 45 degree angular separations from said first direction.

4. A method as in claim 1, wherein step (e) comprises correlating start and stop patterns pursuant to clause (i) with said predetermined lateral spacing in clause (i) equal to twice the separation between adjacent scan lines and pursuant to clause (ii) with said predetermined separation in clause (ii) equal to a maximum bar code dimension.

5. A method as in claim 1, wherein step (f) comprises identifying said nominally rectangular area by the coordinates of its four corners and wherein data defining said coordinates is made available in step (g).

6. A method as in claim 1, wherein step (f) comprises identifying said nominally rectangular area as the smallest such area encompassing the positions of all said start and stop pattern traversals correlated as representing a common bar code image.

7. A method as in claim 1, wherein step (f) comprises identifying nominally rectangular areas bounding one-dimensional bar code images as well as such areas bounding two-dimensional bar code images.

8. A system for locating a two-dimensional bar code image, including identifiable start and stop patterns, within a stored image representing a scanned image area which may include said two-dimensional bar code image, comprising:

sampling means for sampling said stored image along spaced parallel scan lines in a first direction across a potential bar code image location included in said image area to provide first scan line samplings, and for similarly sampling said stored image in at least one additional direction having an angular separation from said first direction to provide additional scan line samplings;

analysis means, coupled to said sampling means, for analyzing said first and additional scan line samplings to identify bar code start and stop patterns traversed by said samplings;

correlating means, coupled to said analysis means, for correlating said bar code start and stop patterns as representative of a common bar code image (i) if two start patterns, or two stop patterns, are identified in scan line samplings taken along parallel scan lines having not more than a predetermined lateral spacing and (ii) if a start pattern and a stop pattern are identified in the same scan line sampling with said patterns having not more than a predetermined separation, to provide correlated start and stop pattern data representing said bar code image;

bounds identifying means, coupled to said correlating means, for utilizing said correlated start and stop pattern data representing said bar code image to derive data identifying a nominally rectangular area bounding said bar code image; and

output port means, coupled to said bounds identifying means, for coupling said data identifying said nominally rectangular area for further use.

9. A system as in claim 8, wherein said sampling means is arranged for sampling said stored image in four directions having successive angular separations of 45 degrees.

10. A system as in claim 8, wherein said bounds identifying means is arranged for deriving data identifying said nominally rectangular area by the coordinates of four corners of said rectangular area.

11. A system as in claim 8, wherein said bounds identifying means is arranged for deriving data identifying the smallest area encompassing the positions of all said start and stop pattern traversals correlated as representing a common bar code image.