Template Matching non-rectangular template in non-linear order

Question

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: