Search for an image template
I need to make a program that does this: given an image (5 * 5 pixels), I need to search how many images like this exist in another image composed by many other images. That is, I need to search for a given pattern in the image.
The language to use is C. I need to use parallel computation to search for 4 angles (0º, 90º, 180º and 270º).
What's the best way to do this?
a source to share
Seems straightforward.
- Create 4 versions of the image, rotated 0 °, 90 °, 180 ° and 270 °.
- Start four streams with one version of the image.
- For all positions from
(0,0)
to(width - 5, height - 5)
- Comapare 25 pixels reference image with 25 pixels at the current position
- If they are fairly equal using some metric, please report it.
a source to share
Use normalized correlation to determine pattern matching.
@Daniel, Daniel's solution is suitable for multiple CPU usage. He does not mention a quality metric that would be useful, and I would like to suggest one quality metric that is very common in image processing.
I suggest using the normalized correlation [1] as a comparison indicator as it outputs a number between -1 and +1. Where 0 there is no correlation 1 will be output if the two patterns were identical, and -1 would be if the two patterns were exactly opposite.
After calculating the normalized correlation, you can check if you have found a pattern by performing either a threshold test or a peak-average test [2].
[1 - footnote] How do you implement normalized correlation? It's pretty simple and only has two loops. If you have an implementation that is good enough, you can test your implementation by checking if an identical image will get 1.
[2 - footnote] You are doing the max (array) / average (array_without_peak) ratio. Then a threshold to make sure you have a good ratio to the mean.
a source to share
There is no need to create additional three versions of the image, just refer to them differently or use something like the class I created here . Better yet, just duplicate the 5x5 matrix and rotate them. Then you can linearly scan the image for all rotations (which is good).
This issue will not scale well for parallel processing as the bottleneck is certainly accessing the image data. Having multiple threads accessing the same data will slow them down, especially if the threads are "out of sync"; One stream will pass through the image than the other streams so that the other streams will finish reloading the data that the first stream has discarded.
So the solution that I think will be most efficient is to create four threads that scan 5 lines of the image, one thread per revolution. The fifth thread loads the image data one line at a time and passes the line to each of the four scan threads, waiting for all four threads to complete, i.e. loads one image line, appends to five line buffers, starts four scan threads, wait for the threads to finish, and repeat them until all image lines are read.
a source to share