SIMD implementation of 2d reverse euclidean distance. See "Optimal Separable Algorithms to Compute the Reverse Euclidean Distance Transformation and Discrete Medial Axis in Arbitrary Dimension" D. Coeurjolly et al.

reverse-euclidean-distance-transform.py

import numpy



def reverse_euclidean_distance_transform(F):
	ret = numpy.empty_like(F, dtype = int)

	def get_parabola_matrix(N):
		X = numpy.arange(N, dtype = int)
		G = numpy.empty((N, N), dtype = int)
		G[:] = X
		G -= X[:, None]
		G *= G
		G *= -1
		return G

	# Horizontal pass
	G = get_parabola_matrix(F.shape[1])
	for i in range(F.shape[0]):
		numpy.amax(G + F[i][:, None], axis = 0, out = ret[i, :])		

	# Vertical pass
	G = get_parabola_matrix(F.shape[0])	
	for i in range(F.shape[1]):
		numpy.amax(G + ret[:,i][:, None], axis = 0, out = ret[:, i])		

	# Job done
	return ret