基于隨機梯度下降算法的公安視頻偵查圖像修復

孟鈺瀟，周西平

(中國人民公安大學 國家安全學院，北京 100038)

在情報部門搜集的情報中，圖像占據較大比例，其來源傳統上被認為是可見光攝影，在軍事化行動中還包含雷達和紅外頻譜圖像。無論是使用遙感裝置收集到的圖像還是普通手持照相設備采集到的圖像，都能為警務工作提供有價值的情報。圖像情報的優點是能夠較為直觀地顯示所需的信息，為后續分析工作節省人力和物力，將圖像情報與通信和人力情報相結合，可以較為準確地確定目標的位置和地形等詳細信息，同時為其他情報搜集行動提供線索，協調使用非圖像情報收集手段，可以有效覆蓋警務工作活動。

然而由于主觀和客觀的多方面原因，實戰部門搜集到的圖像資料可能會產生不同程度的缺損和失真，失真的原因包括采集設備的異常數據、傳感采集時的大氣噪聲、數據傳輸過程中的丟失以及從不同角度進行觀察而產生的幾何失真等，特別是在實戰中視頻偵查對動態圖像捕捉中產生的圖像模糊，都需要對圖像進行以修復為主的預處理。

本文在研究視頻偵查的基礎上，引入基于隨機梯度下降的張量鏈分解算法，用于受損圖像的修復，在仿真實驗中觀察其峰值信噪比和相對平方差參數值，判斷修復效果。

1 研究現狀

圖像修復技術課題主要屬于對圖像缺損的處理，指對已重建的圖像和視頻中已經丟失或嚴重損壞部分的修復過程，具體是指利用復雜的圖像處理算法和工具來自動替換已修復或丟失、損壞的部分圖像處理數據，主要是替換一些小的區域和瑕疵。其目的主要在于根據圖像中原本或者已知的信息，按照一定的圖像處理程序和技術原則自動地修復其中受損或嚴重丟失的部分，使得修復后的圖像更加接近甚至可以達到恢復原圖像所想要呈現的清晰度和視覺效果。許多實際的問題中，圖像數據可能在獲取、傳輸或者是保存的整個過程中都不可避免產生缺失項，比如利用醫學遙感掃描圖像中的三維視覺器官和影像中的病灶、遙感掃描影像中的缺損和劃痕現象[1]、珍貴的影像資料中因保存不善可能帶來的缺損和劃痕等，這類帶有缺失項的圖像數據就可以稱作不完整的數據，圖像補全技術可以利用已有的數據來恢復缺失的數據。這種圖像處理技術在遙感掃描圖像的縮放、文物保護、影視制作、虛擬現實以及多余圖像目標的移除等許多技術領域中都存在重大的應用和價值。在圖像攝影和電影業中，使用這項技術來修復電影、還原變質惡化的膠片[2]。同時，還可用來消除紅眼、照片上的日期、水印等等，甚至還可以實現某些特效。數字圖像的編碼和傳輸過程中也能使用圖像修復技術替換丟失的數據。

傳統圖像修復的相關方法可以分為兩類:基于補丁的方法和基于擴散的方法。基于補丁的方法是通過在圖像的未損壞部分搜索匹配良好的替換補丁(即候選補丁)，并將其復制到相應的位置，從而填補缺失區域的patch-by-patch技術。基于補丁的圖像修復方法已經被多次提出。JIN和YE[1]提出了一種基于湮沒性質濾波器和低秩結構矩陣的補丁方法。為了從圖像中移除目標，KAWAI et al[2]提出了一種基于選擇目標對象和通過背景限制目標周圍搜索的方法。DUAN et al[3]提出了一種基于非局部Mumford-Shah模型(NL-MS)的圖像修復方法。許多圖像在采集獲取的過程中由于設備或人為的因素造成圖像的離散型缺失，對于這種情況，如果采用傳統的圖像修復算法需要花費巨大的人力物力，并且修復的結果往往不盡如人意，因此，有必要開發一個更為高效的算法來獲取數據全部信息。

2000年，基于偏微分方程的數字圖像修復模型方法第一次被提出[4]，其圖像修復原理主要是根據圖片中待修補缺損區域的邊緣信息，利用熱擴散的機制沿著等照度線的方向，將缺損區域已有的信息均勻地擴散到圖片中待修補的缺損區域內部，本模型方法對于修復缺損圖片中的劃痕、裂痕等小尺度的缺損區域修復效果較好，但修復效率相對較低，并且在圖片缺損待修補區域很大的時候修復效果欠佳。2008年WANG et al第二次提出了基于偏微分幾何圖形修復模型的整體變分圖像修復模型[5]，但由于該模型在平坦的區域容易產生明顯的階梯效應，并且其計算錯誤量較大，2009年又進一步提出了基于圖像曲率合成技術驅動圖像擴散的紋理修復模型[6]，該模型雖然能對較大紋理缺損區域的圖像進行紋理修復，但也可能對圖像造成模糊。以上的方法被認為只適合于修復圖像裂痕、劃痕等小尺度的非紋理缺損圖像，無法很好地廣泛應用于紋理缺損區域很大的圖像修復情況。隨后又進一步提出了基于圖像分解的紋理修復區域合成技術[7]和基于樣本的圖像紋理修復合成區域技術[8]，很好地幫助修復比較大塊缺損的區域，但在其過程中需要搜索最優匹配塊，計算量非常大。

近年來，矩陣逼近問題[9]在圖像處理領域和計算機視覺領域應用越來越廣泛，它的核心思想在于利用數據矩陣的一些結構信息來恢復缺損的數據元素，并且有相應的研究得出矩陣的秩是獲取全局信息的有力工具。它的缺陷在于，矩陣秩函數并不是一個凸函數，一些方法被反復用來估計缺失的元素，由于秩約束的非凸性，不能保證得到一個最優解。在圖像處理領域，圖像修復和視頻修復都可以被歸結為矩陣補全問題，此方法存在可行性，但使用的代價是面對高維數據，使用傳統的矩陣補全算法需要巨大的計算量和儲存空間，導致算法處理效率低。

2 張量補全

張量是矩陣和向量的更高階推廣，它是矩陣的高階推廣形態，能有效解決矩陣補全算法計算量大、效率低下的問題。目前，張量分解在計算機視覺、信息科學、運動物體識別等領域都有廣泛應用，幾乎所有真實世界存在的復雜數據形態都可以用張量表示。張量提供了一種自然的方式來表示多維數據，其條目由幾個連續或離散變量索引。使用張量及其分解來處理數據變得越來越流行，例如，彩色圖像是由兩個空間變量索引和一個顏色模式索引定義的三階張量。由彩色圖像組成的視頻是一個四階張量，具有一個時間變量的附加索引。然而，實際應用中的張量通常是低秩的，它們存在于超高維數據空間中，因此，它們可以有效地投射到更小的子空間，通過基礎分解，如CANDE-COMP/PARAFAC(CP)分解[10]和張量鏈(Tensor Train)分解[11]或矩陣積態(MPS)分解[9]。

在低秩矩陣補全(LRMC)[12]成功的推動下，人們努力將其概念擴展到低秩張量補全(LRTC)[13]。事實上，低秩張量補全已經在計算機視覺和圖形、信號處理和機器學習中找到了應用，常見的目標是從張量的部分觀察到其完整實體。

由于張量秩(定義為CP秩)的計算已經是非確定性多項式困難問題，低秩張量補全仍然是一個巨大的挑戰。有方法試圖通過Tucker秩接近低秩張量補全。Tucker秩的一個概念上的缺點是它的組成部分是基于非平衡矩陣化方案(一種模式對另一種模式)構造的矩陣秩。每個秩的上界通常很小，不適合描述張量的全局信息。此外，只有當矩陣更為平衡時，矩陣秩最小化才是有效的。例如，針對一個m×n的矩陣，秩不大于min{n，m}，其中m和n分別是矩陣的行數和列數，高比率的max{m，n}/min{m，n}將減小矩陣秩最小化的需要，目前最先進的低秩矩陣補全方法隱式假設其所考慮的矩陣是平衡的。

2.1 張量的表示

張量是一個多維數組，其順序(也稱為方式或模式)是其維數。標量可以看作零階張量，向量和矩陣是一階和二階張量。N階張量表示為χ∈RI1×I2×…×IN，N是對應k的維數。χ的元素表示為χi1…ik…iN，其中1≤ik≤Ik,k=1,…,N.

張量χ∈RI1×I2×…×IN的纖維(fiber)是一個通過固定所有索引定義的向量，但是in是由χi1…in-1∶in+1in表示的。

2.2 張量運算

2.2.1張量的模矩陣化

張量χ∈RI1×I2×…×IN的模矩陣化(也稱n模展開或展平)是通過將纖維重新排列為結果矩陣的列，將張量展開或重塑為矩陣X(n)∈RIn×(I1…Ik-1Ik+1…IN)的過程。張量元素(I1,…,In-1,In+1,…,IN)映射到矩陣元素(in,j)，表示為：

(1)

張量χ∈RI1×I2×…×IN與矩陣A∈RJ×IN的模n積得到一個新的張量I1×…×In-1×J×In+1×…×IN，表示為χ×nA.

元素方面，它可以表示為：

(2)

其中，x為張量χ中元素，a為矩陣A中元素。

2.2.2張量的內積和Frobenius范數

張量的范數是指張量內所有元素的平方和的平方根，即：

(3)

兩個張量χ,y∈RI1×I2×…×IN的內積定義為：

(4)

3 基于隨機梯度下降的張量鏈式分解算法

3.1 張量鏈分解

張量是矩陣的自然多維推廣，近年來在各種領域得到了廣泛的應用，多線性代數、張量分析和張量逼近理論在計算數學和數值分析中發揮著越來越重要的作用。用少量參數有效表示一個張量能夠更加方便和高效地處理d維問題，d有時高達10，100，甚至1 000.由于維數災難，這種大小的問題不能用標準的數值方法來處理，因為所有的東西，例如內存和運算量，在d中都是指數增長的。使用給定張量χ和元素χ(i1,…,id)可以有效表示一大類重要的d維張量：

(5)

式(5)中的χ所需的最小求和數r稱為張量秩或規范秩。矩陣Mk=[Mk(ik,α)]被稱為規范因子。對于一個大的d，張量χ不是顯式形成的，而是用一些低參數格式表示的。規范分解式(5)是這種格式的一個很好的選擇。然而，它有幾個缺點：正則秩的計算是一個非確定性多項式困難問題，在Frobenius范數中具有固定正則秩的近似可能是不適定的，因此，在這種情況下計算近似表示的數值算法可能會失敗；此外，即使是用于計算最佳低張量秩近似的最成功的現有算法也不能保證在已知存在良好近似情況下也能很好地工作。通常情況下，它們會遇到局部極小值并卡在那里。這就是為什么研究規范格式的替代方案是一個好主意，規范格式可能有更多的參數，但更適合于數值處理。Tucker格式是穩定的，但在d個參數O(dnr+rd)中是指數型的，它適用于“小”尺寸，特別是三維的情況，對于d較大的情況并不適用。

通過張量χ≈T的元素來近似給定的張量T：

χ(i1,i2,…,id)=G1(i1)G1(i2)…Gd(id) .

(6)

其中，Gk(ik)是rk-1×rk的矩陣。這些參數相關矩陣的乘積是r0×rd大小的矩陣，因此“邊界條件”r0=rd=1必須被施加。比較式(6)與秩-1張量的定義[12]：它是秩-1張量的一個非常直接的塊推廣。如本文所示，式(6)與規范分解式(5)的區別之一是秩rk可以作為某些輔助矩陣的秩來計算。如果把式(6)寫成索引表，矩陣Gk(ik)實際上是一個三維數組，它可以被看作是一個rk-1×nk×rk的數組，其元素為Gk(αk-1,nkαk)=Gk(ik)αk-1αk，在索引表中，分解被寫為[11]：

(7)

3.2 張量鏈秩

由于r0=r1=1，這種分解也可以用線性張量網絡來表示，如圖1所示。

圖1 張量鏈網絡

圖片表示了有兩種類型的節點。矩形包含空間索引(即原始張量的索引ik)和一些輔助索引αk，具有這些索引的張量與此類節點相關。圓僅包含輔助索引α，并且表示一個鏈接：如果兩個核張量中存在輔助索引，則連接它。假設對輔助指標求和，即，要計算一個張量項，必須乘以矩形中的所有張量，然后對所有輔助指標求和。圖1看起來像一列車廂和車廂之間的有連接的火車，這證明了張量鏈分解，或者簡稱張量鏈分解的合理性。秩rk稱為壓縮秩或張量鏈秩，是張量鏈分解的三維張量Gk-core，它類似于Tucker分解的核張量。張量網絡有更一般的類型，用圖來表示，但只有少數具有良好的數值性質。張量鏈格式在其他領域也稱為線性張量網絡(LTN)或矩陣乘積狀態(MPS)，它具有區別于其他類型網絡的若干特征。因此，必須使用這樣的張量來執行近似運算，從而在保持精度的同時減少存儲量。

張量鏈分解最顯著的特點是模型參數的個數不會隨著張量階的增加而呈指數增長。張量鏈分解是把一個張量分解成一系列有序的三核張量(因子張量)：G(1),G(2),…,G(N).近似張量χ∈RI1×I2×…×IN，與核張量之間的關系可以表示為：

χ=《G(1),G(2),…,G(N)》 .

(8)

其中，對于n=1，…，N，G(N)∈RRn-1×In×Rn，R0=RN=1，符號《·》是將核心張量轉換為近似張量的操作，為了簡化表達，G(1)∈RI1×R1和G(N)∈RRN-1×IN可以看作是兩個二階張量。序列R0,R1,…,RN稱為張量鏈秩，它限制了每個核張量的大小。除此之外，張量χ的元素(i1,i2,…,iN)可以用相應的核張量的模2切片的乘積表示為：

(9)

3.3 求解算法

張量鏈格式在數值分析中得到了廣泛的應用，但其在圖像分類和補全方面的應用比較有限。如在[14]概述的，張量鏈分解受到以下限制：(1) TT模型要求邊界因子的秩1約束；(2) 對于近邊界因子，張量鏈秩通常較小，而對于中間因子，張量鏈秩較大；(3) 張量鏈因子的乘法不是置換不變的。為了彌補這些缺點，將隨機梯度下降算法與張量鏈結合，提出TT-SGD算法。隨機梯度下降法(SGD)已經應用于矩陣分解和張量分解，它的優點在于只隨機抽取一個觀測條目來計算每次迭代的梯度，即對于每一次優化迭代，只使用從觀測項中隨機抽取的一個項，并且一個項只能影響部分核張量的梯度[15]。對于一個觀察到的索引項{i1,i2,…,iN}，如果張量鏈核張量近似值為xi1,i2,…,iN，且觀測值(實數)為yi1,i2,…,iN，由公式(8)得，目標函數可以表示為：

(10)

(11)

從方程中可以看出，基于隨機梯度下降的張量鏈分解算法的計算復雜度與觀測張量的尺度和觀測條目的數目無關，因此它可以以更小的計算復雜度處理大規模數據。該算法也適用于在線或實時學習。算法優化過程為：

Algorithm

Input:不完全張量Y和張量鏈秩r

隨機初始化核張量G(1),G(2),…,G(N)

1: 當優化停止條件不滿足時

2: 從y中隨機采樣yi1,i2,…,iN

3: forn=1:N

用公式(11)計算核張量的梯度。

4: End

6: End while

Output:G(1),G(2),…,G(N)

3.4 計算復雜度分析

對于張量χ∈RI1×I2×…×IN，假設所有I1×I2×…×IN等于I，R1=R2=…=RN-1=R，根據公式(11)得出該算法的時間復雜度為O(N2R3)，空間復雜度為O(R2).由于基于隨機梯度下降的張量鏈分解算法不存在數據維數，且每次迭代的復雜度極低，因此非常適合處理大規模數據。對于每次迭代，也可以應用基于批量的隨機梯度下降方法，該方法計算每次迭代的批量大小條目梯度的總和。雖然這可以提高算法的穩定性，并且可能需要較少的迭代來收斂，但會增加計算復雜度，并且每次迭代需要更多的計算時間。在本文中，只使用了第一批SGD算法，下一部分的綜合實驗表明，這一方法也能實現快速穩定的收斂。

4 實驗結果與討論

以2015年江詩丹頓名表專賣店持槍搶劫案中獲取的嫌疑人軌跡圖像為例，實驗結果如圖2-4所示，具體修復結果如表1-3所示。

圖2 軌跡圖像一

表1 軌跡圖像一修復結果

對嫌疑人換裝后在東門中公交站北側視頻監控中出現的圖像進行修復。

圖3 軌跡圖像二

表2 軌跡圖像二修復結果

對曬布路站視頻監控捕捉到的嫌疑人影像進行修復。

圖4 軌跡圖像三

表3 軌跡圖像三修復結果

對修復后的圖像進行放大，可以看出嫌疑人頭戴假發，面部戴黑色墨鏡，身穿米黃色風衣和白色襯衫、黑色領帶，腳踩黑色白邊運動鞋，身高約170 cm，體型偏瘦，且走路有明顯外八。由對圖像進行10次修復的PSNR和RSE值可以看出，該算法修復后的峰值信噪比處于30～40 dB之間，相對平方差值分布在0.040至0.060之間，顯著優于張量環算法。從圖像本身來看，經基于張量鏈分解的隨機梯度下降算法修復后的圖像噪音較少，由此得出該算法性能優于基于張量環分解的算法。

5 結束語

隨著現代科學技術手段尤其是計算機信息技術的迅速發展，警務信息偵查工作需要處理的數據維度逐漸提高，且具有越來越復雜的結構。秩最小化方法在矩陣補全中起到了舉足輕重的作用，但由于如今的大量高維數據結構復雜，這種方法起到的作用越來越有限，并逐漸無法對其進行有效的約束，因此提出了將矩陣補全方法推廣至張量補全，除了警務工作以外，張量補全問題在計算機視覺、信息科學、運動物體識別等領域應用越來越廣泛。

目前，無論是國內還是國外，圖像恢復都是各領域的一大研究熱點，而張量補全則是近幾年才提出的一種理論框架，針對張量補全的算法及應用都還處于初級階段。但張量對大規模高維數據優秀的表達能力賦予了張量巨大的應用潛力，因此，張量領域仍有很大的空間等待探索，圖像恢復僅僅是張量應用的一角，未來的工作應將張量補全推廣到公安工作更廣泛的應用領域，例如修復警務信息數據庫缺失和公安視頻及音頻數據缺失等。