Is there any alternative to brute force matching binary images?

Question

This opencv/numpy code works, but is 1000x too slow. basically I have a white square, and another image that is slightly rotated and translated. The code recovers the pose by brute force trying all angles and translations within 10 degrees and 10 pixels.

I tried find homography but got terrible results. This code got perfect results, but is far too slow. I need it to run 100 to 1000 times faster, while staying in python.

I would like to know how to massively speed up this code, or, an alternate way that recovers the fact that the image is rotated 5 degrees and translated about 5,7 pixels

import cv2
import numpy as np
import random
import math
import time

# Create a 240x224 black image (image01) with a 64-pixel black margin
image01 = np.zeros((224, 240), dtype=np.uint8)
image01[64:160, 64:176] = 255  # Add a white square within the margin

# Copy image01 to image02
image02 = image01.copy()

# Rotate image02 by 5 degrees and translate it 5 pixels up and 7 pixels left
rows, cols = image02.shape
M = cv2.getRotationMatrix2D((cols / 2, rows / 2), 5, 1)
M[0, 2] -= 7
M[1, 2] -= 5
image02 = cv2.warpAffine(image02, M, (cols, rows))

# Create scaled-down copies of image01 and image02
scaling_factor = 1/1
img1 = cv2.resize(image01, None, fx=scaling_factor, fy=scaling_factor)
img2s = cv2.resize(image02, None, fx=scaling_factor, fy=scaling_factor)

# Define parameters for the search
rotation_range = range(-10, 11, 1)
translation_range = range(-10, 11)

# Create a list to store the results
results = []

start = time.time()

for rotation_angle in rotation_range:
    # Rotate img2
    img2 = img2s.copy()
    M_rotation = cv2.getRotationMatrix2D((img2.shape[1] / 2, img2.shape[0] / 2), rotation_angle, 1)
    
    img2_rotated = cv2.warpAffine(img2, M_rotation, (img2.shape[1], img2.shape[0]))

    for dx in translation_range:
        for dy in translation_range:
            # Translate img2_rotated
            M_translation = np.float32([[1, 0, dx], [0, 1, dy]])
            img2_transformed = cv2.warpAffine(img2_rotated, M_translation, (img2.shape[1], img2.shape[0]))

            diff = cv2.absdiff(img1, img2_transformed)
            non_zero_pixels = np.sum(diff[diff == 255])
            
            
            results.append((rotation_angle, (dx, dy), non_zero_pixels))

print(time.time() - start)
# Sort the results based on the number of non-zero pixels
sorted_results = sorted(results, key=lambda x: x[2])

# Show the top 10 results
for i, (rotation_angle, (dx, dy), non_zero_pixels) in enumerate(sorted_results[:10], 1):
    dx = dx/scaling_factor
    dy = dy/scaling_factor
    print(f"Top {i} - Rotation: {rotation_angle}°, Translation: ({dx}, {dy}), Non-zero pixels: {non_zero_pixels}")

the actual images look similar to this (random blobs)

Answer 1

I'm in a bit of a rush so I post the code for finding the x,y offset:

def get_coords(array, locs):
    return np.array([array[i] for i in locs])

def find_center(img):
    ys, xs = np.nonzero(img)
    corner_indices = [np.argmin(xs),np.argmax(xs),np.argmin(ys),np.argmax(ys)]
    corner_xs = get_coords(xs,corner_indices)
    corner_ys = get_coords(ys,corner_indices)
    return np.array((corner_xs[:2].mean(), corner_ys[2:].mean()))# in (x,y) format

print(find_center(img2)-find_center(img1))

you can use similar formulas to find the rotation as well (will update the answer later today to include that)