# Template Matching non-rectangular template in non-linear order

### Question

Is there an existing algorithm that does cross correlation with two images, including a weight image?

In template matching, when should I prefer the sum of absolute errors vs cross correlation?

### Background

I have a high-resolution image of a world game map, my base image. My game displays an axis-aligned mini-map with noise. The minimap is displayed in a circle, and has a player icon in the center. I want to find where I am in the world game map by issuing a template matching algorithm.

I want to mask out parts of my template that are not relevant. The mask is not rectangular. In fact it is a complex donut like shape, but can be thought of as some generic alpha mask:

This minimap will be downsampled, greyscaled, then compared to the world map using template matching.

Existing template matching algorithms work from left to right, top to bottom, but I want to iterate through the image seeding from a given point, searching outwards and exiting early if a match is already found. The idea is that if I am already given a known location, I can predict where I am on the map without having to traverse the entire image.

// existing template matching algorithm
for x in 0..image.width - template.width {
for y in 0..image.height - template.height {
// cross correlation or squared
let result = cross_correlate(image.view(x, y, template.width, template.height), template);
output[x][y] = result;
}
}


On a 3x3 image with a 1x1 template it would iterate something like this

x--
---
---

xx-
---
---

xxx
---
---

xxx
x--
---

...


Here is the desired algorithm:

// desired template matching algorithm, ignoring boundary checks for simplicity
let target_x = ...;
let target_y = ...;

for delta in 0..(image.width - template.width).max(image.height - template.height) {
for x in target_x - delta..= target_x + delta {
let y = target_y - delta;
let result = cross_correlate(image.view(x, y, template.width, template.height), template);
if result < THRESHOLD { return (x, y); }

let y = target_y + delta;
let result = cross_correlate(image.view(x, y, template.width, template.height), template);
if result < THRESHOLD { return (x, y); }
}
// ... same for y-axis
}


On a 3x3 image seeded at x=2, y=1 with a 1x1 template it would iterate something like this (like a flood fill)

---
--x
---

-xx
-xx
-xx

xxx
xxx
xxx


For reference, here is the world map: 