Search image pattern

Question

Hi people!!

I need to do a program that do this: given an image (5*5 pixels). I have to search how many images like that exists 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 paralell computing, to search in the 4 angles (0º, 90º, 180º and 270º)

Waht is the best way to do that?

Thanks for the help. Best reagrds.

Answer 1

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.

Answer 2

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 efficent 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.

Skizz

Answer 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.

Answer 4

There are a given number of Tetris block patterns. For each pattern, there are four variations: not rotated, rotated 90, rotated 180 and rotated 270 degrees.

Construct four arrays, one for each rotation. Each array will contain pointers to all patterns for a given rotation.

If I understand your problem correctly, there is no need for approximate matching. You want to see if a given candidate block image matches any of the Tetris blocks in any way. So, the comparison can be done using the trusty xor.

The code below shows the comparison function for unrotated patterns. Clearly, I did not type in all the patterns (although I found http://www.colinfahey.com/tetris/tetris_diagram_pieces_orientations_new.jpg via Google). That part is up to you.

The multi-threaded version of this program would have separate functions for comparing rotated versions accessing four separate arrays of patterns.

#include <stdio.h>

#define DIM 5

unsigned char blocks[][DIM] = {
    { 0x00, 0x00, 0x04, 0x0e, 0x00, },
    { 0x10, 0x10, 0x10, 0x10, 0x10, }, 
};

int compare_block(
        unsigned char src[DIM], 
        unsigned char candidate[DIM] ) {
    int i;
    int result = 0;

    for ( i = 0; i < DIM; ++i ) {
        result += src[i] ^ candidate[i];
    }

    return !result;
}

int main(void) {
    int i;
    unsigned char candidate[] = { 0x00, 0x00, 0x04, 0x0e, 0x00, };

    for ( i = 0; i < sizeof blocks/sizeof blocks[0]; ++i ) {
        int result = compare_block(blocks[i], candidate);
        printf("Candidate %s block %d\n", 
                (result ? "matched" : "did not match"),
                i
              );
    }
    return 0;
}

Answer 5

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.