# Pattern search in matrix

39 views (last 30 days)
Chris E. on 1 Aug 2014
Commented: Image Analyst on 1 Aug 2014
Hello Everyone, I'm just trying to figure out how to search for repeated patterns in a matrix and am unsure how to really do it. I have tried many different methods with no success. I had been able to find the patterns in rows, but not in entire matrices.
Also any help on the clean up of code would be great too!
Here is some examples that may help you understand what I need:
%
% What I have to begin with:
%
%
% k = [1 5 9;
% 4 5 6;
% 1 5 2;
% 9 7 6;
% 4 1 5;
% 3 4 7]
%
% What I want in the end, the patterns unchanged and the rest set to 0:
%
% k = [1 5 0;
% 4 0 0;
% 1 5 0;
% 4 0 0;
% 0 1 5;
% 0 4 0]
%
% What I have to begin with:
%
% n = [1 2 3 6 5;
% 5 8 9 6 2;
% 9 6 2 4 1;
% 6 7 1 2 3;
% 9 5 1 8 2;
% 1 8 4 3 2]
%
% What I would like to get:
%
% n = [1 2 3 0 0;
% 0 8 0 0 0;
% 0 0 0 0 0;
% 0 0 1 2 3;
% 0 0 0 8 0;
% 0 0 0 0 0]
%
% What I have to begin with:
%
p = [1 2 5 8 4 2 1 2 5 6;
8 5 7 2 6 2 4 1 2 5;
9 4 2 6 7 5 3 1 5 1;
8 4 5 6 9 1 4 2 5 6;
5 6 2 5 5 7 8 9 5 6;
5 1 2 2 4 2 6 7 4 8;
9 5 1 4 1 5 6 3 1 2;
6 9 8 7 4 5 8 7 4 1;
6 5 7 4 2 1 5 7 7 1;
8 4 2 6 6 1 4 2 6 1;
3 6 5 9 7 4 1 5 3 2]
%
% What I would like to get:
%
% p = [0 0 0 0 0 0 0 0 0 0;
% 0 5 7 0 0 0 0 0 0 0;
% 0 4 2 6 0 0 0 0 0 0;
% 0 0 5 0 0 0 0 0 0 0;
% 0 0 0 0 5 7 0 0 0 0;
% 0 0 0 0 4 2 6 0 0 0;
% 0 0 0 0 0 5 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0;
% 0 5 7 0 0 0 5 7 0 0;
% 0 4 2 6 0 0 4 2 6 0;
% 0 0 5 0 0 0 0 5 0 0]
%Using this code I can find the row patterns, but it only isolates what in a row.
%the searchsize will show row patterns of that size, this example, 3
searchsize = 3;
s = unique(p(:));
z = [];
%this first for loop searches and make matrix z of unique row snips
for j = 1:size(p,1)
for k = 1:(size(p,2)-(searchsize-1))
use = p(j,((k):((searchsize-1)+k)));
z = [use; z];
end
end
zz = unique(z,'rows');
out = [];
%This for loop counts the unique snips made in the first for loop
for m = 1:size(zz,1)
count = sum(ismember(z,zz(m,:),'rows'));
out(m,:) = [zz(m,:) count];
end
sortedout = sortrows(out,-(searchsize+1));
l = sum(sortedout(:,(searchsize+1))>3);
lookfor = sortedout((1:l)',:);
%This for loop makes an new matrix putting 0 in the unwanted areas...
b = 1;
for j = 1:size(p,1)
for k = 1:(size(p,2)-(searchsize-1))
use = p(j,((k):((searchsize-1)+k)));
if ismember(use,lookfor(:,1:searchsize),'rows')
new(b,:) = {use j ((k):((searchsize-1)+k))};
b = b + 1;
end
end
end
val = 1:searchsize;
[R C] = size(p);
newp = zeros(R,C);
for j = 1:(b-1)
nums = new{j,1};
row = new{j,2};
cols = new{j,3};
s = 1;
for col = cols
newp(row,col) = nums(val(s));
s = s + 1;
end
end
newp
% What I get so far for p:
%
% newp = [0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0;
% 0 4 2 6 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 4 2 6 0 0 0;
% 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0;
% 0 4 2 6 0 0 4 2 6 0;
% 0 0 0 0 0 0 0 0 0 0]
##### 2 CommentsShowHide 1 older comment
Chris E. on 1 Aug 2014
Well that is the thing, I'm not trying to search for only row patterns, I'm trying to find 2d patterns in matrices. The pattern is [1 5; 4 :] where ":" is a value that does not repeat in the pattern so I do not care about it.
The pattern is:
1 5
4
Not
1 5 and 4
% k = [1 5 9;
% 4 5 6;
% 1 5 2;
% 9 7 6;
% 4 1 5;
% 3 4 7]
%
% What I want in the end, the patterns unchanged and the rest set to 0:
%
% k = [1 5 0;
% 4 0 0;
% 1 5 0;
% 4 0 0;
% 0 1 5;
% 0 4 0]

Image Analyst on 1 Aug 2014
Looking for patterns is what normalized cross correlation is meant for. There's even a function for it built in to the Image Processing Toolbox. If you have that toolbox, then you can use the demo I've attached below the image.
Image Analyst on 1 Aug 2014
Just be careful with indexes though because, as you probably know with any convolution or correlation, as you slide the window completely along the input, the output will be as large as the input plus the window width, because even though the center of the window is off the array, some distant part of the window is still overlapped with the input array, so the output is larger. You can do it, just be careful with indexes so you know what is where.