Obtain subscript values of common diagonal rectangle in binary matrix?

I am trying to find where in the MM_bin binary matrix (see attached MM_bin.mat file) contains the check_mat matrix (see code below), and then extract the subscript coordinates in the MM_bin matrix of the 1s from the check_mat matrix. So far I am able to use a 2D convolution to extract the centroids of the spots where the check_mat matrix is found in the MM_bin matrix, but I am unsure how to extract the subscript coordinates in the MM_bin matrix for each centroid.

load('MM_bin.mat')
check_mat = [0 0 0 0 0 1 1 1 1;
             0 0 0 0 1 1 1 1 0;
             0 0 0 1 1 1 1 0 0;
             0 0 1 1 1 1 0 0 0;
             0 1 1 1 1 0 0 0 0;
             1 1 1 1 0 0 0 0 0];
minLi = 6; %  length of the 1s diagonal
minLj = 4; % width of the 1s diagonal
[i_cent, j_cent] = find(conv2(MM_bin(:,:,1), check_mat, 'same') == minLi*minLj)

[Bruno Luong]

Don't understand your question:

• "So far I am able to use a 2D convolution to extract the centroids of the spots where the check_mat matrix is found in the MM_bin matrix"

In what form you have the extracted centroid? It must be some sort of coordinates.

• "but I am unsure how to extract the subscript coordinates in the MM_bin matrix for each centroid."

What is the difference between those two notions????

[Andrew Poissant]

Thank you for your comment. I am able to use the 2D convolution to extract the center points in MM_bin that contain the pattern of 1s seen in check_mat. So that is a good start because I can plot the center points on the MM_bin matrix to see where the check_mat pattern is found. All that is left is to plot the other 23 points on the MM_bin matrix that correspond to the other 1s from the check_mat matrix.

End goal is this: find where in the MM_bin matrix the check_mat matrix is found and plot those points (minus the 0s) on the MM_bin matrix.

[Guillaume]

Surely, if you have the centroid, it's trivial to find the corners, so I'm unsure what you're asking.

However, unless I misunderstood completely your convolution code does not work. It finds the pattern of 1 but ignores the pattern of zeros. e.g, if you try it on:

MM_bin = ones(7, 9);
i_cent, j_cent] = find(conv2(MM_bin(:,:,1), check_mat, 'same') == minLi*minLj)

The ouput is

i_cent =
     3
     4
j_cent =
     5
     5

when it should be empty?

You cannot use convolution for your search

[Andrew Poissant]

Hm, maybe I am using it incorrectly. But I want to find the pattern of 1s seen in the check_mat matrix. The 0s are simply placeholders/are there to make the desired diagonal pattern of 1s. I just want to find where the pattern of 1s seen in the check_mat matrix is found in the MM_bin matrix. Maybe I should try to ask the question a different way

[Guillaume]

If you're just looking for the pattern of ones and you don't care if the 0s in your check_mat match a 0 or a 1, then your code is correct and I misunderstood. If the 0s must match a 0, then it cannot work with a convolution.

Assuming your code is correct, I still don't understand what final out you want. Perhaps, provide an example with smaller matrices.

E.G., with

MM_bin = [0 1 0 1 0
          0 1 1 1 1
          1 0 1 1 1]

check_mat = [0 1
             1 0]

what final output do you want?

Answer 1

[Bruno Luong]

% Fake data
MM_bin=rand(100)>0.2;

check_mat = [0 0 0 0 0 1 1 1 1;
             0 0 0 0 1 1 1 1 0;
             0 0 0 1 1 1 1 0 0;
             0 0 1 1 1 1 0 0 0;
             0 1 1 1 1 0 0 0 0;
             1 1 1 1 0 0 0 0 0];

s = size(check_mat);       

% Careful if your pattern is not symmetric you must flip it
% for each  dimension when using with CONV
[i_cent, j_cent] = find(conv2(MM_bin(:,:,1), ...
       fliplr(flipud(check_mat)), 'same') == sum(check_mat(:)));
[ip,jp] = find(check_mat);
i = floor(i_cent(:)-s(1)/2)+ip(:).';
j = floor(j_cent(:)-s(2)/2)+jp(:).';
% remove redundancy
ij = unique([i(:) j(:)],'rows');

% graphical check
close all
imagesc(MM_bin);
hold on
plot(ij(:,2),ij(:,1),'.r') % NOTE: x-axis is second dimension
axis equal

[Andrew Poissant]

Beautiful! This was very helpful thank you! So I was on the right track but needed some tweaks.

Answer 2

[Image Analyst]

To find the centroid of the 1's, if you have the Image Processing Toolbox, you can use regionprops

check_mat = [0 0 0 0 0 1 1 1 1;
    0 0 0 0 1 1 1 1 0;
    0 0 0 1 1 1 1 0 0;
    0 0 1 1 1 1 0 0 0;
    0 1 1 1 1 0 0 0 0;
    1 1 1 1 0 0 0 0 0];
props = regionprops(check_mat, 'Centroid');
xCentroid = props.Centroid(1)
yCentroid = props.Centroid(2)

[Andrew Poissant]

I think my question may not be clear. I do not need to find the centroid of the check_mat matrix. I have the centroid points of where in the larger MM_bin matrix the check_mat matrix is found. I just do not know how to extract the rest of the points to visualize where check_mat is found in the MM_bin matrix.

[Andrew Poissant]

I want to visualize/extract where in the MM_bin matrix the check_mat matrix is found (minus the 0s). Just looking for the subscript points in the MM_bin matrix that match the pattern of the check_mat matrix. I used the 2D convolution as a start to this process.

[Image Analyst]

No, you can't use convolution, in general. Think about it and you'll know why. You'd have to check every single element, which is what isequal does(). You simply use isequal() like I said in my answer below. Basically use a for loop like

for col = 1 : columns
    for row = 1 : rows
        thisWindow = binaryImage(row1:row2, col1:col2)
        if isequal(thisWindow, mask)
             % It's found!

and so on. Let me know if you can't finish it.

[Bruno Luong]

The convolution is perfectly a fine method if he looks for matching the pattern of 1s and doesn't care about the surrounding 0s.

I think that what he wants to achieve.

[Image Analyst]

In addition, you'd have to check for the image to be equal to the exact number of 1's in the mask/kernel/window, i.e. 24.

output = conv2(MM_bin, check_mat, 'same');
foundLocations = MM_bin == sum(check_mat(:));

With isequal(), you don't have to do that. But isequal() searches for exact matches while conv2() searches for a match within the 1 area and ignores any 1's in the 0 region of the mask Bruno said. Depends on what he means by "centroids of the spots where the check_mat matrix is found in the MM_bin matrix". I think he means the entire array of both 0 and 1 are found, not just where the 1's are found. If you had an MM_bin image of all solid 1's then the conv2 would be 24 everywhere and then you'd be finding the centroid everywhere which doesn't make much sense to me.

[Bruno Luong]

Why not? May be the image is the gradient of something or a skeleton, so OP just want to find a contour that matches a pattern that going in some direction. Such image doesn't have 1s in a very big area.

[Matt J]

If he does care about the surrounding zeros, then this FEX submission would be applicable.

[Bruno Luong]

Or simply change the single conv2 check to

conv2(Im,p,'same')==sum(p(:)) & conv2(Im,1-p,'same')==sum(1-p(:))

since they are both binary images.

[Image Analyst]

It's not clear to me what "(minus the 0s)" means. Maybe "ignoring any zeros"??? In other words, as long as that parallelogram is there, it doesn't matter if, outside the parallelogram, it's all ones, all zeros, or some random pattern or ones and zeros.

Answer 3

[Image Analyst]

If you want to find where check_mat occurs in a much larger matrix, simple scan and use isequal().

Answer 4

[Matt J]

[I0,J0]=find(check_mat);

I = I0 + (i_cent.'-3); %I subscripts
J = J0 + (j_cent.'-5); %J subscripts