王卓崢，賈克斌

(北京工業(yè)大學(xué)電子信息與控制工程學(xué)院，北京100124)

圖像配準(Image registration)是對取自不同空間、不同傳感器或不同視覺的同一場景的兩幅或多幅圖像進行匹配、疊加的過程。特征提取與特征匹配是圖像配準的重要步驟，也是機器視覺領(lǐng)域基于內(nèi)容的圖像/視頻檢索技術(shù)的核心，可廣泛應(yīng)用于超分辨率圖像重建(Super－resolution Image Reconstruction)、全景視頻拼接(Panoramic Video Mosaics)、即 時 定 位 與 地 圖 構(gòu) 建(Simultaneous Localization And Mapping，SLAM)、目標識別(Object Recognition)等方面。Harris角點檢測算法［1－2］是目前較成熟的特征提取算法，但該算法對圖像的尺度變化非常敏感，不適合匹配不同尺寸下的圖像［3］。尺度不變特征變換(Scale Invariant Feature Transform，SIFT)是 David［4］于2004年在總結(jié)不變量技術(shù)的特征檢測方法基礎(chǔ)上，提出的一種基于尺度空間、對圖像縮放、旋轉(zhuǎn)甚至仿射變換等保持不變的特征匹配算法。該算法描述圖像的局部特征，獨特性好，信息量豐富，適用于海量特征數(shù)據(jù)庫中進行快速、準確的匹配。近幾年，Mikolajczy等［5］對 SIFT、矩不變量、Steerable filter等10種描述子進行了實驗和性能評價，實驗表明:當(dāng)照明、仿射、模糊等變換程度較大時，基于SIFT算子的相關(guān)方法最穩(wěn)定、性能最佳。

為增強算法的抗噪聲能力和精確度，SIFT算法采用128維特征描述子，當(dāng)在圖像特征點較多的情況下進行匹配實驗時，存在存儲空間大、匹配耗時多等缺點。近幾年提出的利用主元分析法(Principal Component Analysis，PCA)對多維特征向量進行降維的算法可有效提高運算效率。

但PCA算法也有很大的局限性:當(dāng)采樣數(shù)據(jù)與真實數(shù)據(jù)存在較小誤差時，即使含誤差的采樣點較多，PCA仍具有較強的精確度;但當(dāng)采樣數(shù)據(jù)被破壞遠離真實數(shù)據(jù)時，即使被破壞的采樣點數(shù)量極少，PCA算法亦將失去有效性。

因此，當(dāng)傳感器獲得的數(shù)據(jù)由于受到硬件或外部條件影響，產(chǎn)生元素丟失的情況時，PCASIFT并不能較好地實現(xiàn)受損圖像的配準。針對以上問題，本文首先利用矩陣填充技術(shù)恢復(fù)原圖像丟失的元素;然后采用主元分析法(Principal Component Analysis，PCA)對多維特征向量進行降維處理，以提高運算效率;最后采用高斯加權(quán)歐式距離代替歐式距離進行特征點的匹配。實驗結(jié)果驗證了算法的有效性。

1 矩陣填充

1.1 矩陣填充概述

矩陣填充技術(shù)是壓縮感知領(lǐng)域的重要理論，它主要解決在僅觀察到一個矩陣的某一小部分數(shù)據(jù)時，填充那些未知或者缺失的數(shù)據(jù)。近幾年，矩陣填充理論取得了較大的發(fā)展。2006年，Emmanuel等［6］證明了在RIP條件下，0范數(shù)優(yōu)化問題與1范數(shù)優(yōu)化問題具有相同的解。2009年，Emmanuel等［7］將矩陣精確填充轉(zhuǎn)為凸優(yōu)化問題，將矩陣的核范數(shù)近似為矩陣的秩。

如前所述，PCA雖然起到了有效降維并保留主要能量的作用，但對錯誤極為敏感。例如圖1 (a)中，多個點組成一維子空間數(shù)據(jù)，黑色直線為含有低值高斯噪聲的采樣信號，灰色短線為PCA結(jié)果，如圖1(a)可見PCA的結(jié)果與真實數(shù)據(jù)非常接近;圖1(b)，只有4個采樣點被破壞而遠離真實數(shù)據(jù)，結(jié)果與真實數(shù)據(jù)差距較大。

圖1 PCA有效性對比圖Fig.1 Comparison of efficiency of PCA

針對以上問題，2010年，文獻［8］對比了現(xiàn)今主流的矩陣填充與 RPCA(Robust Principal Component Analysis)算法，提出了非精確增廣拉格朗日乘子法 (Inexact Augmented Lagrange Multiplier，IALM)。

假設(shè)一低秩矩陣A∈∑m×n的觀測矩陣(采樣矩陣)為D∈∑m×n，則

式中:PΩ(·)為矩陣的采樣投影算子;E表示稀疏矩陣，包括混合噪聲與錯誤。矩陣填充的目標就是從矩陣D中恢復(fù)低秩矩陣A，轉(zhuǎn)化為凸優(yōu)化問題為

式中:‖·‖表示為矩陣的核范數(shù)，在文獻［6］中已驗證，當(dāng)A的秩r滿足r?min(m，n)，采樣數(shù)目m滿足m≥Cn5/4r log n，且E非零并在一定有限范圍內(nèi)時，矩陣可精確恢復(fù)。其中n為矩陣維數(shù)，C為某個常數(shù)。

1.2 增廣拉格朗日乘子法恢復(fù)矩陣丟失元素

對應(yīng)的增廣拉格朗日乘子為

式中:‖·‖F(xiàn)表示矩陣的Frobenius范數(shù);μ為正數(shù);Δ(A，B)為矩陣AT·B的跡函數(shù)。算法的具體步驟為:

算法1 采用IALM進行矩陣填充

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

(2)while not converged do;

(8)k=k+1;

(9)end while;

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

受損圖像通過矩陣填充恢復(fù)了丟失的元素后，通過特征提取獲得多維的特征向量描述圖像中的特征點，主要步驟如下。

2.1 尺度空間極值點檢測

式中:G(x，y，σ)為高斯卷積核，是實現(xiàn)尺度變換的唯一線性核［4］。

然后使用高斯差分 (Difference－of－Gaussian，DoG)函數(shù)與圖像進行卷積，計算尺度空間極值點，可有效地檢測在尺度空間中穩(wěn)定的關(guān)鍵點位置。相鄰兩個尺度的差分值由常數(shù)計算卷積函數(shù)乘以因子k［9］。

為了有效地檢測出DoG函數(shù)中尺度空間的極值，需要在高斯差分圖像序列中，對比當(dāng)前像素與3×3鄰域的當(dāng)前尺度和相鄰尺度共26個像素點的最大和最小值，以確保尺度空間和二維圖像空間都檢測到該極值點。

2.2 精確定位極值點

由于DoG算子會產(chǎn)生較強的邊緣響應(yīng)，為了提高特征匹配的精度和抗噪能力，通過擬和尺度空間的三維二次函數(shù)，即根據(jù)當(dāng)?shù)氐牟蓸狱c確定最大插補位置的泰勒展開式去除低對比度的關(guān)鍵點，同時通過檢查主曲率的比例去除不穩(wěn)定的邊緣響應(yīng)點，實現(xiàn)精確確定關(guān)鍵點的位置和尺度(亞像素)的目的［10］。

2.3 關(guān)鍵點方向分配

精確定位極值點后，為使特征描述算子具備旋轉(zhuǎn)不變性，利用關(guān)鍵點鄰域像素的梯度方向分布特性為每個關(guān)鍵點指定方向參數(shù)，通過建立梯度直方圖分配關(guān)鍵點的主方向和輔方向。為了增強算法的魯棒性，關(guān)鍵點會被賦予一個主方向和多個輔方向。

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

極值點經(jīng)檢測并被精確定位后，分配了關(guān)鍵點的主方向與輔方向，為了使特征點保持豐富的信息量，及對光照、視角變化的不變性，需要計算特征描述子(descriptors)。標準的SIFT算法采用128維特征向量來描述每個關(guān)鍵點，但豐富的圖像信息會獲得更多的特征點，隨之帶來算法復(fù)雜度的升高，導(dǎo)致存儲空間加大，匹配時間過長。針對以上問題，本文采用一種PCA－SIFT特征描述子，使用更少維數(shù)的特征向量描述一個特征點，從而提高算法匹配效率，且可獲得更高精確度。

主元分析又稱主分量分析。是一種將多個相關(guān)的變量轉(zhuǎn)化為少數(shù)幾個獨立變量的有效分析方法，通過減少通道間的依賴性而達到減少數(shù)據(jù)的通道或子帶的目的。

2.4.1 計算PCA－SIFT投影矩陣

PCA－SIFT描述符與標準SIFT描述符具有亞像素位置、尺度和主方向，但在特征描述符生成時有所不同。首先計算投影矩陣步驟如下。

(2)求R的特征值λ1，λ2，…，λm，按從大到小的順序?qū)ζ渑判颍⑶蟮孟鄳?yīng)的單位特征向量。

(3)選擇前k個特征向量，構(gòu)成k×3042投影矩陣并存儲，記為∏。

2.4.2 生成低維特征描述子

得到投影矩陣后，在待配準圖像的關(guān)鍵點中心取41×41的窗口，旋轉(zhuǎn)到它的主方向，并分別計算垂直和水平梯度，構(gòu)成 i維矢量 αi(i= 3042)。用預(yù)先計算好的投影矩陣∏與此矢量相乘，最終生成k維PCA－SIFT描述子βk，即

式中:0＜k＜3042，為描述特征向量的維數(shù)，可根據(jù)需要選取適合的值實現(xiàn)降維，本文取k=20。

3 特征匹配

傳統(tǒng)的特征匹配算法，使用歐氏距離進行特征匹配，歐氏距離值越小，說明這兩個點越相似，它們的匹配程度就越高。然而，對于一幅突出目標物體的圖像，根據(jù)人眼的視覺特性，拍照者所關(guān)心的信息從圖像的中心點向圖像的邊緣逐漸衰減呈正態(tài)分布，即相鄰像素隨著距離中心點像素越來越遠，其權(quán)重也越來越小，用戶所關(guān)心的信息也越來越少，因此本文引入高斯權(quán)重值，計算高斯加權(quán)歐氏距離。

式中:pi和pj分別為待匹配的特征向量;a＞0為高斯核的標準差。定義權(quán)重函數(shù)如下:

遍歷每個特征點，找出其與待配準圖像中歐式距離最近的前兩個關(guān)鍵點，在這兩個關(guān)鍵點中，如果最近的距離除以次近的距離小于某個比例閾值γ，即

則接受這一對匹配點，特征點匹配成功。若降低這個比例閾值，特征匹配點數(shù)會減少，但匹配結(jié)果會更加穩(wěn)定。

使用高斯加權(quán)歐氏距離進行閾值的判定可有效抑制用戶無用信息所帶來的數(shù)據(jù)冗余。

4 實驗結(jié)果與性能分析

實驗環(huán)境為CPU奔騰雙核2.4 GHz，內(nèi)存4.0 GByte，顯存為 512 MByte，操作系統(tǒng)為Windows VisaTMHome Premium，仿真平臺為Matlab2011a(版本號7.12.0.635)。

4.1 矩陣填充性能對比

本文首先對當(dāng)前矩陣填充的主流算法進行了對比，如表1所示。他們分別是:SVT(Singular Value Thresholding)、APG(Accelerated Proximal Gradient)和本文算法IALM。本文并未對EALM (Exact Augmented Lagrange Multiplier)進行討論，由于IALM相比EALM只更新A和E各一次得到子問題的近似解，足以使算法最終收斂到原問題的最優(yōu)解，因此IALM更簡潔收斂速度更快。其中 n為矩陣維數(shù);r為矩陣的秩;NMSE (Normalized Mean Squared Error)為歸一化均方誤差，根據(jù)式(1)定義為

式中:觀測矩陣D(n×n)的采樣率定義為(p/dr)6，即低秩矩陣A中大約60%的數(shù)據(jù)生成D。從結(jié)果可得出結(jié)論:在相同條件下，IALM具有更少的迭代次數(shù)和時間，同時產(chǎn)生更小的歸一化均方誤差，恢復(fù)出的矩陣更接近原始矩陣。

表1 矩陣填充性能對比表Table 1 Comparison ofmatrix completion algorithms

為了驗證IALM算法的有效性，選取一幅時鐘左聚焦圖像，隨機產(chǎn)生100幅30%的像素灰度值為零的受損圖像(見圖2(a))，組成觀測矩陣I^，經(jīng)過IALM矩陣填充后的恢復(fù)圖像如圖2(b)所示。

圖2 矩陣填充恢復(fù)受損圖像Fig.2 Recovery of corrupted image by matrix comp letion

4.2 特征提取與匹配性能對比

表2顯示了五組數(shù)字，每分別對應(yīng)測試圖像庫(來源:http://decsai.ugr.es/cvg/dbimagenes/)中大小為512×512像素的lena、baboon、peppers、toucan、grnpeace圖像。每組數(shù)字進行了兩項指標的對比:提取特征點數(shù)量的對比和提取過程中所需時間的對比。通過數(shù)據(jù)不難看出，本文算法提取的特征點比采用標準的SIFT算法降低19.6%～42.1%，對特征點豐富的圖像，效果尤為明顯;而檢測時間縮短24.1%～40.4%。結(jié)果表明，本文算法可有效降低算法復(fù)雜度，減少數(shù)據(jù)冗余，縮短匹配時間。

表2 特征提取點數(shù)與時間對比Table 2 Comparison of feature points and processing time

在信號檢測理論中，Recall－Precision曲線和接 收 者 操 作 特 征 (Receiver Operating Characteristic，ROC)曲線是最常用的兩種性能評價指標，有時兩種指標可以互換。本文采用Recall－Precision曲線，定義recall和1－precision分別為:

式中:NF為應(yīng)匹配的特征點數(shù)量;NA為實驗匹配的所有特征點數(shù)量，包括正確的和錯誤的;NA為實驗匹配的正確的特征點數(shù)量。

為驗證算法可有效處理圖像間發(fā)生平移、旋轉(zhuǎn)、仿射變換、視角變換、光照變換情況下的圖像配準，本文選取了Harris角點檢測法、標準SIFT算法、PCA－SIFT－12算法(12維PCA－SIFT特征描述子)和本文算法(20維PCA－SIFT特征描述子和高斯加權(quán)歐氏距離實現(xiàn)特征匹配，記為:PCA－GAUSSIANSIFT)對1 000幅、四大類圖片分別在增加噪聲、旋轉(zhuǎn)與尺度變化、仿射變換、光照變化四個場景中進行對比，如圖3所示。其中圖3(a)對圖片組增加高斯噪聲(σ=0.05)，根據(jù)Recall－Precision曲線，參與對比的四種方法均擁有較好的曲線形態(tài)，其中本文算法性能最優(yōu);圖3(b)對圖片組中的圖片先后旋轉(zhuǎn)45°，尺度縮放50%，其中Harris角點檢測法由于對圖像的尺度變化非常敏感，性能最差;圖3(c)對圖片組進行仿射變換(仿射扭曲30°)，結(jié)論與圖3(a)、(b)相同;圖3(d)對圖片組進行光照變化(亮度降低50%)，四個算法除了Harris角點檢測法，recall值都在95%以上，性能接近。

此外，PCA－GAUSSIAN－SIFT與PCA－SIFT－12算法的降維均在41×41的鄰域從3042維特征向量PCA降維，而非從標準SIFT算法的128維數(shù)據(jù)進行降維，因此PCA－SIFT－12的性能要優(yōu)于SIFT。

圖3 主流圖像配準算法性能對比Fig.3 Performance comparison of image register algorithms

5 結(jié)束語

實驗結(jié)果表明，本文算法可針對受損圖像進行圖像匹配，對噪聲、旋轉(zhuǎn)與尺度變換、仿射變換及光照具有較好的魯棒性，算法匹配能力較強，具有較好的穩(wěn)定性、準確率和匹配速度，可有效應(yīng)用在基于內(nèi)容的圖像與視頻檢索等信號處理領(lǐng)域。

［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.