Fast barcode search

• US 20020162889A1
• Filed: 05/02/2001
• Published: 11/07/2002
• Est. Priority Date: 05/02/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Navon, Yaakov
• Granted Patent: US 6,729,544 B2
• Time in Patent Office: Days
• US Class Current: 235/462.14
• 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/1443 locating of the code in an image
• 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 209/90 Sorting flat-type mail

Abstract

A method for locating a barcode in an image includes dividing the image into a plurality of tiles, and scanning each of the tiles so as to detect a pattern of stripes associated with the barcode in at least one of the tiles. The pattern of stripes is analyzed so as to determine an angle of orientation of the barcode. Responsive to the determined angle, bounds of the barcode are defined in alignment with the pattern of the stripes.

Claims

1. A method for locating a barcode in an image, comprising:

dividing the image into a plurality of tiles;

scanning each of the tiles so as to detect a pattern of stripes associated with the barcode in at least one of the tiles;

analyzing the pattern of stripes so as to determine an angle of orientation of the barcode; and

responsive to the determined angle, defining bounds of the barcode that are aligned with the pattern of the stripes.

2. A method according to claim 1, wherein scanning each of the tiles comprises scanning so as to detect the pattern of stripes substantially irrespective of the angle of orientation of the barcode.

3. A method according to claim 2, wherein scanning each of the tiles comprises scanning on a first line through the tile in a first scan direction so as to detect the stripes in the tile that are crossed by the first line, and scanning on a second line through the tile in a second scan direction, at a diagonal to the first direction, so as to detect the stripes in the tile that are crossed by the second line.

4. A method according to claim 1, wherein scanning each of the tiles comprises:

scanning the tile along a selected scan line in a first scan direction so as to locate a first sequence of pixels on the line having pixel values within a predetermined range;

starting from each of at least some of the pixels in the first sequence, scanning in a second scan direction, transverse to the first scan direction, to both sides of the scan line, so as to reach endpoint pixels defined by the first of the pixels on both sides of the line having pixel values outside the predetermined range; and

joining the endpoint pixels on each side of the line so as to define respective edges of a first one of the stripes.

5. A method according to claim 4, and comprising:

repeating the steps of scanning the area in the first and second scan directions and of joining the endpoint pixels for at least a second sequence of the pixels on the line having pixel values within the predetermined range, so as to define the respective edges of at least a second one of the stripes; and

comparing the edges of at least the first and second stripes to find the stripe pattern in the image.

6. A method according to claim 1, wherein scanning each of the tiles comprises detecting the pattern of stripes in a first one of the tiles, and wherein defining the bounds of the barcode comprises seeking the bounds of the barcode in at least a second one of the tiles, adjacent to the first one of the tiles.

7. A method according to claim 1, wherein the stripes have respective ends, and wherein defining the bounds of the barcode comprises locating the ends of the stripes and delimiting a rectangle containing the barcode and having sides defined by the ends of the stripes.

8. A method according to claim 7, wherein defining the bounds of the barcode comprises finding extreme lines of the barcode corresponding to first and last ones of the stripes of the barcode, and wherein locating the ends of the stripes comprises scanning along at least some of the stripes intermediate the first and last stripes in a direction parallel to the extreme lines.

9. A method according to claim 1, and comprising reading the barcode responsive to the bounds.

10. A method for finding a pattern of parallel stripes in an image, which comprises a plurality of pixels having respective pixel values, the method comprising:

scanning an area of the image along a selected scan line in a first scan direction so as to locate a first sequence of the pixels on the line having pixel values within a predetermined range;

starting from each of at least some of the pixels in the sequence, scanning in a second scan direction, transverse to the first scan direction, to both sides of the line, so as to reach endpoint pixels defined by the first of the pixels on both sides of the line having pixel values outside the predetermined range;

joining the endpoint pixels on each side of the line to define respective edges of a first one of the stripes;

repeating the steps of scanning the area in the first and second scan directions and of joining the endpoint pixels for at least a second sequence of the pixels on the line having pixel values within the predetermined range, so as to define the respective edges of at least a second one of the stripes; and

comparing the edges of at least the first and second stripes to find the stripe pattern in the image.

11. A method according to claim 10, and comprising scanning the area along a further scan line, in a direction diagonal to the first scan direction, so as to locate third and fourth sequences of the pixels on the further scan line having pixel values within the predetermined range, and repeating the steps of scanning in the second direction, joining the endpoint pixels and comparing the edges with respect to the third and fourth sequences of the pixels and the diagonal direction.

12. A method according to claim 10, wherein comparing the edges comprises determining an orientation of the stripes in the pattern.

13. A method according to claim 12, wherein comparing the edges comprises identifying the stripes as belonging to the stripe pattern only if the edges are mutually parallel to within a predetermined limit.

14. A method according to claim 10, wherein the pattern comprises a barcode.

16. Apparatus according to claim 15, wherein the processor is arranged to detect the pattern of stripes substantially irrespective of the angle of orientation of the barcode.

17. Apparatus according to claim 16, wherein the processor is arranged to scan each of the tiles on a first line through the tile in a first scan direction so as to detect the stripes in the tile that are crossed by the first line, and on a second line through the tile in a second scan direction, at a diagonal to the first direction, so as to detect the stripes in the tile that are crossed by the second line.

18. Apparatus according to claim 15, wherein the processor is arranged to scan each of the tiles along a selected scan line in a first scan direction so as to locate a first sequence of pixels on the line having pixel values within a predetermined range, and starting from each of at least some of the pixels in the first sequence, to scan in a second scan direction, transverse to the first scan direction, to both sides of the scan line, so as to reach endpoint pixels defined by the first of the pixels on both sides of the line having pixel values outside the predetermined range, and to join the endpoint pixels on each side of the line so as to define respective edges of a first one of the stripes.

19. Apparatus according to claim 18, wherein the processor is arranged to repeat the steps of scanning the area in the first and second scan directions and of joining the endpoint pixels for at least a second sequence of the pixels on the line having pixel values within the predetermined range, so as to define the respective edges of at least a second one of the stripes, and to compare the edges of at least the first and second stripes to find the stripe pattern in the image.

20. Apparatus according to claim 15, wherein upon detecting the pattern of stripes in a first one of the tiles, the processor is arranged to seek the bounds of the barcode in at least a second one of the tiles, adjacent to the first one of the tiles.

21. Apparatus according to claim 15, wherein the stripes have respective ends, and wherein the processor is arranged to locate the ends of the stripes and to delimit a rectangle containing the barcode and having sides defined by the ends of the stripes.

22. Apparatus according to claim 21, wherein the processor is arranged to- find extreme lines of the barcode corresponding to first and last ones of the stripes of the barcode, and to scan along at least some of the stripes intermediate the first and last stripes in a direction parallel to the extreme lines in order to locate the ends of the stripes.

23. Apparatus according to claim 15, and comprising an image capture device, which is arranged to capture the image of an object on which the barcode appears.

24. Apparatus according to claim 23, wherein the image processor is arranged to read the barcode responsive to the bounds so as to extract information contained in the barcode, and comprising a sorter, which is arranged to sort the object responsive to the information.

26. Apparatus according to claim 25, wherein the processor is arranged to scan the area along a further scan line, in a direction diagonal to the first scan direction, so as to locate third and fourth sequences of the pixels on the further scan line having pixel values within the predetermined range, and to repeat the steps of scanning in the second direction, joining the endpoint pixels and comparing the edges with respect to the third and fourth sequences of the pixels and the diagonal direction.

27. Apparatus according to claim 25, wherein the processor is arranged to determine an orientation of the stripes in the pattern by comparing the edges of the stripes.

28. Apparatus according to claim 27, wherein the processor is arranged to identify the stripes as belonging to the stripe pattern only if the edges are mutually parallel to within a predetermined limit.

29. Apparatus according to claim 25, wherein the pattern comprises a barcode.

15. Apparatus for locating a barcode in an image, comprising an image processor, which is arranged to divide the image into a plurality of tiles, to scan each of the tiles so as to detect a pattern of stripes associated with the barcode in at least one of the tiles, to analyze the pattern of stripes so as to determine an angle of orientation of the barcode, and responsive to the determined angle, to define bounds of the barcode that are aligned with the pattern of the stripes.

25. Apparatus for finding a pattern of parallel stripes in an image, which comprises a plurality of pixels having respective pixel values, the apparatus comprising an image processor, which is arranged to scan an area of the image along a selected scan line in a first scan direction so as to locate a first sequence of the pixels on the line having pixel values within a predetermined range, and starting from each of at least some of the pixels in the sequence, to scan in a second scan direction, transverse to the first scan direction, to both sides of the line, so as to reach endpoint pixels defined by the first of the pixels on both sides of the line having pixel values outside the predetermined range, to join the endpoint pixels on each side of the line to define respective edges of a first one of the stripes, and to repeat the steps of scanning the area in the first and second scan directions and of joining the endpoint pixels for at least a second sequence of the pixels on the line having pixel values within the predetermined range, so as to define the respective edges of at least a second one of the stripes, and to compare the edges of at least the first and second stripes to find the stripe pattern in the image.

30. A computer software product for locating a barcode 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 divide the image into a plurality of tiles, to scan each of the tiles so as to detect a pattern of stripes associated with the barcode in at least one of the tiles, to analyze the pattern of stripes so as to determine an angle of orientation of the barcode, and responsive to the determined angle, to define bounds of the barcode that are aligned with the pattern of the stripes.

31. A product according to claim 30, wherein the instructions cause the computer to scan the tiles so as to detect the pattern of stripes substantially irrespective of the angle of orientation of the barcode.

32. A product according to claim 31, wherein the instructions cause the computer to scan each of the tiles on a first line through the tile in a first scan direction so as to detect the stripes in the tile that are crossed by the first line, and to scan on a second line through the tile in a second scan direction, at a diagonal to the first direction, so as to detect the stripes in the tile that are crossed by the second line.

33. A product according to claim 30, wherein the instructions cause the computer to scan each of the tiles along a selected scan line in a first scan direction so as to locate a first sequence of pixels on the line having pixel values within a predetermined range, and starting from each of at least some of the pixels in the first sequence, to scan in a second scan direction, transverse to the first scan direction, to both sides of the scan line, so as to reach endpoint pixels defined by the first of the pixels on both sides of the line having pixel values outside the predetermined range, and to join the endpoint pixels on each side of the line so as to define respective edges of a first one of the stripes.

34. A product according to claim 33, wherein the instructions further cause the computer to repeat the steps of scanning the area in the first and second scan directions and of joining the endpoint pixels for at least a second sequence of the pixels on the line having pixel values within the predetermined range, so as to define the respective edges of at least a second one of the stripes, and to compare the edges of at least the first and second stripes to find the stripe pattern in the image.

35. A product according to claim 30, wherein the instructions cause the computer, upon detecting the pattern of stripes in a first one of the tiles, to seek the bounds of the barcode in at least a second one of the tiles, adjacent to the first one of the tiles.

36. A product according to claim 30, wherein the stripes have respective ends, and wherein the instructions cause the computer to find the ends of the stripes and to delimit a rectangle containing the barcode and having sides defined by the ends of the stripes.

37. A product according to claim 36, wherein the instructions cause the computer to find extreme lines of the barcode corresponding to first and last ones of the stripes of the barcode, and to locate the ends of the stripes by scanning along at least some of the stripes intermediate the first and last stripes in a direction parallel to the extreme lines.

39. A product according to claim 38, wherein the instructions cause the computer to scan the area along a further scan line, in a direction diagonal to the first scan direction, so as to locate third and fourth sequences of the pixels on the further scan line having pixel values within the predetermined range, and to repeat the steps of scanning in the second direction, joining the endpoint pixels and comparing the edges with respect to the third and fourth sequences of the pixels and the diagonal direction.

40. A product according to claim 38, wherein the instructions cause the computer to determine an orientation of the stripes in the pattern responsive to the edges.

41. A product according to claim 40, wherein the instructions cause the computer to identify the stripes as belonging to the stripe pattern only if the edges are mutually parallel to within a predetermined limit.

42. A product according to claim 38, wherein the pattern comprises a barcode.

38. A computer software product for finding a pattern of parallel stripes in an image, which comprises a plurality of pixels having respective pixel values, the product comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to scan an area of the image along a selected scan line in a first scan direction so as to locate a first sequence of the pixels on the line having pixel values within a predetermined range, and starting from each of at least some of the pixels in the sequence, to scan in a second scan direction, transverse to the first scan direction, to both sides of the line, so as to reach endpoint pixels defined by the first of the pixels on both sides of the line having pixel values outside the predetermined range, to join the endpoint pixels on each side of the line to define respective edges of a first one of the stripes, and to repeat the steps of scanning the area in the first and second scan directions and of joining the endpoint pixels for at least a second sequence of the pixels on the line having pixel values within the predetermined range, so as to define the respective edges of at least a second one of the stripes, and to compare the edges of at least the first and second stripes to find the stripe pattern in the image.