改进PCA-SIFT的电子标签图像匹配算法

于林飞,李云红,穆 兴,李传真

(西安工程大学 电子信息学院,陕西 西安 710048)

0 引 言

图像匹配是在特定的算法下将2幅或多幅图像识别特征点的过程。其发展迅速,在许多领域有着广泛的实际应用[1]。近些年,出现了许多图像匹配算法[2-7],而SIFT算法是非常经典、成熟的算法,可在图像中检测出关键点,同时也延伸出多种SIFT改进算法。张杨等[8]提出了基于改进PCA算法的人脸识别,通过ORL人脸的实验库得到运算耗时少于经典PCA算法;程德志等[9]提出了基于改进SIFT算法的图像匹配方法,使得图像匹配精度和匹配效率有所提高;何成伟等[10]提出了基于直方图均衡化的PCA-SIFT[11-12]图像特征提取与匹配改进算法,增强图像的明暗对比度,提高图像匹配效率;田健飞[13]提出了一种曲线拟合的柱面图像匹配算法,增加了剔除误匹配后靠近柱面图像边缘部分的匹配点数量,提高了柱面图像匹配的精度。虽然采用上述方法可以达到一定的效果,但无论使用什么图像匹配方法,在匹配过程中多少都会收到其他因素的干扰,图像匹配的结果就会产生一些错匹配,因此,在图像匹配技术中,为获得高精度的匹配效果,对匹配后的错匹配点进行有效地剔除就显得尤为重要。

目前对于误匹配点改进算法有很多,其中较为常用的算法是RANSAC[14],该算法在剔除错误匹配点时,使用的参数是随机的,主要由随机样本点组成,这样选出的模型参数就不能对更多的特征点信息做出有效的响应,虽然也能检测出误匹配点,但很难区分正确匹配点和错误匹配点[15]。

针对以上存在问题,本文提出了基于改进PCA-SIFT的电子标签图像匹配算法,通过SIFT算法获取图像关键特征点,结合PCA和K-means聚类结果,对剔除后的待匹配的图像集进行图像匹配。实验结果表明,基于PCA-SIFT算法比经典SIFT算法具有更好的匹配效果。

1 SIFT算法

SIFT算法是由Lowe提出并完善的图像特征点检测和描述算法。该算法在图像匹配中具有很好的优势,比如在图像平移、旋转和尺度变换等方面,且对噪声也能保持一定的稳定性,其主要流程是:尺度空间的构建、特征点的检测和描述、特征点的匹配。

1.1 获取图像数据

使用工业CCD传感器获取电子标签数据。如图1所示。

图 1 电子标签图像库

其中，图1(b)～(d)与模板不一致,图1(e)和(f)标签缺失(即空白)，图1(g)和(h)与模板一致。

1.2 SIFT特征点生成

高斯尺度核可以用原始图像与一个可变尺度二维高斯函数的卷积运算定义图像的尺度空间:

L(x,y,σ)=G(x,y,kσ)*I(x,y)

(1)

式中:G(x,y,kσ)为尺度可变高斯函数;I(x,y)为原始图像;k为尺度变化量。为保证检测到的特征点的稳定性,一般采用不同高斯差分核与图像卷积生成高斯差分空间:

(2)

对检测到的特征点,计算出邻域梯度直方图并确定其主方向。需要注意的是,一些特征点不仅具有主方向,而且具有辅方向,它对于后续匹配的稳定性非常重要。

1.3 PCA基本原理

PCA[16-17]是通过线性变换将原有的多个变量转化为少数几个新的综合变量的统计分析方法。PCA的目标是在降维之后尽可能多的保持原有的内在信息,并通过衡量在投影方向上的数据方差的大小来判断该方向的重要性。PCA数学原理如下:设n维向量w,表示低维映射空间的1个映射向量,经过最大化数据映射后可得方差公式为

(3)

定义W是由所有特征映射向量的列向量组成的矩阵,该矩阵可以较好地保留数据中的信息,该矩阵通过线性变换可以得到一个优化的目标函数,为

(4)

式中:tr是矩阵的迹;A是协方差矩阵。A表达式如下:

(5)

PCA 是输出, 可以用Y=W′X来表示, 最优的W是数据协方差矩阵前k个最大的特征值对应的特征向量作为列向量而组成,据此将X原始维度降低到了k维。

1.4 改进PCA-SIFT算法

在图像匹配中,为了便于和传统的SIFT算法作比对,改进算法中引入PCA先进行降维对图像二维表征,再根据聚类后的结果进行初步分类,最后采用RANSAC仿射变换实现图像的快速匹配。改进算法主要流程图如图2所示。

图 2 实验流程图

1)为了增强该算法过程的鲁棒性,将原来8张图像旋转和图像平移操作,得到24张图,增大图像集,并对得到图像集后的所有的图像进行特征提取,得到图像的特征点的高维特征向量。其中1、4、7、10、13、16、19、22图为原始的8张图,分别对应图1(a)～(h)。因为通过降维表征可以更加容易观察出高维特征向量的分布特性,同时大的数据集可以使得PCA的降维矩阵更具有鲁棒性,所以对所有提取的高维特征向量,整体进行PCA降维,得到最佳的降维矩阵和降维后的特征向量。此外,在得到整体分布后,结合最优降维矩阵,进一步观察标记的图像在特征空间的分布特性,同时为了实现图像区分的量化方法,本文提出了基于K均值聚类算法的量化处理方法。

2) K-means聚类算法[18-21]是一种聚类分析算法,通过数学迭代运算,其步骤是随机选取k个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。轮廓系数,是聚类效果好坏的一种评价方式。最早由Peter J.Rousseeuw在1986提出。它结合内聚度和分离度2种因素。可以用来在相同原始数据的基础上用来评价不同算法、或者算法不同运行方式对聚类结果所产生的影响。轮廓系数的值是介于 [-1,1],越趋近于1代表内聚度和分离度都相对较优。

为了寻求较优的聚类数,本文对于从2到20的聚类个数进行聚类分析,根据每次聚类的结果,计算出所有样品点的轮廓系数S,并取均值，得到图3的散点图。考虑到聚类数不应该过大或者过小,所以对散点图进行高斯拟合。可以看出,降维后的特征点呈现出聚类的特性,由图3发现,聚类数为2、3、4时,具有较大的平均轮廓系数。分析高斯拟合得到的结果,高斯函数的对称轴在x=2.7,接近3。

图 3 聚类散点图与高斯函数拟合曲线

为了更直观地观察点分布的聚类中心,计算得到的24张图的各自的聚类中心并表征在同一个坐标下,如图4所示。

图 4 24张图的聚类中心表征

图4中的图例的表征为8×3的排列结构,每一行代表着一张原始及其变化后的图。通过图4可以发现,图例的第5行和第6行所代表的点(13～16图),显著偏移其他点,尤其是第一聚类区间和第二聚类区间。相对于其他聚类中心,偏X轴负向、Y轴正向,印证了上述对于1图和13图的聚类分析结果。

3) 为了区分标签是否丢失,计算类间距(欧氏距离)的加权和,通过距离阈值进行了类的划分。即将有标签的图对应的聚类中心作为基准点的重心,计算得到3个参考点,分别计算24个聚类在各个聚类区间下离参考点的距离,并对3个区间的距离进行求和得到的欧氏距离进行量化分析,如图5所示。

图 5 24张图在特征空间的欧氏距离

通过图5可得,(13～18图)的欧氏距离显著高于其他图。为了获得合适的分类阈值和高可信度,本文采取的算法是取无标签的最小值和有标签的最大值的均值。计算得到,其阈值取0.165 4。

在获得分类阈值后,可以对具有或不具有标签的图片进行分类,之后进行图片配准的计算,得到图片的相似度(匹配点的百分比的曲线)。再将标签缺失的图进行计算,如图6所示。

图 6 24张图的相似度表征

图6中1～3和19～24为与标准图片吻合的正确图片,13～18为缺失的图片,4～12为其他标签。从标签中剔除缺失的图像,并计算其余图像的相似性,如图7所示。

图 7 分类后的24张图的相似度表征

通过相似度可以进一步进行分类,可以实现相似图片和不相似图片的分类,为了获得合适的分类阈值且具有较高的可信度,本文采用的算法为:取模板图及其变换图的相似度的最小值和非模板图的相似度的最大值的均值。计算得到,其相似度阈值取0.4。此过程在有无标签图片的基础上,进一步实现了相似图片和不相似图片的分类。

4) 使用RANSAC,获取仿射变换矩阵,利用几何变换查找物体进行配准。

2 结果与分析

实验硬件环境为Intel CORE i7,内存为8 G,操作系统为64位的PC机。仿真实验环境是Windows10下的Matlab2019(a)软件,实验所采用的电子标签图像为工业CCD相机采集。

除了实现图片的2次分类,剔除了绝大多数的无关图片外,本文提出的算法仍然可以在最终匹配上提高速度。为了表征该算法与现有主流算法的计算速度的差异,本文在最终图像匹配的计算速度上,将改进的PCA-SIFT算法与传统的SIFT匹配进行对比实验分析,改进的PCA-SIFT算法首先通过SIFT获取图像关键特征点后进行PCA降维,实现对电子标签的量化辨别,进而剔除无标签和和不相似图片,在这里,设定匹配阈值为0.165 4,实现标签分类后,又进行相似度分类,设定匹配阈值为0.4,获取出相似图片,再进行RANSAC仿射变换,进行图像的配准。本文不失一般性,认为当匹配点与真实点的欧几里得距离小于5个像素时,认为匹配正确,即当匹配点与真实点的欧几里得距离大于5个像素时,认为匹配错误。传统的SIFT算法是没有进行PCA分类,直接进行图像的配准。

改进的PCA-SIFT算法在进行图像匹配时,将旋转平移的3张图,与原始图进行匹配,计算匹配率。此时,匹配率是相同物体不同照片的特征点匹配的计算,特征点的匹配关系是事先知道的,是一一对应的关系。通过计算图像的特征点及其特征向量,并计算出特征点与特征点的对应关系,并与实际的对应关系相比较,计算出与实际相匹配的百分比。将这2种算法匹配率进行比较,如图8所示。

图 8 2种算法匹配率对比

图9为2种算法耗时结果对比图。表1和表2分别为改进PCA-SIFT算法与传统SIFT算法的匹配率和相对耗时时间。

通过图8和表1发现,当加入PCA分析时,匹配率提高平均约6%,证明该算法能够提高图像的匹配率。通过图9和表2得到,该过程的实现比传统SIFT算法在运算速度上提升了约0.1 s,在处理速度上比原先算法平均大约提升了2倍,如样品2实验,经典SIFT算法耗时约0.19 s,而改进算法只需不到0.04 s,其他同组实验与该结论一致。证明改进过的算法在处理速度上有明显的改善。

图 9 2种算法耗时结果对比

表 1 经典SIFT算法与改进算法的匹配率

表 2 经典SITFT算法与改进算法相对耗时

3 结 语

针对SIFT算法在图像匹配中匹配率不高的问题,提出了改进PCA-SIFT的电子标签图像匹配算法。由于电子标签的数量有限,将原有8张图进行旋转和平移操作扩充了图库数据,将同一幅图的旋转变换图与原始图进行匹配。本实验在SIFT获取图像特征关键点后,进行PCA降维和聚类,实现了对无效图像的分类和剔除,再通过相似性匹配,获取相似图像,比经典SIFT算法在图像匹配时,快速剔除了标签缺失或者相似度不高的图像,有效提高了图像的匹配速度和匹配率。实验结果发现,改进PCA-SIFT算法比经典SIFT算法在图像匹配精度上平均提高了6%,耗时时间上平均节省了约0.1 s,比经典SIFT算法在处理速度上提高了2倍以上。经过大量实验数据结果验证了改进PCA-SIFT算法对电子标签快速匹配的有效性。但是,该研究只进行了改进算法和经典SIFT算法的对比,在其他算法下的效果对比存在不足,以及在背景复杂情况下仍存在检测效果不佳等问题,这些问题将是今后研究的重点。