我们从事从Adwords(Google的广告平台)购买流量的活动。 该领域的常规任务之一是创建新横幅。 测试表明,随着用户习惯横幅广告,横幅广告会随着时间的流逝而失去有效性。 季节和趋势在变化。 此外,我们的目标是吸引不同的受众群体,而目标明确的横幅广告效果更好。
与进入新国家有关,出现了横幅广告本地化的问题。 对于每个横幅,您需要使用不同的语言和币种创建版本。 您可以要求设计人员执行此操作,但是此手动工作将给已经稀缺的资源增加额外的负担。
它看起来像一个易于自动化的任务。 为此,只需创建一个程序即可在横幅空白上为“价格标签”加上本地化价格,然后在按钮上进行号召性用语(例如“立即购买”)。 如果在图片中打印文本很简单,那么确定放置位置并不总是一件容易的事。 Peppercorns补充说,按钮有不同的颜色,并且形状略有不同。
本文致力于:如何在图片中查找指定的对象? 流行的方法将被整理; 应用领域,功能,优缺点。 上面的方法可以用于其他目的:开发用于安全摄像机的程序,自动化测试UI等。 所描述的困难可以在其他任务中找到,并且所使用的方法可以用于其他目的。 例如,Canny边缘检测器通常用于预处理图像,而关键点的数量可用于评估图像的视觉“复杂性”。
我希望所描述的解决方案能够补充您解决问题的工具和窍门。

代码在Python 3.6中( 存储库 ); 需要OpenCV库。 希望读者了解线性代数和计算机视觉的基础知识。
我们将专注于查找按钮本身。 我们会记得找到价格标签(因为找到矩形也可以用更简单的方法解决),但是请不要这样做,因为解决方案的外观相同。
模板匹配
想到的第一个想法是,为什么不只是在图片中选择并找到在像素色差方面与按钮最相似的区域? 这就是模板匹配的原因-一种基于在图像上找到与模板最相似的空间的方法。 图像的“相似性”由特定指标定义。 即,模板被“叠加”在图像上,并且考虑了图像和模板之间的差异。 差异最小的模板位置,它将指示所需对象的位置。
您可以使用不同的选项作为度量标准,例如,模板和图片之间的平方差之和(平方差之和,SSD),或使用互相关(CCORR)。 令f和g分别为尺寸为(k,l)和(m,n)的图像和图案(我们现在将忽略颜色通道); i,j-我们“附加”模板的图像上的位置。
S S D i , j = s u m a = 0 .. m , b = 0 .. n (f i + a , j + b - g a , b ) 2
CCORRi,j= suma=0..m,b=0..n(fi+a,j+b cdotga,b)2
让我们尝试应用方差来寻找小猫

在图片中

(图片来自PETA照料猫)。
左侧图片是图片中位置与模板相似度的度量值(即,不同i,j的SSD值)。 暗区是差异最小的地方。 这是指向最类似于模板的位置的指针-在右图中此位置被圈出。


互相关实际上是两个图像的卷积。 使用快速傅里叶变换可以快速实现卷积。 根据卷积定理,在傅立叶变换之后,卷积变成简单的元素乘法:
CCORRi,j=f circledastg=IFFT(FFT(f circledastg))=IFFT(FFT(f) cdotFFT(g))
哪里 Circledast -卷积运算符。 这样,我们可以快速计算互相关。 正面实现时,这给出了O(kllog(kl)+ mnlog(mn))相对于O(klmn)的总体复杂度。 差异的平方也可以使用卷积来实现,因为打开括号后,它将变成图像像素值的平方和与互相关之间的差:
SSDi,j= suma=0..m,b=0..n(fi+a,j+b−ga,b)2=
= suma=0..m,b=0..nf2i+a,j+b−2fi+a,j+bga,b+g2a,b=
= suma=0..m,b=0..nf2i+a,j+b+g2a,b−2CCORi,j
详细信息可以在此演示文稿中看到。
让我们继续执行。 幸运的是,下诺夫哥罗德英特尔部门的同事们通过创建OpenCV库来照顾我们,它已经使用matchTemplate方法实现了模板搜索(顺便说一句,它使用FFT实现,尽管在文档中没有提到),并且使用了不同的差异指标 :
- CV_TM_SQDIFF-像素值差异的平方和
- CV_TM_SQDIFF_NORMED-色差平方的总和,标准化到范围0.1.1。
- CV_TM_CCORR-模板和图像段的逐元素乘积之和
- CV_TM_CCORR_NORMED-元素的总和,规格化为-1..1。
- CV_TM_CCOEFF-没有平均值的图像互相关
- CV_TM_CCOEFF_NORMED-没有平均值的图像之间的互相关,归一化为-1..1(皮尔森相关)
我们将使用它们来寻找小猫:

可以看出,只有TM_CCORR无法应付其任务。 这是可以理解的:由于它是标量产品,因此该指标的最大价值将是在将模板与白色矩形进行比较时。
您可能会注意到,这些指标要求在所需图像中逐像素匹配图案。 伽玛,亮度或大小的任何偏差都会导致方法无法正常工作。 让我提醒您,这正是我们的情况:按钮可以具有不同的大小和颜色。
可以通过应用边缘检测滤镜来解决不同颜色和光线的问题。 此方法仅保留有关图像中明显颜色变化的信息。 让我们将Canny Edge Detector(我们将对其进行进一步分析)应用于不同颜色和亮度的按钮。 左侧是原始横幅,右侧是应用Canny过滤器的结果。

在我们的情况下,还存在大小不同的问题,但是已经解决了。 对数极坐标变换将图片变换为一个空间,在该空间中缩放和旋转将显示为偏移量。 使用此变换,我们可以恢复比例和角度。 之后,通过缩放和旋转模板,您可以找到模板在原始图像中的位置。 您还可以在整个过程中使用FFT,如基于FFT的平移,旋转和比例不变图像配准技术中所述 。 在文献中,考虑了水平和垂直模式按比例更改而比例因子在较小限制(2.0 ... 0.8)范围内变化的情况。 不幸的是,调整按钮的大小可能很大且不成比例,这可能导致错误的结果。
我们应用生成的构造(Canny滤波器,通过对数极坐标变换仅还原比例,通过找到具有最小二次差异的位置来获得位置),以在三张图片中找到按钮。 我们将使用黄色的大按钮作为模板:

同时,横幅上的按钮将具有不同的类型,颜色和大小:

在调整按钮大小的情况下,该方法无法正常工作。 这是由于该方法涉及在水平和垂直方向上按相同的次数调整按钮的大小。 但是,并非总是如此。 在右图中,按钮的大小在垂直方向上没有改变,但在水平方向上却大大减小了。 如果调整大小太大,则由对数极坐标转换引起的失真会使搜索不稳定。 在这方面,在第三种情况下该方法不能检测到按钮。
关键点检测
您可以尝试另一种方法:代替寻找整个按钮,让我们找到它的典型部分,例如,按钮的角或边框元素(沿着按钮轮廓的装饰笔触)。 看起来拐角和边界似乎更容易,因为它们是小的(因此很简单)的对象。 位于四个角和边框之间的将是一个按钮。 查找关键点的方法类别称为“关键点检测”,而使用关键点进行比较和搜索图像的算法称为“关键点匹配”。 在图片中搜索图案减少到应用用于检测图案和图片的关键点并且比较图案和图片的关键点的算法。
通常,“关键点”是通过查找周围环境具有某些属性的像素自动找到的。 发明了许多找到它们的方法和标准。 所有这些算法都是启发式算法,通常会发现一些特征图像元素-角度或急剧的颜色变化。 好的检测器应能快速工作,并能抵抗图像变换(更改图像时,关键点不应停止/移动)。
哈里斯角落探测器
最基本的算法之一是Harris角点检测器 。 对于图片(以下我们认为我们正在使用“强度”(即转换为灰度的图像)进行操作),他尝试查找强度差大于某个阈值的附近点。 该算法如下所示:
从强度 我 是沿x和y轴的导数( Ix 和 Iy 分别)。 例如,可以通过应用Sobel过滤器找到它们。
对于像素,请考虑正方形 Ix 方 Iy 和作品 Ix 和 Iy 。 一些来源将其标记为 Ixx , Ixy 和 Ixy -不会增加清晰度,因为可能会认为它们是强度的二阶导数(事实并非如此)。
对于每个像素,我们考虑具有以下特征的某个邻域(大于1个像素)的总和:
A= sumx,yw(x,y)IxIx
B= sumx,yw(x,y)IxIy
C= sumx,yw(x,y)IyIy
与模板检测中一样,可以使用卷积定理有效地执行针对大窗口的此过程。
对于每个像素,计算值 \星 启发式
R=Det(H)−k(Tr(H))2=(AB−C2)−k(A+B)2
价值 k 在[0.04,0.06]范围内根据经验选择 R 一些像素有一定的阈值,然后邻域 w 该像素包含一个角度,我们将其标记为关键点。
先前的公式可以创建彼此相邻的关键点群集,在这种情况下,有必要删除它们。 可以通过检查每个点是否具有值来完成 R 在直接邻居中最大。 如果不是,则将关键点过滤掉。 此过程称为非最大抑制 。
\星 配方 R 选择它是有原因的。 A,B,C -结构张量的分量-描述邻域中梯度行为的矩阵:
H=\开始pmatrixA和CC&B\结束pmatrix
该矩阵在许多方面与其协方差矩阵相似。 例如,它们都是正半定矩阵,但是相似性不限于此。 让我提醒您,协方差矩阵具有几何解释。 协方差矩阵的特征向量指示源数据最大方差的方向(在其上计算了协方差),特征值指示沿轴的散布:

图片取自http://www.visiondummy.com/2014/04/geometric-interpretation-covariance-matrix/
结构张量的特征值也以相同的方式表现:它们描述了梯度的扩散。 在平坦的表面上,结构张量的特征值将很小(因为梯度本身的分布会很小)。 建立在一张带有脸的图片上的结构张量的特征值将有很大的变化:一个数字将很大(并且对应于其自身垂直于该脸的向量),第二个数字很小。 在角度张量上,两个特征值都将很大。 基于此,我们可以建立一个启发式( lambda1, lambda2 是结构张量的特征值)。
R= lambda1 lambda2−k( lambda1+ lambda2)2
当两个特征值都较大时,此启发式方法的值将较大。
特征值之和是矩阵的迹线,可以将其计算为对角线上的元素之和(如果您看一下公式A和B,很明显这也是该区域中梯度长度的平方之和):
lambda1+ lambda2=Tr(H)=A+B
特征值的乘积是矩阵的行列式,在2x2的情况下也很容易写成:
lambda1 lambda2=Det(H)=AB−C2
因此,我们可以有效地计算 R ,用结构张量的分量表示。
快的
哈里斯的方法很好,但是有很多替代方法。 我们不会以与上述方法相同的方式来考虑所有内容,我们只会提及一些流行的技巧,以展示有趣的技巧并将其进行实际比较。

通过FAST算法验证的像素
哈里斯方法的替代方法是FAST 。 顾名思义,FAST比上述方法快得多。 该算法尝试找到位于对象边缘和角落的点,即 在对比差异的地方。 它们的位置如下:FAST在候选像素周围建立一个半径为R的圆,并检查它是否具有长度为t的连续像素段,该像素段比候选像素更暗(或更亮)K个单位。 如果满足此条件,则将像素视为“关键点”。 对于特定的t,我们可以通过添加一些初步的检查来有效地实现此启发式检查,这些检查将切断保证为非拐角的像素。 例如,当 R=3 和 t=12 ,只需检查4个极端像素中是否有3个连续像素严格比K的中心暗(或更亮)(在图片中-1、5、9、13)。 这种情况使您可以有效地切断绝对不是关键点的候选人。
SIFT
先前的两种算法都无法抵抗图像大小调整。 如果对象的比例已更改,它们将不允许您在图片中找到模板。 SIFT (尺度不变特征变换)提供了解决此问题的方法。 拍摄从中提取关键点的图像,并开始通过一些小步骤逐渐减小其大小,对于每个比例选项,我们都会找到关键点。 缩放是一个困难的过程,但是可以通过跳过像素来有效地将其缩小2/4/8 / ...时间(在SIFT中,这些多个缩放称为“八度”)。 通过对图片应用具有不同核心尺寸的高斯蓝色,可以近似得出中间比例。 如上所述,这可以有效地在计算上完成。 如果我们先缩小图像,然后再将其放大到原始大小,结果将看起来像-丢失了小的细节,图像变得“模糊”。

完成此过程后,我们计算相邻刻度之间的差异。 如果在下一个比例尺上不再可见一些小细节,或者相反,在下一个比例尺上开始捕获在上一个比例尺上不可见的某些部分,则这种差异的大(绝对值)值将变为零。 这种技术称为DoG,即高斯差分。 我们可以假设,在这种差异中非常重要的是,已经预示着图像上这个位置有一些有趣的信号。 但是我们对这个关键点最能体现出来的规模感兴趣。 为此,我们不仅将关键点视为与其周围环境不同的点,而且还将其视为在不同图像比例之间差异最大的点。 换句话说,我们不仅要在X和Y空间中选择一个关键点,还要在空间中选择一个关键点 (X,Y,比例) 。 在SIFT中,这是通过在DoG(高斯差分)中找到局部高点或低点来完成的。 3x3x3 空间立方体 (X,Y,比例) 在她周围:

查找关键点并构造SIFT和SURF描述符的算法已申请专利。 即,对于其商业用途,必须获得许可证。 这就是为什么它们不能从主opencv软件包中获得,而只能从单独的opencv_contrib软件包中获得的原因。 但是,到目前为止,我们的研究纯属学术性质,因此,没有什么可以阻止我们参加SIFT比较。
描述符
让我们尝试将某种检测器(例如,Harris)应用于模板和图片。


在图片和模板中找到关键点后,您需要以某种方式将它们相互比较。 让我提醒您,到目前为止,我们仅提取了关键点的位置。 这一点的含义(例如,找到的角度指向哪个方向),我们尚未确定。 这样的描述在将图像点和图案相互比较时会有所帮助。 图片中模板的某些点可能会因变形而移动,并被其他对象覆盖,因此仅依靠点相对于彼此的位置似乎是不可靠的。 因此,让我们为每个关键点建立一个邻域,以建立特定的描述(描述符),然后使我们获得几个点(模板中的一个点,图片中的一个点),并比较它们的相似性。
简讯
(.. 0 1), , XOR , . ? , N . , i- , , — i- 1. N. - (, — ), : , “”. , ( ). BRIEF .

. . , GII .
, , (.. , , ). OpenCV .
SIFT
SIFT , . SIFT 1616 , 44 . ( , ). 8 (, -, , ..). — 8 , , . . , 8- . 128 ( 4*4 = 16 , 8 ). .
比较方式
( — , ), - :

— . ?
, . , , . , , , , . ? BRIEF, , , . , BRIEF 1/16 . SIFT — - 1/4 .
SIFT.
现在,我们将获得的所有知识应用于解决我们的问题。在我们的案例中,对关键点检测器的需求就足够了:我们不需要不变性来调整大小,而且不需要极高的性能。比较所有三个检测器。
SIFT发现按钮上的关键点很少。这是可以理解的-按钮是一个很小的扁平对象,并且缩放无助于找到关键点。
同样,没有一个探测器可以处理第三种情况。 这是可以解释和预期的。 通常,以上方法用于从图片中的模板中查找对象,在该对象中对象可能会部分隐藏,旋转或略微变形。 在我们的例子中,我们不希望找到完全相同的对象 ,而是要找到一个与模板(按钮)非常相似的对象 。 这是一个稍微不同的任务。 因此,更改按钮本身的形状(例如,圆角的圆角半径或点的框架的厚度)会更改其中的关键点及其描述符。 此外,关键点将位于按钮的一角。 由于边缘上的位置,这些点将不稳定:它们的确切位置和描述符受按钮旁边绘制的内容的影响。
结论-该方法很好,并且可以正确地旋转所需对象的旋转,更改其大小或部分隐藏对象的情况(例如,这对于查找复杂的对象或价格标签非常有用)。 但是,如果对象上很少有可以“抓住”的点,或者对象的形状变化太大,则模板和图像上的关键点和它们可能不一致。 同样,具有许多小细节的背景可能会移动“关键点”或更改其描述符。
我们可以提出一个使用关键点坐标的匹配项。 您可以搜索这样的点集,而无需在模板和图片上寻找相似的点对,而是可以在模板和图片上找到关键点的插入点。 在一般情况下,这是一个相当复杂的任务(无论是从计算角度还是从编程角度而言),尤其是在某些点可能移动或不存在的情况下。 但是,考虑到我们有关键点-角度,对于我们而言,找到可以大致形成所需比例的矩形的组就足够了,并且在其中没有关键点。 逐渐地,我们得出以下方法:
轮廓检测
通常,按钮是某种矩形对象(有时带有圆角),其侧面与坐标轴平行。 然后,让我们尝试区分对比度差异区域(边缘),并在其中找到轮廓与所需对象轮廓相似的面孔。 此方法称为轮廓检测。
边缘检测
与关键点检测不同,我们不仅对关键点角度感兴趣,而且对边缘感兴趣。 但是,我们可以从那里获取基本思想。 使用高斯滤镜使图像平滑,就像在Harris角检测器中一样。 然后我们计算强度的导数 我X 和 我ÿ 。 由于我们不需要区分边缘的角度,因此我们不需要考虑结构张量-计算梯度的强度就足够了: I l = I 2 x + I 2 y (顺便说一下,这是 Ť - [R (高) ,或来自结构张量的对角线的总和)。 在那之后,我们只剩下就 我升 (使用已经考虑过的非最大抑制),但作为语言环境,我们将选择8个相邻像素,而不是8个相邻像素,而这些像素是I所针对的像素,并且是相反的:

所讨论的像素是蓝色,箭头是方向I。绿色像素是在非最大抑制期间要考虑的像素。
像素比较之所以如此不寻常,是因为我们不想在边框中留出空隙。 在左图中,人脸从上到下,并且由于非最大抑制不会将强度与蓝色上下的像素进行比较,因此我们得到了连续的人脸。
显然,一个非最大抑制是不够的,您需要应用某种过滤来去除Il值过低的边缘。 为此,我们采用“双重阈值”技术:我们删除所有具有Il且梯度强度低于Low阈值的像素,并将高于High阈值的所有像素指定为“强边缘”。 渐变强度介于“低”和“高”之间的像素称为“弱边缘”,仅当它们连接到“强边缘”时才保留它们:

浅蓝色表示“弱肋骨”,深蓝色-强烈。 下部的肋骨被筛出,因为它们没有与任何坚固的肋骨连接。
我们刚刚描述了Canny Edge Detector。 迄今为止,它已被广泛地用作一种简单,快速的过程,使您可以找到对象的轮廓。
边界追踪
下一步是在具有发现的面孔的地图中选择轮廓。 找到相关组件(已通过所有检查的相邻像素岛),并检查每个组件,它们看起来像一个按钮。 在Canny中应用非最大抑制之后,我们保证边缘将为一个像素厚,但是让我们依靠它。 对于分配给面部的每个像素,在其旁边有一个非面部像素,我们将其分配给“边框”。 从边界的一个像素移动到另一个像素,我们要么回到相同的像素(然后我们找到了路径),要么回到死胡同(然后,如果途中某个地方有叉子,您可以尝试返回):

此处介绍了考虑到不同边缘情况(例如,当具有厚脸的对象生成内部和外部两个轮廓时)的全边界跟踪算法。 应用此算法后,我们将获得一组可能是按钮的轮廓。
路径过滤
如何知道我们的电路是一个按钮? 对于矩形和多边形,有一种基于简化轮廓线的优秀方法 。 如果肋条几乎在一条直线上,则逐渐将它们“塌陷”就足够了,然后计算剩余肋条的数量并检查它们之间的角度。 不幸的是,对于我们的情况,这些方法不适合-我们的矩形具有圆角。 此外,具有复杂几何图形的图形也有轮廓匹配 -但这也不关乎我们,因为我们只有一个矩形(本文中提供了带有人类轮廓的示例)。 因此,最好根据图形本身的属性制作一个过滤器。 我们知道:
- 按钮足够大(面积超过100像素)
- 边平行于坐标轴
- 图形的面积与边界矩形的面积之比应非常接近于1。 我们将阈值设置为0.8,因为该按钮是边与坐标轴平行的矩形,而缺少的20%是圆角。
另外,从使用关键点检测器的经验来看,我们记得按钮下方有一个对比对象时可能会出现问题。 因此,在应用Canny之后,我们会模糊边缘以封闭可能由此类对象引起的小孔。
我们应用结果方法:

Canny过滤器应用程序(图2)找到了必要的形状,但是由于按钮的复杂形状和渐变,一次发现了许多轮廓,并且由于非最大抑制,其中一些没有闭合。 应用模糊(3张图片)可以解决此问题。
测试方法
运行搜索结果图片中的轮廓。 将通过测试的轮廓涂成红色。 如果其中有几个,那么我们需要选择其中最成功的选项。 我们选择最大区域的轮廓,并将其涂成绿色。
|
|
|
|
生成的设计在测试图像上找到了按钮。 对所有横幅的运行显示,偶尔(约20个案例中有1个案例)代替了按钮,而是选择了iOS Appstore和Google Apps的矩形图块,或其他矩形对象(手机壳)。 因此,添加了在错误确定的极少数情况下手动指示位置的功能,我们在定位工具中实现了此选项。
结论
总结一下。 无需深度学习的“经典”简历仍然可以工作,并基于此可以解决问题。 它们毫不客气,不需要大量标记数据,功能强大的硬件,并且易于调试。 但是,他们引入了其他假设,因此,在他们的帮助下,并不是每个问题都能得到有效解决。
- 模板匹配是最简单的方法,它基于在图像中找到与模板最相似(通过某种简单度量)的位置。 对逐像素匹配有效。 可以使其抗弯曲和尺寸变化较小,但是如果变化较大,则可能无法正常工作。
- 关键点检测/匹配 -查找关键点,使图像和模板的点匹配。 检测器可以抵抗旋转,缩放(取决于所选的检测器和描述符),并且可以匹配部分重叠。 但是,只有在对象中有足够的“关键点”并且模板和图像点的位置非常吻合(即,模板和图片上的对象相同)时,此方法才有效。
- 轮廓检测 -查找对象的轮廓,并找到与所需对象轮廓相似的轮廓。 此解决方案仅考虑对象的形状,而忽略其内容和颜色(可以是加号也可以是减号)。
博学的读者可能会注意到,借助现代训练有素的计算机视觉方法可以解决我们的问题。 例如, YOLO网络返回所需对象的边界框-这正是我们感兴趣的。 是的,我们成功地测试并启动了基于深度学习的解决方案-但是这是第二次迭代(已经在本地化工具启动并开始工作之后)。 这些解决方案更能抵抗按钮参数的更改,并具有许多积极的特性:例如,您无需动手拿起阈值和参数,而只需在训练集中添加错误的网络示例(主动学习)即可。 将深度学习用于我们的任务有其问题和有趣之处。 例如,许多现代计算机视觉方法需要大量的标记图像,但是我们没有标记(在许多实际情况下),并且不同标语的总数不超过数千。 因此,我们决定自己布置少量图像,并编写一个生成器,以根据它们创建其他类似的横幅。 在这个方向上有很多有趣的技巧 。 还有许多其他陷阱,确定计算机视觉对象位置的任务非常艰巨,并且有很多解决方案。 因此,决定限制文章的视野,并且不考虑基于深度学习的决策。
可以在存储库中找到带有记事本的代码,这些记事本可以实现所描述的方法并绘制文章的图片。