c++ bitmap search
Category: Computers > Algorithms
Asked by: chilltown-ga
List Price: $10.00
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?
|There is no answer at this time.|
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.
If you feel that you have found inappropriate content, please let us know by emailing us at firstname.lastname@example.org with the question ID listed above. Thank you.
|Search Google Answers for|