Python 中的广义距离变换

Question

我目前正在尝试实现 Felzenszwalb 和 Huttenlocher 描述的 GDT (http://www.cs.cornell.edu/~dph/papers/dt.pdf) inside of Python for an image processing algorithm. However I used the algorithm described in the paper they published a few years back but got faulty results. I found a C# implementation here: https://dsp.stackexchange.com/questions/227/fastest-available-algorithm-for-distance-transform/29727?noredirect=1#comment55866_29727

并将其转换为 Python（这与我之前的几乎相同）。

这是我的代码：

def of_column(dataInput):
    output = zeros(dataInput.shape)
    n = len(dataInput)

    k = 0
    v = zeros((n,))
    z = zeros((n + 1,))

    v[0] = 0
    z[0] = -inf
    z[1] = +inf

    s = 0

    for q in range(1, n):
        while True:
            s = (((dataInput[q] + q * q) - (dataInput[v[k]] + v[k] * v[k])) / (2.0 * q - 2.0 * v[k]))

            if s <= z[k]:
                k -= 1
            else:
                break

        k += 1

        v[k] = q
        z[k] = s
        z[k + 1] = +inf

    k = 0

    for q in range(n):
        while z[k + 1] < q:
            k += 1

        output[q] = ((q - v[k]) * (q - v[k]) + dataInput[v[k]])

    return output

我仍然找不到我的错误。当给算法一个二进制（布尔）numpy 数组时，它只是 returns 数组本身而不是距离变换。为什么这在 Python 中不起作用？

Answer 1

我下班后就开始工作了。 link 上面在 C# 中实现代码中给出的答案建议将 "white" 区域设置为非常大的数字。我的 dataInput 数组是一个布尔数组 (0, 1)。我用 2^32 替换了所有的 1，它工作得很好。数字越高，它变得越模糊。越低越接近源码。

Answer 2

我想添加与前面描述的 1D 函数一起使用的 2D 函数：

############################################################################### 
# distance transform of 1d function using squared distance 
############################################################################### 
def dt_1d(dataInput, n):
    output = np.zeros(dataInput.shape)
    k = 0
    v = np.zeros((n,))
    z = np.zeros((n + 1,))
    v[0] = 0
    z[0] = -np.inf
    z[1] = +np.inf
    for q in range(1, n):
        s = (((dataInput[q] + q * q) - (dataInput[v[k]] + v[k] * v[k])) / (2.0 * q - 2.0 * v[k]))
        while s <= z[k]:
            k -= 1
            s = (((dataInput[q] + q * q) - (dataInput[v[k]] + v[k] * v[k])) / (2.0 * q - 2.0 * v[k]))
        k += 1
        v[k] = q
        z[k] = s
        z[k + 1] = +np.inf

    k = 0
    for q in range(n):
        while z[k + 1] < q:
            k += 1
        value = ((q - v[k]) * (q - v[k]) + dataInput[v[k]])
        if value > 255: value = 255
        if value < 0: value = 0
        output[q] = value
    print output
    return output
############################################################################### 
# distance transform of 2d function using squared distance 
###############################################################################     
def dt_2d(dataInput):
    height, width = dataInput.shape
    f = np.zeros(max(height, width))
    # transform along columns
    for x in range(width):
        f = dataInput[:,x]
        dataInput[:,x] = dt_1d(f, height)
    # transform along rows
    for y in range(height):
        f = dataInput[y,:]
        dataInput[y,:] = dt_1d(f, width)
    return dataInput

希望对您有所帮助。

Python 中的广义距离变换

Generalized Distance Transform in Python

python

image-processing

euclidean-distance