（通信与信息系统专业论文）矢量量化在图像处理中的应用研究.pdf

矢量量化在图像处理中的应用研究 专 业：通信与信息系统 博士生：刘诽贝 导师：陆哲明教授 摘要 矢量量化作为一种高效的数据压缩技术在数字通信、多媒体信息处理等诸 多领域得到了广泛的应用。图像、视频、音频等多媒体数据具有数据量大、时 空冗余度高的特点。采用矢量量化技术能够减少各种冗余，并在给定的失真条 件下以较少的比特数表达和重建原始多媒体内容。 矢量量化一直与图像处理有紧密的结合。矢量量化技术最初被应用于图像 压缩编码。随着图像检索研究的兴起，矢量量化作为一种图像特征提取手段开 始被应用于图像检索。随着信息安全研究的兴起，近年来又出现了一批以矢量 量化编码为基础的图像水印和图像隐写算法。 本论文在介绍了矢量量化的基本原理，并总结了矢量量化在图像处理中的 应用现状之后，将其应用延伸至图像彩色化、图像艺术风格学习以及图像语义 检索三个问题上。具体地，本论文的研究成果包括以下几点。 第一，提出了基于色度块量化的图像彩色化算法。该算法利用人眼的彩色 视觉特性，对图像的色度信息进行分块及量化处理，并采用半监督学习方法根 据用户手绘的示范色求解出各色度块的量化值。该算法在保证彩色化视觉效果 的同时有效地提高了彩色化效率。 第二，提出了基于局部线性嵌入的图像色彩传递算法。该算法将模板图像 和目标图像分割成块，利用这些图像块在一个假设的流形空间上的关系，采用 局部线性嵌入算法将模板图像的色彩信息传递至目标图像中。 第三，提出了基于码书替换的矢量量化方法。该方法突破了传统矢量量化 技术在编、解码端使用相同码书的做法，人为构造不相同但是具有内在关联的 两个码书，分别用于编码和解码步骤。码书替换方法灵活性强，可应用于多种 问题的解决，具有较大的应用价值。 第四，提出了基于码书替换的图像色彩传递算法。待着色的目标图像经过 灰度码书的编码以及彩色码书的解码后即可实现色彩的传递。该算法以码书替 换方法为基础，继承了图像矢量量化编码技术简单高效的特点，有效地降低了 色彩传递所需的计算时间。 第五，提出了基于码书替换的图像艺术风格学习算法。目标图像经过原始 码书的编码以及风格码书的解码后即完成了风格的转变。该算法同样以码书替 换方法为基础，具有简单高效的特点。实验表明，该方法尤其适用于以“面 状特征为主要表现形式的风格类型。 第六，提出了基于矢量量化的图像语义快速标注与检索方法。该方法引入 了图像特征码书与图像关键字码书两个码书。标注步骤通过基于码书替换的矢 量量化编、解码完成，检索步骤则通过两步反查找操作完成。该算法利用了矢 量量化方法引入的索引结构，一方面避免在图像库中大量重复存储相同的关键 字，另一方面缩小了关键字匹配的搜索范围。本论文进一步提出了改进算法， 在特征码书与关键字码书联合生成的过程中，引入对关键字出现频率的计算。 从而实现对检索结果进行排序，提高用户利用检索结果的效率。 关键词：矢量量化，图像彩色化，图像风格学习，图像标注，图像检索，码 书替换 s t u d yo na p p l i c a t i o no fv e c t o rq u a n t i z a t i o nt o i m a g ep r o c e s s i n g m a j o r ：c o m m u n ic a ti o n i n f o r m a ti o ns y s t e m s a u t h o r ：b e i - b e il i u s u p e r v is o r ：p r o f z h e m in gl u a b s t r a c t v e c t o rq u a n t i z a t i o n q ) i sa l le f f i c i e n td a t ac o m p r e s s i o nt e c h n i q u eh a v h l g f o u n daw i d er a n g eo fa p p l i c a t i o ni na r e a so fd i g i t a lc o m m u n i c a t i o na n dm u l t i m e d i a p r o c e s s i n g 舢i nt h ei m a g ep r o c e s s i n ga r e a , v qw a sf i r s t l yu s e df o ri m a g ec o d m g l a t e r , i t w a s e m p l o y e db yi m a g er e t r i e v a ls y s t e m sa sat y p eo fc o m p r e s s e df e a t u r e l a t e l y , v q h a sf o u n di t su s ei ni m a g ed i g i t a lw a t e r m a r k i n ga n dd a t ah i d i n g t h i st h e s i se x t e n d st h ea p p l i c a t i o no fv qt ot h r e er e c e n t l yi n t r o d u c e di m a g e r y p r o b l e m s ，n a m e l yi m a g ec o l o r i z a t i o n , i m a g es t y l er e n d e r i n ga n ds e m a n t i cb a s e d i m a g er e t r i e v a l t h ec o n t r i b u t i o n so f t h i st h e s i sa 坞d e s c r i b e da sf o l l o w s ( 1 ) ac o l o rs p r e a d i n ga l g o r i t h mb a s e do nc h r o 幽c eb l o c kq u a n t i z a t i o ni s p r o p o s e d t a k i n ga d v a n t a g e o ft h ec h a r a c t e r i s t i c so fh u m a nc o l o rv i s i o n , t h ep r o p o s e d a l g o r i t h md i v i d e st h ec h r o m i n a n c ei n f o r m a t i o no fa l li m a g ei n t os m a l lq u a n t i z e d b l o c k s t h eq u a n t i z a t i o nv a l u ei st h e nf i g u r e do u tb ys e m i s u p e r v i s e dl e a r n i n g m e t h o d t h ep r o p o s e da l g o r i t h md r a m a t i c a l l yr e d u c e st h et i m ef o rc o l o r i n ga l li m a g e ( 2 ) al o c a l l yl i n e a re m b e d d i n gb a s e dc o l o rt r a n s f e ra l g o r i t h mi sp r o p o s e d t h e t e m p l a t ea n dt a r g e ti m a g e sa r ed i v i d e di n t os m a l lb l o c k s a l lt h eb l o c k sa r es u p p o s e d t 0b ed i s t r i b u t e di nam a n i f o l ds p a c e t h et a r g e tb l o c k sa r ec o l o r i z e db yt h e i rl o c a l n e i g h b o r i n gt e m p l a t eb l o c k sw i t hl l ea l g o r i t h m ( 3 ) ac o d e b o o ks u b s t i t u t i o nm e t h o di sp r o p o s e d t r a d i t i o n a lv qr e q u i r e se x a c t l y i d e n t i c a lc o d e b o o k sf o rc o d i n ga n dd e c o d i n g t h ec o d e b o o ks u b s t i t u t i o nm e t h o d l p r o p o s e st oc o n s t r u c tt w od i f f e r e n tc o d e b o o k sf o rc o d i n ga n dd e c o d i n gr e s p e c t i v e l y t h ef o u n d a t i o no ft h ep r o p o s e dm e t h o dl i e si nt h es p e c i f i cr e l a t i o n sb e t w e e nt h et w o c o d e b o o k s ( 4 ) ac o d e b o o ks u b s t i t u t i o nb a s e dc o l o rt r a n s f e ra l g o r i t h mi sp r o p o s e d f o r c o l o r i z i n g ，t h et a r g e ti m a g ei sf i r s te n c o d e db yag r a y s c a l ec o d o b o o ka n dt h e n d o c o d e db yac o l o rc o d e b o o lt h ep r o p o s e da l g o r i t h mi st i m ea n ds t o r a g ee f f i c i e n t f o r t h ec o m p r e s s i o nt r a i to f v q ( 5 ) ac o d e b o o ks u b s t i t u t i o nb a s e di m a g es t y l er e n d e r i n g a l g o r i t h mi sp r o p o s e d t h es t y l i z a t i o np r o c e s sc o n s i s t so ft w os t e p s ，e n c o d i n gb yap l a i n n e s sc o d e b o o ka n d d e c o d i n gb yas t y l ec o d e b o o k t h ep r o p o s e da l g o r i t h mw o r k sp a r t i c u l a rw e l lo nt h o s e s u r f a c eb a s e ds t y l e s ( 6 ) af a s tv qb a s e di m a g ea n n o t a t i o na n dr e t r i e v a ls c h e m ei sp r o p o s e d t h e i m a g e si nt h ed a t a b a s ec a nb ea n n o t a t e dv i ae n c o d i n gb yaf e a t u r ec o d e b o o ka n d d e c o d i n gb yak e y w o r dc o d e b o o k g i v e nt h eq u e r yk e y w o r d s ，r e t r i e v a lc a nb ed o n e 、 ，i mt w os t e p so fr e v e r s el o o k - u p t h ep r o p o s e ds c h e m eh a st w oa d v a n t a g e s f i r s t l y i ta v o i d sk e e p i n gr e c o r d so fl a r g ea m o u n to fd u p l i c a t ek e y w o r d si nt h ed a t a b a s e s e c o n d l yi t a c c e l e r a t e st h ek c y w o r dm a t c h i n gp r o c e s sb yr e d u c i n gt h es e a r c h i n g r a n g e t of u r t h e ri m p r o v et h ep r o p o s e ds c h e m e ，t h eo c c u r r e n c ef r e q u e n c i e so fe a c h k e y w o r da r ce x p l o i t e di nt h eg e n e r a t i o no fk e y w o r dc o d e b o o k b yd o i n gs o ，t h e r e t r i e v e di m a g e sc a nb er a n k e da c c o r d i n gt ot h e i rp e r t i n e n c et ot h eq u e r yk e y w o r d s k e y w o r d s ：v e c t o rq u a n t i z a t i o n , i m a g ec o l o r i z a t i o n , i m a g es t y l er e n d e r i n g , i m a g ea n n o t a t i o n , i m a g er e t r i e v a l ，c o d e b o o ks u b s t i t u t i o n i v 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：训吲切、 日期：砂7 年彳月日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：刭棚删、 日期：硼7 年6 月毛e l 新签名俐 日期：7 年( 月6 日 第1 章引言 1 1 研究背景 矢量量化技术的发展可追溯到1 9 5 6 年。s t e i n h a u s 第一次系统地阐述了最佳 矢量量化问题。第一个实际的矢量量化器由b u z o 于1 9 7 8 年提出1 9 8 0 年由 l i n d e ，b u z o 和g r a y 三人合作提出的经典l b g 算法标志着人们对矢量量化的理 论和应用研究全面展开n 】。 矢量量化概念来源于数字通信领域中的信源编码。在信息论中，香农提出 了“块源编码系统 的概念。输入信号首先经过分块处理，然后把每一块映射 为信道代码。解码时再把每一块的代码映射为原输入块的重构块。原输入块与 重构块之间的差异用失真测度来衡量。该类型的编码系统称为矢量量化器，该 编码操作就称为矢量量化【l 】。矢量量化器的主要设计目标是获得最小失真映射。 理论上，通过增加矢量的维数可以使编码性能任意地接近速率一失真函数。在 相同的编码速率下，矢量量化比标量量化能达到更小的失真；而在相同的失真 条件下，矢量量化比标量量化需要更低的编码速率。 关于矢量量化的应用研究从该技术被提出之日起就从未停止和冷却过。作 为一种高效的有损数据压缩技术，矢量量化在图像、视频、音频等多媒体数据 压缩编码领域中得到了广泛的应用。图像、视频、音频这类多媒体数据的特点 是数据量大，但在空间和时间上往往存在大量的冗余信息。采用矢量量化技术 能够减少各种冗余并在给定的失真条件下以尽量少的比特数表达和重建原始多 媒体内容。基于矢量量化的图像压缩技术已被广泛应用于卫星遥感图像、气象 图像、雷达图像和军事地图等【2 】。而在语音编解码方面，矢量量化也发挥了重 要作用，已出现i t u tr e c o m m e n d a t i o n ( 2 7 2 9 等较为成熟的标准。此外，矢量 量化技术也被广泛应用于其它众多领域，包括移动通信、纹理压缩、语音识别、 数字水印和信息检索等方面【3 】。事实上，广阔的应用前景正是推动矢量量化技 术发展的重要原因。 在图像处理领域中，矢量量化技术最初被应用于图像压缩编码【4 】。随着图 像检索研究的兴起，矢量量化作为一种图像特征提取手段开始被应用于图像检 索 5 】。最近几年，随着信息安全研究的兴起，又出现了一批以矢量量化编码为 基础的图像水印【6 】和图像隐写算法【7 】。这些矢量量化与图像处理成功结合的例 子显示了矢量量化技术旺盛的生命力。图像处理是- - h 发展迅速的学科，同时 也是一门内容丰富的学科，涵盖了从图像获取、存储、传送、处理到显示等诸 多方面 8 】。随着科学技术手段的进步以及人们对图像需求的多样化，新的图像 处理问题不断涌现，传统的图像处理问题也将会遇到新的挑战。 本论文所研究的图像彩色化问题和图像艺术风格学习问题都属于图像处理 领域中近几年提出的新研究课题。这两个问题的研究目的都是希望借助现代计 算机技术丰富传统手段所获取的图像的内容、类型和视觉效果。除了具有很大 的娱乐性价值，图像彩色化技术更具有工业和科学上的实用价值。很多工业设 备或科学仪器受制造成本或者成像原理的限制，输出的是单色调图像。研究表 明，人眼对于色彩的分辨率远高于对于灰度阶的分辨率。因此，通过彩色化处 理后的图像更有利于操作人员的解读和判断。图像艺术风格学习则属于非真实 感绘制研究中的一个分支【9 】。在当今越来越追求多样化、个性化的社会，人们 有时希望图像在传递信息的同时具有更多的艺术效果。若能使普通用户无需具 备专业画家的技能就可以轻松创作出有一定艺术效果的图像，这将具有很大的 娱乐和商业价值。 图像语义检索问题则是图像检索在经历了基于文本的和基于内容的两代检 索方式之后发展而成的。图像检索问题自上世纪七十年代就已提出，最初依靠 的是人工对图像库进行分类并建立关键字。随着图像处理领域中其它方向取得 日益丰富的研究进展，九十年代开始出现了以自动提取图像视觉特征为基础的 检索方式，即基于内容的图像检索 1 0 ，1 1 。基于内容的图像检索系统往往需要 用户提交一幅内容相关的图像作为查询对象，而人们更希望直接通过输入关键 字进行查询，因此近年来提出了基于语义的图像检索思路。由于数字照相机等 设备越来越普及，每天产生的图像数量成爆炸式增长，人们在生活和工作中也 越来越依赖图像来传递信息。正如文本检索技术给人们带来的便利一样，图像 检索技术的研究对于推动社会发展和进步有着重要意义。 由于图像彩色化、图像艺术风格学习以及图像语义检索这几个问题的研究 历史都不长，目前仍处于百家争鸣的阶段，研究者们在不断尝试各种新思路和 新方法。本论文以矢量量化技术在上述问题中的应用为研究内容，一方面既为 图像彩色化、图像艺术风格学习以及图像语义检索这几个图像处理领域中的问 题引入了新的解决思路和方法，另一方面也延续和拓宽了矢量量化在图像处理 中的应用范围，对于矢量量化技术的发展具有重要的推动意义。 2 1 2 论文主要研究内容 本论文在介绍了矢量量化的基本原理，并总结了矢量量化在图像处理中的 应用现状之后，将其应用延伸至图像彩色化、图像艺术风格学习以及图像语义 检索三个问题上。具体地，本文的研究内容包含以下几个方面。 第一，对现有的图像彩色化算法进行了总结归纳，并将其归纳为基于图像 分割、基于色彩传递以及基于色彩蔓延的三个类别。在分析了各类彩色化方法 的特点及适用图像类型之后，提出了以下三种图像彩色化算法： ( 1 ) 利用人眼的彩色视觉特征，提出了一种基于色度块量化的图像彩色化 算法。该算法对图像的色度分量进行量化和分块处理，并采用半监督学习方法， 将用户的示范着色视为监督信息扩展至图像其余未着色部分。 ( 2 ) 采用流形学习方法中的局部线性嵌入算法提出了一种基于局部线性嵌 入的色彩传递算法。该算法假设目标图像和模板图像的图像块位于同一流形上， 并且目标图像的每一个图像块都能由若干个模板图图像块的线性组合重构而 成。先在灰度值空间中求解出线性组合重构系数，再将重构系数移植到色彩值 空间，即可计算出目标图像的色彩值。 ( 3 ) 提出了一种基于码书替换的图像色彩传递算法。码书替换方法是本论 文在传统矢量量化编码方法基础上提出的一种创新，其核心思想是在编码端和 解码端分别使用两个不同但相关的码书。将码书替换方法用于图像色彩传递时， 先利用模板彩色图像生成灰度码书与彩色码书。对于目标图像，先用灰度码书 对其进行编码，然后再根据编码时所获得的码字索引用彩色码书对其进行解码， 即可实现对目标图像的彩色化处理。 第二，由于图像艺术风格学习问题与图像色彩传递问题的共同点都是要从 模板图向目标图传递信息，因此本文将码书替换的方法延伸至图像艺术风格学 习问题上，提出基于码书替换的图像艺术风格学习算法。从一对包含原始风格 及艺术风格的模板图像中训练获得原始码书及风格码书两个一一对应的码书。 然后先用原始码书为目标图像进行编码，再在解码步骤中替换使用风格码书， 即可实现目标图像的风格转变。 第三，基于语义的图像检索方法通常包含图像关键字标注以及按关键字检 索两个环节。目前多数关于图像语义检索的研究忽略了标注与检索之间的关联 性，从而导致大量关键字重复存储、搜索范围过大，搜索效率低等问题。而矢 量量化在对数据进行压缩的同时引入了一种天然的索引结构，可以明显地提高 检索效率。因此本文提出基于矢量量化的图像语义标注及检索方法，将图像的 关键字标注及按关键字检索两个环节分别对应为矢量量化中的编码和解码步 骤。本算法也引入了两个一一对应的码书。在训练过程中，首先用已由人工标 注的训练图像库的图像特征训练得到特征码书和关键字码书。对测试图像库进 行标注时，先用特征码书进行编码，然后根据所获得的码字索引用关键字码书 进行解码，即可把每幅图像映射到一组关键字上。当用户输入查询关键字时， 只须在关键字码书中查找出匹配的码字，所有在编码时被映射到这些码字的图 像即构成检索结果。每幅图像都通过一个索引号同时与特征码书和关键字码书 建立关联。因此，对于每幅测试图像而言，只须存储一个码字索引号即可完成 关键字标注和按关键字检索。 1 3 论文的组织安排 本论文的章节安排如下： 第一章阐述本论文的研究背景及选题意义，并简要介绍本论文的主要研究 内容及章节安排。 第二章介绍矢量量化的基本原理和概念，并归纳矢量量化目前在图像处理 中的三个主要应用方向。 第三章主要围绕图像彩色化问题展开，在对图像彩色化方法进行归纳总结 后，分别阐述本论文所提出的三种图像彩色化算法：( 1 ) 基于色度块量化与半 监督学习的图像彩色化算法( 2 ) 基于局部线性嵌入的图像彩色化算法( 3 ) 基 于码书替换的图像彩色化算法，给出并分析了相应的实验结果。 第四章简要介绍图像艺术风格学习问题后，阐述本论文所提出的基于码书 替换的图像艺术风格学习算法，给出并分析了相应的实验结果。 第五章围绕图像语义检索问题展开，阐述本论文所提出的基于矢量量化的 图像语义检索方法以及对其的改进方法。 第六章总结本论文的研究内容及成果，并对不足之处及后续研究方向进行 讨论。 4 第2 章矢量量化基本原理 2 1 标量量化原理 通常把数据压缩方法分为无损压缩( 可逆压缩) 和有损压缩( 不可逆压缩) 两类。无损压缩的目标是使数据经压缩后所需的传输或存储量最小化，但同时 又能无失真地重构原始数据。而在有损压缩中，原始信号不能从压缩后的信号 中精确恢复。有损压缩中最常用的技术之一就是量化。量化又分为标量量化、 矢量量化( 分组量化) 和序列量化。标量量化每次只量化一个采样，所有采样 都通过特性相同的量化器进行量化，每个采样的量化是相互独立的。矢量量化 和序列量化则利用了相邻采样之间的相关性。矢量量化也称分组量化，在量化 时用输出组集合( 码书) 中最匹配的一组输出值( 码字) 来代替一组输入采样 值( 输入矢量) 。序列量化则在分组或非分组的基础上，利用一些相邻采样之间 的相关信息对采样序列进行量化，典型的有预测量化。 量化是a d 转换的核心。最基本的标量量化器的功能为对于每一个模拟采 样，在预定的有限集合中找到与该采样值最接近的数值。电平标量量化器可 定义为一个映射q ：r c 。r 为实数集，c = 轨，咒9e , 蜘 c r 为其中的一个 子集。c 称为输出集，也称为码书，该集中的元素只称为输出电平或量化电平。 假设量化电平按数值从小到大升序排列，则两个相邻量化之间的间隔就称为量 化阶距。这个量化电平将实数集r 划分成个子集足，f = 1 ，2 ，n 。子集r 包含所有被映射到输出电平只的输入采样，即局= x r ：q ( x ) = 乃) 。局满足 u 足= r 以及局f i r ，= ( f j ) 两个条件。子集足中的元素必然落在某个区间 ( 毛- ，玉】上，该区间称为量化区间，玉就称为边界点。 标量量化也称零记忆量化。它一次量化一个采样值，并对所有采样都使用 特性相同的量化器。在给定量化电平数目的情况下力求使量化误差最小。当前 采样值的量化值只与当前输入采样值有关，而与其它采样值无关。由于每个量 化电平可用一个l o g ，n 位的二进制数来编码，因此这种标量量化器的编码速率 为，= l o g ，n ( 比特采样) 。 根据量化区间的划分方式和量化电平的选取方式，可得到不同的标量量化 器，如均匀量化和非均匀量化。均匀量化是指所有量化阶距以及规则区内各量 化区间大小均为常数。在均匀量化中，其量化信噪比随量化电平数的减少会明 显下降，尤其是在小信号幅度时信噪比很低。而非均匀量化则根据信源概率分 布来确定相应的量化间隔和量化区间。在非均匀量化中面对的核心问题是，在 不均匀概率密度函数的条件下，该如何划分量化区间和确定量化值。 划分量化区间和确定量化值应与量化噪声功率有关，最佳的量化划分和量 化值应使量化噪声信号的平均功率最小。l l o y d 和m a x 分别在1 9 8 2 年和1 9 6 0 年用量化器的输入和输出之间的均方误差作为失真度量分析了量化噪声，得出 了设计最优量化器的必要条件，分别为质心条件和最优划分条件【1 】。这两个条 件的意义在于指导了最佳标量量化器的设计方法。 质心条件是指在量化区间给定的前提下，使量化噪声最小的各量化值应该 乃= 嚣 亿， 最优划分条件是指在给定一组量化值的前提下， 端点应该是相邻两个量化值的中点，即： 毛= 掣 相应的最佳量化区间的各 ( 2 2 ) l l o y d 和m a x 同时给出了根据上述两个条件设计最优量化器的迭代算法。假 设输入采样x 和量化值乃之间的失真可用失真测度d ( x ，乃) 来表示。l l o y d 算法可 概括为如下几个步骤： 第l 步：生成初始码书，令迭代次数朋= l 。初始码书通常是能将输入采样 值粗略地划分为个胞腔的码书。可通过把输入采样的范围进行等分而得到 相应的个初始量化值。 第2 步：对于给定码书q = 咒，咒，蜘 ，确定其最优划分的量化区间， 即根据最近邻准则把所有输入采样值分配到个区间内。 第3 步：根据质心条件，计算各区间的质心，将此质心作为新码书q + 中 的量化值。 第4 步：计算码书c _ + 。的平均失真，若失真的收敛已达到预定条件则终 6 止迭代；否则令迭代次数m = m + l ，并转至步骤2 。 在上述迭代算法中可采用不同的终止准则，最常用有效的方法为检查失真 的下降程度，即( 见一见+ ) 见，其中见表示第m 次迭代后的平均失真。由于 平均失真是单调下降的，因此算法一定收敛。当平均失真不再有任何变化，或 者已经低于一个指定的阈值，则可以终止迭代。 l l o y d 算法已被推广到矢量量化器设计中，是矢量量化器设计方法的基础。 2 2 矢量量化定义与性质 矢量量化可看作是标量量化的推广，其定义如下 1 2 1 ： 维数为k ，尺寸为的矢量量化器q 定义为从k 维欧几里得空间瞅到一个 包含个输出( 重构) 点的有限集合c 的映射，即q ：r _ c 。其中 c - y l ，y 2 ，y _ ，y f r 七，i c f - 宣 i ，n 集合c 称为码书( c o d e b o o k ) ， 其尺寸为。码书中的个元素称为码字( e o d e w o r d ) 或码矢量( e o d e v e e t o r ) ， 它们均为时中的矢量。 输入矢量空间瞅通过尺寸为的矢量量化器q 后，被划分成个互不重叠 的区域或胞腔，这个过程称为输入矢量空间的划分。对于f f ，胞腔r 定义为： 墨= x r ：q ( x ) = y ， ( 2 3 ) 各胞腔须满足条件： 且对i j ，有： u 冠= 瞅 l 墨nr ；= ( 2 4 ) ( 2 5 ) 一个矢量量化器包含两个部分，编码器和解码器。编码器占是从r 到索引 集合r 的映射，而解码器d 则是从索引集合r 到重构集合( 即码书) c 的映射， 即： 占：r - - - t , fd ：r c( 2 6 ) 7 若给定输入矢量空间的一种划分，则可确定某个输入矢量的编码索引。根 据该索引即可通过简单的查表操作从码书中找出相应的重构矢量。在编码的过 程中，不需要给定码书，只需确定每个输入矢量落在哪一个胞腔内。而解码的 过程实际上是在给定码书中的查表操作，只需给定码书，并不需要知道胞腔划 分。由于在多数情况下，码书可隐含地确定胞腔划分，因此编码操作通常是通 过码书完成的。解码器有时也被称作“逆向量化器一。如图2 - l 所示，整个矢量 量化量化器可看作由编码器和解码器的级联组成，而整个矢量量化操作可看作 两步操作的复合，即： q ( x ) = d 占( x ) = d ( s ( x ) ) ( 2 7 ) 图2 1 矢量量化器级联结构示意图 图2 2 描绘的是一个基本的矢量量化编码、传输和解码过程。由图所示，矢量 量化编码器根据给定的失真测度在码书中搜索与输入矢量最匹配的码字，获得 该码字的索引值。传输过程中仅传输编码所得的索引值。接收端解码时，由解 码器根据所接收到的码字索引在码书中查找出对应的码字作为输入矢量的重构 矢量，这些重构矢量即为解码器的输出结果。 8 蝙码器解码嚣 口口 际订! ! 苎呈嗣 噔靶产点 图2 - 2 矢量量化编码和解码示意图 矢量量化是一种数据压缩技术。从广义上讲，对数据进行压缩就是减少分 配给指定消息集合或数据采样集合的信号空间大小。其中的信号空间既可以指 物理容积，也可以指时间间隔或带宽。数据压缩的主要目的为降低码速率或者 减少存储空同。 矢量量化是标量量化的一种自然推广。标量量化在消除数据冗余度时利用 了数据间的线性依赖性和概率密度函数的形状。在信息论中，香农提出即使信 源是无记忆的，利用矢量量化编码代替标量编码总能在理论上获得更好的性能。 矢量量化之所以能够压缩数据，在于它有效地利用了矢量中各分量问的四种相 关性质，包括线性依赖性、非线性依赖性、概率密度函数形状以及矢量维数。 一个t 维的最优矢量量化器性能总是优于k 个最优标量化器。根据上文描述的矢 量量化器基本编解码原理，假设一个矢量量化编码器的码书由个k 维矢量组 成，则经过编码后得到的码字索引需用1 0 2 ，比特表示，相当予每个采样只需 l o g ，肛比特，接收端将根据所接收的码字索引对输入矢量进行重构。若每个 采样有时个电平，则k 维输入矢量空间大小为盯。因此最大压缩比可达 r = m 。因此在相同的速率下，矢量量化的失真明显比标量量化的失真小。 而在相同的失真条件下矢量量化所需的码速率比标量量化所需的码速率低得 多。无论信源有无记忆，矢量编码总是优于对单个样值逐个编码的，并且当矢 量维数趋于无穷大时，编码性能可逼近速率失真界。但是，矢量量化的复杂度 则比标量量化的复杂度高并且随着矢量维数成指数式增加。 2 3矢量量化关键技术 矢量量化有三大关键技术，分别是码书设计、码字搜索和码字索引分配。 2 3 1 码书设计 矢量量化的首要问题是设计出性能良好的码书。假设有m 个训练矢量。要 生成大小为的码书，其中f 。令迭代次数，= f + 1 ，转至步骤2 。 上述l b g 作为一种经典的码书设计算法至今仍被广泛采用，但近年来也陆 续出现各种改进的算法，大致可分为四类。第一类是直接针对l b g 算法的改进， 例如对码书初始化方法作的改进1 4 1 ，以及提高码书设计时码字匹配的速度等 【1 5 ，1 6 】。第二类是基于神经网络的码书设计算法，例如自学习神经网络和竞争 学习神经网络【1 7 2 0 l 等。第三类是基于全局优化技术的码书设计算法，如随机 松弛算法【1 7 】、模拟退火算法 1 8 1 、遗传算法【1 9 】和禁止搜索算法【2 0 ，2 1 等。第 四类是基于模糊聚类理论的码书设计算法 2 2 1 。 2 3 2 码字搜索 矢量量化编码过程本质上可归结为在给定码书中搜索与输入矢量最匹配码 字的过程。因此码字搜索问题是影响矢量量化器效率的重要因素之一。设给定 的码书为c = y l , - - , y i y ，r ) ，码书大小为，码字维数为k 。矢量量化码字 搜索问题就是在如何在码书c 中搜索与输入矢量x 最匹配，即失真测度最小的码 字y ，。穷尽搜索算法是一种最原始、最直观的最近邻码字搜索算法，需要计算 输入矢量x 与所有码字之间的失真，通过比较找出失真最小的码字。若采用欧氏 距离作为失真度量，则每次失真计算需要k 次乘法和( 2 七一1 ) 次加法，用大小为 的码书对矢量x 进行编码则需要撇次乘法、( 2 七一1 ) 次加法和( 一1 ) 次比较运 算。由于穷尽搜索算法的计算复杂度由码书尺寸和矢量维数决定，因此对于大 尺寸的码书和高维的矢量，码字穷尽搜索所需的计算量将很大。研究码字搜索 算法就是要通过设计快速有效的算法降低码字搜索所需的计算复杂度。 若码字搜索开始于一个跟输入矢量相对接近的码字，则可以比较容易地检 验和排除掉后续的候选码字。同时，有效的码字删除准则可以减少匹配时需要 进行失真计算的码字数目。因此，一种快速有效的码字搜索算法须具有三个必 不可少的因素：良好的初始匹配码字，强有力的码字删除准则以及合理的码字 搜索顺序。为提高码字搜索的效率，快速码字搜索算法往往需要计算码字的特 征值或对码书进行预排序等操作。这类附加计算及由此导致的附加存储空间都 属于快速码字搜索的代价条件。如何在提高搜索效率的同时，尽量减少这类额 外计算和存储开销是码字搜索算法研究的主要问题之一。 近年来出现的各种各样的快速码字搜索算法，大致可分为五类，包括基于 不等式判据的快速码字搜索算法【2 3 2 6 】、基于变换域的快速码字搜索算法 2 7 ， 2 8 、基于金字塔结构的快速码字搜索算法 2 9 ，3 0 、自适应搜索范围及顺序的快 速码字搜索算法【3 l ，3 2 1 。 2 3 3 码字索引分配 相对于前两项关键技术而言，码字索引分配算法是矢量量化技术领域中较 新的研究热点。该问题的产生是为了减少由信道噪声引起的失真。在信道噪声 的影响下，编码所得的索引值经过信道传输后可能出现错误，导致在解码端的 输出中引入额外的失真。通过对码字索引进行优化分配将减少这种额外失真。 1 2 但是对于一个大小为的码书，其索引分配方案共有! 种。要在! 种可能的 码字索引分配方案中寻求最优的方案是相当困难的。码字索引分配算法的目标 就是要在尽量减少计算复杂度和搜索时间的前提下，求得全局最优或者接近全 局最优的码字索引分配方案，从而减少由信道噪声引起的失真。 码字索引分配算法是矢量量化技术中的较新的研究领域。文献 3 3 1 最早提出 码字索引分配问题及其数学模型，该文利用模拟退火算法避免穷尽搜索。文献 3 4 】 采用了b s a ( b i n a r ys w i t c h i n g a l g o r i t h m ) 算法，通过一系列的索引交换使每次 交换后的失真减少。文献【3 5 1 利用码字概率信息对码字索引进行有效分配。文献 【3 6 1 在码字索引分配中用m i n i m a x 设计准则替代均方误差准则。文献 3 7 1 采用了 并行遗传算法。文献 3 8 - 4 0 采用了禁止搜索算法。文献【4 l 】采用了并行禁止搜索 算法。 2 4 矢量量化器主要类型 矢量量化器主要由编码器和解码器组成。其中，编码器主要由搜索算法和 码书构成，而解码器主要由查表方法和码书构成。矢量量化器的研究目前已经 在最基本的矢量量化器基础上演变出各种各样的矢量量化器类型。这些矢量量 化器大致可分为两大类：无记忆矢量量化器和有记忆矢量量化器。无记忆矢量 量化器包括穷尽搜索矢量量化器和约束矢量量化器。有记忆矢量量化器包括预 测矢量量化器、有限状态矢量量化器和自适应矢量量化器。 穷尽搜索矢量量化器通常被认为是最基本的矢量量化器，也称最近邻矢量 量化器或标准矢量量化器，其原理是计算输入矢量与码书中所有码字间的失真， 取失真最小的码字作为输入矢量的重构矢量。 针对标准矢量量化器复杂度高和比特率固定的不足，研究者提出了各种各 样的矢量量化器改进类型，大致可分为四大类。 第一类为约束矢量量化器( c o n s t r a i n e dv q ) ，对基本的矢量量化器附加各 种各样的约束条件，以牺牲部分性能为代价达到降低复杂度的目的。这类矢量 量化器典型的有树型矢量量化器【4 2 4 4 】、分类分裂分段矢量量化器 4 5 - 4 7 1 、乘 积码矢量量化器 4 8 ，4 9 】、变换域矢量量化器【5 0 5 2 】、多级矢量量化器和格型矢 量量化器 5 3 ，5 4 等。 第二类为预测矢量量化器( p r e d i c t i v ev q ) 【5 5 ，5 6 ，这是一类有记忆的矢量 量化器，可分为线性预测和非线性预测两种。其基本原理是先将量化电平通过 预测滤波器，对预测误差进行量化编码，而不对原始信号直接量化编码。 第三类是有限状态矢量量化器( f i n i t e s t a t ev q ，f s v q ) 【5 7 ，5 8 。f s v q 可 看作若干个独立的无记忆矢量量化器和一个选择规则的结合，该选择规则决定 从若干个码书中选取哪一个来对当前的输入矢量进行量化编码。当前状态决定 了当前输入矢量所采用的码书，而当前输入矢量的编码结果和当前的状态共同 决定了下一个状态，即决定了下一个输入矢量将采用的码书。 第四类是自适应矢量量化器( a d a p t i v ev q ) 【5 8 - 6 0 1 ，该类矢量量化器的码 书不是固定的，而是自适应于输入矢量。典型的有均值自适应矢量量化器、增 益自适应矢量量化器和地址矢量量化器等。 2 5矢量量化在图像处理中的应用 矢量量化是分组量化的一种形式，其发展可追溯到1 9 5 6 年，由s t e i n h a u s 第一次系统地阐述了最佳矢量量化问题。1 9 7 8 年，由b u z o 第一个提出实际的矢 量量化器。1 9 8 0 年是矢量量化技术研究的一个里程碑，l i n d e 、b u z o 和g r a y 三 人将l l o y d 算法【6 l 】作了推广，发表了第一个矢量量化器设计算法，即著名的l b g 算法 1 3 】。从此，对矢量量化的理论和应用研究全面展开。理论研究包括各种改 进的矢量量化器、码书设计算法、码字搜索算法和码字索引分配算法等。应用 研究则已推广到图像的矢量量化压缩、语音的矢量量化编码和识别，甚至已开 始研究矢量量化系统的硬件实现问题。 矢量量化的许多结构模型和设计方法都是标量量化的自然推广，但又并不 是标量量化的简单推广。从一维到多维的跳跃促使大量的新思想、新概念、新 技术的出现，因此矢量量化的重要性和应用领域也逐步增加与扩大。 矢量可用于表示各类数据，例如从连续语音信号上截取的一小段语音波形， 或是对图像进行分割获得的- d , 块图像。矢量还可以用于表示各类参数或系数， 如语音的线性预测编码系数、倒谱系数和增益参数等，也可以表示图像的d c t 变换系数等。矢量量化的另一重要应用领域是模式识别。将预先设计的标准模 式集合以码书形式存储，输入模式则由码书中的码字即已存储的模式近似匹配 1 4 在另一些应用中，矢量量化发挥的是降低复杂度的作用。对于一些复杂的信号 处理过程，通过矢量量化降低比特数可简化后续计算。 本论文主要关注矢量量化在图像处理领域中的应用。图像处理是一个很广 阔的研究领域，包含诸多方面和层次。完整的数字图像处理工程大致可分为以 下几个方面：图像信息的获取、图像信息的存储、图像信息的传送、图像信息 的处理以及图像信息的输出