Multi-resolution label locator

• US 6,728,391 B1
• Filed: 12/03/1999
• Issued: 04/27/2004
• Est. Priority Date: 12/03/1999
• 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: Skinger, Gregory P., Wang, Jason, Wu, Jianxin, Recktenwalt, James
• Primary Examiner(s): Patel, Jayanti K.
• Assistant Examiner(s): CARTER, AARON W
• Application Number:
  US09/454,090
• Time in Patent Office: 1,607 Days
• Field of Search: 382/101, 382/199, 382/102, 382/256, 382/224, 382/217, 382/282, 382/306, 382/173-180, 382/299, 209/583, 209/584, 209/900
• US Class Current: 382/101
• CPC Class Codes: B07C 1/00 Measures preceding sorting according to destination
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/147 Determination of region of interest
• CPC Class Codes: G06V 30/18095 Summing image-intensity values; Projection and histogram analysis
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• CPC Class Codes: G06V 30/424 Postal images, e.g. labels or addresses on parcels or postal envelopes
• CPC Class Codes: Y10S 209/90 Sorting flat-type mail

Abstract

A multi-resolution label locator system divides an input image into a plurality of multi-pixel cells. The multi-resolution label locator system then creates a decimated image or low resolution image corresponding to the input image. The decimated image includes a common-characteristic value that corresponds to a multi-pixel cell of the input image. The multi-resolution label locator system identifies one or more areas within the decimated image that have characteristics corresponding to the characteristics of interest. While generating the decimated image, the multi-resolution label locator system simultaneously creates an edge-occurrence image that corresponds to the input image. The edge-occurrence image includes an edge value that corresponds to each cell of the input image. Each edge value represents the number of occurrences of an edge within the pixels of a corresponding cell of the input image. The multi-resolution label locator system identifies one or more candidate areas within the input image that have decimated-image characteristics and edge-occurrence image characteristics corresponding to the characteristics of interest. The multi-resolution label locator system then classifies the candidate areas according to the likelihood of the input image containing indicia having the characteristics of interest. Lastly, the multi-resolution label locator system compiles a list of one or more candidate areas that most likely contain indicia having the characteristics of interest.

Claims

1. A method for locating indicia having characteristics of interest on a substrate, comprising the steps of:

obtaining a video signal defined by a plurality of pixels comprising an input image of the substrate;

dividing the input image into a plurality multi-pixel cells;

creating a decimated image corresponding to the input image comprising a common-characteristic value corresponding to each cell of the input image, each common-characteristic value representing a number of the pixels within the corresponding cell, wherein creating the decimated image includes the steps of,

computing a histogram of pixel values occurring within the cell,

selecting from the histogram a mode value corresponding to the pixel value most frequently occurring within the cell, and

setting the common-characteristic value in the decimated image for the cell to the mode value;

identifying one or more areas within the decimated image having characteristics corresponding to the characteristics of interest;

creating an edge-occurrence image corresponding to the input image comprising an edge value corresponding to each cell of the input image, each edge value representing the number of occurrences of a predetermined edge within the pixels of the corresponding cell;

identifying one or more candidate areas within the input image having decimated-image characteristics and edge-occurrence image characteristics corresponding to the characteristics of interest;

classifying the candidate areas according to likelihood of containing indicia having the characteristics of interest; and

compiling a prioritized list of one or more candidate areas that most likely contain indicia having the characteristics of interest.

2. The method of claim 1, wherein the step of identifying one or more candidate areas within the decimated image having characteristics corresponding to the expected characteristics of the indicia comprises the steps of:

computing a common-characteristic histogram corresponding to the decimated image; and

smoothing the common-characteristic histogram with a low-pass filter and an adaptive-moving-window filter;

selecting one or more peak values from the filtered common characteristic histogram;

isolating a peak region around each peak value by identifying upper and lower bounding valley values;

creating a segmented image by mapping the pixels within each peak region into a blank image corresponding the decimated image; and

identifying one or more connected components within the segmented image.

3. The method of claim 1, wherein the step of creating the edge-occurrence image comprises the steps of, for each cell:

binarizing the pixel values within the cell;

identifying transitions in expected orientations among the binarized pixel values within the cell;

computing a totalized transition value for the cell based on the transitions; and

setting the edge value for the cell to the totalized transition value for the pixels within the cell.

4. The method of claim 3, wherein the step of binarizing the pixel values within the cell comprises the step of applying an adaptive binarizing technique to the pixel values within the cell to select a threshold for binarizing the pixel values based on identified background pixel values.

5. The method of claim 3, wherein the step of identifying transitions in expected orientations among the binarized pixel values within the cell comprises the step of comparing the pixel values within the cell to a plurality of templates that define pixel patterns that are among the characteristics of interest.

6. The method of claim 5, wherein the step of identifying transitions in expected orientations among the binarized pixel values within the cell comprises the steps of:

defining a plurality of counters associated with each of a plurality of orientations; and

for each template

comparing instances of the template to portions of the cell having the same size as the template such that each pixel of the cell is compared to at least one instance of the template;

identifying one or more matching pixel patterns within the cell that correspond to a pixel pattern defined by the template;

identifying an orientation associated with the pixel pattern; and

incrementing one or more of the counters in response to the occurrence of each matching pixel pattern.

7. The method of claim 6, wherein the step of computing a totalized transition value for a cell comprises the step of:

applying a totalization formula that filters the counter values to increment the totalized transition value in response to the presence of text within the cell while avoiding incrementing the totalized transition value in response to the presence of one of a barcode and extraneous markings within the cell.

8. The method of claim 2, wherein the step of identifying one or more candidate areas within the input image having decimated-image characteristics and edge-occurrence image characteristics corresponding to the characteristics of interest further comprises the steps of:

computing a bounding window about each connected component within the segmented image; and

for each bounding window

computing one or more window feature values,

computing one or more feature values corresponding to the cells within the bounding window, and

assembling a feature vector including the window feature values and the feature values for cells within the bounding window.

9. The method of claim 8, wherein the window feature values are selected from the group including:

a normalized height representing a ratio of a height defined by the bounding window to a height defined by the segmented image;

a normalized width representing a ratio of a width defined by the bounding window to a width defined by the segmented image;

a normalized area representing a ratio of an area defined by the bounding window to an area defined by the segmented image; and

an aspect ratio representing a ratio of the width defined by the bounding window to the height defined by the bounding window.

10. The method of claim 8, wherein the feature values are selected from the group including:

a normalized edge-occurrence intensity representing a ratio of the sum of edge values for cells within the bounding window to a total number of cells within the bounding window; and

a normalized transition intensity representing a ratio of the sum of totalized transition values for cells within the bounding window to an area defined by the bounding window.

11. The method of claim 10, further comprising the step of zeroing totalized transition values for cells within the bounding window below a predefined threshold value to remove noise when computing the normalized transition intensity.

12. The method of claim 8, further comprising the step of preclassifying the candidate areas by applying a qualification selected from the group including:

eliminating one or more candidate areas having a corresponding bounding window defining an area below a predefined minimum threshold value;

eliminating one or more candidate areas having a corresponding bounding window defining an area above a predefined maximum threshold value; and

cropping one or more candidate areas to correspond to a bounding window having a predefined size centered about a center of mass computed for the feature values of the corresponding candidate area.

13. The method of claim 8, wherein the step of classifying the candidate areas according to likelihood of containing indicia having the characteristics of interest further comprises the step of listing the candidate areas by comparing their respective feature vectors.

14. The method of claim 13, wherein the step of listing the candidate areas comprises the steps of, for one or more feature vectors:

computing a first decision value corresponding to one or more of the window feature values by comparing the window feature value to an expected value of the window feature value, the expected value of the window feature value being among the characteristics of interest; and

computing a second decision value corresponding to one or more of the cell feature values by comparing the cell feature value to an expected value of the cell feature value, the expected value of the cell feature value being among the characteristics of interest.

15. The method of claim 14, wherein the step of listing the candidate areas comprises the steps of:

defining a decision space comprising a plurality of decision subspaces;

listing the decision subspaces; and

mapping the feature vectors to the decision subspaces based on the relative values of the window and cell feature values of the feature vectors.

16. A method for locating indicia having characteristics of interest on a substrate, comprising the steps of:

obtaining a video signal defined by a plurality of pixels comprising an input image of the substrate;

dividing the input image into a plurality multi-pixel cells;

creating a decimated image corresponding to the input image comprising a common-characteristic value corresponding to each cell of the input image, each common-characteristic value representing a number of the pixels within the corresponding cell;

identifying one or more areas within the decimated image having characteristics corresponding to the characteristics of interest;

creating an edge-occurrence image corresponding to the input image comprising an edge value corresponding to each cell of the input image, each edge value representing the number of occurrences of a predetermined edge within the pixels of the corresponding cell, wherein creating the edge-occurrence image includes the steps of,

binarizing the pixel values within the cell,

identifying transitions in expected orientations among the binarized pixel values within the cell,

computing a totalized transition value for the cell based on the transitions, and

setting the edge value for the cell to the totalized transition value for the pixels within the cell;

identifying one or more candidate areas within the input image having decimated-image characteristics and edge-occurrence image characteristics corresponding to the characteristics of interest;

classifying the candidate areas according to likelihood of containing indicia having the characteristics of interest; and

compiling a prioritized list of one or more candidate areas that most likely contain indicia having the characteristics of interest.

17. The method of claim 16, wherein the step of creating the decimated image comprises the steps of, for each cell:

computing a histogram of pixel values occurring within the cell;

selecting from the histogram a mode value corresponding to the pixel value most frequently occurring within the cell; and

setting the common-characteristic value in the decimated image for the cell to the mode value.

18. The method of claim 16, wherein the step of identifying one or more candidate areas within the decimated image having characteristics corresponding to the expected characteristics of the indicia comprises the steps of:

computing a common-characteristic histogram corresponding to the decimated image; and

smoothing the common-characteristic histogram with a low-pass filter and an adaptive-moving-window filter;

selecting one or more peak values from the filtered common characteristic histogram;

isolating a peak region around each peak value by identifying upper and lower bounding valley values;

creating a segmented image by mapping the pixels within each peak region into a blank image corresponding the decimated image; and

identifying one or more connected components within the segmented image.

19. The method of claim 16, wherein the step of binarizing the pixel values within the cell comprises the step of applying an adaptive binarizing technique to the pixel values within the cell to select a threshold for binarizing the pixel values based on identified background pixel values.

20. The method of claim 16, wherein the step of identifying transitions in expected orientations among the binarized pixel values within the cell comprises the step of comparing the pixel values within the cell to a plurality of templates that define pixel patterns that are among the characteristics of interest.

21. The method of claim 20, wherein the step of identifying transitions in expected orientations among the binarized pixel values within the cell comprises the steps of:

defining a plurality of counters associated with each of a plurality of orientations; and

for each template

comparing instances of the template to portions of the cell having the same size as the template such that each pixel of the cell is compared to at least one instance of the template;

identifying one or more matching pixel patterns within the cell that correspond to a pixel pattern defined by the template;

identifying an orientation associated with the pixel pattern; and

incrementing one or more of the counters in response to the occurrence of each matching pixel pattern.

22. The method of claim 16, wherein the step of computing a totalized transition value for a cell comprises the step of:

applying a totalization formula that filters the counter values to increment the totalized transition value in response to the presence of text within the cell while avoiding incrementing the totalized transition value in response to the presence of one of a barcode and extraneous markings within the cell.

23. The method of claim 18, wherein the step of identifying one or more candidate areas within the input image having decimated-image characteristics and edge-occurrence image characteristics corresponding to the characteristics of interest further comprises the steps of:

computing a bounding window about each connected component within the segmented image; and

for each bounding window

computing one or more window feature values,

computing one or more feature values corresponding to the cells within the bounding window, and

assembling a feature vector including the window feature values and the feature values for cells within the bounding window.

24. The method of claim 23, wherein the window feature values are selected from the group including:

a normalized height representing a ratio of a height defined by the bounding window to a height defined by the segmented image;

a normalized width representing a ratio of a width defined by the bounding window to a width defined by the segmented image;

a normalized area representing a ratio of an area defined by the bounding window to an area defined by the segmented image; and

an aspect ratio representing a ratio of the width defined by the bounding window to the height defined by the bounding window.

25. The method of claim 23, wherein the feature values are selected from the group including:

a normalized edge-occurrence intensity representing a ratio of the sum of edge values for cells within the bounding window to a total number of cells within the bounding window; and

a normalized transition intensity representing a ratio of the sum of totalized transition values for cells within the bounding window to an area defined by the bounding window.

26. The method of claim 23, further comprising the step of preclassifying the candidate areas by applying a qualification selected from the group including:

eliminating one or more candidate areas having a corresponding bounding window defining an area below a predefined minimum threshold value;

eliminating one or more candidate areas having a corresponding bounding window defining an area above a predefined maximum threshold value; and

cropping one or more candidate areas to correspond to a bounding window having a predefined size centered about a center of mass computed for the feature values of the corresponding candidate area.

27. The method of claim 23, wherein the step of classifying the candidate areas according to likelihood of containing indicia having the characteristics of interest further comprises the step of listing the candidate areas by comparing their respective feature vectors.

28. The method of claim 27, wherein the step of listing the candidate areas comprises the steps of, for one or more feature vectors:

computing a first decision value corresponding to one or more of the window feature values by comparing the window feature value to an expected value of the window feature value, the expected value of the window feature value being among the characteristics of interest; and

computing a second decision value corresponding to one or more of the cell feature values by comparing the cell feature value to an expected value of the cell feature value, the expected value of the cell feature value being among the characteristics of interest.

29. The method of claim 27, wherein the step of listing the candidate areas comprises the steps of:

defining a decision space comprising a plurality of decision subspaces;

listing the decision subspaces; and

mapping the feature vectors to the decision subspaces based on the relative values of the window and cell feature values of the feature vectors.