含缺失成分的矩阵的广义低秩逼近及其在图像处理中的应用.pdf

第 27 卷 第 11 期 计算机辅助设计与图形学学报 Vol. 27 No.11 2015 年 11 月 Journal of Computer-Aided Design 国家“八六三”高技术研 究发展计划(2014AA015202); 中央高校基本科研业务费专项基金(2013JBZ003); 教育部博士点基金(20120009110008); 教育部新世纪 优秀人才支持计划(NCET-12-0768). 李 璐(1989), 女, 硕士研究生, 主要研究方向为低秩矩阵的恢复与填充; 董秋雷(1980), 男, 博士, 副研究员, 主要研究方向为三维计算机视觉、模式分类; 赵瑞珍(1975), 男, 博士, 教授, 博士生导师, 主要研究方向为小波 变换及其应用、图像与信号处理算法. 含缺失成分的矩阵的广义低秩逼近及其在图像处理中的应用 李 璐1), 董秋雷2), 赵瑞珍1) 1) (北京交通大学计算机与信息技术学院信息科学研究所 北京 100044) 2) (中国科学院自动化研究所模式识别国家重点实验室 北京 100190) () 摘 要: 针对在许多实际应用中数据以矩阵形式而非向量形式存在的问题, 重点讨论含缺失成分的矩阵低秩逼近问 题的广义版本, 即如何对一组含缺失成分的矩阵进行低秩逼近. 首先构造一个最优化问题来表达原始的广义低秩逼 近问题, 该最优化问题最小化输入矩阵组中已知成分的总重构误差; 然后提出了一种迭代优化算法来求解上述的最 优化问题; 最后给出详细的算法分析. 大量的模拟实验与真实图像实验结果表明, 文中算法具有较好的性能. 关键词：广义低秩逼近; 缺失成分; 重构误差; 迭代优化算法 中图法分类号：TP391 Generalized Low-rank Approximations of Matrices with Missing Components and its Applications in Image Processing Li Lu1), Dong Qiulei2), and Zhao Ruizhen1) 1) (Institute of Information Science, School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044) 2) (National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing 100190) Abstract: Considering that data used in many applications are intrinsically in matrix form rather than in vector form, this paper focuses on the generalized version of the problem of a low-rank approximation of a matrix with missing components, i.e. low-rank approximations of a set of matrices with missing components. This generalized problem is formulated as an optimization problem at first, which minimizes the total reconstruction error of the known components in these matrices. Then, an iterative algorithm is designed for calculating the generalized low-rank approximations of matrices with missing components, called GLRAMMC. Finally, detailed algorithmic analysis is given. Extensive experimental results on synthetic data as well as on real image data show the effectiveness of our proposed algorithm. Key words: generalized low-rank approximation; missing components; reconstruction error; iterative algorithm 矩阵低秩逼近问题是模式识别领域一个重要 问题1-10. 近年来, 含缺失成分的矩阵低秩逼近问 题在许多应用中得到广泛研究, 例如物体建模1、 结构重建(structure from motion, SFM)2-6、运动分 割7、图像去噪8等, 但在这些应用中数据矩阵往 往是不完整的. 对于一个含缺失成分的矩阵, m n A 计算 A的低秩逼近通常通过求解下面的最小化问题, 2066 计算机辅助设计与图形学学报 第 27 卷 即计算A中相应已知成分的重构误差最小值 T , min U V WAUV; 其中, 表示任意矩阵范数, 表示 2 个矩阵的 哈达玛积(逐项的乘积), m n W代表一个指示矩 阵(若 , i j A已知, , i j W=1, 否则 , i j W=0),U表示一个 尺寸为m k的矩阵, V表示一个尺寸为nk的矩 阵, min,km n. 针对该问题, 文献1, 3, 6, 11-18中提出了大 量优化算法. 例如, Shum 等1在计算机视觉中首次 描述了这个问题并提出了一种数值算法; Okatani 等 6就含缺失成分的低秩矩阵逼近问题研究了 Wiberg 算法19的数值实现; 文献3针对含缺失成 分的大尺寸矩阵的低秩分解问题提出了 2 种 LM(Levenberg-Marquardt)算法; Buchanan 等11对 基于 Frobenius 范数的矩阵低秩逼近算法进行了综 述. 此外, 文献13将含缺失成分的矩阵低秩逼近 问题表达为一个 L1范数下的最小化问题, 并通过 迭代凸规划进行求解; Eriksson 等12基于线性规划 的可微性提出一种 1 L范数下的矩阵低秩逼近算法, 该算法可以看作是一种泛化的 Wiberg 算法; 文献 14提出了一种基于核范数正则子的大尺寸矩阵 填充算法; 文献16基于自适应离群点追踪提出了 一种精确的低秩矩阵恢复算法; 文献17在证明了 广义误差存在下限的情况下建立了一个概率分布 模型, 来恢复含未知输入的图像数据. 值得注意的是, 为了处理一组数据, 例如在 SFM 问题中的一组轨迹, 大部分已有算法将每个 数据转换成一个向量, 然后计算数据矩阵的低秩 逼近. 然而在许多情况下, 数据是以矩阵形式存在 的, 例如图像数据, 如果将其转换成向量再进行处 理, 则最终得到的处理结果可能会损失原始图像 中的一部分结构信息. 因此, 近年来研究者也针对 如何直接处理矩阵数据展开了相关研究. Yang 等20 提出了针对矩阵形式数据的二维主成分分析方法 (two-dimensional principal component analysis, 2DPCA), 实验结果表明, 与针对一维向量数据的 传统主成分分析方法(principal component analysis, PCA)相比, 2DPCA 在人脸分类方面具有更好的性 能. Ye21针对矩阵数据低秩表达问题, 提出一种针 对无缺失成分的广义低秩逼近算法. 值得注意的 是, 在许多涉及矩阵数据的实际应用(如图像去 噪、图像分类)中, 数据有时是不完整的(如局部被 遮挡的图像、含有冲击噪声的图像等), 上述算法 均无法处理这些含缺失成分的数据. 这促使我们 考虑如下更一般的广义低秩逼近问题: 如何直接 计算一组含缺失成分矩阵的低秩逼近, 而不是把 它们转换成向量再进行处理? 换句话说, 如何找 到2个变换矩阵和一组低维矩阵, 使得每个低维矩 阵和 2 个变换矩阵的乘积逼近相应的原始矩阵? 本文首先构造一个新的优化问题来表达上述 低秩逼近问题. 对于输入的一组矩阵形式数据, 本 文不改变其数据形式, 将这组原始数据看作一组 数据矩阵; 然后提出一种用于计算含缺失成分的 矩阵的广义低秩逼近算法(generalized low-rank approximations of matrices with missing components, GLRAMMC). 当所有的数据矩阵是完整的(无缺失 成 分 ) 时 , GLRAM(generalized low-rank appro- ximations of matrices)算 法 21可 以 有 效 地 计 算 Frobenius 范数下矩阵的最优低秩逼近; 但当矩阵 缺失了一些成分时, 该算法将无法获得其最佳的 低秩逼近. 因此, GLRAM 算法可以看作是本文提 出的 GLRAMMC 算法在所有矩阵成分已知情况下 的一种特殊情况. 1 GLRAMMC 算法 1.1 基本问题 为了便于下文的讨论, 介绍3个基本问题的解法. 问题 1. 为了计算一组含缺失成分的矩阵 m n i A(1,2,iN)的低秩逼近, 将这些矩阵 存储成一个矩阵 mnNv A, 其第 i 个列向量 i a是 i A每一列的级联; 然后将 v A因式分解成一个列向 量正交的左变换矩阵 mnr U(min(,)rmn N) 和一个低秩矩阵 T . r N M 所得到的 U 的列向 量张成一个 r 维空间, 且 M 的第 i 个行向量可以看 作是对 i A的 r 维表示. 相应地, 对一组矩阵的低秩逼近问题被转换 成对单个矩阵的低秩逼近问题. 在数学上, 可以构 造如下最小化问题( v W是指示矩阵, 其第i列是 i W的列级联, r I是r维的单位矩阵), 即最小化 v A中已知成分的重构误差 2 T I ,F T min s.t. vv r E U M WAUM U UI (1) 求解. 值得注意的是, 式(1)中函数 I 与引言 中的目标函数具有相同的形式. 因此, 许多 第 11 期 李 璐, 等: 含缺失成分的矩阵的广义低秩逼近及其在图像处理中的应用 2067 现有的用于求解引言中的目标函数的算法均可 以用在这里, 如交替最小二乘算法(alternated least squares, ALS), Wiberg 算法和高斯-牛顿算法. 尽管 由这些算法所得到的解U未必正交, 不过可以再 使用奇异值分解计算U的正交解. 在第 3 节中, 问 题 1 的 ALS 算法会与本文算法一起在相同的数据 上进行测试, 记为 P-I-ALS. 问题 2. 如果不改变原始数据 i A(1,2,iN) 的矩阵形式, 将这组原始数据看作一组数据矩阵, 找到一个左正交变换矩阵 m r U和一组低秩矩 阵 r n i M, 使矩阵U和 i M的乘积逼近 i A, 在 数学上, 可以构造如下的最小化问题( i W是 i A的 指示矩阵), 即最小化 i A中已知元素的重构误差 1 2 II F , 1 T min s.t. N ii N iii i r UM WAUM U UI (2) 求解. . 式(2)可写成 1 2 II F , T min s.t. N ii aaa r UM WAUM U UI (3) 其中, 12aN AA AA, 12aN WW WW, a M 12N M MM. 显然, 目标函数 II 和引言中的目标函数具 有相同的形式. 因此,