Bar code scanning

From Scholarpedia
Jerry Swartz et al. (2012), Scholarpedia, 7(9):12215. doi:10.4249/scholarpedia.12215 revision #137139 [link to/cite this article]
(Redirected from Barcodes)
Jump to: navigation, search
Post-publication activity

Curator: Jerry Swartz

Figure 1: Encoding the binary string 100111000 by a delta code (top) and width code (bottom).
Figure 2: 2D bar code.

Introduced more than 50 years ago, linear bar codes have spread to virtually all industries (e.g., retailers, military, airlines, overnight shipping, the medical field, and any business where tracking or monitoring is involved). The bar code industry uses the term symbology to denote the particular bar coding scheme, while the term symbol refers to the printed bar code itself. In all cases, the information is encoded in the width of the bars (dark) and spaces (light), but in different ways.

Contents

Encoding symbologies

Delta codes vs. width codes

There are two fundamental ways of encoding information in such a one-dimensional scheme. In one, we subdivide the available interval into modules with identical width, and assign 1’s and 0’s to each module. Modules with 1’s are printed to form the bars, while modules with 0’s correspond to spaces. A single bar or space may contain many modules. Such schemes are called delta codes in communication theory since ratios are formed during the decoding process. These codes are advantageous in accuracy and security.

In another scheme, we assign each bit to a bar or space and make that element wide if the bit is one and narrow if bit is 0. We refer to all such schemes as width-modulated codes, although the common name used in the bar coding industry is binary codes.

Figure 1 shows two encodings of the binary string 100111000. In both cases the minimum printed module width is the same. The delta code requires nine such widths (the number of bits), while the width code requires 13 such widths if a wide element is twice as wide as a narrow element.

Code density

If a delta code has \(n\) modules and can generate \(S (n)\) code words, then we define its information content, per module, as:

\[\tag{1} H(n)=\frac{1}{n}\log_2 S(n) \]


If we need a width \(W\) to print the \(n\) modules on the substrate, then we define the density of the code (in bits per unit length) as:

\[\tag{2} D_w(n)=\frac{1}{W}\log_2 S_w(n) \]

where \(X\) denotes the module width. An unrestricted delta code can encode up to \(2^n\) code words so that its information density is:

\[\tag{3} D_{\delta}(n)=\frac{1}{W}\log_2 2^n = \frac{n}{W}=\frac{1}{X} \]

This equation is a special case of a well-known result by Shannon (1948). The first fraction in the above equation equals 1.618 and the second equals -0.618, so that as \(n\) increases, the second term goes to zero. For values of \(n\) greater than 5, the following provides a very good approximation:

\[\tag{4} D(n)=\frac{1}{W}\log_2 S(n) = + \frac{1}{X} H(n) \]

Therefore, the density of an unrestricted width code is:

\[\tag{5} D_w(n) = \frac{1}{W} \log_2 S_w(n) \approx \frac{1}{X} \log_2 1.618 + \frac{ \log_2 (1.618 \cdot 0.4472) }{W} \]

\[\tag{6} D_w(n)\approx \frac{0.694}{X} - \frac{0.467}{W} \]

Thus, width codes have a density of approximately 70 percent that of delta codes for the same module width.

Types of symbologies

One-dimensional bar codes

In the basic one-dimensional bar code, information is linearly encoded with intervals of alternating diffuse reflectivity (highs and lows signal-wise), usually black and white in color. The intervals are actually stored as rectangles whose vertical height carry no information but facilitates the scanning process and electronically corresponds to the actual bars and spaces of the symbol. The term bars denote the rectangles with a darker foreground color, while the term spaces denotes the light intervals (or as a background color) between the bars. There are many different bar code symbologies; a few of them are briefly described in the following paragraphs.

Universal product code and European article numbering

Universal Product Code. UPC is the (delta code) symbology historically used in US retailing. What we describe here is version A, where each symbol encodes 12 digits. UPC can only represent 20 characters (10 each of 2 different parities) and digits 0-9. However, all versions use the same basic linear structure for the code words. Each UPC code word consists of two bars and two spaces having a total width of seven modules (the building block width of the symbol). The number of possible code words can be computed as follows: two bars and two spaces require three dividers in one of six positions.

While symbols must be readable by scanning in either direction, we also want to detect the direction of scanning. UPC achieves that by assigning two code words for each digit: those used on the right part of the symbol start with a bar and those used on the left half start with a space. UPC specifies a symbol format as shown in Figure 2.

Figure 3: Illustration of the specifications of the UPC-A symbol. The readable characters are normally printed in OCR-B font. The diagram is not drawn to scale.

The symbol contains the following groups of code words:

  • a left guard pattern 101 (bar module – space module – bar module)
  • industry designation digit
  • left 5 digits correspond to manufacturer
  • six digits of odd parity:
    • One digit denoting the industry type (such as 0 for grocery, 3 for pharmaceutical, etc.)
    • five digits with the manufacturer’s code
  • a center guard pattern 01010 of five modules
  • six digits of even parity:
    • five digits with the item code
    • one check digit (sum of the other digits to double check for errors)
  • a right guard pattern 101
  • right 5 digits correspond to the product/item number from manufacturer
  • last digit is a check digit for decoding security

The EAN (European Article Number) code is very similar to UPC except that it is a 13-character symbol in which the first two characters represent the country (flag) in Europe.

Binary Codes

Codabar

Codabar is one of the simplest and earliest symbologies (e.g., used in blood banking). It is discrete, self-checking and variable in length. The symbology is presented as a series of groups of four bars and three intervening spaces. It has 18 different dimensions for bar and space widths.

Code 39
Table 1 Swartz bar code.png
Table 1 - Part of the specification for Code 39.

Code 39 (Three of Nine). Code 39 is the most used binary code with three wide elements out of a total of nine: five bars and four spaces between them. It was the initial standard for the Department of Defense in 1980. The total number of code words that it can generate is the number of ways three items can be chosen out of nine, or 84. It has code words for the 10 digits, the 26 letters, and eight special characters (hyphen, period, space, *, $, /, +, and %) so that a total of 44 code words are used. The asterisk is used only as the first and the last code word of a symbol.

The patterns for both the bars and the spaces have been chosen in such a way that changing a single bit in either of them results in an illegal code word. The code is called self-checking/self-clocking for that reason.

Two-dimensional bar codes

A relatively recent development in bar coding is the introduction of two-dimensional codes called stacked or matrix bar codes. Two-dimensional symbols can provide more information density and better security/encryption. Most two-dimensional bar codes stack one-dimensional codes in rows as the basic encoding scheme. Code 49, introduced in 1987, was based on a new \((n, k)\) one-dimensional code with 16 modules and four pairs of bars and spaces. PDF417 and data matrix two-dimensional codes started in 1989 and the QRcode was developed in Japan 1994. PDF417 is based on the UPC scheme, using a new \((n, k)\) code with 17 modules and 4 pairs of bars and spaces. Symbol Technologies developed the PDF417 2-dimensional bar code which took 10 years to gain acceptance in US government, General Motors and airport applications (e.g., airplane ticket and baggage).

For more details on bar code specifications and for a complete review for all the existing symbologies, refer to the bar coding literature.9-11

Obstacles for bar codes

Bar codes were not always accepted with open arms. Some politicians like Ellen Haas launched an anti-UPC campaign fearing bar codes may lead to job loss. In the 1970s, Shop Rite wrote to International Paper requesting the printing of scannable bar codes on Shop Rite’s labels. Fearing change, the Vice President of International Paper called Jerry and said that did not like being told to change their printing process, especially since they owned 50% of the forests in the US.

The cosmetic companies were particularly difficult to get to commit due to the aesthetics of their small item packaging. Fabergé (back then) just unveiled a new green, black, and silver (colors that don’t readily lead to a scannable bar code) packaging for the earliest supermarket cologne sales, and had asked Symbol to design a scannable bar code combination for them – a difficult project. Fabergé’s director of quality control ultimately said to Jerry “You’re really smart; you have a Ph.D. Can’t you find anything else to do besides work with bar codes?” Luckily Jerry did not follow the advice and did pursue bar code systems, helping the growth of the industry.

Importance of bar codes

The bar code has simplified operations in the retailing and shipping industries with faster, more accurate and cheaper applications. Quoting a past issue of the New Yorker, ‘In a world without bar codes, if you placed an order in mid-December, you’d be hard pressed to get it by Christmas. Going forward, automated warehouses are as much part of ecommerce as websites, in fact, it’s the ’tougher part’.

Land’s End head of operations, Phil Shaker, when asked what he would do if he had to choose between the two great innovations of the past 25 years: the bar code, which has transformed the back-end of the business or the internet which is transforming the front-end, he paused, “I’d take the internet” he said finally, towing the line retailers followed even in those days. Then he smiled and said, “but of course, if we’d lose bar codes I’d retire the next day”.

Types of readers and reading reliability

Manual readers: Light pens or wands

A pen-type manual (swipe) reader consisting of a light source/fiber optic core and a photodiode, is a pen (wand) type structure with a ball lens tip that makes direct contact to “swipe” the bar code. The intensity of light reflected back is transduced by the photodiode and decoded to represent bars and spaces. The reader weakness is the manual motion, which causes obvious variations in velocity and angle.

Automatic (machine) scanning readers

Laser/moving beam scanners

The next generation of portable devices consisted of noncontact automatic laser scanners for reading the bar code. The first such generation of laser scanners used (relatively large [632.8 nm (red)] TEM-00) Helium-Neon laser tubes in the 1970-80’s, which later evolved to solid-state semiconductor lasers as their emitted light became visible and their price relatively inexpensive (under $100). The scanners can be housed in either today’s mobile handhelds or large stationary units. The mechanism consists of a constantly moving beam scan element (e.g., revolving polygons, oscillating mirrors, holograms or Micro Electro Mechanical Systems [MEMS]), which creates an automatic scan rate of typically at least 40 scans per second. The analog signal received by the photodiode is filtered and amplified, converted into a digital signal, which is then analyzed by the decoder.

CCD scanners and other imagers

In CCD (charge-coupled device) scanners (non-laser imaging/illumination), there are hundreds to thousands of tiny light sensors in the reading head, measuring the light intensity reflected from the bar code symbol and a light-emitting diode (LED) based illumination source. A voltage pattern corresponding to the symbol (bar code) is generated in the reader by measuring voltages across (or charges in) each sensor.

Starting in the late 1990s, a new category of bar-code scanner based on digital imaging technology began to be developed. This type of scanner is essentially a miniature camera which captures an image of a one-dimensional or especially a two-dimensional bar-code that is then processed by sophisticated software to recover its information content.

The rise of these “imaging” scanners was made possible in part by the rapid improvement in digital image sensor technology driven by the new digital photography industry. Another essential technology element was the appearance of very powerful, yet cheap, microprocessors and digital signal processors used in the new miniature digital device market which was taking off at about the same time.

Advances in application of physical optical principles to scanning also revealed that fundamental limits on performance of imagers was not much below that of laser-based scanners (E. Barkan, M. Stern, J. Katz, E. Marom). It was recognized that the ray bundle associated with an individual pixel is analogous to a focused laser beam, and that diffraction limits for this bundle are only slightly less favorable than those for such a beam. Moreover, it was realized that the incoherent illumination used for imaging would eliminate the problem of “laser speckle” which had become limiting in miniature laser scanner engines.

At the level of scanning product design and manufacturing, imagers’ lack of moving parts may ultimately lead to less expensive and more reliable devices. In addition, the underlying image processing capability can be employed in devices that are not mainly intended as scanners, such as cell phones with cameras.

Beyond these technical advances, it became increasingly clear that imaging scanners have some intrinsic advantages. These include the ability to read any 2-dimensional code, as well as the ability to capture general image data such as faces or documents. This general imaging capability fits naturally into a generalized data capture model for scanners when used in modern data-intensive IT environments.

Naturally, imaging scanners also have some weaknesses. They may have problems with long scan distances at low light levels, as in warehouses, as well as in applications requiring very high-speed code capture.

Other scanner types used over the decades include omnidirectional bar code laser high-speed scanners, video camera readers, down to miniature (CCD two-dimensional array) cell phone camera-based bar code readers.

Reliability of a laser scanner

Figure 4: Percentage of successful decodes after (n) multiple scanning attempts obtained from an automatic (e.g., laser) scanner, even if the bar code is poorly printed; p0 is the single attempt at decode probability, and after n attempts, we get the pn graph above.

Due to the automatic (scan element) scanning attempts made by a laser scanner versus a manual wand, reliability/probability of success reaches almost 100% in correctly decoding a bar code symbol (see Figure 3).

\[\tag{7} p_n = 1-(1-p)^n \]

The origin of the moving beam laser scanner

The hand-held moving beam laser scanner was born from a classic “Aha!” moment. One evening, a single parent struggling entrepreneur brought home a new toy from work - the laser pointer - to entertain his three children. He would shine the light on moving car doors outside his window. Although the light source was fixed, the moving car was completely scanned in a smooth hand motion. This was the Eureka moment that led to the development of the handheld moving beam laser bar code reader/scanner.

Dr. Jerome Swartz would then become the co-founder of Symbol Technologies in 1975, one of the leading manufacturers of bar code scanners and communications technologies through the ‘80s and ‘90s. Back then, Symbol was a struggling startup operating on sweat equity – more sweat than equity, the future was the end of the month, where another credit card was maxed-out to pay the infant company’s expenses. Initially, Symbol was venture-capitalized from Holland and Germany with 6 more rounds of VC and public financing over the next 10 years.

Scanning/scanner design

History behind the original design

Figure 5: Original LS 1000 prototype sketch.

Jerry went to a trade show in 1980 with a LS 1000 prototype sketch, which was still being developed in the lab (See Figure 4). They had no resources, just a patent application and a dream.

Designing and co-developing the LS 7000 (Symbol’s first flagship volume product) was based on a laser that did not yet exist. The gun-shaped handheld laser scanner tube required a HeNe (Helium Neon) laser no longer than 5-6 inches, to fit in the gun barrel, which experts said was impossible as a stable (1 milliwatt) TEM-00 device.

They were trying to develop a handheld laser scanner that was under one pound, with aim-and-shoot portability. Optomechatronic miniaturization led the paradigm shift from large/heavy supermarket slot scanners of the 1970s to HHLS (handheld laser scanner) that replaced contact wands and slot scanners particularly for standalone ECR (electronic cash registers) for general merchandise retailers, department stores, boutiques etc. Swartz calculated that it was possible to build a stable 6 inch HeNe laser tube at ~1 milliwatt and stable TEM-00 (Gaussian) laser operation.

Dr. Swartz met with the laser specialists at that time at Spectra-Physics and they laughed at the idea of a half-length tube. Jerry didn’t get a meeting, much less a quote from them. His printed bar code quality control instrument at that time (Laserchek) weighed over 30 lbs., including the decode computer electronics and the 4 lb scanning head, containing an 11 inch long HeNe laser tube at its source.

Luckily, Jerry met Dale Crane, former head of manufacturing of Spectra-Physics, who had just left to form an infant company called Uniphase. He agreed with Jerry’s analysis and was willing to attempt to build the first such small laser tube. Jerry worked with Uniphase, which later became JDS Uniphase (later known worldwide for its fiber optic communication systems). Ironically, Uniphase soon became the largest supplier of HeNe lasers, succeeding Spectra-Physics.

Many inventors comment that perseverance makes the difference – (e.g., Thomas Edison, et al.). Believing in something, and not taking “no” for an answer, even against tremendous odds, is frequently the critical ingredient of successful innovation (in particular building a company).

Figure 6: Swartz’s Law comparing the inverse relationship between size of the scanners to the number of units sold.

In the late 1980s, a Symbol board member (Dr. Fred Heiman) brought back from Japan one of the first IR (infrared) laser diodes, which the engineers built into an LS 7000 in 1984. With a much smaller semiconductor that lacked a bulky power supply, there was room to spare. This was the beginning transition development of HeNe tubes to semiconductor lasers diodes. The size and weight of scanners plunged (LS 1000 @ 24 oz.; LS 7000 @ 16 oz.; LS 2000 (IR) @ 8 oz.; LS 4000 visible laser diode @ less than 6 oz. in the ‘90s). Miniaturization of the bar code scanner engine (and the lowering of the cost) was also based on the advent of the microprocessor, which then matched bar code-based distributed data entry to distributed data processing. All the analog/optoelectronic plus scan motor, digital electronics and decoder are all contained in the handheld gun. Dr. Swartz came up with a comparable auto-ID technology "rule of thumb" to Moore's Law (which compares the inverse relationship of computing power and cost) with “Swartz’s Law”, which compared the inverse/log linear relationships between the size of a scan engine to the number of scanners sold (see Figure 5).

Symbol learned to ride the development path of the semi-conductor laser (initially gain-guided and not visible), to 100 hour lifetime IR laser diodes, down the wavelength curve to red visible (650 nm index-guided lasers) at 100k hour lifetime/5V diodes that preserved contrast on the then 100 billion bar codes printed on packages, initially designed to be readable by HeNe lasers at 633 nm. Mini-tube lasers with no need (in fact, the reverse) to go down further in wavelength (vs. brightness-driven laser pointers [which are now green] and other applications) but a key path to today’s bar code HHLS. The HHLS was the first breakthrough in calculations/hard-seal product design which was manufactured by Uniphase, Hughes and Siemens. These were 5” (4”-6” at 10000 hour lifetime) TEM-00 HeNe mini-laser tubes that could simply shoot over the gun barrel and through a window in the back of the scan gun, as patented in the early ‘80s (Patent #4409470).

Scanner overview

Figure 7: Scanner block diagram and schematic diagram.

Under different ambient light conditions, the bar code scanner must work with a variety of symbols varying in such qualities as color/contrast, bar-space density, substrate characteristics, and printing process/quality. The design must contend with many inherent scanning system trade-offs, such as wavelength, optical spot size (resolution), working distance (for “aim-and-shoot” HHLS operation at a distance) from the printed symbol to the scanner, frequency band of the receiving electronics, and choice of digitizer (i.e., A/D converter). Also, the decoder must be considered an integral part of the scanning system and its design.

The general block diagram of a bar code scanner is shown in Figure 6A and a schematic diagram in Figure 6B:

For analysis purposes, the system variables associated with the block diagram are as follows (also see Figure 7):

1. Transmitter: Laser Light Source and Focusing Optics – Wavelength \(\lambda\ ;\) power \(P\ ;\) beam profile diameter \({W(Z),X}\) /waist size \(W_0\ ;\) and beam profile waist location (\(Z_0\)).
2a. Bar Code Symbol – Density, contrast (function of \(\lambda\) bar-space printing), substrate material/printing process (i.e., light scattering-diffuse/reflectance characteristics).
2b. Deflector/Scan Element – Scanning speed (scans/sec.), scan angle field of view (\(\Phi\)/range).
2c. Optoelectronic Receiver & Analog Electronics/Filters – Frequency band (\(\Delta F\)), Signal-to-Noise Ratio (SNR), ambient light immunity; working distance from scanner (\(Z\))
3 & 4. Digitizer and threshold detector – (analog to digital converter [A/D]) Sensitivity, digitization error (function of SNR, spot size, frequency band), signal depth of modulation
5. Decoder/decoding software – Tolerance to digitization error, speed, noise immunity, scans/sec.

Since it is a critical part of the system, the bar code is included in the flow & block diagrams. Bar code parameters are a given and are not subject to trade-offs, but they affect the trade-offs inherent in the characteristics of scanner design and the readability (especially working distance from the HHLS to the symbol). The scanner design is expected to compensate for any specific issues in reading problematic bar code printing/substrate.

System design: objectives and constraints

System design begins with imposing system goals and understanding what constraints affect the design. For example, consider working distance (range) in laser-based handheld bar code scanners. Since a laser is a source of coherent radiation, as compared to LED or CCD scanner illumination, laser-based scanners have a considerable noncontact working distance range, which is a major advantage to users in their ease-of-use. In this context, working range is the distance (as defined as “r” in Figure 7B) within which we can decode the symbol, measured from the nose of the HHLS to the point where the bar code blurs out (viz. becomes undecodable). However, it is impossible to make a scanner with an optimized working range for all symbol densities simultaneously. For this reason, a general purpose bar code scanner must be designed with parameter trade-offs in mind to maximize working distance range for different symbol densities. On the other hand, if the bar code scanner application can work with only one symbol density, it is possible to maximize that working range without so many trade-offs.

Light source and focusing optics

Figure 8: Focused laser beam profile.

Together with focusing optics, the laser source forms the beam, which has a certain profile in space (X, Y-transverse, and Z-longitudinally). The most valuable and simplest case to understand is the so-called “Gaussian” beam. Helium-Neon (\(\lambda\)=632.8 nm) miniature laser glass tubes (1985-1989) produce well-defined, narrow laser beams with a Gaussian intensity (I) transverse mode distribution (TEM-00). Such a focused laser beam has the profile shown in Figure 7.

The waist size (\(W_0\)) and the wavelength (\(\lambda\)) determine the angle of laser beam divergence Ɵ and beam profile size (diameter) at any distance from the waist. The major advantage of Gaussian beams is that they have a longer Depth of Focus (DOF) than beams with any other energy distribution (i.e., they remain relatively collimated over longer distances), ideal for non-contact, easy-to-use, “aim-and-shoot” bar code scanning.

Figure 9: Graph of true Gaussian spot scanning a bar edge.

In Figure 8, the solid curve shows the output function \(f (t)\) resulting when a true Gaussian spot scans a bar edge, and the dashed curve shows \(f (t)\) in the case where a real filter is inserted in the system. It can be seen that the two curves are virtually identical, in strong support of the claim that the filter transfer function \(h_s\) is nearly Gaussian.

Over the decades, laser scanner system performance continued to be challenged by increased demand for bar code scanning applications. The highest density Universal Product Code (UPC) formats and even high density Codabar, Code 39, and the highest density linear bar code 128, for example, needed to be scanned with improved throughput and reliability. In addition, these symbols became printed on a wider variety of substrates, which also affect reading/decode performance. Early on, there was also a need for convenient/accurate measuring equipment to assure the dimensional integrity of the printed symbols and original master artwork/printing plate. Note that the wavelength (\(\lambda\)) of scanner light must not deviate much from 633 nm, since the bar code colors over the decades were chosen to be scannable by exciting Helium Neon lasers (i.e., the reflected symbol signal would not have the same contrast/readability at a different wavelength). Today, semiconductor laser diode systems, LED scanners and CCD scanner illumination sources are close enough in color to allow equivalent results.

Spot Size and Analog Electronics. System errors (i.e., internal) are caused by the methods used for detecting and digitizing bars and spaces. Because of contrast uncertainties and problems with ambient illumination, it is advisable to look for changes in the intensity of the reflected light rather than in the absolute level of the light (automatic gain controls notwithstanding). Indeed, most bar code systems use edge detection or highly adaptive thresholding techniques that look, in effect, at the slope of the waveform produced when a bar code is scanned. While the ideal signal would be a set of rectangular pulses, the real signal has a rounded form because of convolution distortion (see Figure 9). As described, this refers to the moving average of the signal due to the nonzero size of the laser beam (spot) and the delays in the electronic circuits. Such rounding changes the slope and can cause significant error even in the absence of noise or printing problems.

Figure 10: Oscilloscope tracings of bar codes with a laser scanner.

Figure 9 derives from a photograph of oscilloscope traces from the scanning of actual bar codes. This is a far cry from the crisp, alternating black and white bars and spaces perceived by the human eye.

Within the scanning system, working range is also determined by the photoreceiver and analog processing electronics. The parameter of key interest is the frequency band of the electronics. To better understand this, suppose we are scanning just a single bar. Suppose also that we have four different combinations of laser beam diameters and analog electronics frequency bands and see the joint effect.

Figure 11: Spot size and analog electronics.
A. Very small spot and very wide frequency band \(\Delta F\ ;\) ideal replication… Scanned bar is least distorted (Figure 10A).
B. Big spot and very wide frequency band. Scanned bar is slightly blurred and distorted in width and shape (Figure 10B).
C. Small spot/narrow frequency band. Scanned bar may be largely blurred and distorted (Figure 10C).
D. Big spot/narrow frequency band. Scanned bar has large distortions of actual bar width (Figure 10D).
E. Small spot; wide frequency band: close to ideal replication of a spotted pattern (similar to Figure 10A). Note that the scanning spot does need to be larger than the voids and spots in the imperfect printing of a symbol. The symbol is not a black and white monolith (e.g., flexigraphic printing of cases, cartons, plastic bottles or dot matrix printing), which can produce not perfectly uniformed bars and spaces. Spot and errors in printing processes or substrates are averaged.

Note that the optical spot and analog electronics have a similar effect on the bar code image/digitization; both can blur that image independently, and combine in action on the waveform’s final result. If we assume that the frequency band of the processing electronics is infinitely wide, the “effective spot” size is the same as the optical spot size (Figure 10E) alone. If not, the combined effect of situation D (e.g., Figure 10D), strong blurring/distortion can occur, leading to a non-read or even digitizer decode error. Or, we say that the blurring of an optoelectronic bar image, is caused by a machine vision system with an effective spot size due to the combination of a root mean square of the nonzero optical spot and a finite electronic bandwidth (i.e., nonzero rise time in the amplifier). That time-space interdependence has also been known for some time in animal vision systems (Priebe et al., 2006; Tolhurst & Movshon, 1975).

\[\tag{8} W_{eff} = \sqrt{(\nu \tau)^2 + (w_z)^2 }\]

Figure 12: Depth of modulation.

Depth of Modulation. By depth of modulation, we mean the maximum change in the filter output signal \(f (t)\) due to the presence of a bar of width \(w\) in the symbol (see Figure 11). Without the effects of the electronic filter, we have for a Gaussian optical spot on a normalized basis.

\[\tag{9} DOM = \sum_{-b}^{+b}{ \frac{e^{-t^2 2\sigma_s^2}}{\overline{2 \pi}\sigma_s} dt } \equiv 2ErF \frac{w}{\sigma_s}\]

where \(b = w/2\) and \( Erf(x) = \sum_{0}^{x} \frac{e^{\frac{s^2}{2}}}{\sqrt{2 \pi}} ds\)

The filter is essential to the system design for noise reduction. In general, it can modify the spot intensity profile \(s (t)\) so much that above equation may be far from valid. However, for a particularly useful class of filters, the above equation remains very nearly valid.

Digitizer/threshold detector

In order to estimate bar widths, the filter output function \(f(t)\) is now applied to the threshold detector. This is a nonlinear circuit. The basic properties of a threshold detector will allow us later to optimize the preceding linear sections in the presence of noise. For now, we return to further considerations concerning choice of a particular type of linear filter. This choice will be guided by the need of the threshold detector for adequate depth of modulation (DOM).

Noise

Figure 13: Graphing of quantities used in considering noise performance of scanners.

Figure 12 shows a typical transition of the filter output \(f (t)\) as the spot scans a bar edge.

The bar edge is defined by the system to occur at \(t = T\ ,\) when \(f (t)\) crosses a preset value \(f_0\ .\) The noise amplitude \(\sigma_f (t)\) is reflected as an uncertainty in the time \(T\) of \(\sigma_T\ .\) \(\sigma_f\) and \(\sigma_T\) are true statistical uncertainties and should not be confused with the \(\sigma\)’s used as measures of spot size in the previous sections. By inspection, if \(\sigma_f\) is reasonably small, we have

\[\tag{10} \sigma_T \cong \left | \frac{\sigma_f}{\dot{f}(T)_f} \right |\]

where \(\dot{f}(T)\) is the slope of \(f\) at \(T\ .\) Since the value of \(T\) is the only number directly visible to the system, we propose the above equation as a measure of system performance with respect to noise.

Although the above equation may be difficult to evaluate in general, we can make good estimates of it in an important class of cases. We assume that extraneous noise sources (such as low frequency fluctuations in ambient light or electronic crosstalk) can be controlled. We are left with fundamental noise sources such as thermal and shot noise due to the signal itself, ambient light, and detector dark current of the amplifiers. The residual noise will usually be nearly “white” in character, especially over the modest bandwidths (typically below 5 MHz) generally encountered in scanners. For white noise we have a well-known result for a signal filtered by a transfer function \(H(w)\)

\[\tag{11} \sigma_f \propto \int_{-\infty}^{+\infty} \left | H(W) \right |^2 dw\]

For comparison of systems, the proportionality is all that is required. In any case, the proportional constant will depend on the particular type of noise source.

Other sources of noise: Substrate - Part of the laser light incident upon the space penetrates inside the substrate. This light undergoes a multiple scattering within the bulk volume of the substrate. Some portion of this light reemerges at some point of entry, causing a “halo” around the main spot. Such halos may extend 1 or 2 mils beyond the boundaries of the incident beam. The net effect of substrate scattering results in space shrinking and, correspondingly, in bar fattening. Different substrate materials give rise to different amounts of this scattering effect.

Decoding: Methods for detecting bars and spaces

Figure 14: Graphical representation of a signal to noise ratio.

The scanning process

After focusing by the optical train, the scanning spot is caused to move over the symbol surface by a deflection system with a transverse velocity \(v_0\) (see Figure 6A and 6B). If the spot is at the origin at \(t = 0\ ,\) and if the symbol pattern is described by a reflectance distribution \(r (x)\ ,\) then, at the instant \(t\)

\[\tag{12} l(t) = \int_{-\infty}^{+\infty} r(x')s(x' - v_0 t) dx' = r(t)*s(-t)\]

where \(l (t)\) is proportional to the total energy reflected by the symbol from the spot at the time \(t\ .\) On the right, the “\(*\)” refers to convolution, and we have written \(r\) and \(s\) as functions of \(t\) rather than \(x\) through the approximate, linearized transformation \(x \to v_0 t\ .\) For example, if \(v_0 =\) 1,000” / second then we have the relation 0.001” (1 mil) \(\to\) 1µs. We will continue to write \(s\ ,\) \(r\) and other spatial functions as functions of time to avoid confusion. Note that space and time are not independent variables in a bar code scanning and filter/machine vision system (nor in animal vision systems as well [Priebe et al., 2006; Tolhurst & Movshon, 1975]).

The above result (1) says that the reflected light signal \(l\) is given by the convolution of the symbol reflectance and the (time reflected) moving beam profile \(s\ .\) Assuming that \(s (t)\) is an even function (which is true for most applications), then

\[\tag{13} l = r*s\]

Photo detection

We assume that the fluctuating light level \(l(t)\) is converted to a corresponding electrical signal by a linear photodetector. Of course, noise also enters the system at this point from the photodetector itself (see Figure 6B), from its associated electronics, and from detected ambient light, shot and thermal noise, which may be difficult to exclude from the system.

Effects of filtering

The detected light level \(l (t)\) now enters the linear filter portion of the system. If the filter has the impulse response \(h (t)\) then its output \(f (t)\) is

\[\tag{14} f = l*h\]

But from (13)

\[\tag{15} f = l*h = (r*s)*h = r*(h*s)\]

If we define the system impulse response \(h_s\) as \(h_s = h * s\) we have

\[\tag{16} f = r*h_s \]

Note that the spot scan velocity generally varies over the field. For constant angular velocity (\(\dot{\phi}\)) rotational systems, at a distance \(R\) from the scan plane

\[\tag{17} v(x) = v_0 \bigg( l+\frac{x^2}{R^2} \bigg)\]

where \(v_0 = v(0) = 2R \phi\ ,\) and \(\phi\) is the angular velocity of the scan element.

Thus, \(h_s\) incorporates the effects of both the optical spot profile and the filter response to the symbol input in a convenient convolution form.

By taking the Fourier transform we get:

\[\tag{18} F(w) = R(w)H_s (w) \]

where \(F\ ,\) \(R\ ,\) and \(H_s\) are the transforms of \(f\ ,\) \(r\ ,\) and \(h_s\) respectively. Thus, we can see that \(H_s (w)\) can be considered the system transfer function, which takes into account the effects of both the optical spot and the filter, viz.

\[\tag{19} H(s) = HS \]

where \(H\) and \(S\) are the transforms of \(h\) and \(s\) respectively. The filter amplifier also adds noise at this point.

Decoding theory and bar codes: diagonal distance

Figure 15: Topology of the diagonal distance.

The cornerstone of error correction techniques is the definition of a distance between a pair of messages. The most common such measure, the Hamming distance, equals the number of places two strings differ (see Figure 14). In decoding, if only a subset of all possible code words has been chosen, then a corrupted message is assumed to represent the nearest correct code word.

Instead of having to go to the binary representation each time, we can introduce a different way of calculating the distance between the strings. Such a step is advisable for the primary reason that most scanners detect the change of edge reflectance of the substrate rather than the existence of bars or spaces. Therefore, a single physical event will cause an edge shift. In fact, the scanner does not see the underlying bar-space module structure.

Summary

There are few technologies that have had so much impact on the lives of consumers worldwide as bar codes have. The technology is inexpensive and easily connects physical objects to information systems. Just like a human can be identified by a name, bar codes give a name to any object and allow automatic capture of that name through various scanning devices and connect them to a computer system where decisions can be made regarding the object (e.g., price, manufacturer, date of manufacture, distribution chain and inventory levels, tracking in the pipeline, retailers availability, price and location on a cell phone, etc.). Bar coding continues to be practical, economical and highly efficient in data capture and read rate accuracy. With the advent of RFID technology a few years ago, its obituary was written by a number of experts. However, predictions of its demise were premature. In the late 1990s, the editor of Wired magazine was asked about the two most important technologies of the last few decades that had the most impact on the lives of consumers; he named the Internet and bar codes. It looks like bar codes will continue to be around for a long time to come due to inherent simplicity, accuracy, low cost and efficiency. In this review, we have provided the concepts of symbology and the challenges in analyzing and designing bar code scanning systems.

Acknowledgments: Most of the information in this article has been derived from Symbol Technologies’ Monograph 4 authored by Boris Metlitsky and Monograph 5 coauthored by Theo Pavlidis, Jerome Swartz, and Ynjiun Wang of Symbol Technologies (now part of Motorola), and from an article that appeared in SPIE volume 299, Advances in Laser Scanning Technology, authored by Eric Barkan and Jerome Swartz. The senior author of this article wishes to acknowledge contributions of Dr. T. Pavlidis, Dr. Y. Wang, Dr. B. Metlitsky and especially Eric Barkan, Symbol Technologies consultant to the core references. Thanks also to the editors, Dr. Joseph Katz and Aileen Chou as well as Eric Barkan and Ed Barkan on the optics/signal processing analysis/review and Dr. Sharma on the bar code symbology-end.

References

  1. D.C. Allais, Bar Code Symbology, Intermec, Lynnwood, WA, 1985.
  2. E. Barkan and D. Sklar, “The Effects of Substrate Scattering On Bar Code Scanning Signals,” Proc. SPIE 26th Int’l. Tech. Symp. And Instructional Display, San Diego, Aug. 1982, paper no. 362-34.
  3. E. Barkan and J. Swartz, “Depth of Modulation and spot size selection in Bar Code Laser Scanners”, Proceedings of SPIE – The International Society of Optical Engineering, Vol. 299, 1981, pp. 82-97.
  4. E. Barkan and J. Swartz, “System Design Considerations in Bar Code Laser Scanning,” Optical Engineering, Vol. 23, July/Aug. 1984, pp. 413-420.
  5. W. Feller, An Introduction to Probability Theory and its Applications, Vol. I, 2nd ed., J. Wiley and Sons, New York, 1957.
  6. C.K. Harmon and R. Adams, Reading Between the Lines, Helmers Publishing, Peterborough, N.H., 1989.
  7. R. Hill, A First Course in Coding Theory, Clarendon Press, Oxford, 1986.
  8. T.D. Howell, “Statistical Properties of Selected Recording Codes,” IBM J. Research and Development, Vol.33, Jan. 1989, pp. 60-73.
  9. CD ROM, The New Papyrus, S. Lambert and S. Ropiequet, eds., Microsoft Press, Redmond, WA, 1986.
  10. B. Metlitsky, “Laser Bar Code Scanning: A System Design and Analysis model”, Symbol Technologies, 1990. Monograph.
  11. R.C. Palmer, The Bar Code Book, Helmers Publishing, Peterborough, N.H., 1989.
  12. T. Pavlidis, J. Swartz and Y. Wang, “Fundamentals of Bar Code Information Theory” computer, Vol.23, issue 4, pp. 74-86.
  13. N.J. Priebe, S.G. Lisberger and J.A. Movshon (2006). Tuning for spatiotemporal frequency and speed in directionally selective neurons of macaque striate cortex. Journal of Neuroscience 26, 2941-2950.
  14. D. Savir and G. Laurer, “The Characteristics and Decodability of the Universal Product Code,” IBM Systems J., Vol. 14, 1975, pp. 16-33.
  15. K.A. Schouhamer Immink, “Coding Methods for High Density Optical Recording,” Philips J. Research, Vol.41, 1986, pp. 410-430.
  16. P.H. Siegel, “Application of a Peak Detecting Channel Model,” IEEE Trans. Magnetics, Vol. MAG-18, No. 6, Nov. 1982, pp. 1, 250-1,252.
  17. D. J. Tolhurst and J. A. Movshon (1975). Spatial and temporal contrast sensitivity of striate cortical neurones. Nature 257, 674-675.
  18. W.J. van Gils, “Two-Dimensional Dot Codes for Product Identification,” IEEE Trans. Information Theory, IT-33, Sept.1987, pp.
  19. Y.P. Wang, “Spatial Information and Coding Theory,” PhD Thesis, SUNY, Stony Brook, Dec. 1989.
  20. E. Zehavi and J.K. Wolf, “On run length Codes,” IEEE Trans. Information Theory, It-34, Jan. 1988, pp. 45-54.
  21. Keyence, Bar Code Reader Technical Guide, 2000.

Further reading

In this article, we use only elementary concepts of coding theory, which you can be found in any text on the subject. The following book by Hill is a particularly readable source.

  • R. Hill, A First Course in Coding Theory, Clarendon Press, Oxford, 1986.

External links

See also

Information theory, Pattern recognition

Personal tools
Namespaces

Variants
Actions
Navigation
Focal areas
Activity
Tools