aspose file tools*
The moose likes Java in General and the fly likes Find know image in a bigger image Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Find know image in a bigger image" Watch "Find know image in a bigger image" New topic
Author

Find know image in a bigger image

Joris Cools
Greenhorn

Joined: Jan 11, 2012
Posts: 8
Hi all,

I want to find a know image (a sub image) in a larger image.

i have written a fairly simple code that searches for all the occurrences.
But the thing is, it's really slow.

Anybody know a faster (and i mean a lot faster) way to do this?



What i know on how to improve this is:
instead of comparing the entire arrays is just to look for the beginning of the array (the image i'm looking for) and see where i find it in the 'canvas'-array (the image i'm looking in).
from these location look for the entire image (the one i'm looking for).

But perhaps you guys (or girls) know a lot faster way.

thanks in advace

Dendeze

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8188
    
  23

Joris Cools wrote:Anybody know a faster (and i mean a lot faster) way to do this?

Well, I suspect there may well be an ImageComparer class out there in Googleland. However, there are also optimized 'substring' searches such as this one, or its rather simpler cousin; and I suspect you could modify either one to work with pixels rather than characters. That said, I still wouldn't expect it to be blazingly fast.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Tim Moores
Rancher

Joined: Sep 21, 2011
Posts: 2408
I wouldn't create PixelGrabber objects for each pixel, because there's no need to compare all pixels of the subimage for each possible location. The common case is that the subimage is *not* found at position (x,y), so that's the case you should make fast. Start by comparing the top-left pixel; if that's not identical the search can move on. If that's identical, proceed around the perimeter and stop as soon as a pixel is found that does not match.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8188
    
  23

Tim Moores wrote:Start by comparing the top-left pixel; if that's not identical the search can move on. If that's identical, proceed around the perimeter and stop as soon as a pixel is found that does not match.

Interesting idea, and probably very well-suited to images. Boyer-Moore similarly works backwards from the far end and so is likely to find mismatches quickly (and also know how much to skip when it does); but it was designed for string searching, not for images.

Winston

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39784
    
  28
And welcome to the Ranch
Joris Cools
Greenhorn

Joined: Jan 11, 2012
Posts: 8
Thank you all, i will try all these tips. All in good times ofcourse.
When i find the time, i'll test these.

@Ritchie: thanks
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Find know image in a bigger image