Group them by your positions with MATLAB?

Question

I have a matrix in MATALB with elements {0, 1}. I want to collect those 1in groups following these rules:

• I start with anyone 1in the matrix, and I put it, say, in group1.
• After I go over and see if there is a corresponding row and column. If so, I add all of this row and column to group1.
• Each time I find one in a row or in a column, I go and I see the corresponding row and column, and I add them to this group ( group1).
• If I do not find anyone else in the corresponding row or column, I will move on to the next group, say, group2
• I continue this way until one is found in the matrix.

Here I will give a simple example:

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

group1 = {(1, 1)}
% I put in group1 the first element A(1, 1) (arbitrarly)
% Since in row 1 and column 1 we have A(1, 4) = 1 and A(2, 1) = 1 so I 
% add them to group1
group1 = {(1, 1), (1, 4), (2, 1)}
% We see now that I have no one that correspond to the element A(2, 1) since 
% A(2, :) = 0 and A(:, 1) = 0. But I have ones that correspond to element A(1, 4) 
% which are A(3, 4) and A(4, 4) so I add them to group1
group1 = {(1, 1), (1, 4), (2, 1), (3, 4), (4, 4)}
% Also A(3, 4) and A(4, 4) have no corresponding ones. Hence I stop and I go to group2
group2 = {(5, 2)}
% I do the same and I get:
group1 = {(1, 1), (1, 4), (2, 1), (3, 4), (4, 4)}
group2 = {(5, 2), (5, 3)}

, , :

for i = 1:size(A, 1)
   e{i} = find(A(i, :)~=0);
end
for j = 1:size(A, 1)
   for i = e{j}
      a{i} = find(A(:, i)~=0);
   end
end

, ? ?

.

Answer 1

( ), / , , .

, :

groups = []
while any_points_left(A):
    group = []
    stack = [pick_random_point(A)]
    while not_empty(stack):
        p = stack.pop()
        group.append(p)
        mark_as_done(p)
        for q in all_points_in_same_row_or_column(p):
            stack.append(q)
    groups.append(group)

Matlab ( ):

groups = {};
while nnz(A) > 0 % any points left?
    % find random point
    [i, j] = ind2sub(size(A), find(A, 1, 'first'));
    stack = {[i, j]};
    group = {};
    while ~isempty(stack)
        p = stack{end}; stack = stack(1:end-1); % pop point from stack
        i = p(1); j = p(2);
        if A(i, j) == 0 % check if point is not already removed
            continue
        end
        A(i, j) = 0; % mark as done   
        group{end+1} = p; % add to group

        for ii = 1:size(A, 1) % check same column
            if A(ii, j) == 1
                stack{end+1} = [ii, j]; % add to stack
            end
        end        
        for jj = 1:size(A, 2) % check same row
            if A(i, jj) == 1
                stack{end+1} = [i, jj]; % add to stack
            end
        end
    end
    groups{end+1} = group;
end

% print result
for ig = 1:length(groups)
    fprintf('Group %i: ', ig)
    group = groups{ig};
    for ip = 1:length(group)
        fprintf('(%i, %i) ', group{ip}(1), group{ip}(2))
    end
    fprintf('\n')
end

. :

Group 1: (1, 1) (1, 4) (4, 4) (3, 4) (2, 1) 
Group 2: (5, 2) (5, 3) 

Answer 2

, , , . :

:

Apad=padarray(A, [1,1], 0, 'both');

:

se1 = strel('line',3,0);
se2 = strel('line',3,90);
closedA = imclose(Apad,se1);
closedA = imclose(closedA,se2);

,

Segments=closedA(2:end-1, 2:end-1);

:

Segments =

     1     1     1     1     0
     1     0     0     1     0
     0     0     0     1     0
     0     0     0     1     0
     0     1     1     0     0

:

CC = bwconncomp(Segments,4);

A, :

LinIndices=find(A);
for k=1:CC.NumObjects
   Pixels{k}=LinIndices(ismember(LinIndices, CC.PixelIdxList{k}))
end

Pixels, :

Pixels{1}= [1 2 16 18 19]

Pixels{2}= [10 15]

:

A(Pixels{1})=1
A(Pixels{2})=2

A =

     1     0     0     1     0
     1     0     0     0     0
     0     0     0     1     0
     0     0     0     1     0
     0     2     2     0     0

se1 se2 . . @Bentoy13 .

Answer 3

Following @Jigg's idea , I propose another very similar solution.

Find the first and last indices for each row and column, where there is 1. Fill the segment between the two indices with the units in another matrix:

B = zeros(size(A));
for i=1:size(A,1)
    m1 = find(A(i,:),1,'first');
    m2 = find(A(i,:),1,'last');
    B(i,m1:m2) = 1;
end
for i=1:size(A,2)
    m1 = find(A(:,i),1,'first');
    m2 = find(A(:,i),1,'last');
    B(m1:m2,i) = 1;
end

(Maybe a shorter way to do this ...)

Then mark all connected components of the new array B and mask it with array A:

Result = bwlabel(A,4).*A;