Method and portable device for recognising barcodes

[0001] The invention relates to the area of ​​optical barcode recognition. In particular, it relates to a method and a portable device for optical recording of a linear bar code pattern and for determining a sequence of symbols that are encoded by a bar code pattern in accordance with the preamble of the respective independent claims.

BACKGROUND ART [0002] Methods and devices for optical recording of a linear bar code pattern are known, especially those in which mobile devices are mobile phones with cameras: The starting point is usually the fact that pictures taken with a camera are sufficient sharp because, for example, the camera has the autofocus function. Such methods, however, fail using cheaper cameras with fix focus lenses, because cameras at a distance from the object that is necessary for a bar code or bar code image with sufficient resolution does not provide a sharp image.

[0003] There are also approaches for processing blurry photos to recognize a bar code. They are known, for example, from the following publications:

• J. Kim and H. Lee, "Joint nonuniform illumination estimation and deblurring for bar code signals," Opt. Express 15, 14817-14837 (2007) • Ta-Hsin Li, Ke-Shin Lii, “Deblurring Two-Tone Images by A Joint Estimation Approach Using Higher-Order Statistics”, Proceeding of the 1997 IEEE Signal Processing Workshop on Higher-Order Statis-tics (SPW-HOS '97), Page: 108, Year of Publication: 1997, ISBN: 0-8186-80005-9 • S. Esedoglu, "Blind deconvolution of bar code signals" Inverse Probl. 20, 121135 (2004).

[0004] The methods described are, however, computational, such that, for example, minutes are needed for image analysis. In addition, recognition in photos of a quality that is provided by a camera in a mobile phone without autofocus is not meaningful and even impossible.

PRESENTATION OF THE INVENTION [0005] Accordingly, the object of the invention is to create a method and a portable device for optical recording of a linear bar code pattern and for determining a sequence of symbols that are encoded by a bar code pattern that removes the disadvantages described above.

[0006] This task is solved by a method and a portable device in accordance with the respective independent claims.

[0007] A method of optical recording of a linear bar code pattern and for determining a sequence of symbols that are encoded by a bar code pattern emerges from a blurred RAW image and has the following steps:

• taking a RAW image of the bar code pattern;

• pre-processing a RAW image to create a sequence of output patterns;

• comparison of the initial pattern with the saved reference patterns, where reference patterns correspond respectively to out-of-focus images of sharp nominal patterns, and at least one symbol is assigned to one reference pattern;

• establishing, respectively, a reference formula for each of the initial patterns that shows the greatest similarity with the initial formula;

• issuing, sending or saving symbols that correspond to specific reference patterns, in accordance with the sequence of output patterns, as a sequence of symbols.

[0008] Alternatively, instead of a series of output patterns, the starting point is one output pattern. This only output pattern represents a complete bar code, with no subdivision into individual symbols. The steps explained below can also be applied to an output pattern that maps the sequence of more symbols according to the overall bar code.

[0009] The starting point is therefore one image from a non-focusing camera (or focusing incorrectly) in which the bar code to be recognized lies outside the distance of the sharp image. After pre-treatment, the image is compared with reference patterns. Each reference formula corresponds to a blurred image of the nominal formula, which is preferably offline and has been previously calculated. In turn, the nominal pattern corresponds to a code pattern or code pattern with at least one adjacent code pattern. Due to the fact that the nominal pattern contains adjacent code patterns, the influence of the adjacent code pattern can be taken into account when it arises with a blurred image. Instead, the code pattern is assigned to the code symbol. A larger number of code patterns can also be assigned to the same code.

[0010] In the commonly known EAN (European Article Number) code or related codes, such as the GTIN (Global Trade Item Number) code, the code represents a series of numbers. The numbers correspond to the symbols mentioned above, and each digit, depending on the context, is assigned one or several code patterns consisting of two black bars and two white boxes.

[0011] To create a reference pattern to the nominal pattern, the camera out of focus is modeled and the blurred image is simulated. Out of focus is modeled, for example, using the "point spreading function" (PSF), i.e. at least the approximate impulse response of a camera. For example, it can be experimentally simply determined by photographing a black spot against a white background.

[0012] PSF depends on various parameters, especially the distance from the object between the mapped plane and the optics. Therefore, PSF is preferably determined for a greater number of distances from the object, and for each code a larger number of reference formulas are calculated and stored according to different distances from the object. For each of the nominal patterns, therefore, preferably a larger number of saved reference patterns are available, respectively for various image parameters, especially for various distances. When comparing the output formulas with the saved reference formulas, reference formulas are used that correspond to the estimation of the actual image parameters, e.g. distances.

[0013] Estimation of the real distance from the object is preferably also exclusively based on a RAW image or an initial pattern. For example, the slope (gradient) of signals that correspond to the black / white transitions in the bar code gives a measure of defocusing, and thus also a measure of the distance to the object. For example, the most inclined side can be searched for in the original formula, and the slope can be mapped using a predetermined and saved assignment function over distance or directly on the index of the series of corresponding reference formulas.

[0014] Alternatively, other methods may also be used to estimate the distances that originate from the recorded images, which are known, for example, in autofocus cameras.

[0015] Due to the lack of sharpness of the image, the adjacent code patterns interact with each other. Therefore, for various combinations consisting of two or more adjacent code patterns, a custom reference pattern is preferably created. For example, for the digit or the symbol "3" (in the coded coding), ten separate reference patterns corresponding to the pairs of the symbols "03", "13", ... to "93" are created and saved. If, in addition to the previous symbol, the next symbol is also taken into account, 100 separate reference patterns "030" are produced. "130", "230",. "031", "131", "231",. "739", "839", "939",. . In other words, the nominal patterns are set up respectively from the code pattern according to the first symbol (reference symbol) and at least with the adjacent code pattern according to the second symbol or with the second and third symbols (adjacent symbols). Thus, reference formulas resulting from nominal formulas are assigned to one pair or three symbols respectively.

[0016] The entire reference pattern may be memorized according to two or three symbols, or only the part of the reference pattern that is of interest to us which corresponds to the symbol of interest (in the example above the symbol "3") may be remembered. Part of the information about the adjacent symbol or adjacent symbols goes through the blurry image to the end areas of the relevant part of the reference pattern.

[0017] The reference formulas are preferably pre-calculated offline outside the mobile device and then transferred with the assigned symbols to the mobile device and used there to compare the formulas. Preferably, information is also sent on the allowed symbol sequences in a particular combination, whether in the form of a list of symbol sequences or as a distance specification. For example, when selling, you know which product codes should be expected so that only these will be provided. In this way, recognition can be accelerated and reliability further improved.

[0018] Reference patterns are thus assigned to one reference symbol and at least one adjacent symbol respectively. When comparing the sequence of output patterns (according to the symbol sequence) with reference patterns, it is preferably required not only to correctly assign the output pattern to the reference pattern, and thus also to the reference symbol, but also that the symbol adjacent to the reference symbol matches the corresponding adjacent output pattern. Conversely, when a neighbor symbol is known, the search for a reference symbol can be restricted and thus accelerated. In general, there is a multidimensional optimization problem in which when recognizing reference patterns, pairs of symbols or triples of symbols with adjacent reference patterns must be coherently assigned. Various optimization methods are used for this problem.

[0019] In a preferred embodiment of the invention, the sequence of output patterns during recognition is read sequentially. Preferably, reference patterns of the respective symbol combinations are used. For example, if the "4" symbol was last recognized, then the next symbol is recognized from reference patterns to "40", "41", "42", ... to "49" or three "400" symbol pairs, "401", "402", ... to "499", i.e. these reference formulas are first or only compared with the current output pattern. In this way, the search space is limited and the speed and quality of recognition is increased.

[0020] The pre-processing step exhibits at least the step of: creating an overall output pattern according to a luminance pattern along the bar code pattern, i.e. in a direction perpendicular to the direction of the individual bar code bars, and dividing the overall output pattern in a sequence of output patterns.

[0021] An overall output pattern can be created, for example, by creating a brightness path along the bar code pattern by selecting a scan line of an optionally rotated RAW image, or by information about more RAW image scan lines.

[0022] In another preferred embodiment of the invention, during the pre-processing, a brightness waveform is generated along the bar code pattern as a result of performing a Hough transformation into a RAW image or a fragment of a RAW image, thereby creating a frequency distribution on the image plane positioned by angle and distance (Hough space) . The course of brightness is extracted according to the sequence of values ​​on these lines on the image plane, which leads through the maximum values ​​on the image plane and corresponds to a fixed angle in the RAW image. Thanks to the Hough transformation, the brightness waveform is determined on the one hand, regardless of the bar code orientation, and on the other hand, the averaging of the parallel brightness waveforms is automatically carried out over the entire height of the bar code bars.

[0023] In a preferred embodiment of the invention, the steps from recording the RAW image to determining the recognized symbol sequence are repeated several times until the given number of results match. This preferably takes place with the frequency of the image recording or the frequency of the video camera, for example with 15 or 30 images / second.

[0024] The method according to the invention is preferably used in commercial spaces. A customer with a properly prepared mobile device, usually a mobile phone with a camera, can read bar codes on products and / or commercial shelves. A large number of information services can be provided based on this product identification. They may be of a general nature or individually tailored to the user, and may be prepared by sales organizations or by third parties. Product information may be, for example, allergy information, price comparisons with similar offers, information from Fair-Trade organizations, certification and consumer organizations, etc. in addition to price and quantity, etc. In another preferred application of the invention, the product is registered as user-selected. Directly or at the checkout, the products are transferred to a sales transaction, for example via a local wireless connection such as Bluetooth or WLAN, and based on this payment is made.

[0025] The basis of the described application in a preferred embodiment of the invention are the symbol sequences to be recognized and the corresponding reference patterns are thus transmitted wirelessly to the mobile device at the point of sale, optionally also further information to individual products. In this way, recognition can be limited to realistically available product codes that contain a small number of essentially possible maximum numbers, for example an EAN code. For example, the maximum number is 1000 to 100,000 codes. In this case, a variant of the method in which the bar code is recognized as the overall, the only output pattern, without subdivisions into a larger number of output patterns, can be used favorably: Only reference patterns for all real product codes should be made, possibly also repeatedly for various parameters image, and transfer it to your mobile device.

[0026] Known methods can in principle also be used to compare the initial pattern and the reference pattern. In another preferred embodiment of the invention, the comparison takes place when the first derivatives of both formulas are compared, especially when the difference in values ​​of the first derivatives is created and added together. The sum calculated in this way is a measure of the similarity of both formulas. In the preferred method variant, the derivative sign is additionally compared in the area of ​​the extremities of the formulas. Different characters reduce the similarity dimension of the designs. In addition, differences in the absolute values ​​of the formulas can also be added. In addition, in all variants, patterns can be repeatedly compared with each other, and each time shifted relative to each other by different values.

[0027] As has just been described, in a further preferred embodiment of the invention in a first pass the recognition of the bar code as a whole is tried on the basis of one output pattern. Only when this fails with the designated confidence - because, for example, a given bar code is not part of the number of expected bar codes - the overall output pattern is divided into output patterns and individual symbols are recognized.

[0028] The portable device has a camera and a data processing unit, the data processing unit being programmed to carry out the method described. To this end, it preferably includes memory means with computer program code tools stored therein which describe the computer program, wherein the implementation of the computer program leads through the data processing unit to carry out the method.

[0029] The computer program for optical recording of the linear bar code pattern and for determining the sequence of symbols that are encoded by the bar code pattern is loaded into the external digital memory of the data processing unit and has computer program code tools that lead to the implementation of the method according to the invention if implemented in a digital data processing unit. In a preferred embodiment of the invention, the corresponding computer program product has a data carrier or computer readable medium on which the computer program's code tools are stored.

[0030] Further advantageous embodiments arise from the dependent claims. The features of the method claim can be combined with the device claims and vice versa.

BRIEF DESCRIPTION OF THE DRAWINGS [0031] The subject of the invention is described below in more detail on the basis of preferred embodiments which are shown in the accompanying drawings.

<td colspan="2">shows:</td>

<td>Fig. 1</td><td>the relationship between the information processed;</td>

<td>Fig. 2</td><td>defocused image of the bar code;</td>

<td>Fig. 3</td><td>brightness course along the bar code;</td>

<td>Fig. 4</td><td>an exemplary initial formula and the reference formula thus identified;</td>

<td>Fig. 5</td><td>process flowchart; and</td>

<td>Fig. 6</td><td>portable device.</td>

[0032] The symbols used in the drawings and their meanings are summarized in the symbol list. In general, the same parts are marked with identical symbols in Fig.

WAYS OF IMPLEMENTING THE INVENTION [0033] The starting point is a coding system of known type. One symbol, one digit in the EAN code, can be assigned different codes or code patterns depending on the connection. For example, one digit can be encoded using a specific bit string (e.g. 0111011, corresponding to a black and white string in the bar code), either by the same bit string or backwards (1101110) or by the complementary bit string (1000100) or backwards and complementarily. The last two variants are known in the EAN code as the R code and the G code.

[0034] Fig. 1 shows the relationship between the barcode recognition information processed according to the invention. The goal is to extract the initial RAW image 6 (see also Fig. 2) of the bar code 12, taken with the help of the camera 13, to extract the initial sequence of symbols 1 underlying the bar code. Through pre-processing 7, the overall output pattern 8 is generated from the RAW image 6 (see also Fig. 3). This basically corresponds to the brightness course along the bar code. The course of brightness can be determined along a single line perpendicular to the bars of the bar code in the photo RAW 6, or with the help of information about more such lines. When rotating and distorting the RAW images 6, they can be aligned in a known manner before the overall output pattern 8 is extracted. For example, Hough transformation can be used for this purpose.

[0035] The overall output pattern 8 is divided according to Fig. 3 into individual output patterns 9. To this end, a priori knowledge of the coding structure is used, for example, that it relates to the EAN-8 or EAN-13 (UPC12) bar code , that the codes for all symbols have the same width and consist of four alternating white and black lines, and that known start and end patterns are available.

[0036] In Fig. 1, between the two vertical lines, for example, the overall output pattern 8 is shown as a slice of about 400 pixels from a brightness waveform of about 650 pixels. Above it, the output patterns 9 with a total width of approx. 400 pixels are shown (both patterns come from different angles). The horizontal axis represents the number of pixels, respectively, and the vertical brightness. In Fig. 3 the output patterns 9 with the borders lying between them (vertical lines) are shown next to each other and enlarged. Fig. 2 shows a blurred photo of a bar code, with recognized lines bounding the ends (vertical lines) and a horizontal line along which the course of brightness is determined.

[0037] The output patterns 9 are preferably compared in a mobile device 15 compared 10 patterns with reference patterns 5, in order to reconstruct the recognized sequence of 11 symbols, which must be identical to the original sequence of 1 symbols. The production of reference pattern 5 and the comparison of 10 patterns are first described below, again based on Fig. 1:

[0038] For each symbol, in this example, the numbers 0 to 9 (top line in Fig. 1), is assigned at least one code pattern. Here, for example, there are three patterns of 4 code every symbol, as is known from the EAN code. They are called the code L, G and R. For example, in Fig. 1 in the second line three code patterns 4 for numbers 2 and 7 are marked, the remaining patterns of 4 codes have been marked with points. In the first group of digits of the 13-digit EAN code (there are two groups of digits, one to the left of the separating pattern in the middle, the other to the right of it) only L codes and G codes can be available, so a total of twenty code patterns, in the other a group of digits only R codes, so only ten code patterns. The first and last digits of a group of digits attach to the start code or end code. For each digit, depending on the possible neighborhood, all combinations can be created including changing neighbors. So for each digit in the first group of digits it is 20 * 20 = 400 (i.e. assuming that one of the adjacent digits is known) combinations, for each digit at the end of the first group of digits twenty combinations, for each digit in the second group of digits 10 * 10 = 100 combinations, and for each digit at the end of the second group of digits, ten combinations.

[0039] Each of these combinations of code patterns 4 has a nominal pattern 2. A large number of nominal patterns are represented, for example, in the third line of Fig. 1 by means of two connections. From the nominal formulas 2, by means of the simulation of a blurry optical image 3 reference formulas 5 are calculated. To this end, PSF image 3 is preferably used (especially reduced to one dimension) and folded with the nominal formulas

2. Reference formulas 5 can be reduced to the segment corresponding to the symbol of interest. So, for example, when neighboring symbols, as shown in Fig. 1, are included in the blur simulation, one third on the left and one third on the right may be cut off according to the blurred image 3, so that the reference pattern already contains only the middle one third parts. Thus, the reference formula 5 represents only one symbol, however, with the influence of the adjacent symbols.

[0040] By assigning reference pattern 5 and nominal pattern 2 to combinations of code patterns 4 and assigning code patterns 4 to symbols, the nominal patterns 2 are also assigned to three symbols respectively. (In the event that adjacent code patterns are not included in the simplified embodiment of the invention, exactly one symbol would be assigned to each nominal pattern 2.

[0041] The calculation of the reference formulas 5 is preferably first performed offline, based on simulations of various distances from the object and, respectively, for various types of cameras.

[0042] In a preferred embodiment of the invention, the possibly resulting several thousand reference patterns 5 are archived in the form of an image file. Each reference pattern 5 is represented, for example, by an image slice with 30 image points (pixels). In an image consisting of, for example, 1056 times 421 pixels, it is possible to write all 5 reference patterns for the EAN-13 code at a certain distance from the object. Since the image can have three color channels and possibly an alpha channel, and the reference patterns are only monochrome, more series of reference patterns can be transferred in the form of one image. This has the advantage that existing methods can be used for (lossless) compression and for transferring photos to portable devices using a camera.

[0043] When comparing 10 patterns, preferably in a mobile device 15, for example, proceeding from the end of the bar code 12, one proceeds sequentially, and by using information on the structure of the bar code as well as information on just recognized symbols, the search for the next optimally matching symbol remains limited and thus accelerated. In this case, it is also generally possible to correct the assignment of the last recognized symbol when the symbol does not match the expected symbol. Optionally, the search can also be limited by information about the symbol sequence allowed in the current context.

[0044] Thus, for example, when, for example, in the first digit fragment of the EAN-13 code to the first output pattern 9 the symbol was identified as the digit "7", encoded in the L code, then for the next output pattern 9 only or at least initially a series consisting of 400 reference formulas 5 (i.e. compared with the initial formula 9), which belongs to the number "7", coded in the code "L". Furthermore, in a preferred embodiment of the invention, the search begins with those reference patterns whose assigned average symbol is identical to the expected next symbol from the comparison of the patterns 10 of the first output pattern 9.

[0045] For the known EAN-13 code, when recognizing individual symbols, it is also recognized whether the symbols are encoded in the L or G code, respectively, and according to the coding sequence, the first place or the next symbol sequence symbol 1 is decoded in a known manner.

[0046] Fig. 4 shows exemplary output patterns 9 and reference patterns identified with them. Continuous waveforms show the output pattern 9. Extracted from the camera image, respectively. Intermittent waveforms show the reference pattern, which has been assigned to the output pattern, respectively. 9. Point waveforms, which in almost every case coincide with reference patterns, present correct patterns for comparison purposes. reference. Six groups of a longer series were presented. Each pattern group has a length of about 30 pixels and is assigned to a symbol sequence location. The title to the group of patterns reproduces the position of the symbol in the sequence using "digit pos:", and the previously recognized sequence symbol using "before d:", and the coding (also called "parity") of the previously recognized symbol using "p:", shown with the values ​​1 and 2 for coding L or G. The numbers in the legend in each pattern group or each sequence symbol show, respectively:

• in the first line: the correct or ideal number and code of the symbol (in the first example: 7 and 1), then the right number and the code of the next symbol (in the first example: 4 and 2). These values ​​are naturally only present in a test environment in which the code sequence to be identified is known. Then the second digit in brackets tells you where the correct reference pattern is in line with the similarity to the initial pattern 9 mixed reference patterns 5 (in the first example in the fourth place; in the third, fifth and sixth examples in the first place, which means perfect recognition ; in the fourth example, in thirteenth place).

• in the second line: the digit and coding of the symbol recognized in accordance with the presented method (in the first example: 7 and 1), then the expected digit and the coding of the next symbol (in the first example: 1 and 1, which in this case corresponds to a false estimate).

[0047] The comparison of the second and third lines shows that the recognition of the symbols for all positions in the sequence is correct and partly incorrect only in the estimates of the next symbol.

[0048] Fig. 5 shows a block diagram of the method. In this it defines • the first stage 21 "grab" taking a RAW image 6 using camera 13;

• the second stage 22 "preproc" pre-processing 7 RAW images 6 to produce a sequence of output patterns 9;

• third stage 23 "comp" comparing 10 output patterns 9 with the saved reference patterns;

• fourth step 24 "assoc", specifying for each of the output patterns 9 the optimally assigned reference pattern 5;

• fifth stage 25 "stor" issuing, sending or saving symbols that correspond to specific reference patterns 5.

[0049] The third and fourth steps 23, 24 can be repeated many times if the starting patterns 9 are processed one after the other. For cases in which the first to five stages are carried out repeatedly until the set interruption criterion is met, the fifth stage is recorded accordingly the transition result, and then the next stage 26 "ok?" Is carried out to control the interruption criterion. If the interrupt criterion (s) is met, in the exit stage 27 "outp" the result is issued, saved or transmitted, and finally the process is terminated. Otherwise (n) the steps are repeated with a new shot for the RAW image.

[0050] Fig. 6 schematically shows a portable device 15 with a camera 13 and a data processing unit 14. The data processing unit 14 is programmed to perform the recognition starting on the one hand from the stored reference patterns 5 and on the other hand from the sequence of photos RAW 6.

LIST OF REFERENCES [0051] symbol sequence nominal pattern out of focus image code pattern reference pattern RAW image pre-processing overall output pattern output pattern comparison pattern recognition recognized sequence of symbols 12 bar code 13 camera 14 data processing unit 15 portable device

ETH Zurich, Switzerland Representative:

EP 2 377 072 B1

Z-14000