Where the Shape Hides

You have a small picture of the thing you are looking for — the pattern — and a larger picture to search. The idea from this chapter is to turn the pattern into a filter, slide it across the picture, and read the brightest spot of the feature map as found it here.

Copy the pattern straight into a filter, though, and it rewards brightness rather than shape. Every value in a picture is 0 or more, so a patch of solid white — with no trace of the pattern in it — multiplies large pixels against every positive filter value and outscores the real thing.

So the filter is built differently: subtract the pattern's own average value from every one of its entries. What remains is positive wherever the pattern is brighter than its average and negative wherever it is darker — much like this chapter's edge filter, with its negatives on one side and its positives on the other. For example, the 1×3 pattern [[0, 90, 0]] has average 30 and becomes the filter [[-30, 60, -30]].

Task: write find_pattern(image, pattern), returning [row, col, score] — where the pattern was found, and how strongly.

• image is a grayscale picture: a list of rows of pixel values from 0 to 255. It is not always square.
• pattern is a smaller grayscale picture. Its height and its width are both odd, so every window has a single centre pixel, but the two need not be equal.
• Build the filter as described, then sweep it over image: top-left corner first, one position at a time across and then down, stopping only where the window fits entirely on the picture. At each stop, multiply every pixel by the filter value on top of it and add the products. Nothing is flipped. Round each score to 4 decimal places.
• The winner is the stop with the highest score. That score may be negative: when nothing in the picture resembles the pattern, the least-bad stop still wins and is still reported.
• If several stops share the highest score, the one the sweep reaches first wins — the top-most, and among those the left-most.
• row and col locate the winning window's centre pixel in the coordinates of image itself — not the window's top-left corner, and not its position in the feature map. score is the winning score.

This is the chapter's reading of a feature map turned into code: a bright spot should mean the filter found its pattern here, not the picture was bright here. Building the filter from the pattern's differences from its own average, rather than from the raw pattern, is what keeps those two apart.