第29卷第6期昆明理工大学学报(理工版)
2004年12月 Journal of Kunming University of Science and Tec hnology (Science and Technology) Vol. 29 No. 6
Dec. 2004
基本矢量量化器的性能研究
徐全元, 邵玉斌, 鲁莹
(昆明理工大学信息工程与自动化学院, 云南昆明 650051)
摘要:介绍了基本矢量量化器的理论和结构设计基本原理. 研究和实现了基本矢量量化器的LBG 算法, 并着眼于在优化系统结构和性能时选择LBG 算法中产生初始码书的方法. 通过对输入的语音信号进行矢量量化仿真, 分析了基本矢量量化器的性能. 关键词:矢量量化; 优化; LBG 算法中图分类号:TN912. 3文献标识码:A
文章编号:1007-855X(2004) 06-0075-04
Performance Research of Full -Search Vector Quantizer
XU Quan yuan, SHAO Yu bin, LU Ying
(Faculty of Information Engineering and Automation, Kunming University of Science and Technology , Kunming 650051, China )
Abstract:The principle of the theory and configuration of full-search vector quantizer is introduced. Then the LBG Algorithm of full-search VQ is studied and thus a means of generating initialization code-books is cho sen, which is necessary in LBG Algorithm aimed at optimizing structure and performance of VQ system. The per formance of full-search VQ by VQ simulating on speech signals is analyzed. Key words:vector quantization; optimize; LBG Algorthim
0引言
数据压缩是为了在现有系统特性条件下满足工作要求, 或者在新系统设计时降低成本的一种技术. 矢量量化(VectorQuantization, 简写为VQ) 是一种极其重要的压缩方法, 广泛应用于图像信号压缩、语音压缩等领域. 矢量量化是将若干个幅度连续取值的时域采样信号分成组, 即构成矢量, 然后用若干个离散的数字值来表示各种矢量. 矢量量化之所以能压缩数据, 是由于它能去掉冗余度, 且能有效地利用矢量各分量间的四种相关的性质:线性依赖性、非线性依赖性、概率密度函数的形状及矢量维数. 研究矢量量化器通常从码书设计和搜索算法着手, 以构造一个搜索效率和编码质量好的矢量量化器. 现有的各种矢量量化器主要以穷尽搜索矢量量化器(full-search VQ) 为标准进行比较, 所以常称穷尽搜索矢量量化器为基本矢量量化器.
1矢量量化的基本原理[1, 2]
矢量量化的理论基础是香农的速率 失真理论[1]. 1959年, 香农定义了速率失真函数R (D ) , 并证明只要R (D ) 不超过信道容量就能使接收端的失真不超过给定的阈值D. 对于幅值离散的信源, R (D ) 定义如下:
R (D ) =min
其中Q (Y) =
X
P (X ) P (Y |
X
Y
X ) log 2[P (Y |X ) /Q (Y) ](1)
P (X ) P (Y |X ) . 平均失真满足条件: P (X ) P (Y |X ) d (X ; Y) D
X
Y
(2)
收稿日期:2003-10-21. 基金项目:云南省自然科学基金资助项目(项目编号:F0040M ).
第一作者简介:徐全元(1979~) , 男, 在读硕士研究生. 主要研究方向:扩频通信. E -mail:xqy 322@y ahoo. com.
76昆明理工大学学报(理工版) 第29卷
R (D ) 的逆函数为失真-速率函数D (R ) , 它表示在给定速率不超过R 的条件下, 系统所能达到的最小失真. D (R ) 是在维数k 趋向无穷大时D K (R ) 的极限, 即:
D (R ) =k lim D k (R ) ! ∀
利用矢量量化, 编码性能可任意接近速率-失真函数, 其方法是增加矢量的维数k. 在实际应用中, 速率-失真函数常常作为一个理论下限与实际编码速率相比较, 分析系统还有多大
的改进余地. 一个时间连续、无记忆高斯信源的速率-失真函数R (D ) 的曲线图如图1所示. 速率-失真理论的一个基本结论是:无论对于何种信息源, 即使是无记忆的信息源, 矢量量化总是优于标量量化, 且矢量维数越大优度越高.
一个无记忆VQ 系统的基本框架如图2所示.
输入矢量为X , 若其维数为K , 则X =[x 1, x 2, #, x k ].系统中有两个完全相同的码本, 每个码本中包含M 个码字Y i , i =1~M , 每个码字是一个K 维矢量. VQ
编码器的原理是根据输入矢量X 从编码器码本中选择一个与之相应的矢量Y i , 其输出v 即等于此矢量的下标, 这一过程可以形式化地用下式表示:v =r (X ). VQ 译码器的运行原理是按照v 从译码器码本中通过查表操作选出一个具有相应下标的码字作为输出Y. 这可以表示为:Y = (v ).
(3
)
2基本矢量量化器的设计算法[2, 3]
矢量量化器设计的主要目标是寻找一个码书(用来确定译码器) 和一个划分法或编码准则(用来确定编码器) , 以使待编码序列的总体失真最小.
对于整个输入语音信号和相应的重构语音信号之间的失真则用信噪比(SNR ) 来测度重构语音信号的质量. 其定义如下:
j=1
SNR =10∃log 10
x j
m
2
j =1
m
(4)
2
|x j -y j |
式中, x j 是输入语音信号, y j 是重构语音信号, m 为语音信号的样值数.
如果用d (X , Y) 表示X 和Y 之间的畸变, VQ 的任务就是在给定R 的条件下, 使得此畸变的统计平均值达到最小. D =E [d (X , Y) ].为了实现这一目的, 应该遵循以下两条优化原则[2]:
(1) 最紧邻原则(最佳划分) :对于给定码书, 训练矢量集的最佳划分可通过把每个训练矢量映射为离它最近的码字而得到. 这可表示为:d (X , Y l ) =min d (X , Y i ). i
(2) 质心条件(最佳码书) :设所有选择码字Y l 的输入矢量X 的集合为S l , 那么应使此集合中所有矢量与Y l 之间的畸变平均最小. 如果X 与Y 之间的畸变等于它们的欧氏距离, 那么易证明Y l 等于S l 中所有矢量的%质心&, 即:Y l =
X , N l 是S l 中所包含的矢量个数. N l X ∋S
i
一个VQ 系统能否给出较低的D 值, 从而具有较高的质量, 关键在于码本设计. 根据第(1) 和(2) 两条原则, 可以形成一种码本递推算法. 这种算法常称为LBG 算法或GLA 算法[3, 4]. 下面给出基于平方误差测度和训练矢量集的LBG 算法具体步骤:
C (0) =[Y 1(0) , Y 2(0) , , M (0) ]m =0, D (-1)
! ∀,
第6期 徐全元, 邵玉斌, 鲁莹:基本矢量量化器的性能研究77
的相对门限 (0
步骤2:用码书C (m) 中的各码字作为质心, 根据最佳划分原则把训练矢量集X 划分为M 个子集S 1m ,
m S 2m , #, S M . 即当X ∋S l m 时, 下式应成立:
d (X , Y l (m-1) ) d (X , Y i (m-1) ) , i , i (l
步骤3:计算总畸变:
D
(m )
(5)
=
l=1X ∋S
d (X , Y l
l
M
(m-1)
) (6)
判断相对误差是否满足
:
(D (m-1) -D m ) /D (m )
若满足, 则停止算法, 码书C (m) 就是所求的码书; 否则, 转步骤4.
步骤4:根据最佳码书条件, 计算新码字, 即:
X Y i (m) =
N i X m
∋S
i
(7)
表1 1bit/采样的基本VQ 的性能表Tab ! 1 Pe rf ormanc e of VQ with 1bit/sample
矢量维数1235333811. 2
440001612. 4
532003213. 8
626676414. 9
7228712816. 1
8200025617. 9
训练矢量数160008000码书大小24信噪比SNR
3. 8
8. 1
(8) , i =
,
矢量维数训练矢量数码书大小信噪比SNR
表2 2bit/采样的基本VQ 的性能表Tab. 2 Pe rf ormanc e of VQ with 2bit/sample
11600048. 5
280001615. 6
353336418. 1
4400025621. 3
由这个新质心, Y i
m +1
1, 2, #, M 形成新码书C
(m+1)
置m =m +1, 转步骤2.
初始码书的选择影响码书训练的收敛速度和最终码书的性能. 传统的初始码书生产方法有两种:
(1) 随机选择法:直接从训练矢量集中选择N 个训练矢量作为初始码字构成初始码书. 该方法的优点是计算量小, 缺点是码书性能可能较差.
(2) 分裂法:该方法具体步骤如下:
步骤1:计算所有训练矢量的质心
Y 0(0)
N
j=1
=
X j
步骤2:用合适的
乘以码字
N
参数A , Y 1(0) Y 0(0) , 形成第二个码字
78昆明理工大学学报(理工版) 第29卷
(m )
步骤3:以Y 0(0) 和Y 1(0) 为初始码字, 用前面所述的LBG 算法设计仅含2个码字的码书C m , 2=[Y 0
Y 1(m ) ].
m ) m ) (m ) 步骤4:将码书C 2(m ) 中的两个码字Y (0和Y 1(m ) 分别乘以合适的参数B , 得到4个码字Y (0, Y 1, ) (m) BY (m0, BY 1.
步骤5:以这4个码字为初始码书, 用前面的LBG 算法设计仅含4个码字的码书, 再对设计好的4个码字乘以适当系数进一步扩大码字数目. 如此反复, 经过log 2M 次设计, 就得到所要求的含M 个码字的初始码书.
用分裂法产生的初始码书性能好, 但其主要缺点是计算量大.
穷尽搜索矢量量化的计算量, 即复杂度为:k 2KR , k 为矢量维数, R 为比特数. 信源编码理论常着眼于如何优化系统的结构和性能, 即如何在给定编码速率条件下达到最佳性能或在给定性能条件下将比特率降至最小, 却不太注重复杂度的问题.
3性能仿真实验
本实验利用实际的语音波形数据(8bit/采样, 共16000个采样) , 设计一个速率为1bit/采样和2bit/采样的能以不同维数工作的基本矢量量化器. 下面的实验仿真结果是以采用LBG 算法进行仿真而得到的. 在生产初始码书时, 采用分裂法. 因为采用随机法很难得到一个性能较好的码书, 而用分裂法产生的码书性能比较好. 语音的质量是用整个输入信号和相应重构信号之间的信噪比SNR 来测度的.
4分析与结论
从表1、表2的信噪比SNR 和图3、图4、图5、图6的量化后的波形比较来看, 在相同编码速率条件下, 基本矢量量化器的性能随着矢量维数的增大而提高, 量化误差减小. 编码速率提高时, 在相同的矢量维数条件下, 基本矢量量化器的性能随着提高, 量化误差也变小, 当然矢量量化器的压缩率就变小了. 若矢量维数趋于无穷大时, 其编码性能可达到速率-失真界, K 越大离速率-失真界越近. 当矢量量化的维数为一维时, 它就等同于标量量化. 一般矢量量化的维数都大于一维, 从上面的仿真可得出矢量量化总是优于标量量化. 参考文献:
[1]John G. Proakis. Digital Communications (Fourth Edition) [M ].N ew York:M cGraw -Hill, 2001. 104~120. [2]孙圣和, 陆哲明. 矢量量化技术及应用[M ].北京:科学出版社, 2002. 31~68. [3]杨行峻, 迟惠生. 语音信号数字处理[M ].北京:电子工业出版社, 1995. 91~109.
第29卷第6期昆明理工大学学报(理工版)
2004年12月 Journal of Kunming University of Science and Tec hnology (Science and Technology) Vol. 29 No. 6
Dec. 2004
基本矢量量化器的性能研究
徐全元, 邵玉斌, 鲁莹
(昆明理工大学信息工程与自动化学院, 云南昆明 650051)
摘要:介绍了基本矢量量化器的理论和结构设计基本原理. 研究和实现了基本矢量量化器的LBG 算法, 并着眼于在优化系统结构和性能时选择LBG 算法中产生初始码书的方法. 通过对输入的语音信号进行矢量量化仿真, 分析了基本矢量量化器的性能. 关键词:矢量量化; 优化; LBG 算法中图分类号:TN912. 3文献标识码:A
文章编号:1007-855X(2004) 06-0075-04
Performance Research of Full -Search Vector Quantizer
XU Quan yuan, SHAO Yu bin, LU Ying
(Faculty of Information Engineering and Automation, Kunming University of Science and Technology , Kunming 650051, China )
Abstract:The principle of the theory and configuration of full-search vector quantizer is introduced. Then the LBG Algorithm of full-search VQ is studied and thus a means of generating initialization code-books is cho sen, which is necessary in LBG Algorithm aimed at optimizing structure and performance of VQ system. The per formance of full-search VQ by VQ simulating on speech signals is analyzed. Key words:vector quantization; optimize; LBG Algorthim
0引言
数据压缩是为了在现有系统特性条件下满足工作要求, 或者在新系统设计时降低成本的一种技术. 矢量量化(VectorQuantization, 简写为VQ) 是一种极其重要的压缩方法, 广泛应用于图像信号压缩、语音压缩等领域. 矢量量化是将若干个幅度连续取值的时域采样信号分成组, 即构成矢量, 然后用若干个离散的数字值来表示各种矢量. 矢量量化之所以能压缩数据, 是由于它能去掉冗余度, 且能有效地利用矢量各分量间的四种相关的性质:线性依赖性、非线性依赖性、概率密度函数的形状及矢量维数. 研究矢量量化器通常从码书设计和搜索算法着手, 以构造一个搜索效率和编码质量好的矢量量化器. 现有的各种矢量量化器主要以穷尽搜索矢量量化器(full-search VQ) 为标准进行比较, 所以常称穷尽搜索矢量量化器为基本矢量量化器.
1矢量量化的基本原理[1, 2]
矢量量化的理论基础是香农的速率 失真理论[1]. 1959年, 香农定义了速率失真函数R (D ) , 并证明只要R (D ) 不超过信道容量就能使接收端的失真不超过给定的阈值D. 对于幅值离散的信源, R (D ) 定义如下:
R (D ) =min
其中Q (Y) =
X
P (X ) P (Y |
X
Y
X ) log 2[P (Y |X ) /Q (Y) ](1)
P (X ) P (Y |X ) . 平均失真满足条件: P (X ) P (Y |X ) d (X ; Y) D
X
Y
(2)
收稿日期:2003-10-21. 基金项目:云南省自然科学基金资助项目(项目编号:F0040M ).
第一作者简介:徐全元(1979~) , 男, 在读硕士研究生. 主要研究方向:扩频通信. E -mail:xqy 322@y ahoo. com.
76昆明理工大学学报(理工版) 第29卷
R (D ) 的逆函数为失真-速率函数D (R ) , 它表示在给定速率不超过R 的条件下, 系统所能达到的最小失真. D (R ) 是在维数k 趋向无穷大时D K (R ) 的极限, 即:
D (R ) =k lim D k (R ) ! ∀
利用矢量量化, 编码性能可任意接近速率-失真函数, 其方法是增加矢量的维数k. 在实际应用中, 速率-失真函数常常作为一个理论下限与实际编码速率相比较, 分析系统还有多大
的改进余地. 一个时间连续、无记忆高斯信源的速率-失真函数R (D ) 的曲线图如图1所示. 速率-失真理论的一个基本结论是:无论对于何种信息源, 即使是无记忆的信息源, 矢量量化总是优于标量量化, 且矢量维数越大优度越高.
一个无记忆VQ 系统的基本框架如图2所示.
输入矢量为X , 若其维数为K , 则X =[x 1, x 2, #, x k ].系统中有两个完全相同的码本, 每个码本中包含M 个码字Y i , i =1~M , 每个码字是一个K 维矢量. VQ
编码器的原理是根据输入矢量X 从编码器码本中选择一个与之相应的矢量Y i , 其输出v 即等于此矢量的下标, 这一过程可以形式化地用下式表示:v =r (X ). VQ 译码器的运行原理是按照v 从译码器码本中通过查表操作选出一个具有相应下标的码字作为输出Y. 这可以表示为:Y = (v ).
(3
)
2基本矢量量化器的设计算法[2, 3]
矢量量化器设计的主要目标是寻找一个码书(用来确定译码器) 和一个划分法或编码准则(用来确定编码器) , 以使待编码序列的总体失真最小.
对于整个输入语音信号和相应的重构语音信号之间的失真则用信噪比(SNR ) 来测度重构语音信号的质量. 其定义如下:
j=1
SNR =10∃log 10
x j
m
2
j =1
m
(4)
2
|x j -y j |
式中, x j 是输入语音信号, y j 是重构语音信号, m 为语音信号的样值数.
如果用d (X , Y) 表示X 和Y 之间的畸变, VQ 的任务就是在给定R 的条件下, 使得此畸变的统计平均值达到最小. D =E [d (X , Y) ].为了实现这一目的, 应该遵循以下两条优化原则[2]:
(1) 最紧邻原则(最佳划分) :对于给定码书, 训练矢量集的最佳划分可通过把每个训练矢量映射为离它最近的码字而得到. 这可表示为:d (X , Y l ) =min d (X , Y i ). i
(2) 质心条件(最佳码书) :设所有选择码字Y l 的输入矢量X 的集合为S l , 那么应使此集合中所有矢量与Y l 之间的畸变平均最小. 如果X 与Y 之间的畸变等于它们的欧氏距离, 那么易证明Y l 等于S l 中所有矢量的%质心&, 即:Y l =
X , N l 是S l 中所包含的矢量个数. N l X ∋S
i
一个VQ 系统能否给出较低的D 值, 从而具有较高的质量, 关键在于码本设计. 根据第(1) 和(2) 两条原则, 可以形成一种码本递推算法. 这种算法常称为LBG 算法或GLA 算法[3, 4]. 下面给出基于平方误差测度和训练矢量集的LBG 算法具体步骤:
C (0) =[Y 1(0) , Y 2(0) , , M (0) ]m =0, D (-1)
! ∀,
第6期 徐全元, 邵玉斌, 鲁莹:基本矢量量化器的性能研究77
的相对门限 (0
步骤2:用码书C (m) 中的各码字作为质心, 根据最佳划分原则把训练矢量集X 划分为M 个子集S 1m ,
m S 2m , #, S M . 即当X ∋S l m 时, 下式应成立:
d (X , Y l (m-1) ) d (X , Y i (m-1) ) , i , i (l
步骤3:计算总畸变:
D
(m )
(5)
=
l=1X ∋S
d (X , Y l
l
M
(m-1)
) (6)
判断相对误差是否满足
:
(D (m-1) -D m ) /D (m )
若满足, 则停止算法, 码书C (m) 就是所求的码书; 否则, 转步骤4.
步骤4:根据最佳码书条件, 计算新码字, 即:
X Y i (m) =
N i X m
∋S
i
(7)
表1 1bit/采样的基本VQ 的性能表Tab ! 1 Pe rf ormanc e of VQ with 1bit/sample
矢量维数1235333811. 2
440001612. 4
532003213. 8
626676414. 9
7228712816. 1
8200025617. 9
训练矢量数160008000码书大小24信噪比SNR
3. 8
8. 1
(8) , i =
,
矢量维数训练矢量数码书大小信噪比SNR
表2 2bit/采样的基本VQ 的性能表Tab. 2 Pe rf ormanc e of VQ with 2bit/sample
11600048. 5
280001615. 6
353336418. 1
4400025621. 3
由这个新质心, Y i
m +1
1, 2, #, M 形成新码书C
(m+1)
置m =m +1, 转步骤2.
初始码书的选择影响码书训练的收敛速度和最终码书的性能. 传统的初始码书生产方法有两种:
(1) 随机选择法:直接从训练矢量集中选择N 个训练矢量作为初始码字构成初始码书. 该方法的优点是计算量小, 缺点是码书性能可能较差.
(2) 分裂法:该方法具体步骤如下:
步骤1:计算所有训练矢量的质心
Y 0(0)
N
j=1
=
X j
步骤2:用合适的
乘以码字
N
参数A , Y 1(0) Y 0(0) , 形成第二个码字
78昆明理工大学学报(理工版) 第29卷
(m )
步骤3:以Y 0(0) 和Y 1(0) 为初始码字, 用前面所述的LBG 算法设计仅含2个码字的码书C m , 2=[Y 0
Y 1(m ) ].
m ) m ) (m ) 步骤4:将码书C 2(m ) 中的两个码字Y (0和Y 1(m ) 分别乘以合适的参数B , 得到4个码字Y (0, Y 1, ) (m) BY (m0, BY 1.
步骤5:以这4个码字为初始码书, 用前面的LBG 算法设计仅含4个码字的码书, 再对设计好的4个码字乘以适当系数进一步扩大码字数目. 如此反复, 经过log 2M 次设计, 就得到所要求的含M 个码字的初始码书.
用分裂法产生的初始码书性能好, 但其主要缺点是计算量大.
穷尽搜索矢量量化的计算量, 即复杂度为:k 2KR , k 为矢量维数, R 为比特数. 信源编码理论常着眼于如何优化系统的结构和性能, 即如何在给定编码速率条件下达到最佳性能或在给定性能条件下将比特率降至最小, 却不太注重复杂度的问题.
3性能仿真实验
本实验利用实际的语音波形数据(8bit/采样, 共16000个采样) , 设计一个速率为1bit/采样和2bit/采样的能以不同维数工作的基本矢量量化器. 下面的实验仿真结果是以采用LBG 算法进行仿真而得到的. 在生产初始码书时, 采用分裂法. 因为采用随机法很难得到一个性能较好的码书, 而用分裂法产生的码书性能比较好. 语音的质量是用整个输入信号和相应重构信号之间的信噪比SNR 来测度的.
4分析与结论
从表1、表2的信噪比SNR 和图3、图4、图5、图6的量化后的波形比较来看, 在相同编码速率条件下, 基本矢量量化器的性能随着矢量维数的增大而提高, 量化误差减小. 编码速率提高时, 在相同的矢量维数条件下, 基本矢量量化器的性能随着提高, 量化误差也变小, 当然矢量量化器的压缩率就变小了. 若矢量维数趋于无穷大时, 其编码性能可达到速率-失真界, K 越大离速率-失真界越近. 当矢量量化的维数为一维时, 它就等同于标量量化. 一般矢量量化的维数都大于一维, 从上面的仿真可得出矢量量化总是优于标量量化. 参考文献:
[1]John G. Proakis. Digital Communications (Fourth Edition) [M ].N ew York:M cGraw -Hill, 2001. 104~120. [2]孙圣和, 陆哲明. 矢量量化技术及应用[M ].北京:科学出版社, 2002. 31~68. [3]杨行峻, 迟惠生. 语音信号数字处理[M ].北京:电子工业出版社, 1995. 91~109.