矩形阵列中最快的距离计算

Question

我正在寻找最快的方法来计算从图像中的某个原点到每个其他点的距离。现在，我所拥有的是这样的：

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

有没有更快的方法？我看到了 this answer，但我不确定如何应用它。

Answer 1

让我们发挥一些 broadcasting -

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

运行时测试和验证结果

定义函数-

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

案例#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

案例#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

Answer 2

除了其他答案，您绝对应该回答是否需要距离的问题，或者如果您的问题仅需距离的平方就可以解决。例如。如果你想知道最近的那个，用正方形就可以完美完成。

这将为您节省每个点对的昂贵的平方根计算。

矩形阵列中最快的距离计算

Fastest computation of distances in rectangular array

python

performance

numpy

distance