How to get all array edges?

Question

I have a n x n array, and want to receive its outline values. For example,

[4,5,6,7]

[2,2,6,3]

[4,4,9,4]

[8,1,6,1]

from this, i would get this

[4,5,6,7,3,4,1,6,1,8,4,2]

(see where bold)

So essentially, what is the most efficient way of getting a 1D array of all the values going around the edges of a 2D array? I ask because I assume there is a numPy function that helps with this (which I haven't yet found!), instead of doing it manually with loops?

Answer 1

In [1]: arr=np.arange(16).reshape(4,4)
In [2]: arr
Out[2]: 
array([[ 0,  1,  2,  3],
       [ 4,  5,  6,  7],
       [ 8,  9, 10, 11],
       [12, 13, 14, 15]])

A relatively straight forward way of doing this - in clockwise order is:

In [5]: alist=[arr[0,:-1], arr[:-1,-1], arr[-1,::-1], arr[-2:0:-1,0]]
In [6]: alist
Out[6]: [array([0, 1, 2]), array([ 3,  7, 11]), array([15, 14, 13, 12]), array([8, 4])]
In [7]: np.concatenate(alist)
Out[7]: array([ 0,  1,  2,  3,  7, 11, 15, 14, 13, 12,  8,  4])

In a sense it's a loop, in that I have to build 4 slices. But if 4 is small compared to n, that's a small price. It has to concatenate at some level.

If order doesn't matter we could simplify the slices some (e.g. forgetting the reverse order, etc).

alist=[arr[0,:], arr[1:,-1], arr[-1,:-1], arr[1:-1,0]]

If I didn't care about order, or double counting the corners I could use:

np.array([arr[[0,n],:], arr[:,[0,n]].T]).ravel()

eliminating the duplicate corners

In [18]: np.concatenate((arr[[0,n],:].ravel(), arr[1:-1,[0,n]].ravel()))
Out[18]: array([ 0,  1,  2,  3, 12, 13, 14, 15,  4,  7,  8, 11])

Answer 2

Here's one vectorized approach to create a mask of such edge pixels/elements and then simply indexing into the array to get those -

def border_elems(a, W): # Input array : a, Edgewidth : W
    n = a.shape[0]
    r = np.minimum(np.arange(n)[::-1], np.arange(n))
    return a[np.minimum(r[:,None],r)<W]

Again, this not exactly meant for performance, but more for cases when you might to vary the edge-width or just create such a mask of such edge elements. The mask would be : np.minimum(r[:,None],r)<W as created at the last step.

Sample run -

In [89]: a
Out[89]: 
array([[49, 49, 12, 90, 42],
       [91, 58, 92, 16, 78],
       [97, 19, 58, 84, 84],
       [86, 31, 80, 78, 69],
       [29, 95, 38, 51, 92]])

In [90]: border_elems(a,1)
Out[90]: array([49, 49, 12, 90, 42, 91, 78, 97, 84, 86, 69, 29, 95, 38, 51, 92])

In [91]: border_elems(a,2) # Note this will select all but the center one : 58
Out[91]: 
array([49, 49, 12, 90, 42, 91, 58, 92, 16, 78, 97, 19, 84, 84, 86, 31, 80,
       78, 69, 29, 95, 38, 51, 92])

For generic shape, we can extend like so -

def border_elems_generic(a, W): # Input array : a, Edgewidth : W
    n1 = a.shape[0]
    r1 = np.minimum(np.arange(n1)[::-1], np.arange(n1))
    n2 = a.shape[1]
    r2 = np.minimum(np.arange(n2)[::-1], np.arange(n2))
    return a[np.minimum(r1[:,None],r2)<W]

2D convolution based solution for generic shape

Here's another with 2D convolution that takes care of generic 2D shape -

from scipy.signal import convolve2d

k = np.ones((3,3),dtype=int) # kernel
boundary_elements = a[convolve2d(np.ones(a.shape,dtype=int),k,'same')<9]

Sample run -

In [36]: a
Out[36]: 
array([[4, 3, 8, 3, 1],
       [1, 5, 6, 6, 7],
       [9, 5, 2, 5, 9],
       [2, 2, 8, 4, 7]])

In [38]: k = np.ones((3,3),dtype=int)

In [39]: a[convolve2d(np.ones(a.shape,dtype=int),k,'same')<9]
Out[39]: array([4, 3, 8, 3, 1, 1, 7, 9, 9, 2, 2, 8, 4, 7])

Answer 3

Assuming your list is in the following format:

l = [
     [4, 5, 6, 7],
     [2, 2, 6, 3],
     [4, 4, 9, 4],
     [8, 1, 6, 1]
    ]

You can achieve what you want with this quick one-liner, using list comprehensions:

out = list(l[0]) +  # [4, 5, 6, 7]
      list([i[-1] for i in l[1:-1]]) +  # [3, 4]
      list(reversed(l[-1])) +  # [1, 6, 1, 8]
      list(reversed([i[0] for i in l[1:-1]])) # [4, 2]

print(out)  # gives [4, 5, 6, 7, 3, 4, 1, 6, 1, 8, 4, 2]

This works whether you have a plain python list or a numpy array.

Regarding efficiency, using %timeit on a 20000x20000 matrix, this method took 16.4ms.

l = np.random.random(20000, 20000)
%timeit list(l[0]) + list(...) + list(...) + list(...)
100 loops, best of 3: 16.4 ms per loop

I'm sure there are more efficient methods to accomplish this task, but I think that's pretty good for a one-liner solution.

Answer 4

It's probably slower than the alternatives mentioned in the other answers because it's creating a mask (which was my use-case then) it can be used in your case:

def mask_borders(arr, num=1):
    mask = np.zeros(arr.shape, bool)
    for dim in range(arr.ndim):
        mask[tuple(slice(0, num) if idx == dim else slice(None) for idx in range(arr.ndim))] = True  
        mask[tuple(slice(-num, None) if idx == dim else slice(None) for idx in range(arr.ndim))] = True  
    return mask

As already said this creates and returns a mask where the borders are masked (True):

>>> mask_borders(np.ones((5,5)))
array([[ True,  True,  True,  True,  True],
       [ True, False, False, False,  True],
       [ True, False, False, False,  True],
       [ True, False, False, False,  True],
       [ True,  True,  True,  True,  True]], dtype=bool)

>>> # Besides supporting arbitary dimensional input it can mask multiple border rows/cols
>>> mask_borders(np.ones((5,5)), 2)
array([[ True,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True],
       [ True,  True, False,  True,  True],
       [ True,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True]], dtype=bool)

To get the "border" values this needs to be applied with boolean indexing to your array:

>>> arr = np.array([[4,5,6,7], [2,2,6,3], [4,4,9,4], [8,1,6,1]])

>>> arr[mask_borders(arr)]
array([4, 5, 6, 7, 2, 3, 4, 4, 8, 1, 6, 1])

Answer 5

You can also use itertools.groupby and list comprehension like the example below:

a = [
        [4,5,6,7],
        [2,2,6,3],
        [4,4,9,4],
        [8,1,6,1],
    ]

from itertools import groupby

def edges(a = list):
    final, i = [], []
    for k, _ in groupby(a[1:-1], lambda x : [x[0], x[-1]]):
        i += k

    return a[0] + [k for n in range(1,len(i), 2) for k in i[n:n+1]] + a[-1][::-1] + [k for n in range(0, len(i), 2) for k in i[n:n+1] ][::-1]

Output:

print(edges(a))
>>> [4, 5, 6, 7, 3, 4, 1, 6, 1, 8, 4, 2]

Test using timeit:

a = [
        [4,5,6,7],
        [2,2,6,3],
        [4,4,9,4],
        [8,1,6,1],
    ]

from itertools import groupby

def edges():
    final, i = [], []
    for k, _ in groupby(a[1:-1], lambda x : [x[0], x[-1]]):
        i += k

    return a[0] + [k for n in range(1,len(i), 2) for k in i[n:n+1]] + a[-1][::-1] + [k for n in range(0, len(i), 2) for k in i[n:n+1] ][::-1]


if __name__ == '__main__':
    import timeit
    print(timeit.timeit("edges()", setup="from __main__ import edges", number = 100))

Best time was 0.0006266489999688929