Turning iteratively all elements after and above a '1' into '0'-s starting from the left bottom corner

I have logical square matrices consisting of non-intersecting rectangular patches of '1'-s with no gaps and otherwise '0'-s. 'No gaps' in particular means that two different rectangular patches are not allowed to share horizontal or vertical coordinates. Moreover, the rectangular patches are strictly monotone increasing from the POV of the bottom left corner. For example:

A = [0 0 0 0 1;
     0 0 0 0 1; 
     0 1 1 1 0; 
     0 1 1 1 0;
     1 0 0 0 0]

I would like to perform the following operation on A in a fast way, possibly on GPU. Starting from the left bottom corner, I would like to iteratively turn all elements above and after a '1' into '0'. For example:

B = [0 0 0 0 0;
     0 0 0 0 1; 
     0 0 1 0 0; 
     0 1 0 0 0;
     1 0 0 0 0]

That is, B(3,3) = 1 because after the iteration at A(4,2), A(4,3) turns into a '0'.

My logical matrices are of size at most 15 and I would like to perform this operation on a 3D-array of many such square matrices stacked upon each other in a fast way, hence the request for vectorizability if possible.

[James Tursa]

Why is B(3,3) a 1? That is "above" and "after" other 1's in A. I think we need clarification on your criteria. Is the criteria iteratively applied in some fashion? Or ...?

I would have suggested simple shifting and logical indexing to get the result based on your wording, but the B(3,3) element doesn't fit your wording.

[Marin Genov]

@James Tursa: You are absolutely right! This was an oversight on my part. Give me some time to revise the question.

[Marin Genov]

@James Tursa: I have now revised the question. Please have a look if it is clear now. Yes, the B(3,3) is supposed to be 1 rather than 0, my wording was poor.

[James Tursa]

If you apply iteratively from lower left corner, then why isn't B(4,4)=1?

[Matt J]

Starting from the left bottom corner,

And rastering in which direction? From left to right first, or from bottom to top first?

That is, B(3,3) = 1 because after the iteration at A(2,2), A(3,4) turns into a '0'.

In the matrix that you've shown A(2,2) and A(3,4) begin as zero.Or are your coordinates relative to the bottom left corner? And if so, which is the horizontal coordinate?

[Marin Genov]

@Matt J Gosh, nothing is going right today. I was implicitly counting from bottom to top, sorry about that. It's been a long day. I fixed now the coordinates in the example to be standard matrix coordinates. The rastering direction is diagonal so to speak. Basically, you are jumping from lower left corner to lower left corner, patch by patch. Also, the matrix is square.

@James Tursa: Because A(4,2) = 1. The zeroing procedure is simultaneous in the column above the 1 and the row after the 1. The important thing is that the patches are rectangular and contain no gaps of 0-s. So, if you start at lower left corner and turn everything above and eveything on the RHS into 0, you are left with a strictly smaller patch, 1x1 patch counts too.

I hope that makes more sense now.

[Marin Genov]

@Matt J: Oh, I see what you mean by rastering direction. I added the clarification that the 'no gaps' condition also means that different rectangular patches do not share vertical or horizontal coordinates.

Answer 1

[DGM]

This might not be particularly efficient, but maybe it's one way (if i'm interpreting it right):

A = [0 0 0 0 0 0 1
     0 0 0 0 0 0 1;
     0 0 0 0 1 1 0;
     0 0 0 0 1 1 0; 
     0 1 1 1 0 0 0; 
     0 1 1 1 0 0 0;
     1 0 0 0 0 0 0];

D = rot90(hankel(size(A,1):-1:1),2).*A;
D(D==0) = NaN;
Dmin = min(D,[],2);
D = D - (flip(cummax(flip(Dmin)))-1);

output = D==1

output = 7×7 logical array
   0   0   0   0   0   0   0
   0   0   0   0   0   0   1
   0   0   0   0   0   1   0
   0   0   0   0   1   0   0
   0   0   1   0   0   0   0
   0   1   0   0   0   0   0
   1   0   0   0   0   0   0

[Marin Genov]

Thanks! Yes, your interpretation seems correct.