# US 10,504,002 B2 · Systems and methods for clustering of near-duplicate images in very large image collections > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,504,002 B2 - Document ID: US10504002B2 - Status: Granted - Kind: B2 - Application number: 15/663,815 - Filed: 2017-07-30 - Published: 2019-01-31 - Granted: 2019-12-10 - Earliest claimed: 2017-07-30 - Assignees: Fuji Xerox Co., Ltd. - Applicants: Fuji Xerox Co., Ltd. - Inventors: Andreas Girgensohn - Web page: https://patentgrep.com/patent/US10504002B2 ## CPC - G06F 16/55: Clustering; Classification - G06F 18/22: Matching criteria, e.g. proximity measures - G06F 18/231: Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram - G06F 18/24: Classification techniques - G06V 10/462: {Salient features, e.g. scale invariant feature transforms [SIFT]} - G06V 10/464: {using a plurality of salient features, e.g. bag-of-words [BoW] representations} - G06V 10/50: by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis - G06V 10/761: {Proximity, similarity or dissimilarity measures} - G06V 10/7625: {Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract Detection of near-duplicate images is important for detecting the reuse of copyrighted material. Some applications require the clustering of near-duplicates instead of the comparison to an original. Representing images as bags of visual words is the first step for our clustering approach. An inverted index points from visual words to all the images containing that visual word. In the next step, matches are geometrically verified in pairs of images that share a large fraction of their visual words. Geometric verification may use affine, perspective, or other transformations. The verification step provides a similarity measure based on the fraction of the matching image points and on their distributions in the compared images. The resulting distance matrix is very sparse because most images in the collection are not compared to each other. This distance matrix is used as input for modified agglomerative hierarchical clustering approach that can handle a sparse distance matrix. ## Claims ### Claim 1 A computer-implemented method for clustering a plurality of images, the computer-implemented method being performed in connection with a computerized system comprising a central processing unit and a memory, the computer-implemented method comprising: a. generating a vocabulary of visual words in the plurality of images; b. extracting image features for image key points for each of the plurality of images; c. based on the extracted image features, creating an index pointing from the visual words in the vocabulary to images from the plurality of images, which contain these visual words; d. using the created index to collect all other images of the plurality of images that share at least one visual word with a selected image and determining a number of shared visual words; e. performing a geometric verification to verify whether the shared visual words are located at same locations in the selected image and the other images of the plurality of images and taking a fraction of verified shared visual words to all shared visual words as a similarity measure; and f. clustering the plurality of images hierarchically based on the similarity measure. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the vocabulary of visual words is generated from a set of image features extracted from a collection of representative images. ### Claim 3 (depends on 2) The computer-implemented method of claim 2, wherein the collection of representative images comprises at least one million images. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, wherein generating the vocabulary of visual words comprises clustering similar feature vectors and representing all feature vectors similar to each cluster centroid with a visual word and adding that visual word to the vocabulary of visual words for each cluster. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein the image features for image key points are extracted for the each of the plurality of images using a scale-invariant feature transform (SIFT). ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the index pointing from the visual words in the vocabulary to images from the plurality of images is an inverted index. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, further comprising sorting the collected other images of the plurality of images that share at least one visual word with a selected image based on the number of the shared visual words. ### Claim 8 (depends on 7) The computer-implemented method of claim 7, further comprising selecting a predetermined number of the collected other images with top numbers of the shared visual words. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, wherein performing the geometric verification comprises determining an affine transformation that maps at least a portion of the selected image to another image of the plurality of images. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, wherein performing the geometric verification comprises determining a perspective transformation that maps at least a portion of the selected image to another image of the plurality of images. ### Claim 11 (depends on 1) The computer-implemented method of claim 1, further comprising verifying uniformity of distribution of the shared visual words over the other images and rejecting the other images with uniformity of distribution of the shared visual words below a predetermined threshold. ### Claim 12 (depends on 11) The computer-implemented method of claim 11, wherein the verifying uniformity of distribution of the shared visual words over the other images comprises dividing the other images into a coarse two-dimensional grid comprising a plurality of cells, and for each grid cell, determining a fraction of matching visual words to the total visual words in that cell, and performing a statistical test for sufficient uniformity of the distribution of the shared visual words among the grid cells. ### Claim 13 (depends on 1) The computer-implemented method of claim 1, wherein the clustering the plurality of images is performed using a modified complete-linkage agglomerative hierarchical clustering algorithm. ### Claim 14 (depends on 1) The computer-implemented method of claim 1, wherein the clustering the plurality of images is performed using a sparse distance matrix calculated based on the similarity measure. ### Claim 15 A computerized system for clustering a plurality of images, the computerized system comprising a central processing unit and a memory storing a set of computer-executable instructions for: a. generating a vocabulary of visual words in the plurality of images; b. extracting image features for image key points for each of the plurality of images; c. based on the extracted image features, creating an index pointing from the visual words in the vocabulary to images from the plurality of images, which contain these visual words; d. using the created index to collect all other images of the plurality of images that share at least one visual word with a selected image and determining a number of shared visual words; e. performing a geometric verification to verify whether the shared visual words are located at same locations in the selected image and the other images of the plurality of images and taking a fraction of verified shared visual words to all shared visual words as a similarity measure; and f. clustering the plurality of images hierarchically based on the similarity measure. ### Claim 16 (depends on 15) The computerized system of claim 15, wherein the vocabulary of visual words is generated from a set of image features extracted from a collection of representative images. ### Claim 17 (depends on 15) The computerized system of claim 15, wherein the collection of representative images comprises at least one million images. ### Claim 18 (depends on 15) The computerized system of claim 15, wherein generating the vocabulary of visual words comprises clustering similar feature vectors and representing all feature vectors similar to each cluster centroid with a visual word and adding that visual word to the vocabulary of visual words for each cluster. ### Claim 19 (depends on 15) The computerized system of claim 15, wherein the image features for image key points are extracted for the each of the plurality of images using a scale-invariant feature transform (SIFT). ### Claim 20 A non-transitory computer-readable medium embodying a set of computer-executable instructions, which, when executed in a computerized system comprising a central processing unit and a memory, cause the computerized system to perform a method for clustering a plurality of images, the method comprising: a. generating a vocabulary of visual words in the plurality of images; b. extracting image features for image key points for each of the plurality of images; c. based on the extracted image features, creating an index pointing from the visual words in the vocabulary to images from the plurality of images, which contain these visual words; d. using the created index to collect all other images of the plurality of images that share at least one visual word with a selected image and determining a number of shared visual words; e. performing a geometric verification to verify whether the shared visual words are located at same locations in the selected image and the other images of the plurality of images and taking a fraction of verified shared visual words to all shared visual words as a similarity measure; and f. clustering the plurality of images hierarchically based on the similarity measure. ### Claim 21 A computer-implemented method for clustering a plurality of content items, the computer-implemented method being performed in connection with a computerized system comprising a central processing unit and a memory, the computer-implemented method comprising: a. generating a vocabulary of words in the plurality of content items; b. extracting features from the plurality of content items; c. based on the extracted features, creating an index pointing from the words in the vocabulary to content items from the plurality of content items, which contain these words; d. using the created index to collect all other content items of the plurality of content items that share at least one word with a selected content item and determining a number of shared words; e. performing a content verification to verify whether the shared words are located at same locations in the selected content item and the other content items of the plurality of content items and taking a fraction of verified shared words to all shared words as a similarity measure; and f. clustering the plurality of content items hierarchically based on the similarity measure. ### Claim 22 (depends on 21) The computer-implemented method of claim 21, wherein the content items in the plurality of content items are texts. ### Claim 23 (depends on 21) The computer-implemented method of claim 21, wherein the content items in the plurality of content items are audio recordings. ### Claim 24 (depends on 21) The computer-implemented method of claim 21, wherein the content items in the plurality of content items are videos.