Is it possible to detect a specefic form of matrices from a big one?

Hello, I need to find those 5 forms of matrices from a binary 'big' matrice

X=[1 0 1 ;
   0 1 0 ;
   1 0 1 ;];
Y=[1 0 1 ;
   0 1 0 ;
   1 0 0 ;];
O=[0 1 0 ;
   1 0 1 ;
   0 1 0 ;];
-=[0 0 0 ;
   1 1 1 ;
   0 0 0 ;];
L=[1 0 0 ;
   1 0 0 ;
   1 1 1 ;];

Any idea? help is much appreciated

[Cedric]

How big is 'big' ?

[mika]

it's 1000*1001

[talha]

how to connect blocks of two different library together ?

Answer 1

[Cedric]

EDITED: got rid of a side effect in the dash case (illustrated in the 4th picture below.. I didn't update it though) by using 2*A-1 instead of A and numel(X) instead of nnz(X).

Someone might provide you with a solution based on the Image Processing Toolbox (which I am not familiar with). Here is one potential solution and a hint in the meantime..

1. Based on CONV2

    A = double( rand(10) > 0.4 ) ;      % Small example.

    X = [1 0 1 ; ...
         0 1 0 ; ...
         1 0 1 ] ;

    ker = rot90(rot90( 2*X -1 )) ;
    [r, c] = find( conv2(2*A-1, ker, 'same') == numel(X) ) ;

With that and a few runs (need a little luck for RAND to output one or more fillings with matches):

 >> A
 A =
     1     1     1     1     1     1     0     1     0     1
     0     0     0     1     1     0     1     1     0     1
     1     0     0     0     0     1     0     1     0     1
     1     0     1     0     1     0     1     1     1     1
     0     1     0     1     0     1     1     1     1     0
     0     1     1     0     1     0     0     1     1     0
     0     1     1     0     1     1     0     0     0     1
     0     1     0     0     1     0     1     1     1     1
     0     1     0     1     1     1     1     0     1     1
     1     1     0     1     0     1     1     1     0     0

 >> [r,c]
 ans =
     5     4
     3     6

which indicates two matches, centered in (5,4) and (3,6). This approach takes ~13ms on my laptop with a 1000x1001 A matrix.

2. By looping over elements of patterns and vectorizing tests on A rather than the opposite.

 .. I leave that for later if CONV2 is not suitable.

--------------------------------------------------------------------------------------------------------------------------------

EDIT: here is a more elaborate example..

 n = 50 ;
 A = double( rand(n, n+1) > 0.5 ) ;
 B = 2*A - 1 ;

 patterns = {[1 0 1; 0 1 0; 1 0 1]; ... % X
             [1 0 1; 0 1 0; 1 0 0]; ... % Y
             [0 1 0; 1 0 1; 0 1 0]; ... % O
             [0 0 0; 1 1 1; 0 0 0]; ... % -
             [1 0 0; 1 0 0; 1 1 1]} ;   % L
 labels   = {'X', 'Y', 'O', '-', 'L'} ;
 matches  = cell( size(labels )) ;

 for pId = 1 : numel( patterns )
     nel    = numel( patterns{pId} ) ;
     ker    = 2*patterns{pId} - 1 ;    
     [r, c] = find( conv2(B, rot90(rot90(ker)), 'same') == nel ) ;
     matches{pId} = [r, c] ;

     figure(pId) ;  clf ;  hold on ;
     spy(A) ;
     plot( c, r, 'r+', 'MarkerSize', 20 ) ;
     title( sprintf( 'Matches for "%s" pattern', labels{pId} )) ;
     set( gcf, 'Units', 'normalized' ) ;
     set( gcf, 'Position', [0 0 0.4 0.7] ) ;
 end

which outputs the following figures..

[mika]

Thank you for your response, i don't understand the code can you explain instructions for me please .After i applied the proposed exemple on my skeletoned image which outputs the following figures for label '-' and 'L' (no matches for 'X','Y' and 'O'):

How to divide that skeleton to a set of regions based on those labels after detecting them.

Any idea? Thank you and best regards,

[mika]

because purpose is to determine all the possible paths to matches extremities of those regions and for every extremity how to determine the paths which verify a configuration of the set of patterns . may this help thank you and best regards, mika.

[Cedric]

Just to be sure, what you want to detect with e.g. the Y pattern, is really a location in the array that corresponds to your picture above where values at the location and its direct neighbors are exactly

   1 0 1
   0 1 0
   1 0 0

and not all possible rotations of this array.. ? Also, are you really looking for 3x3 pixels regions matching these patterns that you provide, or is the goal ultimately to split your skeleton into nodes and vertices using the skeleton to define the topoly (in which case you should look more into the Image Processing Toolbox help, e.g. BWMORPH)?

To understand my solution, you need to understand an operation called "convolution". The simplest illustration that I can provide is that if

 C = conv2(B, rot90(rot90(ker)), 'same') ;

then you have element (2,2) of C, for example, which is numerically equal to

 sum( sum( B(1:3,1:3) .* pattern ))

If B(1:3,1:3) and ker as both defined as (the Y pattern with 0's replaced by -1)

   1 -1  1
  -1  1 -1
   1 -1 -1

their element-wise product is

   1  1  1
   1  1  1
   1  1  1

which sums up to 9. If there is any mismatch between B(1:3,1:3) and ker, it introduces negative values in the element-wise product, which lowers the sum. This is why we look for elements of the convolution which are equal to the number of elements in the pattern (=9). You can try this illustration with A and X for example and see that their 0 entries are introducing false positives (e.g. X patterns are positive when testing for Y); this is why B and ker have to be built by replacing 0's by -1.

[mika]

I'm trying to detect all possible rotations of 'Y' labels for example, but the main goal is to split that skeleton into regions(nodes and arcs) using the skeleton to define the topology in a way that i can determine all the possible paths to matches extremities of those regions and choosing paths which verify a configuration of the set of patterns.

[Cedric]

Ok, this is quite different from what the initial question suggested. I would advise you to re-post the question including images of the skeleton and zooms over regions which represent the different patterns. You should also attach the source array or image so people can perform tests.

[mika]

Hello,

Can you tell me please how to make the output into the same plot. i'm trying to make the result as one plot but in vain can you help me please.

thank you.

Answer 2

[talha]

how to connect blocks of two different library together ?

[Cedric]

Please post a new question and provide more details about your issue.

[mika]

okk sorry for late reply

i' m still looking for the solution

Answer 3

[Image Analyst]

Try normalized cross correlation (see attached demo below in blue text), or the hit or miss transform, done by bwhitmiss() in the Image Processing Toolbox.