Method for locating the position and orientation of a fiduciary mark

• US 5,642,442 A
• Filed: 11/08/1995
• Issued: 06/24/1997
• Est. Priority Date: 04/10/1995
• 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: Lais, Kenneth A., Recktenwalt, James V., Morton, James S., Bjorner, Johannes A. S.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): KELLEY, CHRISTOPHER S
• Application Number:
  US08/554,321
• Time in Patent Office: 594 Days
• Field of Search: 382/151, 382/227, 382/168, 382/287, 235/462, 235/424
• US Class Current: 382/287
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1429 Identifying or ignoring parts by sensing at different wavelengths
• CPC Class Codes: G06V 30/424 Postal images, e.g. labels or addresses on parcels or postal envelopes

Abstract

Fiduciary mark detection system usable with an over-the-belt optical character recognition (OCR) reader for ascertaining the position and orientation of text within the destination address on parcels moving along a conveyor, comprising charged coupled device (CCD) array, analog-to-digital (A/D) converter, general purpose computer, and software program. Image processing software program comprising projection histograms, convolution filtering, correlation, radial variance, first moments of inertia, edge image analysis, Hough method, detection confidence testing. Orientation defining mark comprising fluorescent ink placed approximately in the center of the destination address block on a parcel is non obstructive of the underlying text and may be affixed to parcel any time prior to scanning. Fiduciary mark comprising two circles of different diameter oriented such that a vector from the center of large circle to center of small circle is oriented in the same direction as underlying text.

Claims

1. A method of analyzing indicia including a first component having a first optical signature and a second component having a second optical signature, comprising the steps of:

(a) reading said indicia;

(b) storing an image of pixel values corresponding to said indicia in a matrix defining a set of coordinate axes;

(c) a first cropping step wherein said image is reduced to a first area, and then within said first area;

(i) conducting a first series of detection attempts of increasing computational complexity until said first component is successfully detected;

(ii) defining a first point associated with said first component;

(iii) setting to zero the pixel values associated with said first component;

(iv) conducting a second series of detection attempts of increasing computational complexity until said second component is successfully detected;

(v) defining a second point associated with said second component; and

(vi) determining the orientation of a vector from said first point to said second point with respect to said first set of coordinate axes.

2. The method of claim 1, wherein step (c) comprises the steps of:

computing a set of projection histograms corresponding to said image, wherein each member of said set of projection histograms corresponds to one axis of said set of coordinate axes;

computing a set of first-filtered projection histograms, wherein each member of said set of first-filtered projection histograms corresponds to a member of said set of projection histograms adjusted to diminish features not corresponding to said indicia;

defining a first set of maximum points, wherein each member of said first set of maximum points corresponds to one axis of said set of coordinate axes, and wherein each member of said first set of maximum points corresponds to the point along its axis having the largest first-filtered projection histogram value;

defining a first set of maximum lines, wherein each member of said first set of maximum lines corresponds to one axis of said set of coordinate axes, and wherein each member of said first set of maximum lines includes the member of said first set of maximum points corresponding to the same axis, and runs parallel to the other axis; and

defining around the intersection of the members of said first set of maximum lines a first predetermined configuration.

3. The method of claim 2, wherein said step of computing a set of first-filtered projection histograms comprises convolution of each member of said set of projection histograms with a first triangular kernel.

4. The method of claim 3, wherein said indicia nominally comprises two non-overlapping circles of different diameter, and said first triangular kernel has a maximum dimension approximately equal to the sum of the diameters of each said circle plus the minimum distance between said circles.

5. The method of claim 1, wherein step (c)(i) comprises:

conducting a first detection attempt;

if said first detection attempt fails, conducting a second detection attempt, said second detection attempt having a greater computational complexity than said first detection attempt; and

if said second detection attempt fails, conducting a third detection attempt, said third detection attempt having a greater computational complexity than said second detection attempt.

6. The method of claim 5, wherein said first detection attempt comprises the steps of:

a second cropping step wherein said image is reduced to a second area;

computing the center of mass of the pixel values within said second area;

defining a first region about said center of mass of the pixel values within said second area;

computing the mass of the pixel values within said first region; and

comparing said mass of the pixels values within said first region to the mass of the pixel values within a nominal first component.

7. The method of claim 6, wherein said first region is approximately circular and larger than said nominal first component.

8. The method of claim 6, wherein said second cropping step comprises the steps of:

computing a set of projection histograms corresponding to said image, wherein each member of said set of projection histograms corresponds to one axis of said set of coordinate axes;

computing a set of second-filtered projection histograms, wherein each member of said set of second-filtered projection histograms corresponds to a member of said set of projection histograms adjusted to diminish features not corresponding to said first component;

defining a second set of maximum points, wherein each member of said second set of maximum points corresponds to one axis of said set of coordinate axes, and wherein each member of said second set of maximum points corresponds to the point along its axis having the largest second-filtered projection histogram value;

defining a second set of maximum lines, wherein each member of said second set of maximum lines corresponds to one axis of said set of coordinate axes, and wherein each member of said second set of maximum lines includes the member of said second set of maximum points corresponding to the same axis, and runs parallel to the other axis; and

defining around the intersection of the members of said second set of maximum lines a second predetermined configuration.

9. The method of claim 7, wherein said step of computing a set of second-filtered projection histograms comprises convolution of each member of said set of projection histograms with a second triangular kernel.

10. The method of claim 8, wherein said nominal first component is approximately circular, and said second triangular kernel has a maximum dimension approximately equal to the diameter said first component.

11. The method of claim 5, wherein said second detection attempt comprises the steps of:

performing a first sequence of correlations, each of said first sequence of correlations being performed between pixels encompassed by a first template corresponding to a nominal first component positioned about one of a first plurality of selected pixels, and the pixel values within an area defined by said first plurality of selected pixels;

defining a second plurality of selected pixels associated with the member of said first plurality of selected pixels with the largest correlation;

performing a second sequence of correlations, each of said second sequence of correlations being performed between pixels encompassed by said first template positioned about one of said second plurality of selected pixels, and the pixels within an area defined by said second plurality of selected pixels;

determining a member of said second plurality of selected pixels with the largest correlation;

computing a first correlation measure corresponding to the correlation associated with said member of said second plurality of selected pixels with the largest correlation; and

comparing said first correlation measure to a threshold value.

12. The method of claim 11, wherein the members of said first plurality of selected pixels are spaced a first distance apart from each other, and the members of said second plurality of selected pixels are spaced a second distance apart from each another, and wherein said second distance is less than said first distance.

13. The method of claim 5, wherein said third detection attempts comprises the steps of:

defining a first candidate set of pixels; and

then

computing the radial variance of the pixel values associated with said first candidate;

setting to zero all pixel values associated with said first candidate;

defining a second candidate set of pixels;

computing the radial variance of the pixel values associated with said second candidate;

defining a first preferred candidate to be the one among said first and second candidates with a radial variance more nearly approximating the radial variance of a nominal first component;

computing a first variance measure corresponding to the radial variance associated with said first preferred candidate; and

comparing said first variance measure to a threshold value.

14. The method of claim 5, further comprising a fourth detection attempt comprising the steps of:

determining a first set of edge pixel groups, wherein each member of said first set of edge pixel groups comprises pixels forming the edge of a contiguous formation of pixels within said first area; and

comparing members of said first set of edge pixel groups to the edge pixels of a nominal first component.

15. The method of claim 1, wherein step (c)(iv) comprises the steps of:

conducting a first detection attempt;

if said first detection attempt fails, conducting a second detection attempt said second detection attempt having a greater computational complexity than said first detection attempt; and

if said second detection attempt fails, conducting a third detection attempt, said third detection attempt having a greater computational complexity than said second detection attempt.

16. The method of claim 15, wherein said first detection attempt comprises the steps of:

a second cropping step wherein said image is reduced to a second area;

computing the center of mass of the pixel values within said second area;

defining a second region about said center of mass of the pixel values within said second area;

computing the mass of the pixel values within said second region; and

comparing said mass of the pixel values within said second region to the mass of the pixel values within a nominal second component.

17. The method of claim 16, wherein said second cropping step comprises the steps of:

computing a set of projection histograms corresponding to said image, wherein each member of said set of projection histograms corresponds to one axis of said set of coordinate axes;

computing a set of third-filtered projection histograms, wherein each member of said set of third-filtered projection histograms corresponds to a member of said set of projection histograms adjusted to diminish features not corresponding to said second component;

defining a third set of maximum points, wherein each member of said third set of maximum points corresponds to one axis of said set of coordinate axes, and wherein each member of said third set of maximum points corresponds to the point along its axis having the largest third-filtered projection histogram value;

defining a third set of maximum lines, wherein each member of said third set of maximum lines corresponds to one axis of said set of coordinate axes, and wherein each member of said third set of maximum lines includes the member of said third set of maximum points corresponding to the same axis, and runs parallel to the other axis; and

defining around the intersection of the members of said third set of maximum lines a third predetermined configuration.

18. The method of claim 17, wherein said step of computing a set of third-filtered projection histogram comprises convolution of each member of said set of projection histograms with a third triangular kernel.

19. The method of claim 18, wherein said nominal second component is approximately circular, and said third triangular kernel has a maximum dimension approximately equal to the diameter said second component.

20. The method of claim 19, wherein said nominal first component is approximately circular and larger than said second component, and wherein said second region is approximately circular and larger than said nominal second component, and smaller than said nominal first component.

21. The method of claim 15, wherein said second detection attempt comprises the steps of:

performing a third sequence of correlations, each of said third sequence of correlations being performed between pixels encompassed by a second template corresponding to said nominal second component positioned about one of a third plurality of selected pixels and the pixel values within an area defined by said third plurality of selected pixels;

defining a fourth plurality of selected pixels associated with the member of said third plurality of selected pixels with the largest correlation;

performing a fourth sequence of correlations, each of said fourth sequence of correlations being performed between pixels encompassed by said second template positioned about one of said fourth plurality of selected pixels, and the pixel within an area defined by said fourth plurality of selected pixels;

determining the member of said fourth plurality of selected pixels with the largest correlation;

computing a second correlation measure corresponding to the correlation associated with said member of said fourth plurality of selected pixels with the largest correlation; and

comparing said second correlation measure to a threshold value.

22. The method of claim 21, wherein the members of said third plurality of selected pixels are spaced a third distance apart from each other, and the members of said fourth plurality of selected pixels are spaced a fourth distance apart from each another, and wherein said fourth distance is less than said third distance.

23. The method of claim 15, wherein said third detection attempt comprises the steps of:

defining a third candidate set of pixels;

computing the radial variance of the pixel values associated with said third candidate;

setting to zero all pixel values associated with said third candidate;

defining a fourth candidate set of pixels;

computing the radial variance of the pixel values associated with said fourth candidate;

defining a second preferred candidate to be the one among said third and fourth candidates with a radial variance more nearly approximating the radial variance of said nominal second component;

computing a second variance measure corresponding to the radial variance associated with said second preferred candidate; and

comparing said second variance measure to a threshold value.

24. The method of claim 15, further comprising a fourth detection attempt comprising the steps of:

determining a second set of edge pixel groups, wherein each member of said second set of edge pixel groups comprises pixels forming the edge of a contiguous formation of pixels within said first area; and

comparing members of said second set of edge pixel groups to the edge pixels of a nominal second component.

25. The method of claim 1, further comprising the step of computing a net confidence value for the likelihood that an expected indicia has been detected.

26. The method of claim 25, wherein said step of computing a net confidence value comprises one or more of the following steps:

computing a first confidence value by comparing the distance between said first point and said second point to a distance associated with said nominal indicia;

computing a second confidence value by comparing a measure of said first detection step to a first nominal value associated with said nominal first component;

or

computing a third confidence value by comparing a measure of said second detection step to a second nominal value associated with said nominal second component.

27. The method of claim 26, further comprising the step of computing a net confidence value based on a combination of said first, second and third confidence values.

28. The method of claim 27, wherein said combination is computed by taking the minimum of said first, second and third confidence values.

29. The method of claim 1, wherein said components are approximately circular images of different diameter.

30. The method of claim 1, wherein said step (a) comprises capturing an image of said indicia in a CCD array.

31. The method of claim 1, wherein said step (b) comprises storing said matrix in a computer memory.

32. The method of claim 1, wherein said indicia comprises fluorescent ink.