Systems and methods for clustering of near-duplicate images in very large image collections

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.