Technical Field

The present invention relates to detecting a bar code in image data. More specifically, the present invention relates to a method of detecting a one- or two-dimensional bar code in image data of the bar code, an apparatus configured to detect a bar code, and corresponding computer programs and computer program products.

Background

Nowadays, one-dimensional and two-dimensional bar codes can be found on consumer products, electronic and non- electronic devices, machines, vehicles, packed food, tobacco products (e.g. cigarette packages), beverage cans, packages and bottles, and also on documents, such as tickets, papers, currency bills etc. Whereas the one-dimensional bar code is classically limited to encoding information only in one dimension, a two-dimensional bar code comprises at least first and second type elements arranged in an ordered grid, and consequently allows for substantially increasing the amount of data that can be encoded.

Figures 1A and IB show schematic views of conventional bar codes. In figure 1A a common one-dimensional bar code is shown that comprises an arrangement of, for example, black lines V and white lines 2' . Information is encoded in a one- dimensional bar code by concatenating pre-defined groups of black and white lines 1', 2' of varying thickness. These groups are usually associated to a specific character or meaning by some kind of industry standard. Figure IB shows a common two-dimensional bar code that encodes information by means of arranging, in general terms, first type elements 1" and second type elements 2 " , such as rectangles, dots, triangles and the like, along two dimensions in some sort of ordered grid. The example of Figure IB follows an implementation according to the GS1 (Trademark) DataMatrix ECC 200 standard (GS1 being an international association providing standards for two- dimensional barcodes) . This standard, for example, employs a so-called "L finder pattern" 4 (also called L-shape solid line, L-line, solid line, etc.) and a so-called "clock track" 3 (also called clock line, L-shape clock line etc.) surrounding the data 5 that carries the actual payload data of the bar code .

In both cases of one -dimensional and two-dimensional bar codes, at least two distinguishable types of elements/lines are used. For example, a white-printed square as a first type element may represent the information 0, whereas a black- printed square as a second type element represents the information 1. In general, however, the barcodes can be well implemented also by using color and/or fluorescent dyes or inks, thermo printing on heat- sensitive paper, mechanical means, such as milling, embossing, grinding, or physical/chemical means, such as laser etching, acid etching, etc. Any type of implementation is possible as long as the elements can be distinguished into their respective type in, for example, image data that has been obtained from the two- dimensional bar code being normally attached to some kind of object (good) . For example, a digital camera can obtain digital image data of the bar code that is printed on a paper document or laser- etched on a metal can.

Once the barcode is applied (or printed) to an object, the encoded information can then be later retrieved by means of barcode reading devices . Such devices usually first obtain said image data that was acquired using, for example, a digital camera. Other acquisition support may be provided by means of illumination devices, such as LEDs, lasers and other light sources . The barcode reading devices may then employ processing resources, e.g. in the form of a microprocessor

(CPU) and an associated memory, for processing the obtained image data. Usually, such processing involves isolating

(identifying) the barcode in the image data and decoding the payload data. The decoded data can then be further processed, displayed, or transmitted to other entities.

One of the parameters which influence the quality of a printed one- or two-dimensional bar code is modulation. Modulation is a measure of the consistency of reflectance of the elements of a first and second type, respectively. A high modulation is needed to efficiently and correctly locate, sample, and decode a bar code during the already mentioned image processing for decoding and/or authenticating. In case of a low modulation, some of the element of a first type may be erroneously classified as element of second type and vice versa. A possible cause for low modulation is the irregular reflectance of the substrate on which the bar code is printed .

An example of a two-dimensional bar code printed on a packaged good (i.e. product or object) with logo is shown in Figure 2A showing an object 21 on which a logo 22 is printed. Furthermore, a two-dimensional bar code 20 is attached to object that may - at least in part - overlap logo 22.

Figure 2B shows an enlarged view of a two-dimensional bar code 20 printed on top of the logo 22 as a schematic- representation of correspondingly obtained image data. The different spacing of the diagonal lines in Figure 2B represents varying properties between the logo 22 and the substrate of the object (e.g. reflectance, fluorescence, or absorbance) . For example, the logo 22 may have a high reflectance whereas the object surface has a low reflectance (modulation can be related to reflectance) .

Due to these varying properties the two-dimensional bar code 20 may have a poor modulation. Especially, the first type elements (i.e. the black squares in this example) have very different reflectance because some elements are printed on top of the logo 22 while others are printed directly on the object 21. Especially, the first type elements 201 have a different reflectance than the first type elements 202, although being of the same type. Thus the bar code 20 may show low modulation. If the degree of modulation reaches a certain level, decoding of the bar code may fail.

Conventional techniques currently applied determine a threshold for intensities to distinguish between the different elements of the bar code. If the intensity at a certain point in the image data is below the threshold, the point yields a first type element. If the intensity at a certain point in the image data is above the threshold, the point yields a second type element.

A problem of the threshold based techniques is that it may be difficult to determine a threshold that can be used globally for the complete area of bar code. Due to the fact that the modulation can vary, a threshold based technique may not be reliable and can lead to decoding errors. For example, the first type elements 202 shown in Figure 2B could be erroneously determined as second type elements.

Conventional attempts to solve the above modulation problem try to define subareas of the bar ^' code and determine a unique threshold for each subarea . However, this leads to a contradiction. The smaller the subareas are, the more reliable the determined threshold is. On the other hand, if the subareas are too small, the determined threshold becomes independent of surrounding subareas and the modulation problem remains unsolved. Further, such an approach may require a large amount of processing resources which may not be desirable in view of the required decoding speed in modern production and packaging lines and/or in view of the involved power resources (e.g. in a battery-powered handheld reading device) .

There is therefore a need for improvements in detecting a bar code in image data. More specifically, it is desirable to have image processing at hand which is fast and reliable in the presence of low modulation in the image data.

Summary

The above-mentioned objects and problems are solved by the subject-matter of the independent claims. Further preferred embodiments are defined in the dependent claims.

According to one aspect of the present invention, a method of detecting a two-dimensional bar code in image data of the bar code is provided. The bar code comprises first and second type elements arranged in an ordered grid. The method comprising the steps of calculating intermediate image data indicative of a divergence of a gradient of pixel values of said image data; identifying at least one element of said first and second type elements based on an extremum of the intermediate image data; and determining the location of the two-dimensional bar code in said image data based on the identified element.

According to another aspect of the present invention, a barcode reading device is provided comprising processing resources configured to identify a one- or two-dimensional barcode in input image data, and configured to calculate intermediate image data indicative of a divergence of a gradient of pixel values of said input image data, identify at least one element of said first and second type elements based on an extremum of the intermediate image data, and to determine the location of the bar code in said image data based on the identified element.

According to further aspects, a related computer program, and a related computer program product are provided.

Brief Description of the Drawings

Embodiments of the present invention, which are presented for better understanding the inventive concepts and which are not the same as limiting the invention, will now be described with reference to the figures in which:

Figures 1A and IB show schematic views of exemplary- conventional bar codes;

Figure 2A shows a two-dimensional bar code printed on a logo;

Figure 2B shows a schematical view of image data as obtained from a two-dimensional bar code with poor modulation;

Figure 3A shows a block diagram of a method embodiment for decoding a two-dimensional bar code;

Figure 3B shows a block diagram of a method embodiment for detecting a two- dimensional bar code in image data;

Figure 4A shows a schematical view of image data of two-dimensional bar code with poor modulation; Figure 4B shows a schematical view of image data of a gradient field of the image data according to an embodiment of the present invention; and

Figures 5A to 5C show schematic views of apparatus and device embodiments of the present invention.

Detailed Description

Generally, image processing for decoding a bar code includes various sub-processes. Such image processing usually starts from a raw image (image data) of the bar code, possibly attached to an item or document. The image is obtained as said image data from the bar code by means of, for example, conventional digital cameras, video cameras, CCD cameras, scanners, and the like.

A possible image processing is explained for the example of the two-dimensional bar code (data matrix) shown in Figure IB. There are several existing methods for locating, sampling, and decoding data matrix symbols. For example the reference decode algorithm for data matrix (ISO/IEC 16022:2006, Information technology - Automatic identification and data capture techniques - Data matrix bar code symbology specification) is widely used. One example is one according to the already mentioned GS1 (Trademark) DataMatrix ECC 200 standard (GS1 being an international association providing standards for two-dimensional barcodes) . In the example of Figure IB, the clock track are the upper most and right most elements of alternating type and the L finder pattern consists of the elements at respective opposite locations (bottom and left) . The L finder pattern can be used to determine the size, orientation and distortion of the symbol. The clock track can be used to define the cell structure of the two-dimensional bar code.

In order to decode the two-dimensional bar code correctly, quality of the printed two-dimensional bar code should be sufficient. For example, the ISO/IEC 15415:2011 standard (Information technology - Automatic identification and data capture techniques - Bar code symbol print quality test specification - Two-dimensional symbols) defines the methodology to test the print quality of printed data matrix symbols .

Fig. 3A shows a block diagram of a method for decoding a two- dimensional bar code. The first step 312 ("DETECTING") is detecting image data 311 ("IMAGE DATA") obtained from a digital camera or the like. This step processes image data 311 which includes a two-dimensional bar code and is responsible for the detection of the pixels which are part of the two-dimensional bar code. The output of this step is a binary image 313 ("BINARY IMAGE") representing the two classes (i.e. background and data matrix symbol) . Due to the non-uniformity of reflectance of the dark and light modules (elements) , a global threshold may not be suitable to detect the data matrix symbol. The performance of the subsequent components is strongly influenced by the accuracy of the binary image, i.e. clock adjustment and sampling.

The next step 314 ("LOCALIZATION") is the localization of the two-dimensional bar code. The goal of this step is to estimate the location of the two-dimensional bar code by processing the binary image 313. More specifically, the L boundary and the clock track are localized. The next step 316 ("SAMPLING") is the sampling to obtain symbol characters 317 ("SYMBOLS") . This step can comprise plotting a grid, constructed by making use of the L boundary and the clock track, on the two-dimensional bar code. The intersections of the lines forming the grid should coincide with the centres of the modules. If the estimated centre of the grid is black then the sample is one otherwise zero.

Step 318 ("DECODING") is the decoding. This step decodes the symbol characters 317 by applying for example the Reed- Solomon error correction followed by decoding the symbol characters into data characters 319 ("DATA") .

Embodiments of the present invention can be employed in conjunction with the detection step 312 by enhancing the decoding performance of a one- or two-dimensional bar code which suffers from low modulation. Instead of estimating a global threshold to detect the data matrix, embodiments of the present invention employ the use of differential operators. That is, different combinations of derivatives of the image data, e.g. the image intensity.

Fig. 3B shows a block diagram of a method for detecting a two-dimensional bar code in image data according an embodiment to the present invention. The method comprises the following steps.

In a first step 321 ("GRADIENT") , the gradient operator ^ is applied to two-dimensional image data. In one example, the image data may be the image intensity I(x,y) . The gradient operator in Cartesian coordinates acts on the image intensity as follows:

V7T \ ^{91 91}

ox oy

S

where ei and e ₂ are the orthogonal unit vecgtors, m is the partial derivative with respect to ^Λ' , and dy ± _s the partial derivative with respect to ^v . Hence, applying the gradient operator to the image data yields a two-dimensional vector field. In order to efficiently use computation power, an approximation of the gradient operator may be used. An efficient approximation of the gradient operator is the Sobel filter which acts on the image data via convolution. Thereby, an estimation of the gradient can be obtained. The 3x3 masks of a Sobel filter are as follows:

In a next step 322 ("DIVERGENCE") , the divergence of the gradient of the two-dimensional vector field is calculated. The divergence ^® iv of a vector field ^{r =} ( ^Γ ~' ^Γ τ,,? is calculated as follows:

Thus, the result of applying the divergence operator to a vector field is a scalar function. More specifically, the divergence measures the net flow at a given point in the vector field. If the divergence is negative, then a sink exists at that point. Otherwise the point corresponds to a source. The module corresponds to a source or a sink depending on the format of the two-dimensional bar code (dark on light, or light on dark) .

Figure 4Ά shows a schematical view of image data of two- dimensional bar code with poor modulation, and Figure 4B shows a schematical view of image data of a gradient field of the image data according to an embodiment of the present invention. Especially, the dots 411 and 412 in Fig. 4A exhibit different reflectance, albeit representing elements of the same type. Therefore, it may be difficult to determine that both positions correspond to a first type element (for example a black square) . At the same time, however, the corresponding sinks 411' and 412' in Figure 4B clearly show that both positions correspond to elements of the same type.

The divergence of the gradient is also known as the Laplacian operator ^Δ , which acts on a two-dimensional function as follows :

Also, the Laplacian operator can be approximated. An example of a discrete approximation of the Laplacian operator is:

- 1 -1 -1

1 = 1 8 -1

1 -1 -1

Thus, steps 321 and 322 can also be performed in a singl step by using the Laplacian operator. In other words, step 321 and 322 calculate intermediate image data indicative of divergence of a gradient of pixel values of the image data.

As a high-pass filter, the Laplacian operator detects noise in addition to the two-dimensional bar code. To alleviate this effect, a Gaussian smoothing can be applied to the image before employing the Laplacian operator. This detector is known as the Laplacian of Gaussian (LoG) . A fast approximation of the LoG is the Difference of Gaussians (DoG) .

In a further step 323 ("ENHANCING") , the divergence may be enhanced. In case of a dark on light two-dimensional bar code, the element, which corresponds to a sink, is often surrounded by several sources. To amplify the divergence of the module, the following filter mask is applied to the divergence :

The parameter A allows controlling the contribution of the original divergence. Good results have been obtained by selecting A = 8.

In a next step 324 ( "EXTREMUM IDENTIFICATION"), at least one element of the first and second type elements is identified based on an extremum of the intermediate image data. That is, minima and maxima of the divergence are determined and the position of the minima and maxima are identified with first and second type elements, respectively. The exact identification of the minima and maxima with the first and second type elements depends on the format of the two- dimensional bar code (dark on light, or light on dark) . Then the procedure may then continue with determining the location of the two-dimensional bar code in the image data based on the identified element in step 314 in Figure 3A.

Figure 5A shows a general apparatus embodiment of the present invention (a barcode reading device) . Specifically, there is shown an apparatus 100 comprising a processing unit 110 and a memory unit 120. The memory unit 120 may store code that, when executed on the processing unit 110, implements one or more method embodiments of the present invention. Optionally, the apparatus 100 may comprise an imaging unit 131 for acquiring image data. Further, the apparatus 100 may comprise a communication unit 132 for communicating a detection, decoding and/or authentication result to other entities, such as servers, controllers and the like. The communication may be effected over a network, such as a local area network (LAN), wireless network (WLAN) , the internet, and the like. Further, also bus systems, such as CAN, can be employed for data exchange . Fig. 5B shows a schematic view of a handheld embodiment of an apparatus for taking an image of the bar code and detecting, decoding, and/or authenticating the same in the form of a barcode reading device. The apparatus 100' comprises a window 101' through which a digital image of an item can be acquired. A two-dimensional bar code 20 is applied to the object by means of any mentioned printing, mechanical, physical, or chemical method. The apparatus 100' may further comprise an integrated processing unit (not shown) for performing one or more method of embodiments of the present invention. An additional operation element 102' may be provided for switching on and off the apparatus 100' and/or initiating the taking of a picture, acquiring/obtaining respective image data, and/or processing of the digital image data so as to detect, decode, and/or authenticate the two- dimensional barcode 20 on the object. The device may, of course, take other forms and may be wire-bound or wireless.

Fig. 5C shows a schematic view of a fixed type embodiment of an apparatus for taking an image of the bar code and detecting, decoding, and/or authenticating the same in the form of a barcode reading device. Like, for example, a module operable to be mounted on a production/distribution line for detecting bar codes disposed on items transported on said line. Again, the apparatus 100'' comprises a window 101'' through which a digital image of an item with a two- dimensional bar code can be acquired. The apparatus 100'' may further comprise an integrated processing unit (not shown) for performing one or more method of embodiments of the present invention. An additional fixation element 102'' may be provided for mounting the apparatus 100' ' on, for example, a production line in which a plurality of items pass by the apparatus 100'' for detection. The device may, of course, take other forms and may be wire-bound or wireless.

Benefits of the present disclosure and the embodiments of the present invention include that a two-dimensional bar code can be detected in image data that shows significant spatial variations in reflectance. Further, whereas conventional methods use a threshold for detecting two-dimensional bar code, embodiments of the present invention use differential operators which make thresholds obsolete.

A further advantage of the present disclosure can be achieved in overcoming restrictive requirements as they may be set by standards (e.g. ISO/IEC 16022:2006, Information technology - Automatic identification and data capture techniques - Data matrix bar code symbology specification) . More specifically, the data matrix (barcode) can be printed on a complex background rather than the mandatory quiet zone (i.e. a light area around the symbol which must not contain any graphic element which may disrupt decoding the barcode) .

Although detailed embodiments have been described, these only serve to provide a better understanding of the invention defined by the independent claims, and are not to be seen as limiting .