Python欧几里得距离变换-Toy模板网

这篇具有很好参考价值的文章主要介绍了Python欧几里得距离变换。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

欧氏距离变换

edt，即Euclidean distance transform.，欧氏距离变换。对于一个二值矩阵 $A$ ，元素 $a\in A$ ，则 $\operatorname{edt}(a)$ 为 $a$ 到矩阵中0元素的最短距离。假设现有一矩阵

$\begin{bmatrix} 0&1&1&1&1\\ 0&0&1&1&1\\ 0&1&1&1&1\\ 0&1&1&1&0\\ 0&1&1&0&0 \end{bmatrix}$

记 $B=\operatorname{edt}(a)$ ，则

对于 $A_{11}$ 而言，由于其本身为0，则对应的 $B_{11}=0$
$A_{12}=1$ ，距离 $A_{12}$ 最近的0在 $A_{11}$ 和 $A_{22}$ 处，相隔均为1，所以 $B_{12}=1$
$A_{13}=1$ ，距离 $A_{13}$ 最近的0在 $A_{22}$ 处，由于在左下角，故距离为 $\sqrt{1+1}=\sqrt{2}$ ，即 $B_{12}=\sqrt{2}$

以此类推，得到

$\begin{bmatrix} 0.&1.&\sqrt{2}&\sqrt{5}&3.\\ 0.&0.&1.&2.&2.\\ 0.&1.&\sqrt{2}&\sqrt{2}&1.\\ 0.&1.&\sqrt{2}&1.&0.\\ 0.&1.&1.&0.&0. \end{bmatrix}$

distance_transform_edt

在scipy.ndimage中，distance_transform_edt可计算欧式变换，

from scipy import ndimage
import numpy as np
a = np.array(([0,1,1,1,1],
              [0,0,1,1,1],
              [0,1,1,1,1],
              [0,1,1,1,0],
              [0,1,1,0,0]))

ndimage.distance_transform_edt(a)
'''
array([[0.        , 1.        , 1.41421356, 2.23606798, 3.        ],
       [0.        , 0.        , 1.        , 2.        , 2.        ],
       [0.        , 1.        , 1.41421356, 1.41421356, 1.        ],
       [0.        , 1.        , 1.41421356, 1.        , 0.        ],
       [0.        , 1.        , 1.        , 0.        , 0.        ]])
'''

其完整定义为

distance_transform_edt(input, sampling=None, return_distances=True, return_indices=False, distances=None, indices=None)

其参数含义为

sampling 网格间距，相当于 $B$ 乘以一个系数
return_distances 为True时返回距离矩阵
return_indices 为True时返回特征变换矩阵
distances, indices 用于指针传参的数组，不用管

其他距离变换函数

scipy.ndimage除了edt之外，还提供了另外两个距离变换函数

istance_transform_bf(input, metric='euclidean', sampling=None, return_distances=True, return_indices=False, distances=None, indices=None)
distance_transform_cdt(input, metric='chessboard', return_distances=True, return_indices=False, distances=None, indices=None)

二者和edt相比，多了个metric函数，其中bf可选三种euclidean, taxicab, chessboard，cdt无euclidean选项。二者其他区别主要是采用的算法不同。

这三种不同的metric在计算距离时采用的方案不同

euclidean 即前面提到的欧几里得距离
chessboard 会将对角线的距离算作1，而非 $\sqrt2$
taxicab 类似于曼哈顿距离，不处理对角线

二者差异如下文章来源地址https://www.toymoban.com/news/detail-460102.html

>>> ndimage.distance_transform_bf(a,'chessboard')
array([[0, 1, 1, 2, 3],
       [0, 0, 1, 2, 2],
       [0, 1, 1, 1, 1],
       [0, 1, 1, 1, 0],
       [0, 1, 1, 0, 0]], dtype=uint32)
>>> ndimage.distance_transform_bf(a,'taxicab')
array([[0, 1, 2, 3, 3],
       [0, 0, 1, 2, 2],
       [0, 1, 2, 2, 1],
       [0, 1, 2, 1, 0],
       [0, 1, 1, 0, 0]], dtype=uint32)
>>>