Sign in to follow this  

Image Comparison

This topic is 3843 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, I am new to image manipulation stuff. I have done some programming in the past in Java/XML etc. I am trying to write an algorithm for image comparison in realtime. Any ideas where I can start with? any decent tutorials available I can refer to? I want the algorithm to be able to search a local drive of images and find exact similarities with other images. regards,

Share this post


Link to post
Share on other sites
Machine vision, statistics, heuristics and artificial intelligence would be the topics look into. Many of those also require somewhat advanced mathematical background.

The only tutorial level documents you might find will simply use pixel-wise comparison to determine the RMS deviation between two images, but will be unable to compare images of different size.

Main problem here comes from "exact similarities". While somewhat trivial for human, expressing similarity is a very big problem for a computer.

Also, what does real-time mean? From a video camera live feed? Difficult.

Trying to build face recognition software or other pattern matching system isn't an easy task. 98% of the application is trivial. Unfortunately, the 2% comes down to actually comparing the images, which is still a very active research topic.

Share this post


Link to post
Share on other sites
Antheus speaks the truth. Tell us what is required of your image comparison routines and we'll be able to give more specific advice. I hope you're not scared of a little mathematics.

Most of the work of general image comparison comes down to pattern-matching and majorisation representation. These both hinge on spectral decompositions of image matrices, so that only the salient information is passed to the image-distance metric (so you are comparing the general form of the images and not the background noise). Fortunately for you, the first part of this process is exactly image compression, so you immediately have a whole bunch of resources at your disposal.

A fairly simple, but general system would do something like this:

1. Determine the colour-gamuts of the two images and transform them both to a 'canonical domain', so that the two images look like they came from the same palette.
2. Perform a generalised Q-transform (it closely related to the Fourier transform) on the two images so that a linear comparison can detect matching pieces. For each suitably similar pair of pieces:
3. Scale the two images onto yet another canonical domain, so that the pieces now have the same dimensions, colours and gamma.
4. Filter the two images to remove noise and invisible high-frequency data. A simple JPEG compression would do the trick, but there are faster methods.
5. Compare the images pixel-wise, perhaps by a (colour-component-weighted) RMS difference in the YCC colour-space.

Any number of these steps may be simplified or discarded depending on the nature of the source images. In particular, you'd like to do away with the pattern-matching if possible, as it's computationally costly and rather error-prone.

Admiral

Share this post


Link to post
Share on other sites
explaining a bit further!!

here is what I have in mind

1- upload an image to an interface
2- perform a search based on the uploaded image. This will result in all the images in the repository compared to the primary image.
3- return matching images.
These steps would form the core functionality. I would then want to (if possible) add features such return images higher/lower than a certain resolution, quality, type (gif, jpeg etc) and percentage of similarity (50% similar, 90% similar etc

The idea I have (although in its infancy and widely open to ideas that would make my life easier) is use something like image slicing so keep slicing an image into equal cubes on the basis of N(exp)2.

Not sure if I am making any sense.

Dont know what I really meant with real-time (maybe it was just to emphasize the fact that I want a very efficient algorithm) - not like the windows search which takes years to return results

I appreciate your help!

Share this post


Link to post
Share on other sites
Quote:
Original post by sshah
explaining a bit further!!

here is what I have in mind

1- upload an image to an interface
2- perform a search based on the uploaded image. This will result in all the images in the repository compared to the primary image.
3- return matching images.
These steps would form the core functionality. I would then want to (if possible) add features such return images higher/lower than a certain resolution, quality, type (gif, jpeg etc) and percentage of similarity (50% similar, 90% similar etc



Heh, all easy. Except for 2).

What is "similarity"?

Does deviation in brightness mean two images are similar? Or are you interested in facial features, where an old BW photograph can be 100% identical to HD DVD video cap?

Forget formats, forget UI, even language and the rest.

This is typically done by transforming the image into some context dependant vector space. How this transformation is performed depends on the context. You then use a library that contains pre-calculated vectors for various criteria, then compare those to the picture you're interested in.

The most trivial transformation that yields somewhat practical results, is comparing resolution independant (scaled to pre-determined size) image, then doing RMS pixel-wise comparison, preferably in YUV format to emphasize the features - which also allows you to normalize the brightness of the Y channel.

So, simply put:
- Resize image to (w, h)
- Convert to YUV
- Perform normalization on Y channel
- Do pixelwise comparison between this image and every image in library, calculating RMS deviation.

The other is to extract features. There's several image classification algorithms, where you pre-process the image searching for edges, corners, or other distint elements.

Then you compare those with same types of elements stored in the library. After you find suitable candidates, you can resize/align images to fit each other, and perform more complex pixel-wise comparison.

The second method is considerably better, since it will, in many cases, be oblivious to rotation, scaling, even shear or other transforms, plus it allows you to search for parts of image only.

But all this is just high level talk. There's so many details here that are highly dependant on the purpose of your application.

Keep in mind that simply offsetting an image by 1 pixel can cause simple algorithms to fail completely.

But the key to this problem is determining "similarity". The word has no meaning, the key is devising an algorithm that will express that.

Share this post


Link to post
Share on other sites
As a demonstration of how much you shouldn't expect, I'll give you a few links.

An air-fan photo site has a 'similarity search' which uses an algorithm similar to what you seem to be looking for to find similar images (by using data in the photograph, rather than meta-data -- although such a search is available).

I took this photo some years ago. Clicking to find similar photos yields these results -- some of which are good, some of which aren't. However, neither of the following images (which are virtually identical to the human eye) show up high in the results: One, two.

Share this post


Link to post
Share on other sites

This topic is 3843 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this