矩阵填充与主元分析在受损图像配准中的应用

王卓峥，贾克斌

(北京工业大学电子信息与控制工程学院，北京100124)

图像配准(Image registration)是对取自不同空间、不同传感器或不同视觉的同一场景的两幅或多幅图像进行匹配、叠加的过程。特征提取与特征匹配是图像配准的重要步骤，也是机器视觉领域基于内容的图像/视频检索技术的核心，可广泛应用于超分辨率图像重建(Super－resolution Image Reconstruction)、全景视频拼接(Panoramic Video Mosaics)、即 时 定 位 与 地 图 构 建(Simultaneous Localization And Mapping，SLAM)、目标识别(Object Recognition)等方面。Harris角点检测算法［1－2］是目前较成熟的特征提取算法，但该算法对图像的尺度变化非常敏感，不适合匹配不同尺寸下的图像［3］。尺度不变特征变换(Scale Invariant Feature Transform，SIFT)是 David［4］于2004年在总结不变量技术的特征检测方法基础上，提出的一种基于尺度空间、对图像缩放、旋转甚至仿射变换等保持不变的特征匹配算法。该算法描述图像的局部特征，独特性好，信息量丰富，适用于海量特征数据库中进行快速、准确的匹配。近几年，Mikolajczy等［5］对 SIFT、矩不变量、Steerable filter等10种描述子进行了实验和性能评价，实验表明:当照明、仿射、模糊等变换程度较大时，基于SIFT算子的相关方法最稳定、性能最佳。

为增强算法的抗噪声能力和精确度，SIFT算法采用128维特征描述子，当在图像特征点较多的情况下进行匹配实验时，存在存储空间大、匹配耗时多等缺点。近几年提出的利用主元分析法(Principal Component Analysis，PCA)对多维特征向量进行降维的算法可有效提高运算效率。

但PCA算法也有很大的局限性:当采样数据与真实数据存在较小误差时，即使含误差的采样点较多，PCA仍具有较强的精确度;但当采样数据被破坏远离真实数据时，即使被破坏的采样点数量极少，PCA算法亦将失去有效性。

因此，当传感器获得的数据由于受到硬件或外部条件影响，产生元素丢失的情况时，PCASIFT并不能较好地实现受损图像的配准。针对以上问题，本文首先利用矩阵填充技术恢复原图像丢失的元素;然后采用主元分析法(Principal Component Analysis，PCA)对多维特征向量进行降维处理，以提高运算效率;最后采用高斯加权欧式距离代替欧式距离进行特征点的匹配。实验结果验证了算法的有效性。

1 矩阵填充

1.1 矩阵填充概述

矩阵填充技术是压缩感知领域的重要理论，它主要解决在仅观察到一个矩阵的某一小部分数据时，填充那些未知或者缺失的数据。近几年，矩阵填充理论取得了较大的发展。2006年，Emmanuel等［6］证明了在RIP条件下，0范数优化问题与1范数优化问题具有相同的解。2009年，Emmanuel等［7］将矩阵精确填充转为凸优化问题，将矩阵的核范数近似为矩阵的秩。

如前所述，PCA虽然起到了有效降维并保留主要能量的作用，但对错误极为敏感。例如图1 (a)中，多个点组成一维子空间数据，黑色直线为含有低值高斯噪声的采样信号，灰色短线为PCA结果，如图1(a)可见PCA的结果与真实数据非常接近;图1(b)，只有4个采样点被破坏而远离真实数据，结果与真实数据差距较大。

图1 PCA有效性对比图Fig.1 Comparison of efficiency of PCA

针对以上问题，2010年，文献［8］对比了现今主流的矩阵填充与 RPCA(Robust Principal Component Analysis)算法，提出了非精确增广拉格朗日乘子法 (Inexact Augmented Lagrange Multiplier，IALM)。

假设一低秩矩阵A∈∑m×n的观测矩阵(采样矩阵)为D∈∑m×n，则

式中:PΩ(·)为矩阵的采样投影算子;E表示稀疏矩阵，包括混合噪声与错误。矩阵填充的目标就是从矩阵D中恢复低秩矩阵A，转化为凸优化问题为

式中:‖·‖表示为矩阵的核范数，在文献［6］中已验证，当A的秩r满足r≪min(m，n)，采样数目m满足m≥Cn5/4r log n，且E非零并在一定有限范围内时，矩阵可精确恢复。其中n为矩阵维数，C为某个常数。

1.2 增广拉格朗日乘子法恢复矩阵丢失元素

对应的增广拉格朗日乘子为

式中:‖·‖F表示矩阵的Frobenius范数;μ为正数;Δ(A，B)为矩阵AT·B的迹函数。算法的具体步骤为:

算法1 采用IALM进行矩阵填充

(1)初始化Y(0)，λ，μ(0);

(2)while not converged do;

(8)k=k+1;

(9)end while;

2 基于主元分析的SIFT特征提取

受损图像通过矩阵填充恢复了丢失的元素后，通过特征提取获得多维的特征向量描述图像中的特征点，主要步骤如下。

2.1 尺度空间极值点检测

式中:G(x，y，σ)为高斯卷积核，是实现尺度变换的唯一线性核［4］。

然后使用高斯差分 (Difference－of－Gaussian，DoG)函数与图像进行卷积，计算尺度空间极值点，可有效地检测在尺度空间中稳定的关键点位置。相邻两个尺度的差分值由常数计算卷积函数乘以因子k［9］。

为了有效地检测出DoG函数中尺度空间的极值，需要在高斯差分图像序列中，对比当前像素与3×3邻域的当前尺度和相邻尺度共26个像素点的最大和最小值，以确保尺度空间和二维图像空间都检测到该极值点。

2.2 精确定位极值点

由于DoG算子会产生较强的边缘响应，为了提高特征匹配的精度和抗噪能力，通过拟和尺度空间的三维二次函数，即根据当地的采样点确定最大插补位置的泰勒展开式去除低对比度的关键点，同时通过检查主曲率的比例去除不稳定的边缘响应点，实现精确确定关键点的位置和尺度(亚像素)的目的［10］。

2.3 关键点方向分配

精确定位极值点后，为使特征描述算子具备旋转不变性，利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，通过建立梯度直方图分配关键点的主方向和辅方向。为了增强算法的鲁棒性，关键点会被赋予一个主方向和多个辅方向。

2.4 PCA-SIFT特征描述子的建立

极值点经检测并被精确定位后，分配了关键点的主方向与辅方向，为了使特征点保持丰富的信息量，及对光照、视角变化的不变性，需要计算特征描述子(descriptors)。标准的SIFT算法采用128维特征向量来描述每个关键点，但丰富的图像信息会获得更多的特征点，随之带来算法复杂度的升高，导致存储空间加大，匹配时间过长。针对以上问题，本文采用一种PCA－SIFT特征描述子，使用更少维数的特征向量描述一个特征点，从而提高算法匹配效率，且可获得更高精确度。

主元分析又称主分量分析。是一种将多个相关的变量转化为少数几个独立变量的有效分析方法，通过减少通道间的依赖性而达到减少数据的通道或子带的目的。

2.4.1 计算PCA－SIFT投影矩阵

PCA－SIFT描述符与标准SIFT描述符具有亚像素位置、尺度和主方向，但在特征描述符生成时有所不同。首先计算投影矩阵步骤如下。

(2)求R的特征值λ1，λ2，…，λm，按从大到小的顺序对其排序，并求得相应的单位特征向量。

(3)选择前k个特征向量，构成k×3042投影矩阵并存储，记为∏。

2.4.2 生成低维特征描述子

得到投影矩阵后，在待配准图像的关键点中心取41×41的窗口，旋转到它的主方向，并分别计算垂直和水平梯度，构成 i维矢量 αi(i= 3042)。用预先计算好的投影矩阵∏与此矢量相乘，最终生成k维PCA－SIFT描述子βk，即

式中:0＜k＜3042，为描述特征向量的维数，可根据需要选取适合的值实现降维，本文取k=20。

3 特征匹配

传统的特征匹配算法，使用欧氏距离进行特征匹配，欧氏距离值越小，说明这两个点越相似，它们的匹配程度就越高。然而，对于一幅突出目标物体的图像，根据人眼的视觉特性，拍照者所关心的信息从图像的中心点向图像的边缘逐渐衰减呈正态分布，即相邻像素随着距离中心点像素越来越远，其权重也越来越小，用户所关心的信息也越来越少，因此本文引入高斯权重值，计算高斯加权欧氏距离。

式中:pi和pj分别为待匹配的特征向量;a＞0为高斯核的标准差。定义权重函数如下:

遍历每个特征点，找出其与待配准图像中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离小于某个比例阈值γ，即

则接受这一对匹配点，特征点匹配成功。若降低这个比例阈值，特征匹配点数会减少，但匹配结果会更加稳定。

使用高斯加权欧氏距离进行阈值的判定可有效抑制用户无用信息所带来的数据冗余。

4 实验结果与性能分析

实验环境为CPU奔腾双核2.4 GHz，内存4.0 GByte，显存为 512 MByte，操作系统为Windows VisaTMHome Premium，仿真平台为Matlab2011a(版本号7.12.0.635)。

4.1 矩阵填充性能对比

本文首先对当前矩阵填充的主流算法进行了对比，如表1所示。他们分别是:SVT(Singular Value Thresholding)、APG(Accelerated Proximal Gradient)和本文算法IALM。本文并未对EALM (Exact Augmented Lagrange Multiplier)进行讨论，由于IALM相比EALM只更新A和E各一次得到子问题的近似解，足以使算法最终收敛到原问题的最优解，因此IALM更简洁收敛速度更快。其中 n为矩阵维数;r为矩阵的秩;NMSE (Normalized Mean Squared Error)为归一化均方误差，根据式(1)定义为

式中:观测矩阵D(n×n)的采样率定义为(p/dr)6，即低秩矩阵A中大约60%的数据生成D。从结果可得出结论:在相同条件下，IALM具有更少的迭代次数和时间，同时产生更小的归一化均方误差，恢复出的矩阵更接近原始矩阵。

表1 矩阵填充性能对比表Table 1 Comparison ofmatrix completion algorithms

为了验证IALM算法的有效性，选取一幅时钟左聚焦图像，随机产生100幅30%的像素灰度值为零的受损图像(见图2(a))，组成观测矩阵I^，经过IALM矩阵填充后的恢复图像如图2(b)所示。

图2 矩阵填充恢复受损图像Fig.2 Recovery of corrupted image by matrix comp letion

4.2 特征提取与匹配性能对比

表2显示了五组数字，每分别对应测试图像库(来源:http://decsai.ugr.es/cvg/dbimagenes/)中大小为512×512像素的lena、baboon、peppers、toucan、grnpeace图像。每组数字进行了两项指标的对比:提取特征点数量的对比和提取过程中所需时间的对比。通过数据不难看出，本文算法提取的特征点比采用标准的SIFT算法降低19.6%～42.1%，对特征点丰富的图像，效果尤为明显;而检测时间缩短24.1%～40.4%。结果表明，本文算法可有效降低算法复杂度，减少数据冗余，缩短匹配时间。

表2 特征提取点数与时间对比Table 2 Comparison of feature points and processing time

在信号检测理论中，Recall－Precision曲线和接 收 者 操 作 特 征 (Receiver Operating Characteristic，ROC)曲线是最常用的两种性能评价指标，有时两种指标可以互换。本文采用Recall－Precision曲线，定义recall和1－precision分别为:

式中:NF为应匹配的特征点数量;NA为实验匹配的所有特征点数量，包括正确的和错误的;NA为实验匹配的正确的特征点数量。

为验证算法可有效处理图像间发生平移、旋转、仿射变换、视角变换、光照变换情况下的图像配准，本文选取了Harris角点检测法、标准SIFT算法、PCA－SIFT－12算法(12维PCA－SIFT特征描述子)和本文算法(20维PCA－SIFT特征描述子和高斯加权欧氏距离实现特征匹配，记为:PCA－GAUSSIANSIFT)对1 000幅、四大类图片分别在增加噪声、旋转与尺度变化、仿射变换、光照变化四个场景中进行对比，如图3所示。其中图3(a)对图片组增加高斯噪声(σ=0.05)，根据Recall－Precision曲线，参与对比的四种方法均拥有较好的曲线形态，其中本文算法性能最优;图3(b)对图片组中的图片先后旋转45°，尺度缩放50%，其中Harris角点检测法由于对图像的尺度变化非常敏感，性能最差;图3(c)对图片组进行仿射变换(仿射扭曲30°)，结论与图3(a)、(b)相同;图3(d)对图片组进行光照变化(亮度降低50%)，四个算法除了Harris角点检测法，recall值都在95%以上，性能接近。

此外，PCA－GAUSSIAN－SIFT与PCA－SIFT－12算法的降维均在41×41的邻域从3042维特征向量PCA降维，而非从标准SIFT算法的128维数据进行降维，因此PCA－SIFT－12的性能要优于SIFT。

图3 主流图像配准算法性能对比Fig.3 Performance comparison of image register algorithms

5 结束语

实验结果表明，本文算法可针对受损图像进行图像匹配，对噪声、旋转与尺度变换、仿射变换及光照具有较好的鲁棒性，算法匹配能力较强，具有较好的稳定性、准确率和匹配速度，可有效应用在基于内容的图像与视频检索等信号处理领域。

［1］Shum H Y，Szeliski R.Panoramic image mosaics［R］. MSR－TR－97－23.Microsoft Research，1997.

［2］Faille F.A fastmethod to improve the stability of interest point detection under illumination changes［C］//Singapore:ICIP，2004:2673－2676.

［3］Sunil Arya，David M Mount，Nathan SNetanyahu，et al.An optimal algorithm for approximate nearestneighbor searching fixed dimensions［J］.Journal of the ACM，1998，45 (6):891－923.

［4］David G Lowe.Distinctive image features from scale－invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91－110.

［5］Mikolajczyk K，Schmid C.A performance evaluation of local descriptors［J］.IEEETrans Pattern Analysis and Machine Intelligence，2005，27(10):1615－1630.

［6］Emmanuel Candes，Terence Tao.The Dantzig selector:Statistical estimation when p ismuch larger than n［J］.Annals of Statistics，2007，35(6):2392－2404.

［7］Emmanuel JCandès，Benjamin Recht.Exact matrix completion via convex optimization［J］.Foundations of Computational Mathematics，2009，9(6):717－772.

［8］Lin Zhou－chen，Chen Min－ming，Ma Yi.The augmented lagrangemultiplier method for exact recovery of corrupted low－rank matrices［R］.University of Illinois，2009.

［9］David G Lowe.Object recognition m local scale－invariant features［C］//Proc of the 7th IEEE International Conference on Computer Vision.Kerkyra，Greece，1999，2:1150－1157.

［10］王鹏，王平，沈振康，等.一种基于SIFT的仿射不变特征提取新方法［J］.信号处理，2011，27(1):88－93.

Wang Peng，Wang Ping，Shen Zhen－kang，et al.A novel algorithm for affine invatiant feature extraction based on SIFT［J］.Journal of Signal Processing，2011，27(1): 88－93.