矩阵的奇异值分解在数字图像处理的应用浅析
学院:
专业:
姓名:
学号:
目录
一、绪论 ................................................................................................................................. - 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 离散化称之为量化。经过取样和量化的图像是一幅数字图像。数字图像的质量很大程度上取决于取样和量化的取样数和灰度级。取样和量化的结果是一个实际的矩阵。这个矩阵可以表示为
n
m n m f m f m f n f f f n f f f y x f ??
??
????
??
???------=)1,1()1,1()
0,1()1,1()1,1()
0,1()1,0()1,0()0,0(),(
更一般的矩阵表达方式为:
n
m n m m m n n a a a a a a a a a A ?------?
?
?????
?????=1.11
.10
.11.11.10
.11,01,00,0
图像压缩是数据压缩技术在数字图像上的应用,它的目的是减少图像数据中的冗余信息从而用更加高效的格式存储和传输数据。图像数据之所以能被压缩,就是因为数据中存在着冗余。图像数据的冗余主要表现为:图像中相邻像素间的相关性引起的空间冗余;图像序列中不同帧之间存在相关性引起的时间冗余;不同彩色平面或频谱带的相关性引起的
频谱冗余。
图像压缩可以是有损数据压缩也可以是无损数据压缩。无损图像压缩方法主要有行程长度编码、熵编码法如LZW;有损压缩方法主要有变换编码,如离散余弦变换(DCT)或者小波变换这样的傅立叶相关变换,然后进行量化和用熵编码法压缩和分形压缩(fractal compression)。
图像矩阵A的奇异值(Singular Value)及其特征空间反映了图像中的不同成分和特征。奇异值分解(Singular Value Decomposition ,SVD) 是一种基于特征向量的矩阵变换方法,在信号处理、模式识别、数字水印技术等方面都得到了应用。我们主要讨论奇异值分解在图像压缩上的应用。
三、矩阵的奇异值分解原理
3.1 矩阵的奇异值
设n
m r C A ?∈,)(rank A r =,i λ是H AA 的特征值,i μ是A A H 的特征值,它们都是实
数。且设
02121==???==>≥???≥≥++m r r r λλλλλλ
02121==???==>≥???≥≥++n r r r μμμμμμ
则特征值
i λ与i μ之间的关系为:0>=i i μλ,),,2,1(r i ???=。
设n m r C A ?∈, H AA 的正特征值i λ,A A H 的正特征值i μ,称i i i μλα==,
),,2,1(r i ???=是A 的正奇异值,简称奇异值。若A 是正规矩阵,则A 的奇异值是A 的
非零特征向量的模长。
3.2 矩阵的奇异值分解(SVD )
若n
m r C A ?∈,r δδδ≥???≥≥21是A 的r 个正奇异值,则存在m 阶酉矩阵U 和n 阶酉
矩阵V ,满足:
H
H V U UDV A ???????==000
其中,),,,(21r diag δδδ???=?,?为奇异对角阵。U 满足U AA U H
H
是对角阵,V 满足
AV A V H H 是对角阵。U 的第i 列为A 的对应于i δ奇异值对应的左奇异向量,V 的第i 列
为A 的对应于i δ奇异值对应的右奇异向量。它们的每一列均为单位向量,且各列之间相互
正交。
若n m r C A ?∈,r δδδ≥???≥≥21是A 的r 个正奇异值,则总有次酉矩阵r
m r r U U ?∈,
r n r r V V ?∈满足:H r r V U A ?=,其中),,,(21r diag δδδ???=?。
奇异值分解是一种基于特征向量的矩阵变换方法。奇异值分解是现代数值的最基本和最重
要的工具之一。
四、奇异值分解的图像性质
任意一个n
m C
A ?∈矩阵的奇异值),,,(21r δδδ???是唯一的,它刻画了矩阵数据的分布
特征。直观上,可以这样理解矩阵的奇异值分解:将矩阵n
m C A ?∈看成是一个线性变换,
它将m 维空间的点映射到n 维空间。n
m C
A ?∈经过奇异值分解后,这种变换被分割成3个
部分,分别为U 、?和V ,其中U 和V 都是标准正交矩阵,它们对应的线性变换就相当于对m 维和n 维坐标系中坐标轴的旋转变换。
若A 为数字图像,则A 可视为二维时频信息,可将A 的奇异值分解公式写为:
∑∑====?
??????==r
i H
i i i r i i H H
v u A V U UDV
A 11000δ
其中,i u
和
i v 分别是U 和V 的列矢量,i δ是A 的非零奇异值。故上式表示的数字图像A 可
以看成是r 个秩为1的子图H
i i v u 叠加的结果,而奇异值i δ为权系数。所以i A 也表示时频信
息,对应的
i u 和i v 可分别视为频率矢量和时间矢量,因此数字图像A 中的时频信息就被分解到一系列由
i u 和i v 构成的视频平面中。
由矩阵范数理论, 奇异值能与向量2-范数和矩阵Frobenious-范数(F-范数)相联系。
)
max(22
21X AX
A ==λ
2
1
122
1
2)(∑∑==???
???=r
i i mn mn F
a A
λ
若以F-范数的平方表示图像的能量,则由矩阵奇异值分解的定义知:
∑==?
?????????????==r
i i H
H H
F
V U U V tr A A tr A
12
2)000000()(δ。
也就是说,数字图像A 经奇异值分解后,其纹理和几何信息都集中在U 、H
V 之中,
而?中的奇异值则代表图像的能量信息。
性质1:矩阵的奇异值代表图像的能量信息,因而具有稳定性。
设n
m C A ?∈,δ+=A B ,δ是矩阵A 的一个扰动矩阵。A 和B 的非零奇异值分别记
为:r 11211δδδ≥???≥≥和r 22221δδδ≥???≥≥。且)(rank A r =,1δ是δ的最大奇异值。
则有:
1
2
221δδ
δδ==-≤-B A i i 。
由此可知,当图像被施加小的扰动时,图像矩阵的奇异值变化不会超过扰动矩阵的最大奇异值,所以图像奇异值的稳定性很好。
性质2:矩阵的奇异值具有比例不变性。
设n
m C A ?∈,矩阵A 的奇异值为
i δ),,2,1(r i ???=,)(rank A r =,矩阵kA (0≠k )
的奇异值为
i α),,2,1(r i ???=。则有:),,,(),,,(2121r r k αααδδδ???=???。
性质3:矩阵的奇异值具有旋转不变性。
设n
m C
A ?∈,矩阵A 的奇异值为
i δ),,2,1(r i ???=,)(rank A r =。若r U 是酉矩阵,
则矩阵A U r 的奇异值与矩阵A 的奇异值相同:
)(22=-=-E A U A U E AA i H r r i H δδ。
性质4:设n
m C
A ?∈,s r A ≥=)(rank 。若),,,(21s s diag δδδ???=?,
∑==s
i H
i i i s v u A 1
δ,
s rank A s s =?=)()(rank
所以可得:
{
}
2
2221min r s s n m F
F
S
C B B
A A A δδδ+???++=∈-=-++?
上式表明,在F-范数意义下,s A 是在空间n
m s C ?(秩为s 的n m ?维矩阵构成的线性空
间)中A 的一个将秩最佳逼近。因此可根据需要保留)(r s s <个大于某个阈值的i δ而舍弃
其余s r -个小于阈值的
i δ且保证两幅图像在某种意义下的近似。
这就为奇异值特征矢量的
降维和数据压缩等应用找到了依据。
五、图像的奇异值分解压缩方法
5.1 奇异值分解压缩原理分析
用奇异值分解来压缩图像的基本思想是对图像矩阵进行奇异值分解,选取部分的奇异值和对应的左、右奇异向量来重构图像矩阵。根据奇异值分解的图像性质1和4可以知道,奇异值分解可以代表图像的能量信息,并且可以降低图像的维数。如果A 表示n 个m 维向量,可以通过奇异值分解将A 表示n m +为个r 维向量。若A 的秩远远小于m 和n ,则通过奇异值分解可以大大降低A 的维数。
对于一个n n ?像素的图像矩阵A ,设H
V
U A ?=,其中,),,,(21r diag δδδ???=?。
按奇异值从大到小取k 个奇异值和这些奇异值对应的左奇异向量及右奇异向量重构原图像矩阵A 。如果选择的r k ≥,这是无损的压缩;基于奇异值分解的图像压缩讨论的是r k <,即有损压缩的情况。这时,可以只用)12(+n k 个数值代替原来的n n ?个图像数据。这
)12(+n k 个数据分别是矩阵A 的前k 个奇异值, n n ?左奇异向量矩阵U 的前k 列和
n n ? 右奇异向量矩阵V 的前k 列元素。
比率:
)12(2
+=
n k n ρ
称为图像的压缩比。
显然,被选择的奇异值的个数k 应该满足条件2)12(n n k <+,即
)12(2
+ 向量r v v v ,,,21???后,可以通过: ∑==k i H i i i k v u A 1 δ 重构出原图像矩阵。 k A 与A 的误差为: 2 22212r k k F k A A δδδ+???++=-++ 某个奇异值对图像的贡献可以定义为 ) (k j j i i ,,2,1,/22 ==∑δδε,对一幅图像来 说,较大的奇异值对图像信息的贡献量较大,较小的奇异值对图像的贡献较小。假如 )(k i i ,,2,1, =∑ε接近1,该图像的主要信息就包含在 ) (k i v u A H i i i k ,,2,1, ==∑δ之中。通常图像的奇异值都具“大L 曲线”,只有不多的一些比较大的奇异值,其它的奇异值相对较小,因此一般只需要比较小的k 就使 )(k i i ,,2,1, =∑ε接近1。在满足视觉要 求的基础上,按奇异值的大小选择合适的奇异值个数r k <,就可以通过k A 将图像A 恢复。 k 越小,用于表示k A 的数据量就小,压缩比就越大,而k 越接近r ,则k A 与A 就越相似。 在一些应用场合中,如果是规定了压缩比,则可以由式 )12(2 +=n n ρ求出k ,这时也同样可以求出 )(k i i ,,2,1, =∑ε。 5.2 奇异值分解压缩应用过程 在对图像进行操作时,因为矩阵的维数一般较大,直接进行奇异值分解运算量大, 可以将图像分解为子块,对各子块进行奇异值分解并确定奇异值个数,将每个子块进行重构。这样操作除了因为对较小型的矩阵进行奇异值分解的计算量比较小外,另一方面是为了利用原始图像的非均匀的复杂性。如果图像的某一部分比较简单,那么只需要少量的奇异值,就可以达到满意的近似效果。 为了保证图像的质量就需要较多的奇异值。但是各个子块的奇异值数目, 大小各不相同, 因此可以考虑为每个子块自适应的选择适当的奇异值数目。一种简单的方法是定义奇异值贡献量的和 ) (k i a i ,,2,1, =>∑ε 来选择k ,其中a 是一个接近1的数。对常见的 256 ×256 .bmp 格式的图像(位图),划分为4×4个子块,每个子块大小为64×64。对每个子块根据 ) (k i i ,,2,1,99.0 =>∑ε 来选择所需要的奇异值数目。增大a 的值来选择奇异值 数目,可以推理得随着a 不断增大,视觉效果越来越好。随着a 不断增大, 需要的奇异值也增多, 压缩比会减小。 六、小结 经过以上讨论可知,用奇异值分解进行图像压缩,肯定能取得成功,也具有较好的应用价值,但仍然需要有以下值得去思考并改善: 1、对子块的划分可以采取更加有效的方法来完成。例如对规模很大的矩阵,随机抽取矩阵的某些行列得到规模较小的矩阵,计算小矩阵的奇异值,重复若干次,用这些小矩阵的奇异值逼近原始矩阵的奇异。 2、影响运算速度的因素是SVD 变换运算比较大,能否找到一个快速的SVD 变换算法。 另外,若已知图像矩阵的奇异值及其特征空间,一般认为较大的奇异值及其对应的奇异向量表示图像信号,而噪声反映在较小的奇异值及其对应的奇异向量上。依据一定的准则选择门限,低于该门限的奇异值置零(截断) ,然后通过这些奇异值和其对应的奇异向量重构图像进行去噪。若考虑图像的局部平稳性,也可以对图像分块奇异值分解去噪,这样能在一定程度上保护图像的边缘细节。如果仔细分析,SVD去噪具有的方向性。根据SVD 图像性质3,可以把图像分块旋转SVD去噪,即将图像划分为不同的块,然后对每个图像块单独进行旋转SVD去噪,最后再整体组合得到去噪后的图像。这样图像的主观质量可能有较大改善。