Geometric Consistent Tree Partitioning Min-Hash for Large-Scale Partial Duplicate Image Discovery

This paper introduces a novel method that effectively and efficiently encodes the spatial geometric information of bag of visual words (BoW) to boost the performance of large scale partial duplicate image discovery and clustering. The loose cyclic spatial verification (LCSV) technique projects the locations of BoWs onto the perimeter of a circle centred around their geometric centroid and encodes their geometric relations in a simple ordered sequence of scalar values. We then treat the problem of validating the geometric consistencies of the BoWs from two separate image patches as the longest common cyclic subsequence (LCCS) problem and solve it using dynamic programming. By embedding the LCSV technique in a modified tree partitioning min-Hash framework, we introduce a geometric consistent tree partitioning min-Hash (gcTmH) technique forpartial duplicate image discovery and clustering. We show that gcTmH is invariant to rotation and scaling, robust against noisy conditions, and is able to handle multiple duplicate models. We show that gcTmH can boost the accuracy of partial duplicate image discovery by deleting the random and false matching image pairs in a very efficient way. We present experimental results on two datasets and show that our method can boost partial duplicate image discovery performances of state of the art techniques.