CODEWITHSUNDEEP
pythonperformancenumpydistance
user2297781
user2297781

Reputation:

Fastest computation of distances in rectangular array

I'm looking for the fastest way to compute a lot of distances from some origin in a an image to every other point. Right now, what I have is something like this:

origin = [some_val,some_other_val]
y,x = np.mgrid[:image.shape[0],:image.shape[1]].astype(float)    
r = np.hypot(y-origin[0],x-origin[1])

Is there a faster way? I saw this answer, but I'm not sure how to apply it.

Upvotes: 2

Views: 174

Answers (2)

xtofl
xtofl

Reputation: 41509

Apart from the other answers, you should definitely answer the question whether you need the distance, or if your problem can be solved with just the square of the distance. E.g. if you want to know the nearest one, this can be perfectly done with the square.

This would save you an expensive square root calculation for each point pair.

Upvotes: 1

Divakar
Divakar

Reputation: 221504

Let's bring some broadcasting into play -

m,n= image.shape
r = np.sqrt((np.arange(m)[:,None]-origin[0])**2 + (np.arange(n)-origin[1])**2)

Runtime tests and verify results

Define functions -

In [115]: def broadcasting_based(origin,image_shape):
     ...:     m,n= image_shape
     ...:     return np.sqrt((np.arange(m)[:,None]-origin[0])**2 + (np.arange(n)-origin[1])**2)
     ...: 
     ...: 
     ...: def original_approach(origin,image_shape):
     ...:     y,x = np.mgrid[:image_shape[0],:image_shape[1]].astype(float)    
     ...:     return np.hypot(y-origin[0],x-origin[1])
     ...:

Case # 1:

In [116]: origin = np.array([100,200])

In [117]: np.allclose(broadcasting_based(origin,[500,500]),original_approach(origin,[500,500]))
Out[117]: True

In [118]: %timeit broadcasting_based(origin,[500,500])
100 loops, best of 3: 3.28 ms per loop

In [119]: %timeit original_approach(origin,[500,500])
10 loops, best of 3: 21.2 ms per loop

Case # 2:

In [123]: origin = np.array([1000,2000])

In [124]: np.allclose(broadcasting_based(origin,[5000,5000]),original_approach(origin,[5000,5000]))
Out[124]: True

In [125]: %timeit broadcasting_based(origin,[5000,5000])
1 loops, best of 3: 460 ms per loop

In [126]: %timeit original_approach(origin,[5000,5000])
1 loops, best of 3: 2.96 s per loop

Upvotes: 2

Related Questions