Find distance between all pairs of pixels in an image

user_6580268 0
Viewed 373

Question

I have a numpy.array of shape (H, W), storing pixel intensities of an image. I want to generate a new array of shape (H, W, H, W), which stores the Euclidean distance between each pair of pixels in the image (the "spatial" distance between the pixels; not the difference in their intensities).

Solution attempt

The following method does exactly what I want, but very slowly. I'm looking for a fast way to do this.

d = numpy.zeros((H, W, H, W)) # array to store distances.
for x1 in range(H):
    for y1 in range(W):
        for x2 in range(H):
            for y2 in range(W):
                d[x1, y1, x2, y2] = numpy.sqrt( (x2-x1)**2 + (y2-y1)**2 )

Extra details

Here are more details for my problem. A solution to the simpler problem above would probably be enough for me to figure out the rest.

  • In my case, the image is actually a 3D medical image (i.e. a numpy.array of shape (H, W, D)).
  • The 3D pixels might not be cubic (e.g. each pixel might represent a volume of 1mm x 2mm x 3mm).
linear-algebra numpy python performance
1 Answers

We can setup open grids with 1D ranged arrays using np.ogrid, which could be operated upon in the same iterator notation for a vectorized solution and this will leverage broadcasting for the perf. boost :

X1,Y1,X2,Y2 = np.ogrid[:H,:W,:H,:W]
d_out = numpy.sqrt( (X2-X1)**2 + (Y2-Y1)**2 )

To save on two open grids :

X,Y = np.ogrid[:H,:W]
d_out = numpy.sqrt( (X[:,:,None,None]-X)**2 + (Y[:,:,None,None]-Y)**2 )

If we are working with large arrays, consider using numexpr for further boost :

import numexpr as ne

d_out = ne.evaluate('sqrt( (X2-X1)**2 + (Y2-Y1)**2 )')
user_32938810
Related