1

I need to do a program that does this: given an image (5*5 pixels), I have to search how many images like that exist in another image, composed by many other images. That is, i need to search a given pattern in an image.

The language to use is C. I have to use parallel computing to search in the 4 angles (0º, 90º, 180º and 270º).

What is the best way to do that?

Scott Stensland
  • 26,870
  • 12
  • 93
  • 104
Ricardo Felgueiras
  • 3,589
  • 6
  • 25
  • 27

4 Answers4

5

Seems straight forward.

  • Create 4 versions of the image rotated by 0°, 90°, 180°, and 270°.
  • Start four threads each with one version of the image.
  • For all positions from (0,0) to (width - 5, height - 5)
    • Comapare the 25 pixels of the reference image with the 25 pixels at the current position
    • If they are equal enough using some metric, report the finding.
Daniel Brückner
  • 59,031
  • 16
  • 99
  • 143
3

Use normalized correlation to determine a match of templates.

@Daniel, Daniel's solution is good for leveraging your multiple CPUs. He doesn't 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 normalized correlation[1] as a comparison metric because it outputs a number from -1 to +1. Where 0 is no correlation 1 would be output if the two templates were identical and -1 would be if the two templates were exactly opposite.

Once you compute the normalized correlation you can test to see if you have found the template by doing either a threshold test or a peak-to-average test[2].

[1 - footnote] How do you implement normalized correlation? It is pretty simple and only has two for loops. Once you have an implementation that is good enough you can verify your implementation by checking to see if the identical image gets you a 1.

[2 - footnote] You do the ratio of the max(array) / average(array_without_peak). Then threshold to make sure you have a good peak to average ratio.

Trevor Boyd Smith
  • 18,164
  • 32
  • 127
  • 177
1

There's no need to create the additional three versions of the image, just address them differently or use something like the class I created here. Better still, just duplicate the 5x5 matrix and rotate those instead. You can then linearly scan the image for all rotations (which is a good thing).

This problem will not scale well for parallel processing since the bottleneck is certainly accessing the image data. Having multiple threads accessing the same data will slow it down, especially if the threads get 'out of sync', i.e. one thread gets further through the image than the other threads so that the other threads end up reloading the data the first thread has discarded.

So, the solution I think will be most efficient is to create four threads that scan 5 lines of the image, one thread per rotation. A fifth thread loads the image data one line at a time and passes the line to each of the four scanning threads, waiting for all four threads to complete, i.e. load one line of image, append to five line buffer, start the four scanning threads, wait for threads to end and repeat until all image lines are read.

Community
  • 1
  • 1
Skizz
  • 69,698
  • 10
  • 71
  • 108
  • I meant in memory rotation because different indexing for different threads using the same code will become a little bit messy... – Daniel Brückner May 20 '09 at 15:44
  • I too was refering to in-memory rotation. Using the class in the link in the post will make the code far simpler, just a rotation parameter for each instance of the processing thread. Having said that, the rotating the 5x5 matrix instead is even more efficent. – Skizz May 20 '09 at 16:05
0

5 * 5 = 25

25 bits fits in an integer.

each image can be encoded as an array of 4 integers.

Iterate your larger image, (hopefully it is not too big), pulling out all 5 * 5 sub images, convert to an array of 4 integers and compare.

EvilTeach
  • 28,120
  • 21
  • 85
  • 141