JP2007094584A - Method for detecting two dimensional code, detecting device, and detecting program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a method for detecting two dimensional code, detecting device, and detecting program for avoiding mis-detection of two dimensional code due to mis-recognition of the position detecting pattern, and accurately detecting two dimensional code from an image including two dimensional code. <P>SOLUTION: The method for detecting two dimensional code determines there is a single two dimensional code in the two dimensional code area under the condition that characteristic of the two dimensional code is detected from the two dimensional code area including three position detecting element patterns and the peripheral area in addition to the condition that an apex of a rectangular isosceles triangle is formed by the central point of three position detecting element patterns. <P>COPYRIGHT: (C)2007,JPO&INPIT

Description

  The present invention relates to a two-dimensional code detection method, detection apparatus, and detection program, and more particularly, to a two-dimensional code detection method, detection apparatus, and detection program for detecting a two-dimensional code from an image including the two-dimensional code.

  Bar codes that represent data by combining vertical lines with different thicknesses and intervals are widely used around the world, such as for product information management. The bar code is a one-dimensional code in which vertical lines are arranged in one direction. Recently, the use of two-dimensional codes has become widespread due to the large amount of information that can be expressed. The two-dimensional code is a code in which data represented by a binary code is converted into cells and arranged as a pattern on a two-dimensional matrix (Patent Document 1). Regarding the QR code which is a representative example of the two-dimensional code, the basic specification is standardized by JIS (JIS-X-0510).

  For example, by converting the description content of a paper document into a two-dimensional code and adding the two-dimensional code to the margin of the paper document, when the paper document is scanned, the added two-dimensional code is recognized. If decrypted, it is possible to acquire the description content of the document as electronic data without using an optical character reader (OCR) or the like.

  As shown in FIG. 3, the QR code symbol is composed of modules arranged in a square, and includes a coding area used for data coding and a function pattern such as a position detection pattern. . The position detection pattern is a functional pattern composed of three position detection element patterns arranged at the three corners of the symbol. The center points of the three position detection element patterns form a right-angled isosceles triangle having each center point as a vertex. In addition, a blank area called a quiet zone is provided around the four sides of the symbol.

  When decoding the QR code, the symbol is optically read by scanning with a dedicated QR code reader, the QR code is detected from the read image, and the detected QR code is decoded (Patent Document 2). In order to detect the QR code, three position detection element patterns are detected, and all the coordinates of the center point of the position detection element pattern are calculated. The calculation of the coordinates of the center point is performed according to the method described in p65-66 of the JIS standard (JIS-X-0510). By specifying the coordinates of the center point of the position detection element pattern, the position of the position detection pattern is obtained, and the QR code is detected.

Further, the above-described two-dimensional code has a larger amount of information that can be expressed than the one-dimensional code, but the information amount is still limited. For this reason, when a large amount of information is expressed by QR codes as described in the section “Connection mode” of p22 5.3.2.7 of the JIS standard, the information is divided into a plurality of QR codes. expressing. Conventionally, when decoding QR codes in this concatenation mode, symbols are read one by one and a plurality of QR codes are sequentially decoded.
Japanese Patent No. 2938338 Japanese Patent Laid-Open No. 06-012515

  However, in the conventional detection method, when noise is included in the read image, the position detection pattern is erroneously detected by, for example, misrecognizing the noise as a position detection element pattern, and the QR code is accurately detected. There was a problem that it was not possible. For example, this is a case where the Chinese character “times” is erroneously recognized as a position detection element pattern.

  If a general-purpose scanner such as a flatbed scanner can be used for optical reading of symbols, the convenience of the QR code is significantly improved. However, when information is expressed by a plurality of QR codes, an image obtained by scanning with a general-purpose scanner includes a plurality of symbols, and it is difficult to accurately and quickly detect individual QR codes. There was a problem.

  That is, a large number of position detection element patterns are detected from an image including a plurality of symbols. For example, if there is one QR code, there are three position detection element patterns. However, if there are four QR codes, the number of position detection element patterns is four times that of twelve. For this reason, as shown in FIG. 4, position detection element patterns included in different symbols are combined and misrecognized as a position detection pattern, making it difficult to accurately detect a QR code.

  In addition, it is possible to avoid erroneous recognition by considering all combinations of position detection element patterns. In this case, however, the calculation is repeated endlessly until an optimal combination is obtained. As a result, the amount of calculation increases, the processing speed decreases, and it becomes difficult to quickly detect the QR code.

  The present invention has been made to solve the above problems, and an object of the present invention is to prevent a two-dimensional code from being erroneously detected due to erroneous recognition of a position detection pattern, and to perform two-dimensional detection from an image including a two-dimensional code. It is an object to provide a two-dimensional code detection method, a detection device, and a detection program capable of accurately detecting a code.

  Another object of the present invention is to provide a two-dimensional code detection method, detection apparatus, and detection program capable of accurately and quickly detecting individual two-dimensional codes from an image including a plurality of two-dimensional codes. There is to do.

In order to achieve the above object, the two-dimensional code detection method of the present invention comprises:
Two-dimensional code detection method for detecting a two-dimensional code in which three position detection element patterns are provided at positions corresponding to respective vertices of a right isosceles triangle and a data area is provided in an area determined by the position detection element pattern Because
Read an image containing the two-dimensional code,
Binarize the scanned image,
A plurality of position detection element patterns included in the binarized image are detected,
Specify the position of the center point of the detected position detection element pattern,
From the center points whose positions are specified, select the three center points that form the vertices of a right isosceles triangle,
Extract a feature as a two-dimensional code from a two-dimensional code area determined by the position detection element pattern corresponding to the selected center point or its peripheral area,
When a feature as a two-dimensional code is extracted, it is determined that one two-dimensional code exists in the two-dimensional code region,
It is characterized by detecting a two-dimensional code.

  According to the present invention, in addition to the condition that the vertex of the right isosceles triangle is constituted by the center points of the three position detection element patterns, the two-dimensional code area including the three position detection element patterns and the surrounding area are two-dimensionally Since it is determined that one two-dimensional code exists in the two-dimensional code area on the condition that a feature as a code is extracted, two-dimensional code is prevented from being erroneously detected due to erroneous recognition of the position detection pattern. A two-dimensional code can be accurately detected from an image including the code. Further, even in the case of an image including a plurality of two-dimensional codes, individual two-dimensional codes can be accurately and quickly detected from such images.

  Hereinafter, an example of an embodiment of the present invention will be described in detail with reference to the drawings. Here, an example using a “QR code” as a two-dimensional code will be described.

(First embodiment)
FIG. 1 is a block diagram showing a schematic configuration of a QR code processing apparatus according to the present embodiment. This apparatus applies the present invention to detection of a QR code from image data. As shown in FIG. 1, the processing apparatus includes an image input device 10 that acquires raster image data from a document image. The image input device 10 includes a scanner that reads a document image from a paper document, a digital camera, and the like. When a plurality of QR codes are attached to a paper document, the image input device 10 acquires raster image data including a plurality of QR codes.

  The processing device holds raster image data acquired by the image input device 10 and also functions as a working area, a CPU 14 that reads a program and executes various processes, and a QR code detection process and a decoding process. ROM 16 storing a program to be executed, external interface 18 for connecting to another computer via a network, image output device 20 such as a printer, and document data related to data obtained by decoding a QR code And a database 22 in which are stored.

  The image input device 10, the memory 12, the CPU 14, the ROM 16, the external interface 18, the image output device 20, and the database 22 are connected to each other via a data bus 24.

  Next, a procedure for acquiring raster image data including a plurality of QR codes and decoding each of the plurality of QR codes with the above processing device will be described. FIG. 2 is a flowchart showing a processing routine executed by the CPU 14.

  First, in step 100, raster image data is acquired from the image input device 10 and stored in the memory 12. In the next step 102, the image data is binarized on the memory 12. The binarization method may be simple binarization using a threshold or other binarization methods. In the next step 104, all the coordinates of the center point of the QR code position detection element pattern (hereinafter sometimes referred to as “center coordinate”) are detected from the binarized raster image data, and the detected center point is detected. Are stored in the memory 12 as a list. As a detection method, for example, an existing method described in JIS standard (JIS-X-0510) can be used.

  Next, in step 106, a “combination detection process” for detecting a combination of three position detection element patterns included in the same symbol is executed. In step 104, the coordinates of the center point of the position detection element pattern are detected and listed. At the stage of listing, it is unknown which three combinations are included in the same symbol. By detecting a combination of three position detection element patterns included in the same symbol from the list, the position of the position detection pattern of each symbol is obtained, and a QR code is detected.

  Here, the outline of the “combination detection process” will be briefly described. FIG. 10 is a diagram illustrating a QR code symbol structure. As shown in FIG. 10, the QR code symbol 30 has three position detection element patterns 32A, 32B, and 32C. The center points a, b, and c of the position detection element patterns 32A, 32B, and 32C constitute a right-angled isosceles triangle 36 having each center point as a vertex as shown in the figure. In addition, a blank area (hereinafter referred to as “quiet zone”) 34 in which nothing is displayed is provided around the four sides of the symbol 30. An outer periphery 34A of the quiet zone 34 is illustrated by a dotted line. According to the JIS standard, the width of the quiet zone 34 is defined as 4 modules. The module is a unit square that displays 1-bit information in the QR code.

  In the present embodiment, combinations are detected using the above-described symbol features. Specifically, a combination of coordinates of the center points of the three position detection element patterns forming a right isosceles triangle is detected, and it is determined whether or not there is a quiet zone around the three coordinates. When there is a quiet zone, it can be determined that the combination is a combination of three position detection element patterns included in the same symbol. Details of the combination detection process will be described later.

  If all the combinations of the position detection element patterns are detected in step 106, then one set of combinations is selected from the combinations, and the QR code related to the combination is decoded. That is, first, in step 108, one set of combinations is selected, the symbol rotation angle is calculated from the coordinates of the center point of the position detection element pattern, the symbol direction is corrected based on the calculated rotation angle, and the reference Make the QR code upright with respect to the coordinates. In the next step 110, the symbol whose direction is corrected is cut out (trimmed) and held in the memory 12. In the next step 112, the coding region of the symbol is decoded. As a decoding method, for example, an existing method described in the above JIS standard can be used.

  Next, in step 114, it is determined whether or not QR codes have been decoded for all the detected combinations. If the determination is affirmative, the routine is terminated. If the determination is negative, the routine returns to step 108, and another set of combinations is selected, and the processing of steps 108 to 112 is repeated. That is, when a plurality of combinations are detected as a result of combination detection, rotation correction, trimming, and decoding are performed for all combinations.

  The above processing device can perform various processes based on the decoded data. For example, when the decrypted data is an ID number for identifying a document stored in the database 22 (hereinafter referred to as “document ID”), the database 22 is searched using the document ID as a search key. The document data body is acquired from 22. The acquired document data is printed using the image output device 22. The obtained document data can also be transferred to another computer via the external interface 18.

  Here, the “combination detection process” executed in step 106 of FIG. 2 will be described in detail. As described above, this processing is executed after all the coordinates of the center point of the position detection element pattern are detected and listed. Since one QR code symbol includes three position detection element patterns, when there are N QR codes, 3N coordinates are listed.

  FIG. 5 is a flowchart showing a subroutine of the combination detection process. First, in step 200, the coordinate list of the center point held in the memory 12 is referred to. The center points of the three position detection element patterns constituting the position detection pattern are A, B, and C, and the three coordinates from the coordinate list are associated with the center points A, B, and C in steps 202 to 206. Select.

  Combine 3N to 3 pieces so as to be brute force. The number of combinations is obtained by calculating a combination (= combination) for extracting 3 from 3N, as shown in the following equation.

  For example, if there are two QR codes, the number of position detection element patterns is 2N = 6, and there are 20 combinations to select from 6 to 3. If there are 10 QR codes, there are 4060 combinations.

  Next, in step 208, “right-angled isosceles triangle determination process” is executed. In such determination processing, it is determined whether or not the center points A, B, and C specified by the three selected coordinates constitute each vertex of a right-angled isosceles triangle. In the case of an affirmative determination (True), the center points A, B, and C constitute vertices of a right-angled isosceles triangle, and three position detection element patterns may be included in the same symbol. The process proceeds to “a determination process for whether there is a quiet zone” in step 210.

  In step 210, an area (candidate area) where a QR code symbol may exist is assumed from the three selected coordinates, and it is determined whether or not a quiet zone exists around the candidate area. In the case of an affirmative determination (True), there is a quiet zone around the candidate area, and it is very likely that a symbol exists in the candidate area. A list of coordinates representing the position of the detection pattern is listed and stored in the memory 12. That is, it is determined that the position detection element patterns corresponding to the three selected coordinates are included in the same symbol and constitute a position detection pattern, and the combination of the coordinates is stored in the memory 12.

  Various factors cause misrecognition of the position detection pattern. For example, noise included in raster image data may be recognized as a position detection element pattern. Even if the center points A, B, and C form vertices of a right isosceles triangle, position detection element patterns included in different symbols may be combined. However, since the QR code symbol has a feature that a quiet zone is provided around its four sides, it is determined whether or not a quiet zone exists around the candidate area as in the present embodiment. By doing so, it is possible to prevent a position detection element pattern included in different symbols from being combined and erroneously recognized as a position detection pattern.

  In addition, since combinations of position detection element patterns (combinations of three coordinates) included in the same symbol are sequentially specified, it is not necessary to repeat the calculation endlessly, and QR code detection processing is simplified, and all combinations The time until is identified is shortened.

  On the other hand, if the determination in step 208 or step 210 is negative (false), it is verified in step 214 to step 218 whether or not all combinations have been selected. If all combinations have been selected, the routine is terminated. To do. On the other hand, if there is a combination that has not been selected, the process returns to step 202 to step 206 to select a different combination of three coordinates from the coordinate list in correspondence with the center points A, B, and C. . And the process of step 208-step 212 is repeated about a new combination.

  Here, the “right isosceles triangle determination process” executed in step 208 of FIG. 5 will be described in detail. FIG. 7 is a flowchart showing a routine for determining a right isosceles triangle.

  First, in step 300, the three selected coordinates are acquired, and in step 302, it is determined whether or not the center point A can be a right angle apex of a right isosceles triangle. If the determination in step 302 is affirmative (True), it is determined that the center points A, B, and C constitute vertices of a right-angled isosceles triangle (True). On the other hand, in the case of negative determination (False) in step 302, the process proceeds to the next step 304, and it is determined whether or not the center point B can be a right angle apex of a right isosceles triangle.

  If the determination in step 304 is affirmative (True), it is determined that the center points A, B, and C constitute vertices of a right-angled isosceles triangle (True). On the other hand, in the case of negative determination (False) in step 304, the process proceeds to the next step 306, where it is determined whether or not the center point C can be a right angle apex of a right isosceles triangle. If the determination in step 306 is affirmative (True), it is determined that the center points A, B, and C constitute vertices of a right-angled isosceles triangle (True). On the other hand, if the determination in step 306 is negative (False), it is determined that the center points A, B, and C do not constitute vertices of a right isosceles triangle (False).

  Here, the “right angle apex determination process” executed in steps 302 to 306 in FIG. 7 will be described in detail. FIG. 6 is a diagram for explaining the geometrical conditions for forming a right isosceles triangle. FIG. 8 is a flowchart showing a routine for determining the right-angled vertex executed in step 302 of FIG.

  As shown in FIG. 6, in order for a triangle having points A, B, and C as vertices to be a right isosceles triangle having a point A as a right angle apex, an angle formed by a line segment AB and a line segment AC θ must be 90 °, and the lengths of the line segment AB and the line segment AC must be equal.

  Therefore, first, in step 400 of FIG. 8, the three selected coordinates are acquired, and in step 402, an angle θ formed by the line segment AB and the line segment AC is calculated from the acquired coordinates, and in step 404, Based on the calculation result, it is determined whether or not the angle θ is 90 °. That is, it is determined whether or not the inner product of the vector from point A to point B and the vector from point A to point C becomes zero. Here, in the case of negative determination (False), it can be determined that it is not a right-angled isosceles triangle having the center point A as a right angle apex (False). On the other hand, if the determination in step 404 is affirmative (True), the process proceeds to the next step 406.

  In step 406, the lengths of line segment AB and line segment AC are calculated from the acquired coordinates, and in step 408, it is determined whether the lengths of line segment AB and line segment AC are equal based on the calculation result. . Here, in the case of negative determination (False), it can be determined that it is not a right-angled isosceles triangle having the center point A as a right angle apex (False). On the other hand, if the determination in step 408 is affirmative (True), it can be determined that the center point A is a right-angled isosceles triangle (True).

  Next, the “blank area (quiet zone) presence / absence determination process” executed in step 210 of FIG. 5 will be described in detail. 11 and 18 are diagrams for explaining a method for determining whether or not there is a quiet zone.

  As shown in FIG. 11, when a QR code is present, when scanning on a virtual line (scan line) 38 drawn in the quiet zone 34 of the symbol 30, all of the scan lines 38 have pixel values of “white”. (Hereinafter, referred to as “white pixel”). A pixel having a pixel value “black” is referred to as a “black pixel”. Further, except for the illustration of the scan line 38, the same configuration as the QR code shown in FIG. 10 is provided.

  In the present embodiment, as shown in FIG. 18, the center points of the three position detection element patterns 42A, 42B, and 42C are A, B, and C, and regions (candidates) where a QR code symbol may exist. Region) 40 is assumed. Further, it is assumed that a quiet zone exists around the candidate area 40, and an outer periphery 44A of the quiet zone is assumed. Further, a scan line 48 is set between the outer periphery 40A of the candidate area 40 and the outer periphery 44A of the quiet zone.

  This scan line 48 is scanned. That is, the pixel values of the image data developed on the memory are acquired in order. If the scan line 48 is composed of white pixels, it can be determined that there is a quiet zone around the candidate area 40. That is, it has a QR code feature that there is a quiet zone around the symbol, and the possibility that a symbol exists in the candidate area 40 is very high.

The scan line 48 can be set along the center line of the quiet zone, for example. That is, the scan line 48 can be set at an intermediate position between the outer periphery 40A and the outer periphery 44A. When the scan line 48 is set around the four sides of the candidate area 40 along the center line, the shape of the area surrounded by the scan line 48 is the same square as the candidate area 40. The reference of the scan line 48 is the points A _S , B _S , C _S on the extension line extending from the center point E of the candidate area 40 in the direction of the center points A, B, C, and the points A _S , B _S. , C _S is a point D _S that forms a vertex of a square. The coordinates of the point D _S are calculated from the coordinates of the points A _S , B _S and C _S.

  FIG. 12 is a diagram illustrating an example in which it is determined that a quiet zone exists. In this case, it is determined that the center points A, B, and C constitute each vertex of the right-angled isosceles triangle 46, and a scan line 48 is set around the candidate area assumed from the coordinates of the center points A, B, and C. However, since the scan line 48 is composed of white pixels, it is determined that a quiet zone exists around the candidate area.

  On the other hand, FIG. 13 is a diagram illustrating an example in which it is determined that a quiet zone does not exist even though it is determined that the center points A, B, and C constitute each vertex of the right-angled isosceles triangle 46. As described above, the center points A, B, and C may form the vertices of the right-angled isosceles triangle 46 even if the center points A, B, and C do not all belong to the same symbol. In this case, when the scan line 48 is set around the candidate area assumed from the coordinates of the center points A, B, and C, the scan line 48 is composed of white pixels and black pixels. It is determined that there is no quiet zone around.

  FIG. 14 is a flowchart illustrating a routine for determining whether or not there is a blank area (quiet zone). As described above, the point for determining whether or not there is a quiet zone is in the method for determining the position of the scan line. The coordinates of the reference point of the scan line are calculated from the coordinates of the center points A, B, and C.

First, in step 500, the coordinates of the midpoint E of the line segment BC connecting the points B and C are calculated (see FIG. 18). Point E is the midpoint of the long sides of the right-angled isosceles triangle when point A is a right angle apex. The point E is the center point of the candidate area 40, and is also the center point of the QR code when a symbol exists in the candidate area 40. If the coordinates of the point B are (x _b , y _b ) and the coordinates of the point C are (x _c , y _c ), the coordinates (x _e , y _e ) of the point E are expressed by the following equations.

Next, in steps 502 to 506, the coordinates of the reference points A _S , B _S , and C _S of the scan line are calculated. First, in step 502, the coordinates of the reference point A _S are calculated from the coordinates of the point A, in step 504, the coordinates of the reference point B _S are calculated from the coordinates of the point B, and in step 506, the coordinates of the reference point A _S are calculated. The coordinates of the point C _S are calculated. Details of the calculation method will be described later. Then, in step 508, the coordinates of the reference point D _S that is point-symmetric with the reference point A _S around the point E are calculated. The coordinates of the point D _S can be obtained by the following vector calculation. As a result, scan lines connecting the reference points A _S , B _S , C _S and D _S are set.

Next, in step 510, the scan line is scanned. For example, scanning in the order of the reference point A _S → reference point B _S → reference point D _S → reference point C _S → reference point A _S. In the next step 512, the total number of pixels N on the scan line, the number of white pixels W, and the ratio W / N of the number of white pixels to the total number of pixels are calculated. In subsequent step 514, referring to “threshold value TH” preset in the memory of CPU 14, is the ratio W / N of the number of white pixels to the calculated total number of pixels larger than “threshold value TH”? Judge whether or not.

  If the determination in step 514 is affirmative (OK), it is determined that a quiet zone exists around the candidate area (True), and the routine is terminated. On the other hand, in the case of negative determination (NG), it is determined that there is no quiet zone around the candidate area (False), and the routine is terminated.

Figure 15 is a diagram showing the positional relationship between the reference point A _S of the center point A and the scan line position detection pattern. As shown in FIG. 15, a line segment EA connecting the center point E of the QR code and the center point A of the position detection element pattern 42A is extended to the outer periphery 44A of the quiet zone outside the QR code. This extension passes through the apex A _p of the position detection element patterns 42A, intersects the scan line 48 at the reference point A _S. Looking at the pixel value on the extension line, it is black at the center point A, but then it is inverted to white and then inverted to black. Then, at the apex A _p of the position detection element patterns 42A, inverted to white again.

  FIG. 16 is a diagram illustrating the structure of the position detection element pattern. The structure of the position detection element pattern is defined by the JIS standard, and as shown in the figure, it is a shape in which three concentric squares are overlapped. The black 7 × 7 module 50, the white 5 × 5 module 52, and the black The 3 × 3 module 54 is used. The ratio of each module width is 1: 1: 3: 1: 1.

Assuming that the module size is 1, the length of the line segment AA _p is expressed as 3.5 as shown in FIG. The module size is the minimum width of a monochrome element when drawing a QR code. The width W _{q of the} quiet zone is defined by 4 module sizes and JIS standards. When the scan line 48 is set along the center line of the quiet zone, the length of the line segment A _S A _p is expressed as 2. In other words, the position of the reference point A _{S is} a position obtained by extending the line segment AA _p having a length of 3.5 by the length 2. The vector notation is as shown in FIG. Therefore, the coordinates of the reference point A _S can be obtained by the following vector calculation. Further, the coordinates of the reference point B _S and the reference point C _S can be obtained in the same manner.

  As described above, in the present embodiment, in addition to the condition that the center points of the selected three position detection element patterns form the vertices of a right-angled isosceles triangle, it is assumed from the coordinates of the three center points. If the condition that there is a quiet zone around the candidate area is satisfied, it is determined that the position detection element patterns corresponding to the three selected coordinates are included in the same symbol and constitute the position detection pattern. By combining the position detection element patterns included in the symbol, it is possible to prevent erroneous recognition as a QR code position detection pattern. Thereby, each QR code can be accurately detected from an image including a plurality of QR codes.

  Further, in the present embodiment, by adding the condition that there is a quiet zone around the candidate area, combinations of position detection element patterns (combinations of three coordinates) included in the same symbol are sequentially specified. There is no need to repeat the calculation endlessly, the QR code detection process is simplified, and the time until all combinations are specified is shortened. Thereby, it is possible to accurately and quickly detect individual QR codes from an image including a plurality of QR codes.

  In the first embodiment, when the presence / absence of a quiet zone is determined, the “threshold value TH” for evaluating the ratio W / N of the number of white pixels to the calculated total number of pixels is set in advance. Although the example using the value has been described, the threshold value can also be dynamically set according to the symbol size of the QR code read from the document image.

  In the JIS standard, as the QR code model number increases, the area of the QR code increases, so the scan line for determining the presence or absence of a quiet zone also increases accordingly. As the scan line becomes longer, the possibility of noise on the scan line increases. In this case, by setting the “threshold value TH” small, it is possible to accurately determine whether there is a quiet zone even if there is some noise.

For example, the value of “threshold value TH” is determined based on the value R obtained by converting the distance from the coordinate of the center point E of the QR code to the coordinate of the center point A of the position detection element pattern by the number of modules. FIG. 19 is a conceptual diagram for explaining a method of calculating the conversion value R. The distance L1 from the coordinate of the center point E of the QR code to the coordinates of the center point A of the position detection element patterns 42A, and the distance L2 from the center point A of the position detection element patterns 42A to the apex A _p of the position detection element patterns 42A Are calculated respectively. Note that the values of the distance L1 and the distance L2 are values converted by the number of modules (= number of pixels). The value of the distance L2 corresponds to 3.5 modules. Therefore, the number R of modules corresponding to the distance L1 can be obtained from the following equation.

  The threshold value TH can be obtained from the following calculation formula based on the converted value R. A and B are constants. By obtaining the threshold value TH according to this calculation formula, it is possible to set the optimum threshold value TH according to the QR code model number.

In the first embodiment, the example in which the scan lines are set around the four sides of the candidate area has been described. However, as shown in FIG. 20, the scan connecting the reference point Cs, the reference point As, and the reference point Bs. By setting the line 48 at least on the short side of the isosceles right triangle with respect to the candidate region 40, it is possible to determine whether or not there is a quiet zone. In this case, it is not necessary to calculate the coordinates of the reference point D _S shown in FIG. 18, and the setting of the scan line is facilitated. In addition, since the scan line becomes shorter, it is less susceptible to noise.

  In the first embodiment, the example in which the presence / absence of the quiet zone is determined using the scan line has been described. However, as illustrated in FIG. It is also possible to determine whether or not there is a quiet zone by scanning the scan area 78.

  In the first embodiment, the example in which the determination process for the presence / absence of the quiet zone is performed after the determination process for the right isosceles triangle has been described. However, the determination process for the presence / absence of the quiet zone is performed by changing the processing order. After that, a determination process of a right isosceles triangle can be performed.

  Furthermore, in the first embodiment, an example in which a combination of three position detection element patterns determined to constitute a position detection pattern (a combination of three coordinates) is stored in the memory has been described. As shown in FIG. 5, instead of storing the combination of the three coordinates in the memory (step 212 in FIG. 5), in step 211, the combination of the three coordinates is managed separately by storing it in the memory, and step 213 is performed. Thus, the routine may be changed so that the three coordinates stored in the memory are deleted from the first list. By adopting such a processing procedure, the number of determinations can be reduced, the amount of processing can be reduced, and the processing time can be shortened. Since steps other than step 211 and step 213 are the same as the processing procedure shown in FIG. 5, the same procedure is denoted by the same reference numeral and description thereof is omitted.

(Second Embodiment)
In the second embodiment, the coordinates of the center point of the position detection element pattern are detected, and the coordinates of the center point are managed by a method different from the first embodiment in which the position detection element pattern is managed in a list. FIG. 23 is a flowchart showing a subroutine of the combination detection process. This subroutine is executed in step 106 of the routine shown in FIG. The other points are the same as the processing procedure according to the first embodiment.

  The combination detection process shown in FIG. 23 is executed after all the coordinates of the center point of the position detection element pattern are detected and listed. Since one QR code symbol includes three position detection element patterns, when there are N QR codes, the coordinates of the center point of 3N position detection element patterns are listed. . At the time of listing, all coordinate values are set to be valid.

  First, in step 600, the coordinate list of the center point held in the memory 12 is referred to. Next, the center points of the three position detection element patterns constituting the position detection pattern are set as A, B, and C, and 3 from the coordinate list corresponding to the center points A, B, and C in steps 602 to 612. Select a combination of coordinates.

  In step 602, a coordinate corresponding to the center point A is selected from the coordinate list, and in step 604, it is determined whether or not the selected coordinate is valid. In the case of negative determination (False), that is, when the selected coordinate is invalid, the process proceeds to Step 622 to select a valid coordinate from the coordinate list and replace the coordinate data corresponding to the center point A. If the determination is affirmative (True), that is, if the selected coordinates are valid, the process proceeds to the next step 606.

  Next, in step 606, a coordinate corresponding to the center point B is selected from the coordinate list, and in step 608, it is determined whether or not the selected coordinate is valid. In the case of negative determination (False), that is, when the selected coordinate is invalid, the process proceeds to step 624 to select a valid coordinate from the coordinate list and replace the coordinate data corresponding to the center point B. If the determination is affirmative (True), that is, if the selected coordinates are valid, the process proceeds to the next step 610.

  Next, in step 610, a coordinate corresponding to the center point C is selected from the coordinate list, and in step 612, it is determined whether or not the selected coordinate is valid. In the case of a negative determination (False), that is, when the selected coordinate is invalid, the process proceeds to step 626 to select a valid coordinate from the coordinate list and replace the coordinate data corresponding to the center point C. If the determination is affirmative (True), that is, if the selected coordinates are valid, the process proceeds to the next step 614.

  Next, in step 614, a right isosceles triangle determination process is executed. The determination process of the right isosceles triangle is executed according to the routine shown in FIG. Here, in the case of an affirmative determination (True), the center points A, B, and C constitute vertices of a right isosceles triangle, and three position detection element patterns may be included in the same symbol. Proceeding to next step 616, the process for determining whether or not there is a quiet zone is executed. The process for determining whether there is a quiet zone is executed according to the routine shown in FIG.

  If the determination in step 616 is affirmative (True), in step 618, the selected combination of three coordinates is listed as a coordinate group representing the position of the position detection pattern and stored in the memory 12. That is, it is determined that the position detection element patterns corresponding to the three selected coordinates are included in the same symbol and constitute the position detection pattern, and the combination of the three selected coordinates is stored in the memory 12.

  Next, in step 620, the coordinate value stored in the coordinate list is set to be invalid. Since the position detection element pattern corresponding to the selected three coordinates has already been determined to form a position detection pattern, it is impossible to form the coordinates of the center point of the position detection pattern of another QR code. . For this reason, it can be set that the value of the selected three coordinates is invalid.

  Next, in step 622, it is verified whether all combinations have been selected. If all combinations have been selected, the routine is terminated. On the other hand, if there is a combination that has not been selected, the process returns to step 602 to select a different combination of three coordinates from the coordinate list in correspondence with the center points A, B, and C. Repeat the process of step 620.

  As described above, in the present embodiment, in addition to the condition that the center points of the selected three position detection element patterns form the vertices of a right-angled isosceles triangle, it is assumed from the coordinates of the three center points. If the condition that there is a quiet zone around the candidate area is satisfied, it is determined that the position detection element pattern corresponding to the three selected coordinates is included in the same symbol and constitutes the position detection pattern. As in the first embodiment, individual QR codes can be detected accurately and quickly from an image including a plurality of QR codes.

  In addition, the coordinate value of the center point determined to constitute the position detection pattern is set to be invalid and is not used for subsequent determinations, thereby reducing the number of determinations and reducing the processing amount. Processing time can be shortened.

  Since the processing of the first embodiment is simple, it is suitable for mounting on hardware (HW) or mounting on firmware such as DSP. On the other hand, the processing of the second embodiment is complex, but is suitable for mounting on software (SW) because the processing amount is reduced.

(Third embodiment)

  In the third embodiment, a combination of position detection element patterns is used by utilizing the feature that the ratio of black and white pixels is substantially equal in an area where a QR code symbol exists (hereinafter referred to as “QR code-likeness”). To detect. FIG. 24 is a flowchart showing a subroutine of the combination detection process. This subroutine is executed in step 106 of the routine shown in FIG. The other points are the same as the processing procedure according to the first embodiment.

  In this subroutine, as shown in FIG. 24, instead of the process of determining whether there is a quiet zone (step 210 in FIG. 5), the likelihood of a QR code is determined in step 209. Since the processing procedure other than step 209 is the same as the processing procedure shown in FIG. 5, the same procedure is denoted by the same reference numeral and description thereof is omitted.

  Here, the “QR-likeness determination process” executed in step 209 in FIG. 24 will be described in detail. 25 and 26 are diagrams for explaining a QR code-likeness determination method.

  As shown in FIG. 25, when the symbol 30 of the QR code exists, if the center points of the three position detection element patterns 32A, 32B, and 32C are a, b, and c, the points a, b, and c are respectively A region 35 surrounded by a square 33 serving as a vertex exists inside the symbol 30. FIG. 26 is a diagram in which this region 35 is cut out. As can be seen from FIGS. 25 and 26, in the region 35 surrounded by the square 33, the number of white pixels and the number of black pixels are substantially equal. That is, the ratio between the number of white pixels and the number of black pixels is approximately 1, and the difference between the number of white pixels and the number of black pixels is approximately 0. Also, the number of black and white inversions is relatively large.

  In the present embodiment, as shown in FIG. 27, the center points of the three position detection element patterns 42A, 42B, and 42C are A, B, and C, and the squares 43 have points A, B, and C as vertices. An enclosed area (candidate area) 40 is assumed. As a result of scanning the candidate area 40 and calculating the number of white pixels and the number of black pixels, if the ratio between the number of white pixels and the number of black pixels falls within a preset range, the candidate area 40 is displayed as a QR code. It can be determined that the image is unique. That is, it has a QR code feature that the ratio of black and white pixels is substantially equal in the area where the symbol exists, and the possibility that the candidate area 40 exists in the symbol is very high.

  Specifically, as shown in the following formula, when the difference between the number of white pixels and the number of black pixels becomes smaller than the “threshold value M”, it is determined that the image has QR code-likeness. In the formula, “threshold value M” is a constant representing a margin, and is set according to the symbol size of the QR code.

  On the other hand, FIG. 28 is a diagram showing an example in which it is determined that the center points A, B, and C constitute each vertex of a right-angled isosceles triangle but do not have the QR code-likeness. . In this way, even if the center points A, B, and C do not all belong to the same symbol, the center points A, B, and C may constitute vertices of a right-angled isosceles triangle. In this case, in the candidate area 40 assumed from the coordinates of the center points A, B, and C, it is determined that the ratio of the number of white pixels is overwhelmingly large and does not have the QR code quality.

  FIG. 29 is a flowchart illustrating a routine of QR code likelihood determination processing. This routine is executed in step 209 of FIG. First, in step 700, the number of white pixels on the candidate area 40 is counted, and in the next step 702, the number of black pixels on the candidate area 40 is counted. In the subsequent step 704, the difference between the number of white pixels and the number of black pixels is obtained, and it is determined whether or not the difference is smaller than the “threshold value M”. If the determination is affirmative (YES), it is determined that the candidate area 40 has a QR code quality (True), and the routine is terminated. On the other hand, in the case of negative determination (NO), it is determined that the candidate area 40 does not have the QR code-likeness (False), and the routine is ended.

  As described above, in the present embodiment, in addition to the condition that the center points of the selected three position detection element patterns constitute the vertices of a right isosceles triangle, it is assumed from the coordinates of the three center points. Since the position detection element pattern corresponding to the selected three coordinates is included in the same symbol, and it is determined that the position detection pattern constitutes a position detection pattern. Similar to the first embodiment, each QR code can be detected accurately and quickly from an image including a plurality of QR codes.

  In the third embodiment, the example in which “monochrome pixel ratio” is used as a numerical index representing “QR code likeness” has been described. However, as shown in FIG. The “number of black and white inversions” when scanned in the vertical direction (indicated by an arrow A) or in the vertical direction (indicated by an arrow B) can also be used as a numerical index representing “likeness of QR code”. Further, both “the ratio of black and white pixels” and “the number of times of black and white inversion” can be used.

  FIG. 30 is a flowchart showing another routine of QR code-likeness determination processing. This routine is executed in step 209 of FIG. First, in step 800, the number of black and white inversions (the number of times the pixel value changes from white to black) when the candidate area 40 is scanned in the horizontal direction is counted, and in step 802, the candidate area 40 is scanned in the horizontal direction. In this case, the black / white inversion count (the number of times the pixel value changes from black to white) is counted. In step 804, the number of black / white inversions when the candidate area 40 is scanned in the vertical direction is counted, and in step 806, the number of black / white inversions in the case where the candidate area 40 is scanned in the vertical direction is counted.

  FIG. 31 is a diagram illustrating an example of counting the number of black and white inversions when scanning in the horizontal direction. In this example, the black-and-white inversion count is 3 and the black-and-white inversion count is 3.

  Next, in step 808, a total value (sum) of the four inversion numbers obtained in steps 800 to 806 is obtained, and it is determined whether or not the sum is greater than a preset “threshold value TH”. If the determination is affirmative (YES), it is determined that the candidate area 40 has a QR code quality (True), and the routine is terminated. On the other hand, in the case of negative determination (NO), it is determined that the candidate area 40 does not have the QR code-likeness (False), and the routine is ended.

  In the third embodiment, an example in which a QR code-likeness determination process is performed after a right-angled isosceles triangle determination process has been described. However, after the QR code-likeness determination process is changed, the processing order is changed. It is also possible to perform determination processing of a right isosceles triangle.

  In the third embodiment, an example in which the QR code-likeness determination process is performed in the “combination detection process” has been described. However, a quiet zone presence / absence determination process can be performed together with the QR code-likeness determination process. . Combining multiple conditions improves QR code detection accuracy.

It is a block diagram which shows schematic structure of the processing apparatus of QR Code which concerns on the 1st Embodiment of this invention. It is a flowchart which shows the process routine performed by CPU. It is the schematic which shows the structure of QR Code. It is the figure which combined the position detection element pattern contained in a different symbol. It is a flowchart which shows the subroutine of a combination detection process. It is a figure for demonstrating the geometrical establishment conditions of a right-angled isosceles triangle. It is a flowchart which shows the routine of the determination process of a right-angled isosceles triangle. It is a flowchart which shows the routine of the determination process of a right angle apex. It is a figure for demonstrating the determination method of QR code likeness. It is a figure which shows the structure of the symbol of QR Code. It is a figure for demonstrating the determination method of the presence or absence of a quiet zone. It is a figure which shows the example determined with a quiet zone existing. It is a figure which shows the example determined with a quiet zone not existing. It is a flowchart which shows the routine of the determination process of the quiet zone presence / absence. Is a diagram showing the positional relationship between the reference point A _S of the center point A and the scan line position detection pattern. It is a figure which shows the structure of a position detection element pattern. It is a vector diagram for _obtaining the coordinates of the reference point A _S. It is a figure for demonstrating the determination method of the presence or absence of a quiet zone. It is a conceptual diagram for demonstrating the calculation method of the conversion value R. FIG. It is a figure which shows the other example of a setting of a scan line. It is a figure which shows the example of a setting of a scanning area | region. It is a flowchart which shows the other routine of a combination detection process. It is a flowchart which shows the subroutine of the combination detection process which concerns on the 2nd Embodiment of this invention. It is a flowchart which shows the subroutine of the combination detection process which concerns on the 3rd Embodiment of this invention. It is a figure for demonstrating the determination method of QR code likeness. It is a figure for demonstrating the determination method of QR code likeness. It is a figure which shows the determination area | region of QR code likelihood. It is a figure which shows the example determined not to have QR Code likeness. It is a flowchart which shows the routine of a QR code-likeness determination process. It is a flowchart which shows the other routine of a QR code-likeness determination process. It is a figure which shows the example of a count of black-and-white inversion frequency.

Explanation of symbols

10 Image Input Device 12 Memory 14 CPU
16 ROM
18 External interface 20 Image output device 22 Database 22 Image output device 24 Data bus 30 Symbol 32A, 32B, 32C Position detection element pattern 33 Square 34 Quiet zone 34A Perimeter 35 Area 36 Right-angled isosceles triangle 38 Scan line 40 Candidate area 40A Perimeter 42A , 42B, 42C Position detection element pattern 43 Square 44A Perimeter 46 Right-angled isosceles triangle 48 Scan line 50 Module 52 Module 54 Module 78 Scan area

Claims (17)

A two-dimensional code detection method for detecting a two-dimensional code in which three position detection element patterns are provided at positions corresponding to respective vertices of a right-angled isosceles triangle and a data area is provided in an area determined by the position detection element pattern Because
Read an image containing the two-dimensional code,
Binarize the scanned image,
A plurality of position detection element patterns included in the binarized image are detected,
Specify the position of the center point of the detected position detection element pattern,
From the center points whose positions are specified, select the three center points that form the vertices of a right isosceles triangle,
Extract a feature as a two-dimensional code from a two-dimensional code area determined by the position detection element pattern corresponding to the selected center point or its peripheral area,
When a feature as a two-dimensional code is extracted, it is determined that one two-dimensional code exists in the two-dimensional code region,
A two-dimensional code detection method for detecting a two-dimensional code.   The method for detecting a two-dimensional code according to claim 1, wherein a pre-standardized blank area existing in the peripheral area is extracted as the feature.   The two-dimensional code detection method according to claim 2, wherein the blank area is adjacent to at least a short side of the right isosceles triangle of the two-dimensional code area.   A virtual line that is spaced a predetermined distance from the outer periphery of the two-dimensional code region is set on the short side of the right-angled isosceles triangle of the two-dimensional code region, and the ratio of the number of white pixels to the total number of pixels on the virtual line is set. The method for detecting a two-dimensional code according to claim 3, wherein when the threshold value is exceeded, it is determined that a blank area exists.   A virtual region within a predetermined distance from the outer periphery of the two-dimensional code region is set on the short side of the right-angled isosceles triangle of the two-dimensional code region, and the ratio of the number of white pixels to the total number of pixels of the virtual region is set. The method for detecting a two-dimensional code according to claim 3, wherein when the threshold value is exceeded, it is determined that a blank area exists.   The two-dimensional code detection method according to claim 2, wherein the blank area exists in four directions around the two-dimensional code area.   When a virtual line spaced apart from the outer periphery of the two-dimensional code region by a predetermined distance is set around the two-dimensional code region, and the ratio of the number of white pixels to the total number of pixels on the virtual line exceeds a threshold value The two-dimensional code detection method according to claim 6, wherein it is determined that a blank area exists.   When a virtual region within a predetermined distance from the outer periphery of the two-dimensional code region is set on all four sides of the two-dimensional code region, and the ratio of the number of white pixels to the total number of pixels in the virtual region exceeds a threshold value The two-dimensional code detection method according to claim 6, wherein it is determined that a blank area exists.   The method of detecting a two-dimensional code according to any one of claims 4, 5, 7, and 8, wherein the threshold value is determined according to a symbol size of the two-dimensional code.   The method of detecting a two-dimensional code according to claim 1, wherein a ratio or difference between the number of white pixels and the number of black pixels in the two-dimensional code area is extracted as the feature.   The two-dimensional code detection method according to claim 9, wherein the number of white pixels and the number of black pixels are substantially equal in the two-dimensional code region.   The method for detecting a two-dimensional code according to claim 1, wherein a feature that the number of times of black and white inversion when the two-dimensional code region is scanned in a predetermined direction is within a predetermined range is extracted. When the binarized image includes a plurality of two-dimensional codes,
Further, from among the center points whose positions are specified, select three center points that form vertices of a right isosceles triangle and have a combination different from the three center points,
Extracting features as a two-dimensional code from the two-dimensional code area determined by the position detection element pattern corresponding to the selected center point and its peripheral area,
When a feature as a two-dimensional code is extracted, it is determined that one two-dimensional code exists in the two-dimensional code region,
The two-dimensional code detection method according to any one of claims 1 to 12, wherein a plurality of two-dimensional codes are sequentially detected. Two-dimensional code detection device for detecting a two-dimensional code in which three position detection element patterns are provided at positions corresponding to the vertices of a right isosceles triangle and a data area is provided in an area determined by the position detection element pattern Because
Image reading means for reading an image including the two-dimensional code;
Binarization means for binarizing the image read by the image reading means;
A reference position specifying means for detecting a position detection element pattern of a two-dimensional code included in the image binarized by the binarization means and specifying the position of the center point of the detected position detection element pattern;
Two-dimensionality determined by a position detection element pattern corresponding to the selected center point by selecting three center points constituting the vertices of a right isosceles triangle from the center points whose positions are specified by the reference position specifying means A feature extraction means for extracting features as a two-dimensional code from the code region and its peripheral region;
A determination unit that determines that one two-dimensional code exists in the two-dimensional code region when a feature as a two-dimensional code is extracted by the feature extraction unit;
A two-dimensional code detection device comprising:   15. A two-dimensional code reading device further comprising decoding means for decoding the two-dimensional code detected by the detection device according to claim 14.   Before the decoding of the two-dimensional code by the decoding means, further comprising a position correcting means for correcting the rotational position of the two-dimensional code so that the pixel arrangement direction of the two-dimensional code is parallel or orthogonal to the scanning direction. The two-dimensional code reader according to claim 15. A two-dimensional code for detecting a two-dimensional code in which three position detection element patterns are provided at positions corresponding to the vertices of a right isosceles triangle and a data area is provided in an area determined by the position detection element pattern by a computer Detection program,
A plurality of position detection element patterns included in the binarized image are detected,
Specify the position of the center point of the detected position detection element pattern,
From the center points whose positions are specified, select the three center points that form the vertices of a right isosceles triangle,
Extract a feature as a two-dimensional code from a two-dimensional code area determined by the position detection element pattern corresponding to the selected center point or its peripheral area,
When a feature as a two-dimensional code is extracted, it is determined that one two-dimensional code exists in the two-dimensional code region,
A two-dimensional code detection program for detecting a two-dimensional code.