Abstract:
Architecture that guides the freeform drawing of objects by a user to enable the user to produce improved drawings without significant training. As the user draws, the architecture dynamically updates a relevant shadow image proximate (e.g., underlying) the user&#39;s strokes. The strokes overlay an evolving shadow image, which shadow image is suggestive of object contours that guide the user during the drawing process. Relevant edge images selected from a large database are automatically blended to construct the shadow image. As the user draws, the strokes are dynamically analyzed using an encoding of overlapping windows for fast matching with the database of images. A top ranked set of matching database edge images are aligned to the drawing, a set of spatially varying weights blend the edge images into the shadow image, and a scoring technique is employed to select the optimum shadow image for display.

Description:
BACKGROUND 
       [0001]    The huge volume of image and video data available on the networks (e.g., the Internet), scientific databases, and newspaper archives, along with recent advances in efficient (approximate) image matching schemes have opened the door for a number of large scale matching applications. The general field of content based image retrieval (CBIR) uses many different input modalities to search for similar images in a database. 
         [0002]    In the realm of freeform hand sketches using interactive displays and a standard drawing interface, if a novice user is asked to sketch a face, the result will typically look rough and unrefined. Similarly, if asked to draw a bicycle, for example, most of users would have a difficult time depicting how the frame and wheels relate to each other. 
         [0003]    One solution is to search for an image of the object to be drawn, and to either trace the object or use the object in some other way, such as for a reference. However, aside from the difficulty of finding an image of what is to be drawn, simply tracing object edges eliminates much of the essence of drawing (there is very little freedom in tracing strokes). Conversely, drawing on blank paper with only the image in the mind&#39;s eye gives the drawer more freedom. Without significant training it is difficult to get the relative proportions of objects correct. Thus, freehand drawing remains a frustrating endeavor. 
       SUMMARY 
       [0004]    The following presents a simplified summary in order to provide a basic understanding of some novel embodiments described herein. This summary is not an extensive overview, and it is not intended to identify key/critical elements or to delineate the scope thereof. Its sole purpose is to present some concepts in a simplified form as a prelude to the more detailed description that is presented later. 
         [0005]    The disclosed architecture guides the freeform drawing of objects by a user to enable the user to produce improved drawings without significant training. As the user draws, the architecture dynamically updates a relevant shadow image underlying the user&#39;s strokes. The shadow images are suggestive of object contours that guide the user during the drawing process. The architecture automatically blends relevant edge images from a large database to construct the shadow. The shadows can either be used or ignored by the drawer. 
         [0006]    The architecture preserves the essence of drawing (freedom and expressiveness) and at the same time uses the shadow images as visual references to guide the drawer. Furthermore, shadows obtained from real images can enlighten the artist with the gist of many images simultaneously. The creation becomes a mix of both human intuition and computer intelligence. The computer, in essence, is a partner in the drawing process, providing guidance like a teacher, instead of actually producing the final artwork. The user&#39;s own creative styles remain consistent in the drawings, while the overall shapes and spacing are more realistic. 
         [0007]    The architecture includes a user interface and two computational processes. An offline step builds a database of images from images collected from the Internet. Each image is converted to an edge drawing using an existing long edge detector technique, and then stored. Numerous overlapping windows in each edge image are analyzed into edge descriptors, which are further coded as sketches with distinct hash keys (e.g., using min-hash), and then stored. 
         [0008]    As the user draws, the architecture dynamically analyzes the strokes using a similar encoding to determine hash keys for overlapping windows for fast matching with the database of images. A top ranked set (e.g., one hundred) of matching database edge images are further aligned to the drawing. A set of spatially varying weights are used to blend the edge images into a shadow image. A scoring method is employed to select the optimum image for display. In the user interface, the strokes are overlaid on top of an evolving shadow image to provide guidance for potential future strokes. 
         [0009]    To the accomplishment of the foregoing and related ends, certain illustrative aspects are described herein in connection with the following description and the annexed drawings. These aspects are indicative of the various ways in which the principles disclosed herein can be practiced and all aspects and equivalents thereof are intended to be within the scope of the claimed subject matter. Other advantages and novel features will become apparent from the following detailed description when considered in conjunction with the drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0010]      FIG. 1  illustrates a system in accordance with the disclosed architecture. 
           [0011]      FIG. 2  illustrates an alternative system that shows an analysis component. 
           [0012]      FIG. 3  illustrates a flowchart of an exemplary database creation process. 
           [0013]      FIG. 4  illustrates a flowchart of an exemplary image matching algorithm. 
           [0014]      FIG. 5  illustrates a flow diagram for an online processing pipeline for image matching in realtime guidance of freehand drawing. 
           [0015]      FIG. 6  illustrates a rendering pipeline for the user interface. 
           [0016]      FIG. 7  illustrates a computer-implemented method in accordance with the disclosed architecture. 
           [0017]      FIG. 8  illustrates further aspects of the method of  FIG. 7 . 
           [0018]      FIG. 9  illustrates a block diagram of a computing system that executes realtime user guidance for freehand drawing in accordance with the disclosed architecture. 
       
    
    
     DETAILED DESCRIPTION 
       [0019]    The disclosed architecture is an interactive system that dynamically adapts to the user&#39;s sketching and provides realtime feedback. The architecture employs a framework of content based image retrieval (CBIR) as well as a technique of partial spatial matching, and enables multiple matching images based on different sub-regions of the image. In addition, a verification stage and methods for determining blending weights are employed. 
         [0020]    As the user draws, a shadow image underlying the user strokes is dynamically updated. The shadows are suggestive of object contours that guide the user during the ongoing drawing process. Relevant edge images are obtained from a large database of images and automatically blended to construct the shadow image. 
         [0021]    As described herein, the architecture also provides the capability of an image (visual object) retrieval system that searches and returns candidate images for processing. In other words, a set of images is produced for selection and processing that is similar to the user sketch (or drawing). 
         [0022]    Reference is now made to the drawings, wherein like reference numerals are used to refer to like elements throughout. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding thereof. It may be evident, however, that the novel embodiments can be practiced without these specific details. In other instances, well known structures and devices are shown in block diagram form in order to facilitate a description thereof. The intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the claimed subject matter. 
         [0023]      FIG. 1  illustrates a system  100  in accordance with the disclosed architecture. The system  100  includes an input component  102  that receives a freeform user stroke  104  (e.g., by pen, touch, mouse, etc.) in association with an interactive surface (e.g., a touch screen, pen-based display, standard non-touch display, etc.). The stroke  104  is input to a drawing process that includes an evolving drawing  106 . A search component  108  searches and retrieves matching visual objects  110  from a datasource  112  in response to input of the user stroke  104 . The visual objects include images, other user-generated hand sketches, art work, photos, web content, video content, and so on. The matching visual objects  110  have object portions which match a part of the evolving drawing  106 . 
         [0024]    The system  100  can further include a user interface (UI) component  114  (e.g., a drawing program UI) that presents a dynamically changing composite image  116  of the matching visual objects  110  proximate the user stroke  104  during the drawing process to guide the drawing process. 
         [0025]      FIG. 2  illustrates an alternative system  200  that shows an analysis component  202 . The analysis component performs all the analysis capabilities for visual object matching including, but not limited to, candidate matching, alignment, and weighting. For example, the analysis component  202  performs verification of candidate visual objects by alignment of the candidate visual objects to the evolving drawing to obtain matching scores and computation of weights for the candidate visual objects based on the scores. The analysis component  202  computes a score for a candidate visual object based on similarity between an edge orientation of the candidate visual object and the user stroke. The analysis component  202  computes global and spatially varying weights to blend corresponding edge images of candidate visual objects into the composite image. The analysis component  202  performs spatial matching to obtain multiple matching visual objects that include different sub-regions which match parts of the evolving drawing. 
         [0026]    Following is a detailed description of the disclosed architecture for realtime guidance for freehand drawing. 
         [0027]    The architecture includes the construction of an inverted file structure that indexes a database of visual objects (e.g., images) and associated edge maps; a query method that, given user strokes, dynamically retrieves matching visual objects, aligns the objects to the evolving drawing and weights the objects based on a matching score; and, the user interface for drawing, which displays a shadow of weighted edge maps proximate (e.g., beneath) the user&#39;s drawing to guide the drawing process. 
         [0028]    With respect to database creation, the visual objects in the database are selected so that the objects depicted, as well as object appearance and pose, are likely to be similar to those drawn by the user. Note that although the term “image” or “images” is used during this description, it is to be understood that an image is one form of visual object, and the description herein applies to all types of visual objects, including images. A large database of hand drawn images can be used. Alternatively, a set of natural images collected from the Internet via categorical image queries such as “t-shirt”, “bicycle”, “car”, etc., as well as from category specific databases can be employed. Although such images have many extraneous backgrounds, objects, framing lines, etc., on average, the images will contain edges a user may want to draw. 
         [0029]    Included herein is a set of flow charts representative of exemplary methodologies for performing novel aspects of the disclosed architecture. While, for purposes of simplicity of explanation, the one or more methodologies shown herein, for example, in the form of a flow chart or flow diagram, are shown and described as a series of acts, it is to be understood and appreciated that the methodologies are not limited by the order of acts, as some acts may, in accordance therewith, occur in a different order and/or concurrently with other acts from that shown and described herein. For example, those skilled in the art will understand and appreciate that a methodology could alternatively be represented as a series of interrelated states or events, such as in a state diagram. Moreover, not all acts illustrated in a methodology may be required for a novel implementation. 
         [0030]      FIG. 3  illustrates a flowchart of an exemplary database creation process. At  300 , database creation of visual objects is initiated. At  302 , each visual object is scaled to a predetermined pixel resolution. At  304 , edges from the visual object are extracted. At  306 , local edge descriptors are computed. At  308 , set of concatenated hashes are computed from the edge descriptors. At  310 , the sets of concatenated hashes are stored in a database. At  312 , the above steps are repeated for all visual objects. At  314 , the resulting database is stored as an inverted file. 
         [0031]    More specifically, the images are scaled to fit a predefined pixel resolution (e.g., 300×300). Each image is then processed in three stages and added to an inverted file structure. First, edges are extracted from the image. Next, local edge descriptors are computed. Finally, sets of concatenated hashes (called sketches) are computed from the edge descriptors and added to the database. The database is stored as an inverted file, in other words, indexed by sketch value, which in turn points to the original image, its edges, and the position of the edge descriptor used to compute the sketch. 
         [0032]    With respect to edge extraction, given a natural image (a form of visual object), it is desired to find the edges most likely to be drawn by a user while ignoring others. The method of edge detection locally normalizes the magnitudes of the edges, and then sums the normalized magnitudes, weighted by local curvature, along the length of the edge. The result is an edge response that is related to the length of the edge and its degree of curvature, rather than the magnitude of the intensity gradients. The edge images E can be stored using run length encoding. 
         [0033]    With respect to patch descriptors, for each edge image, edge positions are determined by finding maxima in the responses perpendicular to the edge direction. The edge&#39;s orientation is found using a standard second order operator [−1, 2, −1] applied to the final edges in both horizontal and vertical directions. (The operator is a discrete differential operator used in image processing for edge detection.) Given an image I in the database with corresponding edges E and orientations θ, a set of edge descriptors d i εD is computed. Since the goal is to match an edge image E to incomplete and evolving drawings, the descriptors are computed locally over predetermined patch dimension (e.g., 60×60 patches). The patches used to compute neighboring descriptors can overlap by fifty percent, resulting in eighty-one descriptors over the fixed grid (e.g., 9×9) of patches. 
         [0034]    The descriptors can be computed using the BiCE (binary coherent edge) descriptor algorithm, which encodes a histogram of edge positions and orientations. Since the edges drawn by a user are typically less dense than in natural images, a low dimensional version of BiCE can be employed. 
         [0035]    A three dimensional histogram can be defined with four discrete edge orientations, eighteen positions perpendicular to the edge, and six positions tangent to the edge. In this example, and using a conventional notation, set n x′ =18, n y′ =6, n θ =4, and n l =1. The buckets of the histogram can be binarized by setting the top twenty percent to one and the rest to zero. The final descriptor d, has four-hundred thirty-two binary bits, with eighty-six ones and three-hundred forty-six zeros. 
         [0036]    A feature of the BiCE descriptor is its binary encoding: it can be viewed as a set representation where the ones indicate edge presence. This makes it amenable to min-hash, which is an effective hashing technique for retrieval and clustering. Min-hash has the property that the probability of two sets having the same hash value (“colliding”) is equal to their Jaccard similarity. The Jaccard similarity sim(d i , d j ) between two sets, d i  and d j , is the cardinality of the intersection divided by the cardinality of the union: 
         [0000]    
       
         
           
             
               
                 
                   
                     sim 
                      
                     
                       ( 
                       
                         
                           d 
                           i 
                         
                         , 
                         
                           d 
                           j 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         # 
                          
                         
                           ( 
                           
                             
                               d 
                               i 
                             
                             ⋂ 
                             
                               d 
                               j 
                             
                           
                           ) 
                         
                       
                       
                         # 
                          
                         
                           ( 
                           
                             
                               d 
                               i 
                             
                             ⋂ 
                             
                               d 
                               j 
                             
                           
                           ) 
                         
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0037]    A min-hash function randomly permutes the set of indices (the ones and zeros). All sets (BiCE descriptors) are permuted using the same min-hash function. The min-hash value for a given permuted set is its smallest index containing a one after the permutation. A single min-hash can be non-discriminative and introduce many false positive retrievals, especially if the descriptor is non-sparse. To increase precision, k independent random min-hash functions can be computed and applied to all BiCE descriptors. 
         [0038]    The resulting k min-hash values are concatenated for each descriptor into k-tuples, called sketches. The probability of two sketches colliding is thus reduced exponentially to sim (d i , d j ) k . To increase recall, this process is repeated n times using n different sets of k min-hash functions, resulting in n sketches per descriptor. To maintain high recall while reducing false positives, tradeoffs are made between the number of sketches stored for each descriptor and the size of the sketch, k. In one implementation, n=20 sketches of size k=3 are stored for each descriptor. 
         [0039]    An inverted file structure is stored for each of the n min-hash sketches. Each unique sketch is allocated as a new entry in the structure. The image index and patch location of the descriptor instance that produced the sketch are recorded. 
         [0040]    With respect to image matching, the disclosed hashing scheme allows for efficient image queries, since only images with matching sketches need to be considered. 
         [0041]    A realtime matching pipeline between the edge images in the database and the user&#39;s drawing is now described.  FIG. 4  illustrates a flowchart of an exemplary image matching algorithm. At  400 , image matching is initiated. At  402 , a user stroke is received as input to an evolving drawing. At  404 , a set of candidate matching visual objects is obtained from an inverted file structure. At  406 , each candidate match is aligned with the user&#39;s drawing. At  408 , Scores from the alignments of candidate objects are generated. At  410 , the scores are used to compute a set of spatially varying weights for each edge image. At  412 , the output is a shadow image resulting from the weighted average of the edge images. At  414 , the shadow image is displayed to the user. 
         [0042]    With respect to candidate matches, the user&#39;s drawing is recorded as a set of vectorized multi-segment strokes. An edge image {tilde over (E)} is created from these strokes by drawing lines (e.g., with a width of one pixel between the stroke points). The rendered lines have the same style as the edges extracted from the natural images in the database (the edge image {tilde over (E)} used for matching does not need to use the stylized strokes that are seen by the user). The BiCE descriptors and corresponding sketches are computed as described above, using a higher resolution grid (e.g., 18×18=324 patches) with seventy-five percent overlap between neighboring patches. A higher resolution grid is used to increase the accuracy of the predicted position and to increase invariance to translations in the drawing. In one implementation, the user&#39;s drawing occupies an area of 480×480 pixels, resulting in 96×96 pixel patches with twenty-four pixel offsets between neighboring patches. Descriptors and sketches can be computed for each of the three-hundred twenty-four patches. 
         [0043]    Using the inverse lookup table, each sketch from the user&#39;s drawing is matched to the sketches stored in the database. A matching sketch casts one vote for the corresponding database image and patch offset pair. The matches are aggregated in a histogram H storing the number of matching sketches for each image at each grid offset. To reduce the size of H, votes are only stored if the database patch offset is within four patch grid points of the patch being considered in the user&#39;s drawing. This corresponds to relative shifts of less than ninety-six pixels between the user&#39;s drawing and the database images. The resulting histogram has size m×9×9, where m is the number of images in the database. After adding all the matches for each sketch to the histogram, the optimum matching offset is found for each image, and the top one-hundred images are added to the candidate set C. n=20 sketches are computed for each descriptor, resulting in a maximum possible twenty votes per sketch in the histogram. To reduce the bias from any single descriptor, each descriptor can be limited to at most four votes in the histogram. 
         [0044]    Given a large database, computing the candidate set as described above can be computationally expensive. However, user strokes change gradually over time to increase performance, thus, at each time step, only votes resulting from sketches derived from patches that have changed, are updated. This can be accomplished by subtracting the votes added from the previous sketches from H, followed by adding in the votes from the new sketches. At each time frame, any candidate image from the previous time frame that contributed to the shadow image can also be added to the candidate set, if not already present. 
         [0045]    With respect to image alignment, the candidate image set of candidates C contains a set of images with approximate offsets d x  and d y  defined by the optimum matching offset, as described above. The approximation arises from the discretization of the offsets in the grid of patches. These offsets can be refined using a 1D (one-dimensional) variation of the Generalized Hough transform. Using the standard Generalized Hough transform for 2D (two-dimensional) translations, a 2D histogram T over possible offsets x and y is created using: 
         [0000]    
       
         
           
             
               
                 
                   
                     T 
                      
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       p 
                     
                      
                     
                       
                         
                           E 
                           ~ 
                         
                          
                         
                           ( 
                           
                             
                               p 
                               x 
                             
                             , 
                             
                               p 
                               y 
                             
                           
                           ) 
                         
                       
                        
                       
                         E 
                          
                         
                           ( 
                           
                             
                               
                                 p 
                                 x 
                               
                               + 
                               
                                 d 
                                 x 
                               
                               + 
                               x 
                             
                             , 
                             
                               
                                 p 
                                 y 
                               
                               + 
                               
                                 d 
                                 y 
                               
                               + 
                               y 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where {tilde over (E)}(p x ,p y ) is the value of {tilde over (E)} at pixel p in location (p x , p y ), and similarly for the edge image E. The optimum offset can be determined by finding the maximum value of T(x,y). This approach can be computationally expensive due to the need to sum over the image for every possible combination of x and y offsets. Alternatively, compute the x and y dimensions separately using two histograms: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         T 
                         x 
                       
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         p 
                       
                        
                       
                         
                           sin 
                            
                           
                             ( 
                             
                               
                                 θ 
                                 ~ 
                               
                                
                               
                                 ( 
                                 
                                   
                                     p 
                                     x 
                                   
                                   , 
                                   
                                     p 
                                     y 
                                   
                                 
                                 ) 
                               
                             
                             ) 
                           
                         
                          
                         
                           
                             E 
                             ~ 
                           
                            
                           
                             ( 
                             
                               
                                 p 
                                 x 
                               
                               , 
                               
                                 p 
                                 y 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       sin 
                        
                       
                         ( 
                         
                           θ 
                            
                           
                             ( 
                             
                               
                                 
                                   p 
                                   x 
                                 
                                 + 
                                 
                                   d 
                                   x 
                                 
                                 + 
                                 x 
                               
                               , 
                               
                                 
                                   p 
                                   y 
                                 
                                 + 
                                 
                                   d 
                                   y 
                                 
                               
                             
                             ) 
                           
                         
                         ) 
                       
                     
                      
                     
                       E 
                        
                       
                         ( 
                         
                           
                             
                               p 
                               x 
                             
                             + 
                             
                               d 
                               x 
                             
                             + 
                             x 
                           
                           , 
                           
                             
                               p 
                               y 
                             
                             + 
                             
                               d 
                               y 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    and similarly for T y  using the cosine of the angles. The sine of the edge angles provides higher weights to the more informative vertical edges when determining the horizontal offsets, and similarly for T y  and cosine with horizontal edges. Once the histograms T x  and T y  are created, the histograms are slightly blurred with σ h =2. The final sub-pixel offsets d′ x  and d′ y  are determined by adding a quadratic interpolation of the resulting peak response in T x  and T y  to d x  and d y . For additional accuracy, two iterations can be run. To reduce computation, the search range of x and y can be limited to twice the distance between the grid points. In addition, equation (3) is computed on reduced resolution images (e.g., size 160×160). If desired, another one-dimensional histogram may be similarly computed over scale to provide scale alignment between the user drawing and the line images. The aligned edge image is denoted as E′ i . 
         [0046]    With respect to image weighting, there now exists a set of candidate images, C, and associated aligned edge images E′ i , aligned using offsets d′ i . The intent is now to blend these aligned edge images into a shadow image S that will help guide the user as the user draws. To do so, blending weight images W i  are constructed. 
         [0000]    
       
         
           
             S 
             = 
             
               
                 ∑ 
                 i 
               
                
               
                 
                   W 
                   i 
                 
                  
                 
                   E 
                   i 
                   ′ 
                 
               
             
           
         
       
     
         [0047]    The blending weight can be set high where there is a good match between the drawing and the candidate&#39;s aligned edges, and low, where there is not a good match. The weight image can be constructed from two terms: a global matching term, v i  and a spatially varying matching term, V i , normalized as follows over all images in the candidate set: 
         [0000]    
       
         
           
             
               
                 
                   
                     W 
                     i 
                   
                   = 
                   
                     
                       
                         v 
                         i 
                       
                        
                       
                         V 
                         i 
                       
                     
                     
                       
                         
                           ∑ 
                           i 
                         
                          
                         
                           
                             v 
                             i 
                           
                            
                           
                             V 
                             i 
                           
                         
                       
                       + 
                       ε 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The parameter ε is included in the normalization to avoid a noisy shadow just as the drawing begins and all match scores are low. The values of v i  and V i  are defined based on the global and spatially varying matching scores respectively, u i  and U i  (described below), based on edge matches at discrete orientations (e.g., eight). 
         [0048]    The overall weight, v i , and ε are defined by a non-linear function, Ψ, and the average of the highest matching scores u* (e.g., five), 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       v 
                       i 
                     
                     = 
                     
                       
                         Ψ 
                          
                         
                           ( 
                           
                             u 
                             i 
                           
                           ) 
                         
                       
                       
                         
                           ∑ 
                           j 
                         
                          
                         
                           Ψ 
                            
                           
                             ( 
                             
                               u 
                               j 
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where 
         [0000]    
       
         
           
             
               
                 
                   
                     Ψ 
                      
                     
                       ( 
                       
                         u 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       max 
                       ( 
                       
                         0 
                         , 
                         
                           ( 
                           
                             
                               
                                 u 
                                 i 
                               
                               - 
                               
                                 γ 
                                  
                                 
                                     
                                 
                                  
                                 
                                   u 
                                   * 
                                 
                               
                             
                             
                               
                                 u 
                                 * 
                               
                               - 
                               
                                 γ 
                                  
                                 
                                     
                                 
                                  
                                 
                                   u 
                                   * 
                                 
                               
                             
                           
                           ) 
                         
                       
                       ) 
                     
                     κ 
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    In one implementation, a value of 0.5 is assigned to y, which means the value of Ψ (u i ) is greater than zero only if the score is greater than half the highest scores. κ=2 sets the rate of weight decay as quadratic. In Equation (5), ε=Ψ (u ε ) is added to the denominator to force all of the weights towards zero when all the scores are low (e.g., when the drawing has just started), resulting in the shadows not being seen by the user. U ε  is set to correspond to the score after a single stroke is drawn (e.g., of approximately two-hundred pixels). The locally varying weight V i  is set to the spatially varying matching score image U i  as described next. 
         [0049]    Note that the weighting technique described above is just one possible technique for computing the weights. Accordingly, it is to be understood that other weighting techniques can be employed as well. 
         [0050]    Following is a description of the global matching score u and the spatially varying matching image U. A goal is for a candidate image&#39;s score to increase if an edge exists with a similar orientation to a user&#39;s stroke. To compute the matching scores, each candidate edge image is decomposed into new images θ t  (e.g., eight), where t=1 . . . 8 and similarly, the drawing edges into eight images {tilde over (θ)} t . Each of the eight images captures only strokes nearly parallel to one of eight evenly spaced orientations. In other words new image θ 1  includes only the horizontal edges, θ 5  depicts vertical edges, and the other six each capture one other orientation. Edge orientation at each pixel is measured by the ratio of second order operators. If an edge&#39;s orientation falls inbetween two of the eight discrete orientations, its contribution is linearly divided between the two oriented edge images. To provide some invariance to position, the oriented edge images can be Gaussian blurred with a blur kernel (σ s ) with standard deviation σ s =1.25φ, where φ is the relative distance between grid points. 
         [0051]    It is also desirable that images that contain multiple edges near a stroke receive the same score contribution as those with a single edge. This is accomplished by enforcing the sum of the blurred oriented edge images at each pixel location to be no more than the maximum possible contribution from a single edge crossing that pixel. 
         [0052]    Both the matching positive image θ +  and negative image θ −  are computed as the sum of the products of oriented edge images. The positive matches are the products of the images with same orientations, while the negative matches are defined by the products of orthogonally oriented edge images. 
         [0000]    
       
         
           
             
               
                 
                   
                     ϑ 
                     + 
                   
                   = 
                   
                     
                       ∑ 
                       
                         
                           t 
                           = 
                           1 
                         
                         , 
                         8 
                       
                     
                      
                     
                       
                         ϑ 
                         t 
                       
                       * 
                       
                         
                           ϑ 
                           ~ 
                         
                         t 
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 
                   
                     ϑ 
                     - 
                   
                   = 
                   
                     
                       ∑ 
                       
                         
                           t 
                           = 
                           1 
                         
                         , 
                         8 
                       
                     
                      
                     
                       
                         ϑ 
                         t 
                       
                       * 
                       
                         
                           ϑ 
                           ~ 
                         
                         
                           
                             ( 
                             
                               t 
                               + 
                               4 
                             
                             ) 
                           
                            
                           %8 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0053]    Finally, the global matching score u i  is defined as the sum of the differences between the positive and negative matches over all pixels, 
         [0000]    
       
         
           
             
               
                 
                   
                     u 
                     i 
                   
                   = 
                   
                     
                       
                         ∑ 
                         p 
                       
                        
                       
                         
                           ϑ 
                           i 
                           + 
                         
                          
                         
                           ( 
                           p 
                           ) 
                         
                       
                     
                     - 
                     
                       
                         ϑ 
                         i 
                         - 
                       
                        
                       
                         ( 
                         p 
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0000]    and the spatially varying score image is a Gaussian blurred version of the positive match image, 
         [0000]        U   i   =g (θ i   + ,4φ)  (11)
 
         [0054]    An offset is added to U i  to ensure non-zero values. To reduce computation, the image scores and weights are computed on reduced resolution images (e.g., 40×40 pixels). 
         [0055]    As a general summary, a shadow image is computed in realtime by comparing the user-drawn strokes to the candidate images obtained from the database. Global and spatially varying weights are computed to blend the corresponding edge images to create the shadow image used in the drawing interface. These weights are determined by comparing local orientations of edges between the developing drawing and the database edge images. 
         [0056]    With respect to the user interface, in one implementation, the user can use a screen/tablet to draw or erase strokes using a stylus. The user sees the evolving drawing formed with pen strokes superimposed on a continuously updating shadow S. The drawing area (e.g., 480×480 pixels) and the line strokes can be rendered using a dark blue marker style. To provide some color contrast, the shadow can be rendered in a sepia tone. 
         [0057]    To further make the shadow visible to the user, while not distracting from the user&#39;s actual drawing, the shadow image can be filtered to remove noisy and faint edges, 
         [0000]        {tilde over (S)}=S *( g ( S,σ   r )−ε)  (12)
 
         [0000]    where σ r =16. Multiplying by a blurred shadow image strengthens edges that agree in position, and weakens others. ε=1 is used to additionally suppress faint edges. In addition, a nominal amount of blur can be added with a standard deviation of 1.25 to soften the shadows. Finally, the shadow S′ can be weighted to show a higher contrast near the user&#39;s cursor position p c : 
         [0000]        S ′( p )=λ{tilde over ( S )}( p )+(1−λ)ω{tilde over ( S )}( p )  (13)
 
         [0000]    where ω is a Gaussian weighted distance between p and p c  with a standard deviation of 120 pixels. Contrast control parameter λ may be set by the user and controls the contrast of the shadows. 
         [0058]    Put another way, a system is provided that comprises an input component that receives a freeform user stroke in association with an interactive surface, the stroke input to a drawing process that includes an evolving drawing, a database of visual objects, the database stored as an inverted file of indexed sketch values that map to original visual objects and associated object edge images, a search component that performs a search of the inverted file in response to the user stroke using a hashing technique to retrieve matching visual objects, the search component includes an analysis component that analyzes the database of visual objects for candidate objects and processes the candidate objects to return the matching visual objects, and a user interface component that presents a dynamically changing composite image of the matching visual objects proximate the user stroke during the drawing process to guide the drawing process. 
         [0059]    The analysis component performs verification of candidate visual objects by, alignment of the candidate visual objects to the evolving drawing to obtain matching scores for the candidate visual objects based on similarity between an edge orientation of the candidate visual object and the user stroke, and computation of weights for the candidate visual objects based on the scores. 
         [0060]    The visual objects of the database are indexed by concatenated hashes which are derived from an edge extraction process and patch descriptors. The analysis component computes global and spatially varying scores to blend corresponding edge images of candidate visual objects into the composite image, the scores computed based on comparison of local orientation edges between the evolving drawing and database edge images. The analysis component increases a score for a candidate visual object if an edge exists with a similar orientation to the user stroke. 
         [0061]    In yet another embodiment, a system is provided that comprises a source of visual objects, the source includes a database where the visual objects are stored as an inverted file of indexed values (e.g., sketch) that map to original visual objects and associated object edge images, and a search component that performs a search of the inverted file using a hashing technique to retrieve matching visual objects, the search component includes an analysis component that analyzes the source of visual objects for candidate objects and processes the candidate objects to return matching visual objects, the analysis component computes global and spatially varying weights for blending of corresponding edge images of candidate visual objects into a composite image presented as a shadow image for drawing guidance during a drawing process. The search component and the analysis component dynamically update the shadow image in response to strokes input to the drawing process. 
         [0062]    The analysis component performs verification of candidate visual objects by, alignment of the candidate visual objects to an evolving drawing to obtain matching scores for the candidate visual objects based on similarity between an edge orientation of the candidate visual object and an input stroke, and computation of weights for the candidate visual objects based on the scores. The visual objects of the database can be indexed by concatenated hashes which are derived from an edge extraction process and patch descriptors. The analysis component computes the weights based on comparison of local orientation edges between an evolving drawing and database edge images. The analysis component increases a score for a candidate visual object if an edge exists with a similar orientation to an input stroke. 
         [0063]      FIG. 5  illustrates a flow diagram  500  for an online processing pipeline for image matching in realtime guidance of freehand drawing. At  502 , user strokes are received on a user drawing. The user drawing is recorded as a set of vectorized multi-segmented strokes. At  504 , patch descriptors are determined based on predetermined sub-region patches with a percentage overlap. For each sub-region, matches are aggregated in a histogram  506 . Thereafter, a verification process  508  performs fine alignment  510 , spatial scoring  512 , and outputs the resulting shadow image  514  (composite image). 
         [0064]      FIG. 6  illustrates a rendering pipeline  600  for the user interface. At  602 , user strokes are received and rendered. In this example, a bicycle is sketched in the drawing  604 . At  606 , weighting is performed based on pen position (for a pen-based interactive surface). The pen position  608  is represented in the drawing  604 . At  610 , a shadow image  612  is created. At  614 , the shadow image  612  is presented relative to the pen position  608 . In other words, the shadow image  612  can be presented under (and perhaps slightly offset from) the drawing  604 . 
         [0065]      FIG. 7  illustrates a computer-implemented method in accordance with the disclosed architecture. At  700 , a user stroke is received as input to an evolving drawing during a drawing process. At  702 , visual objects are obtained to find candidate visual objects. At  704 , the candidate visual objects are processed to find matching visual objects. At  706 , relevant matching visual objects are dynamically presented as shadow visual objects proximate the drawing 
         [0066]      FIG. 8  illustrates further aspects of the method of  FIG. 7 . Note that the flow indicates that each block can represent a step that can be included, separately or in combination with other blocks, as additional aspects of the method represented by the flow chart of  FIG. 7 . At  800 , the matching visual objects are aligned to the evolving drawing. At  802 , the matching visual objects are weighted based on the alignment. At  804 , the shadow visual objects are presented as weighted edge maps underlying the drawing and visually perceived to guide the user in the drawing process. At  806 , the visual objects are obtained from other drawings and/or a database, the database is stored as an inverted file of indexed concatenated hashes searchable by a min-hash technology. At  808 , the candidate visual objects are aligned to the drawing to generate associated scores. At  810 , a set of spatially varying weights is computed for each edge of the candidate matching object based on alignment scores. At  812 , the shadow visual objects are filtered to remove noisy and faint edges. 
         [0067]    As used in this application, the terms “component” and “system” are intended to refer to a computer-related entity, either hardware, a combination of software and tangible hardware, software, or software in execution. For example, a component can be, but is not limited to, tangible components such as a processor, chip memory, mass storage devices (e.g., optical drives, solid state drives, and/or magnetic storage media drives), and computers, and software components such as a process running on a processor, an object, an executable, a data structure (stored in volatile or non-volatile storage media), a module, a thread of execution, and/or a program. By way of illustration, both an application running on a server and the server can be a component. One or more components can reside within a process and/or thread of execution, and a component can be localized on one computer and/or distributed between two or more computers. The word “exemplary” may be used herein to mean serving as an example, instance, or illustration. Any aspect or design described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other aspects or designs. 
         [0068]    Referring now to  FIG. 9 , there is illustrated a block diagram of a computing system  900  that executes realtime user guidance for freehand drawing in accordance with the disclosed architecture. However, it is appreciated that the some or all aspects of the disclosed methods and/or systems can be implemented as a system-on-a-chip, where analog, digital, mixed signals, and other functions are fabricated on a single chip substrate. In order to provide additional context for various aspects thereof,  FIG. 9  and the following description are intended to provide a brief, general description of the suitable computing system  900  in which the various aspects can be implemented. While the description above is in the general context of computer-executable instructions that can run on one or more computers, those skilled in the art will recognize that a novel embodiment also can be implemented in combination with other program modules and/or as a combination of hardware and software. 
         [0069]    The computing system  900  for implementing various aspects includes the computer  902  having processing unit(s)  904 , a computer-readable storage such as a system memory  906 , and a system bus  908 . The processing unit(s)  904  can be any of various commercially available processors such as single-processor, multi-processor, single-core units and multi-core units. Moreover, those skilled in the art will appreciate that the novel methods can be practiced with other computer system configurations, including minicomputers, mainframe computers, as well as personal computers (e.g., desktop, laptop, etc.), hand-held computing devices, microprocessor-based or programmable consumer electronics, and the like, each of which can be operatively coupled to one or more associated devices. 
         [0070]    The system memory  906  can include computer-readable storage (physical storage media) such as a volatile (VOL) memory  910  (e.g., random access memory (RAM)) and non-volatile memory (NON-VOL)  912  (e.g., ROM, EPROM, EEPROM, etc.). A basic input/output system (BIOS) can be stored in the non-volatile memory  912 , and includes the basic routines that facilitate the communication of data and signals between components within the computer  902 , such as during startup. The volatile memory  910  can also include a high-speed RAM such as static RAM for caching data. 
         [0071]    The system bus  908  provides an interface for system components including, but not limited to, the system memory  906  to the processing unit(s)  904 . The system bus  908  can be any of several types of bus structure that can further interconnect to a memory bus (with or without a memory controller), and a peripheral bus (e.g., PCI, PCIe, AGP, LPC, etc.), using any of a variety of commercially available bus architectures. 
         [0072]    The computer  902  further includes machine readable storage subsystem(s)  914  and storage interface(s)  916  for interfacing the storage subsystem(s)  914  to the system bus  908  and other desired computer components. The storage subsystem(s)  914  (physical storage media) can include one or more of a hard disk drive (HDD), a magnetic floppy disk drive (FDD), and/or optical disk storage drive (e.g., a CD-ROM drive DVD drive), for example. The storage interface(s)  916  can include interface technologies such as EIDE, ATA, SATA, and IEEE 1394, for example. 
         [0073]    One or more programs and data can be stored in the memory subsystem  906 , a machine readable and removable memory subsystem  918  (e.g., flash drive form factor technology), and/or the storage subsystem(s)  914  (e.g., optical, magnetic, solid state), including an operating system  920 , one or more application programs  922 , other program modules  924 , and program data  926 . 
         [0074]    The operating system  920 , one or more application programs  922 , other program modules  924 , and/or program data  926  can include the entities and components of the system  100  of  FIG. 1 , the entities and components of the system  200  of  FIG. 2 , the entities, components, and flow of the diagram  500  of  FIG. 5 , the entities and components of the rendering pipeline  600  of  FIG. 6 , and the methods represented by the flowcharts of  FIGS. 3 ,  4 ,  7 , and  8 , for example. 
         [0075]    Generally, programs include routines, methods, data structures, other software components, etc., that perform particular tasks or implement particular abstract data types. All or portions of the operating system  920 , applications  922 , modules  924 , and/or data  926  can also be cached in memory such as the volatile memory  910 , for example. It is to be appreciated that the disclosed architecture can be implemented with various commercially available operating systems or combinations of operating systems (e.g., as virtual machines). 
         [0076]    The storage subsystem(s)  914  and memory subsystems ( 906  and  918 ) serve as computer readable media for volatile and non-volatile storage of data, data structures, computer-executable instructions, and so forth. Such instructions, when executed by a computer or other machine, can cause the computer or other machine to perform one or more acts of a method. The instructions to perform the acts can be stored on one medium, or could be stored across multiple media, so that the instructions appear collectively on the one or more computer-readable storage media, regardless of whether all of the instructions are on the same media. 
         [0077]    Computer readable media can be any available media that can be accessed by the computer  902  and includes volatile and non-volatile internal and/or external media that is removable or non-removable. For the computer  902 , the media accommodate the storage of data in any suitable digital format. It should be appreciated by those skilled in the art that other types of computer readable media can be employed such as zip drives, magnetic tape, flash memory cards, flash drives, cartridges, and the like, for storing computer executable instructions for performing the novel methods of the disclosed architecture. 
         [0078]    A user can interact with the computer  902 , programs, and data using external user input devices  928  such as a keyboard and a mouse. Other external user input devices  928  can include a microphone, an IR (infrared) remote control, a joystick, a game pad, camera recognition systems, a stylus pen, touch screen, gesture systems (e.g., eye movement, head movement, etc.), and/or the like. The user can interact with the computer  902 , programs, and data using onboard user input devices  930  such a touchpad, microphone, keyboard, etc., where the computer  902  is a portable computer, for example. These and other input devices are connected to the processing unit(s)  904  through input/output (I/O) device interface(s)  932  via the system bus  908 , but can be connected by other interfaces such as a parallel port, IEEE 1394 serial port, a game port, a USB port, an IR interface, short-range wireless (e.g., Bluetooth) and other personal area network (PAN) technologies, etc. The I/O device interface(s)  932  also facilitate the use of output peripherals  934  such as printers, audio devices, camera devices, and so on, such as a sound card and/or onboard audio processing capability. 
         [0079]    One or more graphics interface(s)  936  (also commonly referred to as a graphics processing unit (GPU)) provide graphics and video signals between the computer  902  and external display(s)  938  (e.g., LCD, plasma) and/or onboard displays  940  (e.g., for portable computer). The graphics interface(s)  936  can also be manufactured as part of the computer system board. 
         [0080]    The computer  902  can operate in a networked environment (e.g., IP-based) using logical connections via a wired/wireless communications subsystem  942  to one or more networks and/or other computers. The other computers can include workstations, servers, routers, personal computers, microprocessor-based entertainment appliances, peer devices or other common network nodes, and typically include many or all of the elements described relative to the computer  902 . The logical connections can include wired/wireless connectivity to a local area network (LAN), a wide area network (WAN), hotspot, and so on. LAN and WAN networking environments are commonplace in offices and companies and facilitate enterprise-wide computer networks, such as intranets, all of which may connect to a global communications network such as the Internet. 
         [0081]    When used in a networking environment the computer  902  connects to the network via a wired/wireless communication subsystem  942  (e.g., a network interface adapter, onboard transceiver subsystem, etc.) to communicate with wired/wireless networks, wired/wireless printers, wired/wireless input devices  944 , and so on. The computer  902  can include a modem or other means for establishing communications over the network. In a networked environment, programs and data relative to the computer  902  can be stored in the remote memory/storage device, as is associated with a distributed system. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers can be used. 
         [0082]    The computer  902  is operable to communicate with wired/wireless devices or entities using the radio technologies such as the IEEE 802.xx family of standards, such as wireless devices operatively disposed in wireless communication (e.g., IEEE 802.11 over-the-air modulation techniques) with, for example, a printer, scanner, desktop and/or portable computer, personal digital assistant (PDA), communications satellite, any piece of equipment or location associated with a wirelessly detectable tag (e.g., a kiosk, news stand, restroom), and telephone. This includes at least Wi-Fi (or Wireless Fidelity) for hotspots, WiMax, and Bluetooth™ wireless technologies. Thus, the communications can be a predefined structure as with a conventional network or simply an ad hoc communication between at least two devices. Wi-Fi networks use radio technologies called IEEE 802.11x (a, b, g, etc.) to provide secure, reliable, fast wireless connectivity. A Wi-Fi network can be used to connect computers to each other, to the Internet, and to wire networks (which use IEEE 802.3-related media and functions). 
         [0083]    The illustrated and described aspects can be practiced in distributed computing environments where certain tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules can be located in local and/or remote storage and/or memory system. 
         [0084]    What has been described above includes examples of the disclosed architecture. It is, of course, not possible to describe every conceivable combination of components and/or methodologies, but one of ordinary skill in the art may recognize that many further combinations and permutations are possible. Accordingly, the novel architecture is intended to embrace all such alterations, modifications and variations that fall within the spirit and scope of the appended claims. Furthermore, to the extent that the term “includes” is used in either the detailed description or the claims, such term is intended to be inclusive in a manner similar to the term “comprising” as “comprising” is interpreted when employed as a transitional word in a claim.