常用算法简介

机器视觉中常用图像处理算法

机器视觉就是用机器代替人眼来做测量和判断。机器视觉系统是指通过机器视觉产品（即图像摄取装置，分 CMOS 和CCD 两种）将被摄取目标转换成图像信号，传送给专用的图像处理系统，得到被摄目标的形态信息，根据像素分布和亮度、颜色等信息，转变成数字化信号；图像系统对这些信号进行各种运算来抽取目标的特征，进而根据判别的结果来控制现场的设备动作。机器视觉是使用计算机（也许是可移动式的）来模拟人的视觉，因此模拟才是计算机视觉领域的最终目标，而真正意义上的图像处理侧重在“处理”图像：如增强，还原，去噪，分割，等等，如常见的Photoshop就是功能强大的图像处理软件。大部分的机器视觉，都包含了图像处理的过程，只有图像处理过后，才能找到图像中需要的特征，从而更进一步的执行其它的指令动作。在我们实际工程应用中研究的一些图像算法，实际上是属于机器视觉，而不是纯粹的图像处理。总的来说，图像处理技术包括图像压缩，增强和复原，匹配、描述和识别3个部分，在实际工程中，这几块不是独立的，往往是环环相扣、相互辅助来达到实际效果。接下来简单介绍一下机器视觉中常用的图像处理算法。 一、 滤波

滤波一般在图像预处理阶段中使用，改善图像信息，便于后续处理，当然，这不是绝对的，在图像算法过程中如果有需要，随时可以进行滤波操作。比较常用的滤波方法有以下三种：

1、均值滤波

均值滤波也称为线性滤波，其采用的主要方法为邻域平均法。线性滤波的基本原理是用均值代替原图像中的各个像素值，即对待处理的当前像素点(x,y)，选择一个模板，该模板由其近邻的若干像素组成，求模板中所有像素的均值，再把该均值赋予当前像素点(x,y)，作为处理后图像在该点上的灰度值g(x,y)，即

g(x,y)?1?f(x,y)，m为该模板中包含当前像素在内的像素总个数。这种滤m波方法可以平滑图像，速度快，算法简单。但是无法去掉噪声，只能减弱噪声。

2、中值滤波

1

中值滤波法是一种非线性平滑技术，它将每一像素点的灰度值设置为该点某邻域窗口内的所有像素点灰度值的中值。其实现过程为：

1) 从图像中的某个采样窗口取出奇数个数据进行排序 2) 用排序后的中值作为当前像素点的灰度值

在图像处理中，中值滤波常用来保护边缘信息，是经典的平滑噪声的方法，该方法对消除椒盐噪声非常有效，在光学测量条纹图像的相位分析处理方法中有特殊作用。

3、高斯滤波

高斯滤波是一种线性平滑滤波，适用于滤除高斯白噪声，已广泛应用于图像处理的预处理阶段。对图像进行高斯滤波就是对图像中的每个点的像素值进行计算，计算准则是，由该点本身灰度值及其邻域内的其他像素灰度值加权平均所得，而加权平均的权系数由二维离散高斯函数采样并归一化后所得。离散的高斯卷积核H：(2k?1)?(2k?1)维，其元素计算方法为： Hi,j?12??e2?(i?k?1)2?(j?k?1)22?2 其中?为方差，k确定核矩阵的维数。 二、 图像分割

图像分割就是把图像分成若干个特定的、具有独特性质的区域并提取出感兴趣目标的技术和过程。它是由图像处理到图像分析的关键步骤。现有的图像分割方法主要分以下几类：基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法以及基于特定理论的分割方法等。图像分割后提取出的目标可以用于图像语义识别、图像搜索等领域。

1、 阈值分割法

最常用的阈值分割方法有最大类间方差法(OTSU)、最小误差法、最大熵法等方法，其中，OSTU算法应用最多。

最大类间方差法OTSU算法又称为大津算法，是在判决分析最小二乘法原理的基础上，推导得出的自动选取阈值的二值化方法，其基本思想是将图像直方图用某一灰度值分割成两组，当被分割成的两组方差最大时，此灰度值就作为图像二值化处理的阈值。OSTU阈值法有较好的鲁棒性，使用范围比较广，不论图

2

像的直方图有无明显的双峰，都能得到比较满意的分割效果。

设灰度图像f(x,y)的灰度级为0:L，灰度级i的像素数为ni，则图像中总像素数为N??ni，灰度级i出现的概率为pi?niN，pi?0，?pi?1，总的灰

i?0i?0LL度平均值为???ipi。

i?0L设阈值k将灰度级分为两组C0、C1，分别代表背景和目标：C0?0:k，

C1?k?1:L，则有：

C0产生的概率：?0??pi??k

i?0LkC1产生的概率：?1?ki?k?1?pi?1??k

k?k，其中?k??ipi C0的均值：?0????ki?0i?0?0ipiC1的均值：?1?i?k?1??Lipi1????k 1??k则两组间的数学期望为：?0?0??1?1??

按照模式识别理论，可求出这两类的类间方差为：

?2(k)??0(?0??)2??1(?1??)2 ??0?1(?1??0)2?[??(k)??(k)]2(?(k)[1??(k)]) 以类间方差?2(k)作为衡量不同阈值导出的类别分离性能的测量准则，极大化?2(k)的过程就是自动确定阈值的过程，因此，最佳阈值Th为：

Th?arg max?2(k)

0?k?L因方差是灰度分布均匀性的一种度量，方差值越大，说明构成图像的两部分差别越大，当部分目标错分为背景或部分背景错分为目标都会导致两部分差别变小，因此类间方差最大的分割意味着错分概率最小。

3

2、 基于区域的分割法

区域增长法是一种比较普遍的方法，在没有先验知识可以利用时，可以取得最佳的性能，可以用来分割比较复杂的图像，如自然景物。但是，区域增长方法是一种迭代的方法，空间和时间开销都比较大。

区域生长的基本思想是将具有相似性质的像素集合起来构成区域。具体先对每个需要分割的区域找一个种子像素作为生长起点，然后将种子像素和周围邻域中与种子像素有相同或相似性质的像素（区域内像素的相似性度量可以包括平均灰度值、纹理、颜色等信息）合并到种子像素所在的区域中。将这些新像素当作新的种子继续上面的过程，直到没有满足条件的像素可被包括进来。这样一个区域就生长成了。

除此之外还有区域分裂合并的方法，基本思想是先确定一个分裂合并的准则，即区域特征一致性的测度，当图像中某个区域的特征不一致时就将该区域分裂成4 个相等的子区域，当相邻的子区域满足一致性特征时则将它们合成一个大区域,直至所有区域不再满足分裂合并的条件为止。当分裂到不能再分的情况时，分裂结束，然后它将查找相邻区域有没有相似的特征，如果有就将相似区域进行合并，最后达到分割的作用。在一定程度上区域生长和区域分裂合并算法有异曲同工之妙，互相促进相辅相成的，区域分裂到极致就是分割成单一像素点，然后按照一定的测量准则进行合并，在一定程度上可以认为是单一像素点的区域生长方法。区域生长比区域分裂合并的方法节省了分裂的过程，而区域分裂合并的方法可以在较大的一个相似区域基础上再进行相似合并，而区域生长只能从单一像素点出发进行生长（合并）。一致性准则的选择及阈值设定是影响区域分割算法的关键因素。

3、 活动轮廓的分割法

最经典、使用最广的活动轮廓模型是Snake模型，它以构成一定形状的一些控制点为模板（轮廓线），通过模板自身的弹性形变，与图像局部特征相匹配达到调和，即某种能量函数极小化，完成对图像的分割。再通过对模板的进一步分析而实现图像的理解和识别。

Snake模型首先需要在感兴趣区域的附近给出一条初始曲线，接下来最小化能量泛函，让曲线在图像中发生变形并不断逼近目标轮廓。

4

Kass等人提出的原始Snakes模型由一组控制点：v(s)?[x(s),y(s)], s?[0,1]组成，这些点首尾以直线相连构成轮廓线。其中x(s)和y(s)分别表示每个控制点在图像中的坐标位置。s是以傅立叶变换形式描述边界的自变量。在Snakes的控制点上定义能量函数（反映能量与轮廓之间的关系）： Etotal??2??(?v(s)??2v(s)?Eext(v(s)))ds， ?s?ss22其中第1项称为弹性能量是v的一阶导数的模，第2项称为弯曲能量，是v的二阶导数的模，第3项是外部能量（外部力），在基本Snakes模型中一般只取控制点或连线所在位置的图像局部特征例如梯度：

Eext(v(s))?P(v(s))???I(v)， 2也称图像力。（当轮廓C靠近目标图像边缘，那么C的灰度的梯度将会增大，那么上式的能量最小，由曲线演变公式知道该点的速度将变为0，也就是停止运动了。这样，C就停在图像的边缘位置了，也就完成了分割。那么这个的前提就是目标在图像中的边缘比较明显了，否则很容易就越过边缘了。） 弹性能量和弯曲能量合称内部能量（内部力），用于控制轮廓线的弹性形变，起到保持轮廓连续性和平滑性的作用。而第三项代表外部能量，也被称为图像能量，表示变形曲线与图像局部特征吻合的情况。内部能量仅跟Snake的形状有关，而跟图像数据无关。而外部能量仅跟图像数据有关。在某一点的?和?的值决定曲线可以在这一点伸展和弯曲的程度。 选取适当的参数?和?，将能量函数Etotal极小化，所对应的v(s)就是对物体的分割。在能量函数极小化过程中，弹性能量迅速把轮廓线压缩成一个光滑的圆，弯曲能量驱使轮廓线成为光滑曲线或直线，而图像力则使轮廓线向图像的高梯度位置靠拢。基本Snakes模型就是在这3个力的联合作用下工作的。因为图像上的点都是离散的，所以用来优化能量函数的算法都必须在离散域里定义，求解能量函数Etotal极小化是一个典型的变分问题。 三、 特征提取

1、 HOG特征

5

方向梯度直方图（Histogram of Oriented Gradient，HOG）特征是一种在计算机视觉和图像处理中用来进行物体检测的特征描述子。它通过计算和统计图像局部区域的梯度方向直方图来构成特征。HOG特征结合SVM分类器已经被广泛应用于图像识别中，尤其在行人检测中获得了极大的成功。HOG+SVM进行行人检测的方法是法国研究人员Dalal在2005的CVPR上提出的，如今虽然有很多行人检测算法不断提出，但基本都是以HOG+SVM的思路为主。HOG特征的提取过程如下：

1) 标准化gamma空间和颜色空间 为了减少光照因素的影响，首先需要将整个图像进行规范化（归一化）。在图像的纹理强度中，局部的表层曝光贡献的比重较大，所以，这种压缩处理能够有效地降低图像局部的阴影和光照变化。因为颜色信息作用不大，通常先转化为灰度图。Gamma压缩公式为： I(x,y)?I(x,y)gamma 可以取gamma?12。 2) 计算图像梯度 计算图像横坐标和纵坐标方向的梯度，并据此计算每个像素位置的梯度方向值，梯度特征可以弱化光照的影响。 图像中像素点(x,y)的梯度为： Gx(x,y)?I(x?1,y)?I(x?1,y)Gy(x,y)?I(x,y?1)?I(x,y?1)， 其中，Gx(x,y)、Gy(x,y)和I(x,y)分别表示输入图像中像素点(x,y)处的水平方向梯度、垂直方向梯度和像素值。像素点(x,y)处的梯度幅值和梯度方向分别为：

G(x,y)?Gx(x,y)2?Gy(x,y)2 ?(x,y)?tan(?1Gy(x,y)Gx(x,y)， )3) 为每个细胞单元构建梯度方向直方图 6

这一步的目的是为局部图像区域提供一个编码。将图像分成若干个“单元格cell”，例如每个cell为6*6个像素。假设采用9个bin的直方图来统计这6*6个像素的梯度信息。也就是将cell的梯度方向360度分成9个方向块，如图所示：

例如：如果这个像素的梯度方向是20-40度，直方图第2个bin的计数就加上这个像素的梯度幅值，这样，对cell内每个像素用梯度方向在直方图中进行加权投影（映射到固定的角度范围），就可以得到这个cell的梯度方向直方图了，就是该cell对应的9维特征向量（因为有9个bin）。

4) 把细胞单元组合成大的块（block），块内归一化梯度直方图

由于局部光照的变化以及前景-背景对比度的变化，使得梯度强度的变化范围非常大。这就需要对梯度强度做归一化。归一化能够进一步地对光照、阴影和边缘进行压缩。方法是：把各个细胞单元组合成大的、空间上连通的区间（blocks）。这样，一个block内所有cell的特征向量串联起来便得到该block的HOG特征。这些区间是互有重叠的，这就意味着：每一个单元格的特征会以不同的结果多次出现在最后的特征向量中，归一化之后的块描述符（向量）就称之为HOG描述符。

5) 收集HOG特征

最后一步就是将检测窗口中所有重叠的块进行HOG特征的收集，并将它们结合成最终的特征向量供分类器使用。

2、 SIFT特征

SIFT特征是具有尺度不变性的局部特征检测算法。整个算法分为以下几个部分：

1) 构建尺度空间

7

这是一个初始化操作，通过生成尺度空间来创建原始图像的多层表示以保证尺度不变性。高斯卷积核是实现尺度变换的唯一线性核，一幅二维图像的尺度空间定义为：

L(x,y,?)?G(x,y,?)?I(x,y)， 其中，?表示卷积，G(x,y,?)是尺度可变高斯函数： G(x,y,?)?12??2e?(x2?y2)2?2， (x,y)是空间坐标，?的大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的?值对应粗糙尺度(低分辨率)，反之，对应精细尺度(高分辨率)。为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。 D(x,y,?)?(G(x,y,k?)?G(x,y,?))*I(x,y)。 ?L(x,y,k?)?L(x,y,?)图像金字塔的建立：对于一幅图像I，建立其在不同尺度(scale)上的图像，也成为子八度（octave），这是为了仿射不变性，也就是在任何尺度都能够有对应的特征点，第一个子八度的尺度为原图大小，后面每个octave为上一个octave降采样的结果，即原图的1/4（长宽分别减半），构成下一个子八度（高一层金字塔）。 2) LoG近似DoG找到关键点（检测DOG尺度空间极值点） 使用Laplacian of Gaussian能够很好的找到图像中的兴趣点，但是需要大量的计算量，所以使用Difference of Gaussian图像的极大极小值近似寻找特征点。为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图所示， 8

中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。

在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，在每一组图像的顶层继续用高斯模糊生成3 幅图像，所以，高斯金字塔有每组S+3层图像，DOG金字塔每组有S+2层图像。 3) 除去不好的特征点

这一步本质上要去掉DoG局部曲率非常不对称的像素。通过拟和三维二次函数精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力，使用近似Harris角点检测器。

① 空间尺度函数泰勒展开式如下： ?DT1T?2DD(x)?D?x?xx， ?x2?x2对上式求导，并令其为0，得到精确的位置， ?2D?1?D???x。 2?x?x② 已经检测到的特征点中，要去掉低对比度的特征点和不稳定的边缘响应点。去除低对比度的点，即在DoG空间的极值点D(x)处取值，只取前两项可得： 1?DT?)?D??， D(xx2?x??0.03，该特征点就保留下来，否则丢弃。 若D(x)③ 边缘响应的去除 一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率通过一个2×2 的Hessian矩阵H求出： ?Dxx Dxy?H??? D D??xyyy??9

导数由采样点相邻差估计得到。D的主曲率和H的特征值成正比，令?为较大特征值，?为较小的特征值，则 Tr(H)?Dxx?Dyy????Det(H)?DxxDyy?(Dxy)???2， 令??r?，则 Tr(H)2(???)2(r???)2(r?1)2 ???Det(H)??r?2r (r?1)2r的值在两个特征值相等的时候最小，随着r的增大而增大，因此，为了检测主曲率是否在某域值?下，只需检测 Tr(H)2(??1)2， ?Det(H)?如果(???)???(r?1)2r，去除该特征点。在SIFT的经典文章中，取??10。 ④ 给特征点赋值一个128维方向参数 上一步中确定了每幅图中的特征点，为每个特征点计算一个方向，依照这个方向做进一步的计算， 利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。 m(x,y)?(L(x?1,y)?L(x?1,y))2?(L(x,y?1)?L(x,y?1))2?(x,y)?atan2(L(x,y?1)?L(x,y?1),L(x?1,y)?L(x?1,y)) 为(x,y)处梯度的模值和方向公式。其中L所用的尺度为每个关键点各自所在的尺度。至此，图像的关键点已经检测完毕，每个关键点有三个信息：位置，所处尺度、方向，由此可以确定一个SIFT特征区域。 在实际计算时，在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度方向直方图的范围是0～360度，其中每45度一个柱，总共8个柱。Lowe论文中还提到要使用高斯函数对直方图进行平滑，减少突变的影响。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向，其他的达到最大值80%的方向可作为辅助方向。该步中将建立所有尺度中特征点的描述子（128维）。通过对关键点周围图像区域分块，计算块内梯度直10

方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。

⑤ 关键点描述子的生成

首先将坐标轴旋转为关键点的方向，以确保旋转不变性。以关键点为中心取8×8的窗口。

Figure.16*16的图中其中1/4特征点梯度方向及幅值，右图为其加权到8个主方向后的效果。

图左部分的中央为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，利用公式求得每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，然后用高斯窗口对其进行加权运算。图中蓝色的圈代表高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如图右部分示。此图中一个关键点由2×2共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。

计算关键点周围的16*16的窗口中每一个像素的梯度，而且使用高斯下降函数降低远离中心的权重。

11

在每个4*4的1/16象限中，通过加权梯度值加到直方图8个方向区间中的一个，计算出一个梯度方向直方图。这样就可以对每个feature形成一个4*4*8=128维的描述子，将这个向量归一化之后，就进一步去除了光照的影响。

3、 颜色特征

颜色特征是在图像检索中应用最为广泛的视觉特征，主要原因在于颜色往往和图像中所包含的物体或场景十分相关。此外，与其他的视觉特征相比，颜色特征对图像本身的尺寸、方向、视角的依赖性较小，从而具有较高的鲁棒性。颜色特征最常用的表示方法就是颜色直方图，表示为：q?{qu}u?1,2,...,m，qu?C??[b(x)?u]，?是Kronecker

ii?1n函数，b(xi)表示像素xi所属的颜色区间。

计算颜色直方图需要将颜色空间划分成若干个小的颜色区间，每个小区间成为直方图的一个bin。这个过程称为颜色量化（color quantization）。然后，通过计算颜色落在每个小区间内的像素数量可以得到颜色直方图。而且在不同的情况下可以选择不同的颜色空间计算直方图，提高颜色特征的鲁棒性。在实际工程中，由于采集到的数据通常是YCbCr格式，而且亮度分量与颜色分量是分开的，所以，在后续的处理中应用YCbCr模型比较多。 四、 目标识别

目标识别是指一个特殊目标（或一种类型的目标）从其它目标（或其它类型的目标）中被区分出来的过程。它既包括两个非常相似目标的识别，也包括一种类型的目标同其他类型目标的识别。在机器视觉中，目标识别的过程一般都是根

12

据提取出的目标特征，通过训练好的分类器来得到目标所属的类别，从而达到识别的目的。前面已经介绍了几种常用的特征提取方法，当然还有其他的很多特征，比如Haar特征、Harris角点特征、简单的形态学特征等等。在分类器方面，使用比较多的有SVM、AdaBoost、随机森林等。

1、 SVM分类器

支持向量机（SVM）是一个由分类超平面定义的判别分类器。也就是说给定一组带标签的训练样本，算法将会输出一个最优超平面对新样本(测试样本)进行分类。一个线性判别函数是指由x的各个分量的线性组合而成的函数，

g(x)??Tx??0，?是超平面的法向量。对于两类问题的决策规则为：如果

g(x)?0，则判定x属于C1；如果g(x)?0，则判定x属于C2；如果g(x)?0，

则可以将x任意分到某一类或者拒绝判定。设xp是在判别面g(x)?0外的一点，可知，该点到判别面的距离为：

d??Txp??0?， 所以，g(xp)?r?, r=?d。判别函数g(x)正比于点x到超平面的代数距离(带正

g(x)?0；g(x)?0。 负号)。当点x在超平面的正侧时，当点x在超平面的负侧时，

对g(x)进行归一化，使所有样本都满足g(x)?1，即离判别面最近的样本满足g(x)?1，所以，分类间隔为2?。因此，要求分类间隔最大就是要求?i?0,1,...,n。最小，而要求分类面对所有样本正确分类，就要求yi(?Txi??0)?1?0，

求最优分类面问题可以转化为如下的约束优化问题： 12min?, yi(?Txi?b)?1?0, i?0,1,...,n， 2应用拉格朗日乘子法得到最优分类函数为： f(x)?sgn(??iyi(xiTx)??0)。 i一般来说，任意高次判别函数g(x)，都可以通过适当的变换，转化为线性判别函数处理，x?A(y)，所以最优分类函数变为：

f(x)?sgn(??iyiK(xi,x)??0)，

i13

K(?)为核函数，上式就是支持向量机。

2、 AdaBoost分类器

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。这里阐述下算法的具体过程：

1) 给定一个训练数据集T?{(x1,y1),(x2,y2),...,(xn,yn)}，yi属于标记集合{?1,1}。初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权重：

?1(i)?1。 N2) 进行多轮迭代，用m?1,2,...,M表示迭代次数。使用具有权值分布?m的训练数据集学习，得到基本分类器Gm(x)。 3) 计算Gm(x)在训练数据集上的分类误差率。

em???m(i)I(Gm(xi?yi))，

i?1NGm(x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和。 4) 计算Gm(x)的系数，?m表示Gm(x)在最终分类器中的重要程度。

?m?log121?em。 em5) 更新训练数据集的权值分布，用于下一轮迭代。

?m?1(i)??m(i)Zmexp(??myiGm(xi))， Zm是规范化因子。 6) 组合各个弱分类器。

得到最终分类器，

f(x)???mGm(x)，

m?1MG(x)?sgn(??mGm(x))。

m?1M14

3、 随机森林

随机森林指的是利用多棵树对样本进行训练并预测的一种分类器。简单来说，随机森林就是由多棵CART（Classification And Regression Tree）构成的。对于每棵树，它们使用的训练集是从总的训练集中有放回采样出来的，这意味着，总的训练集中的有些样本可能多次出现在一棵树的训练集中，也可能从未出现在一棵树的训练集中。在训练每棵树的节点时，使用的特征是从所有特征中按照一定比例随机地无放回的抽取的，根据Leo Breiman的建议，假设总的特征数量为M，这个比例可以是M，1M，2M。随机森林的训练过程可以总结如下： 2(1) 给定训练集S，测试集T，特征维数F。确定参数：使用到的CART的数量

t，每棵树的深度d，每个节点使用到的特征数量f。终止条件：节点上最少样本数s，节点上最少的信息增益m对于第1?t棵树，i?1?t。

(2) 从S中有放回的抽取大小和S一样的训练集S(i)，作为根节点的样本，从根节点开始训练。

(3) 如果当前节点上达到终止条件，则设置当前节点为叶子节点，如果是分类问题，该叶子节点的预测输出为当前节点样本集合中数量最多的那一类c(j)，概率

p为c(j)占当前样本集的比例；如果是回归问题，预测输出为当前节点样本集各

个样本值的平均值。然后继续训练其他节点。如果当前节点没有达到终止条件，则从F维特征中无放回的随机选取f维特征。利用这f维特征，寻找分类效果最好的一维特征k及其阈值th，当前节点上样本第k维特征小于th的样本被划分到左节点，其余的被划分到右节点。继续训练其他节点。

(4) 重复(2)(3)直到所有节点都训练过了或者被标记为叶子节点。 (5) 重复(2)，(3)，(4)直到所有CART都被训练过。 利用随机森林的预测过程如下： 对于第1?t棵树，i?1?t：

(1)从当前树的根节点开始，根据当前节点的阈值th，判断是进入左节点(?th)还是进入右节点(?th)，直到到达，某个叶子节点，并输出预测值。

(2)重复执行(1)直到所有t棵树都输出了预测值。如果是分类问题，则输出为所有

15

树中预测概率总和最大的那一个类，即对每个c(j)的p进行累计；如果是回归问题，则输出为所有树的输出的平均值。 五、 图像匹配

图像匹配是指通过一定的匹配算法在两幅或多幅图像之间查找同一目标或区域，主要可分为以图像像素值为基础的模板匹配和以特征为基础的匹配。 模板匹配是一种用于在源图像S中寻找定位给定目标图像T（即模板图像）的技术。其原理很简单，就是通过一些相似度准则来衡量两个图像块之间的相似度Similarity(S,T)，源图像和模板图像可以是二值图像、灰度图像、彩色图像。一般而言，模板匹配有两种使用场景：

1) 如果源图像S与模板图像T大小（高和宽）一致，则直接使用相似度计算公式对这两个图像进行相似度计算。

2) 如果源图像S的size大于模板图像T，则在S中匹配T时，需要滑动匹配窗口（即模板图像的大小），计算模板图像与该窗口对应的图像区域之间的相似度。对整张S图像滑动完后，得到多个匹配结果。这里，有两种方式获取匹配结果。一种是返回所有匹配结果中的最佳匹配结果（最小值或最大值，依相似度计算方式而定）。另一种，是设定一个阈值，大于或小于该阈值的匹配结果都认为是有效的匹配。

模板匹配中常用的相似度计算方法有： 1) 平方差 R(x,y)??(T(x?,y?)?I(x?x?,y?y?))2 x?,y?2) 互相关 R(x,y)??(T(x?,y?)?I(x?x?,y?y?)) x?,y?3) 相关系数 R??(x?x)(y?y)?(x?x)?(y?y)ii2ii2 4) 绝对差值 R(x,y)??T(x?,y?)?I(x?x?,y?y?) x?,y?以特征为基础的匹配就是根据从图像中提取出的有效特征向量来进行匹配，

16

一些常用的特征提取及描述方法已经在前面做了简单介绍，这里不再赘述。 六、 视觉跟踪

目标跟踪是绝大多数视觉系统中不可或缺的环节。在二维视频跟踪算法中，基于目标颜色信息或基于目标运动信息等方法是常用的跟踪方法，在特定的场景应用中（如视频监控等领域）主要有三种经典的跟踪算法：CamShift算法、光流跟踪以及粒子滤波算法。

1、 CamShift（Continuously Adaptive Mean Shift）跟踪算法

CamShift算法是一种基于均值漂移的算法。均值移动的理论基础是概率密度估计。均值移动的过程实际上就是在概率密度空间中寻找局部极大点。从其全称可知CamShift的算法基础实际上是MeanShift算法，均值移动的操作过程可用如下几步来表示：

(a) 计算以初始点x0为中心的某一核窗所对应的均值移动向量mG(x0)。 (b) 根据mG(x0)来移动核窗的中心位置，也即把mG(x0)中的加权平均值部

分赋予x0，把x0作为新的初始点，并转回步骤(a)； (c) 重复(a)、(b)过程，直到满足某一预定的条件。

因此，均值移动过程就是寻找数据分布最密集处的过程。均值移动的实现过程可图示为：

(1) 计算目标区域的均值、移动目标区域

(2) 重新计算目标区域均值，还存在移动向量，继续移动目标区域

17

(3) 移动向量越来越小

(4) 找到局部极大点，停止移动

以上过程只是一次MeanShift算法过程，在连续帧上使用MeanShift算法就是CamShift跟踪算法。CamShift同经典的均值移动跟踪算法的基本思想是相同的，所不同的它是建立在颜色概率分布图和矩的基础之上。CamShift对室内环境

18

下的目标跟踪具有较高的鲁棒性。 2、 光流跟踪算法

将三维空间中的目标和场景对应于二维图像平面运动时，他们在二维图像平面的投影就形成了运动，这种运动以图像平面亮度模式表现出来的流动就称为光流。光流法是对运动序列图像进行分析的一个重要方法，光流不仅包含图像中目标的运动信息，而且包含了三维物理结构的丰富信息，因此可用来确定目标的运动情况以及反映图像其它等信息。

光流是空间运动物体在观测成像面上的像素运动的瞬时速度。光流的研究是利用图像序列中的像素强度的时域变化和相关性来确定各自像素位置的“运动”，即研究图像灰度在时间上的变化与景象中物体结构及其运动的关系。一般情况下，光流由相机运动、场景中目标运动或两者的共同运动产生。

Lucas–Kanade光流算法是最常见，最流行的。它计算两帧在时间t到t??t之间每个像素点位置的移动。由于它是基于图像信号的泰勒级数，这种方法称为差分，这就是对于空间和时间坐标使用偏导数。

图像约束方程可以写为I(x,y,z,t)?I(x??x,y??y,z??z,t??t)，假设移动足够的小，那么对图像约束方程使用泰勒公式，我们可以得到：

I(x??x,y??y,z??z,t??t)?I(x,y,z,t)??I?I?I?I?x??y??z??t?H.OT.. ?x?y?z?tH.O.T.指更高阶，在移动足够小的情况下可以忽略。从这个方程中我们可以得到：

?I?I?I?I?x??y??z??t?0 ?x?y?z?t或者

?I?x?I?y?I?z?I?t????0 ?x?t?y?t?z?t?t?t可以得到：

?I?I?I?IVx?Vy?Vz??0 ?x?y?z?t?I?I?I，，,?x?z?yVx，Vy，Vz分别是I(x,y,z,t)的光流向量中x，y，z的组成。 19

和 ?I 则是图像在(x,y,z,t)这一点向相应方向的差分。所以 ?tIxVx?IyVy?IzVz??It， 写做：

??I?V??It

T这个方程有三个未知量，尚不能被解决，这也就是所谓光流算法的光圈问题。那么要找到光流向量则需要另一套解决的方案。而Lucas-Kanade算法是一个非迭代的算法：

假设流(Vx,Vy,Vz)在一个大小为m?m?m(m?1)的小窗口中是一个常数，那么从像素1,2,...,n，n?m3中可以得到下列一组方程：

Ix1Vx?Iy1Vy?Iz1Vz??It1

Ix2Vx?Iy2Vy?Iz2Vz??It2?IxnVx?IynVy?IznVz??Itn

三个未知数但是有多于三个的方程，这个方程组自然是个超定方程，也就是说方程组内有冗余，方程组可以表示为：

?Ix1 Iy1 Iz1???It1????Vx???I I I?I??x2y2z2t2??V???

y??? ? ? ??? ???????Vz???I?I I I??tn??xnynzn???记作：Av??b。为了解决这个超定问题，采用最小二乘法：

?ATAv?AT(?b) ?T?1Tv?(AA)A(?b)得到：

2?Vx???Ixi ?IxiIyi ?IxiIzi?????2V?II I II?yizi??y???xiyi?yi?V??II II I2??z???zi???xizi?yizi??1

???IxiIti????II??yiti? ???II???ziti??其中的求和是从1到n。也就是说寻找光流可以通过在四维上图像导数的分别累加得出。这个算法的不足在于它不能产生一个密度很高的流向量，优点在于对噪

20

声有一定的鲁棒性。 3、 粒子滤波跟踪算法

粒子滤波算法的核心思想是随机采样和重要性重采样。在不知道目标在哪里的情况下，随机向场景中分散粒子，撒完粒子后，根据特征相似度计算每个粒子的重要性，然后在重要的地方多撒粒子，不重要的地方少撒粒子。所以说粒子滤波较之蒙特卡洛滤波计算量较小。这种思想虽然简单，但效果往往很好。

粒子滤波实现对目标的跟踪通常分以下四个步骤： (1) 初始化阶段-提取跟踪目标特征

该阶段要人工指定跟踪目标，程序计算跟踪目标的特征，比如可以采用目标的颜色特征。这点和CamShift算法类似，不能实现自动初始化。但我们可以在初始时给定一个颜色样本，实现程序的半自动初始化。然后计算该区域色调(Hue)空间的直方图，即为目标的特征。直方图可以用一个向量来表示，所以目标特征就是一个N?1的向量V。

(2) 搜索阶段—分撒搜索粒子

获取目标特征后，在场景中分撒许多搜索粒子去搜索目标对象。粒子分撒有许多种方式。比如，a) 均匀分撒。即在整个图像平面均匀的撒粒子(uniform distribution)；b)在上一帧得到的目标附近按照高斯分布来放，可以理解成，靠近目标的地方多放，远离目标的地方少放。粒子放出去后按照初始化阶段得到的目标特征(色调直方图，向量V)计算它所处的位置处图像的颜色特征，得到一个色调直方图，向量Vi，计算该直方图与目标直方图的相似性（直方图匹配）。相似性有多种度量，最简单的一种是计算?Vi?V。每个粒子算出相似度后再做一次归一化，使得所有的粒子得到的相似度之和等于1。

(3) 决策阶段

分撒出去的每个粒子将返回其所处位置的图像信息。比如，一号粒子处图像与目标的相似度是0.3，二号粒子处图像与目标的相似度是0.02，三号粒子处图像与目标的相似度是0.0003，N号粒子处图像与目标的相似度是0.013，然后做加权平均。设N号粒子的图像像素坐标是(xn,yn)，它报告的相似度是?n，于是目标最可能的像素坐标X??(xn??n)，Y??(yn??n)。

21

(4) 重采样阶段

在新的一帧图像里，为了搜索到目标的新位置，需要再分撒粒子进行搜索。分撒粒子时要根据上一帧各个粒子返回的相似度报告。比如，一号粒子处图像与目标的相似度是0.3，二号粒子处图像与目标的相似度是0.02，三号粒子处图像与目标的相似度是0.0003，N号粒子处图像与目标的相似度是0.013。综合所有粒子的报告，一号粒子处的相似度最高，三号粒子处的相似度最低，于是要重新分撒粒子，在相似度最高的粒子那里放更多条粒子，在相似度最低的粒子那里少放粒子，甚至把原来那条粒子也撤回来。这就是重要性重采样(根据重要性重新分撒粒子)。

(2)->(3)->(4)->(2)如是反复循环，即完成了目标的动态跟踪。粒子滤波跟踪算法可用于视频监控领域，可以跟踪速度较快的跟踪目标。

除了前面所介绍的这些常用基本方法之外，还有很多方法，随着研究的不断深入，一些新兴的研究课题也不断涌现，比如，在机器学习方面出现的深度学习理论（deep learning），稀疏表达理论在跟踪中的运用，随机游走、图理论在图像分割中的使用，多模块交叉融合（识别与分割融合、分割与跟踪融合等）等等。

22

本文来源：https://www.bwwdw.com/article/dcs6.html