《武汉工程大学学报》 2015年12期
69-74
出版日期：2016-01-14
ISSN:1674-2869
CN:42-1779/TQ
基于降维压缩法的图像重构
０ 引 言近年来，矩阵填充（Ｍａｔｒｉｘ ｃｏｍｐｌｅｔｉｏｎ，ＭＣ）理论逐渐受到越来越多学者的关注，它是一种高效的信号数据处理技术． 在实际研究中，图像、信号、数据等都可以利用矩阵的形式表示，但由于受到实验条件限制，获得的矩阵元素往往是缺失、受噪声污染的． 如何通过有效算法计算得到干净、完整的矩阵？这便是矩阵填充研究的问题，其核心思想是通过采集部分元素重构出目标矩阵，在重构精度上体现出优越性． 基于矩阵填充技术重构图像矩阵，应用于人脸识别，在保证较高保真度基础上对人脸图像矩阵进行压缩降维处理，利用矩阵填充算法有效实现重构． 对研究人脸识别与追踪问题具有积极意义． １ 相关技术１．１ 图像降维处理将数值元素写成低秩矩阵的形式称之为矩阵的降维过程． 矩阵降维技术作为获取相关性和去噪的基本工具，广泛应用于图像压缩、计算机视图、机器学习等领域． 降维的目的在于从有限缺失的信息中获得更简洁的数据表示，一种经典的降维技术是基于奇异值分解实现低秩逼近． 与其他低秩逼近方法比较，奇异值分解的重建误差较小［１］． 由于图像矩阵的奇异值是人脸识别的代数特征量，能够反映人脸图像的内在属性和本质特征［２-３］，利用奇异值分解的方法能够对获得的人脸图像矩阵进行合理的降维处理，在不影响估计性能的前提下，有效地降低计算量，节约时间和成本［４］． 将人脸图像写成矩阵的形式，设Ｍ∈Ｒｍ×ｎ是原始图像，Ｘ∈Ω是重建的近似图像，整数ｒ满足１≤ｒ＜ｒａｎｋ（M），Ω为矩阵集合，｜｜?荠｜｜为矩阵范数，拟合秩为ｒ的矩阵Ｘ，使其有 ｜｜Ｍ-Ｘ｜｜=■｜｜Ｍ-Ｘ｜｜ 应该指出，对于矩阵Ｘ的重构过程必须在集合Ω和秩为ｒ的限制条件之内． 对矩阵Ｍ进行奇异值分解［５］，即Ｍ（ｖ）＝Ｕ（ｖ）∑（ｖ）Ｖ（ｖ），令Ｓ１（ｖ），Ｓ２（ｖ），…表示奇异值∑（ｖ）的对角元素，现将矩阵∑（ｖ）的对角元替换为｛Ｓ１（ｖ），…，Ｓｋ（ｖ），０，…，０｝，记为∑′（ｖ）定义 Ｘ（ｖ）:=Ｕ（ｖ）∑′（ｖ）Ｖ（ｖ）T在投影过程中，矩阵集合｛Ｍｖ｝满足不等式 ｜｜Ｍ（ｖ＋１）-Ｘ（ｖ＋１）｜｜F ≤｜｜Ｍ（ｖ＋１）-Ｘ（ｖ）｜｜F ≤｜｜Ｍ（ｖ）-Ｘ（ｖ）｜｜F 由此能够对原始图像矩阵进行降维处理，并利用矩阵填充技术在已知部分数据的前提下实现人脸图像的重构． 人脸图像重构流程图如图１所示．图１ 人脸图像重构流程图Ｆｉｇ．１ Ｆｌｏｗ ｄｉａｇｒａｍ ｏｆ ｆａｃｅ ｉｍａｇｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ １．２ 矩阵填充原理由于重构的近似图像矩阵Ｘ是秩为ｒ的低秩矩阵，其独立元的个数ｄｆ＝（２ｍｎ－ｒ）ｒ远小于维数ｍ×ｎ． 这说明只要采样数目大于ｄｆ，是有可能从采集的有限元素中重构矩阵Ｘ，该问题能够通过解决如下凸优化问题实现： ｍｉｎｉｍｉｚｅ ｒａｎｋ（Ｘ） ｓｕｂｊｅｃｔ ｔｏ Ｘｉｊ＝Ｍｉｊ（ｉ，ｊ）∈Ω（１）其中Ｘ为重构矩阵，ｒａｎｋ（Ｘ）表示矩阵Ｘ的秩． 这是一种根据观测数据拟合矩阵的普遍方法，如果存在唯一的低秩拟合数值，那么能够实现重构，但这是个ＮＰ?鄄ｈａｒｄ问题，在理论和数值实验中需要大量时间，不具有应用价值． 如果秩为ｒ的矩阵能够进行奇异值分解，那么在限制集合内能够用奇异值之和最小化来替代（１）式中秩最小化问题，有 ｍｉｎｉｍｉｚｅ ｜｜Ｘ｜｜* ｓｕｂｊｅｃｔ ｔｏ Ｘｉｊ＝Ｍｉｊ（ｉ，ｊ）∈Ω （２）其中｜｜Ｘ｜｜*＝■?滓k（Ｘ）表示核范数，?滓k（Ｘ）为矩阵Ｘ的奇异值． 由于核范数是凸函数，能够通过半正定程序有效优化． 则式（１）的ＮＰ?鄄ｈａｒｄ问题成功转化为凸优化问题，只需要选择合适的算法程序就能够实现矩阵的重构． 如果矩阵的某一行或者列的所有元素都没有被采样得到，那么无论采用何种理论和方法都不可能填充出这一行或者列的数值． 因此，当采样方式满足一定条件时，才有可能实现矩阵重构． 矩阵填充的采样方式一般是随机等分采样． 如果矩阵的行和列几乎都由零值组成，那么无论使用何种采样方式都不可能实现重构，原因是对于大部分的采样集合，得到的都是零值以至于没有办法计算出非零数据． 比如矩阵： Ｍ= 0 0 … 0 1 0 0 … 0 0■ ■ ■ ■ ■ 0 0 … 0 0对于这样的矩阵只有右上角一个数值，其余均为０，虽然是低秩矩阵却无法利用矩阵填充原理实现重构［６］． 这就要求想要重构的目标矩阵Ｍ的奇异向量高度集中，能够在非零空间中进行采样操作． 即，奇异向量在标准基内具有不相关性，为了使观测值数目最小化，有如下定义：假设Ｕ为Rｎ的子空间，ＰＵ为在Ｕ上的正交投影，则Ｕ的相关性表示为 ?滋（Ｕ）=■■｜｜PU ei｜｜■其中ｉ为子空间Ｕ的维度，ｅｉ为标准基． 对于任意子空间，?滋（Ｕ）的最小值为１，如果Ｕ由元素值为■倍数的向量测量得到，那么?滋（Ｕ）的值为■． 对于低相关性的矩阵，对应于子空间中的行列值均具有低相关性，则不能在零空间进行采样． 对矩阵Ｘ进行奇异值分解，有 Ｘ=■Uk?滓kV*k其中Ｕ和Ｖ分别代表行列矢量空间． 由于矩阵的相关性满足max（?滋（Ｕ）），（?滋（Ｖ））≤?滋0，Ｘ=■ＵkＶ*k的最大值上限为?滋1■，则满足柯西?鄄施瓦茨不等式： ■ＵikＶjk≤■■≤■１．３ 基本算法核范数最小化过程是一个凸优化线性约束问题． 虽然能够转换为一个半正定程序解决，但是这种方法在计算大矩阵上是耗时耗资的． 固定点迭代算法［７］（ＦＰＣ），在求解核范数最小化问题上体现了用时短，重构误差小的优越性． 核范数被称为Ｓｃｈａｔｔｅｎ?鄄１范数或Ｋｙ?鄄Ｆａｎ范数，式（２）的核范数问题亦可写成 ｍｉｎｉｍｉｚｅ ｜｜Ｘ｜｜* ｓｕｂｊｅｃｔ ｔｏ A（Ｘ）=b （３）若b受噪声污染，则约束条件改写成 ｍｉｎｉｍｉｚｅ ｜｜Ｘ｜｜* ｓｕｂｊｅｃｔ ｔｏ ｜｜A（Ｘ）-b｜｜2≤?兹 （４）其拉格朗日形式为 ｍｉｎｉｍｉｚｅ ?子｜｜Ｘ｜｜*+■｜｜A（Ｘ）-b｜｜■■（５）其中θ和τ均为中间参数． 利用ＦＰＣ算法解决式（５）的问题如下： Ｙｔ＝Ｘｔ－?着ｇ（Ｘｔ）Ｘｔ+1=Γ?着?子(Ｙｔ) （６）其中Γ（?荠）表示矩阵的收敛操作． 该算法的核心是算子分裂技术，设Ｘ*为式（５）的最优解，当且仅当 ０∈?子ΓＧＮ（Ｘ*）＋ｇ* （７）其中ｇ*＝AＴ（AＸ*－ｂ），对于任意ε＞０，式（７）等价于 ０∈?着?子ΓＧＮ（Ｘ*）＋?着ｇ（Ｘ*）（８）设Ｔ（·）∶＝ετΓＧＮ（Ｘ*）＋εｇ（Ｘ*），能够分成如下两部分：Ｔ（·）＝Ｔ１（·）－Ｔ２（·），其中Ｔ１（·）＝ετΓＧＮ（·）＋Ｉ（·）且Ｔ２（·）＝ Ｉ（·）－εｇ（·）． 设y=T2（Ｘ*）=Ｘ*-?着AT(AＸ*-b)，式（８）又可写成 ０∈T1(Ｘ*)-y=?着?子ΓＧＮ（Ｘ*）＋Ｘ*-y（９）式（９）实际上是如下凸问题的优化条件■?着?子｜｜Ｘ*｜｜■1+■｜｜Ｘ*-y｜｜■■该问题的最优解由收敛算子给出： Ｘ*=■v(y)其中v=?着?子及收缩算子为■v（·）. ■v（·）=sgn(·)·max{｜·｜-v,0}（１０）因此，ＦＰＣ迭代算法由式（1１）给出. Ｘｔ＋１＝■?着?子（Ｘｔ－?着ｇｔ） （１１）由于式（５）的主函数是凸的，当且仅当 0∈?子?坠｜｜Ｘ*｜｜*+g（Ｘ*）（１２）时，Ｘ*是最优解． 其中ｇ（Ｘ*）＝A*（A（Ｘ*）－ｂ），对Ｘ进行奇异值分解，即Ｘ=U∑VＴ，其中，∑=Diag(?滓)∈Rr×r,V∈Rr×r那么 ?坠｜｜Ｘ｜｜*＝｛ＵＶＴ＋Ｗ∶ＵＴＷ＝０｝，ＷＶ＝０，｜｜Ｗ｜｜２≤１ 其中矩阵Ｗ∈Rm×n满足 ?子（ＵＶＴ＋Ｗ）＋ｇ（Ｘ）＝０ＵＴＷ＝０，ＷＶ＝０，｜｜Ｗ｜｜２≤１（１３）则有 ０∈?着?子?坠｜｜Ｘ*｜｜*＋Ｘ*－（Ｘ*－?着ｇ（Ｘ*）） （１４）对任意?着>0，如果Y*=Ｘ*－?着ｇ（Ｘ*)式（１４）式变为 ０∈?着?子?坠｜｜Ｘ*｜｜*＋Ｘ*－Y*■?着?子｜｜Ｘ｜｜*+■｜｜Ｘ-Y*｜｜■■（１５）由此得出Ｘ*的优化解满足. 利用固定点迭代法解决式（５）的具体步骤： （１）初始化：给定Ｘ０，■>0． 选取?子1>?子2>…>?子L=■>0． 设置Ｘ=Ｘ０ ． （2）以?子=?子1，?子2，…，?子L，开始，?着>0数列收敛时，计算Y＝Ｘ－?着A*（A（Ｘ）-b），且对Y作ＳＶＤ分解，Y=UDiag(?滓)VＴ，计算Ｘ＝ＵＤｉａｇ（Γ?着?子（?滓））ＶＴ． （3）逐次迭代至数列不收敛时结束． ２ 数值结果与分析采用２．２ ＧＨｚ ＣＰＵ，４ ＧＢyte内存的计算机进行模拟仿真实验，使用ＭＡＴＬＡＢ编码运行算法程序．将降维技术应用于人脸图像矩阵中，用ＯＲＬ国际标准人脸数据库中Ｓ４０的图像作为研究对象，其图像维数为１１２×５５２，对图像矩阵进行奇异值分解，分析奇异值大小与维数的关系（见图２）可知，并非所有的奇异值均对图像信息有较大贡献，只需要提取出具有决定因素的奇异值就能够充分反映图像特征，从而实现图像的压缩降秩，在保证图像质量的前提下，尽可能地降低矩阵的秩，而评估图像质量的常用函数有：均方根误差SＲＭＳＥ，信噪比QＳＮＲ，峰值信噪比QＰＳＮＲ等． 下面给出峰值信噪比QＰＳＮＲ的计算公式，分析重建图像质量 QＰＳＮＲ＝１０×lg■ SＲＭＳＥ=■从图２可知，随着维数的增大，奇异值逐渐减小，较大的奇异值数量级在１０４，较小的奇异值为５０左右，由于奇异值越小，对图像保真度的影响越低，那么能够将数值较小的，对图像特征贡献少的奇异值合理舍去，并结合奇异值个数与峰值信噪比的关系（见图３），确定降维后的人脸图像矩阵． 图3中秩为３５对应的QＰＳＮＲ值等于３５时，重建的人脸图像轮廓清晰，与原图基本无差别，保证了图像的质量． 这说明能够将维数为１１２×５５２的人脸图像压缩成秩为３５的图像输出． 图２ 奇异值与矩阵维数的关系曲线Ｆｉｇ．２ Ｒｅｌａｔｉｏｎ curve between ｓｉｎｇｕｌａｒ ｖａｌｕｅ and ｍａｔｒｉｘ ｄｉｍｅｎｓｉｏｎ图３ 奇异值个数与１/QＰＳＮＲ关系曲线Ｆｉｇ．３ Ｒｅｌａｔｉｏｎ curve between ｓｉｎｇｕｌａｒ ｖａｌｕｅｓ and １/QＰＳＮＲ人脸识别广泛应用于公安检查、监控等方面，但由于实际条件的限制，获得的图像矩阵往往是缺失的，为了获得较高清晰度的人脸图像，除了利用奇异值分解提取特征信息外，还要求将目标矩阵从获得的部分数据中重构出来． 利用矩阵填充算法，分析不同采样率下对人脸图像的重构效果（见图４）． 其中第一行是原始图像，第二行是秩为３５时的重建图像，第三、四、五行分别是采样率为１０％、３０％、５０％的效果图． 将未经降秩处理直接进行采样的图像进行重构，效果如图５所示，其中第一、二、三行分别对应采样率为１０％、３０％、５０％的效果图． 对于图４，秩为３５时重建图像清晰可辨，说明压缩降维处理合理有效． 当采样率为１０％时，由于采样数目ｍ＝６ １８２小于独立元个数ｄｆ＝２２ ０１５，不符合矩阵填充重构条件，图像模糊失真；采样率为３０％时，能够识别出人脸轮廓；采样率为５０％时，图像整体清晰，虽有模糊，但人脸的识别度较高，与图５进行对比，容易看出，通过降维处理后，重构的人脸图像比较清晰．图６给出运行时间和采样率的关系图，随着采样率逐渐增大，程序运行时间变长，当采样率为７０％时，运行时间为２５ ｓ，均不超过１ ｍｉｎ，这说明通过降维处理的矩阵填充技术能够有效地实现人脸图像的重构． 图４ 降秩处理后不同采样率下图像矩阵填充效果Ｆｉｇ．４ Ｒｅｄｕｃｅｄ－ｒａｎｋ ｍａｔｒｉｘ ｃｏｍｐｌｅｔｉｏｎ ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｓａｍｐｌｅ ｒａｔｅｓ图５ 未经降秩处理不同采样率下图像重够效果Ｆｉｇ．５ Ｉｍａｇｅｓ of ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ results ｏｆ ｄｉｆｆｅｒｅｎｔ ｓａｍｐｌｅ ｒａｔｅｓ ｗｉｔｈｏｕｔ ｒｅｄｕｃｉｎｇ ｒａｎｋ图６ 运行时间与采样率关系图Ｆｉｇ．６ Ｒｅｌａｔｉｏｎ curve between ｒｕｎ－ｔｉｍｅ and ｓａｍｐｌｅ ｒａｔｅs３ 结 语利用奇异值分解法提取人脸图像特征，并进行降维分析，在不影响图像质量前提下，运用矩阵填充技术重构人脸图像，利用计算机模拟，分析实验数值结果表明，重构效果较好，运行时间较短． 对人脸识别的研究工作具有一定的指导意义和参考价值．