0

I am trying to compute the pairwise distances between all points in two binary areas/volume/hypervolume in Tensorflow.

E.g. In 2D the areas are defined as binary tensors with ones and zeros:

input1 = tf.constant(np.array([[1,0,0], [0,1,0], [0,0,1]))
input2 = tf.constant(np.array([[0,1,0], [0,0,1], [0,1,0]))

input1 has 3 points and input2 has 2 points.

So far I have managed to convert the binary tensors into arrays of spatial coordinates:

coord1 = tf.where(tf.cast(input1, tf.bool))
coord2 = tf.where(tf.cast(input2, tf.bool))

Where, coord1 will have shape=(3,2) and coord2 will have shape=(2,2). The first dimension refers to the number of points and the second to their spatial coordinates (in this case 2D).

The result that I want is a tensor with shape=(6, ) with the pairwise Euclidean distances between all of the points in the areas. Example (the order of the distances might be incorrect): 

output = [1, sqrt(5), 1, 1, sqrt(5), 1]

Since TensorFlow isn't great with loops and in my real application the number of points in each tensor is unknown, I think I might be missing some linear algebra here.

Miguel Monteiro
  • 389
  • 1
  • 2
  • 16

2 Answers2

1

I'm not familiar with Tensorflow, but my understanding from reading this is that the underlying NumPy arrays should be easy to extract from your data. So I will provide a solution which shows how to calculate pairwise Euclidean distances between points of 3x2 and 2x2 NumPy arrays, and hopefully it helps.

Generating random NumPy arrays in the same shape as your data:

coord1 = np.random.random((3, 2))
coord2 = np.random.random((2, 2))

Import the relevant SciPy function and run:

from scipy.spatial.distance import cdist
distances = cdist(coord1, coord2, metric='euclidean')

This will return a 3x2 array, but you can use distances.flatten() to get your desired 1-dimensional array of length 6.

sjw
  • 6,213
  • 2
  • 24
  • 39
  • 1
    Thanks, but the whole point is to do it with tensors and not use external packages. I think I have figured out the answer using matrix multiplication and transposition alone. – Miguel Monteiro Mar 28 '18 at 18:09
  • @Miguel Understood, unfortunately I can't help with that, glad you figured out a solution anyway. – sjw Mar 28 '18 at 18:12
0

I have come up with an answer using only matrix multiplies and transposition. This makes use of the fact that distances can be expressed with inner products (d^2 = x^2 + y^2 - 2xy):

input1 = np.array([[1,0,0],[0,1,0],[0,0,1]])
input2 = np.array([[1,1,0],[0,0,1],[1,0,0]])
c1 = tf.cast(tf.where(tf.cast(input1, tf.bool)), tf.float32)
c2 = tf.cast(tf.where(tf.cast(input2, tf.bool)), tf.float32)

distances = tf.sqrt(-2 * tf.matmul(c1, tf.transpose(c2)) + tf.reduce_sum(tf.square(c2), axis=1)
                + tf.expand_dims(tf.reduce_sum(tf.square(c1), axis=1), axis=1))

with tf.Session() as sess:
     d = sess.run(distances)

Since Tensorflow has broadcast by default the fact the arrays have different dimensions doesn't matter.

Hope it helps somebody.

Miguel Monteiro
  • 389
  • 1
  • 2
  • 16