How to look up a smaller array in a larger array while preserving shape

I have a logical array. I want to look for a 2x2 "square" of 1's in this array, and return whether this square is present in this array or not.

LargeArray= [0,0,0,0;1,0,0,0;1,0,0,0;1,1,0,0;1,1,0,0;1,1,0,0;0,0,0,0;0,0,0,0]

LargeArray = 8×4

0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0

FindArray= [1,1;1,1]

FindArray = 2×2

1 1 1 1

When I use ismember, I get the Large array as the answer, but I am looking to get the answer of whether the smaller FindArray is present in the LargeArray or not in True or False so I can use it to tag my data. Thanks!

Answer 1

[Image Analyst]

A simple brute force for loop will do it:

LargeArray= [0,0,0,0;1,0,0,0;1,0,0,0;1,1,0,0;1,1,0,0;1,1,0,0;0,0,0,0;0,0,0,0]

LargeArray = 8×4

0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0

FindArray= [1,1;1,1]

FindArray = 2×2

1 1 1 1

[rL, cL] = size(LargeArray);
[rt, ct] = size(FindArray);
foundIt = false;
for col = 1 : cL-ct
    for row = 1 : rL-rt
        subArray = LargeArray(row:row+rt-1, col:col+ct-1);
        if isequal(subArray, FindArray)
            foundIt = true;
            fprintf('Found it at row %d, column %d.\n', row, col);
        end
    end
end

Found it at row 4, column 1.
Found it at row 5, column 1.

[Can Ozger]

This works great, thank you very much!

[Bruno Luong]

The code is buggy, I did not find if the block is on the extrem right or bottom side

LargeArray= fliplr([0,0,0,0;1,0,0,0;1,0,0,0;1,1,0,0;1,1,0,0;1,1,0,0;0,0,0,0;0,0,0,0])

LargeArray = 8×4

0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0

FindArray= [1,1;1,1]

FindArray = 2×2

1 1 1 1

[rL, cL] = size(LargeArray);
[rt, ct] = size(FindArray);
foundIt = false;
for col = 1 : cL-ct % missing +1
    for row = 1 : rL-rt % missing +1
        subArray = LargeArray(row:row+rt-1, col:col+ct-1);
        if isequal(subArray, FindArray)
            foundIt = true;
            % it never goes here, but it should
            fprintf('Found it at row %d, column %d.\n', row, col);
        end
    end
end

[Image Analyst]

Thanks for catching that Bruno. 🙂 Yes it works when the +1 is added on.

LargeArray= fliplr([0,0,0,0;1,0,0,0;1,0,0,0;1,1,0,0;1,1,0,0;1,1,0,0;0,0,0,0;0,0,0,0])

LargeArray = 8×4

0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0

FindArray= [1,1;1,1]

FindArray = 2×2

1 1 1 1

[rL, cL] = size(LargeArray);
[rt, ct] = size(FindArray);
foundIt = false;
for col = 1 : cL-ct+1
    %fprintf('Checking column %d\n', col)
    for row = 1 : rL-rt+1
        %fprintf('Checking row %d\n', row)
        subArray = LargeArray(row:row+rt-1, col:col+ct-1);
        if isequal(subArray, FindArray)
            foundIt = true;
            fprintf('Found it at row %d, column %d.\n', row, col);
        end
    end
end

Found it at row 4, column 3.
Found it at row 5, column 3.

Also these example arrays were very small. If the image array and template are much larger (like thousands of lines), then conv2 (Like Bruno suggested) would probably be faster and more efficient where you'd notice a difference. Even with the small arrays, conv2 is faster if you take out anything being echoed to the display, though only by a tenth of a millisecond or so. However since there are many ways to get a convolution value (since it's the sum of products and many combinations could give the same sum), conv2 doesn't work in general, but scanning with isequal will still work.

fprintf('Now using arbitrary array values.\n');

Now using arbitrary array values.

LargeArray= randi(9, 8, 4)

LargeArray = 8×4

9 5 6 7 3 6 6 1 9 3 4 9 9 3 7 9 1 6 3 5 4 8 5 5 7 5 5 1 8 9 3 7

FindArray= LargeArray(2:3, 2:3)

FindArray = 2×2

6 6 3 4

[rL, cL] = size(LargeArray);
[rt, ct] = size(FindArray);
foundIt = false;
for col = 1 : cL-ct+1
    % 	fprintf('Checking column %d\n', col)
    for row = 1 : rL-rt+1
        % 		fprintf('Checking row %d\n', row)
        subArray = LargeArray(row:row+rt-1, col:col+ct-1);
        if isequal(subArray, FindArray)
            foundIt = true;
            fprintf('Found it at row %d, column %d.\n', row, col);
        end
    end
end

Found it at row 2, column 2.

shiftfun = @(B) 2*B-1; % transform 0/1 respectively to -1/1
c = conv2(shiftfun(LargeArray),rot90(shiftfun(FindArray),2),'valid');
% Match (upper-left) indexes in LargeArray
[row,col] = find(c==numel(FindArray));
MatchIndex = table(row,col)

MatchIndex =

  0×2 empty table

Perhaps normalized cross correlation, normxcorr2, might work but I haven't tried it out yet.

[Bruno Luong]

@Image Analyst Sorry but my code is originally designed for binary data, as OP has specified. You shouldn't apply it for generic array without knowing what exactly conv2 does.

For generic array this modified code find index (but I can give also false positive, bu I'm not explain how to fix it because it's off topic

LargeArray= randi(9, 8, 4)

LargeArray = 8×4

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

FindArray= LargeArray(2:3, 2:3)

FindArray = 2×2

6 6 3 5

c = conv2(LargeArray,rot90(FindArray,2),'valid');
% Match (upper-left) indexes in LargeArray
[row,col] = find(c==sum(FindArray.^2,'all'));
MatchIndex = table(row,col)

MatchIndex = 1×2 table
    row    col
    ___    ___

     2      2 

[Image Analyst]

OK, I just thought that when you said, in the comment to your original post, "On case the pattern array contains only 1s," and gave simplified code, that the original post would handle any numbers. But anyway, thanks for giving generalized solution that works for any numbers. 🙂

Answer 2

[Bruno Luong]

Use convolution to detect matching

% I modified it to make example more interesting
LargeArray= [0,0,0,0;1,0,0,0;1,0,0,0;1,1,0,0;1,1,1,0;0,1,1,0;0,0,0,0;0,0,0,0]

LargeArray = 8×4

0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0

FindArray= [1,1;1,1]

FindArray = 2×2

1 1 1 1

shiftfun = @(B) 2*B-1; % transform 0/1 respectively to -1/1
c = conv2(shiftfun(LargeArray),rot90(shiftfun(FindArray),2),'valid');
% Match (upper-left) indexes in LargeArray
[row,col] = find(c==numel(FindArray));

MatchIndex = table(row,col)

MatchIndex = 2×2 table
    row    col
    ___    ___

     4      1 
     5      2 

[Bruno Luong]

On case the pattern array contains only 1s, the code can be simplified in single-line

% I modified it to make example more interesting
LargeArray= [0,0,0,0;1,0,0,0;1,0,0,0;1,1,0,0;1,1,1,0;0,1,1,0;0,0,0,0;0,0,0,0]

LargeArray = 8×4

0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0

FindArray= ones(2,2)

FindArray = 2×2

1 1 1 1

% Match (upper-left) indexes in LargeArray
[row,col] = find(conv2(LargeArray,FindArray,'valid')==numel(FindArray));

MatchIndex = table(row,col) 

MatchIndex = 2×2 table
    row    col
    ___    ___

     4      1 
     5      2 

Answer 3

[DGM]

I'm going to demonstrate a couple ways you can do this using neighborhood operations. The case of a solid 2x2 nhood is a bit of a simplified case, but these can be extended to more general binary pattern matching. For these examples, I'm going to shamelessly steal Bruno's improved test array.

If you have IPT, you can use bwlookup().

LargeArray = [0,0,0,0; 1,0,0,0; 1,0,0,0; 1,1,0,0; 1,1,1,0; 0,1,1,0; 0,0,0,0; 0,0,0,0];
nhood = [1 1; 1 1]; % any 2x2 neighborhood

f = @(x) isequal(x,nhood); % function that describes matching behavior
lut = makelut(f,2); % create LUT for a 2x2 nhood
mk = bwlookup(LargeArray,lut) % logical map of matches

mk = 8×4

0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[r c] = find(mk) % convert logical mask to row,col subscripts

r = 2×1

4 5

c = 2×1

1 2

Alternatively, you can use basic linear filters.

LargeArray = [0,0,0,0; 1,0,0,0; 1,0,0,0; 1,1,0,0; 1,1,1,0; 0,1,1,0; 0,0,0,0; 0,0,0,0];
nhood = [1 1; 1 1]; % any 2x2 neighborhood pattern

seb = 2.^([1 3; 2 4]-1); % index weighting array
mk = imfilter(double(LargeArray),seb) == sum(sum(seb.*nhood)) % logical map of matches

mk = 8×4 logical array
   0   0   0   0
   0   0   0   0
   0   0   0   0
   1   0   0   0
   0   1   0   0
   0   0   0   0
   0   0   0   0
   0   0   0   0

[r c] = find(mk) % convert logical mask to row,col subscripts

r = 2×1

4 5

c = 2×1

1 2