Omnidirectional barcode locator

• US 5,698,833 A
• Filed: 04/15/1996
• Issued: 12/16/1997
• Est. Priority Date: 04/15/1996
• 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 Philip
• Primary Examiner(s): Hajec, Donald T.
• Assistant Examiner(s): Lee, Michael G.
• Application Number:
  US08/632,089
• Time in Patent Office: 610 Days
• Field of Search: 235/462, 235/454, 235/471, 235/472, 235/470, 235/463, 250/208.1, 250/559.08, 382/183
• US Class Current: 235/462.09
• CPC Class Codes: G06K 7/1093 sensing, after transfer of the image of the data-field to an intermediate store, e.g. storage with cathode ray tube

Abstract

An efficient method and apparatus for determining the location and approximate orientation of a barcode on a substrate. The inventive method is preferably implemented by an omnidirectional barcode locator including an application specific integrated circuit that includes one or more field programmable gate arrays (FPGAs). The digit image is a one-bit (i.e., black/white) representation of a standard eight-bit grey scale video image produced by the CCD camera. The use of a one-bit digital video signal reduces the amount of mass storage memory required to store images of barcodes and facilitates the manipulation of the video signal by the application specific integrated circuit. The omnidirectional barcode locator processes, in real-time, a digital video signal defining a pixelized image of a conveyor carrying parcels through the field of view of a CCD camera. The omnidirectional barcode locator divides the video image into a plurality of cells and produces two output signals, a cell barcode indication signal and a cell barcode orientation signal, for each cell. A host computer responds to a "true" cell barcode indication signal for a cell by storing the portion of the video image corresponding to the cell in a mass storage memory. The host computer also stores a representation of the cell barcode orientation signal for each cell in which the cell barcode indication signal is "true." The omnidirectional barcode locator thus allows the host computer to store only those cells of the video image that contain barcode data. The barcode data may then be provided to a barcode reader for further processing.

Claims

1. A method for detecting and storing an image of a barcode on a substrate, comprising the steps of:

obtaining a pixel stream defining a pixelized image of the substrate;

channeling said pixel stream through a buffer memory;

assigning pixels from said pixel stream to a plurality of cells; and

for each of a plurality of said cells

determining a cell barcode indication value whereby the cell barcode indication value reflects the likelihood of a barcode being present within the cell, and

storing pixels within said cell in a computer memory if said cell barcode indication value is greater than a predetermined threshold value.

2. The method of claim 1, further comprising the steps of:

for each of a plurality of said cells

determining a cell barcode orientation value, and

storing a representation of said cell barcode orientation value in a mass storage computer memory if said cell barcode indication value is greater than said predetermined threshold value.

3. A method for detecting the presence of a barcode on a substrate, comprising the steps of:

obtaining a pixelized image of the substrate, said pixelized image comprising sequential parallel left-to-right rows of pixels forming orthogonal bottom-to-top columns of pixels;

computing a first horizontal comparison value by comparing intensity of pixels of a current row to intensity of pixels of a previous row wherein, for each comparison, the column of the pixel of said current row is to the left of the column of the pixel of said previous row;

computing a second horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is the same as the column of the pixel of said previous row;

computing a third horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is to the right of the column of the pixel of said previous row;

computing a horizontal barcode detection value based on one or more of said first, second, and third comparison values; and

comparing said horizontal barcode detection value to a horizontal barcode detection threshold value.

4. The method of claim 3, wherein:

said previous row immediately precedes said current row;

said step of computing a first horizontal comparison value comprises comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is one column to the left of the column of the pixel of said previous row; and

said step of computing a third horizontal comparison value comprises comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is one column to the right of the column of the pixel of said previous row.

5. The method of claim 3, further comprising the step of, if said horizontal barcode detection value is greater than said horizontal barcode detection threshold value, storing said pixelized image in a mass storage computer memory.

6. The method of claim 3, wherein said steps of computing said first, second, and third horizontal comparison values comprises the steps of:

for each of a plurality of pixels of said image

defining a horizontal window comprising a plurality of adjacent pixels along a current row of pixels,

computing a first horizontal comparison value by comparing intensity of pixels of said current row within said horizontal window to intensity of pixels of a previous row wherein, for each comparison, the column of the pixel of said current row is to the left of the column of the pixel of said previous row,

computing a second horizontal comparison value by comparing intensity of pixels of said current row within said horizontal window to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is the same as the column of the pixel of said previous row,

computing a third comparison value by comparing intensity of pixels of said current row within said horizontal window to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is to the right of the column of the pixel of said previous row,

computing a horizontal barcode detection value based on one or more of said first, second, and third horizontal comparison values, and

comparing said horizontal barcode detection value to a horizontal barcode detection threshold value.

7. The method of claim 3, further comprising the step of computing a horizontal barcode orientation value based on one or more of said first, second, and third horizontal comparison values.

8. The method of claim 7, further comprising the steps of, if said horizontal barcode detection value is greater than said horizontal barcode detection threshold value:

storing a portion of said pixelized image in a mass storage computer memory; and

storing a representation of said horizontal barcode orientation value in said mass storage computer memory.

9. A method for detecting the presence of a barcode on a substrate, comprising the steps of:

obtaining a pixelized image of the substrate, said pixelized image comprising sequential parallel left-to-right rows of pixels forming orthogonal bottom-to-top columns of pixels;

defining a cell comprising a plurality of pixels;

for each of a plurality of pixels within said cell

defining a horizontal window comprising a plurality of adjacent pixels along a current row of pixels,

computing a first horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of a previous row wherein, for each comparison, the column of the pixel of said current row is to the left of the column of the pixel of said previous row,

computing a second horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is the same as the column of the pixel of said previous row,

computing a third horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is to the right of the column of the pixel of said previous row,

computing a horizontal barcode detection value based on one or more of said first, second, and third horizontal comparison values, and

comparing said horizontal barcode detection value to a horizontal barcode detection threshold value;

computing a cell barcode indication value based on said horizontal barcode detection values; and

comparing said cell barcode indication value to a cell threshold value.

10. The method of claim 9, further comprising the steps of:

for each of a plurality of pixels within said cell, computing a horizontal barcode orientation value based on one or more of said first, second, and third horizontal comparison values; and

computing a cell barcode orientation value based on said horizontal barcode orientation values.

11. The method of claim 10, further comprising the steps of, if said cell barcode indication value is greater than said cell threshold value:

storing the portion of said pixelized image that is within said cell in a mass storage computer memory; and

storing a representation of said cell barcode orientation value in said mass storage computer memory.

12. The method of claim 9, further comprising the steps of:

for each of a plurality of pixels within said cell

defining a vertical window comprising a plurality of adjacent pixels along a current column of pixels;

computing a first vertical comparison value by comparing intensity of pixels of said current column to intensity of pixels of a previous column wherein, for each comparison, the row of the pixel of said current row is to the top of the row of the pixel of said previous column,

computing a second vertical comparison value by comparing intensity of pixels of said current column to intensity of pixels of said previous column wherein, for each comparison, the row of the pixel of said current column is the same as the row of the pixel of said previous column,

computing a third vertical comparison value by comparing intensity of pixels of said current column to intensity of pixels of said previous column wherein, for each comparison, the row of the pixel of said current column is to the bottom of the row of the pixel of said previous column,

computing a vertical barcode detection value based on one or more of said first, second, and third vertical comparison values, and

comparing said vertical barcode detection value to a vertical barcode detection threshold value.

13. The method of claim 12, wherein:

said previous row immediately precedes said current row;

said previous column immediately precedes said current column;

said step of computing a first horizontal comparison value comprises comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is one column to the left of the column of the pixel of said previous row;

said step of computing a third horizontal comparison value comprises comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is one column to the right of the column of the pixel of said previous row;

said step of computing a first vertical comparison value comprises comparing intensity of pixels of said current column to intensity of pixels of said previous column wherein, for each comparison, the row of the pixel of said current column is one row to the top of the row of the pixel of said previous column; and

said step of computing a third vertical comparison value comprises comparing intensity of pixels of said current column to intensity of pixels of said previous column wherein, for each comparison, the row of the pixels of said current column is one row to the bottom of the row of the pixel of the previous column.

14. The method of claim 12, further comprising the steps of, if said cell barcode indication value is greater than said cell threshold value:

storing the portion of said pixelized image that is within said cell in a mass storage computer memory; and

storing a representation of said cell barcode orientation value in said mass storage computer memory.

15. The method of claim 12, wherein said steps performed for each row of pixels within said cell are performed concurrently with said steps performed for each column of pixels within said cell.

16. The method of claim 12, further comprising the steps of:

for each of a plurality of pixels within said cell

computing a horizontal barcode orientation value based on one or more of said first, second, and third horizontal comparison values;

computing a vertical barcode orientation value based on one or more of said first, second, and third vertical comparison values; and

computing a cell barcode orientation value based on said horizontal and vertical barcode orientation values.

17. The method of claim 16, wherein:

said steps performed for each row of pixels within said cell are performed concurrently with said steps performed for each column of pixels within said cell;

said step of computing said horizontal barcode orientation value is performed concurrently with said step of computing said horizontal barcode detection value; and

said step of computing said vertical barcode orientation value is performed concurrently with said step of computing said vertical barcode detection value.

18. A method for detecting the presence of a barcode on a substrate, comprising the steps of:

obtaining a pixelized image of the substrate, said pixelized image comprising sequential parallel left-to-right rows of pixels forming orthogonal bottom-to-top columns of pixels;

defining a plurality of cells, each cell comprising a plurality of pixels; and

for each of a plurality of cells

for each of a plurality of pixels within said cell

defining a horizontal window comprising a plurality of adjacent pixels along a current row of pixels;

defining a vertical window comprising a plurality of adjacent pixels along a current column of pixels;

computing a first horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of a previous row wherein, for each comparison, the column of the pixel of said current row is to the left of the column of the pixel of said previous row,

computing a second horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is the same as the column of the pixel of said previous row,

computing a third horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is to the right of the column of the pixel of said previous row,

computing a horizontal barcode detection value based on one or more of said first, second, and third horizontal comparison values,

computing a first vertical comparison value by comparing intensity of pixels of said current column to intensity of pixels of a previous column wherein, for each comparison, the row of the pixel of said current row is to the top of the row of the pixel of said previous column,

computing a second vertical comparison value by comparing intensity of pixels of said current column to intensity of pixels of said previous column wherein, for each comparison, the row of the pixel of said current column is the same as the row of the pixel of said previous column,

computing a third vertical comparison value by comparing intensity of pixels of said current column to intensity of pixels of said previous column wherein, for each comparison, the row of the pixel of said current column is to the bottom of the row of the pixel of said previous column,

computing a vertical barcode detection value based on one or more of said first, second, and third vertical comparison values,

comparing said horizontal barcode detection value to a horizontal barcode detection threshold value, and

comparing said vertical barcode detection value to a vertical barcode detection threshold value;

computing a cell barcode indication value based on said horizontal and vertical barcode detection values,

comparing said cell barcode indication value to a cell threshold value, and

if said cell barcode indication value is greater than said cell threshold value, storing the portion of said pixelized image that is within said cell in a mass storage computer memory.

19. The method of claim 18, further comprising the steps of, for each of said plurality of said cells:

for each of a plurality of pixels within said cell

computing a horizontal barcode orientation value based on one or more of said first, second, and third horizontal comparison values,

computing a vertical barcode orientation value based on one or more of said first, second, and third vertical comparison values,

computing a cell barcode orientation value based on said horizontal and vertical barcode orientation values; and

if said cell barcode indication value is greater than said cell threshold value, storing a representation of said cell barcode orientation value in said mass storage computer memory.

20. An apparatus operable for detecting the presence and approximate orientation of a barcode on a substrate, comprising:

a buffer memory operable for receiving a digital video signal comprising a pixelized image of the substrate, said pixelized image comprising sequential parallel left-to-right rows of pixels forming orthogonal bottom-to-top columns of pixels;

a horizontal detector operable for

receiving a stream of pixels from said buffer memory, and

for a plurality of said pixels

defining a horizontal window comprising a plurality of adjacent pixels along a current row of pixels, and

computing a horizontal barcode detection value based on a comparison of the pixels of said current row to the pixels of a previous row;

a vertical detector operable for

receiving a stream of pixels from said buffer memory, and

for a plurality of said pixels

defining a vertical window comprising a plurality of adjacent pixels along a current column of pixels, and

computing a vertical barcode detection value based on a comparison the pixels of said current column to the pixels of a previous column;

a trigger detector operable for

receiving said horizontal barcode detection values from said horizontal detector and for receiving said vertical barcode detection values from said vertical detector, and

determining a candidate value for a plurality of said pixels, each said candidate value being based on a horizontal barcode detection value and a vertical barcode detection value; and

a totalizer operable for

receiving said candidate values from said trigger detector,

defining a cell comprising a plurality of said pixels, and

determining a cell barcode indication value based on the candidate values corresponding to the pixels within said cell.

21. The apparatus of claim 20, wherein:

said horizontal detector is further operable, for a plurality of said pixels, for computing a horizontal barcode orientation value based on a comparison of the pixels of said current row to the pixels of a previous row;

said vertical detector is further operable, for a plurality of said pixels, for computing a vertical barcode orientation value based on a comparison of the pixels of said current column to the pixels of a previous column;

said trigger detector is further operable, for a plurality of said pixels, for determining a candidate orientation value based on said horizontal and vertical barcode orientation values; and

said totalizer is further operable for determining a cell barcode orientation value based on the candidate orientation values corresponding to the pixels within said cell.

22. The apparatus of claim 21, wherein one or more of said horizontal detector, said vertical detector, said trigger detector, and said totalizer comprise a field programmable gate array.

23. A storage medium for a computer program, said storage medium comprising a computer program providing a method for detecting the presence of a barcode on a substrate, said computer program comprising the steps of:

obtaining a pixelized image of the substrate, said pixelized image comprising sequential parallel left-to-right rows of pixels forming orthogonal bottom-to-top columns of pixels;

computing a first horizontal comparison value by comparing intensity of pixels of a current row to intensity of pixels of a previous row wherein, for each comparison, the column of the pixel of said current row is to the left of the column of the pixel of said previous row;

computing a second horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is the same as the column of the pixel of said previous row;

computing a third horizontal comparison value by comparing intensity of pixels of said current row to intensity of pixels of said previous row wherein, for each comparison, the column of the pixel of said current row is to the right of the column of the pixel of said previous row;

computing a horizontal barcode detection value based on one or more of said first, second, and third comparison values; and

comparing said horizontal barcode detection value to a horizontal barcode detection threshold value.