Vfrdtyky

How can I find the best "match" for small matrix in big matrix?
For example:

 small=[[1,2,3],

        [4,5,6],

        [7,8,9]]







    big=[[2,4,2,3,5],

         [6,0,1,9,0],

         [2,8,2,1,0],

         [7,7,4,2,1]]

The match is defined as difference of numbers in matrix, so match in position (1,1) is as if number 5 from small would be on number 0 from big matrix (so the central number from small matrix in coordinates (1,1) of big matrix.

The match value in position (1,1) is:
m(1,1)=|2−1|+|4−2|+|2−3|+|6−4|+|0−5|+|1−6|+|2−7|+|8−8|+|2−9|=28

The goal is to find the lowest difference posible in those matrixes.

The small matrix always has odd number of lines and columns, so it's easy to find it's centre.

You can iterate through the viable rows and columns and zip the slices of big with small to calculate the sum of differences, and use min to find the minimum among the differences:

from itertools import islice

min(

    (

        sum(

            sum(abs(x - y) for x, y in zip(a, b))

            for a, b in zip(

                (

                    islice(r, col, col + len(small[0]))

                    for r in islice(big, row, row + len(small))

                ),

                small

            )

        ),

        (row, col)

    )

    for row in range(len(big) - len(small) + 1)

    for col in range(len(big[0]) - len(small[0]) + 1)

)

or in one line:

min((sum(sum(abs(x - y) for x, y in zip(a, b)) for a, b in zip((islice(r, col, col + len(small[0])) for r in islice(big, row, row + len(small))), small)), (row, col)) for row in range(len(big) - len(small) + 1) for col in range(len(big[0]) - len(small[0]) + 1))

This returns: (24, (1, 0))

Done by hand:

small=[[1,2,3],

       [4,5,6],

       [7,8,9]]





big=[[2,4,2,3,5],

     [6,0,1,9,0],

     [2,8,2,1,0],

     [7,7,4,2,1]]



# collect all the sums    

summs=  



# k and j are the offset into big



for k in range(len(big)-len(small)+1):

    # add inner list for one row

    summs.append()

    for j in range(len(big[0])-len(small[0])+1):

        s = 0

        for row in range(len(small)):

            for col in range(len(small[0])):

                s += abs(big[k+row][j+col]-small[row][col])

        # add to the inner list

        summs[-1].append(s)



print(summs)

Output:

[[28, 29, 38], [24, 31, 39]]

If you are just interested in the coords in the bigger one, store tuples of (rowoffset,coloffset,sum) and dont box lists into lists. You can use min() with a key that way:

summs = 

for k in range(len(big)-len(small)+1):

    for j in range(len(big[0])-len(small[0])+1):

        s = 0

        for row in range(len(small)):

            for col in range(len(small[0])):

                s += abs(big[k+row][j+col]-small[row][col])

        summs .append( (k,j,s) )  # row,col, sum



print ("Min value for bigger matrix at ", min(summs , key=lambda x:x[2]) )

Output:

Min value for bigger matrix at  (1, 0, 24)

If you had "draws" this would only return the one with minimal row, col offset.

Another possible solution would be this, returning the minimum difference and the coordinates in the big matrix:

small=[[1,2,3],

       [4,5,6],

       [7,8,9]]



big=[[2,4,2,3,5],

     [6,0,1,9,0],

     [2,8,2,1,0],

     [7,7,4,2,1]]



def difference(small, matrix):

    l = len(small)

    return sum([abs(small[i][j] - matrix[i][j]) for i in range(l) for j in range(l)])



def getSubmatrices(big, smallLength):

    submatrices = 

    bigLength = len(big)

    step = (bigLength // smallLength) + 1

    for i in range(smallLength):

        for j in range(step):

            tempMatrix = [big[j+k][i:i+smallLength] for k in range(smallLength)]

            submatrices.append([i+1,j+1,tempMatrix])

    return submatrices



def minDiff(small, big):

    submatrices = getSubmatrices(big, len(small))

    diffs = [(x,y, difference(small, submatrix)) for x, y, submatrix in submatrices]

    minDiff = min(diffs, key=lambda elem: elem[2])

    return minDiff



y, x, diff = minDiff(small, big)



print("Minimum difference: ", diff)

print("X = ", x)

print("Y = ", y)

Output:

Minimum difference:  24

X =  1

Y =  2

I would use numpy to help with this.

To start I would convert the arrays to numpy arrays

import numpy as np



small = np.array([[1,2,3], [4,5,6], [7,8,9]])

big = np.array([[2,4,2,3,5], [6,0,1,9,0], [2,8,2,1,0], [7,7,4,2,1]])

then I would initialize an array to store the results of the test (optional: a dictionary as well)

result_shape = np.array(big.shape) - np.array(small.shape) + 1

results = np.zeros((result_shape[0], result_shape[1]))

result_dict = {}

Then iterate over the positions in which the small matrix can be positioned over the large matrix and calculate the difference:

insert = np.zeros(big.shape)

for i in range(results.shape[0]):

    for j in range(results.shape):

        insert[i:small.shape[0] + i, j:small.shape[1] + j] = small

        results[i, j] = np.sum(np.abs(big - insert)[i:3+i, j:3+j])

        # Optional dictionary 

        result_dict['{}{}'.format(i, j)] = np.sum(np.abs(big - insert)[i:3+i, j:3+j])

Then you can print(results) and obtain:

[[ 28.  29.  38.]

 [ 24.  31.  39.]]

and/or because the position of the small matrix over the big matrix is stored in the keys of the dictionary, you can get the position of the small matrix over the large matrix where the difference is smallest by key manipulation:

pos_min = [int(i) for i in list(min(result_dict, key=result_dict.get))]

and if you print(pos_min), you obtain:

[1, 0]

then if you need the index for anything you can iterate over it if required. Hope this helps!