Обобщенное преобразование расстояния в Python

Question

В настоящее время я пытаюсь реализовать GDT, описанный Felzenszwalb и Huttenlocher (http://www.cs.cornell.edu/~dph/papers/dt.pdf) внутри Python для алгоритма обработки изображений. Однако я использовал алгоритм, описанный в опубликованном им документе несколько лет назад, но получил ошибочные результаты. Я нашел реализацию 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, он просто возвращает сам массив, а не Transform. Почему это не работает на Python?

Answer 1

Я получил его работу после нескольких часов и часов. Ответ, приведенный в ссылке выше реализации кода на C#, предполагает установку «белых» областей на очень большое число. Мой массив dataInput был булевым массивом (0, 1). Я заменил все 1s на 2^32, и он отлично работает. Чем выше число, тем более размытым. Чем ниже, тем больше похоже на источник, который он получает.

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 

Я надеюсь, что это помогает.