Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Finding a small matrix in larger one

Subject: Finding a small matrix in larger one

From: camilla belle

Date: 8 Feb, 2012 15:34:20

Message: 1 of 13

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 ?

Subject: Finding a small matrix in larger one

From: dpb

Date: 8 Feb, 2012 20:07:45

Message: 2 of 13

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
 >>

--

Subject: Finding a small matrix in larger one

From: Roger Stafford

Date: 8 Feb, 2012 20:50:11

Message: 3 of 13

"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

Subject: Finding a small matrix in larger one

From: camilla belle

Date: 8 Feb, 2012 21:02:57

Message: 4 of 13

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
> >>
>
> --
>

Subject: Finding a small matrix in larger one

From: dpb

Date: 8 Feb, 2012 21:24:22

Message: 5 of 13

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.

--

Subject: Finding a small matrix in larger one

From: Bruno Luong

Date: 8 Feb, 2012 21:57:24

Message: 6 of 13

"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

Subject: Finding a small matrix in larger one

From: camilla belle

Date: 10 Feb, 2012 15:22:44

Message: 7 of 13

Thanks for help.

Subject: Finding a small matrix in larger one

From: Matt J

Date: 10 Feb, 2012 16:11:10

Message: 8 of 13

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

Subject: Finding a small matrix in larger one

From: Bruno Luong

Date: 11 Feb, 2012 09:06:30

Message: 9 of 13


>
> [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

Subject: Finding a small matrix in larger one

From: Matt J

Date: 11 Feb, 2012 18:40:28

Message: 10 of 13

"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.

Subject: Finding a small matrix in larger one

From: Matt J

Date: 11 Feb, 2012 18:56:09

Message: 11 of 13

"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);

Subject: Finding a small matrix in larger one

From: Roger Stafford

Date: 11 Feb, 2012 21:02:29

Message: 12 of 13

"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

Subject: Finding a small matrix in larger one

From: Matt J

Date: 11 Feb, 2012 21:14:12

Message: 13 of 13

"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

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us