CODEWITHSUNDEEP
matlabmatrix
npisinp
npisinp

Reputation: 370

Group the ones according to their positions using MATLAB?

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

Here I 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)}

What I thought of is something like this:

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

Any suggestions please? Can I do it without loops?

Thank you very much for your help.

Upvotes: 4

Views: 110

Answers (3)

Bas Swinckels
Bas Swinckels

Reputation: 18488

When trying to solve similar problems in the past (mainly for solving certain kinds of logical puzzles), I always found it easiest to keep a stack/set of points that you still need to look at, and process them one by one until the stack is empty.

Written in pseudocode, this is pretty easy:

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)

Translated to Matlab (which is not the ideal language for this kind of code):

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

It should be possible to write this code a bit more compact at the cost of clarity. Result:

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

Upvotes: 1

Bentoy13
Bentoy13

Reputation: 4966

Following the idea of @Jigg, I propose another very similar solution.

Locate, for each row and column, the first and the last indexes where there is a 1. Fill the segment between these two indexes with ones 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

(There may be a shorter way to do that thing ...)

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

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

Upvotes: 2

Cape Code
Cape Code

Reputation: 3574

If you have the Image Processing toolbox, one approach would be to create segments that contain all the ones in a given row or column. Here is an example with your matrix:

First, pad the array with a border of zeros:

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

Then perform a morphological closing on this array with horizontal and vertical lines:

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

Get rid of the border pixels, 

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

The results is:

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

You can then extract connected components:

CC = bwconncomp(Segments,4);

And loop along the groups and identify the pixels in A that are contained in each group:

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

The pixels are now grouped in the array Pixels, each cell contains the linear index of the pixels in a given group:

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

Pixels{2}= [10 15]

Graphically:

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

Note the size of the structuring elements se1 and se2 must be optimized to the maximal distance between to isolated pixels. See this other answer by @Bentoy13 for an alternative way of joining the segments.

Upvotes: 2

Related Questions