Image Comparison

[toddmcleod]

Hello Everyone,

I’m trying to do the Lynda.com “code clinic” challenges.

I’m stuck on the image comparison challenge and could use some help.

This is my solution so far.

And here are the images I’m comparing - credit to Lynda.com for the images:

The goal:

Find a “needle” in a “haystack.”

Both the “needle” and the “haystack” are images.

My approach: take the top left pixel of the needle, then compare that to every pixel in the haystack. When there’s a match, start comparing the sequence of pixels that follow, comparing them across the row. As matching continues to be successful, compare the next row, and the next row, etc. Keep comparing successive rows until matching fails.

To create a visual representation of the “needle” image matching / not matching in the “haystack” image, I wanted to create a new image, copy the “haystack” image into it, and then change that new image to reflect where, if anywhere, the “needle” image matches it.

After I get this working with these two images, I want to be able to run it against a directory with several images to find matches.

I think I’m pretty close to a cool solution here. I wanted to do this with just the standard library, build it from the ground up, and not rely on some third-party package.

If you can help me get this code running, I’ll buy you a beer!

Thank you,
Todd

[matt (Matt Holt)]

Looks like a good start. I’m not really sure what you’re asking for specifically, so I’ll just comment my own thoughts. Since it looks like this runs on photographs on the scale of “megapixels” and you’re doing this in Go, I would suggest a few things to boost speed (without having actually tried your program; sorry):

• Consider checking every x pixels where 2 <= x <= 5 for instance. This should give you a solid linear speedup with results comparable to x=1 (but it depends on the picture).
• Do the scanning in parallel - I bet you can halve your scanning time by running on two cores, for example. Have each worker scan a different part of the haystack.
• Stop scanning when there’s no way the needle can be in that position in the haystack. This loop is where you’re going to feel the “mega” number of pixels, so once you’re in a part of the haystack image such that the top-left corner of the needle could not possibly be there because there’s not enough height below or to the right, stop searching that row/column.

To show where in the haystack the needle is, it would be cool if you reduced brightness on the haystack except for where the needle is.

[Egon (Egon Elbre)]

Here’s a tip.

How would you solve this when the image height for the needle and haystack were 1, and you had only grayscale?

[toddmcleod]

Thank you!