随机蕨丛算法匹配识别性能研究

李海涛　朱大明　杨琪莉

摘要：为了改进基于特征点的图像匹配识别方法的精确度，文章对特征点匹配算法随机蕨丛的性能进行评估，并与尺度不变特征变换算法SIFT的匹配性能进行对比研究。通过实验将随机蕨丛算法参数进行优化配置，分别测试两种算法的鲁棒性能和匹配速度。实验结果表明，随机蕨丛算法的匹配精度能达到85%左右，明显高于SIFT算法，匹配速度也远快于SIFT算法，但仍然有待提高。

Abstract： In order to improve the accuracy of the image matching recognition method on the basic of feature points， this paper evaluates the random ferns performance of the feature matching algorithm and compares it with the matching performance of SIFT with scale invariant feature transform algorithm. Through the experiment， the optimized configuration of the parameters of random ferns algorithm is carried out， the robust performance and matching speed of the two algorithms are tested. The experimental results show that the matching accuracy of random ferns algorithm can reach 85%， it is significantly higher than SIFT algorithm， the matching speed of it is far faster than SIFT algorithm， but it remains to be improved.

关键词：图像匹配；片元识别；半朴素贝叶斯方法；蕨结构；分类

Key words： image matching；fragment identification；semi-naive bayesian approach；fern structure；classification

中图分类号：TP391.4 文献标识码：A 文章编号：1006-4311（2016）05-0221-03

0 引言

图像匹配技术被广泛应用于目标识别和图像姿态估计领域[1]。基于特征点的图像识别匹配方法主要分为两大类，一类是通过计算图像的局部描述子，该描述子在透视变化和光照变化的情况下能保持不变。主要有SIFT描述子[2]。另一类方法依赖于统计学的学习技术，通过对图像片元的所有可能出现的情况进行建模，利用该模型进行匹配识别。主要算法有结合PCA和多高斯模型[3]。

上述方法都具有一定的局限性，SIFT描述子通过对图像进行高斯卷积，差分近似以及梯度计算，保证其尺度，光照和透视不变性，具有较好的匹配效果，但也产生了较大的时间代价，算法实时性较差。PCA和多高斯模型方法对于透视变形的图像将匹配失败，应用范围比较局限。随机蕨丛算法将匹配过程分为在线和离线阶段，保证其匹配实时性，在训练阶段对每个特征点出现的变形情况进行了充分的训练，保证其匹配正确率。

1 随机蕨丛算法

隨机蕨丛算法[4，5]是Lepetit等在随机森林算法基础上发展来的，将传统的匹配问题转换为分类问题。随机蕨丛算法在每个蕨类节点包含一个随机二元测试，利用该二元测试将训练样本的片元空间进行剖分来实现图像的识别。每个类别的训练样本是该类别关键点所有可能出现的图像片元的集合，结合每个随机蕨包含的二元测试结果以及半朴素贝叶斯理论[6]训练得到关于该类别的概率分布，并用该分布对测试图像进行分类。

1.1 半朴素贝叶斯

随机蕨丛分类是利用半朴素贝叶斯理论对测试图像的特征点片元估计其最可能的类别的过程。类别集合为C={c1，c2…ci}，i=1，2，…，H，二元测试集合为F={f1，f2…fj}，j=1，2，…，N。对于片元P的类别ci可公式化为：

贝叶斯公式展开为：

先验概率P（C）与类别C之间是相互独立的，所以式（1）可化简为：

每一个二元测试fj的值只依赖于图像片元I中两个像素点的位置dj，1和dj，2的强度值，即：若I（dj，1）< I（dj，2）则fj值为1，反之为0。

需要对每个二元测试进行大概N次的比较才能保证分类精度，考虑到二元测试之间的相关性以及算法的灵活性，通过将二元测试集分成M组，每组包含S个测试，S=N /M。每一个组就是一个蕨类，计算每一个蕨类的二元测试的联合分布概率为：

其中Fk={fσ （k，1）， fσ （k，2），…， fσ （k，S）}，k=1，…，M，表示第k个蕨类，σ（k，S）表示从1到N的一个随机序列函数。

利用半朴素贝叶斯的方法对二元测试集中的部分相关性进行建模。使得原本需要计算2N次降到了M×2S次。通过对蕨类的数量M以及蕨类的大小S进行调整，可使得算法在性能以及内存开销方面更灵活控制。

1.2 随机蕨丛训练

算法训练阶段需要对目标图像提取关键点集。关键点集是通过对目标图像多次变形，变形图像可通过对目标图像进行仿射变换得到。对每一个变形目标图像利用关键点描述子提取关键点，并跟踪每一个关键点，被发现次数最多的点集就是稳定的关键点集。每一个关键点对应一个类别。随机蕨丛算法通过计算图像的Harris角点提取关键点。

随机蕨丛训练过程要对公式（4）中的类别条件概率P（Fm|C=ci）进行估计，每个蕨类的大小为S，即有S个二元测试组成，将产生K=2S个值，k =1，2，…，K，设pk，ci为每个蕨类叶子结点处类别为ci测试结果为k的概率。

对于参数pk，ci最简单的估计方法是利用最大似然估计，令Nk，ci表示在值为k的蕨类节点处类别为ci的样本集出现的次数，Nci表示类别ci总的样本数量。这两个参数可对每个蕨类进行独立估计。则pk，ci即为Nk，ci与Nci的比值。

由于每个样本的数量是有限的，所以有时候将不会有类别为ci的样本出现在值为k的蕨类节点处，使得Nk，ci和pk，ci会很小甚至等于0，从而影响分类结果。为解决这个问题，采用：

Nr是正则化项，是统一的二元测试的值的Dirichlet先验值[7]，算法设置为Nr=1。如果一个类别ci没有在某个特定的蕨类值k里出现，那么参数pk，ci也不会为0，影响概率估计，防止了过拟合产生的分类不正确问题。

1.3 随机蕨丛算法

随机蕨丛算法思想是，每个蕨类包含一个二元测试的集合，离线训练阶段对已知类别的片元进行学习，得到每个类别相对于每个蕨类的类别概率分布，在线匹配阶段利用半朴素贝叶斯方法对每个蕨类的类别概率分布进行联合计算，得出分类结果，并利用法RANSAC剔除误分类，从而判断出两个图像是否匹配。步骤如下：

①输入目标图像，并提取关键点，生成关键点片元；

②生成包含随机二元测试集的随机蕨丛，并将步骤①的关键点片元投入随机蕨丛，生成随机蕨丛分类器。离线训练完成；

③输入测试图像，并提取关键点，生成关键点片元；

④将测试图像关键点片元投入随机蕨丛分类器，利用RANSAC方法剔除误分类，输出分类结果。

2 实验分析

为了验证随机蕨丛算法在图像匹配方面的性能，实验采用书封面以及人脸作为目标图像，分别有不同的纹理和结构。测试图像为电脑摄像头录制视屏序列，分辨率为640480。

2.1 参数估计

在1.1节讨论了，影响随机蕨丛算法性能的参数有蕨类大小S以及数量M。通过实验来优化S，M两个参数可提升算法识别率。图1，图2列出了蕨类数量M和蕨类大小S与算法识别率的关系图，由图可看出当蕨类数量大于30 以及蕨类大小大于13时，算法识别率增长变缓，识别率在83%左右。对算法内存需求预计训练时间的考虑，蕨类数量为30-50，蕨类大小为12-20较为适宜。算法采用S=13，M=30。

2.2 算法性能

本文从算法匹配正確率和算法运行时间两方面对随机蕨丛算法进行性能评估，利用书封面以及人脸两组实验数据进行测试，并将实验结果与SIFT算法进行比较。图3列出了两种算法对于书封面的匹配示意图，图中白色圈表示算法匹配正确的点。在发生旋转，尺度变化以及部分遮挡的情况下随机蕨丛算法都能有效匹配。

利用随机蕨丛算法对书封面进行匹配，并将匹配结果SIFT算法进行比较。随机蕨丛算法识别率平均在85%，SIFT算法识别率平均在83%。在识别率方面随机蕨丛算法要稍优于SIFT算法。在匹配时间方面，随机蕨丛算法由于涉及到计算尺度空间并计算HARRIS特征点增加了其匹配时间，平均每帧匹配时间在1400ms，要优于进行高斯卷积，差分近似和主方向计算的SIFT算法（4000ms/f）。

3 结论

实验结果表明随机蕨丛算法在识别率方面要优于SIFT算法，能达到85%左右的识别率；并在匹配时间上也要优于SIFT算法，能有效对目标图像进行识别，可应用与图像匹配以及图像片元识别等领域。但该算法实时性有待提高，后续可引入能快速检测的特征点在不影响识别率的前提下，增强算法实时性。

参考文献：

[1]余萍，袁辉，赵振兵，等.图像识别中的兴趣点匹配方法研究[J].计算机工程与应用，2010，46（3）：132-135.

[2]石跃祥，蔡自兴，王学武.基于改进的PCA算法和Fisher线性判别的人脸识别技术[J].小型微型计算机系统，2006，27（9）：1731-1736.

[3]程克非，张聪.基于特征加权的朴素贝叶斯分类器[J].计算机仿真，2006，23（10）：92-94.