The 2 images have same color,pattern,etc. One image is cropped from the other one. The algorithms I've found mostly use location to compare difference between images, so it produces false result for cropped image. How to know those 2 images are similar?
Thanks
It would be helpful to know more about your problem domain. For example, are you trying to pick out which of a 100 images the cropped sample came from? Or do you not even know if the cropped sample will have come from any of the images in your library?
I'm not an image processing expert, but I have worked with one or some stuff. The first thing that comes to mind is that you could try doing some kind of color averaging to see if you can create a huristic that lets you find likely candidates.
Find the average RGB of the cropped sample. Then to see if it might be a match with a sample, find the local RGB color average in a number of spots in the image. If your cropped RBG average is too far off from all the local averages in an image, it's not very likely that they are related.
Once you narrow down a few candidates, finding the exact location will still be tricky. Try working on sub-sampled versions of the images. If the orig. image is 2000x2000, sub-sample both images by 10 to get a 200x200 main image. Do the same subsample for the cropped image and see where you get a best fit. Then iteratively reduce the amount of sub-sampling and fine tune the exact location your cropped image came from. You are still doing some brute force, but it's on an image 100 times smaller.
Yikes! I beat my head against this one many years ago and never came up with a viable answer for my problem. I have had some thoughts since that I haven't tried to implement and I'll throw them out just in case they do you any good:
I disagree with Al Crowley's statement about the average RGB values--the cropping could very well be the removal of an object that was quite different than the target.
Furthermore, an observation: Reducing images to an 8x8 thumbnail (not that it's big enough for human eyes) and taking the square of the difference of each component does a pretty good job of picking out duplicates and often works even with small crops around the edge. Ideally contrast should be normalized before doing the thumbnail, I didn't do it and found it was declaring a bunch of low-contrast images to be dupes of each other when they had no similarity at all. This approach uses only 192 bytes per image and thus allows you to compare a large number of images in memory although it's still an O(n^2) algorithm. (I made it so you could close the program at any time, it would dump the state info and shut down, next time it would resume where it left off.)
Given what you are describing as a problem I would be inclined to try taking a set of test crops of the image and running the comparison against each crop. When you find a likely candidate then start working with bigger images and try to narrow it down by jogging a few pixels and seeing if it gets better or worse. I can't imagine anything other than very slow performance from such a routine.