Patent Publication Number: US-8534565-B2

Title: Two-dimensional optical identification device with same gray level for quick decoding and decoding method therefor

Description:
CROSS REFERENCE TO RELATED APPLICATION 
     This application claims the benefits of the Taiwan Patent Application Serial Number 100118251, filed on May 25, 2011, the subject matter of which is incorporated herein by reference. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to the technical field of two-dimensional optical identification and, more particularly, to a two-dimensional optical identification device with same gray level for quick decoding and decoding method therefor. 
     2. Description of Related Art 
     For increasing the convenience, fun, and efficiency of reading a document, a typical way embeds optical identification codes into pictures in which the optical identification codes are printed on the document. An external reader can thus read the optical identification code corresponding to a part of pictures, and activate an output device to, for example, play a voice based on the read optical identification code. Thus, the played voice can effectively help the reading. However, such a technique has to embed the optical identification code into the pictures of the document, which certainly causes the complexity of making a document and affects the picture display. Therefore, it is desired to accurately read the optical identification code without being affected by the pictures. 
     In the known patents, U.S. Pat. No. 7,530,496 granted to Chen for a “Surface sensitive input device with indexes and computer system using the input device” discloses a layer of points corresponding to an optical identification code added onto a raw image, as show in  FIG. 1 . The optical identification code  100  of  FIG. 1  has a plurality of indexing points in an isotropic arrangement. The indexing points are tiny and thus invisible to human eyes. As shown in  FIG. 1 , such indexing points are arranged in an isotropic manner, each indexing point having a radius of about 100 μm. The indexing points include a center point  110 , a plurality of direction points  121  and  122 , a plurality of first data points  131 - 136 , and a plurality of second data points  1401 - 1412 . The direction point  122  is provided as a direction recognition point in blank or hollow, in which the hollow direction point  122  is used to represent no point printed. 
     Such an optical identification code  100  can present a different picture object which can be read by an optical reader for further processing. For example, different optical identification codes representing different picture objects correspond to different voices, respectively, and accordingly a corresponding voice can be played when the optical reader reads a picture object. 
     However, as shown in the optical identification code  100  of  FIG. 1 , the locations of the first data points  131 - 136  and the second data points  1401 - 1412  at the outer circle are determined by using the center point  110 , a direction point  121  and five direction points  122 . Since there is no auxiliary positioning point on the outer circle, it is possible to have a deformed picture taken by a slant lens, which further increases the difficulty of locating the data points. 
       FIG. 2  schematically illustrates another optical identification code  200 . The optical identification code  200  is comprised of one positioning block  201  and eight coded data blocks  202 - 209  arranged in a nine-square grid. Each center of the coded data blocks  202 - 209  is filled up and used as an auxiliary positioning point to thereby avoid the difficulty on locating the data points due to lack of auxiliary positioning point on the outer. The positioning block  201  has five points filled up and used as major positioning points to reduce the difficulty of locating the data points. However, the major positioning points of the block  201  are obvious to see, in which users can easily sense a texture when the optical identification codes  200  repeatedly present on the surface of a picture. In addition, the auxiliary positioning points and data points contained in the coded data blocks  202 - 209  can cause a non-uniform distribution of the data points, resulting in producing the effect of non-uniform gray level. 
       FIG. 3  schematically illustrates another optical identification code  300 . The optical identification code  300  is comprised of a content part  310  and a position part  320 . The content part  310  has nine coded data blocks, and the position part  320  has seven positioning blocks. The position part  320  is arranged at two adjacent sides of the content part  310 . In this case, in order to improve the equality effect of gray level, all positioning points are arranged at the outer with a shifted point  321  to indicate the direction information. However, for the same gray level, all data points  311  are placed in proximity to an intersection of virtual lines  313  and  315 , with a small offset. In addition, a desired pitch between pictures is added in the coded data blocks. Thus, the amount of coded data is relatively small when the optical identification code is shrunk. In contrast, the patterns are not in the same gray level due to the smaller pitch produced when the amount of coded data is increased, as well as the decoding difficulty is increased. 
     Therefore, it is desirable to provide an improved optical identification device and decoding method to mitigate and/or obviate the aforementioned problems. 
     SUMMARY OF THE INVENTION 
     The object of the present invention is to provide a two-dimensional optical identification device with same gray level for quick decoding and decoding method therefor, which can improve the equality effect of gray level and allow printing larger points to reduce the print requirement, so as to increase the recognition accuracy on reading a slant code thereby increasing the decoding speed. 
     In accordance with one aspect of the invention, there is provided a two-dimensional optical identification device with same gray level for quick decoding, on which at least one two-dimensional optical identification code with same gray level is arranged. The two-dimensional optical identification code comprises: a first positioning block having a plurality of first positioning points; a plurality of data blocks placed around the first positioning block, each of the data blocks having a plurality of defined patterns, each defined pattern being selectively positioned in one of a plurality of virtual areas produced by equally dividing the data block; and a second positioning block having a plurality of second positioning points placed at two adjacent boundaries of the plurality of data blocks for defining positions of the plurality of data blocks, wherein one of the second positioning points is defined as a second direction identification point which indicates an identification direction of the two-dimensional optical identification code. 
     In accordance with another aspect of the invention, there is provided a decoding method for quickly decoding two-dimensional optical identification code with same gray level, the two-dimensional optical identification code including a first positioning block, a plurality of data blocks, and a second positioning block, the first positioning block having a plurality of first positioning points, the plurality of data blocks being placed around the first positioning block, each of the data blocks having a plurality of defined patterns selectively positioned in one of a plurality of virtual areas produced by equally dividing the data block, the second positioning block having a plurality second positioning points and being placed at two adjacent boundaries of the plurality of data blocks for defining distributed locations of the data blocks. The method comprises the steps of: (A) finding the plurality of first positioning points of the first positioning block; (B) calculating the plurality of second positioning points of the second positioning block based on the plurality of first positioning points; (C) recognizing a second direction identification point among the plurality of second positioning points; (D) determining an identification direction of the optical identification code with same gray level, and storing coordinates of the first and second positioning points; (E) finding any first positioning block that includes the first positioning points; (F) searching for a plurality of data blocks on the first positioning block found in step (E), so as to find an area with complete plurality of data blocks and corresponding first positioning block; (G) calculating offsets of defined patterns of the complete plurality of data blocks in the area found in step (F); (H) regarding the corresponding first positioning block as illegal when an offset is greater than a threshold; and (I) outputting data corresponding to a smallest offset of the defined patterns when the offsets of the defined patterns are smaller than or equal to the threshold. 
     Other objects, advantages, and novel features of the invention will become more apparent from the following detailed description when taken in conjunction with the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  schematically illustrates a typical optical identification code; 
         FIG. 2  schematically illustrates another typical optical identification code; 
         FIG. 3  schematically illustrates still another typical optical identification code; 
         FIG. 4  schematically illustrates a two-dimensional optical identification device with same gray level for quick decoding in accordance with an embodiment of the invention; 
         FIG. 5  schematically illustrates a two-dimensional optical identifier in a same gray level in accordance with an embodiment of the invention; 
         FIG. 6  schematically illustrates an enlarged data block in accordance with an embodiment of the invention; 
         FIG. 7  schematically illustrates coded data blocks in accordance with an embodiment of the invention; 
         FIG. 8  is a flowchart of a decoding method applied to two-dimensional optical identification code with same gray level for quick decoding in accordance with an embodiment of the invention; and 
         FIG. 9  schematically illustrates a picture with two-dimensional optical identification code with same gray level in accordance with the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       FIG. 4  schematically illustrates a two-dimensional optical identification device with same gray level for quick decoding in accordance with an embodiment of the invention. As shown in  FIG. 4 , the device  400  is partitioned into a plurality of areas, such as  410 ,  411 ,  434 , and the like, each having the same size and having a plurality of two-dimensional optical identification codes  500  with same gray level to represent a corresponding value. For example, the optical identifications  501  and  502  represent values of areas  410  and  411  respectively. The device  400  includes two picture objects  450  and  460 , where the object  450  covers areas  410 ,  411 ,  412 ,  420 ,  421 ,  422 , and the object  460  covers areas  413 ,  414 ,  423 ,  424 ,  433 ,  434 . 
       FIG. 5  schematically shows a two-dimensional optical identification code  500  with same gray level in accordance with an embodiment of the invention. The two-dimensional optical identification code  500  includes a first positioning block  510 , a plurality of data blocks  520 , and a second positioning block  530 . 
     The first positioning block  510  has a plurality of first positioning points  511 ,  512  for quickly detecting the patterns of the two-dimensional optical identification code  500 . 
     The data blocks  520  are placed around the first positioning block  510 . Each of the data blocks  520  has a plurality of defined patterns selectively located in one of virtual areas produced by equally dividing the data block  520 . 
     The second positioning block  530  has a plurality of second positioning points  531 ,  532  placed at two adjacent boundaries  591 ,  592  of the data blocks for defining the positions of the data blocks. 
     In this embodiment, the number of first positioning points  511 ,  512  is five, but not limited to it. For example, in other embodiments, it can be three or four points. One of the second positioning points  531 , 532  is defined as a second direction identification point  531  to indicate the identification direction of the two-dimensional optical identification code  500 . 
     As shown in  FIG. 5 , the first positioning block  510  includes five first positioning points  511 ,  512 , wherein four first positioning points  511  are distributed on four corners of a virtual square (i.e., formed with the four first positioning points  511 ) while the other first positioning point  512  is located at the center of the virtual square. 
     In addition, the second positioning block  520  includes N second positioning points  532  and the second direction identification point  531 . The N second positioning points  532  form an L shape, and the second direction identification point  531  is located on a position with a first offset d from the intersection of two lines of the L shape, where N is a positive integer and, in this embodiment, N=8. 
     In the N second positioning points, I second positioning points are used to define I first-direction virtual lines  533 , and J second positioning points are used to define J second-direction virtual lines  534 . The I first-direction virtual lines  533  are vertical to the J second-direction virtual lines  534 . The center of each data block  520  is located at the intersection of a first-direction virtual line  533  and a second-direction virtual line  534 , where I, J are positive integers, and I+J=N. In this embodiment, when N=8, I=4 and J=4. In other embodiments, N may be 9 so as to have I=5 and J=4, and so on, which can be easily achieved by those skilled in the art, and thus a detailed description is deemed unnecessary. 
     As shown in  FIG. 5 , each data block  520  is partitioned into a plurality of virtual areas  521  by a first-direction virtual line  533  and a second-direction virtual line  534 .  FIG. 6  schematically illustrates an enlarged data block  520  in accordance with an embodiment of the invention. In this embodiment, the number of virtual areas  521  is four. 
     Each data block  520  has four defined patterns  522  respectively located in the four virtual areas  521 . In each data block  520 , only one of the four defined patterns  522  is filled up to thereby indicate a two-bit binary code including 00, 01, 10, and 11. The defined pattern can be a circle and/or square. 
       FIG. 7  schematically illustrates the coded data blocks in accordance with an embodiment of the invention. When the defined pattern  522  of the virtual area  521  on the upper left corner of a data block  520  is filled up, it indicates a two-bit binary code of 00. When the defined pattern  522  of the virtual area  521  on the upper right corner of a data block  520  is filled up, it indicates a two-bit binary code of 01. When the defined pattern  522  of the virtual area  521  on the lower right corner of a data block  520  is filled up, it indicates a two-bit binary code of 10. When the defined pattern  522  of the virtual area  521  on the lower left corner of a data block  520  is filled up, it indicates a two-bit binary code of 11. 
       FIG. 8  is the flowchart for a decoding method for quickly decoding two-dimensional optical identification code with same gray level in accordance with an embodiment of the invention. As cited above, the two-dimensional optical identification code  500  has a first positioning block  510 , a plurality of data blocks  520 , and a second positioning block  530 . The first positioning block  510  has a plurality of first positioning points  511 ,  512  for providing the patterns of the two-dimensional optical identification code. The plurality of data blocks  520  are placed around the first positioning block  510 . Each of the data blocks  520  has a plurality of defined patterns  522 . Each defined pattern  522  is selectively positioned in one of virtual areas  521  produced by equally dividing the data block  520 . The second positioning block  530  has a plurality of second positioning points  531 ,  532  placed at two adjacent boundaries  591 ,  592  of the data blocks  520  for defining the positions of the data blocks  520 . 
     The decoding method can use an optical reader to scan the two-dimensional optical identification device  400  to capture the picture of multiple two-dimensional optical identification codes  500  from the device  400 .  FIG. 9  schematically illustrates the picture of two-dimensional optical identification codes with same gray level in accordance with the invention. As shown in  FIG. 9 , in order to reduce the cost, the size of the picture captured by the optical reader is typically about four times the size of one two-dimensional optical identification code  500 . The captured picture is indicated by the dotted frame  910 . 
     With reference to  FIGS. 5 ,  8  and  9 , for a decoding operation, step (A) first finds the first positioning points of the first positioning block in the captured picture. Because of the distance between two of the first positioning points  511 ,  512  being fixed, the four first positioning points  511  being located on the four corners of a virtual square, and the first positioning point  512  being located on the center of the virtual square, it is applicable to use the size of frame  920  to capture pixels of the picture for determining whether the pixels in the frame  920  contain the first positioning points  511 ,  512 . When the pixels in the frame  920  do not contain the first positioning points  511 ,  512 , the frame  920  is shifted right one pixel each time for performing the determining operation. When being shifted to the rightmost side, the frame  920  is shifted to a pixel in a next row at the leftmost side for repeatedly performing the determining operation, until all pixels in the frame  910  are determined. Thus, in step (A), a plurality of first positioning points  511 ,  512  indicated by the oval  930  can be searched out. 
     In step (B), since the relative location between the first positioning block  510  and the second positioning block  530  is known, the second positioning points  531 ,  532  of the second positioning block  530  can be calculated based on the first positioning points  511 ,  512  in step (A). 
     Step (C) recognizes a second direction identification point  531  among the second positioning points  531 ,  532 . Only the second direction identification points  531  indicated by the oval  940  can be recognized in the captured picture of the frame  910  because other two-dimensional optical identification codes with same gray level are not located in the frame  910 . 
     Step (D) determines an identification direction of the optical identification code of the two-dimensional optical identification device with same gray level based on the second direction identification point  531 , and stores coordinates of the first positioning points  511 ,  512  and coordinates of the second positioning points  531 ,  532 . 
     Step (E) finds any first positioning block  510  that includes the first positioning points  511  stored in step (D). 
     Step (F) performs a searching operation for a plurality of data blocks on the first positioning block found in step (E), so as to find an area with complete data blocks  520  and corresponding first positioning block  510 . In this case, only the two-dimensional optical identification code  500  indicated by the oval  950  has the complete data blocks  520 . 
     Step (G) calculates offsets of the defined patterns  522  of the complete data blocks in the area found in step (F). 
     In step (H), since the defined patterns  522  are located near the intersections of the first and second direction virtual lines  533 ,  534 , it is regarded as inaccurate positioning if an offset is greater than a threshold, so that the corresponding first positioning block is regarded as illegal. 
     In step (I), a data corresponding to a smallest offset of the defined patterns is outputted when the offsets of the defined patterns are smaller than or equal to the threshold. 
     As cited, the two-dimensional optical identification code of the invention present has the essential positioning points  511 ,  512  located in the inner part, and the positioning points  511 ,  512  are not as obviousness as those in  FIG. 2 . In addition, the data points  522  and the positioning points  511 ,  512 ,  531 ,  532  are placed in different blocks for being separated by a blank. Accordingly, all code points (data and positioning points) in a frame are distributed in high uniformity, so as to significantly improve the equality effect of gray level. 
     The data points of the two-dimensional optical identification code  500  are embraced by the positioning points  511 ,  512  in the inner part and the positioning points  531 ,  532  in the outer part. An interpolation can be applied to the positioning points  511 ,  512  in the inner part and the positioning points  531 ,  532  in the outer part so as to find the positions of the data points  522 . Such an interpolation can increase the precision of data searching and the recognition accuracy on reading a slant code. 
     As compared with  FIG. 2 , the data points  522  and the positioning points  511 ,  512 ,  531 ,  532  in the invention are placed in different blocks in order to reduce the density of code points per area and allow the larger print points at the same area ratio, so as to reduce the print requirement. 
     The essential positioning patterns are located in the first positioning block  510  in the inner part and have significant features, so that they can be quickly found even the pitch between the code points becomes smaller or the code points are slant. Further, the found patterns in the inner are combined with the positioning points of the second positioning block  530  in the outer to thereby ensure whether the code pattern is desired. In contrast, the code pattern of  FIG. 3  contains the positioning pattern only in the outer part and is based on an offset of one code point  321  to determine the direction information only, resulting in increase of difficulty in positioning search. Namely, the prior art in  FIG. 3  places the positioning pattern in the outer part to overcome the equality problem of gray level, which causes the non-clear pattern feature and increases the difficulty of searching the positioning points when the code pitch is small and/or the slant angle is large, resulting in reducing the accuracy. 
     Therefore, the positioning points in the invention are placed in the inner part and outer part, and the feature of the positioning pattern in the inner part is significant without affecting the gray level. Even with a small code pitch and large slant angle, the decoding is effectively performed. Since the positioning pattern or patterns in the inner part is clear and can be obtained quickly from the code pattern, the decoding speed is increased. 
     Although the present invention has been explained in relation to its preferred embodiment, it is to be understood that many other possible modifications and variations can be made without departing from the spirit and scope of the invention as hereinafter claimed.