Ускорьте вычисления для преобразования расстояния на изображении в Python

Question

Я хотел бы найти преобразование расстояния двоичного изображения максимально быстрым способом без использования пакета scipy distance_trnsform_edt ().Изображение 256 на 256. Причина, по которой я не хочу использовать scipy, заключается в том, что его использование сложно в тензорном потоке.Каждый раз, когда я хочу использовать этот пакет, мне нужно начать новый сеанс, и это занимает много времени.Поэтому я хотел бы создать пользовательскую функцию, которая использует только numpy.

Мой подход заключается в следующем: найти координаты для всех единиц и всех нулей на изображении.Найти евклидово расстояние между каждым из нулевых пикселей (a) и единичных пикселей (b), а затем значение в каждой (a) позиции - это минимальное расстояние до (b) пикселя.Я делаю это для каждого 0 пикселей.Полученное изображение имеет те же размеры, что и исходная двоичная карта.Моя попытка сделать это показана ниже.

Я пытался сделать это как можно быстрее, не используя петли и только векторизацию.Но моя функция по-прежнему не может работать так быстро, как это делает пакет scipy.Когда я рассчитал время выполнения кода, похоже, что присвоение переменной «а» занимает больше всего времени.Но я не знаю, есть ли способ ускорить это.

Если у кого-нибудь есть какие-либо другие предложения по различным алгоритмам для решения этой проблемы преобразования расстояний или я могу направить меня к другим реализациям в python, это будеточень ценится.

def get_dst_transform_img(og): #og is a numpy array of original image
    ones_loc = np.where(og == 1)
    ones = np.asarray(ones_loc).T # coords of all ones in og
    zeros_loc = np.where(og == 0)
    zeros = np.asarray(zeros_loc).T # coords of all zeros in og

    a = -2 * np.dot(zeros, ones.T) 
    b = np.sum(np.square(ones), axis=1) 
    c = np.sum(np.square(zeros), axis=1)[:,np.newaxis]
    dists = a + b + c
    dists = np.sqrt(dists.min(axis=1)) # min dist of each zero pixel to one pixel
    x = og.shape[0]
    y = og.shape[1]
    dist_transform = np.zeros((x,y))
    dist_transform[zeros[:,0], zeros[:,1]] = dists 

    plt.figure()
    plt.imshow(dist_transform)

Answer 1

Реализация в OP представляет собой грубый метод преобразования расстояния.Этот алгоритм равен O (n ² ), так как он вычисляет расстояние от каждого фонового пикселя до каждого переднего пикселя.Кроме того, из-за того, как он векторизован, он требует много памяти.На моем компьютере не удалось вычислить преобразование расстояния для изображения 256x256 без перемалывания.Многие другие алгоритмы описаны в литературе, ниже я рассмотрю два O (n) алгоритма.

Примечание: Как правило, преобразование расстояния вычисляется для пикселей объекта (значение 1) дляближайший фоновый пиксель (значение 0).Код в OP делает обратное, и поэтому код, который я вставил ниже, следует соглашению OP, а не более распространенному соглашению.

---

Самым простым в реализации, IMO, является алгоритм расстояния с фаской.Это рекурсивный алгоритм, который выполняет два прохода по изображению: один слева направо и сверху вниз, а другой справа налево и снизу вверх.На каждом проходе расстояние, вычисленное для предыдущих пикселей, распространяется.Этот алгоритм может быть реализован с использованием целочисленных расстояний или расстояний с плавающей точкой между соседями.Последнее, конечно, приводит к меньшим ошибкам.Но в обоих случаях ошибки могут быть значительно уменьшены путем увеличения числа соседей, запрашиваемых в этом распространении.Алгоритм более старый, но Дж. Боргефорс проанализировал его и предложил подходящие соседние расстояния ( Дж. Боргефорс, Преобразования расстояний в цифровых изображениях, компьютерное зрение, графика и обработка изображений 34: 344-371, 1986 ).

Вот реализация, использующая расстояние 3-4 (расстояние до соседей, связанных с ребрами, равно 3, расстояние до соседей, связанных с вершинами, равно 4):

def chamfer_distance(img):
   w, h = img.shape
   dt = np.zeros((w,h), np.uint32)
   # Forward pass
   x = 0
   y = 0
   if img[x,y] == 0:
      dt[x,y] = 65535 # some large value
   for x in range(1, w):
      if img[x,y] == 0:
         dt[x,y] = 3 + dt[x-1,y]
   for y in range(1, h):
      x = 0
      if img[x,y] == 0:
         dt[x,y] = min(3 + dt[x,y-1], 4 + dt[x+1,y-1])
      for x in range(1, w-1):
         if img[x,y] == 0:
            dt[x,y] = min(4 + dt[x-1,y-1], 3 + dt[x,y-1], 4 + dt[x+1,y-1], 3 + dt[x-1,y])
      x = w-1
      if img[x,y] == 0:
         dt[x,y] = min(4 + dt[x-1,y-1], 3 + dt[x,y-1], 3 + dt[x-1,y])
   # Backward pass
   for x in range(w-2, -1, -1):
      y = h-1
      if img[x,y] == 0:
         dt[x,y] = min(dt[x,y], 3 + dt[x+1,y])
   for y in range(h-2, -1, -1):
      x = w-1
      if img[x,y] == 0:
         dt[x,y] = min(dt[x,y], 3 + dt[x,y+1], 4 + dt[x-1,y+1])
      for x in range(1, w-1):
         if img[x,y] == 0:
            dt[x,y] = min(dt[x,y], 4 + dt[x+1,y+1], 3 + dt[x,y+1], 4 + dt[x-1,y+1], 3 + dt[x+1,y])
      x = 0
      if img[x,y] == 0:
         dt[x,y] = min(dt[x,y], 4 + dt[x+1,y+1], 3 + dt[x,y+1], 3 + dt[x+1,y])
   return dt

Обратите внимание, что многие изСложность здесь заключается в том, чтобы избежать индексации за пределами границ, но при этом вычислять расстояния до краев изображения.Если мы просто пропустим пиксели вокруг границы изображения, код станет намного проще.

Поскольку это рекурсивный алгоритм, невозможно векторизовать его реализацию.Код Python не будет очень эффективным.Но программирование на C или тому подобное даст очень быстрый алгоритм, который дает довольно хорошее приближение к евклидову расстоянию.

OpenCV cv.distanceTransform реализует этот алгоритм.

---

Другой очень эффективный алгоритм вычисляет квадрат преобразования расстояния.Квадратное расстояние является разделимым (то есть может быть вычислено независимо для каждой оси и добавлено).Это приводит к алгоритму, который легко распараллелить.Для каждой строки изображения алгоритм выполняет прямой и обратный проход.Для каждого столбца в результате алгоритм затем делает еще один прямой и обратный проход.Этот процесс приводит к точному евклидову дистанционному преобразованию.

Этот алгоритм был впервые предложен Р. ван ден Бумгаардом в его кандидатской диссертации.Диссертация в 1992 году .К сожалению, это осталось незамеченным.Затем этот алгоритм был снова предложен А. Мейстером, Дж. Б. Р. Рердинком и В. Х. Хесселинком ( Общий алгоритм вычисления расстояний в линейном времени, математическая морфология и его приложения к обработке изображений и сигналов, стр. 331-340, 2002 * 1032.*) и снова П. Фельзенцвальбом и Д. Хаттенлохером ( Дистанционные преобразования выборочных функций, Технический отчет, Корнельский университет, 2004 ).

Это самый эффективный из известных алгоритмов вчастично, потому что это единственное, которое можно легко и эффективно распараллелить (вычисления для каждой строки изображения, а затем для каждого столбца изображения не зависят от других строк / столбцов).

К сожалению, у меня нет никакихКод Python для этого, чтобы поделиться, но вы можете найти реализации в Интернете.Например, OpenCV cv.distanceTransform реализует этот алгоритм, а PyDIP dip.EuclideanDistanceTransform тоже.