Thread Subject: Finding a small matrix in larger one

Hi.

Is there any function in matlab that i can use to find a small matrix within
a larger one, for example A is 10 x 10 and B 100 x 100 , find A in B and
return indicies of B where they equals A ?

On 2/8/2012 9:34 AM, camilla belle wrote:
> Hi.
>
> Is there any function in matlab that i can use to find a small matrix within
> a larger one, for example A is 10 x 10 and B 100 x 100 , find A in B and
> return indicies of B where they equals A ?

 >> x=rand(3);
 >> y=x(2:3,2:3);
 >> ismember(x,y)
ans =
      0 0 0
      0 1 1
      0 1 1
 >>

--

"camilla belle" <camilla.belle@poczta.wp.pl> wrote in message <jgu4lt$8f4$1@newsfeed1.man.lodz.pl>...
> Is there any function in matlab that i can use to find a small matrix within
> a larger one, for example A is 10 x 10 and B 100 x 100 , find A in B and
> return indicies of B where they equals A ?
- - - - - - - - -
[mA,nA] = size(A);
[mB,nB] = size(B);
F = zeros((mB-mA+1)*(nB-nA+1),2);
k = 0;
for p = 1:mB-mA+1
 for q = 1:nB-nA+1
  if all(all(A==B(p:p+mA-1,q:q+nA-1)))
   k = k + 1;
   F(k,:) = [p,q];
  end
 end
end
F(k+1:end,:) = [];

Roger Stafford

For unique numbers it will work but for repeated it will show every number
from B that equals one from A.

Uzytkownik "dpb" <none@non.net> napisal w wiadomosci
news:jgukme$e8k$1@speranza.aioe.org...
> On 2/8/2012 9:34 AM, camilla belle wrote:
>> Hi.
>>
>> Is there any function in matlab that i can use to find a small matrix
>> within
>> a larger one, for example A is 10 x 10 and B 100 x 100 , find A in B and
>> return indicies of B where they equals A ?
>
> >> x=rand(3);
> >> y=x(2:3,2:3);
> >> ismember(x,y)
> ans =
> 0 0 0
> 0 1 1
> 0 1 1
> >>
>
> --
>

On 2/8/2012 3:02 PM, camilla belle wrote:
> For unique numbers it will work but for repeated it will show every number
> from B that equals one from A.
...

That's true...

You didn't specify the application.

But, the above was shown to demonstrate one starting point containing
the necessary information--add the logic to the above to test that there
is an area of the size of the smaller within the area that is all TRUE,
essentially by deleting contiguous rows in which all elements are 0 and
see if can end up w/ a sub-array the size of the target which satisfies
all(subarray)==TRUE

The more a priori knowledge you have regarding the location of such a
subarray within the larger, the more you can streamline the process--if,
for example, you knew there can't be row in the middle of the subarray
if it exists that is not part of that array, then you can use any() and
all() w/ the dimension arguments and set the found rows/columns = [] w/o
additional checking, just using the found indices. If, otoh, you could
have a row (say) that is all false in the middle of a pattern and that
eliminating that row would create a false subarray, then you would need
to only eliminate rows/columns that are not inside a potential area,
much like Roger's solution.

--

"camilla belle" <camilla.belle@poczta.wp.pl> wrote in message <jgu4lt$8f4$1@newsfeed1.man.lodz.pl>...
> Hi.
>
> Is there any function in matlab that i can use to find a small matrix within
> a larger one, for example A is 10 x 10 and B 100 x 100 , find A in B and
> return indicies of B where they equals A ?
>

http://www.mathworks.com/matlabcentral/fileexchange/23998-findsubmat/

I still remember the very same question was asked few years ago, and Matt has brilliantly derived a fast algorithm that later becomes the FEX. He later "improved" it in order to handle NaN, but using a random pick of pivot value; I don't like very much this undeterministic character, but it's still a good code.

Perhaps his FEX code still has both engines inside it.

Bruno

Thanks for help.

Here's a simple filtering approach (doesn't handle NaNs though):


>> A,

A =

     9 1 2 2 7
    10 3 10 5 1
     2 6 10 10 9
    10 10 5 8 10
     7 10 9 10 7

>> B,

B =

     8 10
    10 7

>> [I,J]=submatCoords(A,B)

I =

     4 5


J =

     4 5



function [I,J]=submatCoords(A,B)

tolerance=.0001;
[m,n]=size(B);

[I,J]=find(abs(imfilter(A,B)-norm(B(:))^2)<=tolerance);

 I=bsxfun(@plus,I,0:m-1); %I(:,k) are i-coordinates of k-th submatrix
 J=bsxfun(@plus,J,0:n-1); %J(:,k) are j-coordinates of k-th submatrix

>
> [I,J]=find(abs(imfilter(A,B)-norm(B(:))^2)<=tolerance);
>

This is method flawed, not imfilter(A,B)-norm(B(:))^2 == 0 is a necessary condition, not sufficient condition of equaled submatrices.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <jh5b2m$ad3$1@newscl01ah.mathworks.com>...
>
> >
> > [I,J]=find(abs(imfilter(A,B)-norm(B(:))^2)<=tolerance);
> >
>
> This is method flawed, not imfilter(A,B)-norm(B(:))^2 == 0 is a necessary condition, not sufficient condition of equaled submatrices.
==========

I'm not seeing that. Show me the counter-example.

"Matt J" wrote in message <jh6cms$f12$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <jh5b2m$ad3$1@newscl01ah.mathworks.com>...
> >
> > >
> > > [I,J]=find(abs(imfilter(A,B)-norm(B(:))^2)<=tolerance);
> > >
> >
> > This is method flawed, not imfilter(A,B)-norm(B(:))^2 == 0 is a necessary condition, not sufficient condition of equaled submatrices.
> ==========
>
> I'm not seeing that. Show me the counter-example.
===============

Okay, maybe you mean the case where nnz(B)==0. So perhaps the following modification

if ~nnz(B)

 A=A+1;
 B=ones(size(B));

end

 [I,J]=find(abs(imfilter(A,B)-norm(B(:))^2)<=tolerance);

"Matt J" wrote in message <jh6cms$f12$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <jh5b2m$ad3$1@newscl01ah.mathworks.com>...
> > > [I,J]=find(abs(imfilter(A,B)-norm(B(:))^2)<=tolerance);
> > This is method flawed, not imfilter(A,B)-norm(B(:))^2 == 0 is a necessary condition, not sufficient condition of equaled submatrices.
> I'm not seeing that. Show me the counter-example.
- - - - - - -
  I think Bruno is saying this. Suppose you have A = [x,y] and B = [1,1]. Then 'imfilter' yields x*1+y*1 = x+y for one of its elements. It is certainly necessary that x+y be close to 1^2+1^2 = 2 if there is to be a match there but it is not sufficient. There are infinitely many ways of making abs(x+y-2) small without there being any kind of match.

Roger Stafford

"Roger Stafford" wrote in message <jh6l15$948$1@newscl01ah.mathworks.com>...
>
> I think Bruno is saying this. Suppose you have A = [x,y] and B = [1,1]. Then 'imfilter' yields x*1+y*1 = x+y for one of its elements. It is certainly necessary that x+y be close to 1^2+1^2 = 2 if there is to be a match there but it is not sufficient. There are infinitely many ways of making abs(x+y-2) small without there being any kind of match.
===========

OK. Take 3. This time I add a requirement that the blockwise norm of A must equal that of B. Necessity and sufficiency should then follow from Cauchy-Schwartz:


function [I,J]=submatCoords(A,B)

tolerance=.0001;
[m,n]=size(B);

Aenergy=imfilter(A.^2,ones(size(B)));
Benergy=norm(B(:))^2;

EqualEnergy=abs(Aenergy-Benergy)<=tolerance*Benergy;

%from Cauchy-Schwartz
[I,J]=find( (imfilter(A,B)>=Benergy-tolerance) & EqualEnergy );

 I=bsxfun(@plus,I,0:m-1); %I(:,k) are i-coordinates of k-th submatrix
 J=bsxfun(@plus,J,0:n-1); %J(:,k) are j-coordinates of k-th submatrix