Basic pattern recognition in binary (pixelated) image

If you have too many operations, think how to do less of them.

For this problem I'd use image integrals.

If you convolve a summing kernel over the image (this is a very fast operation in fft domain with just conv2,imfilter), you know that only locations where the integral is equal to 5 (in your case) are possible pattern matching places. Checking those (even for your 4 rotations) should be computationally very fast. There can not be more than 50 locations in your example image that fit this pattern.

My python is not too fluent, but this is the proof of concept for your first image in MATLAB, I am sure that translating this code should not be a problem.

% get the same image you have (imgur upscaled it and made it RGB)
I=rgb2gray(imread('https://i.stack.imgur.com/l3u4A.png'));
I=imresize(I,[9 11]);
I=double(I>50);

% Integral filter definition (with your desired size)
h=ones(3,4);

% horizontal and vertical filter (because your filter is  not square)
Ifiltv=imfilter(I,h);
Ifilth=imfilter(I,h');
% find the locations where integral is exactly the value you want
[xh,yh]=find(Ifilth==5);
[xv,yv]=find(Ifiltv==5);

% this is just plotting, for completeness
figure()
imshow(I,[]);
hold on
plot(yh,xh,'r.');
plot(yv,xv,'r.');

This results in 14 locations to check. My standard computer takes 230ns on average on computing both image integrals, which I would call fast.

Also GPU computing is not a hack :D. Its the way to go with a big bunch of problems because of the enormous computing power they have. E.g. convolutions in GPUs are incredibly fast.

The operation you are implementing is an operator in Mathematical Morphology called hit and miss.

It can be implemented very efficiently as a composition of two erosions. If the shape you’re detecting can be decomposed into a few simple geometrical shapes (especially rectangles are quick to compute) then the operator can be even more efficient.

You’ll find very efficient erosions in most image processing libraries, for example try OpenCV. OpenCV also has a hit and miss operator, here is a tutorial for how to use it.

---

As an example for what output to expect, I generated a simple test image (left), applied a hit and miss operator with a template that matches at exactly one place in the image (middle), and again with a template that does not match anywhere (right):

I did this in MATLAB, not Python, because I have it open and it's easiest for me to use. This is the code:

se = [1,1,1,1      % Defines the template
      0,0,0,1];
img = [0,0,0,0,0,0 % Defines the test image
       0,1,1,1,1,0
       0,0,0,0,1,0
       0,0,0,0,0,0
       0,0,0,0,0,0
       0,0,0,0,0,0];
img = dip_image(img,'bin');

res1 = hitmiss(img,se);
res2 = hitmiss(img,rot90(se,2));

% Quick-and-dirty display
h = dipshow([img,res1,res2]);
diptruesize(h,'tight',3000)
hold on
plot([5.5,5.5],[-0.5,5.5],'r-')
plot([11.5,11.5],[-0.5,5.5],'r-')

The code above uses the hit and miss operator as I implemented in DIPimage. This same implementation is available in Python in PyDIP as HitAndMiss (there is not yet a binary release of PyDIP, you need to compile it yourself):

import PyDIP as dip
# ...
res = dip.HitAndMiss(img, se)