Hacker Newsnew | comments | show | ask | jobs | submit login

I have a small algorithm to make the comparisons more efficient, assuming you just bruteforce right now. I don't know the name of it.

Preparation, this code sets hash[y][x] to the sum (overflow is ok) of all pixel values in the region to the top left of the pixel at x,y.

This should done for both the image and the thing we want to find in it.

hash[0][0] = pixel[0][0];

for (x=1; x < width; ++x) {

hash[0][x] = hash[0][x-1] + pixel[0][x];

}

for (y = 1; y < height; ++y) {

hash[y][0] = hash[y-1][0] + pixel[y][0];

for (x = 1; x < width; ++x) {

hash[y][x] = hash[y][x-1] + hash[y-1][x] - hash[y-1][x-1] + pixel[y][x];

}

}

Now, when we look for a match for a small image , we could check if the sum of the pixels match by doing following comparison

hashSmallImg[smallheight-1][smallwidth-1] == hash[offsetY+smallheight-1][offsetX+smallwidth-1] - hash[offsetY][offsetX+smallwidth-1] - hash[offsetY+smallheight-1][offsetX] + hash[offsetY][offsetX]

If this fails we know for sure the pixels wont match.

Illustrated: http://i.imgur.com/dHMKj.png

A 2-dimensional state machine might be possible, but I don't know how.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: