# Fill in missing values with nearest neighbour in Python numpy masked arrays?

I am working with a 2D Numpy masked_array in Python. I need to change the data values in the masked area such that they equal the nearest unmasked value.

NB. If there are more than one nearest unmasked values then it can take any of those nearest values (which ever one turns out to be easiest to code…)

e.g.

``````import numpy
import numpy.ma as ma

a = numpy.arange(100).reshape(10,10)
fill_value=-99
a[2:4,3:8] = fill_value
a[8,8] = fill_value

>>> a  [[0 1 2 3 4 5 6 7 8 9]
[10 11 12 13 14 15 16 17 18 19]
[20 21 22 -- -- -- -- -- 28 29]
[30 31 32 -- -- -- -- -- 38 39]
[40 41 42 43 44 45 46 47 48 49]
[50 51 52 53 54 55 56 57 58 59]
[60 61 62 63 64 65 66 67 68 69]
[70 71 72 73 74 75 76 77 78 79]
[80 81 82 83 84 85 86 87 -- 89]
[90 91 92 93 94 95 96 97 98 99]],
``````
• I need it to look like this:
``````>>> a.data
[[0 1 2 3 4 5 6 7 8 9]
[10 11 12 13 14 15 16 17 18 19]
[20 21 22 ? 14 15 16 ? 28 29]
[30 31 32 ? 44 45 46 ? 38 39]
[40 41 42 43 44 45 46 47 48 49]
[50 51 52 53 54 55 56 57 58 59]
[60 61 62 63 64 65 66 67 68 69]
[70 71 72 73 74 75 76 77 78 79]
[80 81 82 83 84 85 86 87 ? 89]
[90 91 92 93 94 95 96 97 98 99]],
``````

What is the most efficient way to do this?

You could use `np.roll` to make shifted copies of `a`, then use boolean logic on the masks to identify the spots to be filled in:

``````import numpy as np
import numpy.ma as ma

a = np.arange(100).reshape(10,10)
fill_value=-99
a[2:4,3:8] = fill_value
a[8,8] = fill_value
print(a)

# [[0 1 2 3 4 5 6 7 8 9]
#  [10 11 12 13 14 15 16 17 18 19]
#  [20 21 22 -- -- -- -- -- 28 29]
#  [30 31 32 -- -- -- -- -- 38 39]
#  [40 41 42 43 44 45 46 47 48 49]
#  [50 51 52 53 54 55 56 57 58 59]
#  [60 61 62 63 64 65 66 67 68 69]
#  [70 71 72 73 74 75 76 77 78 79]
#  [80 81 82 83 84 85 86 87 -- 89]
#  [90 91 92 93 94 95 96 97 98 99]]

for shift in (-1,1):
for axis in (0,1):
a_shifted=np.roll(a,shift=shift,axis=axis)
a[idx]=a_shifted[idx]

print(a)

# [[0 1 2 3 4 5 6 7 8 9]
#  [10 11 12 13 14 15 16 17 18 19]
#  [20 21 22 13 14 15 16 28 28 29]
#  [30 31 32 43 44 45 46 47 38 39]
#  [40 41 42 43 44 45 46 47 48 49]
#  [50 51 52 53 54 55 56 57 58 59]
#  [60 61 62 63 64 65 66 67 68 69]
#  [70 71 72 73 74 75 76 77 78 79]
#  [80 81 82 83 84 85 86 87 98 89]
#  [90 91 92 93 94 95 96 97 98 99]]
``````

If you'd like to use a larger set of nearest neighbors, you could perhaps do something like this:

``````neighbors=((0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,1),(1,-1),(-1,-1),
(0,2),(0,-2),(2,0),(-2,0))
``````

Note that the order of the elements in `neighbors` is important. You probably want to fill in missing values with the nearest neighbor, not just any neighbor. There's probably a smarter way to generate the neighbors sequence, but I'm not seeing it at the moment.

``````a_copy=a.copy()
for hor_shift,vert_shift in neighbors:
a_shifted=np.roll(a_copy,shift=hor_shift,axis=1)
a_shifted=np.roll(a_shifted,shift=vert_shift,axis=0)
a[idx]=a_shifted[idx]
``````

Note that `np.roll` happily rolls the lower edge to the top, so a missing value at the top may be filled in by a value from the very bottom. If this is a problem, I'd have to think more about how to fix it. The obvious but not very clever solution would be to use `if` statements and feed the edges a different sequence of admissible neighbors...

For more complicated cases you could use scipy.spatial:

``````from scipy.spatial import KDTree
x,y=np.mgrid[0:a.shape[0],0:a.shape[1]]

print a
[[0 1 2 3 4 5 6 7 8 9]
[10 11 12 13 14 15 16 17 18 19]
[20 21 22 13 14 15 16 17 28 29]
[30 31 32 32 44 45 46 38 38 39]
[40 41 42 43 44 45 46 47 48 49]
[50 51 52 53 54 55 56 57 58 59]
[60 61 62 63 64 65 66 67 68 69]
[70 71 72 73 74 75 76 77 78 79]
[80 81 82 83 84 85 86 87 78 89]
[90 91 92 93 94 95 96 97 98 99]]
``````

I generally use a distance transform, as wisely suggested by Juh_ in this question.

This does not directly apply to masked arrays, but I do not think it will be that hard to transpose there, and it is quite efficient, I've had no problem applying it to large 100MPix images.

Copying the relevant method there for reference :

``````import numpy as np
from scipy import ndimage as nd

def fill(data, invalid=None):
"""
Replace the value of invalid 'data' cells (indicated by 'invalid')
by the value of the nearest valid data cell

Input:
data:    numpy array of any dimension
invalid: a binary array of same shape as 'data'. True cells set where data
value should be replaced.
If None (default), use: invalid  = np.isnan(data)

Output:
Return a filled array.
"""
#import numpy as np
#import scipy.ndimage as nd

if invalid is None: invalid = np.isnan(data)

ind = nd.distance_transform_edt(invalid, return_distances=False, return_indices=True)
return data[tuple(ind)]
``````