基于随机梯度下降算法的公安视频侦查图像修复

孟钰潇，周西平

(中国人民公安大学 国家安全学院，北京 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 结束语

随着现代科学技术手段尤其是计算机信息技术的迅速发展，警务信息侦查工作需要处理的数据维度逐渐提高，且具有越来越复杂的结构。秩最小化方法在矩阵补全中起到了举足轻重的作用，但由于如今的大量高维数据结构复杂，这种方法起到的作用越来越有限，并逐渐无法对其进行有效的约束，因此提出了将矩阵补全方法推广至张量补全，除了警务工作以外，张量补全问题在计算机视觉、信息科学、运动物体识别等领域应用越来越广泛。

目前，无论是国内还是国外，图像恢复都是各领域的一大研究热点，而张量补全则是近几年才提出的一种理论框架，针对张量补全的算法及应用都还处于初级阶段。但张量对大规模高维数据优秀的表达能力赋予了张量巨大的应用潜力，因此，张量领域仍有很大的空间等待探索，图像恢复仅仅是张量应用的一角，未来的工作应将张量补全推广到公安工作更广泛的应用领域，例如修复警务信息数据库缺失和公安视频及音频数据缺失等。