Python中的广义距离变换

Question

我目前正在尝试实现Felzenszwalb和Huttenlocher描述的GDT(http://www.cs.cornell.edu/~dph/papers/dt.pdf），用于图像处理算法。然而，我使用了他们几年前发表的论文中描述的算法，但得到了错误的结果。我在这里找到了一个C#实现：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数组时，它只返回数组本身，而不是距离变换。为什么这在Python中不起作用？

Answer 1

我让它工作了好几个小时。上面在C#中实现代码的链接中给出的答案建议将"白色"区域设置为非常大的数字。我的dataInput数组是一个布尔数组（0，1）。我用2^32替换了所有的1，效果很好。数字越高，它就越模糊。它越低，与来源越相似。

Answer 2

我想为2D添加一个与前面描述的1D函数一起工作的函数：

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

我希望它能有所帮助。