基于快速稀疏低秩和鲁棒主成分分析的图像处理算法的研究

图像处理算法的研究

郑宝玉1#李#昂1\"2!1. 南京邮电大学通信学院\"江苏南京210003$ 2. 南京理工大学紫金学院\" 江苏南京210023#摘#要! 实际的稀疏低秩处理图像过程中$ 在视觉显示效果没有很大的差异的情况下$ 算法的时间复杂度是唯一

的一个评价指标。我们发现快速交替极小化# FAST PCP)和鲁棒主成分分析# RPCA)的结合是比较快速、比较有 效的利用CPU的高效稀疏低秩处理图像的方法，并且在无法保证计算机配置的情况下，其运算速度也是最快的。 在课题中,将Steffensen迭代法用于改进FAST PCP,由此得到的结果较普通版本的FAST PCP和RPCA更加好。 关键词! 快速交替极小化\" 鲁棒主成分分析\"稀疏低秩\" 图像处理中图分类号! TP751. 1###文献标识码! A###DOI! 10. 16798Ie. ossn. 1003 90530.2020.02.017引用格式：郑宝玉，李昂.基于快速稀疏低秩和鲁棒主成分分析的图像处理算法的研究[J].信号处理，2020, 36 #2) ! 290 9296. DOI! 10. 16798 Ie. osn. 1003 90530. 2020. 02. 017.$%&%'%()%&*'+,-! Phen0BaoQu， coAn0.Ima0ePeocesson0Ae0oeothm Based on FastSpaesecoSRanY and RobustPCA ( J) . Jou ena eo oS o0na eP eoce s on0， 2020， 36#2)!2909296.DOI!10.16798Ie.osn.100390530.2020.02.017.I+,8%S'*)%.3(8 =58*'3-/+ N,.%A*(U,.-SK,'.%P*1

$,(<,(A$*>9.-SC=Phen0BaoQu1 #coAn01，2#1.Coee0eooTeeecommunocatoons[Inooematoon En0oneeeon0， Naneon0Uno]eesotQooPostsand Teeecommunocatoons，

Naneon0， Joan0su 210003 ， Chona\" 2. Inst otute o oE eect eon oc En0onee eon0and OptoeeecteonocTechnoeo0Q，

Naneon0Uno]eesotQooScoenceand Technoeo0QPoJon Coee0e， Naneon0， Joan0su 210023， Chona)=>.-',)-! ThetomecompeedotQootheae0oeothm ostheoneQe]aeuatoon ondedon thecasethatthe]osuaedospeaQeoectosnot ]eeQdooeeenton theactuaespaeseeoSeanY peoceson0oma0epeoces.Seoond thatthecombonatoon oooastaeteenaton0mono9

moeatoon # FASTPCP) and eobustpeoncopaecomponentanaeQsos # RPCA) osaeeeato]eeQoastand eoocoentSaQtousethe

ho0heQeoocoentspaeseeoS9eanY oma0eootheCPU， and thespeed ooopeeatoon osaesotheoastestShen thecomputeeconoo0u9 eatoon cannotbe0uaeanteed.In thospapee， theSteoensen oteeato]emethod osused toompeo]etheFASTPCP， and theeesuet

osamoeecommon ]eesoon ooFASTPCPand RPCAaeebetee.?%@ 1*'A.! Fastaeteenaton0monomoeatoon\" RobustpeoncopaecomponentanaeQsos\" neueoscoenceand ceasooocatoon tasYs\"

eootseaech technoeo0Q1C 引言在图像分析处理技术中，稀疏低秩(1)具有重要 的研究意义& 而目前存在的问题是，在稀疏性和低 秩性之外，如何更进一步地去发掘和利用数据中潜 在的本质结构，开发快速的、并行的新算法，既能够收稿日期! 2019-12-10\" 修回日期! 2020-03-03提高处理的精确度，又能够提升算法的效能& 综合 目前所提出的各种稀疏低秩的算法来看，较为常见 且有效的评价办法就是其计算效率& 基于此，本文 提出了一种快速稀疏低秩鲁棒主成分分析算法，在 不用考虑计算机处理能力的前提下，可以实现较好 的处理效果，是一种较为高效的稀疏低秩算法(296)&基金项目：国家自然科学基金(61671253)；江苏省高校自然科学基金面上项目(18KJD510004)；江苏省普通高校学术学位研究生科研

创新计划项目(KYLX160661)第2期郑宝玉 等! 基于快速稀疏低秩和鲁棒主成分分析的图像处理算法的研究min || #|| s.( rank#；) %!(=；+#;,#f2912C 相关工作在数字图像或视频的实际应用中$给定的数据 矩阵 (往往是低秩或近似低秩的$但存在随机幅值

当#为稀疏的大噪声矩阵时,问题转化为双目

标优化问题:min# rank# ；),|| # || ° )

;,#s. Z (二；+#任意大但是分布稀疏的误差破坏了原有数据的低 秩性$为了恢复矩阵(的低秩结构$可将矩阵(分

解为两个矩阵之和$即(=;+#其中矩阵;和#未知$但;是低秩的& 当矩阵#的

引入折中因子\",将双目标优化问题转换为单 目标优化问题:min rank#；) +2 || 11| 0 s. Z ；+# 二(;,|表1 是稀疏表示和矩阵低秩分解类比,从中可

以看出其中的一些特征,围绕其可以开展很多相关

元素服从独立同分布的高斯分布时$可用经典的

PCA来获得最优的矩阵；,即求解下列最优化问题:研究(10M5)&表 1#稀疏表示和矩阵低秩分解类比Tab61 #Spaeseeepeeseniaioon and maieoiaoSeank decomposoioon anaaogQSpaese5ecioeDegeneeacQooMeasueeConeedSu ogaieCompeessed SensongEeoeCoecioonLoS-Rank Maieoonesognaacoeaaied sognaaseank#4)Nuclear norm || 4 ||'=+# 4)3 norm || x0 °3 norm || x0〔@= +o@= +o+H@)4= +o+H'=+# 4) +VDomaon TeansooemMoed Sieuciuees')=+# 4) +V'=+# 4) +K( V) +Z3C 理论推导3.1算法在这里使用混合规范(11-17)的办法,混合规范在 遗传学,脑电图和信号处理等应用中的组相关性建 模中具有非常重要的作用,如公式#1)所示:W公式#3)可以计算解决独立的问题,所以可以

进行单因素解算&X(#) = arymin^ | X-- ||；+\"( # || X ||<,i-#) #4)

当4# \") = prvx |H|<,i时，公式# 5 )满足傅里叶

变换 #\")=3X#\")3<,1-#

#5)Ull T,i = D,\"ll>JI T 11)对于此解决方案，我们需要解决与“ 1 -ball”密

其中+ ##WI/是具有非重叠组的混合规范应用于矩

阵形式的数值,)”##&代表不同的群体。切相关的问题,它被定义为:

pvjjj(公式#1)主要贡献是提高计算效率,用于计算投影到?#,1&公式#2)是目前最为先进的搜寻主成分的算法

prvj .Ji #-, #)： = aryminy 11 X-B || F

s.i.373#,1 % #

+,#): =mn^ II*- 11$ s.t. ||*||1 %# #6)

+,oo+31k#sheonk# *, 2##) ) , oo +31 &#其中 0, 1# #&* {

(==#7)# 2)shrink # o, 2 (#) ) = sign # o ) ； max # o -2(#%,

0),2##)是依赖于#的收缩参数& 有几种有效的算

这个?#,1的约束问题已经应用于图公式#3)将 计算时间缩短了 4~14倍。prox(法来寻找这个收缩参数, 如下式:0+1:話 +5%

⑻-,2) : = arymin^^ || X-B ||；+2 ||x||p,i (3 %292信号处理Steensen 第36卷( )0) = ( )0* ) j$

#12)的方法是拟牛顿根查找算法$当导数

的解析表达式不可用时$该算法是有用的& 缺点是

o需要两个功能评估$因此通常比牛顿法更优秀& 给 定函数 *#0%$Steoensen 的原始迭代包括更新&|-maxd 娜 |_#,0) = ｛同(|,p

r #$F

为了确保使用凸优化得到的解是最优解, 将其 与使用迭代法#公式#12)) 所得的解进行对比, 发现

凸优化是最佳解决方案&接着公式#10) 继续讨论, 当 ) ()# #(), 可以得

l>#%# (9)到公式#13)( ) ()) = 由于所涉及的所有分量都是正的$ 这是一个凸 优化问题& 对于每个部分, 可以通过凸优化求得其

局部最大值, 即最优解&/()o % = \" 11< D-PD*I\"3$D-peoe353#$D, ) ()) 3 #13)D*IAlgorithm 1: Proposed MethodInput: matrix gj n-31( < D,)o %ll 8>0

( 10 %B,t, maxlter, tolerance1 if ||B||oo, 1< t then对公式#10% 凸优化求最优解得到下式!

mon * )0% = 2 return B\"3 Compute ak = ||shrink(bk,T)||l for each row ofB.DefineY = maxk(ak)3$D-peoe353#$D, )0%3D*I4 for k= 1 : maxlter do5 Prune the rows of B that have 11 -norm less than y6 Obtain f(y) as defined in (13)7 if|f(y)| < tolerance then0#11%由公式#9% 求和, 可以获得公式#10%, 整个算法

subeectto )#4

流程如图 1 所示& 下面介绍的所有测试都是使用运 行在 Inteeo797700ha CPU#4 核'3.50 TWe'16 TA RAM 上的单线程 Mateab 代码计算的&

8 break9 Update y using Steflensen method10 end设0(是通过公式#11 % 求出的最小值, 如果 )(

#4@dom( 11 Obtain A as defined in (12) using the obtained 12 Return B-A丫f)，且 f(x( ) = 0inf-()o* ).则o * 是其全局 #4图1算法伪代码Fig. 1 The pseudo code of the algorithm

最小点, 即 )0* # ae0mon ( )0) , )0# 4&表2#对不同尺寸矩阵的模拟结果和三种测试方法进行了比较&将错误(\\f)，迭代次数(NI.)和它们的运行时间# Time(s))作为评价指标

Tab62#Compaees the s omueat oon eesuetsoodooeeentsoeemateocesSoth thetheeetestmethods6

\\eoe# \\e6) , oteeatoon tomes #NI6) And theoeeunnon.tome # Tome # s) ) asan e]aeuatoon ondedMateodSoeeIspaesotQSea(6)#! )060001 I16022000*100060005 I46130600 1 0 I765 1060001 I1637\\e6N6I6Tome s)3 640\\91 196646044621 650 \\91 013625640\\9101465\\e62660\\9121 640 \\91 2PeoposedPeoposedjpeunon.N6I6Tome s) Speedup\\e6N6I6Tome s) Speedup964066414696I6312660\\912964062711631612160736THF61D1 640 \\91 21 630 \\91 21 660 \\91 2116311106612116106844698563646411621\\9121 662 \\91 25000*200060005 I5659060010I10603173640\\91011697680\\91017694600\\91011642610\\90914651 670 \\91 0136991366714612767411106612116106821627263536323623H6\\HF61DF63T1069956617690\\9126620 \\91 38600\\9126600\\9129680\\9147600\\9142680\\912264426575654686060001 I16629642\\914131211647697769936F]36I3F6THF6\\D131211645671566456792665910000*300060005 I666060010I11688060001 I464229603376095690\\9142640\\912561566413630\\91015675620\\910768133684316643269910000*3000060005 I1665806001 I28652060001 I66182600\\90920191666391666253650\\9141364812628126283640\\91413648266569650\\9141266269660\\914H6DHH6D3F6]366255698191726467600\\90920613606321 620 \\91 02660\\90819612680\\9145660\\9141 61 0 \\91 32680\\91413643746619912635706785828683125640\\91413643576451 600 \\91 31263559673662710000*8000060005 I2367236661H61TH616613567206001 I39697610\\910183576635600\\9141169870616265600\\914116986265第2 期 郑宝玉等!基于快速稀疏低秩和鲁棒主成分分析的图像处理算法的研究

293##如表2 所示$分别对不同尺寸矩阵的模拟结果

本文的算法，可以看出将本文算法与pvming结合在

和三种测试方法进行了比较& 这三种方法分别是 Sea$peoposed 以及 peoposed +peunong$ 1eoposed 就是

不同的尺寸下，无论在错误（Ef %，迭代次数（NI.） 还是它们的运行时间# Tome# s% %上，都具有优势&表 3#算法对于初始点 ,0 的影响Tab63#Theon-auenceo-iheaagoeoihmon iheonoioaapooni)0-IspaesoiQ#! %060001 I1602060002 I1692060003 I2668060004 I3640060005 I4617060006 I4694060007 I5653060008I6628060009I6689Starting v( zero

numoiee12.511.911.911.711.511.311.111.111.011.0iome# s%1.1Siaeiongai ,09.49.710.010.211.311.311.111.111.011.01.11.11.11.11.11.01.11.01.1numoiee#-25!%#-20!%iome#s%0.630.710.770.861.111.061.051.051.041.06#-43!%#-35!%#-29!%#-20!%#4!%#0!%#0!%#0!%#0!%#0!%#-17!%#-13!%#-2!%#0!%#0!%#0!%#0!%#0!%060010 I7653##如表3所示，可以看出算法从）0点比从零点开始运算迭代次数最多可以下降25!，而时间减少了

4C应用本算法的实例效果

为了验证改进算法的可实施性，进行了实例的

最多43!，可见算法在确定了）0的条件下，性能更 加优异&测试，如图2 是低秩矩阵图像去光照影响恢复的应

用， 通过本方法快速找到了显著性特征， 并快速标

公式# 13% 是当整个 稀 疏化矩阵带 入到公式#10% 中得到的式子&Y

注出来，然后通过去光照算法进行恢复&X

E58 images of one person under varying lighting:Y图2#图像去光照影响恢复

Fog62#Imagedeaoghionga-eciseesioeaioon294信号处理提高了效率&第 36 卷##图 3 是应用稀疏低秩特性最多的前景背景分离

的应用$应用本算法可以通过提高运算速度对高帧 如图 4 所示是本算法应用于图像去标签$其速

率视频进行分析$解决了高帧率视频掉帧的问题$率比目前最快的PCP算法快了 10倍。Surveillanee video200 frames,144 x 172 pixels,Video D = Low-rank appx.A+ Sparse errorESignificant foreground motio n」 1D图 3# 背景建模Fo.63#AacY.eound modeeon.Input: images with user-provided tags Output; images with refined tagsPROBLEMD

User-provided tag matrix

A

Low-rank matrix

ESparse error matrix图4图像去标签Fo.64#Ima.eunta..on.第2期郑宝玉 等! 基于快速稀疏低秩和鲁棒主成分分析的图像处理算法的研究表 4#对不同尺寸图片和三个应用场景进行了比较&295将错误(Err.)，迭代次数(NI.)和它们的运行时间# Tme(s))作为评价指标Tab. 4 Compares pictures of dOferent sizes with three application scenarios. Error ( Err.),oieeaioon iomes( NI6) And iheoeeunnongiome ( Tome ( ) ) asan eeaauaioon ondeiMatrin

Size

(sparsity (% %

0 0001 s1 020 0005 s4 130 0010 s7 510 0001 s1 37图像去光照影响恢复

Err. 2 9@E-11N . I . Time# s)

背景建模

Err. 2 60E-12图像去标签Err.

N . I. Time# s) Speedup0 20 @0 @14 6N . I . Time# s) Speedup 9 40 49 64 144 214 42I 13 54 D5 ]4 14 32 50E-129 41 40E-1011 53 40E-1013 53 70E-10131 40E-1211 31 21E-121 21 01 42E-1211 31 33E-12114 9115 313 @913 71 62E-12 10 62 33 23 3704-7101 62E-12 10 6@ 01E-121 22 42 511 05 65 5FASTPCP[RPCA0 0005 s5 590 0010 s10 032 40E-1012 94 @0E-1015 97 90E-12121214 16 20E-1311 16 02E-1211 1##由表4可以看出，算法用于不同尺寸图片和三 个应用场景上都比普通的 FAST1C1[ R1CA 性能

CaoJongang， CangGuoioan， CangEoQun Sueeacedeeeci

好的多&deiecioon oeean baadebased on RPCA and eosuaasognoeo- cance[ J] JouenaaoeCaeiogeaphQ， 2019(4)： 704-710 ( on

5结论快速稀疏低秩和鲁棒主成分分析(RPCA)的结 合是比较快速'比较有效的稀疏低秩处理图像的方 法，并且在无法保证计算机配置的情况下，其运算

速度也是最快的，通过实验证明在大多数情况下， 所提出的方法可以提供5~6倍左右的速度，最高可

Chonese)[4] #叶学义， 罗宵晗， 王鹏， 等 基于非凸低秩分解判别的叠加线性稀疏人脸识别[J].中国图象图形学报，

2019(@)： 1327-1337CeEueQo， Lanieen， XangPeng， eiaa Supeeomposed

aoneaespaeseeaceeecognoioon based on non-coneeiaow-

eank decomposoioon[ J] ChonaImageand Geaphocs， 2019

(@)： 1327-1337 ( on Ch one se)[5] #刘明君， 董增寿， 邵贵成 基于改进的四叉树分解多达10-14倍。在稀疏条件下，解的精度至少比其他 方法的水平高一个数量级，并且在多个应用测试中

都取得了不错的效果&参考文献(1 )#Fu H， XangB， Lou H P OnaoneR1CAon Backgeound

聚焦图像融合算法研究[J].科技通报，2019 (4 )：

152-156Lou Mongjun， DongPengshou， ShaoGuocheng Reseaech

on muaio-eocusomageeusoon aagoeoihm based on ompeoeed

Modeaong! 5oaume I(M) !1eoceedongsoe201@ Chonese

(2) #孙志鹏， 王永丽， 王淑琴， 等 视频背景分离中一种auadieeedecomposoioon[ J] Scoenceand TechnoaogQBua-

aeion， 2019 (4)： 152-156 ( on Chonese)InieaogeniSQsiemsConeeeence， 2019[ 6] #MokamoS， BawamueaA， IogunoC Resoduaadeum sound

esiomaioon eoeRPCA song ong eo oce e iieac ioon[ C] !Asoa-

新的非凸秩近似的RPCA模型[J].山东科技大学学 报! 自然科学版， 2019(4)!@3-91Sun Phopeng， XangCongao， XangShuaon， eiaa Anew non-coneei-eank appeoiomaieRPCAmodeaon eodeoback-

[7 ]

pacoeocSognaa[ Ineoemaioon PeocesongA socoaioon Sum- m oi[Conee eence IEEE， 201@Wange S, Ke wen X, Pu L. Reyularized weighted incom-paeieeobusipeoncopaacomponenianaaQsosmeihod and ois

appaocaioon on eoiongieajecioeQoewoeeaessensoeneiwoek

geound sepaeaioon( J) JouenaaoeShandongVnoeeesoiQoe

Scoenceand TechnoaogQ ! NaiueaaScoenceEdoioon， 2019

(4) ! @3-91 ( on Chonese)[3]

nodes[ J ] JouenaaoeCompuieeAppaocaioons， 201@：1709-1714+1720[ @] # Xu C， Wu P， ChanussoiJ， eiaa JooniReconsieucioon

曹锦纲，杨国田，杨锡运.基于RPCA和视觉显著性

的风机叶片表面缺陷检测[J].图学学报，2019(4)：and AnomaaQDeiecioon Feom CompeesoeeHQpeespecieaa

296信号处理Imayes Using Mahalanobis Distance-Reguladzed Tensor

RPCA(J) 6I\\\\\\Tean4actoon4on Teo4coenceand Remote Sen4on.$ 2018$ PP#99%! 1K126第 36 卷Detectoon on RTAKD 5odeo4U4on.Teaph Re.ueaeoeed

SpatootempoeaeRPCA( C) !InteenatoonaeConoeeenceon ImK a.eAnaeQ4oand Peoce4on.K20176Speon.ee， Cham， 20176(9)#Toan M$ Xan.X$ NoeL$ etae6Reco.notoon oo.eochemoK

caeanomaeoe4ba4ed on .eo.eaphocaeQSeo.hted ee.ee4K

( 17) Tan CW， Chen J， Chau LP6\\d.eKpee4ee]on.eaon eeK

mo]aeooeeo.htooeeeoma.e4ba4ed on RPCA( C) !2017

22nd InteenatoonaeConoeeenceon Do.otaeSo.naePeoce4K on.#DSP%6I\\\\\\， 201764oon! A ca4e4tudQaceo4theboundaeQaeea4ooChona

and Mon.oeoa( J)6Jouena eooTeochem oca e\\dp eoeat oon$ 2018$ 1906( 18) 胡正平， 赵淑欢6 分辨性分解块稀疏表示遮挡人脸识

(10 ) Shen Y$ Xu W$ Lou X6An aeteenaton.monomoeatoon

method ooeeobu4tpeoncopaecomponentanaeQ4o( J) 6MptoK moeatoon Method4and SootSaee$ 2018#591 % ! 1K266(11 ) TaoS$ LoA$ LoN$ etae6ANo]eeAppeoach ooeMo]on.

XondoSSoeeSeeectoon ut oeoeon.eecueo]e PCA(C)!2018 Chone4eConteoeConoeeence$201867! 710K7156(12) eon K$ Sun L$ Lou A$ etae6ARobu4tChan.eKPoontDeK

tectoon Method bQ\\eomonaton.SpaeeNooe4oeom Tome Seeoe4(C)!2018 I\\\\\\Thoed InteenatoonaeConoeeenceon

DataScoenceon CQbeepace #DSC%6I\\\\\\$ 20186(13] 于雯越，安博文，赵明.基于光流法与RPCA的红外

运动目标检测( J) 6 现代计算机#专业版% $ 2018#23%!

66K716Yu XenQue， An AoSen， PhaoMon.6Inoeaeed mo]on.taeK

.etdetectoon ba4ed on optocaeoeoS method and RPCA

( J) 6 Modeen Computee# Peooe4oonae\\dotoon%， 2018 #23 % ! 66K716 # on Chone4e%( 14) Sun X， Du e6TeaphKRe.ueaeoeed Fa4tand Robu4tPeonK

copaeComponentAnaeQ4o ooeWQpeepecteaeAand SeeecK

toon( J) 6 I\\\\\\Tean4actoon4on Teo4coenceand Remote Sen4on.， 2018， PP#99%! 1K116( 15) Jeon.IY， LeeK6Son.on.5ooceSepaeatoon U4on.RPCA

Soth Xeo.hted y y eF - 1 y y Knoem ( C ) ! Inteenatoonae

Conoeeenceon Latent5aeoabeeAnaeQ4oand So.naeSepaK

eatoon6Speon.ee， Cham， 20176( 16) Ja]ed S， AouSman4T， SuetanaM， etae6Mo]on.MbJect别算法( J) 6 信号处理， 2014， 30#2%! 214K2206Wu Phen.pon.， PhaoShuhuan6 Thedoton.uohon.deKcompo4otoon beocY 4pae4emean4thebeocYoaceeeco.notoon

ae.oeothm ( J) 6 Jouena eooS o.na ePeoce 4on.，2014 ， 30#2%! 214K2206 #on Chone4e%作者简介##郑宝玉#男， 1945 年生， 1969 年和

1981 年分别获得南京邮电大学的学士学

位和硕士学位& 从那以后， 一直从事信 号和信息处理的教学和研究& 目前是南

京邮电大学教授'博士生导师& 研究领域 涵盖了智能信号处理'无线网络和信号等领域\\Kmaoe!ebQfnJupt6edu6cn李#昂#男， 1986 年生， 安徽人&

副教授， 博士， 正在参与在研国家自然科 学基金面上项目 2 项， 主持省部级科研 课题 1 项'市厅级科研项目 2 项， 发表学 术论文近 20 篇， 其中 SCI 检索 3 篇， \\ 检索 3 篇， 申请发明专利 2 项， 实用新型

专利 2 项， 近三年来开展了+机器学习专项研究与推广,“5G网络关键技术”、“基于深度学习的基站视频识别分割”等研究\\Kmaoe! eoan.878fnJu4t6edu6cn