14

I am thinking about creating a database system for images where they are stored with compact signatures and then matched against a "query image" that could be a resized, cropped, brightened, rotated or a flipped version of the stored one. Note that I am not talking about image similarity algorithms but rather strictly about duplicate detection. This would make things a lot simpler. The system wouldn't care if two images have an elephant on them, it would only be important to detect if the two images are in fact the same image.

Histogram comparisons simply won't work for cropped query images. The only viable way to go I see is shape/edge detection. Images would first be somehow discretized, every pixel being converted to an 8-level grayscale for example. The discretized image will contain vast regions in the same colour which would help indicate shapes. These shapes then could be described with coefficients and their relative position could be remembered. Compact signatures would be produced out of that. This process will be carried out over each image being stored and over each query image when a comparison has to be performed. Does that sound like an efficient and realisable algorithm? To illustrate this idea:

removed dead ImageShack link

I know this is an immature research area, I have read Wikipedia on the subject and I would ask you to propose your ideas about such an algorithm.

SuperBiasedMan
  • 9,814
  • 10
  • 45
  • 73
Blagovest Buyukliev
  • 42,498
  • 14
  • 94
  • 130
  • 3
    You say you're not talking about similarity algorithms, but duplicate detection. Yet, if you're also talking about allowing changes, especially cropping, you're inevitably going to have to make a judgement about degree of "similarity". – Craig McQueen Feb 08 '10 at 03:21
  • Without a doubt there will be acceptable thresholds when doing the comparisons. The thing is, even a cropped and resized query image still contains a subset of the same shapes/areas of interest, positioned relatively in the same way, but represented with a different amount of pixels. – Blagovest Buyukliev Feb 08 '10 at 10:09

3 Answers3

7

SURF should do its job.

http://en.wikipedia.org/wiki/SURF

It is fast an robust, it is invariant on rotations and scaling and also on blure and contrast/lightning (but not so strongly).
There is example of automatic panorama stitching.

Check article on SIFT first
http://en.wikipedia.org/wiki/Scale-invariant_feature_transform

Luka Rahne
  • 10,336
  • 3
  • 34
  • 56
2

If you want to do a feature detection driven model, you could perhaps take the singular value decomposition of the images (you'd probably have to do a SVD for each color) and use the first few columns of the U and V matrices along with the corresponding singular values to judge how similar the images are.

Very similar to the SVD method is one called principle component analysis which I think will be easier to use to compare between images. The PCA method is pretty close to just taking the SVD and getting rid of the singular values by factoring them into the U and V matrices. If you follow the PCA path, you might also want to look into correspondence analysis. By the way, the PCA method was a common method used in the Netflix Prize for extracting features.

Justin Peel
  • 46,722
  • 6
  • 58
  • 80
1

The article you might be referring to on Wikipedia on feature detection.

If you are running on Intel/AMD processor, you could use the Intel Integrated Performance Primitives to get access to a library of image processing functions. Or beyond that, there is the OpenCV project, again another library of image processing functions for you. The advantage of a using library is that you can try various algorithms, already implemented, to see what will work for your situation.

Chris O
  • 5,017
  • 3
  • 35
  • 42
  • Trying out different processing functions isn't the point. I would be interested if you have a particular idea, even a very sparse one to achieve the task. – Blagovest Buyukliev Feb 08 '10 at 02:48
  • Can you take the frequency components from both the target and query images, and do "some sort of comparison"? Yup, this is very sparse, it's been awhile. Doing this is computational intensive ;-) – Chris O Feb 08 '10 at 03:15