1

Let me describe my problem with an example. Suppose we have matrix A:

A =

     1     0     1
     1     1     1
     0     1     1

and matrix B:

B =

     1     1
     1     1

How do i write function C = func(A, B) to check if B exists in A or not?
If it exists in A, the function returns C = [0 0 0; 0 1 1; 0 1 1], and if it does not, the function returns C = [0 0 0; 0 0 0; 0 0 0];.

Edit:
It should be mentioned that if A is m-by-n, and B is p-by-q, then m > p and p > q always.

Thanks in advance.

Eitan T
  • 32,660
  • 14
  • 72
  • 109
Ehsan
  • 4,334
  • 7
  • 39
  • 59
  • Have you thought this through?? Consider what would you want returned if A was a 4x4 matrix all containing ones?? This would be the same as A - is this actually going to be useful to you? Maybe it is exactly what you want, just pointing it out in case you have not considered it. – mathematician1975 Jul 06 '12 at 10:26
  • @Ehsan Can you elaborate a little. For example, you have matched pattern B in [A(2,2) A(2,3);A(3,2) A(3,3)]. But why cant it be matched with [A(1,1) A(2,1);A(1,3) A(2,3)]. Is it because the pattern that you are looking for in A must be contiguous? – Abhinav Jul 06 '12 at 10:32
  • @Abhinav yes it should be contiguous, and I'm sure that always there would be one match positions for B in A. – Ehsan Jul 06 '12 at 10:35
  • @Ehsan You mean "atleast one match" or "at the most one match" or "one and only one match with certainity" ? – Abhinav Jul 06 '12 at 10:41
  • one and only one match with certainity – Ehsan Jul 06 '12 at 10:42
  • I imagine some combination of structuring elements with morphological operations on the matrices should get you what you need efficiently. – Ansari Jul 06 '12 at 11:07
  • @Ansari could you please give me an example or at least give me some links? Thanks a lot – Ehsan Jul 06 '12 at 11:08
  • Perhaps later sorry, have to head out now. But do look up the terms I mentioned and try to fit them together to get what you need. – Ansari Jul 06 '12 at 11:17

3 Answers3

4

The most efficient requires the signal processing toolbox. Then you can simply use xcorr2(). Following your example, the following should work:

C = xcorr2 (A, B);
[Row, Col] = find (C == max (C(:)));
%% these are not the coordinates for the center of the best match, you will
%% have to find where those really are
%% The best way to understand this is to strip the "padding"
row_shift = (size (B, 1) - 1)/2;
col_shift = (size (B, 2) - 1)/2;
C = C(1+row_shift:end-row_shift, 1+col_shift:end-col_shift)
[Row, Col] = find (C == max (C(:)));
if (B == A(Row-row_shift:Row+row_shift, Col-col_shift:Col+col_shift))
    disp ("B shows up in A");
endif

The code above looks a bit convoluted because I'm trying to cover inputs of any size (still only odd sized) but should work.

If you don't have this toolbox, I think you can use the Octave code for it which should require only small adjustments. Basically, the only three lines that matter follow (note that the code is under GPL):

[ma,na] = size(a);
[mb,nb] = size(b);
c = conv2 (a, conj (b (mb:-1:1, nb:-1:1)));

In Octave, if you are using at least the signal package 1.2.0, xcorr2 can also take an extra option "coeff" which calculates the normalized cross correlation. This will have a value of 1 when the match is perfect, so you can simplify this with:

C = xcorr2 (A, B, "coeff");
if (any (C(:) == 1)
    display ("B shows up in A");
endif
carandraug
  • 12,938
  • 1
  • 26
  • 38
1

I would do a loop to check resized sub-matrix of A. My code stops after B is found once but it could be updated to count the number of found occurrences.

A = [1 0 1; 1 1 1; 0 1 1; 0 0 0];
B = [1 1; 1 1]; 

[m n] = size(A);
[p q] = size(B);

found = 0;
x = 0;

while ~found && (x+p-1 < m)
    y = 0;
    x = x + 1;
    while ~found && (y+q-1 < n)
        y = y + 1;
        A(x:x+p-1,y:y+q-1)
        found = isequal(A(x:x+p-1,y:y+q-1),B);
    end
end

fprintf('Found Matrix B in A(%d:%d, %d:%d)\n',x,x+p-1,y,y+q-1);
Markus
  • 589
  • 1
  • 6
  • 19
0

Maybe there is some vectored way, but this is a straight forward function which just slides across A and checks for B:

function ret=searchmat(A,B)
    ret=zeros(size(A));
    for k=0:size(A,1)-size(B,1)
        for l=0:size(A,2)-size(B,2)
            if isequal(A(1+k:size(B,1)+k,1+l:size(B,2)+l),B)
                ret(1+k:size(B,1)+k,1+l:size(B,2)+l)=1; % or B as you wish
            end
        end
    end
end

If B is discovered more than once, it's also marked with ones. If you want to quit after the first match, you can just put in a return statement in the if clause.

jpjacobs
  • 9,359
  • 36
  • 45