Method of scanning indicia using selective sampling

[0002] This application is a divisional application of and claims priority to U.S. application Ser. No. 08/455,216, filed on May 31, 1995 now U.S. Pat. No. 6,170,709.

[0003] The invention relates to a method of scanning indicia using selective sampling, and particularly although not exclusively to a method of reading bar codes using a laser scanner.

[0004] Various optical readers and optical scanning systems have been developed heretofore for reading bar code symbols appearing on a label or on the surface of an article. The bar code symbol itself is a coded pattern of indicia comprising a series of adjacent bars and spaces of various widths, the bars and spaces having different light reflecting characteristics.

[0005] A number of different bar code standards or symbologies exist. These symbologies include, for example, UPC/EAN, Code 128, Codabar, and Interleaved 2 of 5. The readers and scanning systems electro-optically decode each symbol to produce multiple alphanumerical characters that are intended to be descriptive of the article or some characteristic thereof. Such characters are typically represented in digital from as an input to a data processing system for applications in point-of-scale processing, inventory control, and the like. Scanning systems of this general type have been disclosed, for example, in U.S. Pat. Nos. 4,251,798; 4,360,798; 4,369,361; 4,387,297; 4,409,470 and 4,460,120, all of which have been assigned to Symbol Technologies, Inc., the assignee of this application. As disclosed in some of the above patents, one commonly used example of such a scanning system functions by scanning the laser beam in a line across a symbol. The symbol, composed of alternating, rectangular, reflective and non-reflective segments of various widths, reflects a portion of this lasex light. A photo detector then detects this reflected light and creates an electrical signal indicative of the intensity of the received light. The electronic circuitry or software of the scanning system decodes the electrical signal creating a digital representation of the data represented by the symbol scanned.

[0006] Typically, a scanner includes a light source such as a gas laser or semiconductor laser that generates a light beam. The use of semiconductor lasers as the light source in scanner systems is especially desirable because of their small size, low cost and low power requirements. The light beam is optically modified, typically by a lens, to form a beam spot of a certain size at a prescribed distance. It is preferred that the beam spot size be no larger than approximately the minimum width between regions of different light reflectivities, i.e., the bars and spaces of the symbol.

[0007] A scanner also includes a scanning component and a photo detector. The scanning component may either sweep the beam spot across the symbol and trace a scan line across the past the symbol, or scan the field of view of the scanner, or do both. The photodetector has a field of view which extends across and slightly past the symbol and functions to detect light reflected from the symbol. The analog electrical signal from the photodetector is first typically converted into a pulse width modulated digital signal, with the widths corresponding to the physical widths of the bars and spaces. This signal is then decoded according to the specific symbology into a binary representation of the date encoded in the symbol to the alphanumeric characters so represented.

[0008] In the prior art described above, a digitizer circuit may be used to translate the analog signal into a digital representation called a Digital Bar Pattern (or DBP). This simple digital representation of the data works extremely well in many situations, although it may sometimes be susceptible to unrecoverable errors if the bar code symbol to be read has substantial noise associated with it. With this prior art representation, a single extra edge detected or shifted due to noise may prevent proper decoding.

[0009] One straightforward way to acquire a more accurate representation of the bar code, for example for more aggressive or adaptive decoding, would be to sample the analog signal above the Nyquist rate, store the analog signal in memory, and then apply digital signal processing (DSP) techniques. This solution is, however, very expensive due to the large amount of samples required and the high speed processing that is necessary.

[0010] There is accordingly a need to provide a relatively cheap and reliable method of decoding an indicia (for example a bar code Symbol) after the optical detection system has transduced it into a distorted analog waveform. Such a need is particularly acute where it is desired to decode the symbol aggressively, that is by attempting to decode after a single scan.

[0011] It is an object of the present invention to aim to meet this need.

[0012] It is a further object of the invention to provide an efficient and economical means of acquiring an improved representation of the bar code signal.

[0013] According to the present invention there is provided a method of reading an indicia comprising areas or differing light reflectivity, comprising:

[0014] a) detecting light reflected from the indicia and producing an electrical signal representative thereof;

[0015] b) selectively sampling the signal, to produce a series of samples, at a sequence or points determined by detected features within the signal;

[0016] c) attempting to decode the indicia using at least some of the samples in the series and, if the attempt was unsuccessful:

[0017] i) analyzing the samples to provide information on the extent to which the samples appear to represent data corresponding to the indicia; and

[0018] ii) repeating steps (a) and (b), adapting the producing of the electrical signal or the selective sampling according to the said information.

[0019] The method of the present invention allows aggressive and reliable bar code symbol decoding, after the optical detection system in the scanner has transduced it into a distorted analog waveform.

[0020] The invention allows in particular an efficient and economical means of acquiring a more accurate representation of the bar code signal (or a signal corresponding to any other indicia to be read) by selectively sampling the analog signal, or a processed analog signal at a rate which is well below the Nyquist rate. The sample points are not uniform and are chosen to represent key features related to the signal.

[0021] If an attempted decode fails, based upon the samples that have been obtained, mechanical, electrical or logical adaptations are made to the scanner in an attempt to provide an improved decode on the next scan. To that end, the decoder analyses the samples to provide information on the extent to which the samples appear to be represent data corresponding to the indicia, and the extent to which the samples are spurious (for example because they represent noise). The information thus determined is used to provide feed-back to adapt the scanner to the current scanning environment, thereby providing improved performance on the next subsequent scan.

[0022] There are many adaptations that could be made, on the basis of the information that has been determined, for example adapting the signal processing of the analog electrical signal, or changing noise thresholds, frequency bandwidths, deconvolution filters, scanning speed, scanning pattern, and laser focusing. Any one or any combination of these may be adaptively altered in the method of the present invention.

[0023] A timing signal is preferably produced which synchronizes and/or provides timing information on the samples that have been taken. In the preferred embodiment, the timing signal is a square wave which changes state whenever a sample has been taken. The timing signal provides further information which is used by the decoder, in association with the values of the samples themselves, thereby enabling the decoder to attempt to decode the indicia.

[0024] In the preferred embodiment, a sample is taken of an analog electrical signal which is representative of light which has been reflected from the indicia at positions which correspond to peaks in the derivative of the said signal. A minimum rejection level may be provided, and the detection logic arranged so that no sample is taken if the corresponding peak is smaller than the minimum level. The value of that minimum level may be one of the adaptive parameters which may be altered according to the estimated amount of noise that has been round on analysis of previous samples.

[0025] The method of the present invention may be particularly useful in devices which make use of non-conventional optics, for example axicon or holographic optics. Such optics may increase the working range of a laser scanner significantly, as is described for example in U.S. Pat. No. 5,080,456. The profile produced by such non-conventional optics are multimodal and contain side lobes. These side lobes introduce additional “wiggles” or bumps on the analog signal. These additional “wiggles”, if detected by a standard digitizer, will most probably result in an unrecoverable error in the bar code representation, thereby making the system less reliable. However, if such non-conventional optics are used in conjunction with the method of the present invention, a much more robust system can be created. Small wiggles introduced by the scanning beam profile may be ignored by the decoder, merely by properly selecting the larger features and ignoring the smaller ones.

[0026] The method of the present invention is also particularly useful in scanners that make use of enhancement filters to increase the depth of modulation, for example as described in U.S. Pat. No. 5,140,146. In such devices, the resulting enhanced analog signal normally exhibits “ringing”. This ringing introduces additional “wiggles” in the analog signal, similar to those described above. However, if enhancement filters are used in conjunction with the method of the present invention, a much more robust system can be created. Small wiggles introduced by the enhancement filter can be ignored by the decoder by properly selecting the larger features and ignoring the smaller ones. This also reduces the trade-off that has to be made between reading high density bar code symbols with a very low depth of modulation, and low quality bar code symbols that might include printing noise (for example dot matrix bar codes).

[0027] The invention may be carried into practice in a number of ways and one specific embodiment will be described, by way of example, with reference to the accompanying drawings, in which:

[0028] FIG. 1 is a block diagram of an exemplary apparatus for use with a method according to the present invention;

[0029] FIG. 2 shows an exemplary method according to the present invention, for decoding a bar code signal: and

[0030] FIG. 3 is a flow chart of the operation of the decoder shown in FIG. 1.

[0031] Turning first to FIG. 1, there is shown a block diagram of an apparatus which embodies the preferred method of the present invention.

[0032] The analog signal 10 to be decoded, which may be distorted and/or which may have noise associated with it, is applied in parallel to first and second signal processing blocks 12, 14. Although two separate signal processing blocks are shown, some or all of the signal processing functions may be shared. For example, a derivative function could be shared between the two blocks. The first signal processing block 12 operates upon the signal in any desired manner, to derive a waveform which is output along a line 16 and applied to an A/D converter 18. The output waveform need not be a simple function of the analog signal 10. For example, the output waveform may be derived from the analog signal using a combination of sample and hold circuits, derivatives, threshold functions and subtractors. Nonlinear circuits such as clamping circuits may also be utilized.

[0033] The output waveform is selectively sampled by the A/D converter 18 according to signals provided by a sampling decision and timing generation block 20.

[0034] The second signal processing block 14 receives the analog signal 10, and performs the processing that is required by the sampling decision and timing generation block 20. The block 20 decides when a selective sample should occur and generates the appropriate timing signal 22, which is passed to a decoder 24. The appropriate signal is also passed to the A/D converter 18.

[0035] The detailed logic within the block 20, which determines exactly when the output waveform along the line 16 is to be sampled, may be chosen according to the particular application. The decision criteria will, however, frequently involve a selected noise threshold, with features in the signal below that threshold being ignored. A specific example is shown in FIG. 2, which will be described below.

[0036] The main purpose of the timing signal 22 is to synchronize the transfer of the selective samples to the decoder. This is necessary due to non-uniform sampling of the waveform. The timing signal provides crucial timing information such as the time between the selective samples.

[0037] The timing signal need not be a single signal but could, in some circumstances, be a multiple signal on a plurality of digital lines. Alternatively, the timing information could be multiplexed on a single line. There may be situations, for example, where it is convenient to have two digital lines, one for positive peaks which have been detected in the output signal on the line 16, and one for negative peaks.

[0038] Although synchronization is the timing signal's main function, the timing signal may in itself contain additional information about the waveform that the A/D samples do not convey. Additional pulses can, for example, selectively send additional timing information about the original waveform. The timing signal may, for example, not only synchronize the data transfer but may also contain edge rise time information represented as a pulse width. Such a concept is disclosed in a patent application filed concurrently herewith entitled “Optical Scanners and Signal Processors Therefor”, inventors David Goren, Stephen Shellhammer, Harry Kuchenbrod, Donna Pandolfo, Gary Serbin, Guy Cipriani, and Edward Barkin, assigned to the same assignee as the present invention. The information could also be used without the A/D converter for a very low cost implementation: see for example our copending U.S. patent application number.

[0039] The A/D converter 18 receives the output signal along the line 16, and selectively samples it according to instructions received from the sampling decision and timing generation block 20. The sampled n-bit output is passed along the line 26 to the decoder 24.

[0040] The A/D converter 18 may include a sample and hold circuit if required. Due to the slower date rate compared with sampling the analog signal at the Nyquist rate, a relatively slow and relatively inexpensive A/D converter can be used. The number of bits required depends on the accuracy of the feature being measured, but normally 4 to 8 bits will be sufficient. The A/D converter may, if necessary, be bipolar to contain signed data. For example, if the peaks of the first derivative of the analog signal 10 are above a reference voltage, the peaks can be positive. If the peaks are below the reference voltage, the values may be negative.

[0041] A flow chart of the operation of the decoder 24 is shown in FIG. 3. The decoder first acquires and stores the selective samples and the timing information. This information will normally contain both the features of the waveform that identify the bar code or other indicia (for example the bar code edges) as well as unwanted noise. The decoder then uses an appropriate algorithm (the details of which are well within the scope of a skilled man in the art) to attempt to identify which samples are noise and which samples represent the indicia to be decoded. Typically, the algorithm will use a combination of trial and error and data analysis techniques, such as statistical classification. This analysis will also lead to an estimate of the coding environment, for example the noise level and the distortion levels. An attempt is then made to decode the indicia using only those features which have been determined by the algorithm to represent the indicia.

[0042] Added decode security may be required, according to the algorithms estimate of the difficulty of the decode environment. For example, the decoder may require additional redundancy before signalling a successful decode if it determines that a high noise level is present If the decode is unsuccessful, a feed-back signal or series of signals is sent from the decoder to the second signal processing block 14 and the sample decision and timing generation block 20. These react to the signals by adapting the scanner to the scanning environment. Another scan of the indicia to be decoded may then be taken, this being processed by the adapted electronics and/or digital logic for a second attempt to achieve a satisfactory decode.

[0043] The adaptations of the scanner may include, inter alia, changing noise thresholds, signal filtering, frequency bandwidths, enhancement or deconvolution filters, and other electronic and/or digital logic. The mechanical/optical features of the scanner may also be adaptive, for example the system may automatically change the intensity of the laser beam used for scanning, the laser focusing, scanning speed and pattern, or other variables.

[0044] Returning to FIG. 3, it will be seen that at step 110 the system acquires a scan of selectively sampled data and timing information. The decoder then attempts to estimate the scanning environment, and to deal as far as possible with noise and with systematic inaccuracies in the data. This is carried out at step 112. At step 114, the decoder attempts to decode the bar code (or other indicia) using only those samples which have been determined to represent real data. At step 116, a test is made to see whether the decode has been successful. If it has, the algorithm finishes at step 118. If the decode was unsuccessful, the scanner is adapted to the scanning environment at step 120, and the process is repeated using a new scan.

[0045] A simple embodiment of the present invention is illustrated in FIG. 2. As illustrated, the bar code symbol 100 to be decoded includes a small flaw 40.

[0046] The symbol 100 is scanned in the usual way, and the first derivative 42 of the raw analog signal is determined. In this embodiment, it is the peak values of the first derivative signal which are used as the selective sample points. These peaks may be positive or negative, and typical negative peak being illustrated in the drawing by the arrow 44.

[0047] The sample decision and timing generation logic is arranged to output a timing signal 22 which changes state at each of the selected sample points.

[0048] The decision logic within the block 20 (FIG. 1) is arranged to accept a sample only when the first derivative is larger than a positive minimum level 46 or is lower than a negative minimum level 48. Accordingly, the small peak 50, associated with the flaw 40 corresponds to an accepted sample point, because it lies outside the lines 46, 48, whereas the even smaller peak 52 is not accepted.

[0049] The peaks in the first derivative signal 42 represent inflection points of the original raw data signal, and are defined as bar code edge locations in may prior art digitizers. The decoder 24 reads in all the peak values, some of which of course represent real edges and others which represent noise. The decoder then decides which edges are real, for example by trial and error or by histogram analysis. Once the real edges have been chosen, the bar code signal can be decoded by standard methods. If the decode is unsuccessful, it is clear that the edges have not been chosen correctly, and the adaptive algorithm shown in FIG. 3 comes into play.

[0050] From the peaks of the first derivative and the bar code decoded or partially decoded, information about the decoding environment can be determined. For example, a large number of false edges can indicate a noisy environment. The various heights of the peaks of the real edges can also be used to estimate the ratio of the scanning spot size to the bar sizes being scanned. This information about the scanning environment is then used to adapt the mechanical, optical, electronic or digital features of the scanner prior to a further scar being taken and another attempt being made to decode the bar code symbol. In an alterative version of the method, selective sampling may be performed on more than one features simultaneously. This could be done either with multiple A/D convertors, or alternatively by using a single A/D convertor and multiplexinq the output.

[0051] It is of course not essential for the preferred method to be embodied within the specific architecture shown in FIG. 1. There are many alternatives. For example, the first and second signal processing blocks 12, 14 could be merged into a single unit, or even omitted altogether for suitable analog input signals 10.

[0052] As previously mentioned, the method that has been described above may find particular application in laser scanners of the type in which the received beam profile is multimodal, and contains side lobes which are an artifact of the imaging process. The examples scanners using non-conventional optics such as axicon or holographic optics, and scanners using enhancement filters to increase depth of modulation.

[0053] Although the invention has been specifically described in connection with the decoding of indicia, particularly bar code symbols, the technique could be applied to many different types of signals and applications. More generally, the method the present invention may be applied to pattern recognition, either in detected images or in detected sounds. The method could be used, for example, in voice recognition techniques and/or speech recognition.

[0054] While this invention has been described with reference to a specific embodiment, the above description is not meant to be construed in a limiting sense. Various modifications of the disclosed embodiments, as well as other embodiments of the invention, will be apparent to persons skilled in the art upon reference to this description. It is accordingly intended that the appended claims will cover any and all such modifications and embodiments as fall within the scope and spirit of the invention.