基于列約束的低秩矩陣恢復方法

裘國永+張力

摘 要：由于在成像過程中出現遮擋現象，圖像矩陣的元素有缺失。在正投影相機模型下，提出一種基于列約束的低秩矩陣恢復方法。該方法利用圖像矩陣是一個低秩矩陣從而圖像序列具有冗余性的特性，利用奇異值分解由圖像矩陣的列空間構造出一個投影矩陣，得到圖像矩陣的列所滿足的約束條件，將缺失元素的恢復轉化為迭代求解二次型的極值問題，利用它恢復出圖像矩陣的缺失元素。該方法從理論上能夠保證收斂到全局最小值。仿真實驗表明，此方法具有收斂速度快，恢復精度高等優點。

關鍵詞：遮擋點；低秩矩陣；奇異值分解；列約束

中圖分類號：TP391 文獻標志碼：A

Low-rank Matrix Recovery Method Based on Column Metric Constraints

QIU Guo-yong，ZHANG Li

（School of Computer Science，Shaanxi Normal University，Xian，Shaanxi 710119，China）

Abstract：To recover the position of occlusion，the image matrix has some missing elements because of occluding in the imaging process.An low-rank matrix recovery method based on column metric constraints under orthographic projection is presented.Utilizing the property that the image matrix is of low rank and the redundancy that exists in an image sequence，a projective matrix is constructed via singular value decomposition to get the image matrixs column metric constraints.The method iteratively solves the minimum of a quadratic function to recover the missing elements of the image matrix.The method can guarantee to converge to the global optimal solution theoretically.The simulated experiments show that the proposed method has the advantages of fast convergence speed and small error.

Key words：occlusion；low-rank matrix；singular value decomposition；column metric constraints

1 引 言

特征點跟蹤是計算機視覺研究領域中三維重建、運動分析等深度研究的前提和基礎[1]。由于在攝像機成像過程中視場改變、遮擋出現、光照變化等諸多原因，在特征點的跟蹤過程中，必然會導致部分特征點跟蹤丟失，從而圖像矩陣的相應位置沒有值。如何恢復這些缺失的矩陣元素，是計算機視覺的熱門研究問題之一[2-3]。

由于圖像矩陣構造的特殊性，圖像矩陣在沒有任何誤差的情形下是一個秩不超過3的低秩矩陣[4]，這也表明圖像序列具有冗余性，且圖像矩陣的列向量組是線性相關的，列空間可以用不同的列向量部分組生成。利用圖像矩陣的低秩性，有的學者利用子矩陣法對低秩矩陣進行恢復[4-5]，但是該方法的結果和所選擇的子矩陣有關。為了克服該方法的缺點，不少研究人員利用圖像矩陣可以分解為兩個矩陣相乘的特性，其中一個表示相機的旋轉，一個表示目標物的形狀，交替固定一個求另外一個，進行循環迭代求解[6-9]。但是該類方法適用于遮擋率比較低的情形，當遮擋率較高時，算法就無法收斂。同時，也有研究人員通過重投影誤差構造出目標函數，采用非線性優化

方法進行迭代求解[10-11]，但由于該目標函數是一個非凸函數，導致若初始值遠離真實解時，不能求到全局最優解。為了解決這個問題，在假設相機為針孔模型下，Martinec等利用三線性約束來求解遮擋點的真實位置[12]，但該方法的缺點是要求三線性約束關系，而在求三線性約束關系過程中，不能把所有的圖像平等看待，因此必然導致誤差較大。

為了克服上述缺點，本文提出了一種基于列約束的低秩矩陣恢復方法，利用圖像矩陣是一個低秩矩陣從而圖像序列具有冗余性，通過奇異值分解由圖像矩陣的列空間構造出一個投影矩陣，由此投影矩陣得到圖像矩陣的列所滿足的約束條件，根據這些約束條件將遮擋點的求解轉化為迭代求解一個半正定二次型的極值問題，利用它恢復出圖像矩陣的缺失元素。由于半正定二次型對應優化問題的目標函數是凸的、一步就可以求解出函數的極值等，因此本文方法具有良好的數值求解特性。本文方法從理論上證明了算法的收斂性。為了驗證方法的有效性，本文進行了仿真實驗，與Martinec方法進行了對比，結果表明，本文算法具有收斂速度快，恢復精度高等優點。

2 相機模型和圖像矩陣

為了表示圖像矩陣，首先需要確定相機模型。在最常用的針孔模型中，對應的透視投影是非線性的，導致計算量大且在透視效果不明顯時表現出病態性，即對躁聲敏感。在某些實際情形，比如攝像機的視場小，且目標物體與攝像機有一定的距離，則可以用線性相機模型—正投影相機模型近似代替針孔相機模型，這樣不僅可以簡化公式的表示而且能減少計算量。因此本文取相機模型為正投影模型。endprint

設給定的圖像序列中有f幅二維圖像及s個三維空間特征點，則有

mi，j=Rixj（1）

式中mi，j=ui，jvi，jT表示二維圖像點，xj=xjyjzjT表示三維空間點，Pi為相機的投影矩陣，i和j分別表示第i幅圖像和第j個圖像點。

為了得到圖像矩陣，現按分塊矩陣的方法將所有特征點的圖像坐標合并成一個2f×s圖像矩陣，每幅圖像對應的投影矩陣也合并成一個2f×3矩陣。則由式（1）可得到

M2f×s=R2f×3S3×s （2）

式中M2f×s=u1，1u1，2…u1，sv1，1v1，2…v1，suf，1uf，2…uf，svf，1vf，2…vf，s2f×s，R2f×3=R1R2Rf2f×3，S3×s=x1x2…xs。

由此可見，圖像矩陣可以表示成兩個矩陣相乘，其中一個與相機的旋轉有關，另一個與目標物的形狀有關。

由于R只有3列，S只有3行，所以根據線性數相關結論得到圖像矩陣M2f×s的秩為3。且M的列向量組和R的列向量組張成的是R2f的同一個三維子空間。

3 基于列約束的低秩矩陣恢復方法

由于圖像矩陣M2f×s的秩為3，所以它的列空間是R2f的三維子空間。因此先找出它的一組基底。為此，對M2f×s進行奇異值分解（SVD），得到

M2f×s=S′2f×2fV′2f×sD′s×s=S2f×3V3×3D3×s（3）

其中S2f×3為S′2f×2f的前3列組成的矩陣，D3×s為D′s×s的前3行組成的矩陣，V3×3為V′2f×s的左上角3×3子矩陣，即3階對角陣。

從上式可以看出，M2f×s中的列向量組和S2f×3的列向量組張成R2f的同一三維線性子空間。同時，R2f到S2f×3列向量組張成的子空間的投影矩陣為：

P2f×2f=S2f×3ST2f×3S2f×3-1ST2f×3（4）

R2f到其正交補空間上的投影矩陣為： P⊥2f×2f=I2f-S2f×3ST2f×3S2f×3-1ST2f×3 （5）

式中I2f為單位陣。

由于S2f×3的列向量組兩兩正交，且模都為1，因此S2f×3滿足

ST2f×3S2f×3=I3×3 （6）

從而式（5）可以簡化為

P⊥2f×2f=I2f×2f-S2f×3ST2f×3（7）

為了方便描述，任取M2f×s中的一個列向量ci。由于M2f×s中的列向量和S2f×3的列向量張成R2f的同一線性子空間，因此，ci投影到S2f×3列向量生成的子空間的正交補空間上的投影為02m×1，即

P⊥2f×2fci=02f×1（8）

這就是M2f×s的元素要滿足的列約束條件。但通常情況下，躁聲使圖像矩陣的元素不可能準確滿足（11）。因此，可以將上式的求解轉化為求余差ei的極小值，即

ei=P⊥2f×2fciTP⊥2f×2fci（9）

由于P⊥2f×2f為投影矩陣，因此上式可以化簡成

ei=cTiP⊥2f×2fci（10）

為了表示方便，令

P⊥2f×2f=p1，1p1，2…p1，2fp2，1p2，2…p2，2fp2f，1p2f，2…p2f，2f（11）

同時，假設由于遮擋的原因，ci含有兩個缺失的元素，即

ci=c1c2…c-k…c-l…c2fT（12）

式中c-表示為遮擋點。

將式（11）和（12）代入式（10）中，則有

ei=ck—cl—pk，kpk，lpl，kpl，lck—cl—+∑2fm=1，m≠k，lpk，mcm+∑2fm=1，m≠k，lpm，kcm∑2fm=1，m≠k，lpl，mcm+∑2fm=1，m≠k，lpm，lcmTck—cl—+c′TiPc′2f-2×2f-2c′i

即

ei=xTiAixi+2bTixi+εi（13）

式中xi=c-kc-lT為未知向量，Ai=pk，kpk，lpl，kpl，l為矩陣P⊥2f×2f的第k、l行和第k、l列構成的子矩陣，

bi=12∑2fm=1，m≠k，lpk，mcm+∑2fm=1，m≠k，lpm，kcm∑2fm=1，m≠k，lpl，mcm+∑2fm=1，m≠k，lpm，lcm

=∑2fm=1，m≠k，lpk，mcm∑2fm=1，m≠k，lpl，mcm，εi=c′iTPc′（2m-2）×（2m-2）c′i為常數項，c′i為向量ci中將兩個缺失元素去除后得到的向量，Pc′2f-2×2f-2為矩陣P⊥2f×2f中刪除了第k、l行和第k、l列的矩陣。

式（13）是一個半正定二次型，對應的極小值問題的目標函數是一個凸函數，因此它的最優解可以直接求出，即為

xi=A-1ibi（14）

在上述推導過程中，我們假設ci僅含有兩個缺失元素，若含有n個缺失元素，則Ai為一個n×n的P⊥2f×2f子矩陣，其元素取自P⊥2f×2f對應于未知元素所在的行和列；bi為一個n×1的向量，其元素為ci中已知元素對應的P⊥2f×2f行中的元素和ci中已知元素相乘之和。

同時，在上述推導中，我們僅針對M2f×s矩陣中的第i列ci，對于所有的其他列，求解都是一樣的，則總余差為：

e=∑si=1ei（15）

在上面的推導過程中，我們假設投影矩陣P⊥2f×2f已知，而事實上P⊥2f×2f由M2f×s矩陣的奇異值分解得到。但在我們所研究的問題中，由于出現了遮擋現象，低秩矩陣M2f×s中產生了缺失元素，因此，無法直接進行奇異值分解。因此算法開始時，可以假設缺失元素的初值由其他已知元素的值的均值確定，然后利用列約束條件，求出缺失元素，此時求出的缺失元素比開始時給定的初值要更加接近真實值，由此可以構造一個迭代算法，恢復出低秩圖像矩陣的缺失元素。endprint

4 算法總結與計算復雜度

現給出基于列約束的低秩矩陣恢復算法：

（1）假設所有的遮擋點m-i，j=1k∑kj=1mi，j（即第i幅圖像中所有已知分量的均值），迭代次數l=1，令ε為任意小的一個正數；

（2）利用式（3），對M2f×s進行奇異值分解；

（3）利用式（7）求投影矩陣P⊥2f×2f；

（4）對于圖像矩陣的每一列，利用式 （14）求出該列的缺失元素xli，并將求出的元素xli代替M2f×s中的缺失元素；

（5）若‖xli-xl-1i‖

SymbolcB@ ε則停止；否則l=l+1，轉第（2）步。

由于式（13） 是一個半正定二次型，從而有唯一的極小值點，而且極小值可以通過式 （14）直接求出。又由于它是一個凸函數，所以迭代誤差滿足

∑si=1e（1）i≥∑si=1e（2）i≥…≥∑si=1e（l）i （15）

因此，理論上保證算法能夠收斂到全局最小值。

本算法的每一步迭代需要進行一次奇異值分解，以及計算P⊥2f×2f，Ai，bi，xi。由于M2f×s奇異值分解的時間復雜度是O（f2s），P⊥2f×2f的計算復雜度是O（f2）。另外由于Ai是P⊥2f×2f的二階子矩陣，bi是二維向量，其計算復雜度為O（f）。而xi=A-1ibi的計算復雜度是一個常數，與f和s均無關。所以本算法的計算復雜度為O（f2sl），其中l為算法收斂所需要的迭代次數。

5 仿真實驗

為了檢驗本文所提方法的收斂速度和恢復效果，現在對含有大量遮擋點的圖像序列進行仿真實驗。實驗的實驗對象是仿真圖像。本文首先用計算機模擬的方法得到100個三維空間點作為特征點，即S為3×100矩陣。另外為了得到矩陣R，模擬相機的位置變化，得到一個包括50幅大小640×480的圖像序列，即R為100×100矩陣。隨機選擇50%的特征點進行遮擋，并在圖像中依次加上均值都為0，方差為0.5、1、1.5、2、2.5、3個像素的高斯噪聲。利用這些模擬得到的圖像點用本文算法進行圖像矩陣的恢復，算法的迭代收斂圖如圖1所示。

同時，為了研究本文算法的收斂性與圖像點的遮擋率之間的關系，在圖像中加入2.0個像素的高斯噪聲，并分別遮擋20%，30%，40%，50%及60%的圖像點，實驗結果如圖2所示。

從圖1和圖2可以看出，本文所提出的方法迭代20次以內就能夠達到收斂，具有良好的收斂性能，原因是由于本文算法將遮擋點的求解轉化為二次型的迭代求解，而二次型的極值點可以一步求解。同時，從圖2還可以看出，遮擋率越高，算法收斂速度越慢，原因是由于遮擋率越高，圖像序列的冗余性也少，約束越少，因此求解的未知數就越多，因此計算量就更大，算法的收斂速度就越慢。

為了比較本文算法和Martinec方法的收斂速度和恢復誤差，用上述方法產生50幅圖像，遮擋率取為20%，并在圖像中依次加入均值為0，方差從0變化到3的高斯噪聲，分別用本文算法和Martinec方法進行圖像矩陣恢復。在每種噪聲下各重復100次實驗，然后求取平均誤差，實驗結果如圖3所示。

從圖3可以看出，相比Martinec方法本文算法具有更高的恢復精度，原因主要有三方面，一方面是由于本文算法不需要計算基礎矩陣，基礎矩陣的計算對圖像噪聲非常敏感；其二方面是由于本文算法將遮擋點的求解轉換為二次型的迭代求解，從而對應優化問題的目標函數是一個凸函數，它可以一步求解到全局最優值，而且算法能夠保證收斂；其三方面是由于本文算法把所有的圖像平等地看待，并沒有倚重某些圖像。因此，本文算法具有較小的誤差。

6 結束語

本文在正投影相機模型下，提出一種基于列約束的低秩矩陣恢復方法。該方法利用圖像矩陣是一個低秩矩陣從而圖像序列具有冗余性，利用奇異值分解由圖像矩陣的列空間構造出一個投影矩陣，將遮擋點的求解轉化為迭代求解二次型的極值問題，利用它恢復出遮擋點，補上圖像矩陣的缺失元素。由于該方法的關鍵在于迭代求解二次型的極值問題，而二次型是一個凸函數，它可以一步求解到全局最優值，因此具有良好的收斂性能。仿真實驗結果表明，本文方法相比Martinec方法具有收斂速度快，恢復精度高等優點。由于在此算法中我們只考慮了基于列向量的約束，進一步的研究方向將是把基于行向量和列向量的約束同時考慮，以提高算法的效率。

參考文獻

[1] KENNEDY R，BALZANO L，WRIGHT S，et al.Online algorithms for factorization-based structure from motion[J].Computer Vision and Image Understanding，2016，150： 139-152.

[2] KIM H，LEUTENEGGER S，DAVISON A.Real-Time 3D Reconstruction and 6-DoF Tracking with an Event Camera[C].14th European Conference on Computer Vision，11-14 October 2016，Amsterdam，Netherlands，349-364.

[3] COHEN A，SCHONBERGER J，SPECIALE P，SATTLER T，FRAHM J，POLLEFEYS M.Indoor-Outdoor 3D Reconstruction Alignment[C].14th European Conference on Computer Vision，11-14 October 2016，Amsterdam，Netherlands，285-300.endprint

[4] TOMASI C，KANADE T.Shape and Motion from Image Streams under Orthography： a Factorization Method[J].International Journal of Computer Vision，1992，9（2）：137-154.

[5] JACOBS D.Linear fitting with missing data for structure-from-motion[J].Computer Vision and Image Understanding，2008，82（1）：57-81.

[6] STRELOW D.General and nested Wiberg minimization[C].IEEE Conference on Computer Vision and Pattern Recognition，Rhode Island，16-21 June 2012，1584-1591.

[7] OKATANI T，DEGUCHI K.On the Wiberg algorithm for matrix factorization in the presence of missing components[J].International Journal of Computer Vision，2007，72（3）：329-337

[8] ZHENG Y，SUGIMOTO S，YAN S，et al.Generalizing Wiberg algorithm for rigid and nonrigid factorizations with missing components and metric constraints[C].IEEE Conference on Computer Vision and Pattern Recognition，16-21 June 2012，Rhode Island，2010-2017.

[9] STRELOW D，WANG Q，SI L，et al.General，Nested，and Constrained Wiberg Minimization[J].IEEE Transactions on Pattern Analysis and Machine Intelligence.2016，38（9） ：1803-1815.

[10] ALBL C，SUGIMOTO A，PAJDLA T.Degeneracies in Rolling Shutter SfM[C].14th European Conference on Computer Vision，11-14 October 2016，Amsterdam，Netherlands，36-51.

[11] AGUDO A，NOGUER F，CALVO B，et al.Sequential Non-Rigid Structure from Motion Using Physical Priors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2016，38（5）： 979-994.

[12] MARTINEC D，PAJDLA T.Outlier detection for factorization-based reconstruction from perspective images with occlusions[A].In Proceedings of the Photogrammetric Computer Vision[C].TU-Graz，2002，B：161-164.endprint