Method and apparatus for decoding two-dimensional symbols in the spatial domain

• US 6,094,509 A
• Filed: 08/12/1997
• Issued: 07/25/2000
• Est. Priority Date: 06/07/1994
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Zheng, Joe, Lei, Ming
• Primary Examiner(s): Chang, Jon
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/909,574
• Time in Patent Office: 1,078 Days
• Field of Search: 382/100, 382/101, 382/139, 382/140, 382/183, 382/209, 382/217, 382/218, 382/216, 382/313, 382/203, 382/278, 382/287, 235/462, 235/464, 235/494-495, 379/910
• US Class Current: 382/218
• 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/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06K 7/1456 determining the orientation of the optical code with respect to the reader and correcting therefore
• CPC Class Codes: Y10S 379/91 Bar code or optical character reader with telephone

Abstract

A method and system for decoding a two-dimensional optical symbol in the spatial domain. The system determines the orientation of an imaged symbol in the spatial domain by using a template to derive a correlation coefficient between radially adjacent signals at a given angle of the template and comparing the correlation coefficients as the template is rotated with respect to the image. The angle of the highest correlation coefficient corresponds to the orientation of a set of symbol axes which include contiguous elements whose centers are collinear. The system then locates each individual information-encoded element of the symbol by using segments of the symbol defined by the axes, first adjusting for each segment the axis position and element size for subsequent determination of the location of all elements for decoding. The system is disclosed as applied to a symbol constructed as a matrix of hexagonal information-encoding elements arranged in a square, with, at its center, an acquisition target consisting of six concentric rings of alternating light and dark reflectivity.

Claims

1. A method of finding collinear elements in a graphic image comprising an array of said elements, regardless of the pattern of gray scale intensities of said collinear elements, comprising the steps of:

developing a sampling template for plotting data acquisition locations in said image, said template having two sequences of data acquisition points, each sequence spaced along one of two parallel lines spaced apart by a distance shorter than a width of each of said elements measured perpendicular to the parallel lines, the sequences together defining pairs of points having a first point positioned on one of the parallel lines across from a second point of said pair on the other parallel line;

positioning said template on said image data;

acquiring gray scale intensities at said data acquisition locations indicated by said template;

comparing gray scale intensities corresponding to the first points of said pairs to gray scale intensities corresponding to respective second points of said pairs to determine a correlation factor between said sequences of said first points and said second points, representing a measure of the pair-by-pair difference in gray scale value between the two sequences of points;

moving said sampling template into varying orientations with respect to said image and determining said correlation factor for each position of said template; and

identifying one or more sets of collinear elements in said image by finding one or more template positions associated with characteristic values of said correlation factor.

2. The method of claim 1 wherein said series of pairs of points extend radially from a template center point;

wherein said step of positioning said template comprises positioning said template center point at a center point of said image; and

wherein said step of moving said template comprises rotating said template about said template center point.

3. An image processor for locating in an image one or more sets of contiguous elements whose centers are collinear, comprising:

a sampling template for plotting data acquisition locations in said image, said template having two sequences of data acquisition points, each sequence spaced along one of two parallel lines spaced apart by a distance shorter than a width of each of said elements measured perpendicular to the parallel lines, the sequences together defining pairs of points having a first point positioned on one of the parallel lines across from a second point of said pair on the other parallel line;

a positioner for positioning said template on said image and for moving said sampling template into varying orientations with respect to said image;

a comparator for comparing gray scale intensities of the first points of said pairs to gray scale intensities of respective second points of said pairs to determine a correlation factor between said sequences of said first points and said second points, representing a measure of the pair-by-pair difference in gray scale value between the two sequences of points; and

a finder for identifying said one or more set of collinear elements by finding one or more template positions associated with characteristic values of said correlation factor.

4. The image processor of claim 3, wherein said series of pairs of points extend radially from a template center point;

and wherein said positioner positions said template center point at a center point of said image and moves said template by rotating said template about said template center point.

5. A method of determining the orientation of a two-dimensional, optically readable symbol of the type having elements of at least two different reflectivities, and at least one radial set of contiguous elements whose centers lie along a line passing through an origin point of said symbol, comprising the steps of:

deriving a multiple-row image including said symbol from a pixel matrix and storing said image;

developing a sampling template for plotting data acquisition locations in said image, said template having two sequences of data acquisition points, each sequence spaced along one of two parallel lines spaced apart by a distance shorter than a width of each of said elements, the sequences together defining pairs of points having a first point positioned on one of the parallel lines across from a second point of said pair on the other parallel line;

comparing gray scale intensities at the first points of said pairs to gray scale intensities at the second points of said pairs to determine a correlation factor between said sequences of said first points and said second points, representing a measure of the pair-by-pair difference in gray scale value between the two sequences of points;

rotating said sampling template in increments about said origin and repeatedly determining said correlation factor for each rotational position of said template; and

identifying said radial set of contiguous elements by finding the rotational position associated with characteristic values of said correlation factor.

6. The method of claim 5, wherein said step of identifying said radial set of contiguous elements further comprises forming a one-dimensional signal by plotting correlation factor against rotational position, and filtering said signal.

7. The method of claim 5, further comprising locating said origin point of said symbol by the steps of:

locating a bounded element demonstrating symmetry along at least two directions; and

determining a center of said bounded element.

8. The method of claim 5, wherein said symbol comprises a plurality of polygonal information encoding elements arranged in a matrix.

9. The method of claim 5, wherein said step of finding the position associated with characteristic correlation factor values comprises forming an orientation signal comprising a sequence of said correlation factors for each position of said template, and comparing the height of peaks of said signal to find the highest peak.

10. The method of claim 9, further comprising the step of low-pass filtering said peaks of said orientation signal.

11. A method of determining the orientation of a two dimensional, optically readable symbol of the type having a plurality of radial sets of contiguous elements whose centers lie along axes passing through an origin point of said symbol and spaced evenly around said origin, said elements being one of at least two different reflectivities, comprising the steps of:

deriving a multiple-row image including said symbol from a pixel matrix and storing said image;

developing a sampling template for plotting data acquisition locations in said image, said template having a plurality of sets of data acquisition locations, each of said sets including two sequences of data acquisition points, each sequence spaced along one of two parallel lines spaced apart by a distance shorter than a width of each of said elements, the sequences together defining pairs of points having a first point positioned on one of the parallel lines across from a second point of said pair on the other parallel line, the number and spacing of said sets being equal to the number and spacing of said symbol axes;

comparing gray scale intensities at the first points of said pairs to gray scale intensities at the second points of said pairs for all of said sets, to determine a correlation factor between said sequences of said first points and said second points, representing a measure of the pair-by-pair difference in gray scale value between the sequences of points, for all of said sets;

rotating said sampling template in increments about said origin and repeatedly determining said correlation factor for each rotational position of said template; and

identifying the position of said axes of said radial sets of contiguous elements by finding the rotational position of said template associated with the highest correlation factor.

12. The method of claim 11, wherein said symbol comprises a plurality of polygonal information encoding elements arranged in a matrix.

13. The method of claim 11, wherein each axis of said symbol has associated therewith a unique pattern of orientation elements, and further comprising identifying each of said axes by determining which pattern of orientation elements is associated with said axis.

14. The method of claim 13, further comprising a method of individually adjusting the positions of said axes comprising the steps of:

selecting a plurality of combinations of axis directions and element sizes as trial parameters;

for each pair of trial parameters in turn, determining the locations in said image at which the centers of elements would occur along said axis;

determining whether centers of elements actually occur at said locations; and

selecting the pair of trial parameters which best locate actual hexagon centers.

15. The method of claim 14, wherein said step of determining the locations in said image at which the centers of elements would occur along said axis includes determining the locations at which the centers of elements would occur adjacent to said axis.

16. The method of claim 14, wherein the method of individually adjusting the positions of said axes further comprises determining whether each pair of trial parameters predicts the colors of said unique pattern of orientation elements.

17. The method of claim 16, further comprising the step of calculating the positions of the centers of elements in an area adjacent to each of said axes using the element size individually adjusted for each of said axes.

18. The method of claim 17, wherein said symbol comprises a plurality of polygonal information encoding elements arranged in a matrix.

19. The method of claim 14, wherein said step of determining whether centers of elements actually occur at said locations comprises determining for each of said locations whether neighboring pixels of said image are the same color as the color at said location.

20. A method of reading an optically encoded, two dimensional symbol of the type having elements of at least two different reflectivities, a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity completely surrounded by an area of a second reflectivity, and a plurality of radial sets of contiguous elements whose centers lie along axes passing through an origin point at the center of said key element, said axes being spaced evenly around said origin and each axis of said symbol having associated therewith a unique pattern of orientation elements, comprising the steps of:

deriving a multiple-row image including said symbol from a pixel matrix and storing said image;

locating said key element by;

scanning said stored image along a scanning direction to detect a candidate bounded element demonstrating symmetry along said scanning direction; and

determining whether said candidate bounded element is symmetric along a second direction;

locating said origin point by examining gray scale intensifies within said key element to locate a center of said key element;

determining the approximate size of the elements of said symbol by averaging a plurality of different diameters of said key element;

locating the position of said axes of said radial sets of contiguous elements by

developing a sampling template for plotting data acquisition locations in said image, said template having a plurality of sets of data acquisition locations, each of said sets including two sequences of data acquisition points, each sequence spaced along one of two parallel lines spaced apart by a distance shorter than a width of each of said elements, the sequences together defining pairs of points having a first point positioned on one of the parallel lines across from a second point of said pair on the other parallel line, the number and spacing of said sets being equal to the number and spacing of said symbol axes;

comparing gray scale intensities at the first points of said pairs to gray scale intensities at the second points of said pairs for all of said sets, to determine a correlation factor between said sequences of said first points and said second points, representing a measure of the pair-by-pair difference in gray scale value between the sequences of points, for all of said sets;

rotating said sampling template in increments about said origin and repeatedly determining said correlation factor for each position of said template; and

finding the position of said template associated with the highest correlation factor;

identifying each of said axes by determining which pattern of orientation elements is associated with said axis;

determining the center coordinates of each element of said symbol using the coordinates of said origin point, the orientation of said axes, and the estimated size of said elements; and

determining the reflectivity of each of said elements by analyzing gray scale intensity near its center.

21. A system for determining the orientation of an optically readable, two dimensional symbol of the type having elements of at least two different reflectivities, and a plurality of radial sets of contiguous elements whose centers lie along axes passing through an origin point of said symbol and spaced evenly around said origin, comprising:

a light source;

a detector comprising an array of pixels positioned to receive light from said light source reflected by said symbol;

a read-out circuit connected to obtain data signals from said pixels and to form in a memory device an image including said symbol; and

a processor configured to locate the position of said axes of said radial sets of contiguous elements by;

developing a sampling template for plotting data acquisition locations in said image, said template having a plurality of sets of data acquisition locations, each of said sets including two sequences of data acquisition points, each sequence spaced along one of two parallel lines spaced apart by a distance shorter than a width of each of said elements, the sequences together defining pairs of points having a first point positioned on one of the parallel lines across from a second point of said pair on the other parallel line, the number and spacing of said sets being equal to the number and spacing of said symbol axes;

comparing gray scale intensities at the first points of said pairs to gray scale intensities at the second points of said pairs for all of said sets, to determine a correlation factor between said sequences of said first points and said second points, representing a measure of the pair-by-pair difference in gray scale value between the sequences of points, for all of said sets;

rotating said sampling template in increments about said origin and repeatedly determining said correlation factor for each position of said template; and

finding the position of said template associated with the highest correlation factor.

22. The system of claim 21, wherein said symbol comprises a plurality of polygonal information encoding elements arranged in a matrix.

23. A system for reading an optically encoded, two dimensional symbol of the type having elements of at least two different reflectivities, a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity completely surrounded by an area of a second reflectivity, and a plurality of radial sets of contiguous elements whose centers lie along axes passing through an origin point at the center of said key element, said axes being spaced evenly around said origin and each axis of said symbol having associated therewith a unique pattern of orientation elements, comprising:

a light source;

a detector comprising an array of pixels positioned to receive light from said light source reflected by said symbol;

a read-out circuit connected to obtain data signals from said pixels and to form in a memory device an image including said symbol; and

a processor configured to locate said key element, locate the position of said axes of said radial sets of contiguous elements, and locate each of said elements by;

deriving a multiple-row image including said symbol from a pixel matrix and storing said image;

locating said key element by;

scanning said stored image along a scanning direction to detect a candidate bounded element demonstrating symmetry along said scanning direction; and

determining whether said candidate bounded element is symmetric along a second direction;

locating said origin point by examining gray scale intensities within said key element to locate a center of said key element;

determining the approximate size of the elements of said symbol by averaging a plurality of different diameters of said key element;

locating the position of said axes of said radial sets of contiguous elements by

developing a sampling template for plotting data acquisition locations in said image, said template having a plurality of sets of data acquisition locations, each of said sets including two sequences of data acquisition points, each sequence spaced along one of two parallel lines spaced apart by a distance shorter than a width of each of said elements, the sequences together defining pairs of points having a first point positioned on one of the parallel lines across from a second point of said pair on the other parallel line, the number and spacing of said sets being equal to the number and spacing of said symbol axes;

comparing gray scale intensities at the first points of said pairs to gray scale intensities at the second points of said pairs for all of said sets, to determine a correlation factor between said sequences of said first points and said second points, representing a measure of the pair-by-pair difference in gray scale value between the sequences of points, for all of said sets;

rotating said sampling template in increments about said origin and repeatedly determining said correlation factor for each position of said template; and

finding the position of said template associated with the highest correlation factor;

identifying each of said axes by determining which pattern of orientation elements is associated with said axis;

determining the center coordinates of each element of said symbol using the coordinates of said origin point, the orientation of said axes, and the estimated size of said elements; and

determining the reflectivity of each of said elements by analyzing gray scale intensity near its center.

24. The system of claim 23, wherein said symbol comprises a plurality of polygonal information encoding elements arranged in a matrix.

25. A method of finding collinear elements in a graphic image comprising an array of said elements, regardless of the pattern of gray scale intensities of said collinear elements, comprising the steps of:

acquiring gray scale intensities of said image at two sequences of data acquisition points, each sequence spaced along one of two parallel lines spaced apart by a distance shorter than a width of each of said elements measured perpendicular to the parallel lines, the sequences together defining pairs of points having a first point positioned on one of the parallel lines across from a second point of said pair on the other parallel line;

comparing gray scale intensities corresponding to the first points of said pairs to gray scale intensities corresponding to respective second points of said pairs to determine a correlation factor between said sequences of said first points and said second points, representing a measure of the pair-by-pair difference in gray scale value between the two sequences of points;

moving said parallel lines defining data acquisition points into varying orientations with respect to said image and determining said correlation factor for each orientation of said parallel lines; and

identifying one or more sets of collinear elements in said image by finding one or more of said positions of said parallel lines associated with characteristic values of said correlation factor.