PYTHON中的测地距离变换

问题描述

在python中，scipy.ndimage.morphology模块中有distance_transform_edt函数。我将其应用于一个简单的情况，以计算与掩码Numpy数组中的单个单元格之间的距离。

然而，该函数移除了数组的掩码，并如预期的那样，计算每个具有非空值的单元格与具有空值的参考单元格的欧几里德距离。

下面是我在my blog post中给出的一个例子：

%pylab
from scipy.ndimage.morphology import distance_transform_edt
l = 100
x, y = np.indices((l, l))
center1 = (50, 20)
center2 = (28, 24)
center3 = (30, 50)
center4 = (60,48)
radius1, radius2, radius3, radius4 = 15, 12, 19, 12
circle1 = (x - center1[0])**2 + (y - center1[1])**2 < radius1**2
circle2 = (x - center2[0])**2 + (y - center2[1])**2 < radius2**2
circle3 = (x - center3[0])**2 + (y - center3[1])**2 < radius3**2
circle4 = (x - center4[0])**2 + (y - center4[1])**2 < radius4**2
# 3 circles
img = circle1 + circle2 + circle3 + circle4
mask = ~img.astype(bool)
img = img.astype(float)
m = ones_like(img)
m[center1] = 0
#imshow(distance_transform_edt(m), interpolation='nearest')
m = ma.masked_array(distance_transform_edt(m), mask)
imshow(m, interpolation='nearest')

但是，我想计算考虑数组掩码元素的测地距离变换。我不想计算穿过遮罩元素的直线上的欧几里得距离。

我使用Dijkstra算法获得了我想要的结果。下面是我提出的实现方案：

def geodesic_distance_transform(m):
    mask = m.mask
    visit_mask = mask.copy() # mask visited cells
    m = m.filled(numpy.inf)
    m[m!=0] = numpy.inf
    distance_increments = numpy.asarray([sqrt(2), 1., sqrt(2), 1., 1., sqrt(2), 1., sqrt(2)])
    connectivity = [(i,j) for i in [-1, 0, 1] for j in [-1, 0, 1] if (not (i == j == 0))]
    cc = unravel_index(m.argmin(), m.shape) # current_cell
    while (~visit_mask).sum() > 0:
        neighbors = [tuple(e) for e in asarray(cc) - connectivity 
                     if not visit_mask[tuple(e)]]
        tentative_distance = [distance_increments[i] for i,e in enumerate(asarray(cc) - connectivity) 
                              if not visit_mask[tuple(e)]]
        for i,e in enumerate(neighbors):
            d = tentative_distance[i] + m[cc]
            if d < m[e]:
                m[e] = d
        visit_mask[cc] = True
        m_mask = ma.masked_array(m, visit_mask)
        cc = unravel_index(m_mask.argmin(), m.shape)
    return m

gdt = geodesic_distance_transform(m)
imshow(gdt, interpolation='nearest')
colorbar()

上面实现的函数运行良好，但对于我开发的需要多次计算测地线距离变换的应用程序来说，速度太慢。

下面是欧几里得距离变换和测地线距离变换的时间基准：

%timeit distance_transform_edt(m)
1000 loops, best of 3: 1.07 ms per loop

%timeit geodesic_distance_transform(m)
1 loops, best of 3: 702 ms per loop

如何才能获得更快的测地距离变换？

---

解决方案

首先，请竖起大拇指回答一个非常清楚且写得很好的问题。

有一个非常好且快速的Fast Marching方法实现，称为scikit-fmm来解决这类问题。您可以在此处找到详细信息： http://pythonhosted.org//scikit-fmm/

安装它可能是最难的部分，但在装有Conda的Windows上很容易，因为有适用于Py27的64位Conda包： https://binstar.org/jmargeta/scikit-fmm

从那时起，只需将掩码数组传递给它，就像处理您自己的函数一样。点赞：

distance = skfmm.distance(m)

结果看起来差不多，我认为甚至更好。您的方法(显然)在八个不同的方向上进行搜索，导致了一个小八角形的距离。

在我的机器上，SCISKIT-FMM实现比您的函数快200倍以上。