矩阵的奇异值分解在数字图像处理的应用
矩阵的奇异值分解在数字图像处理的应用浅析
学 院: 专 业: 姓 名: 学 号:
目 录
一、绪 论 ................................................................................................................................. - 1 - 二、数字图像处理简介 ............................................................................................................. - 2 - 三、矩阵的奇异值分解原理 ..................................................................................................... - 4 -
3.1 矩阵的奇异值 ............................................................................................................. - 4 - 3.2 矩阵的奇异值分解(SVD) ....................................................................................... - 4 - 四、奇异值分解的图像性质 ..................................................................................................... - 5 - 五、图像的奇异值分解压缩方法 ............................................................................................. - 7 -
5.1 奇异值分解压缩原理分析 ......................................................................................... - 7 - 5.2 奇异值分解压缩应用过程 ......................................................................................... - 8 - 六、小 结 ................................................................................................................................. - 9 -
一、绪 论
目前,随着科学技术的高速发展,现实生活中有大量的信息用数字进行存储、处理和传送。而传输带宽、速度和存储器容量等往往有限制,因此数据压缩就显得十分必要。数据压缩技术已经是多媒体发展的关键和核心技术。图像文件的容量一般都比较大,所以它的存储、处理和传送会受到较大限制,图像压缩就显得极其重要。当前对图像压缩的算法有很多,特点各异,类似JPEG 等许多标准都已经得到了广泛的应用。奇异值分解(Singular Value Decomposition ,SVD) 是一种基于特征向量的矩阵变换方法,在信号处理、模式识别、数字水印技术等方面都得到了应用。由于图像具有矩阵结构,有文献提出将奇异值分解应用于图像压缩[2],并取得了成功,被视为一种有效的图像压缩方法。本文在奇异值分解的基础上进行图像压缩。
二、数字图像处理简介
首先,简单介绍一下数字图像处理。人们对数字图像都应该很熟悉。我们在计算机上
看到的图像,数码相机拍到的图像,雷达图像,人体MRI图像等等。数字图像处理是指用计算机对图像进行分析处理,以达到所需结果的技术。
图像处理的内容十分广泛,具体而言,可以分为:图像获取、图像增强、图像复原、
图像压缩、图像分割等。这些内容都是基于矩阵的处理得到的。下面举例介绍几个重要的应用。
图像获取是图像处理的第一步。图像获取有很多方法,最常用的方法就是用传感器如
数字摄像机、扫描仪等设备得到。
数字图像处理的定义:我们可以将一幅图像定义为一个二维函数f(x,y),这里x和y是空间坐标,在空间坐标(x,y)上的幅值f称为该点图像的强度或灰度。对于数字图像而言,x,y和幅值f都是有限的、离散的。这样一幅图像就可以用一个二维函数来表示。模拟图像不利于计算机处理,所以我们常常将模拟图像转换为数字图像。模拟图像转化为数字图像的方式是:取样和量化。我们将x,y坐标值离散化称为取样,将幅度值f离散化称之为量化。经过取样和量化的图像是一幅数字图像。数字图像的质量很大程度上取决于取样和量化的取样数和灰度级。取样和量化的结果是一个实际的矩阵。这个矩阵可以表示为
f(0,0)f(1,0)
f(x,y)
f(m1,0)
更一般的矩阵表达方式为:
f(0,1)f(1,1)f(m1,1)
f(0,n1)f(1,n1)
f(m1,n1)mn
a0,0aA1.0
am1.0
a0,1a1.1am1.1
a0,n1a1.n1
am1.n1mn
图像压缩是数据压缩技术在数字图像上的应用,它的目的是减少图像数据中的冗余信息从而用更加高效的格式存储和传输数据。图像数据之所以能被压缩,就是因为数据中存在着冗余。图像数据的冗余主要表现为:图像中相邻像素间的相关性引起的空间冗余;图像序列中不同帧之间存在相关性引起的时间冗余;不同彩色平面或频谱带的相关性引起的
频谱冗余。
图像压缩可以是有损数据压缩也可以是无损数据压缩。无损图像压缩方法主要有行程长度编码、熵编码法如LZW;有损压缩方法主要有变换编码,如离散余弦变换(DCT)或者小波变换这样的傅立叶相关变换,然后进行量化和用熵编码法压缩和分形压缩(fractal compression)。
图像矩阵A的奇异值(Singular Value)及其特征空间反映了图像中的不同成分和特征。奇异值分解(Singular Value Decomposition ,SVD) 是一种基于特征向量的矩阵变换方法,在信号处理、模式识别、数字水印技术等方面都得到了应用。我们主要讨论奇异值分解在图像压缩上的应用。
三、矩阵的奇异值分解原理
3.1 矩阵的奇异值
设ACr数。且设
mn
HH,rrank(A),i是AA的特征值,i是AA的特征值,它们都是实
12rr1r2m0
12rr1r2n0
则特征值
i与i之间的关系为:ii0,(i1,2,,r)。
mnHHiiACr设, AA的正特征值i,AA的正特征值i,称i,
(i1,2,,r)是A的正奇异值,简称奇异值。若A是正规矩阵,则A的奇异值是A的
非零特征向量的模长。
3.2 矩阵的奇异值分解(SVD)
mn
ACr若,12r是A的r个正奇异值,则存在m阶酉矩阵U和n阶酉
矩阵V,满足:
0H
AUDVHUV00
其中,diag(1,2,,r),为奇异对角阵。U满足UAAU是对角阵,V满足
H
H
VHAHAV是对角阵。U的第i列为A的对应于i奇异值对应的左奇异向量,V的第i列
为A的对应于正交。
mnmr
ACUUA12rrrrr若,是的个正奇异值,则总有次酉矩阵,
i奇异值对应的右奇异向量。它们的每一列均为单位向量,且各列之间相互
VrVrnr满足:AUrVrH,其中diag(1,2,,r)。
奇异值分解是一种基于特征向量的矩阵变换方法。奇异值分解是现代数值的最基本和最重
要的工具之一。
四、奇异值分解的图像性质
任意一个AC
mn
矩阵的奇异值(1,2,,r)是唯一的,它刻画了矩阵数据的分布
mn
特征。直观上,可以这样理解矩阵的奇异值分解:将矩阵AC它将m维空间的点映射到n维空间。AC
mn
看成是一个线性变换,
经过奇异值分解后,这种变换被分割成3个
部分,分别为U、和V,其中U和V都是标准正交矩阵,它们对应的线性变换就相当于对m维和n维坐标系中坐标轴的旋转变换。
若A为数字图像,则A可视为二维时频信息,可将A的奇异值分解公式写为:
AUDV
u
H
rr
0HUVAiiuiviH
i1i100
其中,i和
vi分别是U和V的列矢量,i是A的非零奇异值。故上式表示的数字图像A可
H
Auvii以看成是r个秩为1的子图叠加的结果,而奇异值i为权系数。所以i也表示时频信
息,对应的
ui和vi可分别视为频率矢量和时间矢量,因此数字图像A中的时频信息就被分ui和vi构成的视频平面中。
解到一系列由
由矩阵范数理论, 奇异值能与向量2-范数和矩阵Frobenious-范数(F-范数)相联系。
12AX
A
1
2
2
X2)
1
F
r
2
amn(i2)2
i1mn
若以F-范数的平方表示图像的能量,则由矩阵奇异值分解的定义知:
A
2F
r
0H0H
tr(AA)tr(VUUV)i2
i10000。
H
H
也就是说,数字图像A经奇异值分解后,其纹理和几何信息都集中在U、V而中的奇异值则代表图像的能量信息。
之中,
性质1:矩阵的奇异值代表图像的能量信息,因而具有稳定性。
mn
AC设,BA,是矩阵A的一个扰动矩阵。A和B的非零奇异值分别记
为:11121r和21222r。且rrank(A),1是的最大奇异值。
则有:
1i2iAB22
1
。
由此可知,当图像被施加小的扰动时,图像矩阵的奇异值变化不会超过扰动矩阵的最大奇异值,所以图像奇异值的稳定性很好。
性质2:矩阵的奇异值具有比例不变性。
设AC的奇异值为
mn
,矩阵A的奇异值为
i(i1,2,,r),rrank(A),矩阵kA(k0)
i(i1,2,,r)。则有:k(1,2,,r)(1,2,,r)。
mn
性质3:矩阵的奇异值具有旋转不变性。
设AC
,矩阵A的奇异值为
i(i1,2,,r),rrank(A)。若Ur是酉矩阵,
则矩阵UrA的奇异值与矩阵A的奇异值相同:
AAHi2ErA(UrA)Hi2E0
。
性质4:设AC
mn
,rank(A)rs。若sdiag(1,2,,s),
AsiuiviH
i1
s
,
rank(As)rank(s)s
minAB
所以可得:
AAS
F
F
BCmns21s22r2
mn
ACss上式表明,在F-范数意义下,是在空间(秩为s的mn维矩阵构成的线性空
间)中A的一个将秩最佳逼近。因此可根据需要保留s(sr)个大于某个阈值的其余rs个小于阈值的
i而舍弃
i且保证两幅图像在某种意义下的近似。
这就为奇异值特征矢量的
降维和数据压缩等应用找到了依据。
五、图像的奇异值分解压缩方法
5.1 奇异值分解压缩原理分析
用奇异值分解来压缩图像的基本思想是对图像矩阵进行奇异值分解,选取部分的奇异值和对应的左、右奇异向量来重构图像矩阵。根据奇异值分解的图像性质1和4可以知道,奇异值分解可以代表图像的能量信息,并且可以降低图像的维数。如果A表示n个m维向量,可以通过奇异值分解将A表示mn为个r维向量。若A的秩远远小于m和n,则通过奇异值分解可以大大降低A的维数。
对于一个nn像素的图像矩阵A,设AUV
H
,其中,diag(1,2,,r)。
按奇异值从大到小取k个奇异值和这些奇异值对应的左奇异向量及右奇异向量重构原图像矩阵A。如果选择的kr,这是无损的压缩;基于奇异值分解的图像压缩讨论的是kr,即有损压缩的情况。这时,可以只用k(2n1)个数值代替原来的nn个图像数据。这
k(2n1)个数据分别是矩阵A的前k个奇异值, nn左奇异向量矩阵U的前k列和
nn 右奇异向量矩阵V的前k列元素。
比率:
n2
k(2n1)
称为图像的压缩比。
22
k(2n1)nkn(2n1)。故k显然,被选择的奇异值的个数应该满足条件,即
在传送图像的过程中,不需要传nn个数据,而只需要传k(2n1)个有关奇异值和奇异向量的数据即可。接收端,在接收到奇异值1,2,,r以及左奇异向量向量v1,v2,,vr后,可以通过:
u1,u2,,uk和右奇异
AkiuiviH
i1
k
重构出原图像矩阵。
Ak与A的误差为:
AAk
2F
k21k22r2
,对一幅图像来
某个奇异值对图像的贡献可以定义为
ii2/j2(,j1,2,,k)
H
iii
说,较大的奇异值对图像信息的贡献量较大,较小的奇异值对图像的贡献较小。假如
,i1,2,,k)Auv(接近1,该图像的主要信息就包含在
i
k
(,i1,2,,k)
之中。通常图像的奇异值都具“大L 曲线”,只有不多的一些比较大的奇异值,其它的奇异值相对较小,因此一般只需要比较小的k 就使
,i1,2,,k)(接近1。在满足视觉要
i
A求的基础上,按奇异值的大小选择合适的奇异值个数kr,就可以通过k将图像A恢复。
k越小,用于表示Ak的数据量就小,压缩比就越大,而k越接近r,则Ak与A就越相似。
2
n(2n1)求出k,这时也同在一些应用场合中,如果是规定了压缩比,则可以由式
样可以求出
,i1,2,,k)(。
i
5.2 奇异值分解压缩应用过程
在对图像进行操作时,因为矩阵的维数一般较大,直接进行奇异值分解运算量大, 可以将图像分解为子块,对各子块进行奇异值分解并确定奇异值个数,将每个子块进行重构。这样操作除了因为对较小型的矩阵进行奇异值分解的计算量比较小外,另一方面是为了利用原始图像的非均匀的复杂性。如果图像的某一部分比较简单,那么只需要少量的奇异值,就可以达到满意的近似效果。
为了保证图像的质量就需要较多的奇异值。但是各个子块的奇异值数目, 大小各不相同, 因此可以考虑为每个子块自适应的选择适当的奇异值数目。一种简单的方法是定义奇异值贡献量的和
i
a(,i1,2,,k)
来选择k,其中a是一个接近1的数。对常见的
256 ×256 .bmp格式的图像(位图),划分为4×4个子块,每个子块大小为64×64。对每个子块根据
i
0.99(,i1,2,,k)
来选择所需要的奇异值数目。增大a的值来选择奇异值
数目,可以推理得随着a不断增大,视觉效果越来越好。随着a不断增大, 需要的奇异值也增多, 压缩比会减小。
六、小 结
经过以上讨论可知,用奇异值分解进行图像压缩,肯定能取得成功,也具有较好的应用价值,但仍然需要有以下值得去思考并改善:
1、对子块的划分可以采取更加有效的方法来完成。例如对规模很大的矩阵,随机抽取矩阵的某些行列得到规模较小的矩阵,计算小矩阵的奇异值,重复若干次,用这些小矩阵的奇异值逼近原始矩阵的奇异。
2、影响运算速度的因素是SVD 变换运算比较大,能否找到一个快速的SVD 变换算法。
另外,若已知图像矩阵的奇异值及其特征空间,一般认为较大的奇异值及其对应的奇异向量表示图像信号,而噪声反映在较小的奇异值及其对应的奇异向量上。依据一定的准则选择门限,低于该门限的奇异值置零(截断) ,然后通过这些奇异值和其对应的奇异向量重构图像进行去噪。若考虑图像的局部平稳性,也可以对图像分块奇异值分解去噪,这样能在一定程度上保护图像的边缘细节。如果仔细分析,SVD去噪具有的方向性。根据SVD图像性质3,可以把图像分块旋转SVD去噪,即将图像划分为不同的块,然后对每个图像块单独进行旋转SVD去噪,最后再整体组合得到去噪后的图像。这样图像的主观质量可能有较大改善。
- 9 -