How to eliminate standalone 1 or 0 in binary matrix

Hello

I have large binary matrices (order 30000 x 5000 values) in which I have to eliminate stand-alone 1's or 0's.

E.g. when a row looks like this: 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1

It should be adapted to: 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1

Or thus, when there's only one 1 between some 0's or one 0 between some 1's, it should be changed to a 0 or 1 respectively.

I have no clue how to do this except from running through the entire matrix and keeping count of the length of the series of 1's or 0's - which seems utterly inefficiënt to me. Any ideas on functions or better ways to tackle this? Thanks!

Answer 1

[Rik]

I would suggest using a convolution with a flat kernel.

kernel=ones(1,3,1);kernel=kernel/sum(kernel(:));
A=[0 0 1 1 1 0 1 1 0 0 1 0 1 1 1];
B=convn(A,kernel,'same');
C=round(B);

clc,disp([A;B;C])%display the original, the convolution result and the final output

         0         0    1.0000    1.0000    1.0000         0    1.0000    1.0000         0         0    1.0000         0    1.0000    1.0000    1.0000
         0    0.3333    0.6667    1.0000    0.6667    0.6667    0.6667    0.6667    0.3333    0.3333    0.3333    0.6667    0.6667    1.0000    0.6667
         0         0    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000         0         0         0    1.0000    1.0000    1.0000    1.0000

Note that the [0 0 1 0 1 1] is changed to [0 0 0 1 1 1]. If you don't want that, you can change the kernel to something like this:

kernel=[1 1 1 0 0];kernel=kernel/sum(kernel(:));

[Simon Allosserie]

Hi Rik, thanks for your answer.

This seems to be the method I'm looking for. I don't know yet if your original or alternative kernel would be the best for my purpose, but I'll start from here! :)

[Simon Allosserie]

We do run into issues when we have consecutive 0 1 0 1 patterns, then the convolution just shifts it to 1 0 1 0:

1	0	0	0	0	1	1	0	1	0	1	0	1	0	1
0.333333333333333	0.333333333333333	0	0	0.333333333333333	0.666666666666667	0.666666666666667	0.666666666666667	0.333333333333333	0.666666666666667	0.333333333333333	0.666666666666667	0.333333333333333	0.666666666666667	0.333333333333333
0	0	0	0	0	1	1	1	0	1	0	1	0	1	0

Still figuring out how to clear up this one.

[Rik]

The more fundamental question is what the values should be. If you have a clear description of that, I might be able to help you find the right kernel.

Also note that this kernel only considers rows. It will work on a 2D array as well, but it will not check multiple rows at once. You can change the kernel to 2D if you want to change that.

[Simon Allosserie]

You're right, Rik.

The practical implementation is a laser that cannot switch on/off for just one pixel. So, one on/'1' in a series of off pixels or one zero/'0' pixel in a series of on pixels, should be eliminated

That means that we can keep looking in 1D rows, going from left to right.

The values should then be as follows:

1 0 0 1 1 0 1 0 1 0 0 %orig
0 0 0 1 1 1 1 1 1 0 0 %after convolution

or

0 0 1 0 0 1 0 1 0 1 1 %orig
0 0 0 0 0 0 0 0 0 1 1 %after convolution

in other words, the 0101 sequence adapts to the series of 1's or 0's before it.

Am I making it clear enough in this way? THanks for your help!

Answer 2

[Setsuna Yuuki.]

You only need a loop and correct conditional statement, the conditional can be:

if(A(n) ~= A(n+1) && A(n) ~= A(n-1) && A(n) ==  1)
            A(n) = 0;
elseif(A(n) ~= A(n+1) && A(n) ~= A(n-1) && A(n) ==  0)
            A(n) = 1;
end

so you compare only with the previous bit and the next.

[Rik]

Matlab is fast when using loops, but I would not encourage people to use loops for arrays with 600 million elements.

[Setsuna Yuuki.]

Thanks for your advice, I learn a lot from your answers

[Simon Allosserie]

@Bastian

I updated your code to be complete for an entire matrix, FYI:

for m = 1:rows
    for n = 1
        if (A(m,n) ~= A(m,n+1) && A(m,n) ~= A(m,n+2))
            A(m,n) = abs(A(m,n)-1);
        end
    end
    for n = 2:cols-1
        if (A(m,n) ~= A(m,n+1) && A(m,n) ~= A(m,n-1))
            A(m,n) = abs(A(m,n)-1);
        end
    end
    for n = cols
        if A(m,n) ~= A(m,n-1)
            A(m,n) = abs(A(m,n)-1);
        end
    end
end

[Rik]

This code can be simplified (or at least be edited to remove duplicated code):

%option 1:
sz=size(A);
for m = 1:sz(1)
    for n=1:sz(2)
        if ...
                ( n==1 && ...
                (A(m,n) ~= A(m,2  ) && A(m,n) ~= A(m,3    )) ) || ...
                ( n==sz(2) && ...
                (                      A(m,n) ~= A(m,end-1)) ) || ...
                ( ( n~=1 && n~=sz(2) ) && ...
                (A(m,n) ~= A(m,n+1) && A(m,n) ~= A(m,n-1  )) )
            A(m,n) = abs(A(m,n)-1);
        end
    end
end

%option 2:
sz=size(A);
for m = 1:sz(1)
    for n=1:sz(2)
        if n==1 
            L = (A(m,n) ~= A(m,2  ) && A(m,n) ~= A(m,3    )) ;
        elseif n==sz(2)
            L =                        A(m,n) ~= A(m,end-1)) ;
        else
            L = (A(m,n) ~= A(m,n+1) && A(m,n) ~= A(m,n-1  )) ;
        end
        if L
            A(m,n) = abs(A(m,n)-1);
        end
    end
end

[Setsuna Yuuki.]

I did it this way:

A = [0 0 1 1 1 0 1 1 0 ;0 0 0 1 0 1 0 1 1]';
[r,c,~]=size(A);
A = reshape(A,[1, r*c]);
for n = 2:r*c-1
    if(A(n) ~= A(n+1) && A(n) ~= A(n-1) && A(n) ==  1)
                A(n) = 0;
    elseif(A(n) ~= A(n+1) && A(n) ~= A(n-1) && A(n) ==  0)
                A(n) = 1;
    end
end
A = reshape(A,[r,c])';