Abstract:
Described is a technology in which a two-dimensional barcode symbol (e.g., a QR Code®) is located within an image by looking for angular signatures that indicate a high density of generally vertical and/or horizontal angles. An image is divided into blocks of pixels. Angles are associated with each pixel, forming an angular signature for the block based on how many pixels are associated with each angle. The angular signatures indicate which blocks have pixels associated with mostly generally vertical and/or horizontal angles. A region with the largest number of blocks having such angular signatures is determined, and a bounding box for the barcode symbol grown from that region block by evaluating nearby blocks to find the outermost blocks that contain the barcode symbol.

Description:
BACKGROUND 
       [0001]    A QR Code® (ISO/IEC 18004) is a two-dimensional barcode format that is becoming increasingly popular in facilitating various consumer-oriented scenarios. One of the ways to use a QR Code® is with a camera-equipped mobile phone. 
         [0002]    However, current QR Code® decoding applications on mobile devices are limited in terms of localization, that is, the ability to automatically locate a QR Code® image within a larger container image. Localization is needed because it enables a QR Code® decoder to ignore background artifacts which could disrupt or slow down the performance of the decoding algorithm. 
         [0003]    Current QR Code® decoding applications typically attempt to implement localization by scanning specifically for the QR Code® position detection patterns (three small black boxes) located at the three corners of the symbol to determine a bounding box. However, this is not particularly effective, as it is highly sensitive to environmental conditions (especially lighting, noise, and blur) as well as algorithmic performance. 
         [0004]    The user can attempt to do the localization themselves by manually positioning the camera in such a way as to fill their preview screen entirely with the barcode image, typically within superimposed cross-hair graphics. This technique is error prone, and suffers from usability and/or accessibility issues. Moreover, manual localization is sometimes not possible, such as when the barcode is at a distance and the mobile phone lacks camera zoom functionality. 
       SUMMARY 
       [0005]    This Summary is provided to introduce a selection of representative concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used in any way that would limit the scope of the claimed subject matter. 
         [0006]    Briefly, various aspects of the subject matter described herein are directed towards a technology by which a barcode symbol (e.g., a QR Code®) is located within an image based on angular signatures corresponding to pixels that make up that QR code. In one aspect, an image is divided into blocks of pixels. Angles are associated with each pixel, and based on a count of the number of pixels in the block to which each angle corresponds, the block is given an angular signature. The angular signatures are then used to locate the barcode symbol. 
         [0007]    In one aspect, the angular signatures indicate which blocks have pixels associated with mostly generally vertical and/or horizontal angles. Those blocks are chosen as candidate blocks. The region (within a set of regions of the image) with the largest number of candidate blocks is selected, and a bounding box grown from that region block by block, by including those blocks having mostly generally vertical and/or horizontal angles within the bounding box, and excluding others. When grown, the bounding box identifies the location of the barcode symbol. 
         [0008]    Other advantages may become apparent from the following detailed description when taken in conjunction with the drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]    The present invention is illustrated by way of example and not limited in the accompanying figures in which like reference numerals indicate similar elements and in which: 
           [0010]      FIG. 1  is a block diagram showing an example computing device/environment into which various aspects of barcode localization may be implemented. 
           [0011]      FIG. 2  is a representation of determining an angle corresponding to a pixel for use in localization processing. 
           [0012]      FIG. 3  is a representation of normalizing an angle for use in localization processing. 
           [0013]      FIG. 4  is a representation of a histogram corresponding to an angular signature of a block showing pixel counts for each angle of a set of possible angles, 
           [0014]      FIG. 5  is a flow diagram representing example steps for use in localization processing of an image. 
           [0015]      FIG. 6  is a flow diagram representing example steps for determining candidate image blocks corresponding to possible barcode locations within sub-parts of the image. 
       
    
    
     DETAILED DESCRIPTION 
       [0016]    Various aspects of the technology described herein are generally directed towards locating a two-dimensional barcode symbol based on a signature gleaned from an angular distribution analysis of the distribution of the barcode symbol&#39;s pixels; the signature results from the block-like chunks that occur with high frequency within the symbol. While some of the examples described herein are directed towards a QR-code® barcode symbol, it is understood that these are only examples. For example, other symbols including other types of barcodes that have identifiable signatures may benefit from a similar location technique. As such, the present invention is not limited to any particular embodiments, aspects, concepts, structures, functionalities or examples described herein. Rather, any of the embodiments, aspects, concepts, structures, functionalities or examples described herein are non-limiting, and the present invention may be used various ways that provide benefits and advantages in computing and image processing in general. 
         [0017]    Turning to  FIG. 1 , there is shown a camera device  102  that via a camera program  104  captures an initial image  106  or the like to obtain a containing image  108  in device memory. The containing image includes a two-dimensional barcode  110 , comprising a QR Code® in this example. 
         [0018]    As described below, a localization application  112  (e.g., initiated by a device user) locates the two-dimensional barcode  110  within the containing image  108 . The result is barcode data  112 , e.g., in the form of a bounding box surrounding the barcode (which may be in the same memory location or copied to a different location) for use as needed by the user. 
         [0019]    As will be understood, the localization application  112  requires limited manual labor, as the user need only point their device in the general direction of a QR Code® for the system to locate it. The localization application  112  is robust in that it can reliably locate a QR Code® bounding box within a containing image that suffers from low lighting, image noise/visual artifacts, a skewed capture angle and or focal distortion/blurriness. Additionally, the performance is fast enough on contemporary mobile devices to be considered real-time with respect to consumer use. Thus, the technology described herein is reliable even in poor environmental conditions, yet is sufficiently lightweight to maintain high computational performance even for devices with limited hardware capabilities. 
         [0020]    In one implementation, various steps are performed, including angular distribution analysis. More particularly, instead of searching for the well-known position detection patterns, (the black blocks with surrounding squares located at the three corners of any QR Code® symbol), which is the basis of existing localization techniques, the localization application considers the entire QR Code® as a whole. That is, the application locates a QR Code® within a containing image by exploiting the fact that a QR Code®, in its entirety, has a somewhat unique signature when considering the angular distribution of its pixels; this is a result of the block-like chunks that occur with high frequency within the symbol. 
         [0021]    To perform the angular distribution analysis, as generally represented by step  502  (and sub-steps  503 - 505 ) of  FIG. 5 , the entire source image is divided into subset image blocks (step  503 ). In general, this reduces the locating problem into smaller problems that make the system more resilient to interference caused by visual artifacts and other environmental conditions. This works because when the smaller problems are solved, neighboring blocks that are determined to be likely parts of the QR Code® help to indicate the most likely position of the QR Code®. Note that the actual pixel size of the blocks is application-specific. 
         [0022]    For each image block, a pixel wise angular distribution is calculated (step  504 ). Note that the image is initially processed to detect edges. A suitable algorithm for this task is a convolution mask (such as Sobel) to evaluate the gradient of the axis X the axis Y of an image A, denoted as Gx and Gy, as shown in the Sobel Convolution Matrices below: 
         [0000]    
       
         
           
             
               G 
               x 
             
             = 
             
               
                 
                   [ 
                   
                     
                       
                         
                           + 
                           1 
                         
                       
                       
                         0 
                       
                       
                         
                           - 
                           1 
                         
                       
                     
                     
                       
                         
                           + 
                           2 
                         
                       
                       
                         0 
                       
                       
                         
                           - 
                           2 
                         
                       
                     
                     
                       
                         
                           + 
                           1 
                         
                       
                       
                         0 
                       
                       
                         
                           - 
                           1 
                         
                       
                     
                   
                   ] 
                 
                 * 
                 A 
                  
                 
                     
                 
                  
                 and 
                  
                 
                     
                 
                  
                 
                   G 
                   y 
                 
               
               = 
               
                 
                   [ 
                   
                     
                       
                         
                           + 
                           1 
                         
                       
                       
                         
                           + 
                           2 
                         
                       
                       
                         
                           + 
                           1 
                         
                       
                     
                     
                       
                         0 
                       
                       
                         0 
                       
                       
                         0 
                       
                     
                     
                       
                         
                           - 
                           1 
                         
                       
                       
                         
                           - 
                           2 
                         
                       
                       
                         
                           - 
                           1 
                         
                       
                     
                   
                   ] 
                 
                 * 
                 A 
               
             
           
         
       
     
         [0023]    The angle value of each pixel is derived using the following equation: 
         [0000]      Angle( x,y )=tan −1   GY/Gx    
         [0000]      FIG. 2  represents the angle computation, in which for each pixel at coordinate(x,y), Gx and Gy is evaluated first using the Sobel mask; from there, the angle of the pixel at that point is derived. After calculation, each angle is normalized over the range 0° to 180°. This is accomplished by treating the angle Z and Z+180° as the same value. The angle normalization result is represented in  FIG. 3 . 
         [0024]    In one implementation, an optimization is performed. More particularly, a fast method of storage and lookup of angular computation data is accomplished by reusing a temporary 8-bit image of the same dimensions as the source block, where each pixel is a byte that now holds a value corresponding to its derived angle (0° to 180°). 
         [0025]    An angular distribution representing a measuring block is generated by measuring (e.g., counting) the angle values that show up most often; this corresponds to the block&#39;s angular signature. In  FIG. 4 , such an example distribution is shown, generally in histogram form, with the x-axis representing the angles in degrees, and the y-axis representing the pixel count in an example image block. As the distribution indicates for this block, the two most common angles are 0° and 90°—this represents vertical and horizontal lines respectively, which are the most common features of a QR Code® symbol. The lesser common, but still prevalent, angles are 45° and 135°—these represents the corners that intersect the vertical and horizontal lines, thus completing the box-like graphics that constitute a QR Code® symbol. Note that  FIG. 4  is an ideal (or almost ideal) example for purposes of explanation; in actual images, where a barcode symbols if found, there are more counts than for just these four angles. 
         [0026]    With respect to angled images, various mechanisms may be used to account for users not holding the camera perfectly straight with respect to capturing the image. One mechanism is based on pre-processing the image using known techniques to straighten the image before attempting to locate the barcode symbol as described herein. Another mechanism, described herein, anticipates the possibility by evaluating counts at a range of angles near ninety degrees, e.g., whether the counts are high at an angle of ninety degrees plus or minus some adjustment number of degrees. As used herein, “generally” vertical and/or horizontal refers to any angles within such a range, including exactly vertical and exactly horizontal. Generally horizontal angles also may be considered, instead of or in addition to generally vertical angles. Another mechanism that may be used in addition to or instead of the above mechanisms is to look for peaks in angle counts that are separated by around 90° relative to one another rather than relative to a straight image; for example, if a user holds a camera at 15° degrees relative to a straight image, barcode symbols will have peaks around 15° degrees and 105° degrees. 
         [0027]    Many blocks may fit within the allowed distribution thresholds. The application thus determines candidate image blocks by comprising blocks that are likely part of a QR Code®. Note that this requires some further analysis because in real world images the angular distribution for a block will not be as cleanly-defined as represented in  FIG. 4 . 
         [0028]    In general, a similar angular distribution pattern holds for real world image blocks that are within or part of a QR Code®. Thus, the application needs to efficiently and reliably identify these candidate blocks, given a somewhat potentially fuzzy distribution pattern. To this end, the application performs an algorithm referred to as candidate block selection, as generally illustrated via the example sub-step  505  of  FIG. 5 , shown in more detail in the example steps of the flow diagram of  FIG. 6 . The algorithm works primarily by first obtaining the angular distribution of a block (step  602 ), and then using a quick sort to sort the distribution values (step  602 ). 
         [0029]    Once sorted, the algorithm selects the highest values (according to some threshold) and determines if they are within an acceptable range indicative of a QR Code® distribution. In the example of  FIG. 6 , the top ten angle counts are chosen via steps  608  and  612 . Via step  610 , these top counts are evaluated to determine whether enough of them are within positioned at the desired angle (e.g., 90°), within a general range (adj_val), e.g., generally vertical and/or horizontal. If so, the block is a candidate block (step  614 ), otherwise it is discarded (step  616 ). The intuition is that the highest values are representative of the entire block distribution, while at the same time avoiding noise. Using this algorithm thus maintains accuracy while running with high performance and efficiency. 
         [0030]    After obtaining a list of candidate blocks that may be part of a QR Code®, the process removes any false positives and determines the best possible candidate block within a region, as generally represented by step  507  of  FIG. 5 . In general, this is based on where the various candidate blocks are grouped together with other candidate blocks in the image; those with the tightest grouping correspond to the region that is most likely to contain the barcode symbol. 
         [0031]    To implement this step, the image is scanned with a logical cursor that is sized to be some multiple of the block size; (note that the actual size of the cursor is application-specific). The number of candidate blocks that are located within the cursor is tracked as the cursor moves throughout the image. After scanning the image, the cursor position that contained the most candidate blocks indicates the region that is most likely to contain the barcode symbol. 
         [0032]    Once the region with the most candidate blocks is discovered, the best candidate block is found by iterating through the candidate blocks in the region and determining which one has the closest angular distribution to the ideal case. 
         [0033]    After identifying the best candidate block, it is considered a seed, and used by a fast region grow algorithm to establish the approximate bounding box of the QR Code®. The algorithm works by evaluating the nearby blocks (the actual number of blocks is application-specific) in the directions directly above, below, left, and to the right of the current block. The evaluation at each block determines whether the angular distribution loosely (by some threshold) matches that of a QR Code® angular distribution. If so, this becomes the current block and the processing continues recursively. In this manner, the approximate bounding box is known, and the barcode symbol thus located. 
         [0034]    At this time, the barcode symbol&#39;s location is known, whereby it may be decoded or otherwise used by further processing. Note that as part of the decoding, the further processing can locate the QR Code® position detection patterns (three small black boxes) located at the three corners of the symbol to determine a bounding box, which were heretofore not needed in locating the QR Code® symbol itself. 
         [0035]    While the invention is susceptible to various modifications and alternative constructions, certain illustrated embodiments thereof are shown in the drawings and have been described above in detail. It should be understood, however, that there is no intention to limit the invention to the specific forms disclosed, but on the contrary, the intention is to cover all modifications, alternative constructions, and equivalents falling within the spirit and scope of the invention.