File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Find know image in a bigger image

 
Joris Cools
Greenhorn
Posts: 8
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9476
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Tim Moores
Bartender
Pie
Posts: 2495
9
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9476
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 47258
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And welcome to the Ranch
 
Joris Cools
Greenhorn
Posts: 8
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic