MATLAB: Matrix (n * n) has only elements 1 and 0. I would like to cluster 1’s if they are connected to each other. Every cluster should have atleast four elements connected. Can any one help me with an algorithm.

cluster dataclusteringgrouping data

Attached file contains the image of a matrix which has elements 1's (Blue dots) and 0's (White dots). As highlighted in the figure, I would like to cluster the elements which are connected. It is a symmetric and 65 * 65 matrix.
Eg: Input [ 1 0 0 0 1 0 1 ; 0 0 1 0 1 0 0 ; 0 0 0 1 0 0 1 ; 1 0 1 0 0 1 0 ; 0 0 0 1 0 0 1 ; 0 0 1 0 0 1 0 ; 0 0 0 0 1 0 0 ]
output : cluster1 = {(1,5), (2,5), (3,4), (4,3), (5,4), (6,3)};
cluster2 = {(3,7), (4,6), (5,7), (6,6), (7,5)};
Note: In the given example, it is not a symmetric matrix, however, the output should be represented as shown.

Best Answer

  • If you have the image processing toolbox this is easily achieved with bwconncomp:
    m = [ 1 0 0 0 1 0 1 ;
    0 0 1 0 1 0 0 ;
    0 0 0 1 0 0 1 ;
    1 0 1 0 0 1 0 ;
    0 0 0 1 0 0 1 ;
    0 0 1 0 0 1 0 ;
    0 0 0 0 1 0 0 ];
    cc = bwconncomp(m, 8);
    clusters = cc.PixelIdxList;
    clusters(cellfun(@(c) numel(c) < 4, clusters)) = [] %remove those with less than 4 elements
    %conversion from linear indices to subscript:
    [crows, ccols] = cellfun(@(c) ind2sub(size(m), c), clusters, 'UniformOutput', false);
    clusters = cellfun(@(r, c) [r c], crows, ccols, 'UniformOutput', false);
    celldisp(clusters)