矩陣填充與主元分析在受損圖像配準中的應用

王卓崢，賈克斌

(北京工業大學電子信息與控制工程學院，北京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.