低秩恢复算法(图像去噪)_米米米米粒口红_新浪博客

2024-02-11 13:20

本文主要是介绍低秩恢复算法(图像去噪)_米米米米粒口红_新浪博客,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

声明:本博客为整料整理,引用的地方均有注明。如需转载,请注明出处!

低秩矩阵恢复算法

 

概述

近几年,低秩矩阵恢复(LRMR)广泛用于图像处理用途图像恢复,比如去噪、去模糊等。一幅清晰的自然图像其数据矩阵往往是低秩或者近似低秩的,但存在随机幅值任意大但是分布稀疏的误差破坏了原有数据的低秩性。低秩矩阵恢复是将退化图像看做一组低维数据加上噪声形成的,因此退化前的数据就可以通过低秩矩阵来逼近。

B为模糊图像,根据低秩分解有B=I+N,其中I为清晰图像,是低秩的。N为噪声具有稀疏性。

 

低秩恢复算法(图像去噪)

低秩恢复算法(图像去噪)

 

 

[1]

    设在矩阵A中有一个不等于0r阶子式D,且所有r+1阶子式(如果存在的话)全等于0,那么D称为矩阵A的最高阶非零子式,数r称为矩阵A的秩,记作RA)。并规定零矩阵的秩等于0.

求解方法:对矩阵作初等行变换为行阶梯矩阵,其中非零行的个数为矩阵的秩。其物理意义矩阵中的最大不相关的向量的个数。

 

低秩矩阵(低秩)

低秩是指矩阵的秩比较小,而矩阵的低秩性是指矩阵的秩相对矩阵的行数或列数而言很小[2]

由矩阵秩的定义知道,若将图像看成一个矩阵,那么它的基的数量越少,基对应的线性无关向量数量就越少,矩阵的秩就越小。当它远远小于矩阵的大小的时候,图像就是低秩的。低秩矩阵的每行或者每列都可以用其他的行或者列线性表示,这说明这个矩阵包含了大量的冗余信息。利用这种冗余信息可以对确实图像信息进行恢复,可以将多出来的噪声信息进行去除,还可以对错误的图像信息进行恢复[3]

 

图像处理中,rank可以理解为图像所包含的信息的丰富程度,在现实生活中,一张图片大部分是相似的。比如一张大草原的图片

低秩恢复算法(图像去噪)

可以理解为,草原是由很多草组成的,而草是相似的,所以如果全是草,那么这张图所包含的信息量是很少的的,因为可以理解为草是草的复制品。而上图的蒙古包,人,马之类的则可以理解为图片所包含的信息,实际上,相对于只有草的草原图片和有草和蒙古包的草原图片,后者的秩是较高的。也就是说,图片中比较突兀的成分,比如蒙古包,比如人像照片中的红眼亮点,会增加图像矩阵的秩。而现实生活中一张不错的图片的秩其实是比较低的,如果图像的秩比较高,往往是因为图像中的噪声比较严重。比如拍照的时候ISO感光度设置过高造成噪点太过泛滥之类的。所以,图像处理的低秩性其实可以拿来去除照片中的噪点,电影中的雨丝也可以通过低秩表达的方式来去除。

Note:低秩与稀疏。低秩是指矩阵的秩较小,稀疏是指矩阵中非零元素的个数少。如果对矩阵进行奇异值分解,并把其所有奇异值排列为一个向量,那么这个向量的稀疏性便对应于该矩阵的低秩性

 

我们可以利用图像的低秩性来恢复图像,首先构建融合了低秩矩阵先验的模型,再求解这个模型得到低秩的矩阵。这种基于低秩矩阵逼近(LOW-Rank Matrix Approximation,LRMA)的模型称为低秩矩阵恢复模型(LRMR)。目前,LRMR主要有鲁棒主成分分析robust PCA,RPCA)、矩阵补全(matrix completion,MC)和低秩表示(low-rank representationLRP)等三类模式。

 

LRMR

 

假设给定数据矩阵DD=A+E,其中AE未知,但是A时低秩的。分别采用三种模式来求解A

 

鲁棒主成分分析(RPCA

1)经典PCA

经典的PCA来获得最优的矩阵A优化问题如下[6]

 低秩恢复算法(图像去噪)  1

其中,低秩恢复算法(图像去噪)  是子空间的期望维度,低秩恢复算法(图像去噪)  Frobenius范数,使用PCA的前提是假设数据E元素服从独立同分布的高斯同分布。只需对矩阵D进行SVD取前r项便可得到上述优化问题的最优解。

补充知识:F范数、奇异值分解(Singular Value DecompositionSVD

矩阵低秩恢复算法(图像去噪)  Frobenius的范数为低秩恢复算法(图像去噪)

奇异值[4]:设低秩恢复算法(图像去噪)  ,Rank A=r低秩恢复算法(图像去噪)  的特征值为

低秩恢复算法(图像去噪)

则称低秩恢复算法(图像去噪)  ,(i=1,2,…,r)为矩阵A的正奇异值(低秩恢复算法(图像去噪)  称为奇异值)

矩阵低秩恢复算法(图像去噪)  ,它的奇异值分解为

低秩恢复算法(图像去噪)

其中:低秩恢复算法(图像去噪) 低秩恢复算法(图像去噪) 均为正交矩阵,对角矩阵低秩恢复算法(图像去噪),且其对角线元素满足低秩恢复算法(图像去噪),是A的正奇异值。

物理意义[4]:奇异值分解是将矩阵分解成若干个秩一矩阵(矩阵秩为1)之和,用公式表示就是:

                                                        低秩恢复算法(图像去噪)  

其中,低秩恢复算法(图像去噪) ,奇异值往往对应着矩阵中隐含的重要信息,且重要性和奇异值大小正相关。每个矩阵A都可以表示为一系列秩为1的“小矩阵”之和,而奇异值则衡量了这些“小矩阵”对于A 的权重。当我们需要存储高清图片而存储空间不够时,则可以保留奇异值较大的若干项,舍去奇异值较小的项来保证图像的可被识别精度。

Note:图像处理中奇异值的物理意义,参考:https://www.zhihu.com/question/22237507/answer/53804902

 

(2)鲁棒主成分分析

PCA在噪声较小时效果较好,当噪声较大时,即使只有很少部分的数据被干扰,也会使PCA的性能大大降低。针对该问题,Wright等人提出了鲁棒主成分分析,只要噪声矩阵E是足够稀疏的,不管大小都可以恢复出低秩矩阵A。

当E为稀疏的大噪声时,恢复矩阵A是一个双目标优化问题:

      低秩恢复算法(图像去噪)     

通过引入折中因子λ(>0),将双目标问题式(2)转换成如下的单目标优化问题:

       低秩恢复算法(图像去噪)

优化式(3)是NP难的,因此需要对此问题的目标函数进行松弛。将秩最小松弛为核范数的最小化,将零范数松弛为1范数,故问题式(3)松弛到如下凸优化问题[5]

                                                   低秩恢复算法(图像去噪)   

其中,低秩恢复算法(图像去噪)  表示矩阵的核范数,即矩阵奇异值之和。低秩恢复算法(图像去噪)  为1范数,即矩阵每个元素绝对值之和,低秩恢复算法(图像去噪)  是一个正的权重参数,一般取值低秩恢复算法(图像去噪)  。

 

对于RPCA的求解方法主要有迭代阈值算法、加速近端梯度算法、对偶方法以及拉格朗日乘子法等,具体求解步骤参考文献[5]。

补充知识:NP难、松弛、1范数与0范数

NPP:算起来很快的问题
NP
:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对不对
NP-hard
:比所有的NP问题都难的问题

松弛(拉格朗日松弛):

首先,拉格朗日松弛技术是用在优化问题里面(假设是最小化问题),而且一定是有约束条件的优化问题。

假设我们已经知道没有约束条件的优化问题怎么解了。然后对于有约束条件的优化问题,我们想懒一点的话,就可以想想办法怎么把它转化成没有约束条件的优化问题。于是有人就想到,
1.
直接去掉约束条件!
那显然定义域变大了,那得到的最小值肯定不比原来的大。那怎么办?
2.
那就如果不满足某些约束条件,我们就来点惩罚。这个惩罚表现在目标函数上。我们在目标函数上多加一项,如果某些约束条件没有满足,那目标函数就会变大。另外我们也多了一个叫拉格朗日乘子的东西,它也是我们可以动的变量。
这时候最优的结果当然会满足所有约束条件,不然就被罚惨了。

这就是所谓的拉格朗日松弛技术,是把有约束优化问题转化成无约束优化问题的好方法
作者:知乎用户
链接:https://www.zhihu.com/question/21345731/answer/57182129

1范数与0范数

0范数为矩阵A的非零元素个数,1范数低秩恢复算法(图像去噪)

 

 

迭代阈值算法

 将问题(4)正则化,便得到优化问题:

低秩恢复算法(图像去噪)     

使用迭代阈值算法(iterative thresholding,IT)交替更新矩阵A、E和Y。

低秩恢复算法(图像去噪)  ,  时,

低秩恢复算法(图像去噪)   

低秩恢复算法(图像去噪) , 时,

低秩恢复算法(图像去噪)

低秩恢复算法(图像去噪)

                                                        低秩恢复算法(图像去噪)

其中,低秩恢复算法(图像去噪) 

 

矩阵补全【5】

当数据矩阵D含丢失元素时,可根据矩阵的低秩结构来恢复矩阵的所有元素,称此过程为矩阵补全(MC)。

低秩恢复算法(图像去噪)  为集合低秩恢复算法(图像去噪)  的子集,这里 [m]表示集合 {1,2,3....,m}。MC的原始模型可描述为如下的优化问题:

低秩恢复算法(图像去噪)    

其中:低秩恢复算法(图像去噪)  为一线行投影算子

低秩恢复算法(图像去噪)  

对于式(9)问题的求解参照文献[5].

低秩恢复算法(图像去噪)

低秩恢复算法(图像去噪)

 

 

低秩表示[5]

  低秩矩阵表示(LRR)是将数据集矩阵D表示成字典矩阵B(也称为基矩阵)下的线性组合,即D=BZ,并希望线性组合系数矩阵Z是低秩的。为此,需要求解下列优化问题:

低秩恢复算法(图像去噪)   

含义:求解满足约束条件D=BZ下的秩最小的Z

 

将优化问题式(10)进行凸松弛,得到

低秩恢复算法(图像去噪)   

若选取数据集D本身作为字典,则有

低秩恢复算法(图像去噪)    

为了对噪声和野点更加鲁棒,模型扩展为

低秩恢复算法(图像去噪)    

关于上式的求解参照文献[5]

补充知识:基矩阵、凸集、凸函数、凸优化问题、凸松弛

基矩阵:用矩阵形式写出基向量和基,这样的矩阵我们叫它基矩阵

i = | 1 0 0 |

j = | 0 1 0 |

k = | 0 0 1 |

B = | i | | 1 0 0 |

| j | | 0 1 0 |

| k | | 0 0 1 

 

 

凸集

假设我们拥有一个集合C,从中取两个元素低秩恢复算法(图像去噪) ,并有一个实数低秩恢复算法(图像去噪)  如果

低秩恢复算法(图像去噪)

那么我们称集合C为一个凸集,低秩恢复算法(图像去噪) 被称作x,y之间的凸连接。

通过上述定义我们知道,如果一个集合中的任意两个点的线性组合所得到的一系列的点也在该集合中(该亮点之间的连先生的点都在该集合中),那么该集合就被称为凸集。换句话说,凸集不能有洞,不同有任何凹陷。

低秩恢复算法(图像去噪)

凸函数:

一个函数f满足

(1)    它的定义域是凸集

(2)    对于其定义域中的任意两点低秩恢复算法(图像去噪)任意低秩恢复算法(图像去噪)

低秩恢复算法(图像去噪)

那么这个函数f就是凸函数。

我们可以更加直观的去刻画该定义,如果一个函数是凸函数,那么该函数两点的连线必然在该函数图像的上方。

低秩恢复算法(图像去噪)

凸优化问题:

凸优化问题是一种特殊的优化问题。凸优化问题的形式是

低秩恢复算法(图像去噪)             

其中低秩恢复算法(图像去噪)  是凸函数,可行域S是凸集。此外,还有等价形式

                                                            低秩恢复算法(图像去噪)  

                           

其中低秩恢复算法(图像去噪) 和所有的限制函数低秩恢复算法(图像去噪)  都必须是凸函数

对于凸优化问题来说,局部最优解就是全局最优解

 

凸松弛:有些问题本身并不是凸的,解算起来并不方便,但是可以采用一种技术将其转换为凸函数进行解算,凸松弛就是其中一种技术。

 

低秩降噪

带有噪声的图像的模型如下

低秩恢复算法(图像去噪)    

B为含噪的测量矩阵,L为待恢复的低秩矩阵,代表原始数据。N为稀疏矩阵,代表噪声。

根据RPCA的方法,可以得到图像去噪优化问题:

低秩恢复算法(图像去噪)  

对于该问题求解,可采用迭代阈值法、对偶法、朗格朗日乘子法等进行求解。

相关知识

低秩恢复算法(图像去噪)


[1] 同济大学数学系编.工程数学 线性代数 5[M].高等教育出版社,2007.

[2]彭义刚,索津莉,戴琼海等.从压缩传感到低秩矩阵恢复:理论与应用[J].自动化学报,2013,39(7):981-994.

[3] 吴伟伟.基于低秩矩阵逼近的图像恢复方法研究[D],2016.

[4] 李新,何传江.矩阵理论及其应用[M].重庆大学出版社,2008.

[5] 史加荣,郑秀云,魏宗田等.低秩矩阵恢复算法综述[J].计算机应用研究,2013,30(6):1601-1605

[6] Ming,Yan,.Exact Low-Rank Matrix Completion from Sparsely Corrupted Entries Via Adaptive Outlier Pursuit[J].Journal of Scientific Computing,2013,56(3):433-449.

这篇关于低秩恢复算法(图像去噪)_米米米米粒口红_新浪博客的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/699887

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int