Tree partition voting min-hash for partial duplicate image discovery

Discovering partially duplicated images such as those of the same scenes, buildings or objects taken from different angles, distances and vantage points can be very useful in applications such as managing large image repositories and image search on the Internet. In this paper, we present a novel technique for partial duplicate image discovery. The new technique, termed tree partition voting min-hash (TmH), first partitions interest points within an image based on their geometric or photometric (appearance) properties using a spatial partition tree data structure and then finds potential partial duplicate images through a traditional partition min-hash (PmH) method [1]. We have developed a k-d tree partition min-hash (kdTmH) and a random projection tree partition min-hash (rpTmH) technique and have also developed a weighted voting algorithm for improving the similarity measure of a pair of hashing sketches. We present experimental results on 3 datasets and show that TmH significantly outperforms PmH in terms of recall and precision performances without increasing complexity and that the new voting algorithms performs better than sketch matching techniques in the literature.