Aligning two binary matrices for maximum overlap

Question

I would like to find the number of maximum overlapping 1's of two binary matrices, allowing only for translation (rotation and reflection are not allowed). My question is very similar to this one, but what I want to do is to actually code in an efficient way the "naive" solution proposed by OP in that question.

So, to recap, I have two matrices (not necessarily of the same size) with entries being 0 or 1, for example:

   [0 0]      [0 0 1]
A: [1 1]   B: [0 0 1]
   [1 0]      [1 0 0]

The maximum overlap can be found by aligning one of the corners of one matrix to every possible position of the other matrix and counting all the overlapping 1's. Then, we find than the maximum overlap is two and is given when we align the bottom left corner (2,0) of A to (1,2) of B.

I would like to code in python a simple (and possibly fast) implementation of this method, but I don't really know where to start...

Answer 1

To find the maximum overlap you can use the correlate2d function from scipy:

import scipy

scipy.signal.correlate2d(a, b).max()

Or you can implement it from scratch using numpy (which is a little bit tricky):

import numpy as np
from numpy.lib.stride_tricks import as_strided


def max_overlap(a, b):
    b_p = np.pad(b, ((a.shape[0]-1, a.shape[0]-1), (a.shape[1]-1, a.shape[1]-1)), 'constant', constant_values=0)
    output_shape = (b_p.shape[0] - a.shape[0] + 1, b_p.shape[1] - a.shape[1] + 1)
    b_w = as_strided(b_p, shape=output_shape + a.shape,
                          strides=b_p.strides*2)
    c = (b_w * a).sum(axis=(2,3))
    return c.max()