Neighbourhood of Scipy Labels
Question: I've got an array of objects labeled with `scipy.ndimage.measurements.label`
called `Labels`. I've got other array `Data` containing stuff related to
`Labels`. How can I make a third array `Neighbourhoods` which could serve to
map **the nearest label to _x,y_ is _L_**

Given `Labels` and `Data`, how can I use python/numpy/scipy to get
`Neighbourhoods`?

    
    
    Labels = array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                    [0, 0, 0, 0, 0, 0, 2, 2, 2, 0],
                    [0, 0, 0, 0, 0, 0, 2, 2, 2, 0],
                    [0, 0, 0, 0, 0, 0, 2, 2, 2, 0],
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] )
    
    Data = array([[1, 1, 1, 1, 1, 1, 2, 3, 4, 5],
                  [1, 0, 0, 0, 0, 1, 2, 3, 4, 5],
                  [1, 0, 0, 0, 0, 1, 2, 3, 4, 4],
                  [1, 0, 0, 0, 0, 1, 2, 3, 3, 3],
                  [1, 0, 0, 0, 0, 1, 2, 2, 2, 2],
                  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
                  [2, 2, 2, 2, 2, 1, 0, 0, 0, 1],
                  [3, 3, 3, 3, 2, 1, 0, 0, 0, 1],
                  [4, 4, 4, 3, 2, 1, 0, 0, 0, 1],
                  [5, 5, 4, 3, 2, 1, 1, 1, 1, 1]] )
    
    Neighbourhoods = array([[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
                            [1, 0, 0, 0, 0, 1, 1, 1, 1, 1],
                            [1, 0, 0, 0, 0, 1, 1, 1, 0, 2],
                            [1, 0, 0, 0, 0, 1, 1, 0, 2, 2],
                            [1, 0, 0, 0, 0, 1, 0, 2, 2, 2],
                            [1, 1, 1, 1, 1, 0, 2, 2, 2, 2],
                            [1, 1, 1, 1, 0, 2, 0, 0, 0, 2],
                            [1, 1, 1, 0, 2, 2, 0, 0, 0, 2],
                            [1, 1, 0, 2, 2, 2, 0, 0, 0, 2],
                            [1, 1, 2, 2, 2, 2, 2, 2, 2, 2]] )
    

Note: I'm not sure what should happen with ties, so used zeros in the above
`Neighbourhoods`


Answer: As suggested by David Zaslavsky, this is the job for a voroni diagram. Here is
a numpy implementation: <http://blancosilva.wordpress.com/2010/12/15/image-
processing-with-numpy-scipy-and-matplotlibs-in-sage/>

The relevant function is `scipy.ndimage.distance_transform_edt`. It has a
`return_indices` option that can be exploited to do what you need (as well as
calculate the raw distances (`data` in your example)).

As an example:

    
    
    import numpy as np
    from scipy.ndimage import distance_transform_edt
    
    labels = np.array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                      [0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                      [0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                      [0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 2, 2, 2, 0],
                      [0, 0, 0, 0, 0, 0, 2, 2, 2, 0],
                      [0, 0, 0, 0, 0, 0, 2, 2, 2, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] )
    i, j = distance_transform_edt(labels == 0, return_distances=False, 
                                  return_indices=True) 
    neighborhoods = labels[i,j]
    print neighborhoods
    

This yields:

    
    
    array([[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
           [1, 1, 1, 1, 1, 1, 1, 1, 1, 2],
           [1, 1, 1, 1, 1, 1, 1, 1, 2, 2],
           [1, 1, 1, 1, 1, 1, 1, 2, 2, 2],
           [1, 1, 1, 1, 1, 1, 2, 2, 2, 2],
           [1, 1, 1, 1, 1, 2, 2, 2, 2, 2],
           [1, 1, 1, 1, 2, 2, 2, 2, 2, 2],
           [1, 1, 1, 2, 2, 2, 2, 2, 2, 2],
           [1, 1, 2, 2, 2, 2, 2, 2, 2, 2]])
    

