Methods and apparatus for locating an object in an image

• US 8,326,037 B1
• Filed: 11/23/2005
• Issued: 12/04/2012
• Est. Priority Date: 11/23/2005
• Status: Active Grant

• Current Assignee: Matrox Electronic Systems Ltd.
• Original Assignee: Matrox Electronic Systems Ltd.
• Inventors: Simon, Christian, Abitz, Jon, Meddah, Djamel
• Primary Examiner(s): Bhatnagar, Anand
• Assistant Examiner(s): BLOOM, NATHAN J
• Application Number:
  US11/286,710
• Time in Patent Office: 2,568 Days
• Field of Search: 23546201-46249
• US Class Current: 382/181
• CPC Class Codes: G06K 7/1443 locating of the code in an image
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/146 Aligning or centring of the image pick-up or image-field
• CPC Class Codes: G06V 30/18095 Summing image-intensity values; Projection and histogram analysis

Abstract

A method for locating an object in an image is provided for an object that exhibits, in at least one direction, foreground pixel runs and background pixel runs consistent with at least characteristic of the object. In one embodiment, the method includes the acts of defining a plurality of regions in the image, associating a metric with each of the regions, finding pixel runs in the image, and identifying at least one pixel run in one of the plurality of regions where the at least one pixel run is consistent with the at least one characteristic of the object. According to one embodiment, the method includes the acts of adjusting the metric associated with the region where the at least one pixel run is identified and identifying, from among the plurality of regions, a region where the object is located based on a metric determined for a plurality of regions. In various embodiments, the object includes a repetitive pattern such as those found in barcodes and character strings.

Claims

1. A non-transitory computer readable storage medium encoded with a program for execution on a processor, the program when executed on the processor performing a method for locating a barcode in an image, the barcode having at least one characteristic, the method comprising acts of:

a. Defining a plurality of regions in the image;

b. Associating a vote accumulator with each of the regions;

c. Finding pixel runs in the image, wherein a pixel run includes a group of adjacent pixels having a like binary value that are arranged linearly in a first direction in the image, the pixel run bounded linearly in the first direction by at least one pixel having a binary value that differs from the like binary value;

d. Identifying, in one of the plurality of regions, two consecutive pixel runs comprising a first pixel run of pixels in the first direction and having a first binary value and a second pixel run of pixels in the first direction and having the first binary value, the two consecutive pixel runs separated in the first direction by a third pixel run of pixels in the first direction and having a second binary value, wherein the first pixel run, the second pixel run and the third pixel run are in a line, wherein each of the first pixel run, the second pixel run and the third pixel run has a run length that is consistent with the at least one characteristic;

e. Adjusting the vote accumulator associated with the region where the two consecutive pixel runs are identified; and

f. Identifying from among the plurality of regions, a region where the barcode is located based on the vote accumulators.

2. The non-transitory computer readable storage medium of claim 1, wherein the method further comprises acts of:

locating at least one pixel run adjacent to one of the first pixel run and the second pixel run; and

determining whether the at least one adjacent pixel run includes a run length that is similar to the run length of the one of the first pixel run and the second pixel run to which it is adjacent.

3. The non-transitory computer readable storage medium of claim 2, further comprising locating the at least one adjacent pixel run in one of a preceding row and a subsequent row.

4. The non-transitory computer readable storage medium of claim 1, wherein the act of adjusting the vote accumulator further comprises acts of:

determining a vote weight based at least in part on the identification of the two consecutive pixel runs; and

adjusting the vote accumulator by an amount determined by the vote weight.

5. The non-transitory computer readable storage medium of claim 4, wherein the method further comprises acts of:

determining a degree to which the two consecutive pixel runs identified in one of the plurality of regions are consistent with the at least one characteristic of the barcode; and

determining the vote weight based, at least in part, on the degree.

6. The non-transitory computer readable storage medium of claim 4, wherein the method further comprises acts of:

determining a contrast value of at least one of the first pixel run, the second pixel run and the third pixel run; and

determining the vote weight based, at least in part, on the contrast value.

7. The non-transitory computer readable storage medium of claim 1, wherein the method further comprises an act of determining if the run lengths of each of the first pixel run, the second pixel run and the third pixel run belong to a predetermined range of barcode run lengths.

8. The non-transitory computer readable storage medium of claim 1, wherein the at least one characteristic is a barcode criterion.

19. The non-transitory computer readable storage medium of claim 1, wherein the run length of the first pixel run is consistent with a first characteristic of the barcode, and wherein the run length of the second pixel run is consistent with a second characteristic of the barcode which is different than the first characteristic.

9. A non-transitory computer readable storage medium encoded with a program for execution on a processor, the program when executed on the processor performing a method for locating a character string in an image, the character string appearing in the image in a human-readable form, the character string having at least one characteristic, the method comprising:

a) Defining a plurality of regions in the image;

b) Associating a vote accumulator with each of the regions;

c) Finding pixel runs in the image, wherein a pixel run includes a group of adjacent pixels having a like binary value arranged linearly in a first direction in the image, the pixel run bounded linearly in the first direction by at least one pixel having a binary value that differs from the like binary value;

d) Identifying, in one of the plurality of regions, two consecutive pixel runs comprising a first pixel run of pixels in the first direction and having a first binary value and a second pixel run of pixels in the first direction and having the first binary value, the two consecutive pixel runs separated in the first direction by a third pixel run of pixels in the first direction and having a second binary value, wherein the first pixel run, the second pixel run and the third pixel run are in a line, wherein each of the first pixel run, the second pixel run and the third pixel run has a run length that is consistent with the at least one characteristic of the character string;

e) Adjusting the vote accumulator associated with the region where the two consecutive pixel runs are identified; and

f) Identifying from among the plurality of regions, a region where the character string is located based on the vote accumulators,

wherein the character string includes at least one character of an alphabet.

10. The non-transitory computer readable storage medium of claim 9, wherein the at least one characteristic includes a characteristic associated with the width of an inter-character space.

11. The non-transitory computer readable storage medium of claim 9, wherein the at least one characteristic includes a characteristic associated with a character width.

12. The non-transitory computer readable storage medium of claim 9, wherein the act of adjusting the vote accumulator further comprises acts of:

determining a vote weight based at least in part on the identification of the two consecutive pixel runs; and

adjusting the vote accumulator by an amount determined by the vote weight.

13. The non-transitory computer readable storage medium of claim 12, wherein the method further comprises acts of:

determining a degree to which the two consecutive pixel runs identified in one of the plurality of regions is consistent with the at least one characteristic of the character string; and

determining the vote weight based, at least in part, on the degree.

14. The non-transitory computer readable storage medium of claim 12, wherein the method further comprises acts of:

determining a contrast value of at least one of the first pixel run, the second pixel run and the third pixel run; and

determining the vote weight based, at least in part, on the contrast value.

15. The non-transitory computer readable storage medium of claim 9, wherein the at least one characteristic includes a range of character widths, and wherein the act of identifying two consecutive pixel runs further comprises an act of determining whether each of the first pixel run and the second pixel run has a run length consistent with the range of character widths.

16. The non-transitory computer readable storage medium of claim 9, wherein the at least one characteristic is a character string criterion.

18. The non-transitory computer readable storage medium of claim 15, wherein the at least one characteristic includes a range of widths for inter-character spaces, and wherein the act of identifying the two consecutive pixel runs further comprises an act of determining whether the third pixel run has a run length consistent with the range of widths for inter-character spaces.

17. A non-transitory computer readable storage medium encoded with a program for execution on a processor, the program when executed on the processor performing a method for locating an object in an image, the object exhibiting in at least one direction foreground pixel runs and background pixel runs consistent with at least one characteristic of the object, the method comprising acts of:

a. Defining a plurality of regions in the image;

b. Associating a metric with each of the regions;

c. Finding pixel runs in the image, wherein a pixel run includes a group of adjacent pixels having a like binary value arranged in a first direction in the image, the pixel run bounded in the first direction by at least one pixel having a binary value that differs from the like binary value;

d. Identifying, in one of the plurality of regions, two consecutive pixel runs comprising a first pixel run of pixels in the first direction and having a first binary value and a second pixel run of pixels in the first direction and having the first binary value, the two consecutive pixel runs separated in the first direction by a third pixel run of pixels in the first direction and having a second binary value, wherein the first pixel run, the second pixel run and the third pixel run are in a line, wherein each of the first pixel run, the second pixel run and the third pixel run has a run length that is consistent with the at least one characteristic of the object;

e. Adjusting the metric associated with the region where the two consecutive pixel runs are identified; and

f. Identifying, from among the plurality of regions, a region where the object is located based on the metrics.