Replace adjacent duplicates in 2d array

Question

I have 2d numpy array, example:

array([[0, 1, 1, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 1, 0, 1],
       [1, 0, 0, 0, 0],
       [1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0]])

If the ones are adjacent I would like to replace all of them except one with zeros. Which one to keep doesnt matter. To create:

array([[0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0]])

I dont need a complete solution, just the name of this kind of problem and/or the method names so I can google...

Breadth first search? Don't know if there's an efficient algorithm with numpy though. — Psidom, Jul 02 '20 at 20:04
what if the adjacent 1s are a region (expands more than immediate neighbors)? Do you want to replace every region with single 1 or randomly replace immediate neighbors? — Ehsan, Jul 02 '20 at 20:24
Yes, keep only one 1 per region. The ones are always in regions of 2, 3 or 4, never larger. — BERA, Jul 02 '20 at 20:31

score 1 · Answer 1 · answered Jul 02 '20 at 22:10

More deterministic approach:

ind=np.argwhere(a==1)

a=np.zeros(a.shape).astype(int)
for i in range(len(ind)-1):
    if(np.abs(ind[i,0]-ind[i+1:,0])+np.abs(ind[i,1]-ind[i+1:,1])>1).all():
        a[tuple(ind[i])]=1
a[tuple(ind[-1])]=1

It finds all 1, then runs over the list of these marking only the ones, which don't have adjacent neighbors after them.

score 1 · Accepted Answer · answered Jul 03 '20 at 07:58

Using scipy.ndimage.measurements.label:

import scipy.ndimage.measurements

grouped,ng = scipy.ndimage.measurements.label(a,np.ones((3,3)))
out = np.empty(ng+1,int)
out[grouped.reshape(-1)] = np.arange(a.size)
np.bincount(out[1:],None,a.size).reshape(a.shape)
# array([[0, 0, 0, 0, 0],
#        [0, 0, 1, 0, 0],
#        [0, 0, 0, 0, 0],
#        [0, 0, 0, 0, 0],
#        [0, 0, 0, 0, 0],
#        [0, 0, 1, 0, 1],
#        [0, 0, 0, 0, 0],
#        [1, 0, 0, 0, 0],
#        [0, 0, 0, 0, 0],
#        [0, 0, 0, 0, 0]])

BERA · Answer 3 · 2020-07-02T20:46:54.013

0

I found one solution that seems to be working. Using the accepted answer to Peak detection in a 2D array.

First multiplying my 0/1 array with random values:

rand = np.random.rand(*arr.shape)
arr = arr*rand

Then detecting peaks:

arr = detect_peaks(arr).astype(int)

array([[0, 1, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 1, 0, 1],
       [1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0]])

edited Jul 02 '20 at 20:46

answered Jul 02 '20 at 20:14

BERA

1,345
3
16
36

Not totally convinced about this random part - in a (really) long run you might get some value twice (or close enough for algo to be considered the same), distorting the maximum - I wouldn't necessarily go this way here... – Grzegorz Skibinski Jul 02 '20 at 22:09

Replace adjacent duplicates in 2d array

3 Answers3