在Python中寻找最佳匹配块/补丁

Question

我希望在一个WxW窗口中找到最接近匹配的NxN块，该窗口以较大的2D数组的位置（x，y）为中心。下面的代码可以正常工作，但对于我的需要非常慢，因为我需要运行这个操作很多次。有更好的方法吗？？ 这里N=3，W=15，x=15，y=15，（bestx，besty）是最佳匹配块的中心

import numpy as np

## Generate some test data
CurPatch = np.random.randint(20, size=(3, 3))
Data = np.random.randint(20,size=(30,30))

# Current Location 
x,y = 15,15
# Initialise Best Match
bestcost = 999.0
bestx = 0;besty=0

for Wy in xrange(-7,8):
    for Wx in xrange(-7,8):
            Ywj,Ywi = y+Wy,x+Wx 

            cost = 0.0
            for py in xrange(3):
                for px in xrange(3):
                    cost += abs(Data[Ywj+py-1,Ywi+px-1] - CurPatch[py,px]) 

            if cost < bestcost:
                bestcost = cost
                besty,bestx = Ywj,Ywi

print besty,bestx

Answer 1

正如我在评论中所说的，你可以检查cost是否大于或等于for px in xrange(3):内的bestcost如果这样你就可以中断，这样可以节省很多不必要的迭代

示例（在较大的迭代中，灯光是否会改变以强调差异）：

import numpy as np
import time

## Generate some test data
CurPatch = np.random.randint(100, size=(3, 3))
Data = np.random.randint(100, size=(3000,3000))

# Current Location 
x,y = 10, 10
# Initialise Best Match
bestcost = 999.0
bestx = 0;besty=0

t0 = time.time()
for Wy in xrange(-7,50):
    for Wx in xrange(-7,50):
            Ywj, Ywi = y+Wy, x+Wx

            cost = 0.0
            for py in xrange(3):
                for px in xrange(3):
                    cost += abs(Data[Ywj+py-1,Ywi+px-1] - CurPatch[py,px])
                    if cost >= bestcost:
                        break

            if cost < bestcost:
                bestcost = cost
                besty,bestx = Ywj,Ywi

print besty, bestx
print "time: {}".format(time.time() - t0)

时间是26毫秒

time: 0.0269999504089

不带中断的代码将输出37毫秒：

time: 0.0379998683929

我还建议把这段代码转换成一个函数。在

Answer 2

为了了解速度，使用numpy时，w与大窗口大小相同的子问题更快（也更简洁）：

a= '''import numpy as np


## Generate some test data
CurPatch = np.random.randint(20, size=(3, 3))
Data = np.random.randint(20,size=(30,30))


def best(CurPatch,Data):

    # Current Location 
    x,y = 15,15
    # Initialise Best Match
    bestcost = 999.0
    bestx = 0;besty=0

    for Wy in xrange(-14,14):
        for Wx in xrange(-14,14):
                Ywj,Ywi = y+Wy,x+Wx 

                cost = 0.0
                for py in xrange(3):
                    for px in xrange(3):
                        cost += (Data[Ywj+py-1,Ywi+px-1] - CurPatch[py,px])**2 

                if cost < bestcost:
                    bestcost = cost
                    besty,bestx = Ywj,Ywi
    return besty,bestx,bestcost



def minimize(CurPatch,W):
    max_sum=999
    s= CurPatch.shape[0]
    S= W.shape[0]
    for i in range(0,S-s):
        for j in range(0,S-s):
            running= np.sum(np.square((W[i:i+3,j:j+3]-CurPatch)))
            if running<max_sum:
                max_sum=running
                x=i+1;y=j+1
    return x,y,max_sum

'''


import timeit
print min(timeit.Timer('minimize(CurPatch,Data)', a).repeat(7, 10))
print min(timeit.Timer('best(CurPatch,Data)', a).repeat(7, 10))