Google Answers Logo
View Question
 
Q: c++ bitmap search ( No Answer,   1 Comment )
Question  
Subject: c++ bitmap search
Category: Computers > Algorithms
Asked by: chilltown-ga
List Price: $10.00
Posted: 08 Nov 2005 13:08 PST
Expires: 08 Dec 2005 13:08 PST
Question ID: 590667
This question is regarding bitmaps in a win32 application.  I am
looking for an efficient way to search an active window for a given
24bit bitmap.  For example, does the current webpage contain bitmap X
anywhere in the window?  Currently I am creating a compatible DC to
the window to be searched, then creating compatable bitmap and loading
the bitmap to be searched for into it.  Then I am literally searching
the target window pixel by pixel for one that matches pixel 0,0 of the
created source bitmap.  Once I find a match I move to the second pixel
etc until a match is found or the entire window has been searched. 
This works fine when, say, searching for a 20x20 pixel bitmap in maybe
only the top-left quad of a window, but when searching for larger
bitmaps or larger areas of the window, this process is taking too long
for my application needs.  Are there any suggestions to improve?  Are
there any libraries developed for this type of search?
Answer  
There is no answer at this time.

Comments  
Subject: Re: c++ bitmap search
From: doopdoop-ga on 08 Nov 2005 14:24 PST
 
If you are only looking for EXACT matches, you can use an appropriate
pattern matching algorithm like Rabin-Karp

See:
http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm
http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node43.html#stringSearchRK

Usually, only the one-dimensional case is shown, but it can be adapted
to 2D, if the hash update procedure is changed. It should not be that
hard to do.
For a small (constant) number of possible results, this algorithm is
linear on the image size.
If you have only few colors (e.g. black and white) you might consider
adapting Boyer-Moore. If you have a relative small pattern and a
fairly large image, Knuth-Morris-Pratt might be for you. Both only
work for 1D pattern, but you could start with searching for a line
from the pattern first, and then test, whether the whole pattern match
at this position. Google will help.

The problem of finding ALMOST exact patterns in images is know as
"template matching" in computer vision. Usually,
cross-correlation-based methods are used. Look e.g. for the free
OpenCV library, which implements such methods.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy