python中的矩阵匹配

Question

如何找到大矩阵中小矩阵的最佳“匹配”？例如：

 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]]

匹配定义为矩阵中的数差，所以位置(1,1)上的匹配就好像从小到小的数在0上的大矩阵(所以从小矩阵到大矩阵的坐标(1,1)中的中心数)。

位置(1,1)中的匹配值为: m(1,1)=|2−1|+|4−2|+|2−3|+|6−4|+|0−5|+|1−6|+|2−7|+|8−8|+|2−9|=28

目标是在这些矩阵中找到最小的差分位置。

小矩阵总是有奇数的线和列，所以很容易找到它的中心。

Answer 1

您可以迭代可行的行和列，并使用small压缩big的切片，以计算差异的总和，并使用min查找差异之间的最小值：

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)
)

或者是一行：

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))

返回：(24, (1, 0))

Answer 2

手工完成的：

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)

输出：

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

如果您只是对较大的和弦感兴趣，请将(rowoffset,coloffset,sum)的元组存储在列表中，不要将列表框放在框中。您可以通过这种方式使用带有密钥的min()：

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]) )

输出：

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

如果您有“绘制”，这将只返回最小行的，col偏移量。

Answer 3

另一个可能的解决方案是返回big矩阵中的最小差值和坐标：

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)

输出：

Minimum difference:  24
X =  1
Y =  2