003 目标检测(Object Detection)原理与实现(四)~(六)

Post date: 2015/7/12 下午 01:39:26

目标检测(Object Detection)原理与实现(四)

基于ASM的目标检测

ASM(Active Shape Model:主动形状模型)是Tim Cootes于1995年提出来的,其实是在1992年提交,1994年被接受,1995被发表的。ASM方法是通过寻找一系列匹配点来检测形状的方法,和单纯的基于shift(或者surf)特征点匹配的方法不一样,后者是通过互相独立的shift(或者surf)特征点匹配来做目标检测,当模版图像和待匹配图像之间的大多数shift(或者surf)匹配上了,就宣称目标找到,优点是仿射不变(旋转,缩放,简单的仿射变换),缺点是发生目标发生形变的时候,此种方法会失效。而ASM可适用于有形变的目标检测,这种方法和上节的霍夫投票的方法都是基于统计学习的框架来做的,ASM通过前期训练 (build阶段)来获得一个目标的部件轮廓点分布模型,检测阶段(fit)通过匹配各个部件轮廓点来完成目标检测,咋一听,也是基于特征点匹配的,但是这些特征点之间不是独立的,所有特征点都在小范围内寻找配对点,当所有配对之间的距离之和最小时就宣称完成了目标检测,也就是说每个特征点配对都最满意咯

。同样搜索也会陷入局部最小,只有模型初始位置选的好,然后模型上的每个点小范围内搜索下就完成了匹配,因此初始的位置预估的好坏也影响着ASM的性能,这是他的缺点,一般要借助于其他方法来进行初始位置的预估,比如人脸匹配就要接助于cascade等方法来检测到人脸的位置,然后进行ASM匹配。TimCootes后来还提出了AAM(ActiveAppearance model:主动外观模型)算法,顾名思义偏重于纹理而不是形状,二者的主要区别如下:

1、ASM仅使用一小块图像区域的纹理来寻找特征点,而AAM则使用整个特征点区域的图像。

2、ASM搜索特征点的准则是沿着图像边界的法线来寻找,而AAM仅在当前位置采样。

3、ASM是为了寻找所有特征点匹配距离最小,AAM则是使得合成模型图像和目标图像匹配代价最小。

下面就来看看ASM的工作原理吧:

一、模型的建立(build)

第一步:选择合适的特征点

选择好的特征点对匹配起着决定性作用。好的特征点大概应该或多或少满足如下几点:边缘点、曲率大的、T型连接点和以上这些点的连线上的等分点,如(图一)所示:

(图一)

这些特征点是有序的,通过一系列特征点来描述物体,把这些特征点的坐标串起来形成一个2n维的向量:

,注意坐标不是成对排列的,如上述表达式所示,先是排列X,后排列Y。而这只是一个图像实例形状的描述,假设我们的训练集有S个图像,那么这S个2n维的向量则构成了2n维的向量分布,同样也可以构成一个2n维的向量空间,说到向量空间就有点类似于稀疏编码的基咯,这个话题就此打住,感兴趣的可以翻看前面关于稀疏编码的博文。这个向量分布可以描述大多数的图像模型,同样也可以生成一个类似于原始训练集的图像目标实例。如果这个实例很像训练集中的图像形状样子,那么这个分布是可靠的。那怎么来得到这个分布呢?

考虑到S个手工标注2n维的向量冗余信息很大,可以对其采用PCA方法进行降维。相当于在这个2n维的向量空间里找到几个空间轴来描述分布。基于此作者直接假设了下面的一个模型,如(公式一)所示:

(公式一)

其中P是包含了前t个主成分的协方差矩阵,也就是t个协方差的特征向量,b是一个t维的向量,用来控制特征点形状的变化,可以用(公式二)在训练集中求取,这步还有个问题,就是PCA中主成分个数t的选取,有两种方法:1)选择前s个;2)选择前k%的分量,这里作者推荐使用第二种方法。

(公式二)

当b为0时,X-bar(x上面一横的那个符号)即坐标原点(平均形状),其实是很好理解哈。但这里b不要太大,如果太大,会导致整个形状变化超出人脸的变化范围,会使人变得异常狰狞,大家懂的。。。所以作者这里做了约束,如(图二)和(公式三)所示:

(图二)

(公式三)

二、检测阶段(fix)

这个阶段就像刚开始说的,先用其他第三方方法检测到目标的大概位置,然后把模型初始位置选在那,接着完成两个阶段的任务:一,模型轮廓大概匹配,二,特征点匹配 。模型轮廓大概匹配阶段就是在模型初始位置定位好后,对模型进行一些旋转,平移,缩放的调节,使得模型的朝向和大小和图像中的目标大概差不多,如(公式四)所示:

(公式四)

其中X表示对应待检测图像中调整后的模型的点,(Xt,Yt)、s、theta分别表示平移,缩放,旋转变换,这些变换在图像处理中经常用到的,具体如(公式五)所示:

(公式五)

对于公式五中的参数大家可能比较关系怎么求取这些参数,在图像中可以通过几对对应点来求解,这里给给出一些近似方法,这些参数的求取可按(图三)所述步骤来完成:

(图三)

模型轮廓大概匹配之后就进行特征点匹配,具体来说就是沿着轮廓边缘法线的方向进行搜索、匹配,匹配的方法可以使用图像块的SSD方法,SSD就是图像块之间的像素点差的平方和。也可以使用类似sift的方法来匹配,但是sift被申请了专利,没法免费使用,本节的例子使用了类似sift的方法:Histogram Array Transform。

当所有匹配点之间的欧式距离和最短时,就完成了目标检测(匹配)。如(公式六)所示:

(公式六)

其中Y表示待检测图像中每个模型点附近的图像点,找到Y,再利用Y反求b,并且更新b,直到收敛。目标点搜寻匹配准则如(图四)所示:

(图四)

最后对上述来个总结,整体的匹配流程如(图五)所示:

(图五)

点匹配过程在具体实现中也可以采用金字塔的方式,有粗到精来加快目标点的搜索过程,另外还有些快速判断先验信息,比如先验信息认为特征点主要是图像的强边缘点,并且图像灰度的梯度服从高斯分布,只要找到模型特征点附近梯度最大的值,即认为是特征点所在的位置。但有时这种信息会带来误判,如实验效果(图六)和(图七)所示:

(图六) (图七)

(图七)红圈处的眼镜边缘处强的边缘点被误判成特征点。因此该算法还有很多该改进的地方,虽然如此,ASM仍然是获取人脸特征的强有力的方法,这节写的比较仓促,如果有错误的地方,请指出,谢谢。

参考文献:

An Introduction to Active Shape Models. Tim Cootes

Locating Facial Features with an Extended Active ShapeModel.Stephen Milborrow

Comparing Active Shape Models with Active Appearance Models.TimCootes

Markov Random Field Modeling in Image Analysis. Stan Z.Li

http://blog.sina.com.cn/s/blog_6d8e91f401015pv5.html

转载请注明来源:http://blog.csdn.net/cuoqu/article/details/9154685

目标检测(Object Detection)原理与实现(五)

基于Cascade分类器的目标检测

从今天开始进入基于机器学习的目标检测,前几节虽然也接触了一些机器学习的方法,但它主要是做辅助工作,机器学习的方法和非机器学习的方法结合在一起使用,说到这想起来前几天看到一位博士师兄发的笑话,说的是百度实验室:

Theory is when you know everthing but nothing works.

Practice is when everything works but no one knows why.

In our lab,theory and practice are combined:nothing works and no one knows why.

目前而言,甭管理论好坏吧,只要实用就行,实用的未必是好理论,就像深度学习那样,不说太远了,继续今天的话题,Cascade是Paul Viola发表在2001年的CVPR上,2002年Rainer Lienhart等人改进了Paul的方法,主要是改进了特征并且分析了不同的boosting算法对分类性能的影响和计算复杂度,OpenCV实现的Cascade的分类器也是Rainer的改进版本。所谓不同的boosting算法就是说不同的Adaboost弱分类器,比如Discrete, Real 和 Gentle Adaboost弱分类器,而Cascade(级联)分类器就是基于多个Adaboot弱分类器对不同的特征进行依次处理(分类)来完成对目标的检测,简单的说有多个Adaboost串起来,然后提取每个平滑窗(sliding window)上的不同特征,把这些特征依次放进不同的Adaboost弱分类器里判断,如果所有的弱分类器都判断正标签(1),则表示该该平滑窗内检测到目标,如(图一)所示。这样做的好处是不但通过多个弱分类器来形成一个强的级联分类器,而且可以减少运算量,比如当一个平滑窗第一个特征没有通过第一个分类器,那么就没有必要继续运算下去,直接拒绝掉当前平滑窗,转而处理下一个平滑窗,事实上作者的目的就是为了快速抛弃没有目标的平滑窗,从而达到快速检测目标。

(图一)

知道了Cascade强分类器是基于Adaboost算法的,那我们先看下Adaboost弱分类器的工作原理吧,直接上图,很简单,如图二所示:

(图二)

但OpenCV里还不是用的这个Adaboost,而是用的Rainer等人改进的Gentle Adaboost弱分类器,Gentle Adabboost弱分类器的工作原理如(图三)所示:

(图三)

Rainer等人比较了DiscreteAdaboost,Real Adaboost,Gentle Adaboost弱分类器,发现Gentle Adaboost弱分类器比其他两种效果,但是作者没有详细讨论为什么比他们好,作者只是给出了实际检测的性能比较分析图,我也没看出为什么,如果你们知道为什么,请毫不吝啬的告知,在此先谢过了,为了严谨,把三种分类器的性能分析比较图也发出来吧,如(图四)所示:

(图四)

其中GAB表示Gentle Adaboost,RAB表示Real Adaboost,DAB表示Discrete Adaboost。

好了,介绍完了分类器的工作原理,下面来看下使用的是什么特征。2001年Paul Viola的CVPR上用的几个不同的特征很简单,就是平滑窗内某些区域像素和的差值,比如(图五)所示的,外围黑色框表示平滑窗,窗内固定的位置有个黑白相间的矩形区域,黑色表示该位置上的像素每个权重都是负一(-1),白色位置上的像素权重为正一(1),然后权重于像素卷积得到的值就是特征值,就一个数字(说的白话一点,就是每个像素值乘上权值后,然后黑白相间的矩形区域相加),不同的黑白相间的矩形区域的计算得到不同的特征,作者还提出一个加速计算这个特征的方法,就是积分图,在此不说了,网上很多。

(图五)

同样,OpenCV的实现也没有使用上述特征,而是使用了2002年Rainer 等人改进的Harr-like特征,计算方法也类似,如图六所示:

(图六)

也是矩形区域,不过不同的特征变化的样式多了一些,Rainer也提出了一些快速计算方法,具体阅读参考论文吧。有了特征,有了级联分类器,就是训练和检测了。

直接调用OpenCV的例子程序检测的效果如(图七)所示:

(图七)

这节比较简单,只所以要说这个cascade分类器,是因为前一节用到了这个分类器用于检测人脸,而且后续也会出现cascade级联的思想,也可以给自己查漏补缺,写作仓促,难免有错,如发现请指出,谢谢。

有人做过测试:Opencv的正脸检测精度是68.84058%

Total images 1104

Total correct 760

Total false negatives 314

Total false positives 30%

accurate 68.84058

侧脸识别精度是33.00091

Total images 1103

Total correct 364

Total false negatives 721

Total false positives 18

% accurate 33.00091

参考文献:

[1]Rapid Object Detection using a Boosted Cascade of Simple Features. Paul Viola

[2]Empirical Analysis of Detection Cascades of Boosted Classifiers for Rapid Object Detection. Rainer Lienhart, Alexander Kuranov, Vadim Pisarevsky

转载请注明来源:http://blog.csdn.net/cuoqu/article/details/9173645

目标检测(Object Detection)原理与实现(六)

基于形变部件模型(Deformable Part Models)的目标检测

上节说了基于cascade的目标检测,cascade的级联思想可以快速抛弃没有目标的平滑窗(sliding window),因而大大提高了检测效率,但也不是没缺点,缺点就是它仅仅使用了很弱的特征,用它做分类的检测器也是弱分类器,仅仅比随机猜的要好一些,它的精度靠的是多个弱分类器来实行一票否决式推举(就是大家都检测是对的)来提高命中率,确定分类器的个数也是经验问题。这节就来说说改进的特征,尽量使得改进的特征可以检测任何物体,当然Deep Learning学习特征很有效,但今天还是按论文发表顺序来说下其他方法,(服务器还没配置好,现在还不能大批跑Deep Learning ^.^),在第四节说了ASM并且简单的提了下AAM,这两个模型其实就是形变模型(deform model),说到基于形变模型检测物体的大牛,就不得说说芝加哥大学教授Pedro F. Felzenszwalb,Pedro发表很多有关基于形变部件来做目标检测的论文,并靠这个获得了VOC组委会授予的终身成就奖,另外它早期发表的《Belief propagation for early vision》也很出名,虽然比不上Science那样的开辟新领域的Paper,但在不牺牲精度的情况下大大提高了BP算法的运行效率,这个BP算法不是神经网络的BP算法,而是概率图模型里的推理求解方法(最大后验概率),它也被用在了后面要说基于霍夫推理的目标检测。貌似Pedro很擅长做这种事情,他的另外一篇论文《Cascade Object Detection with Deformable Part Models》也是不牺牲精度的情况下把基于形变部件做目标检测的效率提高了20倍,今天就来学习一下这种基于形变部件的目标检测。

基于形变部件的目标检测是现在除了深度学习之外的还相对不错的目标检测方法,先来看下为什么要使用形变部件,在(图一)中,同一个人的不同姿态,试问用前面几节中的什么方法可以检测到这些不同姿态的人?阈值不行,广义霍夫变换行吗?人的姿态是变换无穷的,需要太多的模板。霍夫森林投票?貌似可以,但是霍夫森立的特征是图像块,只适用于一些形变不大的物体,当图像块内的形变很大时同样不太适用。那么ASM可以吗?想想也是和广义霍夫变换一样,需要太多的均值模板。归根结底就是我们没有很好的形状描述方法,没有好的特征。而Pedro几乎每发表一篇论文就改进一下形状描述的方法,最终由简单的表示方法到语法形式的表示方法,其演化过程可以在参考文献[4]中看出,参考文献[4]是Pedro的博士论文。

(图一)

既然上节中的几种方法都不能解决大形变目标的检测问题,那基于形变部件的目标检测也该上场了。Pedro的五篇关于目标检测的顶级paper,小生就不一一说了,挑参考文献中的三篇学习一下。参考文献[1]、[2]、[3]分别讲述了如何利用形变模型描述物体(特征阶段)、如何利用形变部件来做检测(特征处理+分类阶段)、如何加速检测。首先来说下文献[1]的形变部件。在Deformable Part Model中,通过描述每一部分和部分间的位置关系来表示物体(part+deformable configuration)。其实早在1973年,Part Model就已经在 “Therepresentation and matching of pictorial structures” 这篇文章中被提出了。

(图二)

Part Model中,我们通过描述a collection of parts以及connection between parts来表示物体。(图二)表示经典的弹簧模型,物体的每一部分通过弹簧连接。我们定义一个energy function,该函数度量了两部分之和:每一部分的匹配程度,部分间连接的变化程度(可以想象为弹簧的形变量)。与模型匹配最好的图像就是能使这个energy function最小的图片。形式化表示中,我们可以用一无向图 G=(V,E) 来表示物体的模型,V={v1,…,vn} 代表n个部分,边 (vi,vj)∈E 代表两部分间的连接。物体的某个实例的configuration可以表示为 L=(l1,…,ln),li 表示为 vi 的位置(可以简单的将图片的configuration理解为各部分的位置布局,实际configuration可以包含part的其他属性)。给定一幅图像,用 mi(li) 来度量vi 被放置图片中的 li 位置时,与模板的不匹配程度;用 dij(li,lj) 度量 vi,vj 被分别放置在图片中的 li,lj位置时,模型的变化程度。因此,一副图像相对于模型的最优configuration,就是既能使每一部分匹配的好,又能使部分间的相对关系与模型尽可能的相符的那一个。同样的,模型也自然要描述这两部分。可以通过下面的(公式一)描述最优configuration:

(公式一)

优化(公式一)其实就是马尔科夫随机场中的经典问题求解,可以用上面说的BP算法求解。说的理论些就是最大化后验概率(MAP),因为从随机场中很容易转换到概率测度中(gibbs measure),在这就不说那么复杂了,想系统的学习相关理论可以学习概率图模型(probabilistic graphical model)。识别的时候采用就是采用部件匹配,并且使得能量最小,这有点类似于ASM,但是ASM没有使用部件之间的关系,只是单纯的让各匹配点之间的代价和最小。匹配结果如(图三)所示:

(图三)

上面的方法没有用到机器学习,另外部件的寻找也不是一件容易的事情,因为首先要大概预估部件的位置,因此这个方法也有缺点,但这个形变部件的思想可以用来作为特征,接着就来看下Pedro的第二篇文献[2]如何用它来做目标检测。

Pedro在文献[2]中基于形变模型的目标检测用到了三方面的知识:1.Hog Features 2.Part Model 3. Latent SVM。

1. 作者通过Hog特征模板来刻画每一部分,然后进行匹配。并且采用了金字塔,即在不同的分辨率上提取Hog特征。

2. 利用上段提出的Part Model。在进行object detection时,detect window的得分等于part的匹配得分减去模型变化的花费。

3. 在训练模型时,需要训练得到每一个part的Hog模板,以及衡量part位置分布cost的参数。文章中提出了Latent SVM方法,将deformable part model的学习问题转换为一个分类问题。利用SVM学习,将part的位置分布作为latent values,模型的参数转化为SVM的分割超平面。具体实现中,作者采用了迭代计算的方法,不断地更新模型。

针对上面三条,我们可能有几个疑问:1、部件从何而来?2、如何用部件做检测?在基于部件做目标检测之前,赢得PASCAL VOC 2006年挑战的Dalal-Triggs的方法是直接用HOG作为特征,然后直接基于不同尺度的滑动窗口做判别,像一个滤波器,靠这个滤波器赢得短时的荣誉,但不能抗大形变的目标。Pedro改进了Dalal-Triggs的方法,他计算作为一个得分,其中beta是滤波器,phi(x)是特征向量。通过滤波器找到一个根(root)部件p0,根部件有专门的滤波器,另外还有一系列非根部件(parts)p1…pn,然后把他们组成一个星形结构,此时回顾(图一)的形变模型思想。每个部件用

来表示,其中X,Y是坐标,L表示金字塔级别。当这个星形结构的匹配得分减去模型变化的代价得到最终分最高时,就完成了匹配,如(公式二)所示:

(公式二)

其中F’表示滤波器的向量化表示,b是偏移项,H表示特征金字塔。现在假设滤波器解决了部件,完成了匹配,解答了第二个疑问,但是滤波器从何而来,简单的说就是这个滤波器的权重beta是多少?现在不知道部件,也不知道滤波器,没有滤波器就没有部件,没有部件也求不出滤波器的参数,这就是典型的EM算法要解决的事情,但是作者没有使用EM算法,而是使用隐SVM(Latent SVM)的方法,隐变量其实就是类似统计中的因子分析,在这里就是找到潜在部件。在训练的时候对部分部件进行打标签,用他们求beta,然后用beta再来找潜在部件,因此使用coordinatedescent迭代求解,再一次遇到这个求解方法。有了部件和打分,就是寻找根部件和其他部件的结合匹配最优问题,可以使用动态规划,但很慢,具体请参考文献[2]。

在文献[2]中虽然使用了金字塔来加速搜寻速度,但是对星形结构组合的搜索匹配计算量也很大,检测速度稍慢。因此接着来看第三篇文献[3],文献[3]就是加速检测过程,对于星形结构模型采用cascade来判断,来快速抛去没有有效信息的part,其实实际中根部件的位置对匹配起着很大作用,然后依次对其他部件(n+1),有了这种关系,取一些部件子集后我们可以采用cascade来修剪、抛去一些不是好配置的部件组合(官方用语叫配置),这样一些在弱分类器中评分高的组合进入更一步的判断,类似于cascade的级联思想,但是要注意形变模型的每个部件应该是相关的,而不应该像上节那样harr-like特征之间独立,依次判断在这里行不通,这里其实是个子序列匹配问题,文献[7]提出过一种解决方法,pedro又改进了此方法,在原来n+1个部件的基础上增加n+1可以快速计算的简单部件,这样打乱之后,子序列匹配的代价就小了一些。

下面正式进入检测流程,看看怎么来加速的,大概流程如(图四)所示:

(图四)

其中各个notation含义如(图五)所示(特别注意p不是在上面说的部件,而是表示部件vi的贡献):

(图五)

基于部件检测的主题思想到此差不多了,但是还有更多的trick没有说,比如阈值选取、如何计算简单的部件等

检测效果如(图六)所示:

(图六)

这是一篇学习笔记式的“流水账”,难免有说错的地方,如发现请指出,谢谢。本节所有的文献代码都集成在一起挂在pedro主页上。

参考文献:

[1] Pictorial Structures for Object Recognition. Pedro F.Felzenszwalb

[2]Object Detection with Discriminatively Trained Part Based Models.Pedro F. Felzenszwalb

[3]Cascade Object Detection with Deformable Part Models. Pedro F.Felzenszwalb

[4]From RigidTemplates To Grammars: Object Detection With Structured Models. Pedro F.Felzenszwalb

[5]Histogramsof oriented gradients for human detection. N. Dalal and B. Triggs

[6] http://bubblexc.com/y2011/422/

[7]A computational model for visual selection.Y. Amit and D.Geman

转载请注明来源:http://blog.csdn.net/cuoqu/article/details/9244193