0
$\begingroup$

Question:

I want to compare every item in a 3D array with its first neighborhoods. It's really slow when I have a 500x500x500 (e.g. with only values of 0, 1, 2) ndarray. I post the principle lines here:

import numpy as np

# Create a list to stock all the neighbours' coordinations of the voxel wanted 
def check_neighbor(array, x, y, z):
   #top
   t = array[x, y , z + 1]
   #down
   d = array[x, y , z - 1]
   #left
   l = array[x, y - 1 , z]
   #right
   r = array[x, y + 1 , z]
   #front
   f = array[x - 1, y , z]
   #back
   b = array[x + 1, y , z]
   return [t, d, l, r, f, b]

# Check the voxel with all its neighborhood
def compare_neighbor(array, Value2match, Value2Bmatched):
   for index in np.argwhere(array==Value2match)
      output[index] = 1 if Value2BMatched in checkneighbor(array, index[0],index[1], index[2]) else 0 
   return output

# Main
array = np.random.randint(3, shape=(500, 500, 500))
output = compare_neighbor(array, 1, 2)

This code take me hours only for the n=1 neighbour! Is there an efficient way which can also check the 2, 3... nearest neighbours? Can somebody help me?

Solution 1:

Based on jayprich's answer and n1k31t4's comments, I fused the both function into one and replace the argwhere() by where(). The advantage of this code is that we don't iterate voxel by voxel but do it in a vectorized way:

import numpy as np
# Build a helper function to SHIFT(not roll) a 3Darray
def shift_helper(array, neib_value, shift=0, axis=0):
    #Roll the 3D array along axis with certain unity
    _array = np.roll(array == neib_value, shift=shift, axis=axis)

    # Cancel the last/first slice shifted to the first/last slice
    if axis == 0:
        if shift >= 0:
            _array[:1, :, :] = 0
        else:
            _array[-1:, :, :] = 0
        return _array
    elif axis == 1:
        if shift >= 0:
            _array[:, :1, :] = 0
        else:
            _array[:, -1:, :] = 0
        return _array
    elif axis == 2:
        if shift >= 0:
            _array[:, :, :1] = 0
        else:
            _array[:, :, -1:] = 0
        return _array


def compneib(array, that_value, neib_value):
    _array = np.zeros(array.shape)
    _array[np.where((array == that_value)
                    & (shift_helper(array, neib_value, shift=-1, axis=0)
                    | shift_helper(array, neib_value, shift=1, axis=0)
                    | shift_helper(array, neib_value, shift=-1, axis=1)
                    | shift_helper(array, neib_value, shift=1, axis=1)
                    | shift_helper(array, neib_value, shift=-1, axis=2)
                    | shift_helper(array, neib_value, shift=1, axis=2)
                    ))] = 1
    return _array

# Main
array = np.random.randint(3, shape=(500, 500, 500))
output = compneib(array, 1, 2)

Solution 2:

If there would still be a faster way.

$\endgroup$
  • $\begingroup$ What is output exactly, within compare_neighbor? You have not initialised it. Also, is there an upper limit on the integer contents of your main input array? $\endgroup$ – n1k31t4 Jun 28 '18 at 20:11
  • $\begingroup$ Thanks for your replies. It's true that I just showed the principle lines. Output is a np.ndarray. Then I did a zero-padding of one layer to the surface of the matrix in order to avoiding the out of range from the check_neighbor function $\endgroup$ – Zézouille Jun 28 '18 at 20:19
  • $\begingroup$ I think you are on the right lines, using an approach like @jayprich's. Your Solution 1 code does not work though, as there are basic copy/paste errors I think. Can you fix it? Also, is there an upper limit on the integer values that can be present in your input array? $\endgroup$ – n1k31t4 Jun 29 '18 at 10:52
  • $\begingroup$ @n1k31t4 thanks for your remark. I edited and added a helper function to remove the lowest or toppest slice. Please try again $\endgroup$ – Zézouille Jun 29 '18 at 12:05
1
$\begingroup$

NumPy performs operations in a vectorised manner, you should try and operate on the whole array and avoid explicit loops.

e.g. np.argwhere( (test == 1) & np.roll( test==2 , shift=-1 , axis=0 ) )

can be done for different shift and axis values and results combined

$\endgroup$
  • $\begingroup$ Thanks, I tested but it's still very slow. np.argwhere((array == 1) & (np.roll(array == 2, shift=-1, axis=0) | np.roll(array == 2, shift=1, axis=0) | np.roll(array == 2, shift=-1, axis=1) | np.roll(array == 2, shift=1, axis=1) | np.roll(array == 2, shift=-1, axis=2) | np.roll(array == 2, shift=1, axis=2))) $\endgroup$ – Zézouille Jun 28 '18 at 21:35
  • $\begingroup$ The np.where() works better than the argwhere(). I edited the question $\endgroup$ – Zézouille Jun 29 '18 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.