Patent Publication Number: US-8995771-B2

Title: Identification of duplicates within an image space

Description:
BACKGROUND 
     Discovering duplicate images within an image space can be beneficial. For example, identifying duplicate images can provide better object recognitions results. It can also prevent duplicate images from being presented in an image search results page. Duplicate image discovery techniques fall into two categories: full duplicate discovery and partial duplicate discovery. Conventional partial duplicate discovery—or the discovery of images that may not be full duplicates but that have the same objects within them—utilizes local descriptors of the images and adopts various hashing techniques. Such techniques have been scaled to discover duplicates within an image space containing millions of images. 
     The problem of full duplicate discovery—or the discovery of images that are full duplicates (albeit with slight variations in scale and/or content)—can be tackled with global feature-based methods. Duplicate image discovery is different from, and more challenging than, duplicate image retrieval. Conventional duplicate image retrieval methods are not scalable, since the computational costs are quadratic to the number of images in the image space. 
     BRIEF SUMMARY 
     This Summary is provided in order to introduce simplified concepts of the present disclosure, which are further described below in the Detailed Description. This summary is not intended to identify essential features of the claimed subject matter, nor is it intended for use in determining the scope of the claimed subject matter. 
     Global features are extracted from images within an image space, such as an internet-scale image space with billions of images. The global features are compressed into compact descriptors using Principal Component Analysis, and the compact descriptors are quantized into binary signatures. The signatures are used to partition the image space into coarse clusters, and the compact descriptors are used to create refined clusters within the coarse clusters. 
     Refined cluster growth is performed by searching in similar coarse clusters for images that match pseudo queries associated with the refined clusters. The pseudo queries are generated by averaging the compact descriptors of the images within the refined clusters, and similar clusters are identified based on Hamming distances of their signatures from signatures of the refined clusters. The refined clusters are identified and output as sets of duplicate images. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The Detailed Description is set forth with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The use of the same reference numbers in different figures indicates similar or identical items. 
         FIG. 1  is a block diagram of an example environment for identifying duplicate images according to embodiments. 
         FIG. 2  is a block diagram of an example computing system usable to identify duplicate images. 
         FIG. 3  is a flow diagram showing a process for identifying duplicate images in an image space. 
         FIG. 4  is a flow diagram showing an example process for identifying duplicate images using an E-clustering algorithm. 
     
    
    
     DETAILED DESCRIPTION 
     Overview 
     As discussed above, conventional duplicate image discovery methods successfully scale to millions of images. But such discovery methods do not scale to larger image spaces, such as the public internet which contains billions of images. Embodiments of the present disclosure include methods for full duplicate image discovery that scale to image spaces that contain billions of images. 
     Embodiments utilize global feature extraction from images within the image space. Global features include, for example, gray block features, edge directional histograms, and non-edge-pixel ratios (i.e. the ratio of pixels of detected edges to those of non-edges). Raw global image features are compressed, such as for example by using Principal Component Analysis (PCA), to form compact descriptors of the images. The compact descriptors are quantized to form binary signatures for the images. 
     The image space is partitioned into coarse clusters based on the image signatures. In embodiments, images with identical signatures are grouped together to form coarse clusters. Because such coarse clusters may not have sufficient precision for internet-scale image spaces, additional processing is performed to identify refined clusters of images. 
     Image clustering to identify refined clusters is performed based on a ε-clustering algorithm. The E-clustering algorithm includes pair-wise comparisons of the compact descriptors of the images within the coarse clusters. Images within a coarse cluster that have compact descriptors within a certain predefined distance from one another are grouped together to form refined clusters. Because there may also be images in other coarse clusters that are duplicates of the images within a particular refined cluster, a pseudo query is used to search images within similar coarse clusters. Images in the similar coarse clusters that are within a certain distance of the pseudo query are added to the refined clusters. The pseudo queries are, in embodiments, an average of the compact descriptors of the images in the refined clusters. A similar coarse cluster is defined based on its Hamming distance from the coarse cluster in question. The refined clusters are output as sets of duplicate images. 
     As used herein, the term “duplicate images” includes images that share the same objects, but that may vary slightly in scale, content, or other. That is, as used herein, one image may be deemed a duplicate of another image if the images have a calculated similarity that is greater than a predefined threshold. Thus, embodiments may find “true” duplicates (those that are identical in all respects), as well as images that are substantially similar (i.e., those that differ slightly in scale and/or content). Also, as used herein, the terms “clustering,” “partitioning,” “grouping,” and so forth may be used interchangeably to describe the process of coarse cluster identification and/or refined cluster growth and expansion. These terms are not meant to imply the sorts of data structures that are used to describe images that are in a coarse or refined cluster. A database of image signatures and compact descriptors may be processed, according to embodiments, in order to designate duplicate images as belonging to the same coarse and/or refined clusters. Embodiments may identify images as belonging to the same coarse and/or refined cluster without storing them in a contiguous memory space, although embodiments may do so without departing from the scope of the present disclosure. 
     The processes, systems, and devices described herein may be implemented in a number of ways. Example implementations are provided below with reference to the following figures. 
     Example Environment 
       FIG. 1  is a block diagram of an example environment for identifying duplicate images according to embodiments. Image data  100  is utilized by process  102  to identify duplicate images in image space  104 . Image space  104  includes a plurality of images, and may include billions of images, such as is present in an internet-scale image space. An example image, image  106 , is evenly partitioned into blocks, from which raw global features  108  are extracted. The raw global features include mean gray values that are calculated for each block of the image  106 . Additionally, edge directional histograms plus one dimension of non-edge-pixel ratio are extracted from blocks of the images in the image space  104 . The edge directional histograms and the non-edge-pixel ratios are useful since gray block features are not sufficient to describe images in which a single color dominates. 
     In one example, the image  106  may be partitioned into 8×8 blocks and gray block features extracted from each block, resulting in a 64-dim (dimension) gray block feature for the image  106 . The image  106  may be separately partitioned into 2×2 blocks and a 52-dim feature extracted from it which includes four twelve-edge directional histograms plus four non-edge ratios (one for each block). In this example, a 116-dim global feature is thus extracted from the image  106 . Global features having more or fewer dimensions may be extracted from the images in the image space  104  without departing from the scope of embodiments. Also, embodiments may utilize different global features, such as in order to improve precision. 
     The raw global features  108  are compressed into compact descriptors  110 . In embodiments, Principal Component Analysis (PCA) is utilized to compress the raw global features  108  into the compact descriptors  110 . Additionally, compact descriptors  110  are quantized into binary signatures  112 . 
     A PCA transfer matrix can be learned by conducting PCA on a sufficiently large number of images, for example millions of images. By omitting the least significant dimensions, PCA enables small noise and potential value drifting of features to be reduced. 
     Image space partitioning  114  utilizes the binary signatures of the images in the image space  104  to form coarse clusters. Images that have identical binary signatures are placed into the same coarse cluster. Different numbers of coarse clusters will be generated depending on the length of binary signatures  112 . 
     Identification of duplicate images based only on coarse clustering is likely insufficient for internet-scale image spaces. It was found, for example, that average precision of coarse clustering was 86.5% using 40-bit signatures evaluated on a random selection of 1000 coarse clusters. Thus, refined cluster creation  116  utilizes the compact descriptors  110  to form refined clusters within the coarse clusters. An ε-clustering algorithm is utilized to create the refined clusters. An example of the ε-clustering algorithm is given by the following pseudo-code. 
     
       
         
           
               
             
               
                   
               
               
                 The ε-clustering Algorithm: 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                   
                 Terms: 
               
               
                   
                 N: coarse cluster size 
               
               
                   
                 {x i  | 1 ≦ i ≦ N}: images in a coarse cluster 
               
               
                   
                 C i : the i-th refined cluster, 1 ≦ i ≦ N 
               
               
                   
                 δ i  ε {1, ..., N}: cluster membership of x i , x i  ε C δ     i     
               
               
                   
                 ε: distance threshold 
               
               
                   
                 Initialization: 
               
               
                   
                 Ci = {xi}, 1 ≦ i ≦ N 
               
               
                   
                 δ i  = −1, 1 ≦ i ≦ N 
               
               
                   
                 Clustering: 
               
               
                   
                 for all i = 1 : N do 
               
               
                   
                   for all j = i + 1 : N do 
               
               
                   
                     if Dist(x i , x j ) ≦ ε then 
               
               
                   
                       if δ i  = −1 &amp;&amp; δ j  = −1 then 
               
               
                   
                         δ i  = i 
               
               
                   
                         C i  = C i  ∪ {x j } //ε-ball creation 
               
               
                   
                       end if 
               
               
                   
                       if δ i  &gt; 0 &amp;&amp; δ j  = −1 then 
               
               
                   
                         δ j  = δ i   
               
               
                   
                         C δ     i    = C δ     i    ∪ {x j }//ε-ball expansion 
               
               
                   
                       end if 
               
               
                   
                       if δ i  &gt; 0 &amp;&amp; δ j  &gt; 0 then 
               
               
                   
                         δ j  = δ i   
               
               
                   
                         C δ     i    = C δ     i    ∪ C δ     j    //ε-ball merge 
               
               
                   
                         C δ     j    = Ø 
               
               
                   
                       end if 
               
               
                   
                     end if 
               
               
                   
                   end for 
               
               
                   
                 end for 
               
               
                   
                 return {C i  || C i  | ≧ 2, 1 ≦ i ≦ N} 
               
               
                   
                   
               
            
           
         
       
     
     The ε-clustering algorithm performs pair-wise comparisons between two images in a coarse cluster. Each image is initialized as a refined cluster, and a flag is used to indicate its cluster membership. During the pair-wise comparisons, if image x j  passes the neighborhood check of image x i  (e.g., is within the distance threshold ε from x j ), x j  is assigned to the refined cluster that x i  belongs to. This is the process of ε-ball expansion. ε-ball expansion identifies isolated duplicate images within a coarse cluster. Moreover, if x j  is from a cluster (i.e., C δ     j   ), that cluster is merged into the cluster that x i  belongs to (i.e., C δ     i   ). This is the process of ε-ball merge, and it connects two duplicate clusters. 
     The ε-clustering algorithm is able to form small refined clusters, and is therefore better able than other techniques such as k-means clustering to identify clusters that form a skewed space (such as a horseshoe shape). k-means clustering is sensitive to initial seeds and may fail on a skewed image distribution. Also, the computational cost of k-means clustering may be too high to be practical for internet-scale image spaces. 
     Partitioning the image space into coarse clusters may result in some duplicate images being scattered across multiple coarse clusters. Thus, refined cluster growth  118  utilizes the compact descriptors to search in similar coarse clusters for images to add to the refined clusters. A pseudo-query is constructed for each refined cluster, using the average of the compact descriptors of the images in each refined cluster. The pseudo query is then vector quantized to a pseudo query signature; the length of a pseudo query signature is not necessarily the same as the dimension of a pseudo query. Since the images in a refined cluster have low variance in their features, the pseudo query is representative of the refined cluster as a whole. Once the similar coarse clusters are identified (see discussion below), images within the similar coarse clusters are scored by its L 2  distance to the pseudo query and then ranked. The top-ranked images whose scores are less than a certain threshold are added to the refined cluster. 
     Identification of similar coarse clusters  120  utilizes the binary signatures  112  of the coarse clusters and the pseudo query signatures identified at  118 . A Hamming distance (Dist h ) between the signature of the coarse clusters and the pseudo query signature is used to determine the similar coarse clusters to search in. In one example, Dist h ≦2, and the number of similar signatures is 
                 (         0           H         )     +     (         1           H         )     +     (         2           H         )       ,         
where H is the signature length and
 
                   (         n           m         )           
stands for the Combination operation which counts the number of images having n out of m different bits to the signature of a query. With 16-bit signatures, images from up to 137 coarse clusters will be searched for cluster growing for a given pseudo query.
 
     Identification of duplicate images  122  identifies or outputs the refined clusters as sets of duplicate images. 
     Example Computing Device for Identifying Duplicate Images 
       FIG. 2  is a block diagram of an example computing system  200  usable to identify duplicate images. The computing system  200  may be configured as any suitable computing device capable of implementing all or part of a duplicate image discovery service. According to various non-limiting examples, suitable computing devices may include personal computers (PCs), servers, server farms, datacenters, special purpose computers, tablet computers, game consoles, smartphones, combinations of these, or any other computing device(s) capable of storing and executing all or part of a duplicate image discovery service. 
     In one example configuration, the computing system  200  comprises one or more processors  202  and memory  204 . The computing system  200  may also contain communication connection(s)  206  that allow communications with various other systems. The computing system  200  may also include one or more input devices  208 , such as a keyboard, mouse, pen, voice input device, touch input device, etc., and one or more output devices  210 , such as a display, speakers, printer, etc. coupled communicatively to the processor(s)  202  and memory  204 . 
     Memory  204  may store program instructions that are loadable and executable on the processor(s)  202 , as well as data generated during execution of, and/or usable in conjunction with, these programs. In the illustrated example, memory  204  stores an operating system  212 , which provides basic system functionality of the computing system  200  and, among other things, provides for operation of the other programs and modules of the computing system  200 . 
     Memory  204  includes a feature extraction module  214  configured to extract raw global features, such as raw global features  108 , from images of an image space. The feature extraction module  214  is configured to compress the raw global features into compact descriptors, such as compact descriptors  110 . The feature extraction module may utilize Principal Component Analysis (PCA), along with a PCA transfer matrix, to create the compact descriptors. The feature extraction module  214  is configured to quantize the compact descriptors into binary signatures, such as binary signatures  112 . The compact descriptors may be quantized using mean values of dimensions of the compact descriptors to generate the signatures. 
     A partition module  216  partitions the image space into a plurality of coarse clusters based on the binary signatures of the images within the image space. The coarse clusters are created, in embodiments, by grouping all images in the image space with the same binary signatures into the same coarse cluster. In other words, the partition module creates individual ones of the plurality of coarse clusters such that they include no images with non-identical signatures. Images with different signatures are placed into different coarse clusters. 
     A cluster module  218  is executable to create refined clusters within the plurality of coarse clusters using the ε-clustering algorithm, as described elsewhere within this Detailed Description. In particular, the cluster module  218  is configured to initialize images within a coarse cluster as refined clusters, and merge and grow the clusters based on pair-wise comparisons of the compact descriptors of the images within the same coarse clusters. Images within the coarse cluster are added to a refined cluster if its compact descriptor is within a certain distance threshold of an image within the refined cluster. 
     A growth module  220  searches similar coarse clusters for images to add to the refined clusters based on average compact descriptors of the refined cluster, as described elsewhere within this Detailed Description. In particular, the growth module  220  is configured to identify the similar coarse clusters based on Hamming distances between the coarse clusters and the refined clusters. The growth module  220  is configured to determine average compact descriptors of the refined clusters and to search the similar clusters for images to add to the refined clusters by determining whether compact descriptors of the images are within a threshold distance of the average compact descriptors of the refined clusters. Those that are within the threshold distance are added to the refined clusters. 
     An output module  222  is configured to output the refined clusters as sets of identical clusters. The output module  222  may identify the refined clusters as sets of duplicate images, and/or transmit data identifying the images in the refined clusters as being duplicates. 
     Example Operations for Identifying Duplicate Images 
       FIG. 3  is a flow diagram showing a process  300  for identifying duplicate images in an image space. At  302 , a feature extraction module, such as the feature extraction module  214 , determines compact descriptors and signatures for images within an image space. This includes extracting raw global features from a plurality of images of an image space, the raw global features including gray block features, edge directional histograms, and non-edge-pixel ratios. Principal Component Analysis is used in embodiments to compress the raw global features of the plurality of images into compact descriptors. The compact descriptors are quantized using mean values of the dimensions of the compact descriptors to generate the signatures. 
     At  304 , a partition module, such as the partition module  216 , partitions a plurality of images of an image space into a plurality of coarse clusters based on signatures of the plurality of images determined from compact descriptors of the plurality of images. The images are partitioned, in embodiments, such that images having identical signatures are placed into the same coarse cluster. The coarse clusters may have, in embodiments, only images with identical signatures, and no images with non-identical signatures. 
     At  306 , a cluster module, such as the cluster module  218 , creates one or more refined clusters within the coarse clusters. The refined clusters include one or more images of an individual coarse cluster, and are formed based on pair-wise comparisons of the compact descriptors of the particular coarse cluster. An ε-clustering algorithm is used as is described in more detail elsewhere within this 
     Detailed Description 
     At  308 , a growth module, such as the growth module  220 , searches other coarse clusters for images to add to the refined clusters. The searches are based on pseudo queries which, in embodiments, are average compact descriptors of the one or more images of the refined clusters. Not all coarse clusters are searched. Instead, similar clusters may be searched, determined for example by Hamming distances between signatures of the coarse clusters and quantized binary signatures derived from the average compact descriptors of the refined clusters. Images that are within a certain threshold distance of the pseudo queries are added to the corresponding refined clusters. 
     At  310 , the refined clusters are identified as being sets of duplicate images. Identification of the duplicate sets of images may be used to refine search results of search results, improve image recognition results, and so forth. 
       FIG. 4  is a flow diagram showing an example process  400  for identifying duplicate images using an ε-clustering algorithm. At  402 , a feature extraction module, such as the feature extraction module  214 , extracts raw global features from a plurality of images of an image space. The raw global features includes, in embodiments, gray block features, edge directional histograms, and non-edge-pixel ratios. Other raw global features may be used without departing from the scope of embodiments. 
     AT  404 , the feature extraction module compresses the raw global features into corresponding compact descriptors of the plurality of images. In embodiments, PCA is used to along with a PCA transfer matrix, which can be learned using a suitably sized sample of images. 
     At  406 , the feature extraction module quantizes the compact descriptors using mean values of dimensions of the compact descriptors to generate signatures for the plurality of images. 
     At  408 , a partition module, such as the partition module  216 , partitions the image space into a plurality of coarse clusters such that groups of images with matching signatures are placed together into coarse clusters. 
     At  410 , a cluster module, such as the cluster module  218 , initializes the images within the coarse clusters as belonging to separate refined clusters. Thus, in an initial state, one or more images within a coarse cluster are initialized to be in separate refined clusters. 
     At  412 , the cluster module performs pair-wise comparisons between images within the coarse cluster, according to the ε-clustering algorithm. 
     At  414 , the cluster module adds images that are within a predetermined threshold distance of each other into the same refined cluster. If one or both of the images are in refined clusters with more than one image, the refined clusters are merged such that all images in both clusters are merged into one refined clusters. 
     At  416 , a growth module, such as the growth module  220 , creates pseudo queries for the refined clusters by averaging the compact descriptors of the images within the refined clusters. Because the compact descriptors of the images within a particular refined cluster will have little variance, the average compact descriptor is sufficiently representative of the refined cluster. 
     At  418 , the growth module identifies coarse clusters that are similar to the refined clusters. Identifying the similar coarse clusters includes determining a Hamming distance between quantized binary signatures of average compact descriptors of the refined clusters and signatures associated with the coarse clusters. Those coarse clusters that are within a predetermined Hamming distance from the quantized binary signature of a particular refined cluster are identified as similar coarse clusters with respect to the particular refined cluster. 
     At  420 , the growth module searches in the similar coarse clusters for images to add to the refined clusters. The searching includes determining whether the compact descriptors of the images in the similar coarse clusters are sufficiently similar to the pseudo query. This is repeated for each refined cluster for which similar coarse clusters are identified. Also, since one or more refined clusters are identified for each coarse cluster, the process of cluster growth (searching in similar clusters for images to add to a refined cluster) is performed on each refined cluster of each coarse cluster. 
     At  422 , an output module, such as the output module  422 , outputs the refined clusters as sets of duplicate images. 
       FIGS. 3 and 4  depict flow graphs that show example processes in accordance with various embodiments. The operations of these processes are illustrated in individual blocks and summarized with reference to those blocks. These processes are illustrated as logical flow graphs, each operation of which may represent a set of operations that can be implemented in hardware, software, or a combination thereof In the context of software, the operations represent computer-executable instructions stored on one or more computer storage media that, when executed by one or more processors, enable the one or more processors to perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, modules, components, data structures, and the like that perform particular functions or implement particular abstract data types. The order in which the operations are described is not intended to be construed as a limitation, and any number of the described operations can be combined in any order, separated into sub-operations, and/or performed in parallel to implement the process. Processes according to various embodiments of the present disclosure may include only some or all of the operations depicted in the logical flow graph. 
     Computer-Readable Media 
     Depending on the configuration and type of computing device used, memory  204  of the computing system  200  in  FIG. 2  may include volatile memory (such as random access memory (RAM)) and/or non-volatile memory (such as read-only memory (ROM), flash memory, etc.). Memory 204 may also include additional removable storage and/or non-removable storage including, but not limited to, flash memory, magnetic storage, optical storage, and/or tape storage that may provide non-volatile storage of computer-readable instructions, data structures, program modules, and other data for computing system  200 . 
     Memory  204  is an example of computer-readable media. Computer-readable media includes at least two types of computer-readable media, namely computer storage media and communications media. 
     Computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any process or technology for storage of information such as computer-readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, phase change memory (PRAM), static random-access memory (SRAM), dynamic random-access memory (DRAM), other types of random-access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, compact disk read-only memory (CD-ROM), digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information for access by a computing device. 
     In contrast, communication media may embody computer-readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave, or other transmission mechanism. As defined herein, computer storage media does not include communication media. 
     CONCLUSION 
     Although the disclosure uses language that is specific to structural features and/or methodological acts, the invention is not limited to the specific features or acts described. Rather, the specific features and acts are disclosed as illustrative forms of implementing the invention.