矩陣填充與主元分析在受損圖像配準(zhǔn)中的應(yīng)用

王卓崢，賈克斌

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

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

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

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

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

1 矩陣填充

1.1 矩陣填充概述

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

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

圖1 PCA有效性對(duì)比圖Fig.1 Comparison of efficiency of PCA

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

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

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

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

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

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

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

算法1 采用IALM進(jìn)行矩陣填充

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

(2)while not converged do;

(8)k=k+1;

(9)end while;

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

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

2.1 尺度空間極值點(diǎn)檢測(cè)

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

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

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

2.2 精確定位極值點(diǎn)

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

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

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

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

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

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

2.4.1 計(jì)算PCA－SIFT投影矩陣

PCA－SIFT描述符與標(biāo)準(zhǔn)SIFT描述符具有亞像素位置、尺度和主方向，但在特征描述符生成時(shí)有所不同。首先計(jì)算投影矩陣步驟如下。

(2)求R的特征值λ1，λ2，…，λm，按從大到小的順序?qū)ζ渑判?，并求得相?yīng)的單位特征向量。

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

2.4.2 生成低維特征描述子

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

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

3 特征匹配

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與性能分析

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

4.1 矩陣填充性能對(duì)比

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

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

表1 矩陣填充性能對(duì)比表Table 1 Comparison ofmatrix completion algorithms

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

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

4.2 特征提取與匹配性能對(duì)比

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

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

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

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

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

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

圖3 主流圖像配準(zhǔn)算法性能對(duì)比Fig.3 Performance comparison of image register algorithms

5 結(jié)束語(yǔ)

實(shí)驗(yàn)結(jié)果表明，本文算法可針對(duì)受損圖像進(jìn)行圖像匹配，對(duì)噪聲、旋轉(zhuǎn)與尺度變換、仿射變換及光照具有較好的魯棒性，算法匹配能力較強(qiáng)，具有較好的穩(wěn)定性、準(zhǔn)確率和匹配速度，可有效應(yīng)用在基于內(nèi)容的圖像與視頻檢索等信號(hào)處理領(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］.信號(hào)處理，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.