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:
pattern matching among two matrix

Subject: pattern matching among two matrix

From: PANDIAN` NITHYANANDAM

Date: 24 Nov, 2011 18:48:08

Message: 1 of 6

hai matlab expert

i would like to check a particular pattern of first matrix(2d) available in the second matrix (2d) or not.

is it possible to check like that ; what is the function available for that.
kindly help me regarding this.

Subject: pattern matching among two matrix

From: Roger Stafford

Date: 24 Nov, 2011 20:01:09

Message: 2 of 6

"PANDIAN` NITHYANANDAM" <nithyanandamp@ssn.edulin> wrote in message <jam3h8$sj1$1@newscl01ah.mathworks.com>...
> i would like to check a particular pattern of first matrix(2d) available in the second matrix (2d) or not.
- - - - - - - -
  To my knowledge there is no single function that performs such a test; you have to devise your own. The following is a brute-force (and therefore slow) method of searching for an exact match using the 'all' function. Call A the first matrix and B the (larger) second matrix.

 [m,n] = size(A);
 [p,q] = size(B);
 b = false;
 i1 = 0;
 while i1 <= p-m & ~b
  i1 = i1 + 1;
  i2 = 0;
  while i2 <= q-n & ~b
   i2 = i2 + 1;
   b = all(all(A==B(11:i1+m-1,i2:i2+n-1)));
  end
 end

At exit the logical variable 'b' will be true if an exact match was found, and false otherwise. The indices i1 and i2 at exit will indicate where the first matching position occurred, if any.

Roger Stafford

Subject: pattern matching among two matrix

From: ImageAnalyst

Date: 25 Nov, 2011 04:29:46

Message: 3 of 6

On Nov 24, 3:01 pm, "Roger Stafford"
<ellieandrogerxy...@mindspring.com.invalid> wrote:
> "PANDIAN` NITHYANANDAM" <nithyanand...@ssn.edulin> wrote in message <jam3h8$sj...@newscl01ah.mathworks.com>...
> > i would like to check a particular pattern of first matrix(2d) available in the second matrix (2d) or not.
>
> - - - - - - - -
>   To my knowledge there is no single function that performs such a test; you have to devise your own.
>
> Roger Stafford
------------------------------------------------------------------------

What about the normalized cross correlation, normxcorr2(), in the
Image Processing Toolbox?

normxcorr2

Normalized 2-D cross-correlation
Syntax

C = normxcorr2(template, A)
Description

C = normxcorr2(template, A) computes the normalized cross-correlation
of the matrices template and A. The matrix A must be larger than the
matrix template for the normalization to be meaningful. The values of
template cannot all be the same. The resulting matrix C contains the
correlation coefficients, which can range in value from -1.0 to 1.0.

Can't you just call that and look for 1.0 if you're looking for an
exact match, or somewhat less if you're looking for an approximate
match?
ImageAnalyst

Subject: pattern matching among two matrix

From: Roger Stafford

Date: 25 Nov, 2011 10:35:08

Message: 4 of 6

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <885f3bdc-db64-4b10-935f-bc18baab742e@i6g2000vbe.googlegroups.com>...
> What about the normalized cross correlation, normxcorr2(), in the
> Image Processing Toolbox?
> ........
> Can't you just call that and look for 1.0 if you're looking for an
> exact match, or somewhat less if you're looking for an approximate
> match?
- - - - - - - - - -
  I interpreted Pandian's "pattern ... available" as meaning equality of corresponding elements, which is what my code tested. Having a normalized cross correlation (Pearson coefficient) of unity does not imply such equality. As a counterexample let x = [1;2;6] and y = [3;5;13]. Then the Pearson coefficient between them is:

 ((1-3)*(3-7)+(2-3)*(5-7)+(6-3)*(13-7)) / ...
 sqrt( ((1-3)^2+(2-3)^2+(6-3)^2)*((3-7)^2+(5-7)^2+(13-7)^2) ) =
 (8+2+18)/sqrt((4+1+9)*(16+4+36)) = 28/sqrt(14*56) = 28/28 = 1

The vectors x and y therefore have a correlation of 1 and yet are certainly far from being equal, though they are linearly related: y=2*x+1.

  See for example

 http://en.wikipedia.org/wiki/Correlation_and_dependence

Roger Stafford

Subject: pattern matching among two matrix

From: ImageAnalyst

Date: 25 Nov, 2011 17:21:45

Message: 5 of 6

I interpreted it as doing pattern recognition, like finding a small
matrix that is located within a larger matrix. Like this example
where it generates a big matrix, then gets a template from a certain
place in the big matrix (so we know for a fact that the pattern does
exist), and then finding where it it located:

% Generate the big matrix
bigMatrix = randi(99, [15 15])
% Get a template that's known to exist in the big matrix.
template = bigMatrix(3:5, 7:9)

% Get the normalized cross correlation.
nxc = normxcorr2(template, bigMatrix)

% Crop it to the original size.
nxc = nxc(2:16, 2:16)
% Find the row and columns where it matches.
[row col] = find(nxc >= 0.999)
fprintf('Template found at row=%d, column = %d', row, col);

Subject: pattern matching among two matrix

From: Roger Stafford

Date: 25 Nov, 2011 19:17:08

Message: 6 of 6

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <cb60d1d5-1a81-4185-91b1-ef0fefe5efc6@h42g2000yqd.googlegroups.com>...
> .......
> template = bigMatrix(3:5, 7:9)
> .......
- - - - - - - - - -
  You have given the 'template' equality to a portion of 'bigMatrix' in stating that

 template = bigMatrix(3:5, 7:9)

However the counterexample I mentioned shows that you can get a correlation of 1 at that relative location even where you might only have something like

 template = 10*bigMatrix(3:5, 7:9)-100

holding true there.

  It is a consequence of the Cauchy–Bunyakovsky–Schwarz inequality theorem that equality of the correlation to 1 or -1 is true if and only if the two matrix portions are linearly dependent. They do not have to be equal.

  Of course if the notion of pattern matching is satisfied by merely having linearly related patterns, then searching for a correlation of 1 would be a good method of detecting such a condition. It all hinges on the meaning to be ascribed to a "match" of two patterns.

Roger Stafford

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