WO1996009597A1

WO1996009597A1 - Method and apparatus for detecting and adaptively decoding bar code symbols in continuous images

Info

Publication number: WO1996009597A1
Application number: PCT/US1995/002791
Authority: WO
Inventors: Luis Figarella; Mihael Klancnik
Original assignee: United Parcel Service Of America, Inc.
Priority date: 1994-09-22
Filing date: 1995-02-28
Publication date: 1996-03-28
Also published as: AU1981195A

Abstract

A method and apparatus for detecting a bar code symbol in a continuous two-dimensional pixel image, such as an image generated by a video camera. After each new set of pixel image data is generated and stored in a circular buffer (1900), a set of pixel image data (1904) near the 'center' of the image data stored in the circular buffer is processed to detect bar code symbols. Processing image data for bar code symbols involves scanning along selected rows and columns of the image data. Scanning along a selected row or column involves identifying the locations of pixel-intensity-level transitions, storing the locations in a circular buffer, and testing the contents of the circular transition buffer for a wide bright region (corresponding to a bar code symbol quiet zone) adjacent to a dense sequence of transitions (corresponding to bars and spaces of a bar code symbol). Also, a method and apparatus for decoding a bar code symbol, wherein the width of each space (bar) is characterized according to the area under (over) the portion of the pixel intensity level 'curve' corresponding to that space (bar). The portion of the curve corresponding to a space (bar) is from the center of the previous bar (space) to the center of the following bar (space), where the centers are identified using a two-part scoring algorithm. The baseline level used to calculate the area under (over) the identified portion of the curve is based on the local dynamic range of pixel intensity levels and may be determined using a proportional integral filter.

Description

METHOD AND APPARATUS FOR DETECTING AND ADAPTIVEI DECODING BAR CODE SYMBOLS IN CONTINUOUS IMAGES

BACKGROUND OF THE INVENTION

Field of the Invention

The present ιn\ entιon relates to reading bar code symbols, and. in particular, to methods and apparatuses for detecting and decoding bar code symbols that are randomly arranged in continuous two-dimensional gray-scale pixel images

Statement of Related Art

Bar codes are the most widely used code for automatic identification Traditional bar code sy mbol readers are laser scanners that are ill-suited for reading two-dimensional codes In addition, they may require frequent maintenance and tuning Two-dimensional codes may be more easiK read by systems w ith cameras having linear charge coupled device (CCD) arrays Such cameras, which require little maintenance or tuning, generate two-dimensional gray-scale pixel images of code s mbols The present invention detects and decodes bar code symbols in pixel images generated by CCD camera systems, so that the same code symbol reader may be used for reading both bar codes and two-dimensional codes

SUMMARY OF THE INVENTION

The present invention is a method and apparatus for detecting a bar code symbol in a continuous two-dimensional pixel image A plurality of rows of the image are received and stored in a memory , where the plurality of rows comprises a first set of one or more rows A new set of one or more row s of the image are then received and used to replace the first set in the memory A subimage is processed to determine whether the subimage comprises at least a part of the symbol, where the subimage comprises one or more rows of the image in the memory

In an alternative preferred embodiment, the present invention is a method and apparatus for detecting a bar code symbol in a two-dimensional pixel image A scan line in the image is selected, where the scan line is a row or column of the image One or more transitions along the scan line are characterized and then it is determined whether the one or more transitions correspond to a quiet zone of the symbol

The present invention is also a method and apparatus for decoding a bar code

mbol A signal representativ e of the sy mbol is received The signal is searched in one dimension to locate a first point corresponding to a first element of the symbol This searching comprises ( 1 ) locating a first transition. (2) characterizing the first transition to determine whether the first transition corresponds to a first edge of the first element, (3) locating a second transition. (4) characterizing the second transition to determine w hether the second transition corresponds to a second edge of the first element, and (5 ) locating the first point in accordance w ith the first and second transitions The signal is searched in the one dimension to locate a second point corresponding to a second element A \ aiue representative of the signal energy between the first and second points is computed The width of a third element between the first and second elements is determined in accordance with the value and the bar code symbol is decoded in accordance with the determined w idth

In an alternativ e preferred embodiment of the method and apparatus for decoding a bar code s mbol of the present inv ention, a signal representative of the svmbol is receiv ed The signal is searched to locate a first point corresponding to a first element, where the first element is followed by a second element and the second element is followed by a third element The local dynamic range corresponding to the second element is characterized The signal is searched to locate a second point corresponding to the third element A value representative of the signal energy between the first and second points is computed in accordance with the local dynamic range The w idth of the second element is determined in accordance with the value and the bar code symbol is decoded in accordance w ith the determined w idth

BRIEF DESCRIPTION OF THE DRAW INGS

Fig 1 is a process flow diagram of a detection system for detecting bar code sy mbols according to a preferred embodiment of the present invention.

Fig 2 is a graphical representation of a pixel image containing a bar code symbol oriented at a 45-degree angle w ith respect to the rows and columns of pixels in the pixel image

Fig 3 is a process flow diagram of a start/stop character identification subsystem of the detection system of Fig 1 for identifying bar code symbol start/stop characters.

Fig 4 is a process flow diagram of a four-corner location subsystem of the detection system of Fig 1 for locating the four corners of a bar code symbol.

Fig 5 is a graphical representation of a pixel sub-image of the pixel image of Fig 2.

Fig. 6 is a process flow diagram of a two-corner location subsystem for locating two corners of a bar code symbol according to a preferred embodiment of the present invention, Fig 7 is a process flow diagram for a seed pixel selection subsystem of the two-corner location subsystem of Fig 6 for selecting a next seed pixel from a current seed pixel.

Fig 8 is a table representing first twelve processing cycles of the two-corner location subsystem of Fig 6 for the sub-image of Fig 5.

Fig 9 is a process flow diagram of a bar code symbol decoding subsv stem of the detection sy stem of Fig 1 for decoding a bar code symbol,

Fig 10 is a graphical representation of a pixel image containing a degraded bar code symbol.

Fig 1 1 is a process flow diagram of a stepping subsystem of the bar code symbol decoding subsy stem of Fig 9 for stepping along a reference line and decoding a bar code symbol

Fig 12 is a graphical representation of a pixel image containing a portion of a bar code symbol that is not aligned w ith either the pixel rows or columns of the pixel image.

Fig 13 is a graphical representation of the pixel intensity lev els of 1 1 pixels in a search step of the pixel image of Fig 12,

Fig 14 is a process flow diagram of a subpixel interpolation subsystem for calculating signal energy values for bar code symbol bars according to a preferred embodiment of the present invention.

Fig 15 is a process flow diagram of a subpixel interpolation subsystem for calculating signal energy values for bar code symbol spaces according to a preferred embodiment of the present invention.

Fig 16 is a graphical representation of a bar code symbol character consisting of three bars and three spaces.

Fig 17 is a process flow diagram of a stitching subsystem for decoding bar code symbols by stitching according to a preferred embodiment of the present invention.

Fig 18 is a graphical representation of a pixel image containing a bar code symbol which is not aligned with either the pixel rows or columns of the pixel image.

Figs 19 and 20 are graphical representations of pixel image data stored in a circular image buffer that holds 1024 rows of image data having 4096 pixels per row.

Fig 21 is a process flow diagram of a detection system for detecting and decoding bar code symbols in continuous pixel images according to a preferred embodiment of the present invention,

Fig 22 is a process flow diagram of the means of the detection system of Fig 21 for processing a subimage of the image stored in the circular image buffer of Figs 19 and 20,

Fig 23 is a graphical representation of pixel intensity levels corresponding to a line passing through a pixel image Fig 24 is a graphical representation of an exemplary sequence of the pixel intensitv le els corresponding to a line passing through a noisy image of a bar code sv mbol generated using a CCD-based camera,

Fig 25 is a process flow diagram of a means of the means of Fig 22 for scanning along a selected scan line for potential bar code symbols.

Fig 26 is a process flow diagram of a means of the means of Fig 25 for processing transitions.

Fig 2^" is a process flow diagram of a means of the means of Fig 26 for determining whether the data in a circular transition buffer corresponds to a potential bar code symbol.

Fig 28 is a process flow diagram of a subsystem for performing subpixel interpolation for a sequence of bars and spaces of a bar code svmbol according to a preferred embodiment of the present invention.

Fig 29 is a block flow diagram of the means of the subs stem of Fig 28 for searching for the next peak along a scan line.

Fig 30 is a block flow diagram of the means of the subsv stem ol Fig 28 for searching for the next valley along a scan line.

Fig 31 is a block flow diagram of the means of the subsystem of Fig 28 for determining the center of the current element and generating a subpixel interpolation value for the preceding element,

Fig 32 is a block flow diagram of the means of the subsystem of Fig 28 for searching for the end of a plateau, and

Fig 33 is a block flow diagram for the means of the subsy stem of Fig 28 for determining the appropriate state for the next transition search

DETAILED DESCRIPTION OF THE INVENTION The present inv ention includes a system for detecting and decoding bar code sy mbols In a preferred embodiment, bar code symbols are contained in two-dimensional gray-scale pixel image signals generated by a charge coupled device (CCD) array camera Each pixel image may contain one or more randomly placed and oriented bar code symbols More particularly , the bars in the bar code symbols may not be aligned w ith either the rows or columns of pixels in the pixel images The detecting and decoding system of the present invention requires no a priori kno ledge of the orientations and positions of bar code symbols in the pixel images That is. the sy stem is able to detect bar code symbols in pixel images by processing the pixel images themselv es, without hav ing any existing knowledge about the orientations and positions of those svmbols w ithin those pixel images In a preferred embodiment of the present invention, a pixel image is scanned along successive selected scan lines at low resolution for a bar code symbol quiet zone. Each successive scan line is preferably selected in accordance with a binary search sequence so that, with successiv e scan lines, the pixel image is divided into smaller and smaller sections. When a quiet zone is detected, the pixel image is searched along the selected scan line at high resolution for any one of a set of reference bar code symbol start/stop characters contained in a reference table. If one such start/stop character is found, then a bar code symbol is detected and the four corners of the bar code symbol are located in the pixel image. Using these four corners to identify' the region of the pixel image containing the detected bar code symbol, the bar code symbol is then decoded. After decoding a detected bar code symbol, scanning the pixel image for another quiet zone of another bar code symbol is resumed at lo resolution. This detecting and decoding of bar code symbols may continue until the low-resolution scanning for quiet zones has subdivided the pixel image into a specified section size.

Detecting and Decoding Bar Code Svmbols

Referring no to Fig. 1. there is shown a process flow diagram of detection system 100 for detecting and decoding bar code symbols according to a preferred embodiment of the present invention. Detection system 100 receives a two-dimensional gray-scale pixel image as input, scans the pixel image in one dimension for quiet zones, searches in one dimension for start/stop characters after finding each quiet zone, finds the four corners of each bar code symbol that is detected, and decodes each detected bar code symbol. Detection system 100 may reside in and operate on a 16-MHz 386sx computer with a math co-processor or on a "SUPERCARD2" brand i860 CPU RISC processor, manufactured by CSPI.

In a preferred embodiment of the present invention, detection system 100 accepts a pixel image as input and means 102 generates a histogram of the pixel image. The histogram indicates the minimum and maximum intensity levels for the pixels in that pixel image. As explained later in this specification in conjunction with Figs. 14 and 15. these minimum and maximum intensity levels are used to determine the widths of the bars and spaces of bar code symbols contained in the pixel image.

Detection system 100 scans through the pixel image for quiet zones along selected scan lines. Each scan line is either a row or column of pixels in the pixel image. In a preferred embodiment of the present invention, the scan lines are selected in a bi-directional binary search sequence.

Referring no to Fig. 2. there is shown a graphical representation of pixel image 200 containing bar code symbol 202 oriented at a 45-degree angle with respect to the rows and columns of pixels in pixel image 200. According to a preferred bi-directional binary search sequence of the present invention, a first scan line 264 divides pixel image 200 in half hoπzontallv A second scan line 210 divides pixel image 200 in half vertically Third and fourth scan lines 270 and 258 di ide the top and bottom halves of pixel image 200 m half again, respectively Similarlv fifth and sixth scan lines 204 and 216 div ide the left and right halves of pixel image 200 in half again respectiv elv Thus scan lines are preferablv either parallel or perpendicular to one another

The selection of subsequent scan lines is preferably made by continually div iding in half the remaining sections of pixel image 200 Depending on the operational requirements imposed on detection system 100. the scanning of pixel image 200 may continue until a specified minimum section size is reached, until each and ev ery pixel row and column is scanned or until the allowed processing time has expired In a preferred embodiment, scanning of pixel image 200 ensures that each bar code sv mbol quiet zone is scanned at least two times

For example pixel image 200 may represent an imaged area that is 5 12 inches w ide and 5 12 inches high with each pixel representing an area that is 0 01 inch bv 0 01 inch in size If the bar code symbols being searched for hav e bars that are at least 2 inches high then a search sequence preferably selects scan lines until pixel image 200 is div ided into sections that are at least a small as 0 71 inch by 0 71 inch Where pixel image 200 represents an area that is 5 12 inches bv 5 12 inches square and is scanned in accordance with the preferred binary search sequence shown in Fig 2 each section 238 will represent a 0 64-ιnch by 0 64-inch square area Such section sizes ensure that the quiet zones of a 2-inch high bar code symbol aligned at a worst-case 45-degree angle relativ e to the pixel rows and columns ill be scanned at least two times

Referring again to Fig 1 , means 104 is provided for selecting a scan line from the pixel row s and columns in a pixel image Means 106 scans the selected scan line in a quiet-zone scan direction tor a potential bar code symbol quiet zone Scanning for quiet zones is preferably performed at low resolution where the intensity level of only every second or third pixel in the selected scan line is analyzed

In a preferred embodiment, the energy of each pixel in the pixel image corresponds to a gray-scale intensity level Pixels corresponding to white or bright areas of the pixel image hav e high energies and high gray-scale intensity levels, while pixels corresponding to black or dark areas hav e low energies and low gray -scale intensity levels For example in an 8-bit gra -scale pixel image absolute white corresponds to an intensity level of 255 and absolute black corresponds to an intensity level of 0

A bar code symbol quiet zone is a relatively large bright area adiacent to a bar code symbol Means 106 detects a quiet zone by looking along the selected scan line for a state transition from a sequence of n bright pixels to at least one dark pixel, or from a dark pixel to a sequence of ti bright pixels, where n is a specified value A pixel is considered bright if its intensity level is greater than a first threshold, otherwise the pixel is considered dark In a preferred embodiment, means 102 determines the first threshold by generating a histogram of the pixel image. The first threshold may be either the mean intensity level or the median intensity level from the histogram. Alternatively, the first threshold may simply be a predetermined constant or may be determined in other way s, including other types of statistical analysis. In any case, the first threshold is used to distinguish dark pixels from bright pixels in the pixel image.

In order to detect potential quiet zones, means 106 searches for continuous sequences of n bright pixels, where n is an integer that is greater than a second threshold. This second threshold depends on the resolution of the pixel image, the size of the quiet zones being searched for. and the resolution of the quiet-zone scanning. For example, when every third pixel is analyzed in searching for quiet zones that are at least 0.25 inches w de in a pixel image wherein each pixel represents a 0.01 -inch by 0.01 -inch square area, the second threshold may be selected to be 7 pixels.

In a preferred embodiment, all vertical quiet-zone scans follow the same quiet-zone scan direction, either top to bottom or bottom to top. and. similarly, all horizontal quiet-zone scans follow the same quiet-zone scan direction, either left to right or right to left. In alternative embodiments, scanning for quiet zones may be performed at high resolution by analyzing every pixel in each selected scan line, and scanning of selected scan lines may proceed along different quiet-zone scan directions.

If means 106 determines that a potential quiet zone is not detected along the selected scan line, then means 118 determines whether quiet-zone scanning has reached the end of the selected scan line. If means 118 determines that end of the selected scan line has not been reached, then processing proceeds to means 106 to continue quiet-zone scanning along the selected scan line at low resolution for a potential quiet zone; otherwise means 120 determines whether quiet-zone scanning of the entire pixel image is complete. If quiet-zone scanning is not complete, then processing returns to means 104 to select a next scan line for processing; otherwise processing of the pixel image by detection subsystem 100 is complete.

If means 106 determines that a potential quiet zone is detected along the selected scan line, then means 108 determines whether the potential quiet zone is inside a region of the pixel image previously determined to contain a bar code symbol. In a preferred embodiment, detection system 100 ignores those regions of the pixel image that contain bar code symbols that were already detected and decoded. If the potential quiet zone is inside such a region, then means 118 determines whether quiet- zone scanning has reached the end of the selected scan line.

If means 108 determines that the potential quiet zone is not inside a pixel image region containing a previously detected and decoded symbol, then start/stop character identification subsystem 110 determines whether or not the potential quiet zone is a true quiet zone. A true quiet zone follows or precedes a start/stop character. Identification subsystem 110 searches along the selected scan line at high resolution to identify a start stop character. Thus, the search direction and the selected scan line are collinear Identification subsystem 110 is described briefly below and again in further detail later in this specification in conjunction with Fig 3

Subsystem 110 is provided for searching at high resolution along the selected scan line for a bar code symbol start/stop character In a preferred embodiment, searching at high resolution inv olv es analyzing the intensity of every pixel along a portion of the selected scan line If means 106 detected a potential quiet zone in which the state transition was from bright to dark, then a bar code symbol may follow the potential quiet zone in the quiet-zone scan direction In that case, subsy stem 110 searches for a starfstop character in the same direction as the quiet-zone scan Alternativ ely , it the potential quiet zone detected by means 106 has a state transition from dark to bright, then a bar code sy mbol may precede the potential quiet zone In that case subsv stem 110 searches along the selected scan line in the direction opposite the quiet-zone scan direction for a start stop character

Start stop character identification subsystem 110 determines w hether a stop'start character abuts the potential quiet zone detected by means 106 In a preferred embodiment, detection sv stem 100 mav be used to detect sy mbols of any recognized bar code s mbologv These may include tor example sy mbols of the Universal Product Code (UPC ) the European Article Numbering sv stem (EAN). Interleaved 2 ot 5. Codabar. Code 39. Code 128. Code 93. Code 49. or Code 16k s mbologies Detection system 100 may include a reference table containing information regarding start stop characters of any bar code symbologv For purposes of this invention, start/stop characters may be considered to include termination bars or patterns which traditionallv abut such characters If subsy stem 110 does not identify a character adjacent to the potential quiet zone as one of these reference start/stop characters, then the potential quiet zone is rejected as a false quiet zone and means 118 determines whether the end of the selected scan line has been reached, as described earlier If subsy stem 110 does identify a character adjacent to the potential quiet zone as a reference start/stop character then a bar code symbol is determined to exist in the pixel image and processing continues w ith four-corner location subsy stem 112

Four-comer location subsystem 112 attempts to locate the four corners of the bar code sy mbol identified by identification subsystem 110 If location subsy stem 112 does not locate all four comers of the detected bar code symbol, then the detected bar code symbol is reiected and processing continues to means 118 Otherw ise, after location subsystem 112 successfully locates the four comers of the bar code symbol, decoding subsystem 114 decodes the detected bar code sv mbol Location subsystem 112 and decoding subsystem 114 are described in further detail later in this specification in conjunction with Figs 4 and 9. respectively

After decoding subsystem 114 decodes the detected bar code symbol, means 116 retains information about the region of the pixel image containing that bar code sv mbol Means 108 uses the information stored by mean 116 to ignore that same region during subsequent processing After detecting and decoding a bar code symbol, detection system 100 continues to scan unscanned regions of the pixel image for other bar code symbols. Thus, after means 116 stores information about the region of the pixel image containing the decoded bar code symbol, processing continues with means 118. which determines whether the end of the selected scan line has been reached.

Referring again to the example of Fig. 2. means 102 of detection system 100 of Fig. 1 generates a histogram of pixel image 200. Means 104 may then select scan line 264 as the first scan line for pixel image 200. Means 106 may perform a low-resolution quiet-zone scan from left to right (the quiet-zone scan direction) along scan line 264 starting from point 262. At point 266. means 106 may detect a state transition from a sequence of bright pixels to at least one dark pixel indicating a potential quiet zone. Means 108 then determines that the potential quiet zone is not inside a pixel image region containing a bar code symbol previously detected and decoded. Start/stop character identification subsystem 110 searches along scan line 264 in the quiet-zone scan direction at high resolution for a reference start/stop character contained in the reference table. Since point 266 is not the start of a start/stop character, subsystem 110 does not identify any reference start/stop character, indicating that the potential quiet zone detected by means 106 was a false quiet zone. Means 118 then determines that the end of scan line 264 has not been reached and means 106 resumes the low- resolution scan in the quiet-zone scan direction (left to right) along scan line 264 from point 266.

Means 106 may detect another state transition from a dark pixel to sequence of bright pixels at point 232 indicating another potential quiet zone. Means 108 again determines that this potential quiet zone is not inside a region of pixel image 200 containing a previously decoded bar code symbol. Since the detected state transition is from dark to bright, subsystem 110 searches for a start/stop character at high resolution along scan line 264 from right to left, that is. in the direction opposite that of the quiet-zone scan direction. Once again, subsystem 110 fails to identif a reference start/stop character, means 118 determines that scan line 264 is not complete, and means 106 resumes the lo -resolution quiet-zone scan along scan line 264 from point 232 in the quiet-zone scan direction from left to right.

The low-resolution quiet-zone scan along scan line 264 continues in the quiet-zone scan direction without detecting any more potential quiet zones until point 234 is reached, at which time means 118 determines that scan line 264 is complete. Means 120 then determines that scan line 264 is not the last scan line for pixel image 200 and that quiet-zone scanning of pixel image 200 is therefore not complete. Means 104 then selects scan line 210 as the next scan line for low-resolution quiet-zone scanning from point 208 to point 244. Thus, during lov -esolution scanning from point 208 to point 244. the quiet-zone scan direction is from top to bottt While scanning pixel image 200 at low resolution for quiet zones along scan line 210. means lOo may detect potential quiet zones corresponding to the state transitions at points 206 and 242 that are rejected by identification subsystem 110 as false quiet zones. After completing the low-resolution quiet-zone scan of pixel image 200 along scan li 210. means 104 selects scan line 270 and begins scanning from point 268 to point 226 in a left-to- πght quiet-zone scan direction After detecting another false quiet zone at point 212. means 106 detects a state transition from a dark to a sequence of bright pixels at point 224 and again means 10 determines that the region is not to be ignored Subsystem 110 then performs a high-resolution sear for a start stop character from right to left (I e , in a direction opposite the quiet-zone scan direction) along scan line 270 In this case, identification subsystem 110 may identify a reference start/stop character at point 224 Location subsystem 112 then locates comers 214. 230 246. and 260. and decoding subsystem 114 decodes bar code svmbol 202

After decoding bar code symbol 202. detection sy stem 100 continues to scan pixel image 200 for other bar code sv mbols along other selected scan lines In a preferred embodiment means 108 instructs detection sy stem 100 to ignore the region of pixel image 200 containing detecte and decoded bar code symbol 202 while performing subsequent low-resolution quiet-zone scanning Thus detection sy stem 100 subsequently ignores potential quiet zones associated w ith bar code sv mb 202 For example, after completing scan line 270. detection system 100 mav scan at low resolution along scan line 258 In doing so. detection system 100 ignores both the potential quiet zone at point 256 and the potential quiet zone at point 236

Detection system 100 continues to scan pixel image 200 for other bar code symbols until means 120 determines that the last selected scan line has been completely scanned In the example shown, detection system 100 continues to select scan lines until each of the 14 grid lines 24 of Fig 2 has been selected

Detecting and Decoding Bar Code Svmbols in Continuous Images

In an alternativ e preferred embodiment, the detection system according to the present inv ention detects and decodes bar code symbols in continuous two-dimensional gray-scale pixel images generated with a video camera A video camera continues to generate new row s of image dat as long as the camera is operating Such a video camera may contain a linear CCD array, such as a 4096-pixel Linear Image Sensor Array (Model IL-C5-4096 "TURBOSENSOR") manufactured by DALSA Inc of Waterloo. Ontario, Canada For purposes of this specification, the image generated such a v ideo camera is defined to be continuous in that, although the image has a definite number of pixels per image row. there is an indefinite number of rows in the image Such a continuous image may be generated, for example, by mounting the video camera in a fixed overhead position, wherein the camera may be focused onto a continuously moving conveyor belt ly ing below the camera

The pixel data for such a continuous image may be stored in a circular image buffer that has enough room for a finite number of rows of image data Each new row of continuous imag data that is generated by the video camera is stored in the circular image buffer by replacing the olde row of continuous image data in the circular image buffer. For example, a video camera may generate image data having 4096 8-bit pixels per row and a circular image buffer may be able to store 1024 of such image rows. The continuous image generated by the video camera may have more than 1024 rows. but. at any given time, only the 1024 most recent rows of continuous image data are stored in the circular image buffer. Since the entire continuous pixel image is not retained indefinitely in memory, the system of the present invention preferably continuously processes the image data to ensure that each row of pixel data in the continuous image is processed before being overwritten in the circular image buffer.

Referring now to Figs. 19 and 20. there are shown graphical representations of a circular image buffer 1900 that is capable of storing 1024 rows of image data having 4096 pixels per row . As new image data is generated, the oldest rows of data in circular image buffer 1900 are overwritten with the new rows. In one preferred embodiment, the detection system of the present invention reads package labels containing bar code symbols that are about two to three inches long. The video camera in that preferred embodiment generates about 100 rows of image data for every one inch of the imaged label. In this preferred embodiment, once circular image buffer 1900 is initially filled, a 32-row subimage of the pixel image then stored in circular image buffer 1900 is selected and processed to detect bar code symbols within the circular image buffer. When bar code symbols are randomly oriented with respect to the continuous pixel image, each 32-rovv subimage will typically contain, at most, only a portion of a bar code symbol.

In order to process all image data before it is overwritten in circular image buffer 1900 by new data, the detection system must process data as quickly as. or preferably more quickly than, the video camera generates data. The detection system ensures that there is a sufficient offset or lag between the processing of the detection system and the image generation of the camera. If the detection system gets "too close" to the bottom of the continuous image, bar code symbols may be detected which are not entirely contained in the image buffer. Similarly, if the detection system lags the video camera too much, then the image data corresponding to a bar code symbol may be overwritten before the detection system detects and decodes that symbol.

To ensure that each bar code symbol can be efficiently decoded after being detected, the 32-row subimage selected for processing is preferably about 4 inches or about 400 rows from the "bottom" of the image stored in circular image buffer 1900. The continuous image wraps around circular image buffer 1900 as new rows replace the oldest rows of data. As a result, the "bottom" of the image moves within the circular buffer.

For example, in Fig. 19, after image rows 0 to 1023 of the continuous image are generated and stored in buffer rows 0 to 1023 of circular image buffer 1900, subimage 1902 is processed, where subimage 1902 comprises image rows 592 to 623 stored in buffer rows 592 to 623 of the circular image buffer 1900. Thereafter, as each new row of image data is generated, it is stored in circular image buffer 1900 by ov erwriting the oldest row of image data then stored in circular image buffer 1900 As show n in Fig 20. image row 1024 of the continuous image is stored by ov erwriting image row 0 of the continuous image in buffer row 0 of circular image buffer 1900 After image row s 1024 to 1055 of the continuous image are generated and stored in buffer row s 0 to 3 1 of circular image buffer 1900 (replacing old image row s 0 to 31 ). subimage 1904 is selected and processed Subimage 1904 comprises image rows 624 to 655 of the continuous image stored in buffer rows 624 to 655 of circular image buffer 1900 As such, the subimage selected for processing lags the "bottom" of the image by 400 ro s

The processing of each subimage (e g . subimage 1904 of Fig 20) preferably inv olves scanning for bar code sy mbols first along a row of the subimage (e g . row 655 of the continuous image for subimage 1904) from column 0 to 4095 and then sequentially along columns 16, 48. 80. . . 4080 through the subimage (e g . from row 624 to 655 of the continuous image for subimage 1904) As described in further detail later in this specification in coniunction w ith Figs 21 -27. this scanning for bar code sy mbols involves transition-based scanning for potential bar code sy mbols using circular transition buffers After each subsequent set of 32 new rows is generated and stored in circular image buffer 1900. another 32-row subimage in circular image buffer 1900 is selected and processed

Preferred Detection Sv stem for Continuous Images

Referring now to Fig 21, there is shown a process flow diagram of detection sy stem 2100 for detecting and decoding bar code symbols in continuous pixel images according to a preferred embodiment of the present invention Detection system 2100 continuously receives image data corresponding to a continuous two-dimensional gray-scale pixel image generated by a v ideo camera (not show n) Detection system 2100 stores the image data in a circular image buffer, such as buffer 1900 of Figs 19 and 20 As the camera continues to generate data, detection system 2100 successiv ely processes 32-rovv subimages of the stored image data by scanning along selected scan lines for potential bar code symbols. Detection system 2100 also decodes each detected potential bar code symbol Detection system 2100 may reside in and operate on a 16-MHz 386sx computer w ith a math co-processor or on a "SUPERCARD2" brand i860 CPU RISC processor, manufactured by CSP1

As described earlier in this specification in coniunction in Figs 19 and 20. detection system 2100 ensures that there is a sufficient offset or lag between subimage processed by detection system 2100 and the new rows of data generated by the camera and stored at the "bottom" of the image In a preferred embodiment of the present invention, means 2102 of detection system 2100 initializes a row pointer YROW. that identifies the subimage in the continuous pixel image to be processed by detection system 2100 Row pointer YROW is initialized according to Equation (1 ) as follows YROW = YDIM - YOFF - 1 , ( 1 )

where YDIM is the number of rows in circular image buffer 1900 (i.e.. preferably 1024) and row offset YOFF is the number of rows (i.e., preferably 400) between the subimage to be processed by detection system 2100 and the "bottom" of the image (i.e.. the lag between detection system 2100 and the video camera).

Means 2104 receives new image data from the video camera and stores that data in circular image buffer 1900. The camera pointer YCAM identifies the last row (i.e.. newest row) of the continuous image generated by the video camera and stored in buffer 1900. Means 2106 determines whether there is a sufficient offset or lag between detection system 2100 and the camera to process another subimage of the continuous image.

If camera pointer YCAM minus row offset YOFF is not greater than row pointer YROW. then the video camera is not leading detection system 2100 by a sufficient number of rows and processing returns to means 2104 to await the next row of image data from the camera. Otherw ise, the video camera does sufficiently lead detection system 2100 and means 2108 processes another set of data (or 32-row subimage) in circular image buffer 1900 by detecting and decoding bar code symbols in that subimage. After means 2108 processes the selected subimage. means 2110 increments row pointer YROW by the selected grid size (i.e., preferably 32). before returning processing to means 2104.

In the example of Fig. 19, row pointer YROW is initialized by means 2102 using Equation ( 1 ) to be ( 1024 - 400 - 1 ) or 623. Camera pointer YCAM is incremented for each new row of data generated by the video camera and stored by means 2104. For YCAM values from 0 to 1022. camera pointer YCAM minus YOFF (i.e., 400) is not greater than or equal to row pointer YROW (i.e.. 623 ) and means 2106 returns processing to means 2104. When YCAM is 1023. YCAM minus YOFF is equal to YROW and means 2108 processes a subimage. Means 2110 then increments row pointer YROW to be (623 + 32) or 655. Processing then returns to means 2104. The next subimage will be processed when YCAM reaches 1055. Detection subsystem continues to process subimages as long as the ideo camera continues to generate new data. Row pointer YROW and camera pointer YCAM are continuous counters that have no upper limits.

Processing Subimages in the Continuous Image

Referring no to Fig. 22, there is shown a process flo diagram of means 2108 of detection system 2100 of Fig. 21 for processing a subimage stored in circular image buffer 1900. Means 2108 scans through the subimage along selected scan lines for potential bar code symbols and decodes those detected symbols. In a preferred embodiment, means 2108 first selects an image row and then selects a sequence of image columns as the scan lines used to search for bar code symbols. In particular, means 2202 of means 2108 performs a horizontal scan tor potential bar code sy mbols along a selected image row In a preferred embodiment the row ) tor horizontal scanning is selected by Equation (2) as follows

Y = YROW MOD YDIM , ( 2 )

where YROW is the row pointer as defined earlier in the specification in coniunction with Fig 21. MOD is the modulo function, and YDIM is the number of rows in circular image buffer 1900 (I e . preferably 1024) Those skilled in the art w ill understand that row } is the row of circular image buffer 1900 containing row \ROW oϊ the continuous image Means 2202 scans along buffer row } from column 0 to column 4095 to detect potential bar code sy mbols as described in further detail later in this specification in coniunction w ith Fig 25 Means 2204 then decodes each of the potential bar code sy mbols detected along the selected image row

In a preferred embodiment where the grid size is 32 rows by 32 columns and there are 4096 columns of image data, means 2108 sequentially selects columns 16 48. 80 . 4080 for v ertical scanning Means 2206 begins the process of vertical scanning by initializing a column pointer XCOL which identifies the image column currently selected for vertical scanning Means 2206 preferably initializes column pointer XCOL to one-half of the grid size or 16

Means 2208 determines whether the processing of the current subimage is complete by comparing column pointer XCOL to XDIM, the number of columns in the image (i e . preferably 4096) If XCOL is greater than or equal to XDIM, then scanning through the current subimage is complete and processing returns to means 2110 of Fig. 21 Otherwise, the processing of the current subimage is not complete and processing continues to means 2210 of Fig 22

As described earlier in this specification in conjunction with Figs 19 and 20. detection sy stem 2100 processes image data one subimage at a time, where each subimage preferably has 32 rows and 4096 columns of data To make processing efficient, detection system 2100 sav es the processing results for each selected column of the previously selected subimage in a dedicated memorv buffer (called a circular transition buffer) for use in processing the current subimage Means 2210 retrieves the appropriate transition-buffer data for the currently selected image column XCOL

Means 2212 then performs a vertical scan for potential bar code sy mbols through the currently selected subimage along the selected column XCOL In a preferred embodiment, means 2212 scans along column XCOL starting at row F₀ defined by Equation (3 ) as follows

Y_Ό = ( YROW - GRIDSIZE) MOD YDIM , ( 3 )

where GRIDSIZE is preferably 32 and YROW and YDIM are as defined above for Equation (2) Means 2212 continues to scan along column XCOL from row ) _n to row }. as defined by Equation (2) above Means 2214 decodes each of the potential bar code symbols detected along column XCOL Means 2216 then increments the column pointer XCOL by GRIDSIZE and returns processing to means 2208 to determine whether another image column is to be scanned

In a preferred embodiment, means 2204 and 2214 decode each potential bar code symbol using processing similar to that employed by means 108. 110 112. 114. and 116 of Fig 1. as described in further detail earlier in this specification

Transition-Based Scanning for Potential Bar Code Svmbols

A bar code symbol is a ide bright quiet zone followed by a sequence of narrow dark bars and narrow bright spaces followed by another a wide bright quiet zone To detect and decode bar code sy mbols in some pixel images, a fixed threshold value mav be used to distinguish bright pixels (corresponding to spaces and quiet zones) from dark pixels (corresponding to bars) However, in some images of bar code sv mbols. there are variations in the dynamic range of pixel intensities across the pixel image These v ariations may be due. for example, to non-uniform illumination of a label containing the bar code sy mbol and/or to a non-uniform response across the CCD-based v ideo camera used to generate the pixel image

As depicted in Fig 23. this dynamic range variation may be so great that some pixels corresponding to "dark" bars have intensity levels greater than the intensity levels of other pixels that correspond to "bright" spaces In such situations, a fixed threshold value cannot be used to identify accurately all of the bars and spaces of a bar code symbol

In addition, as depicted in Fig 24. the response of a CCD-based v ideo camera may be such that the intensities of pixels in a wide bar are darker than the intensities of pixels in a narrow bar Similarly , the intensities of pixels in a wide space may be brighter than the intensities of pixels in a narrow space The image may also contain noise resulting in valleys and peaks (i e . critical points) in the pixel data that do not represent individual bars and spaces of the bar code symbol

Giv en these characteristics of some pixel images of bar code symbols, the pixel intensity data along a scan line through a bar code symbol is preferably characterized as a relatively wide, relatively bright region (i e., the first quiet zone) followed by a relatively dense sequence of interleaved bπght-to-dark and dark-to-bright transitions of sufficient magnitude (I e . corresponding to the edges of bars in the bar code symbol) followed by another relatively wide, relatively bright region (i e.. the second quiet zone) Under this characterization, one edge of a bar may be identified as being a bπght-to-dark transition of sufficient magnitude and the other edge of a bar may be identified as being a dark-to-bπght transition of sufficient magnitude

Referring now to Fig. 25, there is shown a process flow diagram of means 2500 for scanning along a selected scan line for potential bar code symbols according to a preferred embodiment of the present invention Means 2500 may be used to perform either horizontal scanning along a selected image row or vertical scanning along a selected image column Means 2500 is a preferred embodiment of means 2202 and 2212 of means 2108 of detection sy stem 2100 as depicted in

As described in further detail later in this specification in coniunction with Figs 26 and 2⁷. means 2500 scans along the selected scan line for potential bar code svmbols by identify ing and storing the locations of bright-to-dark and dark-to-bπght transitions These transition locations are stored in circular transition buffers When means 2500 performs a horizontal scan along a selected image row means 2500 scans across the entire row from column 0 to column 4095 As such, for each new horizontal scan, means 2500 starts with an empty circular transition buffer

On the other hand, when means 2500 performs a v ertical scan along a selected image column, means 2500 scans onlv the portion of that image column corresponding to the currently selected 32-row subimage For each vertical scan, means 2500 uses the transition data stored in the circular transition buffer for that column from the processing of the prev ious subimage Thus, the circular transition buffers for vertical scans are empty only when the v erv first subimage (i e . subimage 1902 of Fig 19) is processed by detection system 2100

Means 2502 of means 2500 receives the initial position for the current scan line and the appropriate circular transition buffer For a horizontal scan the initial position is preferably column 0 and row } (as determined by Equation (2) above) For a vertical scan, the initial position is preferably column XCOL (as defined earlier in conjunction with Fig 22) and row }₀ (as determined by Equation (3 ) above)

If the circular transition buffer is empty, means 2504 directs processing to means 2506 to initialize the circular transition buffer by storing the current position (I e . the initial position) as the first transition (even though the current position may not correspond to a true transition) Those skilled in the art will understand that this initialization is intended to handle the situation where scanning begins at a position corresponding to a pixel falling w ithin a quiet zone of a bar code symbol Means 2506 is implemented at the start of horizontal scanning along each selected row for each subimage and once for each selected column during vertical scanning of the very first subimage

Means 2508 then selects the next scan position along the selected scan line by incrementing the appropriate pointer (I e . the column pointer for horizontal scans and the row pointer for v ertical scans) by the specified scan increment STEP In a preferred embodiment. STEP is two. so that means 2500 scans along the selected scan line by analyzing every other pixel Those skilled in the art will understand that, during vertical scanning, the incremented row pointer must be adjusted by MOD YDIM to account for wrapping around circular image buffer 1900 Those skilled in the art will also understand that the value selected for STEP may depend on the resolution of the pixel image relative to the expected size of bar code symbols m that image The value for STEP may be selected empirically Means 2510 then determines whether the current scan position corresponds to a transition. The current scan position corresponds to a transition when the magnitude of the difference in pixel intensity level between the next scan position and the current scan position is greater than a specified transition threshold T_na . That is, for a horizontal scan, if:

ABS ( IMAGE [X+STEP, Y) - IMAGE [X, Y] ) > T_zzaτiS , (4 )

then current scan position [X. Y] corresponds to a transition. The value specified for transition threshold 7_tra-s depends on the dynamic range of the images generated with the video camera and may be selected empirically . In a preferred embodiment having 8-bit pixel intensity levels, transition threshold T_ttm, is typically selected to be a value between 20 and 40.

If the intensity -level difference between the two positions is of sufficient magnitude and is also negative, then the current position corresponds to a bright-to-dark transition and a flag is set to - 1. If the intensity-level difference between the two positions is of sufficient magnitude and is also positive, then the current position corresponds to a dark-to-bright transition and the flag is set to + 1 .

If means 2510 detects a transition, then means 2512 processes the transition by recording the transition in the appropriate circular transition buffer and then analyzing the data stored in that transition buffer to determine whether the data corresponds to a potential bar code symbol. The processing of means 2512 is described in further detail later in this specification in conjunction with Figs. 26 and 27. Regardless of whether means 2510 detects and means 2512 processes a transition at the current scan position, means 2514 selects the next scan position identically to the processing of means 2508.

Means 2516 then determines whether scanning along the current scan line for potential bar code symbols is concluded. A horizontal scan is concluded when the column pointer is greater than or equal to XDIM, indicating that the scan has reached the right side of the image. A vertical scan along a selected image column is concluded after the 32-row subimage has been scanned, again adjusting if necessary for wrapping around the circular image buffer. If scanning along the currently selected scan line is not yet complete, then means 2516 directs processing to return to means 2510 to check for another transition. Otherwise, processing proceeds to means 2518.

At the completion of scanning along each selected scan line, means 2518 processes the last scan position as if it were a transition, whether or not it corresponds to an actual transition. Those skilled in the art will understand that this processing is intended to handle the situation where scanning ends at a position corresponding to a pixel falling within a quiet zone of a bar code symbol. Means 2518 functions identically to means 2512. For vertical scanning, after means 2518 adds the last scan position to the circular transition buffer and analyzes the buffer for potential bar code symbols means 2520 remov es that last transition from the buffer to correct the buffer data for later processing of the next 32-row subimage

Processing Identified Transitions

Referring now to Fig 26. there is shown a process flow diagram of means 2512 of means 2500 of Fig 25 for processing an identified transition according a preferred embodiment of the present invention Means 2602 of means 2512 stores the current scan position at the appropriate location w ithin the appropriate circular transition buffer The size of the circular transition buffers is preferablv 16 and each circular transition buffer contains the information regarding the last 16 transitions that were detected along the corresponding scan line

Means 2602 stores a value for the new transition in the circular transition buffer by replacing the v alue for the oldest transition As the data wraps around the circular transition buffer a transition-buffer pointer keeps track of the location of the oldest transition data in the buffer ( i e the location where the newest transition data is to be written) The value recorded for each transition is the product of the position of the transition along the selected scan line and the flag that indicates whether the transition is a dark -to-bright transition or a bright-to-dark transition

That is. if a bπght-to-dark transition is detected at scan position \ \' Y] during a horizontal search along row Y. then means 2602 stores the value -X at the appropriate location in the circular transition buffer for horizontal scans Similarly, if a dark-to-bπght transition is detected at scan position [XCOL } ] during a vertical search along column XCOL. then means 2602 stores the v alue ) at the appropriate location in the circular transition buffer for column XCOL

Means 2604 then analyzes the data in the circular transition buffer to determine whether the data corresponds to a potential bar code symbol The processing of means 2604 is described in further detail later in this specification in conjunction ith Fig 27 If means 2604 does detect a potential bar code symbol, then that potential bar code symbol is added to a list or stack for subsequent decoding In a preferred embodiment, detection system 2100 completes the scanning along the currently selected scan line before proceeding to decode each of the potential bar code symbols detected along that scan line

Analyzing Circular Transition Buffers for Bar Code Svmbols

Referring now to Fig 27, there is shown a process flow diagram of means 2604 of means 2512 of Fig 26 for determining whether the data in a circular transition buffer corresponds to a potential bar code symbol, according to a preferred embodiment of the present inv ention A quiet zone of a potential bar code symbol may be characterized as a relatively wide bright region adjacent to a sufficiently dense sequence of bright-to-dark and dark-to-bπght transitions (corresponding to the sequence of bars and spaces at one end of the potential bar code symbol). Depending on the scan direction and the orientation of the bar code symbol, the bright region may either lead or follow the sequence of transitions.

In accordance w ith the present invention, the transition at a pixel / w ill correspond to a transition from a potential quiet zone to an outer bar (i.e.. either the first bar or last bar) of a potential bar code sy mbol, if:

( 1 ) The transition at pixel ; is a bright-to-dark transition.

(2 ) The transitions immediately following pixel / occur with sufficient density (i.e.. a specified number of transitions foi owing pixel / occur within a specified density threshold distance); and

(3 ) The distance between pixel i and the transition immediately preceding pixel / is greater than a specified quiet-zone threshold distance

Similarly, the transition at a pixel / corresponds to a transition from the outer bar of a bar code symbol to a potential quiet zone, if

( 1 ) The transition at pixel j is a dark-to-bright transition:

(2 ) The transitions immediately preceding pixel j occur with sufficient density (i.e.. a specified number of transitions preceding pixel / occur within a specified density threshold distance); and

(3) The distance between pixel j and the transition immediately following pixel / is greater than a specified quiet-zone threshold distance.

In a preferred embodiment of the present invention, means 2604 of Fig. 27 applies the above tests to the data in the circular transition buffer to determine whether that data corresponds to a potential bar code sy mbol Specifically, means 2604 applies the first set of three tests (i.e.. those described above for pixel /) to the second oldest transition in the circular transition buffer to determine whether that transition corresponds to a potential quiet zone followed by a potential bar code sy mbol Means 2604 also applies the second set of three tests (i.e., those described above for pixel j) to the second newest transition in the circular transition buffer to determine whether that transition corresponds to a potential bar code symbol followed by a potential quiet zone.

More particularly , means 2702 of means 2604 determines whether the circular transition buffer is full. If not. then the analysis is not performed and means 2720 indicates that a potential bar code symbol has not been detected. A circular transition buffer ill not be full only near the beginning of the corresponding scan line. Once a circular transition buffer is full, it remains full throughout the scanning along the corresponding scan line. Thus, the horizontal circular transition buffer will not be full near the beginning of each horizontal scan along each selected image row . The vertical circular transition buffers, however, will not be full only while the first few 32-row subimages are processed. After that, they will remain full throughout the processing of the continuous image. In a preferred embodiment, a buffer pointer CIRC COUNT identifies the oldest transition in a circular transition buffer BUFF, which is of buffer size BUFF SIZE. When BUFF SIZE is 16. CIRC COUNT varies from 0 to 15. In general, the data for the oldest transition is recorded at:

BUFF [CIRCJCOUNT] . the data for the second oldest transition is recorded at:

BUFF [(CIRC_JCOUNT + 1 ) MOD BUFF SIZE] , the data for the newest transition is recorded at:

BUFF [( CIRCJCOUNT + BUFF SIZE - 1 ) MOD BUFF SIZE] . and the data for the second newest transition is recorded at:

BUFF [(CIRC_COUNT + BUFF SIZE - 2 ) MOD BUFF SIZE] . w here the modulo function MOD keeps track of wrapping around the circular transition buffer. For example, when CIRC COUNT is 1 , the oldest transition data is recorded at:

BUFF [\ ] . the second oldest transition data is recorded at:

BUFF [( 1 + 1 ) MOD 16] = BUFF [2], the newest transition data is recorded at:

BUFF [( 1 + 16 - 1 ) MOD 16] = BUFF [0] . and the second newest transition data is recorded at:

BUFF [(\ + 16 - 2) MOD 16] = BUFF [15] . If the circular transition buffer is full, then processing continues to means 2704. Means 2704 determines whether the second oldest transition in the circular transition buffer is a bright-to-dark transition by applying the following test:

BUFF [(CIRC_COUNT+ I ) MOD BUFF SIZE] < 0 . If the second oldest transition is not a bright-to-dark transition, then processing continues to means 2712: otherwise, processing continues to means 2706.

Means 2706 applies a density test that determines whether the distance between the newest transition and the second oldest transition is less than a specified density distance threshold BAR TLENGTH by applying the following test:

ABS (BUFF [(CIRCJCOUNT + BUFF SIZE - 1 ]) MOD BUFF SIZE]) - ABS (BUFF [(CIRCJCOUNT + 1 ) MOD BUFF SIZE]) < BAR TLENGTH , where ABS is the absolute value function and BAR TLENGTH is preferably 80. If the second oldest transition does not pass this density test, then processing continues to means 2712: otherwise, processing continues to means 2708. Means 2708 applies a quiet-zone test that determines whether the distance between the second oldest transition and the oldest transition is greater than a specified quiet-zone distance threshold OT_LENGTH ^'by applying the following test:

ABS (BUFF [(CIRCJCOUNT + 1 ) MOD BUFF SIZE]) - ABS (BUFF [CIRCJCOUNT]) > QT_LENGTH . where QT_LENGTH is preferably 20. If the second oldest transition does not pass this densit test, then processing continues to means 2712: otherwise, means 2710 indicates that the second oldest transition does correspond to a potential bar code symbol.

Means 2712 determines whether the second newest transition in the circular transition buffer is a dark-to-bright transition by applying the following test:

BUFF [(CIRCJCOUNT* BUFF SIZE - 2) MOD BUFF SIZE] > 0 . If the second newest transition is not a dark-to-bright transition, then means 2720 indicates that a potential bar code symbol has not been detected: otherwise, processing continues to means 2714.

Means 2714 applies a density test that determines whether the distance between the second newest transition and the oldest transition is less than the specified densitv distance threshold BAR TLENGTHby applying the following test:

ABS (BUFF [(CIRCJCOUNT + BUFFJSIZE - 2) MOD BUFFJSIZE] - ABS (BUFF [CIRCJCOUNT]) < BAR TLENGTH . If the second newest transition does not pass this density test, then means 2720 indicates that a potential bar code symbol has not been detected: otherwise, processing continues to means 2716.

Means 2716 applies a quiet-zone test that determines whether the distance between the newest transition and the second newest transition is greater than the specified quiet-zone distance threshold OT LENGTH ^' by applying the following test:

ABS (BUFF [(CIRCJCOUNT + BUFFJSIZE - 1 ) MOD BUFFJSIZE]) -

ABS (BUFF [(CIRCJCOUNT + BUFFJSIZE - 2) MOD BUFFJSIZE])

> QTJLENGTH . If the second newest transition does not pass this density test, then means 2720 indicates that a potential bar code symbol has not been detected: otherwise, means 2718 indicates that the second newest transition does correspond to a potential bar code symbol.

Those skilled in the art will understand that when the circular image buffer and the circular transition buffers are integer powers of 2, all modulo functions can be optimized as bit manipulations of binary-encoded values. In a preferred embodiment, circular image buffer 1900 has YDIM= 2'° = 1024 rows and each circular transition buffer stores BUFF SIZE = 2⁴ = 16 transitions.

Those skilled in the art will also understand that the values of the various parameters and thresholds used in these examples are presented for descriptive purposes. In a preferred embodiment, detection system 2100 is parameter-driven w ith the selection of parameter v a'ues to be made by the user based on the particular application and if necessarv on an empirical basis

Identify ing Bar Code Svmbol Start/Stop Characters

Referring now to Fig 3, there is shown a process flow diagram of start stop characte identification subsystem 110 of detection system 100 for identifying bar code sy mbol start/stop characters according to a preferred embodiment of the present invention Identification subsystem 11 searches at high resolution for a start/stop character along the selected scan line in the direction dictated by the type of state transition detected by means 106 of detection sy stem 100 If a reference star stop character is identified then identification subsy stem 110 v erifies that identification by searching for the same start/stop character along search lines parallel to the selected scan line

Means 302 is prov ided for generating a first sequence of symbol element w idths for detecting a bar code sy mbol start/stop character along the selected scan line Each element in the sequence has an element w idth and is either a bar or a space Means 302 deriv es the element idths of the sequence from signal energy values generated during subpixel interpolation along a portion of the selected scan line Subpixel interpolation is described in further detail later in this specification coniunction w ith Figs 14 and 15

Searching for a start/stop character preferably starts at the state transition point used t detect the potential quiet zone Each reference start/stop character in a reference table has a unique sequence of element w idths, and different bar code symboiogies may have start/stop characters of different numbers of symbol elements Means 302 preferably generates a first sequence of ;; element w idths. w here n corresponds to the number of symbol elements in the reference start'stop character in the reference table w ith the largest number of symbol elements

For example, if detection system 100 is used to detect and decode only Code 128 bar code svmbols. then means 302 preferably generates a first sequence of 5 element w idths In Code 128. a start character has 6 elements (3 bars and 3 spaces) and a stop character which includes the termination bar has 7 elements (4 bars and 3 spaces) However, the start and stop characters in Code 128 can be uniquely identified by characterizing the widths of only the first 5 elements For the Cod 128 start character, the 5 elements characterized are the three bars and the two spaces bounded by those three bars For the Code 128 stop character, the 5 elements characterized are the termination bar, the two bars closest to the termination bar, and the two spaces bounded by those two bars and th termination bar Since a potential start stop character may be either a start or a stop character of Cod 128. means 302 generates a first sequence of 5 element widths

The portion of the selected scan line along which means 302 performs subpixel interpolation to generate the first sequence of element widths starts at the state transition point and continues until a sequence of n element widths is generated If the end of the selected scan line is reached before all n element widths are determined, then the current state transition point does not correspond to a reference start/stop character. In addition, if a "bar" or "space" is too wide to correspond to an element of the expected bar code symbols, then generation of the sequence of element widths may be stopped and no start/stop character is identified.

Means 304 compares the first sequence of element widths with the reference start 'stop characters. If means 304 determines that the first sequence does not match any of the reference start/stop characters, then no bar code symbol start/stop character is identified and processing is directed to means 118 of detection system 100 of Fig. 1 . Matching between sequences of element widths and reference start stop characters is preferably based on confidence factors as described in further detail later in this specification in conjunction with Fig. 16.

If. however, means 304 determines that the first sequence does match a reference start/stop character, then means 306 generates a second sequence of element widths by performing subpixel interpolation along a first verification search line parallel to and near the selected scan line. In a preferred embodiment, the first verification search line is displaced from the selected scan line by a few pixels. Means 308 determines if the second sequence of element widths matches the same reference start stop character identified by means 304. If the second sequence does match the same reference start stop character, then the start/stop character identified by means 304 is confirmed and processing continues to location subsystem 112 of detection system 100 of Fig. 1 with a confirmed bar code symbol identification.

If means 308 does not confirm the reference start/stop character identification made by means 304. then a second confirmation is attempted by means 310 and means 312. Means 310 and means 312 function substantially in accordance with means 306 and means 308. respectively , except that a second verification search line is analyzed. The second verification search line is positioned on the side of the selected scan line opposite the first verification search line. If means 312 confirms the start/stop character identified by means 304, then processing continues to location subsystem 112 of detection system 100 of Fig. 1 with a confirmed bar code symbol identification. Otherwise, identification subsystem 110 identifies no bar code symbol stop/start character and processing is directed to means 118 of detection system 100 of Fig. 1.

Referring again to the example of Fig. 2. after detection system 100 detects a potential quiet zone at point 224 along scan line 270, means 302 of identification subsystem 110 performs subpixel interpolation along scan line 270 to generate a first sequence of element widths. If means 304 determines that the first sequence matches a reference start/stop character, means 306 then performs subpixel interpolation along first verification search line 222 to generate a second sequence of element widths. If means 308 determines that the second sequence confirms the start/stop character identified by means 304, means 308 then directs processing to location subsystem 112 of detection system 100 of Fig. 1 with a confirmed start/stop character. If the second sequence does not match the same reference start'stop character identified by means 304. then means 310 performs subpixel interpolation along second v erification search line 228 to extract a third sequence of element widths Means 312 then determines w hether th third sequence confirms the start'stop character identified by means 304 A start stop character may identified by means 304 and not confirmed by either means 308 or means 312 for v arious reasons The identification by means 304 may be a false positive, identifying a bar code symbol where there i none Alternatively , a bar code symbol may be present, but it may be degraded in the pixel image Such degradation may be caused by phy sical defects in the label carry ing the bar code symbol or by defects introduced during the creation of the pixel image of that label

Locating the Four Corners of a Bar Code Svmbol

Referring now to Fig 4, there is shown a process flow diagram of four-comer locatio subsystem 112 of detection sy stem 100 for locating the four co ers of a bar code symbol according t a preferred embodiment of the present invention Location subsy stem 112 begins by locating two comers of the start/stop character identified by subsystem 110 These two corners correspond to tw o comers of the first or outside bar of that first start stop character Location subsystem 112 then attempts to find the other end of the bar code symbol by searching for the second quiet zone and the second start/stop character associated with the bar code symbol If the second quiet zone and second start/stop character are successfully found, location subsystem 112 locates the last two comers of the bar code symbol These two corners correspond to two co ers of the outside bar of the second start'stop character Each comer is defined by the position of the pixel in the pixel image that contains that comer of the bar code symbol.

Means 402 locates the first two corners of the identified bar code symbol, that is. those at the top and bottom of the outside bar of the start/start character identified by identification subs stem 110 Means 402 is described in further detail later in this specification in conjunction w ith Fig 6 After the first two corners are found, means 404 determines the location of a line that bisects and is perpendicular to the line that connects the first two comers Means 404 performs a low- resolution quiet-zone scan across the detected bar code symbol along the perpendicular bisecting line for the second quiet zone at the other end of the symbol.

Means 406 determines whether that second quiet zone is found by looking for a continuous sequence of n bright pixels along the perpendicular bisecting line, where ;; is greater than the second threshold The second threshold was described earlier in this specification in conjunction with Fig 1 If the second quiet zone is not found, then the four corners are not located and means 406 directs processing to means 118 of detection system 100 of Fig 1 If means 406 finds the second quiet zone, then means 408 performs subpixel interpolation along a first search line to generate a first sequence of element widths. This first search line may be a pixel row or column that intersects the perpendicular bisecting line at the edge of the second quiet zone.

Means 410 determines whether the first sequence of element w idths gercrated means 408 matches the start'stop character that complements the start/stop character identified by identification subsystem 110. Bar code symbols contain unique start/stop characters that indicate the type of bar code symbologv Ev ery bar code symbol has a pair of complementary start and stop characters, each of which identifies the symbology of the bar code symbol Therefore, once a first start'stop character is identified at one end of a bar code symbol, the second start/stop character at the other end of the bar code symbol must complement the first start/stop character before a bar code symbol identification can be confirmed For example, in Code 128. there are three different start characters and one stop character If one of the three Code 128 start characters is identified, then the complementary stop character is know n Similarly , if the Code 128 stop character is identified, the complementary start character must be one of the three possible Code 128 start characters.

If means 410 determines that the first sequence of element widths generated by means 408 matches the complementary start/stop character, then the second start/stop character is confirmed and means 420 finds the last two comers of the detected bar code symbol, that is. those that define the top and bottom of the outside bar of the second start/stop character. Means 420 functions substantially in accordance with means 402 and is described in further detail later in this specification in conjunction with Fig 6 Following means 420, processing continues with decoding subsystem 114 of detection system 100

If the first sequence of element widths generated by means 408 does not match the complementary start/stop character, means 412 performs subpixel interpolation along a second search line to generate a second sequence of element widths. The second search line may be parallel to and near the first search line In a preferred embodiment, the second search line is parallel to and displaced from the first search line by a few pixels. Means 414 then determines whether the second sequence matches the complementary start/stop character. If so. then processing continues to means 420 for location of the other two corners of the bar code symbol. Otherwise, means 416 generates a third sequence of element w idths by performing subpixel interpolation along a third search line positioned on the side of the first search line opposite the second search line Means 418 then determines whether the third sequence matches the complementary start/stop character If so, processing continues to means 420 for location of the other two comers of the bar code symbol Otherwise, the complementary start/stop character is not identified, the four corners of the bar code symbol are not located, and processing returns to means 118 of detection system 100

Referring again to the example of Fig. 2. after detection system 100 identifies and confirms a first start/stop character of bar code symbol 202 at point 224 along scan line 270. means 402 of four-comer location subsystem 112 locates co ers 214 and 230 Means 404 determines the location of line 220 which bisects and is perpendicular to the line between co ers 214 and 230 at point 218. Means 404 then scans at low-resolution across bar code symbol 202 along line 220 for the second quiet zone at the other end of bar code symbol 202. Means 406 locates the second quiet zone follow ing point 248 by detecting a continuous sequence of bright pixels longer than the second threshold at that position. Means 408 then performs subpixel interpolation along search line 252 from left to right to generate a first sequence of element widths. Means 410 may then determine that the first sequence matches the complement of the first start/stop character. In that case, means 420 finds comers 246 and 260. If means 410 determines that the first sequence does not match the complementary start/stop character, then location subsystem 112 would attempt to identify the complementary start'stop character using means 412 and 414 along search line 254. and. if necessary , using means 416 and 418 along search line 250.

Locating Two Comers of a Bar Code Svmbol

Referring now to Fig. 5. there is shown a graphical representation of sub-image 500 of pixel image 200 of Fig. 2. Each square in Fig. 5 represents a pixel (/._/) in pixel image 500 identified by column index / and row index /, where ;^' and y run from 0 to 15. Pixel row 6 in Fig. 5 corresponds to scan line 270 of Fig. 2. and pixel (13,6) corresponds to point 224 of Fig. 2. Pixels not ly ing on the outside edges of pixel image 200 have eight neighbors. For example, the neighbors of pixel ( 13.6) are pixels ( 13.5). ( 14.5), ( 14.6), ( 14.7), ( 13,7), (12,7). (12.6). and ( 12.5).

Pixels in Fig. 5 have a black dot if their gray-scale intensity level is less than or equal to the first threshold. Similarly , pixels in Fig. 5 have no black dots if their intensity level is greater than the first threshold. As described earlier in this specification in conjunction w ith Fig. 1. the first threshold may be determined from the histogram of the pixel image generated by means 102 of detection system 100. Pixels shown with a black dot may form part of a bar in bar code symbol 202 Pixels shown without a black dot may form part of spaces in bar code symbol 202.

Referring now to Fig. 6, there is shown a process flow diagram of two-co er location subsystem 600 for locating two co ers of a bar code symbol according to a preferred embodiment of the present invention. Means 402 and means 420 of four-comer location subsystem 112 of Fig. 4 function substantially in accordance with two-comer location subsystem 600 Location subsystem 600 finds two comers of a detected bar code symbol by sliding along the "outside edge" of a bar that forms an outside symbol element of a start/stop character to find the outside corners of that bar. The "outside edge" of a bar that forms an outside symbol element of a given start/stop character is positioned where the start/stop character and its associated quiet zone meet.

In order to facilitate explanation, location subsystem 600 is described in the context of the example of Figs. 2 and 5. After detection system 100 identifies a start/stop character of bar code symbol 202 in pixel image 200. location subsystem 112 activates means 402 to locate comers 214 and 230. After finding the complementary start/stop character, location subsystem 112 activates means 420. which then locates co ers 246 and 260.

Location subsystem 600 receives as an input the "original seed pixel." An original seed pixel is a pixel in a quiet zone that abuts a start/stop character. An original seed pixel may be determined by identification subsystem 110 or location subsystem 112. An original seed pixel preferably is a bright pixel that forms part of a quiet zone and is immediately adjacent to a dark pixel that forms part of the first or outside bar of one of the two start/stop characters of a detected bar code symbol. In the example of Fig. 2. the original seed pixel corresponds in location to point 224 and is represented by pixel (13.6) in Fig. 5.

Location subsystem 600 also receives as input the search direction in which detection system 100 searched for the start/stop character associated with the original seed pixel. In a preferred embodiment, there are four possible search directions: east. west, north, and south, corresponding to searching along pixel rows and columns. These four directions, along with the four intermediate directions northeast, southeast, southwest, and northwest, are defined in Fig. 5. Each of the eight neighbors of the current seed pixel has a unique direction relative to the current seed pixel. In the example of Fig. 5. the search direction received by location subsystem 600 is west, since the high- resolution search for the stop/start character adjacent to point 224 along line 270 proceeded from east to west.

Location subsystem 600 finds a comer by sliding along the outside edge of the first bar of a start'stop character in search of the co er. Location subsystem 600 slides along the outside edge of the bar by replacing the current seed pixel with a next seed pixel after analyzing the neighbors of the current seed pixel in either a clockwise or counterclockwise sequence orientation. A selected sequence orientation of clockwise results in location of one of the two comers of the first bar of the start'stop character, while a selected sequence orientation of counterclockwise results in location of the other co er. Since location subsystem 600 eventually locates both comers, location subsystem 600 uses both the clockwise sequence orientation to locate one comer and the counterclockwise sequence orientation to locate the other comer. It does not matter which sequence orientation is selected first. The selection of a next seed pixel based on a current seed pixel using a clockwise or counterclockwise sequence orientation is described in further detail later in this specification in conjunction with Fig. 7.

After the original seed pixel and the search direction are received by location subsystem 600 as inputs, means 602 selects a clockwise sequence orientation to be used in the selection of a next seed pixel from a current seed pixel. Means 604 then sets the current seed pixel equal to the original seed pixel and means 606 starts the list of selected seed pixels. Location subsystem 600 maintains a list of the last n pixels selected as seed pixels, where n is preferably 5. Means 606 starts growing the list of selected seed pixels with the original seed pixel. Seed pixel selection subsystem 608 selects the next seed pixel from the current seed pixel based on the selected sequence orientation (1 e . clockwise or counterclock ise) and the search direction Seed pixel selection subsystem 608 is described in further detail later in this specification conjunction with Fig 7 Means 610 then updates the list of selected seed pixels bv adding the curre seed pixel to the end of the list and means 612 sets the current seed pixel to be the next seed pixel After the list of selected seed pixels reaches the preferred length of 5 pixels, means 610 updates the list bv adding the current seed pixel to the end of the list and deleting the first seed pixel in the list

If means 614 determines that the length of the list of selected seed pixels is less than the preferred threshold of 5, then processing returns to seed pixel selection subsv stem 608 to select th next seed pixel Other ise, means 616 creates a current vector The current vector is determined bv translating to the origin the v ector from the first seed pixel in the list of selected seed pixels to the la seed pixel in the list where the origin may be any pixel in the pixel image If means 618 determine that the current vector is the first vector generated by location subsv stem 600 for the selected sequen orientation, then means 620 sav es the current vector as a reference vector before proceeding to means 622 otherw ise, processing proceeds directly to means 622

Means 622 calculates the magnitude of the vector difference between the current v ector and the reference vector If means 624 determines that that magnitude is less than a specified third threshold, a corner has not yet been detected and processing returns to seed pixel selection subsy stem 608 Otherwise, a comer has been detected and means 626 selects a pixel corresponding t that detected comer If means 628 then determines that the detected comer is only the first of the tw co ers to be located, then means 630 selects a counterclockwise sequence orientation and processing returns to means 604 to start the search for the second comer To search for the second comer w ith counterclockwise sequence orientation, means 604 returns to the original seed pixel as the current see pixel and means 606 starts the list of selected seed pixels over again w ith only the original seed pixel Other ise, if means 628 determines that the just-detected comer is the second corner, then both co ers hav e been located and location subsystem 600 is complete

Those skilled in the art will understand that location subsystem 600 may detect corner of bar code symbols using measures other than the magnitude of the v ector difference For example in an alternative preferred embodiment, means 622 calculates the magnitude of the angle between the current v ector and the reference vector This may be referred to as the phase of the vector difference Means 624 then tests this phase against a selected phase threshold If the phase is less than the phase threshold, then a comer has not yet been detected, otherwise, a corner has been detected

Selecting a Next Seed Pixel from a Current Seed Pixel

Referring now to Fig 7, there is shown a process flow diagram for seed pixel selection subsystem 608 for selecting a next seed pixel from a current seed pixel according to a preferred embodiment of the present invention. Selection subsystem 608 forms part of two-comer location subsystem 600. Selection subsystem 608 selects the next seed pixel from the eight neighboring pixels of the current seed pixel. Like the current seed pixel, the next seed pixel forms part of the quiet zone In addition to being a neighbor of the current seed pixel, the next seed pixel lies immediately adjacent to another neighbor of the current seed pixel, w hich other neighbor forms part of the outside bar of the start/stop character.

If the intensity levels of two pixels are both less than or equal to the first threshold, they are considered "similar." because they may both form parts of one or more bars Two pixels are also considered similar if their intensity levels are both greater than the first threshold, because they may both form parts of one or more spaces. For example, in Fig 5. pixels ( 12.6) and (1 1.6) are similar to each other, as are pixels (12,7) and (13.6). but not pixels (12.6) and (13.6).

Selection subsystem 608 receives as input the current seed pixel, search direction, and the selected sequence orientation The selected sequence orientation may be either clockwise or counterclockwise Selection subsystem 608 analyzes neighbors of the current seed pixel in either clockw ise or counterclockw ise sequence orientation to determine the next seed pixel After the input is received, means 702 of selection subsystem 608 sets the current neighbor to be the neighbor in the search direction from the current seed pixel. For example, if the search direction is west, means 702 selects the west neighbor of the current seed pixel as the current neighbor

Means 704 determines whether the current neighbor is similar to the current seed pixel, that is. hether they are both bright pixels that may form part of a quiet zone If so. then, before proceeding to means 708. means 706 temporarily reverses the selected sequence orientation for neighbor analysis, that is. from clockwise to counterclockwise or from counterclockwise to clockw ise, whichev er orientation is appropriate This reversal of the selected sequence orientation is temporary in that the reverse sequence orientation is retained only until processing of selection subsystem 608 is complete When processing returns to location subsystem 600. the sequence orientation reverts back to what it was when selection subsystem 608 was implemented. Otherwise, if the current neighbor is not similar to the current seed pixel, processing proceeds directly to means 708

Means 708 selects the next neighbor by moving around the current seed pixel in the selected sequence orientation from the current neighbor in 45-degree increments For example, if the current neighbor is the west neighbor and the selected sequence orientation is clockwise, then means 708 selects the northwest neighbor to be the next neighbor. Similarly, if the current neighbor is west neighbor and the selected sequence orientation is counterclockwise, then the southwest neighbor is selected as the next neighbor.

If means 710 determines that the next neighbor is similar to the current neighbor, then the next seed pixel has not yet been found. In that case, means 712 sets the current neighbor to be the next neighbor and processing returns to means 708 to select the next neighbor Otherwise, means 714 determines whether the next neighbor is similar to the current seed pixel If so then means 716 selects the next seed pixel to be the next neighbor Otherwise, means 718 selects the next seed pixel to be the current neighbor In either case, the next seed pixel is selected and processing of selection subsy stem 608 is complete

Example of Locating a Corner of a Bar Code Svmbol

The processing of both seed pixel selection subsystem 608 and two-comer location subsystem 600 may also be explained in the context of the example of Fig 5

Referring again to the example of Fig 5, two-comer locating subsystem 600 receiv es an original seed pixel of pixel ( 13.6) and a search direction of west Means 602 of Fig 6 selects a clock ise sequence orientation means 604 sets the current seed pixel to be the original seed pixel ( 13.6), and means 606 starts the list of selected seed pixels

Referring now to Fig 8, there is shown a table representing the first twelve processin cycles of location subsystem 600 for the example of Fig 5 After cycle 1 the list of selected seed pixels maintained by location subsystem 600 contains only the original seed pixel ( 13.6)

At the beginning of cycle 2. selection subsystem 608 receives as inputs the current seed pixel ( 13.6). the west search direction, and the clockw ise selected sequence orientation Means 702 of Fig 7 sets the current neighbor to be pixel (12,6), since that is the neighbor in the west search direction from the current seed pixel (13,6) Since current neighbor (12.6) is a dark pixel and current seed pixel ( 13.6) is a bright pixel, they are not similar pixels and means 704 directs processing to means 708

Means 708 selects pixel (12,7) to be the next neighbor by moving clockwise around current seed pixel ( 13,6) from current neighbor (12,6) Since next neighbor ( 12,7) is bright next neighbor ( 12,7) is not similar to current neighbor (12,6) and means 710 directs processing to means 714 Since next neighbor ( 12 7) is similar to current seed pixel ( 13,6), means 714 directs processing to means 716. which selects next neighbor (12,7) to be the next seed pixel Processing then returns to means 610 of location subsystem 600 to update the list of selected seed pixels by adding next seed pixel ( 12,7) as reflected at cycle 2 of Fig 8 Means 612 then selects next seed pixel ( 12,7) to be the current seek pixel Since the list of selected seed pixels is only 2 pixels long which is shorter than the preferred selected threshold of 5 pixels, means 614 directs processing back to selection subsystem 608

In cycle 3. means 702 of selection subsystem 608 uses current seed pixel (12,7) and west search direction to select current neighbor (1 1 ,7) After means 704 determines that current neighbor ( 1 1.7) is not similar to current seed pixel (12,7). means 708 selects next neighbor ( 1 1.8) bv moving clockwise around current seed pixel ( 12,7) from current neighbor ( 1 1.7) Since next neighbor (1 1 ,8) is similar to current neighbor ( 1 1 ,7), means 710 directs processing to means 712. which sets the current neighbor to be next neighbor (1 1,8) Processing then returns to means 708, which selects next neighbor ( 12,8) by moving clockwise around current seed pixel (12,7) from current neighbor ( 1 1.8). Since next neighbor ( 12.8) is not similar to current neighbor ( 1 1 ,8). means 710 now directs processing to means 714, which in turn determines that next neighbor (12.8) is similar to current seed pixel ( 12.7). Means 716 then sets the next seed pixel to be next neighbor ( 12,8).

Means 610 then updates the list of seed pixels by adding next seed pixel ( 12.8). as reflected at cycle 3 of Fig. 8, and means 612 sets the current seed pixel to be next seed pixel ( 12.8). Since the list of selected seed pixels is still shorter than the selected threshold of 5 pixels, means 614 again returns processing to means 608.

Similarly, in cycles 4 and 5. selection subsystem 608 selects pixels ( 1 1.9) and ( 10.10) as the next two seed pixels and means 610 updates the list of selected seed pixels, as reflected in Fig. 8. In cycle 5. means 614 determines that the list of selected seed pixels is no longer shorter than the selected threshold of 5 pixels and directs processing to means 616. which creates the current vector of (-3,4) by translating to the origin the vector from first seed pixel ( 13.6) in the list to last seed pixel ( 10.10) in the list, as reflected in cycle 5 of Fig. 8. The current vector (-3.4) indicates that going from pixel ( 13.6) to pixel ( 10.10) requires moving west 3 pixels and north 4 pixels.

Since current vector (-3,4) is the first vector generated by location subsystem 600 for the selected sequence orientation of clockwise, means 618 directs processing to means 620. which saves current vector (-3.4) as the reference vector. Since current vector (-3.4) is identical to reference vector (-3.4), means 622 calculates a vector difference magnitude of 0, as reflected in cycle 5 of Fig. 8.

Since magnitude 0 is less than the selected third threshold, which in the example of Fig. 5 is assumed to be 2.5. means 624 returns processing to selection subsystem 608 for cycle 6. Those skilled in the art w ill understand that the value selected for the third threshold may be determined empirically off-line by testing location subsystem 600 using various values for the third threshold to process images containing known bar code symbols.

In cycle 6. using current seed pixel (10,10). selection subsystem 608 selects as next seed pixel (9.1 1 ) and means 610 updates the list of selected seed pixels by dropping first seed pixel (13.6) and adding next seed pixel (9, 1 1 ). as reflected in Fig. 8. Means 616 creates current vector (- 3.4), means 622 calculates magnitude 0. and means 624 directs processing back to selection subsystem 608 for cycle 7. Similarly , in cycles 7, 8, and 9, selection subsystem 608 selects pixels (9,12), (8.13 ). and (7, 14), respectively, as the next three seed pixels, means 610 updates the list of selected seed pixels, means 616 creates current vectors (-3,4). and means 624 directs processing back to selection subsystem 608 for the next cycle.

In cycle 10, means 702 of selection subsystem 608 sets the current neighbor to be west neighbor (6,14) based on current seed pixel (7,14). Since current neighbor (6, 14) is bright, it is similar to current seed pixel (7, 14) and means 704 directs processing to means 706, which temporarily reverses the selected sequence orientation Since the selected sequence orientation was clockwise, means 706 temporarily selects counterclockwise as the sequence orientation Means 708 then selects next neighbor (6, 13) by moving counterclockw ise around current seed pixel (7 14) from current neighbor (6.14) Since next neighbor (6.13) is dark, it is not similar to current neighbor (6 14) and means 710 directs processing to means 714 Since next neighbor (6.13) is also not similar to current seed pixel (7, 14), means 714 directs processing to means 718. which sets the next seed pixel to be current neighbor (6.14) Means 610 then updates the list of selected seed pixels and means 616 creates current vector (-3.3 ) as reflected in cycle 10 of Fig 8 In this case means 622 calculates a magnitude of 1 0. representing the magnitude of the vector difference between current vector (-3.3 ) and reference vector (-3.4) Means 624 then directs processing back to selection subsystem 608 for cycle 1 1. since magnitude 1 0 is less than the selected third threshold of 2 5

Similarly , in cvcle 1 1. selection subsystem 608 selects next seed pixel (5.13). means 610 updates the list of selected seed pixels means 616 creates current v ectors (-4 1 ) and means 622 calculates a magnitude of 3 2. as reflected in cvcle 1 1 of Fig 8 Means 624 determines that magnitude 3 2 is not less than selected third threshold 2 5 and directs processing to means 626 Means 626 selects the pixel corresponding to the detected comer To ensure that the region defined by the four co ers identified by location subsystem 112 contains the entire located bar code symbol, means 626 of location subsvstem 600 preferably selects a pixel outside the actual corner of the outside bar of the start stop character as the detected comer In the example of Fig 5. means 626 may select pixel (7 15 ) as the first comer corresponding to point 214 of Fig 2 by mov ing two pixels north and two pixels east from the last selected seed pixel (5, 13)

W hen the search direction is west and the selected sequence is clockwise, location subsvstem 600 locates the northeast co er of a bar code symbol and means 626 moves north 2 pixel and east 2 pixels from the last selected seed pixel to ensure selection of a comer pixel that w ill prov ide encompassing the entire bar code symbol. Similarly, when the search direction is west and the selected sequence is counterclockwise, location subsystem 600 locates the southwest comer and means 626 mov es south and east When the search direction is east and the selected sequence is clockwise, location subsystem 600 locates the southwest co er and means 626 move south and west In alternative embodiments, means 626 may move in these directions by other numbers of pixels including zero

Following selection of the first co er pixel, means 628 determines that only one comer pixel has been selected so far and means 630 then selects the counterclockw ise sequence orientation Location subsystem 600 begins the process of locating the second comer using the counterclockwise sequence orientation in cycle 12 by returning to means 604. which sets the current seed pixel back to original seed pixel (13,6). and to means 606. which starts the list of selected seed pixels over again with only original seed pixel (13.6). as reflected in Fig 8 Location subsystem 600 continues processing analogous to that for locating the first comer until the second comer is located, at which time, means 628 determines that both comers have been located and processing of location subsystem 600 is complete.

Those skilled in the art will understand that co er location subsystems of the present invention may be used to locate comers of artifacts in pixel images other than bar code symbols. Such artifacts ma be of a shape other than a rectangle with right-angle comers.

Decoding Bar Code Svmbols

Referring now to Fig. 9. there is shown a process flow diagram of bar code symbol decoding subsystem 114 of detection system 100 for decoding a bar code symbol according to a preferred embodiment of the present invention. If four-co er location subsystem 112 of detection system 100 of Fig. 1 locates all four comers of a detected bar code symbol, decoding subsystem 114 decodes the symbol by determining the series of alphanumeric characters that are encoded as bars and spaces in the bar code symbol. Alphanumeric characters may be any possible character and are not limited to only digits and letters of the English alphabet. Decoding subsystem 114 selects a reference line across the randomly oriented bar code symbol and decodes the symbol by stepping along the reference line.

For those symbologies having checksum characters such as Code 128, decoding subsystem 114 selects one or more alphanumeric character choices for each symbol character. Decoding subsystem 114 then performs checksum analysis on sets of alphanumeric characters selected from those character choices. If a character set satisfies the checksum analysis, then that character set is selected as the result of decoding the bar code symbol. If none of the character sets satisfy the checksum analysis, then decoding subsystem 114 selects another reference line for which the process of decoding and checking is repeated. Decoding subsystem 114 continues to select reference lines until the checksum analysis is satisfied, or until a specified stop condition occurs. The stop condition may be a specified resolution between reference lines, a specified number of reference lines, or a specified processing duration, depending upon the requirements of the particular application.

For those symbologies that have no checksum characters, decoding subsystem 114 selects a best alphanumeric character choice for each symbol character. Each of these choices has a corresponding confidence factor. If each of the choices in the set of best choices is "good enough" based on the confidence factors, then decoding subsystem 114 selects that set as the decoding result for the bar code symbol. If one or more choices is not good enough, then decoding subsystem 114 selects another reference line for which the process of decoding is repeated, saving the best choices from each reference line. The selection of reference lines continues until each of the choices is good enough, or until the specified stop condition occurs. Referring now to Fig. 10. there is shown a graphical representation of pixel image 1000 containing degraded bar code symbol 1002. Bar code symbol 1002 is a Code 128 symbol encoding the data "CODE 128" In addition to the eight data characters, bar code sy mbol 1002 includes a start character, a stop character which is considered to include the termination bar. and a checksum character. The checksum character represents the value 84. which is equivalent to the result of performing the appropriate Code 128 checksum computation on the eight data characters of bar code symbol 1002. The checksum character may be used to verify the correctness of the decoding of bar code symbol 1002

Bar code sy mbol 1002 is degraded in regions 1004. 1006. and 1008 Degradations may make bars and spaces appear thinner or thicker than they were intended to be Such dev iations from intended thicknesses may result in errors in decoding bar code symbol 1002 along reference line that pass through the degraded regions.

Referring again to Fig 9. in a preferred embodiment, decoding subsystem 114 receive as inputs the four comers of the bar code symbol located by four-comer location subsystem 112 Means 902 then selects a first reference line across the bar code symbol In general, a reference line preferably runs through a bar code symbol perpendicular to the bars and spaces of that bar code symbol Thus, a reference line starts at one quiet zone and ends in the other quiet zone of the bar code symbol. In a preferred embodiment, the first reference line is the perpendicular bisecting line, referred to earlier in conjunction with Figs. 2 and 4, that runs through the center of the bar code symbol.

In the example of Fig. 10. decoding subsystem 114 receives as inputs comers 1010. 1012. 1014. and 1016. which define a region of pixel image 1000 containing bar code symbol 1002 Means 902 selects reference line 1018 as the first reference line for decoding bar code symbol 1002 Reference line 1018 may be the line through points 1020 and 1022. where point 1020 is the midpoint between comers 1010 and 1012 at one end of bar code symbol 1002 and point 1022 is the midpoint between comers 1014 and 1016 at the other end of bar code symbol 1002

Stepping subsystem 904 then performs subpixel interpolation of bar code symbol 1002 along search steps associated w ith reference line 1018. Stepping subsystem 904 and subpixel interpolation are described in further detail later in this specification in conjunction with Figs 1 1. 14. and 15. Each symbol character of bar code symbol 1002 is a set of bars and spaces that represents an alphanumeric character. Stepping subsystem 904 selects one or more alphanumeric characters to associate with each symbol character of bar code symbol 1002 In addition, for each symbol character, stepping subsystem 904 assigns to each selected alphanumeric character a confidence factor that indicates how "confident" subsystem 904 is that the symbol character actually represents the selected alphanumeric character. For example, using reference line 1018, stepping subsystem 904 may determine that the first data character of bar code symbol 1002 should be associated with the alphanumeric character "C". as presented in Table 1. That character choice is then assigned a particular confidence factor. Stepping subsystem 904 may also determine that the second data character is to be associated with the alphanumeric character "O". which is assigned its own confidence factor. Table I . DATA CHARACTERS

CHECKSUM

CHOICE 11 12 11 11 i li j£7 £8_. CHARACTER

1st c 0 D 7 space 1 2 8 84

2nd w L

3rd E

Because bar code symbol 1002 is degraded in regions 1004 and 1006. stepping subsy stem 904 may generate one or more alphanumeric character choices for each of the other data characters using reference line 1018. For example, stepping subsystem 904 may generate a first or best choice of "O" and a second best choice of "W" for the second data character of bar code symbol 1002. because reference line 1018 passes through degraded region 1004 at the second data character. The relative values of the assigned confidence factors may indicate that stepping subsystem 904 is "more confident" that the second data character actually represents the alphanumeric character "O" than that it actually represents the alphanumeric character "W". Similarly , stepping subsystem 904 may generate best, second best, and third best choices "7", "L". and "E". respectively, for the fourth data character of bar code symbol 1002 due to the adverse results of degraded region 1006.

When the first reference line is selected, means 906 creates a character table of the alphanumeric characters and associated confidence factors assigned by stepping subsystem 904. Each column of the character table corresponds to a different symbol character and each column contains the alphanumeric characters associated with that symbol character arranged from highest confidence to lowest confidence, that is. from best choice to worst choice.

After means 906 creates the character table, means 908 selects a character set from the character table. Initially, means 908 selects the set of first-choice characters from the character table. Each character in this set of first-choice characters is the best or first choice, that is. the alphanumeric character with the highest confidence, for each symbol character represented in the character table.

Means 910 then performs a checksum computation on that selected set of alphanumeric characters and compares the result to the checksum character. If means 910 determines that the checksum result matches the checksum character, then the bar code symbol is decoded and processing of decoding subsystem 114 is concluded. Otherwise, the checksum analysis is not satisfied and means 912 determines whether there are any more sets of character choices in the character table to check If so, then means 908 selects a next character set from the character table for checksum analysis by means 910

As described abov e, each symbol character may hav e one or more associated alphanumeric characters in the character table Decoding subsystem 114 may test other sets of alphanumeric characters, other than the first-choice character set. against the checksum character In a preferred embodiment, each of these other character sets consists of the first-choice alphanumeric character for each sy mbol character except for one symbol character w hich is represented by one of its other choices Decoding subsv stem 114 tests these other character sets until one is found that satisfies the checksum analysis

If there are no more character sets to be tested then means 914 determines whether any more reference lines are to be selected Depending upon the requirements of the particular application, the selection of reference lines may be continued until a specified resolution between reference lines has been reached, or until a specified number of reference lines hav e been selected, or until a specified processing time has expired, whichever criterion is desired In a preferred embodiment, up to three reference lines are selected to decode a detected bar code symbol If there are more reference lines, then means 902 selects a next reference line for further subpixel interpolation bv stepping subsy stem 904 Otherwise, all reference lines hav e been selected and decoding subsv stem 902 fails to decode the bar code symbol

In the example of Fig 10, Table I may represent the character choices created by means 906 using reference line 1018 Means 908 first selects the set of first-choice characters corresponding to character set ! "C". "O", "D", "7", space, " 1 ". "2". "8". "84" ! Means 910 then performs checksum analy sis on the selected character set Since the checksum result of means 910 does not match the checksum character "84", the checksum analy sis is not satisfied Means 912 then determines w hether the character table contains any more character sets In a preferred embodiment of decoding subsy stem 114 if the set of first-choice characters fails the checksum analysis then selected other character sets are tested

After the first-choice character set fails the checksum analysis, means 912 determines that there are other character sets in the character table and means 908 selects another character set from the character table In the example of Table I, means 908 may select { "C". "W", "D". "7". space, " 1 ", "2", "8", "84"} as the next character set to be tested This set represents the first choice for each symbol character except for data character #2. for which the second choice is selected Means 910 performs the checksum computation on this character set and determines that it too fails the checksum analysis Again, means 912 determines that the selected character set is not the last character set and means 908 may select {"C". "O". "D". "L". space. " 1 ". "2". "8". "84" } as the next character set. This character set also fails the checksum analysis of means 910 and {"C". " ". "D". "E", space. " 1 ", "2". "8". "84"} is then selected by means 908 to be the next character set.

Since {"C". "O". "D". "E". space. " 1 ". "2". "8", "84"} is the correct character set. it satisfies the checksum analysis of means 910, that is. the result of the checksum computation performed on the data characters of that set of characters is "84", the value of the checksum character. At this point, bar code symbol 1002 is decoded and processing of decoding subsystem 114 is concluded. If it turned out for some reason, however, that region 1006 was so degraded that, for reference line 1018, none of the character sets selected by means 908 satisfies the checksum analysis, then means 914 determines whether there are any more reference lines to be used to decode bar code symbol 1002. The number of reference lines to be used may be dictated by the processing requirements of the particular application. In one embodiment, up to 20 reference lines are selected.

After means 914 determines that reference line 1018 is not the last reference line to be selected, means 902 may select reference line 1024 as the next reference line, where reference line 1024 is preferably the line midway between reference line 1018 and the line defined by comers 1010 and 1016. Stepping subsystem 904 then decodes by stepping along reference line 1024. As before, this decoding may result in one or more alphanumeric characters and associated confidence factors for each symbol character in bar code symbol 1002. Means 906 then updates the character table using the results for reference line 1024 and the results previously generated for reference line 1018.

As described in further detail later in this specification in conjunction with Fig. 1 1. in a preferred embodiment, the confidence factors are distance measures reflecting deviations from ideal characters. As such, a small confidence factor implies a smaller deviation from an ideal alphanumeric character and a higher level of confidence that that ideal alphanumeric character is the correct character. In a preferred embodiment, means 906 updates the character table by generating a effectiv e confidence factor R for each alphanumeric choice according to Equation (5) below:

(5 )

R

where the R, are the confidence factors for that alphanumeric choice using different reference lines. The character table is then updated by arranging the choices according to their effective confidence factors.

For example, assume that, for one of the symbol characters in a bar code symbol, two alphanumeric choices are generated using the first reference line: the letter "A" with a confidence factor of 0.5 and the letter "B" with a confidence factor of 0.8. After this first reference line, "A" is the first choice and "B" is the second choice, because "A" has the smaller confidence factor. Assume further that using the second reference line results in two more choices for the same symbol character: "B" with a confidence factor of 0.8 and "C" with a confidence factor of 0.6. In this case, means 906 updates the character table for this symbol character by retaining "A' ith a confidence factor of 0 5 adding "C" ith a confidence factor of 0 6. and updating the confidence factor R for "B" to 0 4 according to Equation (5). where

- -!_ + -!_ (₆)

R 0 . 8 0 . 8

Since "B" now has the smallest effective confidence factor, it becomes the first choice in the character table, followed by "A" and "C Those skilled in the art will understand that the character table may be updated using alternativ e methods that are within the scope of the present inv ention

The updated character table is then processed bv means 908 910 and 912. as described before If none of the character sets selected by means 908 from the updated character table satisfies the checksum analy sis then another reference line 1026 mav be selected and the procedure of stepping, updating and checksum analyzing repeated

In a preferred embodiment, the checksum character in the character table is represented by onlv a first choice alphanumeric character In an alternativ e preferred embodiment the checksum character may have one or more choices in addition to the first choice In such cases, the checksum character may be treated as any other character in generating character sets for checksum analv sis

Stepping Along a Reference Line To Decode a Bar Code Svmbol

Referring now to Fig 1 1. there is shown a process flow diagram of stepping subsy stem 904 of bar code symbol decoding subsystem 114 for stepping along a selected reference line and decoding a bar code symbol according to a preferred embodiment of the present invention Since the bar code svmbols to be detected and decoded by detection system 100 may be randomlv oriented relative to the rows and columns of pixels in the pixel image, the reference lines selected bv decoding subsvstem 114 are typically not aligned with pixels rows or columns

In order to preserve the information content of these pixel images, decoding subsvstem 114 decodes bar code symbols by performing subpixel interpolation along a series of search steps Each search step is a portion of a pixel row or column that starts at the intersection of the pixel row or column and the selected reference line If the reference line is oriented to the pixel rows of the pixel image with an angle magnitude of less than 45 degrees, then the search steps are portions of pixel rows Otherwise, the search steps are portions of pixel columns

Referring now to Fig 12, there is shown a graphical representation of pixel image 1200 containing quiet zone 1204 and a portion of bar code symbol 1202 which is not aligned with either the pixel rows or columns of pixel image 1200 Bar code symbol 1202 includes bars 1206 through 1214, and spaces 1216 through 1224 Fig 12 also shows reference line 1226 and search steps 1228 through 1242. Reference line 1226 is analogous to reference lines 1018. 1024. and 1026 of Fig. 10.

Referring now to Fig. 13. there is shown a graphical representation of the pixel intensity levels of 1 1 pixels in search step 1228 of pixel image 1200. Each pixel along search step 1228 has a corresponding intensity level representative of its brightness. In order to facilitate explanation, stepping subsystem 904 is described in the context of the example of Figs. 12 and 13.

Stepping subsystem 904 of Fig. 1 1 begins with means 1102 which selects the first search step and the start point for the first search step. The first search step is preferably a row or column of pixels that intersects the reference line at the state transition between a quiet zone and a start stop character of the detected bar code symbol. The start point is preferably the pixel that corresponds to the point of intersection. In Fig. 10, point 1020 may be the start point of the first search step when using reference line 1018 to decode bar code symbol 1002. Similarly, in Fig. 12. point 1244 may be the start point of first search step 1228 when using reference line 1226 to decode bar code symbol 1202. Search step 1228 forms part of the row of pixels that intersects reference line 1226 at point 1244.

After means 1102 selects the start point of the first search step, means 1104 performs subpixel interpolation along the first search step to determine a signal energy value that represents the width of the first bar of the bar code symbol. In the example of Fig. 12, means 1104 performs subpixel interpolation along search step 1228 to determine a signal energy value for bar 1206 of bar code symbol 1202. The higher the signal energy value, the wider the symbol element. Subpixel interpolation is further described later in this specification in conjunction with Figs. 14 and 15.

Means 1106 sets the current search step to be the first search step. Means 1108 then performs subpixel interpolation for another element along the current search step, where elements are analyzed by means 1108 in the order in which they appear in the bar code symbol. Means 1110 then determines whether subpixel interpolation for the next element is to be performed along the current search step or whether a new current search step is to be selected. A new current search step is selected if the next-to-last analyzed element is wide enough to project from. For example, where the last analyzed element was a space, a new current search step is selected to analyze the bar that immediately follows that space, if the bar that immediately precedes that space is wide enough from which to project.

To make this determination, means 1110 compares the signal energy value for the previous symbol element to a fourth threshold. The fourth threshold is preferably equivalent to at least two times the width of the narrowest bar code symbol element. If means 1110 determines that the signal energy value for the next-to-last analyzed element is larger than the fourth threshold, then means 1112 selects the start point for a new current search step by projecting from the center of the next-to-last analyzed element onto the reference line Otherwise, means 1114 selects the start point along the current search step as the center of the next-to-last analyzed element

After the start point is selected either by means 1112 or 1114. means 1116 determines whether stepping along the reference line is complete by checking w hether the quiet zone has been reached If so. character determination subsystem 1118 generates the alphanumeric character choices and confidence factors associated with each symbol character of the bar code symbol At that point processing by stepping subsystem 904 is complete Character determination subsv stem 1118 is further described later in this specification in conjunction w ith Fig 16

In the example of Fig 12. means 1110 may determine that the signal energy v alue for bar 1206 is greater than the fourth threshold Means 1112 may then select start point 1246 of search step 1230 as the start point for the new current search step by projecting from point 1248 of search step 1228 onto reference line 1226 For example, where bar code sy mbol elements have a minimum width of 0 015 inches, the fourth threshold may be equivalent to 0 030 inches The projection from search step 1228 to reference line 1226 is preferably perpendicular to reference line 1226 If reference line 1226 is characterized by slope k and intercept n and center point 1248 is represented by point (*,,i _ι ). then the projection line from center point 1248 is characterized by slope λ and intercept /;,. w here

*' - ^<7> and

ⁿx ⁼ Yx ^{~ k}ι ^xι ^■ ( 8 )

Start point 1246 may be represented by the point (x₂,y₂). where n-n_Υ

( 9 ) k, -k

and y₂ = k_xx_^ + n_x . ( 10 )

After means 1116 determines that the quiet zone has not been reached, means 1108 performs subpixel interoolation for bar 1208 along search step 1230

Otherwise, if the signal energy value for bar 1206 is not greater than the fourth threshold, then means 1114 sets the start point for subpixel interpolation to the center of bar 1206 along current search step 1228 After means 1116 determines that quiet zone has not been reached, means 1108 calculates the signal energy value for bar 1208 along current search step 1228 Subpixel interpolation of subsequent symbol elements continues along search step 1228 until the next-to-last analyzed element is a bar or space of sufficient width, in which case, means 1112 then projects from the center of that element onto reference line 1226 to select the start point of the ne current search step. In this way. stepping subsystem 904 determines signal energy values for each symbol element of bar code symbol 1202.

Subpixel Interpolation of Bar Code Svmbol Elements

Referring now to Figs. 14 and 15, there are shown process flow diagrams of subpixel interpolation subsystems 1400 and 1500 of the present invention for calculating signal energy values for bars and spaces, respectively . If the bar code symbol element to be analyzed is a bar. means 1108 of stepping subsystem 904 implements subpixel interpolation subsystem 1400 to determine a signal energy value for the region from the center of the space that immediately precedes the bar to the center of the space that immediately follows the bar. Similarly . if the symbol element to be analyzed is a space, means 1108 implements subsystem 1500 to determine an signal energy value for the region from the center of the bar that immediately precedes the space to the center of the bar that immediately follow s the bar.

When a bar is to be analyzed, means 1402 of subpixel interpolation subsystem 1400 locates a first peak corresponding to the center of the space immediately preceding the bar to be analyzed. When analyzing any bar other than the first bar of a bar code symbol, a peak generally represents a pixel intensit level maximum with respect to adjacent pixels. When analyzing the first bar. the first peak is preferably a bright pixel near the end of the quiet zone abutting the first bar. Means 1404 then locates a second peak corresponding to the center of the space immediately following the bar to be analyzed. The two peaks are adjacent critical points along a one-dimensional signal curve that represents a portion of the current search step that is centered on the bar to be analyzed.

Means 1406 then computes the area above the gray-scale signal curve between the tw peaks by numerically integrating using the pixel intensity levels. This area is the signal energy value of the bar being analyzed. In making this integration computation, means 1406 preferably uses the maximum pixel intensity level from the histogram generated by means 102 of detection system 100 of Fig. 1 as the upper limit for computing the area above the curve. In general, the signal energy value όj for a bar is given by:

( 11 )

where I_mn is the maximum pixel intensity level from the histogram. /_p^ ,, is the pixel intensity level of the pixel corresponding to the first peak, I_{pak M2} is the pixel intensity level of the pixel corresponding to the second peak, and /_p are the pixel intensity levels of the pixels lying between the first and second peaks along the current search step.

In the example of Figs. 12 and 13. stepping subsystem 904 implements subpixel interpolation subsystem 1400 along search step 1228 to determine the signal energy value for bar 1206 Since bar 1206 is the first bar in bar code symbol 1202. means 1402 preferably selects as the first peak a pixel near the end of quiet zone 1204, such as pixel 2 in Fig. 13. Means 1404 then locates the second peak which is at the center of space 1216. immediately follow ing bar 1206 Means 1404 may select pixel 7 in Fig 13 as that second peak. Means 1406 then computes the signal energy value for bar 1206 using Equation (1 1 ) Assume, for example, that the histogram for the pixel image containing bar code symbol 1202 indicates that the maximum pixel intensity level 7_ma is 240 The signal energy value b, for bar 1206 from means 1406 is then given by

^ ₌ ⁽ 240 -230 ) ₊ ( 240 -150 ) + ( 240 -50 ) + ( 240 -6 0 ) +

; 240 -²i 00 > ♦ ( 240 -19 0 ) - 630 . ^{( 12 )}

2

Similarly, when a space is to be analyzed, means 1502 of subpixel interpolation subsy stem 1500 locates a first valley corresponding to the center of the bar immediately preceding the space to be analyzed. A valley generally represents a pixel intensity level minimum with respect to adjacent pixels. Means 1504 then locates a second valley corresponding to the center of the bar immediately following the space to be analyzed. The two valleys are adjacent critical points along a one-dimensional signal curve that represents a portion of the current search step that is centered on the space to be analyzed

Means 1506 then computes the area under the gray-scale signal curve between the two valleys by numerically integrating using the pixel intensity levels. This area is the signal energy v alue of the space being analyzed. In making this integration computation, means 1506 preferably uses the minimum pixel intensity level from the histogram generated by means 102 of detection system 100 of Fig 1 as the lower limit for computing the area under the curve In general, the signal energy v alue , for a space is given by:

where I_mm is the minimum pixel intensity level from the histogram, 7_{vjl % B l} is the pixel intensity level of the pixel corresponding to the first valley, /_{vantv w} is the pixel intensity level of the pixel corresponding to the second valley, and 7. are the pixel intensity levels of the pixels lying between the first and second valleys along the current search step. In the example of Figs. 12 and 13, stepping subsystem 904 implements subpixel inteφolation subsystem 1500 along search step 1228 to determine the signal energy value for space 1216. Means 1502 locates the first valley which is at the center of bar 1206. immediately preceding space 1216. Means 1502 may select pixel 4 in Fig. 13 as the first valley. Means 1504 then locates the second valley which is at the center of bar 1208. immediatel following space 1216. Means 1504 may select pixel 9 in Fig. 13 as that second valley. Means 1506 then computes the signal energ value for space 1216 using Equation (13). Assume, for example, that the histogram for the pixel image containing bar code symbol 1202 indicates that the minimum pixel intensity level I_mπ is 50. The signal energy value Λ, for space 1216 from means 1506 is then given by:

_ε^ ₌ ⁽ 50 -50 ⁾ ₊ ( _{6 0} __{5 0} ) ₊ ( 100 -50 ) + ( 190 -50 ) _* _{{ 14} θ'-50 ) * ^{( 1} ° ° -^{5 0 )} = 315 . ^{U4 )}

Location of Centers of Bars and Spaces in Noisy Images

A bar code symbol may be represented by a sequence of intensity levels corresponding to the pixels along a scan line across the symbol, as graphically depicted in the example of Fig. 24. In an ideal, noise-free image of a bar code symbol, every peak along the scan line corresponds to the center of a space and every valley corresponds to the center of a bar of the bar code symbol. However, in a noisy image such as that depicted in Fig. 24, there may be peaks and valleys that do not correspond to the centers of spaces and bars in the bar code symbol.

In addition, in an ideal image of a bar code symbol, all pixels at the center of spaces have the same intensity level. Similarly, all pixels at the center of bars also have the same intensity level. However, in real images generated with CCD-based cameras, pixels at the center of narrow spaces (e.g., pixel 4 in Fig. 24) may have lower intensities than pixels at the center of wide spaces (e.g.. pixel 10). Similarly, pixels at the center of narrow bars (e.g., pixel 14) may have intensities greater than pixels at the center of wide bars (e.g., pixel 6).

Referring no to Fig. 28. there is shown a process flow diagram of subsystem 2800 for performing subpixel inteφolatioπ for a sequence of bars and spaces of a bar code symbol according to a preferred embodiment of the present invention. Subsystem 2800 is a preferred embodiment of means 1108 of Fig. 1 1 , which performs subpixel inteφolation for one bar or space at a time. As such, subsystem 2800 combines the functions of subsystems 1400 and 1500 of Figs. 14 and 15, which perform subpixel iπteφolation for only bars and only spaces, respectively . Subsystem 2800 may be used to perform subpixel inteφolation on noisy images of bar code symbols generated with CCD-based cameras. Subsystem 2800 searches along a selected scan line for bright-to-dark transitions and dark -to-bright transitions that correspond to the leading and trailing edges of bars and spaces of a bar code symbol. Those skilled in the art will understand that a leading edge of a space (e.g.. as defined by pixels 7 and 8 of Fig. 24) is also the trailing edge of the preceding bar and that the trailing edge o a space (e.g.. as defined by pixels 16 and 17 of Fig. 24) is also the leading edge of the following bar. Thus, when subsystem 2800 identifies a bright-to-dark transition, subsystem 2800 locates both the end of a space and the beginning of the following bar. Similarly, when subsystem 2800 identifies a dark- to-bright transition, subsystem 2800 locates both the end of a bar and the beginning of the following space.

After subsvstem 2800 locates the end of a bar. subsystem 2800 then determines the center of that bar. Subsystem 2800 uses the center of that bar to generate a subpixel inteφolation value for the space that preceded that bar. Similarly, after subsystem 2800 locates the end of a space, subsystem 2800 then determines the center of that space and uses that space center to generate a subpixel inteφolation value for the bar that preceded that space.

As described earlier in this specification in conjunction w ith Fig. 14. the subpixel inteφolation value for a bar is preferably a function of the area above the gray-scale signal curve between the center of the space that immediately precedes the bar and the center of the space that immediately follows the bar. Similarly, as described earlier in this specification in conjunction with Fig. 15. the subpixel inteφolation value for a space is preferably a function of the area under the gray scale signal curve between the center of the bar that immediately precedes the space and the center of the bar that immediately follows the space.

In particular, means 2802 of subsystem 2800 receives as input the pixel coordinates of the beginning [X0. Y0] and end [XF. YF] of the currently selected scan line. The current scan line may be all or part of either a row or column of the pixel image. The following description is based on a horizontal scan line coinciding with an image row. Those skilled in the art will understand the analogous processing applies when an image column is selected as a vertical scan line. It w ill also be understood that the present invention may be applied to decode bar code symbols along "virtual" scan lines that do not coincide with either image rows or columns.

Means 2804 initializes the state variable SEARCH to the "DOWN' state to indicate that subsystem 2800 begins by searching for a valley. In this embodiment, subsystem 2800 begins scanning at a pixel corresponding to a quiet zone or to a space. When subsystem 2800 searches for a peak, the state variable SEARCH will have an "UP" state.

Means 2804 also initializes the current transition state variable TRANS C to be "0". There are two transition state variables TRANS C and TRANS P which indicate the states of the current and previous transitions, respectively. A "DOWN" state indicates that a transition is a bright- to-dark transition. An "UP" state indicates that a transition is a dark-to-bright transition. TRANS C is initialized to a "0" state to indicate that the type of transition for the current transition is not initially known

Means 2806 tests the state of SEARCH to determine whether to direct processing to means 2808 to search for the next peak or to means 2824 to search for the next v alley along the scan line A peak along a scan line is preferably defined as a pixel whose intensity is greater than the intensity of the preceding pixel and greater than or equal to the intensity of the following pixel Similarly , a valley along a scan line is preferably defined as a pixel whose intensity is less than the intensity of the preceding pixel and less than or equal to the intensity of the following pixel

Referring again to Fig 24. pixels 2. 4. 8. 10. 12. 15. and 20 are peaks, because they have intensity lev els greater than the preceding pixel and the follow ing pixel Pixel 22 is also a peak, because its intensity level is greater than that of pixel 21 and greater than or equal to that of pixel 23 Similarly , pixels 1. 3. 9. I I . 14. 1 7. and 21 are valleys, because they each hav e an intensity lev el less than the intensity level of the preceding pixel and less than or equal to the lev el of the follow ing pixel Consecutiv e pixels 1 7. 1 8. and 19 have the same value and are therefore said to correspond to a plateau Similarly , pixels 22. 23. 24. and 25 correspond to another plateau

Referring now to Fig. 29, there is shown a block flow diagram of means 2808 of Fig 28. which searches for the next peak along the scan line. Means 2808 sequentially selects pixels until either the next peak is found or the end of scan line is reached. In particular, means 2902 of means 2808 saves the current pixel coordinates [X, Y] as the coordinates of the start of the current transition [XS. YS] Means 2904 then determines whether the current pixel is a peak by evaluating the following condition

(IMAGE [X, Y] > IMAGE [X-], Y]) AND (IMAGE [X. Y] ≥ IMAGE [X+I Y]) If the condition is satisfied, then the current pixel is a peak and means 2910 saves the current pixel coordinates [X, Y] as the coordinates of the end of the current transition [XE. YE] Otherwise, the current pixel is not a peak and means 2906 selects the next pixel by incrementing X by 1 Means 2908 then determines whether the end of the current scan line has been reached. If the column X for the next pixel is greater than the column XF for the end of the current scan line, then the scan line end has been reached and processing of means 2808 terminates without finding the next peak. Otherwise, the scan line end has not be reached and processing returns to means 2904 to determine if the new pixel is a peak. This processing continues until either the next peak is found or t - end of the scan line is reached without finding a peak.

Referring again to Fig. 28, if means 2808 reached the end of the scan line without finding a peak, means 2810 directs processing of subsystem 2800 to terminate. Otherwise, means 2808 found the next peak and means 2810 directs processing to continue to means 2812, which tests the current transition to determine whether it qualifies as the leading edge of the next space of the bar code symbol.

Means 2812 is designed to select only transitions that correspond to actual edges within a bar code symbol and to ignore those transitions that correspond to noise in the image data. The test applied by means 2812 is based on a scoring algorithm that includes two partial scores. Each partial score quantifies a different characteristic of actual edges within images of bar code symbols.

The first partial score is based on the characteristic that transitions corresponding to actual edges are typically larger than transitions corresponding to noise. The first partial score PI is given by Equation ( 15) as follows:

_D , _ r._nτ,_η ABS ( IMAGE lXS, YS) - IMAGE [XE, YE) ) .. . .

Pi - CO ii x — - — , ( 15 )

where CON1 is a specified first weighting factor. ABS is the absolute value function, IMAGE is the pixel intensity level at the specified pixel coordinates, [Λ'S, T5 are the pixel coordinates for the start of the current transition as determined by means 2808, [XE. YE] are the pixel coordinates for the end of the current transition as determined by means 2808, I_v is the current white intensity reference, and /,, is the current black intensity reference. In a preferred embodiment, first weighting factor CON] has a value of 2. The white and black intensity references 7_W and 7_b depend upon the local dynamic range and are described in further detail in the following section of this specification.

The second partial score is based on the characteristic that pixels corresponding to narrow spaces and narrow bars in images generated using a CCD-based camera often have intensity levels that are close to the center of the local dynamic range. The second partial score P2 is given by- Equation ( 16) as follows:

_{ΛE£ (} IMAGE [XΞ, YS] + IMAGE [XE, YE] _ *_w ^* ϊ_{b )} p? CONΣ

I« ^~ ι_b where CON2 is a specified second weighting factor. In a preferred embodiment, second weighting factor CON2 has a value of - 1.

Means 2812 evaluates the following condition to determine if the current transition qualifies as a transition corresponding to an actual edge within a bar code symbol:

THRESH < P1 -r P2 , where THRESH is a specified scoring algorithm threshold, which preferably has a value of 0. If the condition is not satisfied, then the transition is to be ignored and processing continues to means 2818.

Otherwise, the transition corresponds to a leading edge of a space and means 2814 updates certain transition parameters. In particular, means 2814 updates the start coordinates [XPS. YPS] and end coordinates [XPE. YPE] for the previous transition, such that: XPS = xcs

YPS = YCS XPE = XCE YPE = YCE where [XCS. YCS] were the start coordinates and [XCE, YCE] were the end coordinates for the current transition. Means 2814 then updates [XCS.YCS] and [XCE. YCE]. such that:

XCS = XS

YCS = YS

XCE = XE

YCE = YE where [XS.YS] and [XE. YE] are the start and stop coordinates, respectfully, for the new transition, as determined by means 2808.

Means 2814 also updates the previous and current transition state variables TRANS P and TRANSJC. such that:

TRANS_P = TRANS JC TRANS J = "UP" where "UP" indicates that the current transition corresponds to the leading edge of a space.

Referring now to Fig. 30, there is shown a block flow diagram of means 2824 of Fig. 28. which searches for the next valley along the scan line. Processing is directed to means 2824 by means 2806 when the state variable SEARCH has a "DOWN' state. Means 2824 functions identically to means 2808, except that in order to determine whether the current pixel [X. Y] is a valley, the following condition is evaluated:

(IMAGE [X, Y] < IMAGE [X-\, Y]) AND (IMAGE [X, Y] ≤ IMAGE [X+\, Y]) Referring again to Fig. 28, if means 2824 reached the end of the scan line without finding another valley, means 2826 directs processing of subsystem 2800 to terminate. Otherwise, means 2824 found the next valley and means 2826 directs processing to continue to means 2828. which tests the current transition to determine whether it qualifies as the leading edge of the next bar of the bar code symbol. Means 2828 applies the identical scoring algorithm to test for a bar leading edge that means 2812 applies to test for a space leading edge. If the test condition is not satisfied, then the transition is to be ignored and processing continues to means 2818. Otherwise, the transition corresponds to a leading edge of a bar and means 2830 updates the same transition parameters as means 2814, except that:

TRANS_C = "DOWN" to indicate that the current transition corresponds to the leading edge of a bar. Referring now to Fig. 31 , there is shown a block flow diagram of means 2816 of Fig. 28. Means 2816 determines the center of the current element (i.e.. bar or space) and generates a subpixel inteφolation value for the preceding element. If the current element is a bar. then means 2816 determines the center of that bar and generates a subpixel inteφolation for the preceding space based on the area under the pixel intensity level curve from the center of the previous bar to the center of the current bar. Similarly , if the current element is a space, then means 2816 determines the center of that space and generates a subpixel inteφolation for the preceding bar based on the area over the pixel intensitv level curve from the center of the previous space to the center of the current space.

Means 3102 of means 2816 determines whether the previous-transition state v ariable TR4NS P has a "0" state. TR4NS P will be "0" after the first transition along the current scan line is located, but before the second transition is located. In that case, there is only one transition and the center of an element cannot be determined. Therefore, no subpixel inteφolation value can be generated and means 3102 ends processing of means 2816. Those skilled in the art will understand that TR4NS P w ill be "0". for example, when the current transition corresponds to the leading edge of an outer bar of a bar code symbol. If TRANS_P does not equal "0." then processing continues to means 3104.

Means 3104 determines whether the previous-transition state variable TRANS P has the same state as the current-transition state variable TRANS C. If so. then means 3104 ends processing of means 2816. Otherwise, processing continues to means 3106.

Those skilled in the art will understand that TRANS P and TR4NSJC will have the same state when, for example, a large transition is interrupted by noise, such as in pixels 19. 20. 21. and 22 of Fig. 24. Means 2828 of Fig. 28 will reject the bright-to-dark transition from pixel 20 to pixel 21 as corresponding to noise. In that case, when the current transition is the dark-to-bright transition from pixel 21 to pixel 22, the previous transition will be the dark-to-bright transition from pixel 19 to pixel 20 and TRANS P will have the same state as TRANS C (i.e.. "UP").

If the previous and current transitions are of different type (i.e.. if TRANS P and TRANS JC have different states), then means 3106 determines the type of the prev ious transition. If TR4NS_P has a "DOWN' state, then processing continues to means 3108: otherwise, processing continues to means 3112. If TRANS_P is "DOWN." then TRANS C is "UP" and the current element corresponds to a bar: otherwise. TRANS P is "UP," TRANSjC is "DOWN." and the current element corresponds to a space.

Means 3108 updates the location [SPX.SPY] of the center of the previous space, such that:

SPX = SCX SPY = SCY where [SCX.SCY] was the location of the current space. Means 3108 then determines the location [SCX.SO^'] of the center of the new space, according to Equations (1 7) and ( 18) below :

SCX = ^{XPE + XCS} (17 )

2

and

SCY = YPE , ( 18 )

where XPE is the image column corresponding to the end of the pre ious transition. XCS is the image column corresponding to the start of the current transition, and YPE is the image row corresponding to the end of the previous transition.

Means 3110 then generates a pixel inteφolation value for the bar that falls between the previous space and the current space. This pixel inteφolation value may be generated as described earlier in this specification in conjunction with Fig. 14. where [SPX.SPY] is the center of the previous space and [SCX.SO^'] is the center of the current space.

Similarly, means 3112 updates the location [BPX.BPY] of the center of the previous bar. such that:

BPX = BCX BPY = BCY where [BCX.BCY] was the location of the current bar. Means 3112 then determines the location [BCX.BO of the center of the new bar. according to Equations (19) and (20) below:

BCX = ^{XPE + XCS} ( 19 )

and

BCY = YPE . ( 20 )

Means 3114 then generates a pixel interpolation value for the space that falls between the previous bar and the current bar. This pixel inteφolation value may be generated as described earlier in this specification in conjunction with Fig. 15. where [BPX.BPY] is the center of the previous bar and [BCX.BCY] is the center of the current bar.

Returning again to Fig. 28, after means 2816 determines the center of the current element and generates a subpixel inteφolation value for the previous element, processing continues to means 2818. Means 2818 handles any plateaus (i.e.. sequences of pixels with identical intensity levels) that occur along a scan line. According to the definitions of peaks and valleys as applied by subsystem 2800, a pixel at the beginning of a plateau is defined to be a valley (e.g.. pixel 17 in Fig. 24) or a peak (e g., pixel 22 in Fig 24) Means 2818 finds the pixel at the end of a plateau before subsy stem 2800 starts to search for the next transition

Referring now to Fig 32. there is shown a block flow diagram of means 2818 of Fig 28. for searching for the end of a plateau Means 3202 of means 2818 determines whether the current pixel corresponds to the end of the plateau by evaluating the condition

IMAGE [X )^'] = IMAGE [_Y⁺1 }] If the condition is not satisfied, then pixel [X Y] corresponds to the end of the plateau and means 3202 ends processing of means 2818 Other ise, the end of the plateau has not been found and means 3204 selects the next pixel by incrementing the pixel column coordinate Λ^' by 1

Means 3206 then determines whether the end of the current scan line has been reached w ithout finding the end of the plateau by evaluating the condition

Λ' > XF . where XF is the pixel column coordinate of the end of the current scan line If the condition is satisfied then the end of the current scan line has been reached w ithout finding the end of the plateau and means 3206 ends processing of means 2818 Otherwise, processing returns to means 3202 to test the new current pixel

Referring again to Fig 28, after means 2818 searches for the end of a plateau, means 2320 ends processing of subsy stem 2800 if the end of the plateau was not found Otherwise means 2820 directs processing to means 2822, which sets the appropriate state for the next transition search

Referring now to Fig 33, there is shown a block flow diagram for means 2822 of Fig 28. for determining the appropriate state for the next transition search Means 3202 of means 2822 determines whether the current pixel indicates that the state of the next transition search should be "UP" bv ev aluating the follow ing condition

IMAGE [X Y] < IMAGE [X+\ }^"] If the condition is satisfied, then the next search is for a dark -to-bright transition and means 3204 sets the transition search state variable SEARCH to be "UP " Otherw ise, the next search is for a bπght-to- dark transition and means 3206 sets SEARCH to "DOWN "

Referring again to Fig 28. after means 2822 sets the appropriate transition search state, processing returns to means 2806 to search for the next transition In this way . subsystem 2800 searches for transitions and generates subpixel inteφolation v alues for each bar and each space aiong the length of the current scan line

Selection of White and Black Intensity References

As described earlier in this specification in conjunction w ith Figs 14 and 15. subpixel inteφolation is based on calculating signal energy values b, and s, for bars and spaces, respectively The signal energy values for bars and spaces are defined as the areas over and under the gray -scale signal curve, respectively, and are calculated using Equations (11) and (13). respectively In the preferred embodiment described earlier in this specification in conjunction with Figs 14 and 15.7_ma and 7_mιn of Equations (11) and (13) are fixed values defined as being the maximum and minimum pixel intensity levels, respectively, in a histogram generated for the pixel image In an alternative preferred embodiment, 7_max and 7_mιn of Equations (11) and (13) are set to the white and black intensity references 7_Λ and 7_b. respectively, that were introduced in the previous section of this specification in conjunction with Equation (15)

In a preferred embodiment of the present invention, to account for variations in the dynamic range within a pixel image, the white and black intensity references 7_W and 7_b are adaptively selected based on the local dynamic range within the pixel image As the pixel data are processed, whenever a space ider than a specified space-width threshold is detected, the white intensity reference 7„ is updated according to Equation (21) as follows

~ updated ,, __{r τ} previous _rmax (21)

where I^m' is the maximum intensity level in the wide space and C_w is a white-reference weighting factor having a value between 0 and 1.

Similarly, whenever a bar wider than a specified bar-width threshold is detected, the black intensity reference 7_b is updated according to Equation (22) as follows _τ updated _ /, \ _τ previous _τmιn (00)

I_b ~ {1-C_b> ^J*> ^Cb^Jb • ^ΔΔ)

where 7^m,n is the minimum intensity level in the wide bar and C_b is a black-reference weighting factor having a value between 0 and 1 The initial values for the white and black intensity references 7„ and 7_h may be selected as the maximum and minimum intensity levels over a specified region at the beginning of a bar code symbol

Referring again to Fig.24, assume that, at pixel 0. the white intensity reference 7„ is 30 and the black intensity reference 7_b is 12. Assume further that the white- and black-reference weighting factors C„ and C_h are both 0.5 and that the bar- and space-width thresholds are both two pixels Thus, whenever a bar or space wider than two pixels is detected, the corresponding intensity reference is updated according to the appropriate Equation (21) or (22)

For example, the bar at pixels 1-3 is wider than two pixels.7_b""ⁿ is 10. and the black intensity reference 7_b is updated according to Equation (22). such that updated , v _τ previous b = r

(1- ~^Lb> ¹b + c_t ι ¹ _b

= (1. .0-0.5) xl2 + 0. 5xlC (23)

= 11. .0

The space at pixel 4 is not wider than two pixels, so the white intensity reference 7_W is not updated. The black intensity reference 7 is again updated when the bar at pixels 5-7 is detected, such that: -- updated _ ι _τ previous , _ _τmr. It ~ ⁽~¹~^Lt' ¹b ⁺ G_b ._C

= (1.0-0.5) xll.O + 0.5x9 <²⁴>

= 10.0

The white intensity reference /„ is updated according to Equation (21 ) when the space at pixels 8-13 is detected, such that: updated _ / ., _.-, > γ previous — --max

±w ,± L._W) J._W ^L-w¹s

= (1-0.5) 30 + 0.5x32 ⁽²⁵⁾

= 31.0

When calculating the signal energy value b, for a bar during subpixel inteφolation. the current value for the white intensity reference 7_W is preferably used for 7_mlx in Equation (11). Similarly, when calculating the signal energy value s, for a space during subpixel inteφolation. the current value for the black intensity reference 7_b is preferably used for 7_mιn in Equation (13).

Those skilled in the art will recognize that Equations (21 ) and (22) define proportional integral filters. It will be understood that other proportional integral filters may be used to update the values of the white and black intensity references.

Determining Character Choices from Subpixel Inteφolation Results

After subpixel inteφolation has been performed for all of the symbol elements of the detected bar code symbol, character determination subsystem 1118 of stepping subsystem 904 determines the alphanumeric character choices for each of the symbol characters. Subpixel inteφolation generates a signal energy value for each bar and space of the detected bar code symbol. Combinations of bars and spaces in the bar code symbol correspond to symbol characters. Character determination subsystem 1118 uses the signal energy values to determine one or more choices of alphanumeric characters for each of the symbol characters. Subsystem 1118 also computes a confidence factor for each alphanumeric character choice. These character choices and confidence factors are then used by decoding subsystem 114 to create and update the character table used in the checksum analysis described above.

Each bar code symbology has a particular format for the encoding of alphanumeric characters into bars and spaces. In this specification, subsystem 1118 is described in the context of decoding bar code symbols of Code 128 Symbology. although those skilled in the art will understand that the present invention may also employ analogous processing to decode any known symbology. In Code 128 Symbology. each alphanumeric character is represented by a symbol character having three bars and three spaces. The width of every symbol character is 11 modules, where each symbol element (bar or space) is an integral number of modules wide and the minimum width for a symbol element is 1 module. In addition, the sum of the widths of the three bars is always an even number of modules, while the sum of the three space widths is always an odd number of modules. Character determination subsystem 1118 generates one or more choices of alphanumeric characters for each symbol character of three bars and three spaces.

Referring now to Fig. 16. there is shown a graphical representation of bar code symbol character 1600 consisting of three bars 1602. 1604, and 1606. and three spaces 1608. 1610. and 1612. The widths of the symbol elements of symbol character 1600 may be represented by signal energy values />,. b₂. b for the three bars and s,, s₂, s, for the three spaces. These signal energy values are generated by subpixel inteφolation performed by decoding subsystem 114. Character determination subsystem 1118 determines a 1 -module value A^' equivalent to 1 module for symbol character 1600. where:

X = — (b. + s. + b^ s^ b-, ~ s . (26 )

11 - - - - - -

Subsystem 1118 then forms four measured widths /,. /,. /,. /₄ from the signal energy values generated bv decoding subsystem 114 and the 1 -module value A^', where:

t. = - (.b, + s, ) X ' ¹ t₂ = ^ ⁽s. + b₂ ⁾

(27)

t« = ls₂ ⁺ *>₃ ⁾

Each width t_t corresponds to the width along symbol character 1600 from one symbol element edge to the next symbol element edge of the same type. For example, the width /, corresponds to the number of modules from the leading edge of bar 1602 to the leading edge of the next bar - bar 1604. Similarly , the width /_: corresponds to the number of modules from the leading edge of space 1608 to the leading edge of the next space « space 1610. Since bars and spaces are integral numbers of modules wide, ideally the widths /, are integers from 2 to 7. In practice, however, noise may cause deviations from these ideal widths.

Subsystem 1118 compares each measured width /, to the ideal widths to assign one or more ideal widths and deviations from those ideal widths to the measured width. For example, an ideal width of 2.0 may be associated with measured widths /, from 1.3 to 2.7. Similarly, an ideal width of 3.0 may be associated with measured widths /, from 2.3 to 3.7. Some measured widths may be associated with more than one ideal width, e.g.. a measured width of 2.5 would be associated both with ideal width 2.0 and ideal width 3.0. Those skilled in the art ill understand that these ranges may be selected empirically by testing various ranges with known bar code symbols. Assume that the set of measured widths {/,. /_:, r„ / } derived by subpixel inteφolation of character symbol 1600 of Fig. 16 is {2.45. 5.2. 4.9. 2.9} . Subsystem 1118 may select the ideal set {2.0, 5.0. 5.0. 3.0} for this measured set. In that case, a distance measure reflecting the deviations from ideal is the sum of the absolute differences between the ideal set and the measured set. that is. (12.45-2.0 + J5.2-5.0; + |4.9-5.0; + |2.9-3.0|) or 0.85. This distance measure may be used by decoding subsystem 114 as the confidence factor for the alphanumeric character corresponding to the ideal set {2.0, 5.0. 5.0. 3.0} . The closer the measured set is to the ideal set. the smaller the distance measure or confidence factor, and the greater the confidence that the measured set is the ideal set. If no alphanumeric character corresponds to that ideal set. then subsystem 1118 does not select that ideal set as a possible choice for the current symbol character.

Subsystem 1118 will generate alternative choices when the measured widths t_t fall within the ranges of more than one ideal width. Since the measured width /, in character symbol 1600 is 2.45. it falls within the ranges for both a 2.0 and a 3.0. Thus, measured width /, may correspond to a 3.0 instead of a 2.0. and a possible alternative choice for the measured set is the ideal set {3.0. 5.0. 5.0. 3.0 ; . The confidence factor for the alphanumeric character associated with this second ideal set is 0.95. Since the previous character choice has a lower confidence factor than this character choice, the previous character would be the first choice in the character table created by decoding subsystem 114. Other characters are also possible, but assuming the other measured widths /, lie within the ranges of only one ideal width each, subsystem 1118 does not select further alternative choices.

Subsystem 1118 decodes each of the symbol characters in a detected Code 128 bar code symbol by performing similar analysis on each set of three bars and three spaces corresponding to a symbol character. The resulting alphanumeric character choices and associated confidence factors are used by means 906 of decoding subsystem 114 to create and update the character table used to generate character sets for checksum analysis.

Decoding Bar Code Symbols bv Stitching

Referring now to Fig. 17, there is shown a process flow diagram of stitching subsystem 1700 for decoding bar code symbols by stitching according to a preferred embodiment of the present invention. Stitching subsystem 1700 functions substantially in accordance with stepping subsystem 904 except that stitching subsystem 1700 uses each search step to perform subpixel inteφolation of two or more symbol elements of the detected bar code symbol and each search step has one or more symbol elements in common with at least one other search step. That is, there is overlapping of symbol elements between successive search steps. Stitching subsystem 1700 determines the signal energy values to assign to each symbol element by comparing the redundant signal energy values that may exist for that symbol element from two or more different subpixel inteφolations. In a preferred embodiment, means 1702 performs subpixel inteφolation along multiple search steps that may be selected by projecting onto a reference line similarly to that performed by stepping subsystem 904 Each search step is used to determine the signal energy v alue for two or more symbol elements As opposed to stepping subsystem 904. which starts the next search step from where the prev ious search step left off, stitching subsystem 1700 puφosely repeats subpixel inteφolation for symbol elements that have been previously analyzed Thus, the search steps of stitching subsystem 1700 overlap, where those for stepping subsystem 904 follow end to end

Means 1704 then compares the redundant results for each symbol element of the bar code sy mbol to select a single signal energy v alue for that symbol element In a preferred embodiment, this selection mav be performed by av eraging the redundant signal energy values In alternativ e embodiments, other types of statistical analysis may be performed to select a single signal energy value for each sy mbol element After each symbol element is assigned a signal energv value character determination subsystem 1118 of Fig 1 1 may then generate character choices for use by decoding subsv stem 114 as described earlier in this specification

Referring now to Fig 18. there is shown a graphical representation of pixel image 1800 containing bar code symbol 1802 which is not aligned with either the pixel rows or columns of pixel image 1800 Bar code symbol 1802 contains bars 1806 through 1822 and spaces 1824 through 1838 Stitching subsystem 1700 may decode bar code symbol 1802 by stepping along reference line 1804 to perform subpixel interpolation along search steps 1840 through 1864 With each search step, means 1702 generates energy signal values for one or more elements of bar code symbol 1802 For example, means 1702 may perform subpixel inteφolation along search step 1840 to generate energy signal v alues for bar 1806 and space 1824 Similarly, means 1702 may perform subpixel inteφolation along search step 1842 to generate energy signal values for bars 1806 and 1808 and space 1824 Table II contains the elements of bar code symbol 1802 that may be characterized along search steps 1840 through 1864

Each element may be characterized using one or more search steps For example, bar 1808 may be characterized using search steps 1842. 1844, and 1846 Means 1704 may keep track of the symbol elements by assigning each element an offset value corresponding to its location along the bar code symbol, where the offset value is based on the total energy signal value for the preceding elements For example, bar 1806 of bar code symbol 1802 is the first bar in the symbol and has an offset of 0 If means 1702 generates an energy signal value equivalent to 9 modules for bar 1806 along search step 1840. then space 1824 has an offset of 9 Table III presents the offsets and energy signal values that may be generated by means 1702 for search steps 1840 through 1864 Search step 1844 begins with space 1824 having offset 8 based on the energy signal values of 8 and 9 for bar 1806 generated by means 1702 along search steps 1840 and 1842. respectively Table II

SEARCH STEP ELEMENTS

1840 1806 1824 1842 1806 1824, 1808 1844 1824 1808, 1826, 1810 1846 1808 1826, 1810, 1828 1848 1826 1810, 1828, 1812 1830 1850 1810 1828, 1812, 1830, 1814 1852 1812 1830, 1814, 1832 1854 1830 1814 , 1832, 1816, 1834 1856 1832 1816, 1834, 1818, 1836 1858 1816 1834, 1818, 1836, 1820 1860 1834 1818, 1836, 1820, 1838 1822 1862 1836 1820, 1838, 1822 1864 1838 1822

Table III

SEARCH OFF, OFF, OFF, OFF, OFF, OFF,

STEP ELE ELE ELE ELE ELE ELE

1840 0,9 9,8

1842 0,8 8,10 18,8

1844 8,9 17,9 26,4 30,5

1846 17,8 25,5 30,4 34, 9

1848 26,4 30,5 35,9 44,4 48,4

1850 30,5 35,10 45,4 49,5 54,9

1852 44,5 49,4 53,9 62, 9

1854 49,5 54,8 62,9 71,4 75,5

1856 62,8 70,5 75,5 80,4 84,4

1858 71,5 76,4 80,5 85,4 89,8

1860 75,4 79,6 85,3 88,9 97,4 101,4

1862 85,4 89,9 98,4 102,5

1864 97,5 102,4

Since the energy signal values generated by means 1702 for each symbol element along different search steps may be different from one another, means 1704 may average the energ signal values for each element to determine a mean energy signal value to assign to that element, as presented in Table IV for the example of Fig. 18. In alternative embodiments, means 1704 may determine an energy signal value to assign to each element using other types of statistical analysis, including voting schemes.

It will be understood by those skilled in the art that aspects of the present invention may be operated in conjunction with systems that detect and decode bar code symbols using laser scanners. Those skilled in the art will realize that the present invention is not limited to processing Table IV

ENERGY

SIGNAL

ELEMENT VALUES MEAN

1806 9,8 8.5

1824 8,10,9 9.0

1808 8,9,8 8.3

1826 4,5,4 4.3

1810 5,4,5,5 4.8

1828 9,9,10 9.3

1812 4,4,5 4.3

1830 4,5,4,5 4.5

1814 9,9,8 8.7

1832 9,9,8 8.7

1816 4,5,5 4.7

1834 5,5,4,4 4.5

1818 4,5,6 5.0

1836 4,4,3,4 3.8

1820 8,9,9 8.7

1838 4,4,5 4.3

1822 4,5,4 4.3

images generated by CCD devices. For example, the present invention may be used to process images generated by a laser scanner moving peφendicular to a belt direction of travel. In addition, the concept of character tables, containing one or more choices of alphanumeric characters for each symbol character, may be used in the decoding of bar code symbols by systems having laser scanners.

As described earlier in conjunction with Fig. 1, in a preferred embodiment, means 102 of detection system 100 generates a histogram of the entire input pixel image. The histogram is then used to select thresholds for detecting state transitions between bar code symbol quiet zones and start'stop characters. The histogram is also used to select minimum and maximum pixel intensit levels used in subpixel inteφolation, as described earlier in conjunction with Figs. 14 and 15. In an alternative preferred embodiment, detection system 100 performs adaptive thresholding in which the dynamic range of pixel intensity levels is determined for every part of the image separately. In adaptive thresholding, thresholds may be adjusted while scanning or searching through the image. In this preferred embodiment, detection system 100 can process images whose dynamic ranges vary over the image areas due. for example, to nonuniform illumination.

It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain the nature of this invention may be made by those skilled in the art without departing from the principle and scope of the invention as expressed in the following claims.

Claims

CLAIMS What is claimed is-

1 A method for detecting a bar code symbol in a continuous two-dimensional pixel image, comprising the steps of

(a) receiv ing a plurality of rows of said image, said plurality of row s comprising first set of one or more rows.

(b) storing said plurality of rows in a memory,

(c) receiv ιng a new set of one or more rows of said image.

(d) replacing said first set with said new set in said memory : and

(e) processing a subimage to determine whether said subimage comprises at least part of said symbol, said subimage comprising one or more row s of said image in said memory

2 The method of claim 1. wherein said memory is a circular buffer and said firs set comprises the oldest rows of said image in said circular buffer.

3 The method of claim 1. wherein said subimage lies between said first set and said new set in said image.

4. The method of claim 1, wherein step (e) further comprises the step of selecting said subimage to ensure that said symbol can be decoded using said rows of said image in said memory

5. The method of claim 1 , wherein step (e) further comprises the step of searching for a quiet zone of said symbol.

6 The method of claim 1, wherein step (e) comprises the steps of:

( 1 ) selecting a row of said subimage;

(2) scanning along said selected row for a quiet zone of said symbol.

(3) selecting one or more columns of said subimage. and

(4) scanning along said one or more selected columns for said quiet zone

7 The method of claim 6, wherein step (e)(2) comprises the steps of

(0 characterizing one or more transitions along said selected row ; and (ii) determining whether said one or more transitions correspond to said quiet zone.

8. The method of claim 1, further comprising the step of locating the four comers of said symbol.

9. The method of claim 1. further comprising the step of decoding said symbol using subpixel inteφolation.

10. An apparatus for detecting a bar code symbol in a continuous two-dimensional pixel image, comprising:

(a) means for receiving a plurality of rows of said image, said plurality of rows comprising a first set of one or more rows;

(b) means for storing said plurality of rows in a memory;

(c) means for receiving a new set of one or more rows of said image;

(d) means for replacing said first set with said new set in said memory; and

(e) means for processing a subimage to determine whether said subimage comprises at least a part of said symbol, said subimage comprising one or more rows of said image in said memory.

1 1 . The apparatus of claim 10. wherein said memory is a circular buffer and said first set comprises the oldest rows of said image in said circular buffer.

12. The apparatus of claim 10, wherein said subimage lies between said first set and said new set in said image.

13. The apparatus of claim 10, wherein said means (e) further comprises means for selecting said subimage to ensure that said symbol can be decoded using said rows of said image in said memory.

14. The apparatus of claim 10, wherein said means (e) further comprises means for searching for a quiet zone of said symbol

15. The apparatus of claim 10. wherein said means (e) comprises:

(1 ) means for selecting a row of said subimage;

(2) means for scanning along said selected row for a quiet zone of said symbol:

(3) means for selecting one or more columns of said subimage; and (4) means for scanning along said one or more selected columns for said quiet zone

16. The apparatus of claim 15, wherein said means (e)(2) comprises

( i) means for characterizing one or more transitions along said selected row: and

(ii) means for determining whether said one or more transitions correspond to said quiet zone

P The apparatus of claim 10. further comprising means for locating the four comers of said symbol

18 The apparatus of claim 10. further comprising means for decoding said symbol using subpixel inteφolation

19 A method for decoding a bar code symbol, comprising the steps of:

(a) receiving a signal representative of said symbol.

(b) searching said signal in one dimension to locate a first point corresponding to a first element of said symbol, wherein step (b) comprises the steps of:

( 1 ) locating a first transition;

(2) characterizing said first transition to determine whether said first transition corresponds to a first edge of said first element;

(3 ) locating a second transition;

(4) characterizing said second transition to determine whether said second transition corresponds to a second edge of said first element; and

(5) locating said first point in accordance with said first and second transitions;

(c) searching said signal in said one dimension to locate a second point corresponding to a second element;

(d) computing a value representative of the signal energy between said first and second points.

(e) determining the width of a third element between said first and second elements in accordance with said value; and

(f) decoding said bar code symbol in accordance with said determined width.

20. The method of claim 1. wherein said value is representative of an area described by said signal between said first and second points.

21. The method of claim 1, wherein step (b)(2) further comprises the steps of:

(i) determining a first partial score corresponding to said first transition;

(ii) determining a second partial score corresponding to said first transition: and

(iii) determining whether said first transition corresponds to said first edge in accordance with said first and second partial scores.

22. The method of claim 3, wherein said first partial score is a function of the magnitude of said first transition and said second partial score is a function of the intensity level of said first transition relative to the local dynamic range of said signal.

23. An apparatus for decoding a bar code symbol, comprising:

(a) means for receiving a signal representative of said symbol:

(b) means for searching said signal in one dimension to locate a first point corresponding to a first element of said symbol, wherein means (b) comprises:

(1 ) means for locating a first transition;

(2) means for characterizing said first transition to determine whether said first transition corresponds to a first edge of said first element;

(3) means for locating a second transition:

(4) means for characterizing said second transition to determine whether said second transition corresponds to a second edge of said first element: and

(5) means for locating said first point in accordance with said first and second transitions:

(c) means for searching said signal in said one dimension to locate a second point corresponding to a second element;

(d) means for computing a value representative of the signal energy between said first and second points;

(e) means for determining the width of a third element between said first and second elements in accordance with said value; and

(f) means for decoding said bar code symbol in accordance with said determined width. 24 The apparatus of claim 5, wherein said value is representati e of an area described by said signal between said first and second points

25 The apparatus of claim 5. wherein means (b)(2) further comprises

(i) means for determining a first partial score corresponding to said first transition.

(n) means for determining a second partial score corresponding to said first transition, and

(in) means for determining whether said first transition corresponds to said first edge in accordance ith said first and second partial scores

26 The apparatus of claim 7, wherein said first partial score is a function of the magnitude of said first transition and said second partial score is a function of the intensity level of said first transition relativ e to the local dynamic range of said signal

27 A method for decoding a bar code symbol, comprising the steps of

(a) receiving a signal representative of said symbol.

(b) searching said signal to locate a first point corresponding to a first element, said first element being followed by a second element and said second element being followed by a third element.

(c) characterizing the local dynamic range corresponding to said second element.

(d) searching said signal to locate a second point corresponding to said third element

(e) computing a value representative of the signal energy between said first and second points in accordance w ith said local dynamic range,

(f) determining the width of said second element in accordance with said value, and

(g) decoding said bar code symbol in accordance w ith said determined idth

28 The method of claim 9, wherein said value is representative of an area described by said signal between said first and second points

29 The method of claim 9, wherein step (c) comprises the steps of

( 1 ) determining a white intensity reference for said second element, and

(2) determining a black intensity reference for said second element, and step (e) comprises the steps of

(1 ) computing said value in accordance with said black intensity reference if said second element is a space in said bar code symbol, and (2) computing said value in accordance with said white intensity reference if said second element is a bar in said bar code symbol

30 The method of claim 1 1, wherein step (c)(1 ) comprises the step of determining said white intensity reference for said element using a proportional integral filter

31 An apparatus for decoding a bar code symbol, comprising

(a) means for receiving a signal representative of said symbol.

(b) means for searching said signal to locate a first point corresponding to a first element said first element being followed by a second element and said second element being followed by a third element

(c) means for characterizing the local dynamic range corresponding to said second element

(d) means for searching said signal to locate a second point corresponding to said third element.

(e) means for computing a value representative of the signal energy between said first and second points in accordance with said local dynamic range,

(0 means for determining the width of said second element in accordance w ith said value and

(g) means for decoding said bar code symbol in accordance w ith said determined ldth

32 The apparatus of claim 13, wherein said value is representativ e of an area described by said signal between said first and second points

33 The apparatus of claim 13, wherein means (c) comprises

( 1 ) means for determining a white intensity reference for said second element and

(2) means for determining a black intensity reference for said second element, and means (ej comprises

(1 ) means for computing said value in accordance ith said black intensity reference if said second element is a space in said bar code symbol, and

(2) means for computing said value in accordance with said white intensity reference if said second element is a bar in said bar code symbol 34 The apparatus of claim 15, wherein means (c)( l ) comprises means for determining said white intensity reference for said element using a proportional integral filter