Like most inventions, the first generation of barcodes - a linear one-dimensional bar code - appeared when there was an urgent need to automate a fairly simple, but routine and painstaking job of sorting and recording goods in the process of logistics and sales: what goes to the warehouse, what leaves the warehouse what is shipped to customers and in what assortment. When all these processes are inevitably accompanied by manual filling of the necessary documents, finding the right shelves in the warehouse, generating reporting on logistics, it takes a considerable amount of time for the employee. In addition, errors when manually filling out documents are inevitable. The growth in turnover required a radical solution that would quickly and without errors solve the problems of control and accounting.
The idea of coding goods appeared simultaneously with the idea of organizing the work “ the perfect supermarket ”, developed by Harles Business School student Wallace Flint in the early 1930s. The proposed technical solution suggested that the buyer independently creates a list of purchases in the warehouse, making punctures in a special punch card of the buyer. At the checkout, this punch card was supposed to be read by a special device, the goods were delivered using a special conveyor, and the service process was quick for both the buyer and the seller. The main problem was that at that time there were practically no technologies and equipment for servicing such processes: the computer that would be required to organize the reading and processing of information of this class would be too cumbersome and expensive.
The next approach to coding the product range was taken in 1948, when graduate student enthusiasts from the Drexel Institute of Technology (USA) began developing a technology for collecting analytical information about purchases directly at the cash desks in supermarkets based on labeling of goods. Then a group of researchers created a “hybrid” technology of optical soundtrack and Morse code. In the classical technology of an optical sound track, a coating with an uneven density is applied along the edge of the film. This unevenness leads to the fact that the intensity of the beam of the projector passing through it also changes. These fluctuations in brightness are converted to sound.
Researchers transformed points and dashes of Morse code into uneven bands, as if “stretching” them down. The result is a sequence of wide vertical lines (dashes) and narrow lines (dots), separated by spaces. Reading the combinations of dark lines and light spaces and interpreting the reflected rays turned out to be a workable idea, which was subsequently obtained patent .
For the first time in practice, the barcode was used by a graduate of the Massachusetts Institute of Technology when he started working at a railway station and was involved in simple but routine sorting of wagons, which also required constant observance of the accuracy of operations and avoiding errors in entering data into registration papers.For each car, it is necessary to find out its number, check with the accompanying documents, clarify the route, determine the place in the train, and so on. This procedure was quite lengthy, time-consuming and required stopping the composition.
By the middle of the 20th century, technology had already stepped forward, and it was possible to automatically read out sufficiently large numbers of cars using photocells. But reading the number in the form of Arabic numbers is a fairly simple task for a person who knows how the numbers look and what they mean. For a machine, numbers are a sequence of lines located at a certain angle. The absence of one or more lines or inaccurate application makes the task of digit recognition (in the absence of OCR technology) poorly realizable. Therefore, it was proposed to simplify machine recognition to record numbers not only with ordinary Arabic “human-readable” numbers, but also with a code in the form of wide stripes of blue and red.
This code was placed directly on board the car and made it large enough so that the photocell could snatch out and correctly recognize the bar code illuminated by the spotlight on the passing scanner of the car. Tests have confirmed the effectiveness of the recognition system at speeds up to 100 km/h. It was already a perfectly working technology that completely changed a single process in an entire industry.
Later, with the improvement of technology, the projector was replaced by a laser, which not only consumed less energy than a powerful incandescent lamp, but also made it possible to make the applied barcodes much smaller in size, and the scanning unit itself was much more compact until the creation of hand-held and desktop scanners. The development of laser scanning technologies and compactization has become a step towards the widespread use of barcodes as a universal means of marking goods not only in railway transport.
In the late 60s, the United States began the development of a universal numbering system for goods as a means of identification. The bar coding system, which began to be used in trade, was developed in 1972 and was called UPC - Universal Product Code. The barcodes of this system began to be assigned to all types of goods produced and registered in the USA and Canada. The organization of the same name began active propaganda and the introduction of the use of barcodes in industry and commerce. The first historical retail UPC barcode reading took place at an American supermarket in 1974.
Since 1977, in Western Europe, a similar American system called the European Article Numbering (EAN) has been used to identify consumer goods. Today it is this association that is engaged in the distribution of barcodes for manufacturers of goods. To avoid duplication of numbers, barcodes for goods are issued centrally by the international association, which includes 98 organizations from 100 countries. A manufacturer can get a barcode for his product by registering with this association.
The barcodes of the UPC and EAN families operate with a fairly small alphabet that allows you to encode a fairly limited amount of information. The UPC used in the USA consists of 12 characters, the EAN of 13 digits and is a slightly advanced modification of the UPC code. Coding characters are vertical stripes of varying widths and spaces between them. In standard linear codes, information about the country of origin of the goods, the manufacturing organization, and the product code itself is encrypted. To verify the correctness of the code, a check digit and a special sign are placed at the end, indicating that the goods are manufactured under license.
Now let's look at the code in terms of structure and coding principles. Here we will analyze in detail only one - standardized - UPC-A type barcode to show: coding principles that are applied much more complicated than they seem at first glance. This complexity ensures error-free recognition by minimizing the risk of misreading.
A UPC-A type barcode is divided into 2 equal parts and is displayed as dark (strokes) and light (spaces) stripes that encode the 12-digit UPC-A number. Each digit is a unique set of 2 strokes and 2 spaces of variable width in 1, 2, 3 or 4 modules (in this case, the minimum discrete bandwidth). At the same time, the total width of the coding bands for each digit remains unchanged - 7 modules. Thus, the content of the product code UPC-A is encoded in 84 units.
Many wondered why on different barcodes the same numbers can be in several different ways (some even built conspiracy theories on this subject). The fact is that the barcode coding algorithm is not entirely linear. In the right and left parts of the code, the numbers are encoded differently: the alternation of strokes and spaces in the numbers occurs in three sets of sequences (A, B and C). In sequence A, there are always an odd number of dark modules, in sets B and C it is even. In this case, set B - is an inverse of set a (strokes are replaced by spaces and vice versa), and set C is a mirror image of set B. Signs of a character in numerical sets A and B always begin on the left with a light module and end on the right with a dark module, and in a numerical set C start on the left with a dark module and end on the right with a light module. On the left side, when encoding numbers, sets A or B are used, depending on the position of the numbers in the code, the right side is encoded by set C. The encoding algorithms are described in detail in the standards. For example, in this .
In addition to the bands encoding information, the graphic code contains restrictive patterns of the beginning of the code, completion of the code and the middle. The end patterns have the form bar-space-bar-stroke, and the central one - space-bar-space-bar-stroke. The presence of restrictive patterns, as well as a “quiet zone” around the barcode, allows the reader to more accurately determine the boundaries of the barcode, thereby increasing the speed and accuracy of recognition.
Barcode formats are constantly being improved and changed. Today, in addition to the standard Universal Product Code and European Article Numbering accepted in international trade, there are more than 300 standards for bar coding.
Since 2005, an international standard has been adopted, which uses three main types of coding of product information:
- EAN-8 (abbreviated) - 8 digits encoded.
- EAN-13 (full) - 13 digits are encoded (12 significant + 1 checksum).
- EAN-128 - allows you to encode any number of letters and numbers combined into regulated groups.
Unlike EAN-8 and EAN-13, the EAN-128 (GS1-128) code is used by manufacturers, carriers and trading companies to exchange data on the goods transported. This longer code may contain extended information, such as waybill numbers, destination indexes, volumes of goods transported, product codes and serial numbers of products, expiration dates, etc.
The main advantage of a barcode is its simplicity, functionality and noise immunity. The main drawback is the relatively small amount of information that can be encoded with it.
With the development of information processing technologies, one-dimensional (linear) barcodes have been replaced by two-dimensional ones. If in linear (one-dimensional) codes strokes are used, then in two-dimensional (and multidimensional) other figures can serve as coding elements, therefore, in order to differentiate one from another, here we will call multidimensional codes as barcodes. Research and development of two-dimensional codes began in many countries around the world in the 1980s, since the amount of information encoded in linear codes was clearly insufficient. Their appearance became a natural evolution of coding systems, and at the same time recognition technologies, software and hardware capabilities of recognition systems.
In addition, there was a need to mark literally everything with codes: not only, say, units of assemblies, but also individual parts. Therefore, there was a need to miniaturize the code and increase the density of the encoded information per unit area.
In a two-dimensional code, as the name implies, encoding occurs not in one direction, but in two. Indeed, if you place several one-dimensional codes in the form of alternating fragments, you get the simplest two-dimensional code of the Stacked Linear type (composite linear). If we “pack” the modules into a square, we get a matrix barcode (Matrix).
An example of a composite linear barcode is PDF417, which appeared in 1991 and was patented in 1993. PDF417 code consists of strings formed by “words” - a set of alternating strokes and spaces (4 dashes, 4 spaces - the first number from the code name). The total length of each word is 17 modules (the second number in the code name).
In addition to the actual meaningful words, each line consists of a start pattern (leftmost set, keywords (indicators - they occupy the extreme positions on the line) necessary for error correction, and a stop pattern (However, there is also the so-called “truncated PDF417 ”(Truncated), where the right-line indicator is turned off and the stop pattern is reduced to one line. Thus, truncated PDF417 take up less space, but they are more susceptible to incorrect reading. This version of PDF417 is used only where the risk of damage to the code image is minimal). Since all words have the same length, the columns placed one under the other form columns. In the PDF417 code, both the number of lines and the number of columns can vary: the code can contain from 3 to 90 lines, and have a width of 3 to 30 columns inclusive, not counting columns with words indicators. A detailed article about PDF417 encoding recently appeared on Habr here , and about the possibility of its“ manual ”decoding - here .
The peculiarity of the PDF417 code is the ability to encode information in text mode, numerical mode and data mode (byte mode).
Since the amount of encoded information has increased in PDF417, error correction mechanisms have been used to correctly read and decode it in the code. This is achieved by adding keywords with which the machine can recover data that has been lost or read with an error. The ability to correct errors is a key advantage of PDF417: if recognized, the recognition device will not be afraid of possible distortions.
Like its predecessor, a linear barcode, PDF417 was created at a time when mobile phones were a little smaller than a suitcase, and perhaps they didn’t even think about the built-in cameras. Therefore, its use implied the presence of specialized scanners designed to read such code. This explains the complexity of this barcode and the increased print resolution requirements.
PDF417 barcodes are widely used for marking medical products, are applied to documents in electronic document management systems, and are used on tax return and travel forms.
Code in the matrix
The matrix structure allows you to encode information both vertically and horizontally, due to which the amount of encoded data is significantly increased. An important advantage of all matrix codes is the ability to encode a large amount of information over a very small area.
Data Matrix Code
The Data Matrix code was invented by International Data Matrix in the mid-1980s for the Space Shuttle program, which required the labeling of a large number of parts. The Data Matrix was developed before PDF417, that is, PDF417 could not precede the Data Matrix, as indicated in some sources. An important advantage of the code is its compactness and ease of application. Data Matrix is currently being described by the relevant ISO standards.
DataMatrix is a two-dimensional barcode that can store up to 3116 digits and up to 2335 letters. Information in the Data Matrix barcode is encoded in black and white squares (modules) with a minimum linear module size of 0.255 mm.
The finding pattern in the form of the letter “L” is two solid lines on the outside of the Data Matrix code. This pattern allows the barcode scanner to set the image in the correct orientation and read the information in the correct order.
The second important pattern necessary for the machine to understand the code is the clocking pattern (clock track). It is necessary to inform the reading system about the number of modules in the matrix and to correctly recognize the grid on which the modules are located.
A quiet zone is an area that separates the border of a barcode from the background and other images. For Data Matrix, the width of the “silence zone” is equal to the linear size of the module used. Small dimensions for the silence zone minimize the surface area for applying Data Matrix.
The specificity of the Data Matrix allows you to read it both in direct and reflected light (that is, when using an inverted image in which light modules become dark).
Another advantage of the Data Matrix is that square modules can be replaced with round ones. This further expands the possibilities of using various application technologies, for example, in the form of embossing or impact engraving. However, the same technology for replacing a square module with a round one was adopted by other types of codes, for example, a QR code.
The standardized Data Matrix code is today regarded as a key link in the identification and labeling of pharmaceutical products and medical devices. Starting July 1, 2020, Data Matrix labeling will become mandatory for all drugs in circulation in Russia.
The detailed process for creating the Data Matrix is described here .
The barcode type Aztec appeared in 1995, as they say, as a result of combining the best practices of developing barcodes of previous generations. The look and structure of Aztec code is designed in such a way that it is equally convenient for drawing and reading. Symbols are generally square on a square grid with a square central “sight” of concentric dark and light squares of the “apple” type of the target (the term “bull’s eye” is used in English descriptions).
The smallest Aztec Code character has an area of 15 x 15 modules, and the largest is 151 x 151. The smallest Aztec Code character encodes 13 numeric or 12 letter characters, while the largest Aztec Code character encodes 3832 numeric or 3067 alphanumeric characters.
In this material, we do not set ourselves the task of analyzing each code in detail separately, especially since Aztec is perfectly written in full detail on Habr here .
We got to the most, perhaps, the most common codes that we meet at every step.
QR code is another kind of matrix code. Its name comes from the English “Quick Response” - “Quick Response”. It was created by Denso-Wave in 1994 in Japan for the domestic market (the difference between a QR code and other two-dimensional barcodes is that this code allows you to encode the characters of Japanese (or rather, coming from China to Japan) kanji letters. Also in the QR code redundant information may be embedded that allows you to encode certain actions for a smartphone program or scanner to read.
The principles of encoding a QR code are described in sufficient detail and can be easily found. The algorithm of how to read a barcode not with a scanner, but with your eyes, can be read, for example, here .
In this QR code, you can easily encode the address of the web page that will open when you hover a mobile phone on it:
And this QR code contains not only the address of the web page, but also the phone number, email address, postal address. To create a contact card, just point your mobile phone to the QR code, and the information will be automatically recognized, and the data will be entered into the system.
Moreover, even the presence of the logo of our company, covering about 10% of the code, does not interfere with correctly recognizing all encoded information.
Below is an example of the largest-dimensional QR code that can encode up to 1852 characters.
These barcodes allow you to encode digital and text data with approximately the same efficiency. According to the comparison provided on the RIT service site specializing in barcode processing, a QR code allows you to encode large amounts of digital data in a smaller area with the same module size compared to Aztec and Data Matrix, encode large amounts of digital data. The Data Matrix code is inferior to the QR code when encoding more than 88 digits, Aztec is inferior to the QR code when encoding more than 170 digits. But in terms of text encoding efficiency, the QR code is significantly inferior to Aztec, and the Data Matrix is superior only with a text volume of more than 298 characters. However, when encoding text typed in capital (capital) letters of efficiency, the QR code and Aztec are close, and the Data Matrix is inferior to the QR code already when encoding 88 letters.
What brings all of these codes together?
It is important for a machine to understand that in front of it is a code where its “beginning” and “end” are located. For this, “zones of silence”, special border patterns and “sights” are used. In addition, the machine needs to understand in what format the data is written, that is, how to decode - in the form of numbers, alphanumeric text, or in the data format. The machine should also be able to correct errors so that the accidental loss of several pixels of a barcode image does not lead to its complete unreadability. Errors in DataMatrix, Aztec, QR codes are corrected using the codes Reed-Solomon , which correct reading errors and allowing to recognize data even in highly “damaged” codes (up to 30% of the surface).
Why do we need barcodes at all?
Barcodes have become so commonplace that we don’t even think about why they are needed and what function they perform. And in fact, the answer is not as obvious as it seems. It is important to understand that barcode refers to automation, that is, it provides communication between the machine and the person. The barcode itself is not a working tool, but is of value only if there is a high-quality system of barcode recognition and interpretation of the results.
The introduction of a barcode recognition system in business processes allows you to speed up the search, insertion and extraction of information from databases, improve logistics control, make interaction with customers more comfortable.
The introduction of barcodes in medical records and the introduction of recognition systems in medical institutions increases the speed of patient care and makes the registry work
more systematic and orderly.
The implemented barcodes on tickets accelerate the passage through checkpoints and turnstiles, making contactless ticket verification a more convenient solution than physical verification by the controller. In this case, the barcode serves as an element of protection against counterfeiting, just like the implemented barcodes on secure printing products and strict reporting documents.
The process of making payments has been greatly simplified with the introduction of barcodes on utility bills, fines, taxes and other social payments. All details are encrypted and for making a payment in a banking application it is enough to point a mobile phone to the barcode, and the application with the barcode recognition module will independently enter all the details of the recipient in the required fields.
What is the task and problems of barcode recognition?
Each barcode must be recognized. If it cannot be recognized, then from a barcode it turns into an unrecognizable artistic ornament.
Three main tasks that need to be solved when recognizing a barcode are its detection, localization, detection of the bit matrix and recognition.Each problem can be prevented by various problems that arise due to damage to the barcode carrier itself, or to deficiencies in software and hardware solutions.
The detection and localization of the barcode is hindered by various projective and nonlinear distortions, poor lighting, glare, and application errors. The level of distortion depends on how the barcode is created, and on the device and software with which this barcode is read. The original message is encoded with a bit matrix (of ones and zeros) according to special rules (each symbolology has its own), which is somehow applied to the medium. When applied, the unit usually corresponds to a dark module, and zero to light. The problem is that it is not enough just to localize the boundaries of the code on the media, you need to restore the original bit matrix from the image. And this is accompanied by a number of difficulties, which leads to the presence of a special stage in reading codes.
As mentioned above, each barcode has its own degree of error correction. Even a heavily worn barcode with a high degree of error correction can be correctly read by the system. But at the same time, the system itself, when scanning barcodes, must distinguish a grain of sand adhering to the barcode from an informationally significant element. In the same way, when reading, the system must accurately determine the boundaries of the barcode, eliminate possible distortions caused by slopes, distortions, and optical deformation. This is especially true for two-dimensional ones that carry a significant amount of information.
An important quality of the barcode recognition system is the ability to quickly and accurately recognize them from different angles, in poor lighting, vibration, shaking, with a partially covered field, in the presence of glare and spots on surfaces.
And what's next?
Where there are two dimensions, there are 3 and 4. In mid-2006, the Japanese company “ Content Idea of ASIA ” proudly announced that that they invented the first ever 3D code. In the PM code (from “paper memory” - “paper memory”) as the third dimension color has been added to the two-dimensional QR code. Adding a color component, according to the statement of the inventor Tatsui Onoda, if it can be encrypted in a black and white two-dimensional QR code 3 KB of information, then in 3D - up to 720 (that is, 240 times more). Instead of linking to an image, using the topology of the 3D color code, you can encrypt the entire image, as well as small video and audio fragments. The technology has received patents in Japan and Europe. Apparently, the project developed until 2013, and so far has been frozen or closed. The site of the Japanese inventor company has not been updated since 2013, and it is no longer possible to download the application in official application stores. (If you wish, you can download it from some mirrors on the network and see how it works on the samples posted on the developer's site).
In 2010, Microsoft went a step further - announced the creation of a new concept of high-density color barcodes (High Capacity Color Barcode (HCCB)), where the code was already presented in the form of the same QR-like matrix, however, the elements of the code were not black square modules, but colored (4 or 8 colors) triangles, each of which occupied ⅔ cells.
The HCCB project also existed until 2013: then Microsoft announced that the project will not be supported and was closed in 2015. Recently, information that Apple is developing new types of codes that will be available in future versions of the OS. We are talking about round barcodes, where the information is encoded in the form of 4 color “drops” placed in the center and around the perimeter of the circle.
Of course, studies of the possibility of creating and using color barcodes are still ongoing, but they are not yet widely used. The reason here is that with an increase in “measurements” of the encoding and an increase in the amount of encoded information, the number of errors that need to be fixed also grows. The color code should contain a large redundancy necessary to correct errors that are caused not only by geometric, but also by chromatic distortions that occur during the display of a bar code on a medium (screen, paper or any other surface) and during reading. The higher the expected error rate, the greater redundancy should be in the code. And as a result, the code density decreases, which makes the process of its creation, reading and decoding economically inexpedient.
It is logical to assume that following codes with three parameters, four-dimensional codes will follow, dynamically changing in time. From the point of view of theory, these are very interesting problems that raise the question of the need for the simultaneous development of software that allows one to recognize such objects. And here we come to the concept of 4D recognition, which we will talk about later.
As an afterword
In 2013, a fun program for mobile phones, Barcode KANOJO, appeared, which decoded (or pretended to decode) the barcode in an unusual way. Instead of the embedded character set, a virtual girlfriend (kanojo) appeared on the mobile screen - an anime character - corresponding to the scanned code. It was possible to be friends with her, to gain trust (and love ???). The project did not last long enough, characters were not generated, and most likely, they were simply selected from a certain set of data created in advance from an external data server, which is now unavailable.