Distance Transformation
Photogrammetry-1
So, I have recently implemented Distance Transform as part of an exercise while taking the course Photogrammetry-1 by Prof. Cyrill Stachniss. The main idea of the algorithm is to find out the distance between each image pixel and the foreground/background. What we do is fairly simple. We do 2 passes of the image. In the first pass, we go through the image as usual row by row, finding neighbors of each pixel and finding the distance from that pixel to the background/foreground using the neighbors which can be either 4 or 8. In the second pass, we go from bottom to top and from right to left while calculating distances as we did in the first pass.
In the example above, the pixel under consideration is the one with dot inside it. The distance from background is 1 using the neighbor above the pixel while it is 2 if we consider the neighbor to the left. We calculate distances from all neighbors and choose the minimum as the distance of the pixel from the background. The example shown utilizes N4 neighborhood, similar methodology can be applied for N8 neighborhood with the exception that the number of neighbors will be increased.
Get Talha Hanif Butt’s stories in your inbox
Join Medium for free to get updates from this writer.
So far, we have talked about the first pass of the image. We need to perform a second pass through the image which will be in reverse order which means instead of going from left to right and top to bottom, we will go from right to left and bottom to top. We will follow the same pattern, that is, selecting the minimum distance as we go along the reverse pass and assign a new distance to the current pixel if a shorter distance than current value is found.
In short, what we need is a distance matrix, representing distance of each pixel from the background/foreground, we can either find distance from background or foreground, we perform 2 passes of the image, one from top-down, left-right while the second from bottom-top, right-left, find neighbors and calculate distance of the neighbors to the foreground/background, which means going in a particular direction until we hit a background/foreground pixel or the end/start of the image, and choose the minimum as the distance of the current pixel.
The code of the algorithm is as follows:
import os
import cv2
import numpy as np
%matplotlib inline
from matplotlib import pyplot as plt
import random
import skimage
def distance_transformation(binary_img, neighborhood):
distance_image = np.zeros(np.shape(binary_img)) # image to get output as distance image
for row in range(np.shape(binary_img)[0]): # loop over the image rows
for col in range(np.shape(binary_img)[1]): # loop over the image columns
if binary_img[row,col] == 1: # check if it's a foreground pixel
if neighborhood == 4: # if we are considering 4 neighbors
row_up = row # saving row number to process for neighbors in the upward direction
col_up = col # saving column number to process for neighbors in the upward direction
dist_up = 0 # distance in the upward direction
row_left = row # saving row number to process for neighbors in the left direction
col_left = col # saving column number to process for neighbors in the left direction
dist_left = 0 # distance in the left direction
while row_up - 1 >= 0 and binary_img[row_up,col_up] == 1: # go in the upward direction until we reach end of neighbors or we hit a background pixel
row_up -= 1 # move upwards
dist_up += 1 # add a pixel as a distance to the background
while col_left - 1 >= 0 and binary_img[row_left,col_left] == 1: # go in the left direction until we reach end of neighbors or we hit a background pixel
col_left -= 1 # move left
dist_left += 1 # add a pixel as a distance to the background
if dist_left < dist_up: # assign distance from left if it is shorter else assign distance from the top
distance_image[row,col] = dist_left
else:
distance_image[row,col] = dist_up
if neighborhood == 8: # if we are considering 8 neighbors
row_up = row # saving row number to process for neighbors in the upward direction
col_up = col # saving column number to process for neighbors in the upward direction
dist_up = 0 # distance in the upward direction
row_left = row # saving row number to process for neighbors in the left direction
col_left = col # saving column number to process for neighbors in the left direction
dist_left = 0 # distance in the left direction
row_left_diagonal = row # saving row number to process for neighbors in the left diagonal direction
col_left_diagonal = col # saving column number to process for neighbors in the left diagonal direction
dist_left_diagonal = 0 # distance in the left diagonal direction
row_right_diagonal = row # saving row number to process for neighbors in the right diagonal direction
col_right_diagonal = col # saving column number to process for neighbors in the right diagonal direction
dist_right_diagonal = 0 # distance in the right diagonal direction
while row_up - 1 >= 0 and binary_img[row_up,col_up] == 1: # go in the upward direction until we reach end of neighbors or we hit a background pixel
row_up -= 1 # move upwards
dist_up += 1 # add a pixel as a distance to the background
while col_left - 1 >= 0 and binary_img[row_left,col_left] == 1: # go in the left direction until we reach end of neighbors or we hit a background pixel
col_left -= 1 # move left
dist_left += 1 # add a pixel as a distance to the background
while row_left_diagonal - 1 >= 0 and col_left_diagonal - 1 >= 0 and binary_img[row_left_diagonal,col_left_diagonal] == 1: # go in the left diagonal direction until we reach end of neighbors or we hit a background pixel
row_left_diagonal -= 1 # move left diagonal
col_left_diagonal -= 1 # move left diagonal
dist_left_diagonal += 1 # add a pixel as a distance to the background
while row_right_diagonal - 1 >= 0 and col_right_diagonal + 1 < np.shape(binary_img)[1] and binary_img[row_right_diagonal,col_right_diagonal] == 1: # go in the right diagonal direction until we reach end of neighbors or we hit a background pixel
row_right_diagonal -= 1 # move right diagonal
col_right_diagonal += 1 # move right diagonal
dist_right_diagonal += 1 # add a pixel as a distance to the background
distance_image[row,col] = min([dist_up, dist_left, dist_left_diagonal, dist_right_diagonal]) # assign the minimum distance to the current pixel location
for row in range(np.shape(binary_img)[0]-1,-1,-1): # loop over the image rows in reverse order
for col in range(np.shape(binary_img)[1]-1,-1,-1): # loop over the image columns in reverse order
if binary_img[row,col] == 1: # check if it's a foreground pixel
if neighborhood == 4: # if we are considering 4 neighbors
row_down = row # saving row for processing neighbors in the down direction
col_down = col # saving column for processing neighbors in the down direction
dist_down = 0 # distance in the down direction
row_right = row # saving row for processing neighbors in the right direction
col_right = col # saving column for processing neighbors in the right direction
dist_right = 0 # distance in the right direction
while row_down + 1 < np.shape(binary_img)[0] and binary_img[row_down,col_down] == 1: # go in the down direction until we reach end of neighbors or we hit a background pixel
row_down += 1 # move down
dist_down += 1 # add a pixel as a distance to the background
while col_right + 1 < np.shape(binary_img)[1] and binary_img[row_right,col_right] == 1: # go in the right direction until we reach end of neighbors or we hit a background pixel
col_right += 1 # move right
dist_right += 1 # add a pixel as a distance to the background
distance_image[row,col] = min([dist_down, dist_right, distance_image[row,col]]) # assign the minimum distance to the current pixel location
if neighborhood == 8: # if we are considering 8 neighbors
row_down = row # saving row for processing neighbors in the down direction
col_down = col # saving column for processing neighbors in the down direction
dist_down = 0 # distance in the down direction
row_right = row # saving row for processing neighbors in the right direction
col_right = col # saving column for processing neighbors in the right direction
dist_right = 0 # distance in the right direction
row_down_right_diagonal = row # saving row for processing neighbors in the down right diagonal direction
col_down_right_diagonal = col # saving column for processing neighbors in the down right diagonal direction
dist_down_right_diagonal = 0 # distance in the down right diagonal direction
row_down_left_digonal = row # saving row for processing neighbors in the down left diagonal direction
col_down_left_diagonal = col # saving column for processing neighbors in the down left diagonal direction
dist_down_left_diagonal = 0 # distance in the down left diagonal direction
while row_down + 1 < np.shape(binary_img)[0] and binary_img[row_down,col_down] == 1: # go in the down direction until we reach end of neighbors or we hit a background pixel
row_down += 1 # move down
dist_down += 1 # add a pixel as a distance to the background
while col_right + 1 < np.shape(binary_img)[1] and binary_img[row_right,col_right] == 1: # go in the right direction until we reach end of neighbors or we hit a background pixel
col_right += 1 # move right
dist_right += 1 # add a pixel as a distance to the background
while row_down_right_diagonal + 1 < np.shape(binary_img)[0] and col_down_right_diagonal + 1 < np.shape(binary_img)[1] and binary_img[row_down_right_diagonal,col_down_right_diagonal] == 1: # go in the down right diagonal direction until we reach end of neighbors or we hit a backgraound pixel
row_down_right_diagonal += 1 # move down right diagonal
col_down_right_diagonal += 1 # move down right diagonal
dist_down_right_diagonal += 1 # add a pixel as a distance to the background
while row_down_left_digonal + 1 < np.shape(binary_img)[0] and col_down_left_diagonal - 1 >= 0 and binary_img[row_down_left_digonal,col_down_left_diagonal] == 1: # go in the down left diagonal direction until we reach end of neighbors or we hit a background pixel
row_down_left_digonal += 1 # move down left diagonal
col_down_left_diagonal -= 1 # move down left diagonal
dist_down_left_diagonal += 1 # add a pixel as a distance to the background
distance_image[row,col] = min([dist_down, dist_right, dist_down_right_diagonal, dist_down_left_diagonal, distance_image[row,col]]) # assign the minimum distance to the current pixel location
return distance_imageI have used Adobe-240 dataset for this implementation. This video helped me understand the algorithm. That’s it for now. See you later.
