python - 在python中计算距值距离的有效方法(Efficient way to calculate distance to value in matrix in python)

Question

I have an image and want to calculate for each non zero value pixel its distance to the closest zero value pixel.

(我有一张图片，想要为每个非零值像素计算到最接近的零值像素的距离。)

The way i tried to do it is the following:

(我尝试做到的方式如下：)

import numpy as np
from scipy.spatial.distance import cdist
from skimage import io

im=io.imread('imagepath')
#getting array where elements are 0
a,b = np.where(im == 0) 
# create a list with (row,column)
x = list(zip(a, b)) 
#getting array where elements are non zero
r, c =np.where(im!=0)
#create a list with (row, column) of all non 0 values
#note coordinates are in y, x format
obj = list(zip(r,c))
dist_dict={}
#calculating for each pixel of the object
for o in obj:    
    d = (cdist(np.array([o]), x, metric='euclidean')).min() 
    dist_dict.update({o:d})

I believe this should work, however it is quite slow.

(我认为这应该可以，但是速度很慢。)

For a single pixel it takes around 0.2 seconds to compute the distance.

(对于单个像素，大约需要0.2秒来计算距离。)

With objects around 50.000 pixels big this therefore would take around three hours of computation time per image, which is just not feasible at all.

(对于大约50.000像素大的物体，每个图像因此需要大约3个小时的计算时间，这根本不可行。)

One problem which I can see here is that I just iterate through all non zero pixels.

(我在这里可以看到的一个问题是，我只是遍历所有非零像素。)

Is there a way to start the search not at the beginning of array but from the current coordinates, until a zero value was found?

(有没有一种方法可以从当前坐标开始而不是从数组的开头开始搜索，直到找到零值？)

Or are there any other suggestions how to speed up this process?

(还是有其他建议如何加快这一过程？)

  ask by user11696936 translate from so

Answer 1

You can use scipy.ndimage.morphology.distance_transform_edt which finds the closest background point (value 0) with the smallest Euclidean distance to input pixels.

(您可以使用scipy.ndimage.morphology.distance_transform_edt查找与输入像素具有最小欧氏距离的最近背景点（值0）。)

from scipy import ndimage
import pprint

def nearest_zero(image):
    " Finds closest background (zero) element for each element in image "

    # Find closest zero elements in the inverted image (same as closest non-zero for image)
    edt = ndimage.distance_transform_edt(image, return_indices=False)

    # Create dictionary of indexes
    return {(r,c):edt[r][c] for r in range(image.shape[0]) for c in range(image.shape[1]) if image[r][c]}

Example of Usage

(使用范例)

image = np.array(([0,50,75,15,0],
                  [2,0,111,10,15],
                  [0,112,25,110,115],
                  [0,10,110,115,0],
                  [15,12,115,0,0]))


d = nearest_zero(image)
pp = pprint.PrettyPrinter(indent=4)

print('Original Image')
print(image)

print('
Dictionary of Distances to closest background pixel for each non-background pixel')
pp.pprint(sorted(d.items(), key=lambda x: x[0]))

Output

(输出量)

Original Image
[[  0  50  75  15   0]
 [  2   0 111  10  15]
 [  0 112  25 110 115]
 [  0  10 110 115   0]
 [ 15  12 115   0   0]]

Dictionary of Distances to closest background pixel for each non-background pixel
[   ((0, 1), 1.0),
    ((0, 2), 1.4142135623730951),
    ((0, 3), 1.0),
    ((1, 0), 1.0),
    ((1, 2), 1.0),
    ((1, 3), 1.4142135623730951),
    ((1, 4), 1.0),
    ((2, 1), 1.0),
    ((2, 2), 1.4142135623730951),
    ((2, 3), 1.4142135623730951),
    ((2, 4), 1.0),
    ((3, 1), 1.0),
    ((3, 2), 1.4142135623730951),
    ((3, 3), 1.0),
    ((4, 0), 1.0),
    ((4, 1), 1.4142135623730951),
    ((4, 2), 1.0)]