Finding objects in an image

• US 6,512,849 B1
• Filed: 05/22/2000
• Issued: 01/28/2003
• Est. Priority Date: 05/22/2000
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yair, Eyal, Barkan, Ella, Navon, Yaakov
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US09/575,570
• Time in Patent Office: 981 Days
• Field of Search: 382/199, 382/200, 382/101, 382/102, 382/202, 382/205, 382/286, 382/287, 382/291, 382/190
• US Class Current: 382/202
• CPC Class Codes: B07C 3/14 using light-responsive detecting means for information carriers G06K7/14
• CPC Class Codes: G06V 20/62 Text, e.g. of license plates, overlay texts or captions on TV images
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/424 Postal images, e.g. labels or addresses on parcels or postal envelopes

Abstract

A method for finding a predefined object in an image includes selecting a line belonging to the object, the line having a known stroke width and defining a maximum width and a minimum width that together define a range of widths therebetween that contains the stroke width. A feature in the image is found having a feature width within the range, and the feature is processed to determine whether it is a part of the object.

Claims

1. A method for finding a predefined object in an image, comprising:

selecting a line belonging to the object, the line having a known stroke width;

defining a maximum width and a minimum width that together define a range of widths therebetween that contains the stroke width;

finding a feature in the image having a feature width within the range; and

processing the feature to determine whether it is a part of the object,

wherein finding the feature in the image comprises;

finding a first locus of pixels in the image belonging to one or more elements of the image having a width less than the maximum width;

finding a second locus of pixels in the image belonging to one or more elements of the image having a width less than the minimum width; and

taking a disjunction of the first and second loci.

2. A method according to claim 1, wherein finding the first locus comprises finding a pixel having a gray-scale value that differs by at least a predetermined contrast threshold from the gray-scale values of other pixels at a distance therefrom that is equal to the maximum width.

3. A method according to claim 1, wherein finding the feature in the image comprises sub-sampling the image before finding the loci, so that only a subset of all of the pixels in the image are considered for inclusion in the loci.

4. A method according to claim 1, wherein finding the feature in the image comprises identifying a cluster of the pixels in the disjunction of the first and second loci as a region of interest in the image, which region is a candidate to contain the object.

5. A method according to claim 1, wherein the object comprises one or more markings on an item, according to which the item is to be sorted by a sorting system, and wherein processing the feature comprises identifying the markings, and comprising sorting the item responsive to the identified markings.

6. A method for finding a predefined object in an image, comprising:

selecting a line belonging to the object, the line having a known stroke width;

defining a maximum width and a minimum width that together define a range of widths therebetween that contains the stroke width;

finding a feature in the image having a feature width within the range; and

processing the feature to determine whether it is a part of the object,

wherein finding the feature in the image comprises;

identifying a region of interest in the image, which is a candidate to contain the object;

selecting a scan line passing through the region of interest; and

evaluating gray-scale values of pixels disposed along the scan line so as to find a pair of contrast transitions that are separated from one another by a distance that is within the range.

7. A method according to claim 6, wherein selecting the scan line comprises selecting a plurality of scan lines, having a spacing therebetween determined responsive to a dimension of the object.

8. A method according to claim 6, wherein evaluating the gray-scale values comprises finding the contrast transitions such that a difference between the respective gray-scale values of a selected pair of the pixels on the scan line, one on either side of any given one of the transitions, exceeds a predetermined threshold.

9. A method according to claim 8, wherein the pair of the pixels are separated from one another by a distance that is selected as a function of the stroke width.

10. A method according to claim 6, wherein the object comprises one or more markings on an item, according to which the item is to be sorted by a sorting system, and wherein processing the feature comprises identifying the markings, and comprising sorting the item responsive to the identified markings.

11. A method for finding a predefined object in an image, comprising:

selecting a line belonging to the object, the line having a known stroke width;

defining a maximum width and a minimum width that together define a range of widths therebetween that contains the stroke width;

finding a feature in the image having a feature width within the range; and

processing the feature to determine whether it is a part of the object,

wherein processing the feature comprises;

finding a locus of at least one initial pixel belonging to the feature; and

expanding the locus to reconstruct the line in the object.

12. A method according to claim 11, wherein expanding the locus comprises adding to the locus an additional pixel that is adjacent to the at least one initial pixel and has a gray-scale value beyond a threshold that is set responsive to a gray-scale value of the at least one initial pixel.

13. A method according to claim 12, wherein adding the additional pixel to the locus comprises adding a first additional pixel, and wherein expanding the locus further comprises:

continuing to add further additional pixels that are adjacent to the pixels in the locus and have respective gray-scale values beyond the threshold; and

stopping to add the further additional pixels when the locus reaches a maximum size determined responsive to a dimension of the object.

14. A method according to claim 11, wherein processing the feature comprises processing the expanded locus so as to match the locus to the object.

15. A method according to claim 11, wherein the object comprises one or more markings on an item, according to which the item is to be sorted by a sorting system, and wherein processing the feature comprises identifying the markings, and comprising sorting the item responsive to the identified markings.

16. Apparatus for finding a predefined object in an image, comprising an image processor operative to find a feature in the image having a feature width that is within a range between a predefined maximum width and minimum width, the range being defined so that a known stroke width of a line belonging to the object falls within the range, and further operative to process the feature to determine whether it is a part of the object,

wherein the image processor is arranged to find the feature by finding a first locus of pixels in the image belonging to one or more elements of the image having a width less than the maximum width, finding a second locus of pixels in the image belonging to one or more elements of the image having a width less than the minimum width, and taking a disjunction of the first and second loci.

17. Apparatus according to claim 16, and comprising an image capture device, configured to capture the image including the object and to convey an electronic representation of the image to the image processor.

18. Apparatus according to claim 17, wherein the object comprises one or more markings on an item, according to which the item is to be sorted, and wherein the apparatus is adapted to read the markings and to sort the item responsive thereto.

19. A computer software product for finding a predefined object in an image, comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to find a feature in the image having a feature width that is within a range between a predefined maximum width and minimum width, the range being defined so that a known stroke width of a line belonging to the object falls within the range, and further cause the computer to process the feature to determine whether it is a part of the object,

wherein the instructions cause the computer to find the feature by finding a first locus of pixels in the image belonging to one or more elements of the image having a width less than the maximum width, finding a second locus of pixels in the image belonging to one or more elements of the image having a width less than the minimum width, and taking a disjunction of the first and second loci.

20. Apparatus for finding a predefined object in an image, comprising an image processor operative to find a feature in the image having a feature width that is within a range between a predefined maximum width and minimum width, the range being defined so that a known stroke width of a line belonging to the object falls within the range, and further operative to process the feature to determine whether it is a part of the object,

wherein the image processor is arranged to find the feature by identifying a region of interest in the image, which is a candidate to contain the object, selecting a scan line passing through the region of interest, and evaluating gray-scale values of pixels disposed along the scan line so as to find a pair of contrast transitions that are separated from one another by a distance that is within the range.

21. Apparatus for finding a predefined object in an image, comprising an image processor operative to find a feature in the image having a feature width that is within a range between a predefined maximum width and minimum width, the range being defined so that a known stroke width of a line belonging to the object falls within the range, and further operative to process the feature to determine whether it is a part of the object,

wherein the image processor is arranged to process the feature by finding a locus of at least one initial pixel belonging to the feature, and expanding the locus to reconstruct the line in the object.

22. A computer software product for finding a predefined object in an image, comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to find a feature in the image having a feature width that is within a range between a predefined maximum width and minimum width, the range being defined so that a known stroke width of a line belonging to the object falls within the range, and further cause the computer to process the feature to determine whether it is a part of the object,

wherein the instructions cause the computer to find the feature by identifying a region of interest in the image, which is a candidate to contain the object, selecting a scan line passing through the region of interest, and evaluating gray-scale values of pixels disposed along the scan line so as to find a pair of contrast transitions that are separated from one another by a distance that is within the range.

23. A computer software product for finding a predefined object in an image, comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to find a feature in the image having a feature width that is within a range between a predefined maximum width and minimum width, the range being defined so that a known stroke width of a line belonging to the object falls within the range, and further cause the computer to process the feature to determine whether it is a part of the object,

wherein the instructions cause the computer to process the feature by finding a locus of at least one initial pixel belonging to the feature, and expanding the locus to reconstruct the line in the object.