二进制(像素化)图像中的基本模式识别

Question

下面是这种图像的裁剪示例(关于11x9像素)(最终实际上是所有大小28x28,但存储在内存中作为组件784阵列展平)我将尝试应用该算法:

基本上,我希望能够识别何时出现这种形状(红线用于强调像素的分离,而周围的黑色边框用于更好地勾勒出StackOverflow白色背景下的图像):

它的方向无关紧要:它必须沿水平和垂直轴的任何可能的表示(旋转和对称)检测(因此,例如,不应考虑45°旋转,也不应考虑对角线对称:例如,仅考虑90°,180°和270°旋转.

在我第一次呈现的图像上有两种解决方案,但只需要找到一种(忽略白色区域周围的灰色模糊):

拿这个样本(这也表明图像中的白色图形并不总是被黑色像素完全包围):

该函数应返回True,因为存在形状:

现在,显然有一个简单的解决方案:

使用变量,例如pattern = [[1,0,0,0],[1,1,1,1]],生成其变体,然后沿着图像滑动所有变体,直到找到完全匹配,此时整个事物就停止并返回True.

然而,在最坏的情况下,对于单个图像来说,8*(28-2)*(28-4)*(2*4)大约需要40000次操作,这看起来有点矫枉过正(如果我做了我的快速计算).

我猜测使这种天真的方法变得更好的一种方法是首先扫描图像,直到我找到第一个白色像素,然后开始寻找比该点早4行和4列的模式,但即便如此似乎不够好.

有任何想法吗？也许这种功能已经在某些库中实现了？我正在寻找一种能够击败我天真的方法的实现或算法.

作为旁注,虽然是一种黑客,但我猜这是可以卸载到GPU的那种问题,但我没有太多经验.虽然它不是我正在寻找的主要内容,但如果您提供答案,请随意添加与GPU相关的注释.

Answer 1

如果您有太多的操作,请考虑如何减少它们.

对于这个问题,我会使用图像积分.

如果你在图像上对求和内核进行卷积(这是fft域中的一个非常快的操作,只有conv2,imfilter),你知道只有积分等于5的位置(在你的情况下)才是可能的模式匹配位置.检查那些(即使你的4次旋转)应该在计算上非常快.示例图像中的位置不能超过50个适合此模式的位置.

我的python不太流畅,但这是你在MATLAB中第一个图像的概念证明,我确信翻译这段代码应该不是问题.

% 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.');

这导致14个位置进行检查.我的标准计算机在计算两个图像积分时平均需要230ns,我会称之为快速.

GPU计算也不是黑客攻击:D.由于它们拥有巨大的计算能力,它可以解决大量问题.例如,GPU中的卷积非常快.

Answer 2

您正在实现的操作是数学形态学中的一个运算符，称为hit 和 miss。

\n

它可以非常有效地实现为两个侵蚀的组合。如果您检测到的形状可以分解为一些简单的几何形状（特别是矩形可以快速计算），那么运算符可以更加高效。

\n

你\xe2\x80\x99会在大多数图像处理库中发现非常有效的侵蚀，例如尝试OpenCV。OpenCV 还有一个 hit and miss 运算符，这里有一个如何使用它的教程。

\n\n

作为预期输出的示例，我生成了一个简单的测试图像（左），应用了命中和未命中运算符，其中模板与图像中的一个位置完全匹配（中），并再次使用不匹配的模板任何地方（右）：

\n

\n

我在 MATLAB 中完成此操作，而不是 Python，因为我已打开它并且它对我来说最容易使用。这是代码：

\n

se = [1,1,1,1      % Defines the template\n      0,0,0,1];\nimg = [0,0,0,0,0,0 % Defines the test image\n       0,1,1,1,1,0\n       0,0,0,0,1,0\n       0,0,0,0,0,0\n       0,0,0,0,0,0\n       0,0,0,0,0,0];\nimg = dip_image(img,\'bin\');\n\nres1 = hitmiss(img,se);\nres2 = hitmiss(img,rot90(se,2));\n\n% Quick-and-dirty display\nh = dipshow([img,res1,res2]);\ndiptruesize(h,\'tight\',3000)\nhold on\nplot([5.5,5.5],[-0.5,5.5],\'r-\')\nplot([11.5,11.5],[-0.5,5.5],\'r-\')\n

\n

上面的代码使用了我在DIPimage中实现的命中和未命中运算符。DIPlib的 Python 绑定中也提供了相同的实现dip.HitAndMiss()（使用 进行安装pip install diplib）：

\n

import diplib as dip\n# ...\nres = dip.HitAndMiss(img, se)\n

\n