elimination of conscutive regions (generalization: ones with zeros between)

Question

Michal Kvasnicka on 1 Oct 2018

0

Commented: Bruno Luong on 2 Oct 2018

I need effectively eliminate (by zeroing) the consecutive "1's" between "-1's" and start/end of column at each column of matrix A, which now can be separated by any number of zeroes. The number of consecutive "1's" between "-1's" and start/end of column is > N. This is a non-trivial generalization of my previous Question.

Again, typical size(A) = [100000,1000].

See example:

A =
     1    -1     0
     0     1     1
     0     1     1
     1     1     0
     0     0     1
     1    -1     0
    -1     1     1
    -1     0    -1
     1     1     1
     0     1    -1

For N = 2 the expected result is

Aclean =
     0    -1     0
     0     0     0
     0     0     0
     0     0     0
     0     0     0
     0    -1     0
    -1     0     0
    -1     0    -1
     1     0     1
     0     0    -1

For N = 3 the expected result is

Aclean =
    1    -1     0
    0     1     0
    0     1     0
    1     1     0
    0     0     0
    1    -1     0
   -1     1     0
   -1     0    -1
    1     1     1
    0     1    -1

4 Comments

Show 1 older comment

Michal Kvasnicka on 1 Oct 2018

I need to eliminate (zeroed) all "1's" which are located between "-1's" and start/end at each column of A separately. The number of eliminated "1's" between "-1's" is greater than user defined N.

So in my example, in 1st column of A are three "1's" and any number of "0's", separated by two "-1's" and then one "1's". For N = 2 I will eliminate only first 3 > (N=2) "1's". For N = 3 I do not eliminate any "1's" from 1st columns of A. Similarly for all columns.

Matt J on 1 Oct 2018

which now can be separated by any number of zeroes

This is the definition of non-consecutive. Why, then, are you saying the eliminated 1's are to be consecutive?

Michal Kvasnicka on 1 Oct 2018

Well OK, any sequence of "1's" and "0's" separated by start/end and "-1's".

Sign in to comment.

Sign in to answer this question.

Answer 1

Bruno Luong on 1 Oct 2018

0
Link

Direct link to this answer

https://ww2.mathworks.cn/matlabcentral/answers/421655-elimination-of-conscutive-regions-generalization-ones-with-zeros-between#answer_339293

A = [1    -1     0;
     0     1     1;
     0     1     1;
     1     1     0;
     0     0     1;
     1    -1     0;
    -1     1     1;
    -1     0    -1;
     1     1     1;
     0     1    -1];
N = 3;
[m,n] = size(A);
Aclean = A;
for j=1:n
    Aj = [-1; A(:,j); -1];
    i = find(Aj == -1);
    c = histc(find(Aj==1),i);
    b = c <= N;
    im = i(b);
    ip = i([false; b(1:end-1)]);
    a = accumarray(im,1,[m+2,1])-accumarray(ip,1,[m+2,1]);
    mask = cumsum(a);
    mask(i) = 1;
    Aclean(:,j) = Aclean(:,j).*mask(2:end-1);
end
Aclean

3 Comments

Bruno Luong on 1 Oct 2018

Cleaner version

[m,n] = size(A);
Aclean = A;
for j=1:n
    Aj = A(:,j);
    im1 = find(Aj == -1);
    i1 = find(Aj==1);
    [c,loc] = histc(i1,[-Inf; im1; Inf]);
    b = c > N;
    Aclean(i1(b(loc)),j) = 0;
end

Michal Kvasnicka on 2 Oct 2018

Is there any serious reason to still use old "histc" instead "histcounts"? Both functions has same performance and "histc" will be removed in future releases.

Bruno Luong on 2 Oct 2018

No, I'm just used to HISTC.

Sign in to comment.

Answer 2

Michal Kvasnicka on 1 Oct 2018

1
Link

Direct link to this answer

https://ww2.mathworks.cn/matlabcentral/answers/421655-elimination-of-conscutive-regions-generalization-ones-with-zeros-between#answer_339295

Edited: Michal Kvasnicka on 1 Oct 2018

I am still looking for better (faster) solution. Any idea how to improve so far best solution:

A = [1    -1     0;
     0     1     1;
     0     1     1;
     1     1     0;
     0     0     1;
     1    -1     0;
    -1     1     1;
    -1     0    -1;
     1     1     1;
     0     1    -1];
N = 3;
sep = A==-1;
sep(1,:) = true;
idx = cumsum(sep(:));
sep(1,:) = A(1,:)==-1;
num = accumarray(idx, A(:)==1);
iff = num <= N;
Aclean  = reshape(sep(:)|iff(idx), size(A)) .* A;
Aclean

Big test matrix:

A = double(rand(100000,1000)>.4) - double(rand(100000,1000)>.65);

Bruno's code (N = 5): Elapsed time is 4.848747 seconds.

My code (N = 5): Elapsed time is 3.257089 seconds.

13 Comments

Show 10 older comments

Bruno Luong on 2 Oct 2018

It's not the same thing than

~xor(Aclean, A)

Michal Kvasnicka on 2 Oct 2018

Yes … nice simplification!

Bruno Luong on 2 Oct 2018

And what about

mask = Aclean==A

?

Sign in to comment.

Answer 3

Bruno Luong on 2 Oct 2018

0
Link

Direct link to this answer

https://ww2.mathworks.cn/matlabcentral/answers/421655-elimination-of-conscutive-regions-generalization-ones-with-zeros-between#answer_339411

That's true, somehow it's a 1D scanning problem.

I think we are close to the limit of MATLAB can do, if faster speed is still needed, then one should go to MEX programming route instead of torturing MATLAB to squeeze out the last once of speed.

1 Comment

Bruno Luong on 2 Oct 2018

Sorry, it should be in the comment section

Sign in to comment.

You are now following this question

elimination of conscutive regions (generalization: ones with zeros between)

4 Comments

Accepted Answer

3 Comments

More Answers (2)

13 Comments

1 Comment

See Also

Categories

Tags

Products

Release

Community Treasure Hunt

Tags

Products

Release

See Also

Community Treasure Hunt

You are now following this question

elimination of conscutive regions (generalization: ones with zeros between)

4 Comments

Accepted Answer

3 Comments

More Answers (2)

13 Comments

1 Comment

See Also

Categories

Tags

Products

Release

Community Treasure Hunt

Tags

Products

Release

See Also

Community Treasure Hunt

An Error Occurred

WeChat