Near Duplicate Detection

Chris Pal David Rim

Introduction

We have been working in a collaboration with Eastman House, in building a Wiki to promote research in photography among museum curators, photography researchers and students. The wiki has broad scope, bringing together expert knowledge about photographers and their work and methods. Automating some of the tasks in bringing together this knowledge is a key component in making the wiki both useful and easy to maintain. It is also has given rise to extensive computer vision and natural language applications. For the past semester, we have focused on image comparison, that is, how to detect duplicate images and specifically, how to detect if images are in fact prints of an identical negative. We have developed an application which detects if images are prints of a negative and then displays the duplicates registered with each other in order to give viewers an idea of how the different print making decisions effect the impact of an image.

Abstract

Image duplicate detection can be achieved via landmark or keypoint extraction using simple geometric consistency and verication checks. This can be applied efficiently to the following problem: given a set of images can we determine which came from the same negative? A Bayesian approach to matching might be possible if we consider the underlying mechanism to be a generative process which produces the set of possible matching points We can imagine that the set of candidate matches are generated by two independent processes, one of which corresponds to the an affine trans- formation and a noise generating process. We show that posing this problem in this way produces a robust and efficient estimate. Furthermore our approach leads directly to a formulation that is identical to an iterative weighted least squares procedure, which captures the intuition nicely in a formal way.

Problem

Given two photographs, can we automatically tell if they are prints of an identical negative? This has applications in the study of photographic images.

Local Features

The general outline is to compute local features

Generate a rough set of candidate matches using sum of squared distances nearest neighbor algorithm.

Verifying Matched Features

If the candidates were generated from an affine transform, then we can use this information in a probabilistic model. That is, viewing the problem as a mixture of Gaussians.
Where is the cluster probability and is the affine transformation associated with cluster C.

Viewed in this way, deriving the EM update rules for results in

The above can be interpreted as a weighted least squares algorithm where each is the point estimate of the likelihood of belonging to cluster k.

Compared to standard approaches, the solution recovered by the above is robust to outliers. We use RANSAC to verify the approach.

URCS People | URCS Home Page