Random Ferns随机蕨算法.docx

2随机蕨算法近年来，图像模式识别算法不断涌现，大多分为四步：(1)提取稳定的局部特征；(2)对特征进行不变性描述；(3)特征匹配；(4)基于外极几何约束，求得两图像间的对应关系。比较经典的有Harris仿射不变性特征(Harris-affine)、尺度不变性特征变换(SIFT)、快速稳健性特征(SURF)和最稳定极值区域(MSER)等。这些算法为获取特征的各种不变性，运算量较大，难以满足实时性，MSER虽然能够满足实时性，但对图像模糊和尺度差异的稳健性较差。在成像环境较复杂且对运算量要求严格的图像模式识别领域，上述图像模式识别算法均不适用。为降低运算量，Lepetit等把物体识别视为分类问题，将运算量较大的部分转移到分类器训练过程中，构造了一种名为随机蕨(Random ferns)的非层次结构特征，基于朴素贝叶斯分类算法对局部图像进行快速识别。目前该方法已被用于增强现实和同时定位与地图创建等方面。2.1朴素贝叶斯分类器朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。通俗来说，就好比你在街上看到一个黑人，猜这个人从哪里来的，你十有八九猜是非洲人。为什么呢？因为黑人中非洲人的比率最高，当然人家也可能是美洲人或亚洲人，但在没有其它可用信息下，我们会选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。2.1.1朴素贝叶斯分类的工作过程整个朴素贝叶斯分类分为三个阶段：第一阶段准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备，主要工作是根据具体情况确定特征属性，并对每个特征属性进行适当划分，然后由人工对一部分待分类项进行分类，形成训练样本集合。这一阶段的输入是所有待分类数据，输出是特征属性和训练样本。这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段，其质量对整个过程将有重要影响，分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。第二阶段分类器训练阶段，这个阶段的任务就是生成分类器，主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计，并将结果记录。其输入是特征属性和训练样本，输出是分类器。这一阶段是机械性阶段，根据前面讨论的公式可以由程序自动计算完成。第三阶段应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。这一阶段也是机械性阶段，由程序完成。2.1.2半朴素贝叶斯分类模型为了突破朴素贝叶斯分类器的独立性假设条件的限制，除了一些比较基本的方法之外，还可以通过改变其结构假设的方式来达到目的，为此有人提出了半朴素贝叶斯分类(SNBGSemi-NaiveBayesianclassifier)的构想。半朴素贝叶斯分类模型对朴素贝叶斯分类模型的结构进行了扩展，其目的是为了突破朴素贝叶斯分类模型特征属性间独立性假设限制，提高分类性能。目前半朴素贝叶斯分类模型学习的关键是如何有效组合特片属性。条件互信息度量半朴素贝叶斯分类学习算法可以解决目前一些学习算法中存在的效率不高及部分组合意义不大的问题。SNBC的结构比NBC紧凑，在SNBC的模型构建过程中，依照一定的标准将关联程度较大的基本属性（即NBC中的特征属性）合并在一起构成“组合属性”（也称之为“大属性”）。逻辑上，SNBC中的组合属性与NBC中的基本属性没有根本性差别，SNBC的各个组合属性之间也是相对于类别属性相互独立的。图2是SNBC的模型示意图。这类模型通过将依赖性强的基本属性结合在一起构建新的模型，这样可以部分屏蔽NBC中独立性假设对分类的负面作用。但从名称可以看出，SNBC依然属于朴素贝叶斯分类的范畴。这是因为除了结构上的差别之外，计算推导过程与NBC无异。2.2图像金字塔图像金字塔是以多分辨率来解释图像的一种结构。1987年，在一种全新而有效的信号处理与分析方法，即多分辨率理论中，小波首次作为分析基础出现了。多分辨率理论将多种学科的技术有效地统一在一起，如信号处理的子带编码、数字语音识别的积分镜像过滤以及金字塔图像处理。正如其名字所表达的，多分辨率理论与多种分辨率下的信号（或图像）表示和分析有关。其优势很明显，某种分辨率下无法发现的特性在另一种分辨率下将很容易被发现。图像金字塔是结合降采样操作和平滑操作的一种图像表示方式。它的一个很大的好处是，自下而上每一层的像素数都不断减少，这会大大减少计算量；而缺点是自下而上金字塔的量化变得越来越粗糙，而且速度很快。高斯金字塔里有两个概念：组(Octave)和层(Level或Interval)，每组里有若干层。高斯金字塔的构造是这样的，第一组的第一层为原图像，然后将图像做一次高斯平滑（高斯卷积、高斯模糊），高斯平滑里有一个参数，然后将乘一个比例系数k作为新的平滑因子来平滑第一组第二层得到第三层。这样重复若干次，得到L层他们分别对应的平滑参数为：0,k,k2,。然后将最后一幅图像做比例因此为2的降采样得到第二组的第一层，然后对第二组的第一层做参数是的高斯平滑，对第二层做k的平滑得到第三层，以此类推。每组对应的平滑因子是一样的，这样反复形成了O组L层，组建成高斯金字塔。2.3图像小块的识别思想在众多物体识别方法中，基于图像小块(patch)的方法得到研究者们的青睐。简单来说，它在训练图片中选取一些小块作为单位，在小块上进行一些图像的基本操作，得到描述小块的特征；然后存储这些特征以供识别时使用。以机器学习的术语来说，它是典型的基于实例的学习，训练过程很短，甚至几乎等同于简单存储；而识别过程相对花时相对较长。然而相比更为复杂的基于物体部分进行识别的方法，这些时间还是相当短的。基于图像小块(patch)的方法有以下几点优势。首先。它对于图像的表示比较干净灵活，且抗各种变换(不仅仅是仿射变换，还有各种变形变换)能力强。选取小块的动作本身就能达到抗平移变换的效果，在小块上做适当的特征提取(如提取直方图)更能够抵抗小变形；相比之下旋转变换的解决更难一些，然而这可以通过存储多个不同朝向的小块来解决。其次，应用这种方法，在识别前不需要做分割(segmentation)或者其它任何预先的对于图像的语义解释，如边界抽取以获得不间断的闭合曲线边界。众所周知图像分割是著名的难解问题，边界抽取若没有适当的先验知识也是非常困难的；物体识别如果基于这些并不成熟方法的结果，则显然会进一步降低性能。不如直接使用patch进行识别来的高效。再次小块方法不需要对数据做统计推断，不仅速度快，稳定性好，而且没有陷入局部极小值的危险。与小块方法相联的机器学习算法往往相当简单，如K近邻，如SVM；相比之下基于部分的方法则更多地依赖于物体结构上的全局约束以解决局部的二义性问题，因此需要大量无法得到精确解的统计推断过程及相应复杂的近似算法。不幸的是在大部分情况下这种推断既费时，又不讨好，得到的往往不是最优解。最后，从实用的角度上看，小块方法不仅实现简单方便，原理清晰易懂，而且其综合性能也是最优秀的。具体来说，这个算法准备了一些滤波器，在图像的patch上抽取滤波响应的直方图得到直方图特征；然后使用此特征计算两两照片之间的相似度，做成SVM的核并用直方图特征进行训练得到的。2.4算法思想在本章节将针对随机蕨的算法思想进行简要描述，以达到更加准确地理解该算法并应用它的目的。设基准图像中的特征点数为H，将以特征点k为中心的局部区域patchk所有可能的视图情况均归为一类，将各特征区域所属的类用Ci(i=1,.,H)表示。则可将查找实时图像中特征点kinput在基准图像上的对应特征点视为对patchkinput的分类问题。设fj(j=1,.,N)为基于patchkinput的二元特征集，则patchkinput的所属类别为：式中C为表示类的随机变量，由贝叶斯公式可得设先验概率P(C)为均匀分布，（3-2)式分母部分与类别无关，则(3-1)式可简化为设patchkinput的尺寸为L*L,(取L=32)，则二元特征fj的值取决于patchkinput中在分类器训练时随机生成的两像素位置dj1和dj2的灰度大小Idj1和Idj2比较的结果，即由于fj的形式很简单，因此需要有足够多的特征以确保实现正确分类，取N300，即随机选取300对像素位置进行灰度大小比较，则对(3-3)式中联合分布概率的完整表达形式的求解需要的存储量为H*2N字节。为降低存储量，并保证fj之间具有足够的相关性，将fj分为M组，每组包含S=N/M个二元特征，并假设不同组的二元特征之间相互独立，组内二元特征之间具有相关性，将这些组定义为蕨特征(Ferns)，则(3-3)式中的条件概率可以近似为式中表示第m个蕨，), (m,j)表示范围是1，.，N的随机函数。则patchkinput的所属类别为要对(3-6)式进行求解，只需估计每个蕨Fm和类Ci的类条件概率P(Fm|C=Ci)。与(3-3)式相比，(3-6)式的存储量为M*2S字节，取M=40，s=11，在保证算法具有较高性能的同时，每一类只需8*104字节的存储量，远小于N=440时2N字节的运算量，有利于工程实现。2.5分类器的训练2.5.1建立训练集为使分类器对图像投影变形、光照变化、图像模糊以及噪声具有较强的稳健性，需构造能反映上述变形的训练集对分类器进行训练。当摄像头距离目标较远时，目标上的局部区域可被视为平面，则通过对当前视角下的目标图像进行仿射变换能够模拟目标在其他视角条件下的情况，设仿射变换矩阵为A，可被分解为如下形式:式中R和R是两个角度参数分别为和的旋转矩阵，S=diag1, 2为尺度矩阵。分别在-,+范围内随机选取和,在0.6,1.5范围内随机选取1和 2即可构造出随机的仿射变换矩阵Arand，设基准图像为Io，则与Io具有随机的图像尺度、旋转角和3D视角差异的图像Irand为为提高算法对光照变化的稳健性，随机改变训练图像Irand的平均灰度，以模拟不同光照条件下的图像，将改变平均灰度后的图像记作式scaleI。为提高算法对噪声和图像模糊的稳健性，对Iscale添加均值为0，方差为25的高斯白噪声，得到加噪图像Inoise，然后对加噪图像Inoise进行随机的高斯平滑，最终求得训练图像Itrain，并将由上述不同随机参数生成的训练图像所构成的集合记作Btrain，这个集合Btrain内的训练样本数为10000，即随机生成的训练图像数为10000。2.5.2提取关键点要使分类器足够稳定，必须提取在较大程度投影变形、光照变化、图像模糊以及噪声存在情况下仍然稳定存在的特征点。利用加速分割测试特征(FAST)方法对基准图像Io进行特征点提取，设提取到的某特征点为k，则k应在上述干扰存在的情况下仍然具有较高的被检测概率P(k)。设对Io采用建立训练集中的方法得到的新视角模拟图像为Ii，由(3-8)式可得利用FAST方法对图像Ii进行特征点提取，设k为在Ii中求得的某特征点，根据Arand对其做逆仿射变换，可求得该特征点在基准图像Io中对应的特征点k的位置:因此，随机产生Ntotal幅模拟图像，通过对是否在当前模拟图像Ii中提取到了某特征点k所对应的特征点k进行计数，即可求得特征点k的被检测概率为式中Ndetected为在Ntotal幅模拟图像中成功提取到与特征点k所对应的特征点k的总图像数。令Ntotal=3105，取被检测概率P(k)最高的400个特征点作为分类器的初始类进行训练，则在算法思想中，各特征区域所属的类Ci(i=1,.,H)即对应于分类器的初始类，H=400。2.5.3训练在求得训练集合Btrain和分类器初始类Ci之后，在L*L范围内(取L=32)，按照均匀分布随机选取M*S(M=40,S=11)对像素dj1和dj2的位置。对每个类Ci,将