How can I filter outlying matches based on proximity to other matches?

I'm trying to find a small, similar image, inside a large image. Template matching doesn't seems to handle the minute differences very well so I am trying the feature match approach. After much tinkering around I can get it to do a fairly decent job at matching but the outliers will cause problems. I have homography in my code which doesn't seem necessary, but It has a positive impact on getting the correct matches. Is there some other alternative that would be more effective?

Ultimately, I would like to find the matches, (See image 1) filter out the key points that don't align with the smaller image, (See image 2) determine the boundaries of the smaller image within the large, then find the coordinates for the center of that boundary.

https://ibb.co/c0xC6m

https://ibb.co/mjSZK6

Additional images:

Image to search: (They aren't formatted as images because of an error saying I had code that wasn't formatted.)

https://i.sstatic.net/VyVAv.png

Unedited world map:

https://i.sstatic.net/5u3FN.png

Original search result:

https://i.sstatic.net/VrX63.png

import cv2
import numpy as np
from matplotlib import pyplot as plt
import remove_map_dots as rm

MIN_MATCH_COUNT = 0

img1 = rm.removemapdots()
img2 = cv2.imread('worldmapsnippet1.png')

surf = cv2.xfeatures2d.SURF_create(hessianThreshold=10, upright=True, extended=True)

# find the keypoints and descriptors with SURF/SIFT
kp1, des1 = surf.detectAndCompute(img1, None)
kp2, des2 = surf.detectAndCompute(img2, None)

FLANN_INDEX_KDTREE = 0
index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees=5)
search_params = dict(checks=50)

flann = cv2.FlannBasedMatcher(index_params, search_params)
matches = flann.knnMatch(des1, des2, k=2)

good = []
for m, n in matches:
    good.append(m)

if len(good)>MIN_MATCH_COUNT:
    src_pts = np.float32([kp1[m.queryIdx].pt for m in good]).reshape(-1, 1, 2)
    dst_pts = np.float32([kp2[m.trainIdx].pt for m in good]).reshape(-1, 1, 2)

    M, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC, 10) #RANSAC LMEDS RHO
    matchesMask = mask.ravel().tolist()

    h, w, _ = img1.shape
    pts = np.float32([[0, 0], [0, h - 1], [w - 1, h - 1], [w - 1, 0]]).reshape(-1, 1, 2)
    dst = cv2.perspectiveTransform(pts, M)

    img2 = cv2.polylines(img2, [np.int32(dst)], True, 255, 3, cv2.LINE_AA)
    print(h)
    print(w)
else:
    print("Not enough matches are found - %d/%d" % (len(good), MIN_MATCH_COUNT))
    matchesMask = None

draw_params = dict(matchColor = (0, 255, 0), # draw matches in green color
                   singlePointColor = None,
                   matchesMask = matchesMask, # draw only inliers
                   flags = 2)

img3 = cv2.drawMatches(img1, kp1, img2, kp2, good, None, **draw_params)
plt.imshow(img3), plt.show()

Solution

As discussed in the comments, the issue with your template matching approach is indeed the size of the template and image. The template is larger than the corresponding region of the template, giving false readings. The simple solution is to resize your template so that the region corresponds exactly to the right size region in the map.

Feature matching can be used for this as well, but template matching makes far more sense here. The only difference between the two images will be translation, which template matching can handle really well.

With template matching, it's also easy to make nice optimizations, like reducing the search area to be around the last found location in the map. You can also create a threshold by looking at the last few found locations---so that you know when you're not finding the correct location and need to re-look at the whole map. For e.g., if you teleport it won't be around the last location, so you'll need to go over the whole image. But you know that the min of your SSD image from the last (say) 5 frames were [100, 150, 130, 180, 100] so if your next frame was way different (say the min in your region was 500) then you go and check the whole map again and find the min, and again start tracking that region.