Detecting image cell position with subpixel accuracy

• US 6,129,278 A
• Filed: 05/19/1994
• Issued: 10/10/2000
• Est. Priority Date: 05/19/1994
• Status: Expired due to Term

• Current Assignee: Symbol Technologies, LLC (Zebra Technologies Corporation)
• Original Assignee: Metanetics Corporation
• Inventors: Ju, Paul Pay-Lun, Wang, Ynjiun P.
• Primary Examiner(s): Porta, David P.
• Assistant Examiner(s): TREMBLAY, MARK STEPHEN
• Application Number:
  US08/245,613
• Time in Patent Office: 2,336 Days
• Field of Search: 235/463, 235/462, 235/462.01, 348/625, 382/199
• US Class Current: 235/462.01
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1452 detecting bar code edges
• CPC Class Codes: G06K 7/1469 using sub-pixel interpolation

Abstract

By providing subpixel accuracy in the detection of the position of an element of a pixel data image, the invention makes possible reductions in scanner and storage resolution of the order of 65 percent or greater for two-dimensional applications. Methods use normalized gray level values to determine the extent of coverage of an image cell by individual pixels. By then applying such gray level values of a plurality of successive pixels to a preconstructed lookup table, ambiguities are resolved to determine the position of cell edges. The cell edge data can be used to determine cell position or used directly in edge-based bar code decoding techniques. Cell position data is used for construction of a virtual image of a bar code or other dataform of interest and virtual image information may then be used for purposes of decoding the bar code or other dataform. For two-dimensional applications, the gray level values of a plurality of successive pixels, as referred to, may be implemented as a sliding window of three such gray level values along successive lines in a first dimension which are applied to a lookup table, followed by repetition for successive lines in a perpendicular dimension, to derive cell edge data for both dimensions.

Claims

1. A method for detecting the position of a cell represented in a pixel data image, comprising the steps of:

(a) acquiring a pixel data image including a representation of said cell;

(b) determining a pixels-per-cell nominal resolution of said pixel data image;

(c) normalizing the resolution of said pixel data image by one of the following (i) reducing said nominal resolution to a pixels-per-cell target resolution having a selected value, and (ii) if said nominal resolution corresponds to said selected value, stabilizing said nominal resolution at said target resolution;

(d) determining a gray level value for each of a plurality of successive pixels along a first axis, including cell coverage pixels intersected by cell edge crossings, each said cell coverage pixel having a gray level value representing the position of said cell edge crossing subject to an ambiguity as to the order along said first axis of complementary pixel portions of said cell coverage pixel respectively inside and outside the area of said cell in said pixel data image;

(e) utilizing the order and magnitudes of a sequence of said gray level values for a group of successive pixels along said first axis (i) to resolve said ambiguity to determine, for each said cell coverage pixel, the order of its said complementary inside and outside portions along said first axis and (ii) to derive cell edge position data;

(f) deriving cell position data for said cell using step (e) cell edge position data; and

(g) utilizing said cell position data from step (f) to provide a virtual image of said cell.

2. A method as in claim 1, wherein step (a) comprises acquiring an image of a cell of one of the following machine readable dataforms:

a two-dimensional bar code;

a matrix code.

3. A method as in claim 1, wherein:

step (a) comprises acquiring a pixel data image of an entire machine readable dataform image;

steps (d) through (f) are repeated for additional cells of said image; and

step (g) provides a virtual image of said entire dataform image.

4. A method as in claim 3, additionally comprising the step of decoding said virtual image provided in step (g) to provide output signals representative of data originally encoded in said dataform.

5. A method as in claim 3, wherein said cell first referred to represents a minimum image dimension of interest and certain of said additional cells are included in image elements of larger dimensions.

6. A method as in claim 1, wherein said gray level values are determined on a scale of 0 to 255, and a gray scale value of 153 is correspondingly representative of a pixel which is 60 percent inside a low-reflectance cell and 40 percent outside said cell.

7. A method as in claim 1, wherein step (e) comprises utilizing said step (d) data for successive combinations of three successive pixels along said first axis for deriving normalized cell edge position data for each cell edge lying along said first axis.

8. A method as in claim 1, wherein step (b) comprises determining said pixels-to-cell nominal resolution along an axis which is nominally normal to one of the following:

the bars of a bar code image;

one side of a matrix code.

9. A method as in claim 1, additionally comprising repeating step (d) by determining a gray level value for each of a plurality of successive pixels along a second axis normal to said first axis;

repeating steps (e) and (f) utilizing resulting data; and

utilizing all resulting cell position data in step (g).

10. A method as in claim 1, wherein each pixel of said pixel data image has a basic shape which is one of the following:

square, round, rectangular, hexagonal.

11. A method as in claim 1, additionally comprising the following step between steps (c) and (d):

(x) normalizing gray level values for non-rectangular pixels to enable the gray level value for each said pixel to be correlated to gray level values for other pixels of said plurality of successive pixels.

12. A method as in claim 1, additionally comprising the following step between steps (e) and (f):

(y) repeating step (e) for a second cell coverage pixel which is intersected by a second cell edge crossing of said cell.

13. A method for determining the position of an image cell, represented by cell edges between areas of high and low gray level values in a pixel data image, comprising the steps of:

(a) determining a gray level value for each of a plurality of successive pixels of said image along an axis crossing said image cell, including a cell coverage pixel intersected by a cell edge crossing, said cell coverage pixel having a gray level value representing the position of said cell edge crossing subject to an ambiguity as to the order along said axis of complementary pixel portions of said cell coverage pixel respectively inside and outside of the area of said image cell in said pixel data;

(b) resolving said ambiguity to determine the position of said cell edge crossing along said axis by referring a first sequence of gray level values for a group of successive pixels including said reference pixel to a lookup facility, said lookup facility responsive to different sequences of gray level values to enable resolution of said ambiguity based on the order and relative magnitudes of gray level values of said first sequence; and

(c) deriving cell position data for said image cell using the position of said cell edge crossing as determined in step (b).

14. A method as in claim 13, additionally comprising the following step:

(d) utilizing said cell position data from step (c) to provide a virtual image of said image cell.

15. A method as in claim 14, wherein steps (a), (b) and (c) are repeated for additional image cells of said pixel data image and step (d) provides a virtual image of said pixel data image in its entirety.

16. A method as in claim 15, wherein said image cell first referred to represents a minimum image dimension of interest and certain of said additional image cells are included in image elements of larger dimensions.

17. A method as in claim 13, wherein said gray level values are determined on a scale of 0 to 255, and a gray scale value of 153 is correspondingly representative of a pixel which is 60 percent inside a low-reflectance cell and 40 percent outside said cell.

18. A method as in claim 13, wherein step (b) comprises utilizing said step (a) data for successive combinations of three successive pixels along said first axis for deriving normalized cell edge position data for each cell edge lying along said first axis.

19. A method as in claim 13, wherein each pixel of said pixel data image has a basic shape which is one of the following:

square, round, rectangular, hexagonal.

20. A method as in claim 13, additionally comprising the following step prior to step (a):

(x) normalizing the resolution of said pixel data image by one of the following (i) reducing said resolution to a predetermined pixels-per-cell target resolution, and (ii) if said resolution corresponds to said target resolution, retaining said resolution.

21. A method as in claim 13, additionally comprising the following step between steps (a) and (b):

(y) normalizing gray level values for non-rectangular pixels to enable the gray level value for a pixel to be correlated to gray level values for other pixels of said plurality of successive pixels.

22. A method as in claim 13, additionally comprising the following step between steps (b) and (c):

(z) repeating step (b) for a second cell coverage pixel which is intersected by a second cell edge crossing of said image cell.

24. A method as in claim 14, additionally comprising:

repeating step (a) by determining a gray level value for each of a plurality of successive pixels of said image along a second axis normal to said first axis;

repeating steps (b) and (c) utilizing resulting data; and

utilizing all resulting cell position data in step (d).

23. A method for detecting the position of a cell which is an element of a machine readable dataform, comprising the steps of:

(a) acquiring a pixel data image of said dataform, including said cell;

(b) determining a pixels-to-cell nominal resolution of said pixel data image;

(c) normalizing the resolution of said pixel data image by one of the following (i) reducing said nominal resolution to a pixels-per-cell target resolution, and (ii) if said nominal resolution corresponds to said target resolution, stabilizing said nominal resolution at said target resolution;

(d) determining a gray level value for each of a plurality of successive pixels along a first axis, including cell coverage pixels intersected by cell edge crossings, each said cell coverage pixel having a gray level value representing the position of said cell edge crossing subject to an ambiguity as to the order along said first axis of complementary pixel portions of said cell coverage pixel respectively inside and outside the area of said cell in said pixel data image;

(e) utilizing the order and magnitudes of a sequence of said gray level values for successive groupings of three successive pixels along said first axis to (i) resolve said ambiguity to determine, for each said cell coverage pixel, the order of its said complementary inside and outside portions along said first axis and (ii) to derive cell edge position data;

(f) deriving cell position data for said cell using said step (e) edge position data;

(g) repeating steps (d), (e) and (f) for additional cells of said dataform;

(h) utilizing said cell position data from step (f) to provide a virtual image of said dataform; and

(i) decoding said virtual image to provide output signals representative of data originally encoded in said dataform.