Fast barcode search
AssigneeInternational Business Machines Corporation
InventorYaakov Navon
Life of this patent
Estimating the term…
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.
Claims39
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,
- 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, and
- 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.
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,
- 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.
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,
- 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.
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,
- 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,
- 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.
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.
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,
- wherein the processor is arranged to detect the pattern of stripes substantially irrespective of the angle of orientation of the barcode, and
- 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.
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,
- 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.
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,
- 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.
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,
- 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, and
- 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.
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.
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,
- 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, and
- 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.
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,
- 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.
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,
- 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.
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,
- 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, and
- 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.
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 aide 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.
Dependencies are inferred from the claim text.