arrays - Finding the best matching block/patch in Python -

arrays - Finding the best matching block/patch in Python -

i wish locate closest matching nxn block within wxw window centred @ location (x,y) of larger 2d array. code below works fine slow needs need run operation many times. there improve way this?? here n = 3, w = 15, x =15, y = 15 , (bestx,besty) centre of best matching block

import numpy np ## generate test info curpatch = np.random.randint(20, size=(3, 3)) info = np.random.randint(20,size=(30,30)) # current location x,y = 15,15 # initialise best match bestcost = 999.0 bestx = 0;besty=0 wy in xrange(-7,8): wx in xrange(-7,8): ywj,ywi = y+wy,x+wx cost = 0.0 py in xrange(3): 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

as said in comment can check if cost bigger or equal bestcost within for px in xrange(3): if can break, way can save lot unnecessary iterations

example (will lite alter emphasize difference on bigger iterations):

import numpy np import time ## generate test info curpatch = np.random.randint(100, size=(3, 3)) info = 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() wy in xrange(-7,50): wx in xrange(-7,50): ywj, ywi = y+wy, x+wx cost = 0.0 py in xrange(3): 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)

will time @ 26ms

time: 0.0269999504089

your code out break output 37ms:

time: 0.0379998683929

also have suggest convert code function.

python arrays window patch matching