（控制理论与控制工程专业论文）现代信息处理中关键技术的研究与应用.pdf

优秀工程奖。本文第八章全面介绍了这方面的工作。 2 ，作者在攻读博士学位期间，参加了 天津市政府上网工程项目，全文 检索技术在该项目中得到了很好的应用， 先后获得天津市科技奖和天津 信息港优秀工程奖。本文第七章有专门一节介绍这方面的工作 关键词,a编码， ， 一一朴一一一一一 a b s t r a ( ab s t r ac t b o t h t h e t h e o ry a n d a p p l i c a t i o n o f m o d e rn i n f o r m a t i o n t e c h n o l o g y i n c l u d e a w i d e r a n g e o f r e s e a r c h a r e a . i n t h i s d i s s e r t a t i o n , i w a n t t o i n t r o d u c e s o m e r e c e n t t h e o r e t i c a l a c c o m p l i s h m e n t s a n d a p p l i c a t i o n o n t h e i m a g e c o m p r e s s a n d t h e f u l l t e x t r e t r i e v a l w e r e t h o r o u g h l y s u r v e y e d a t f i r s t . t h e n i w a n t m y w o r k d u r in g t h e s t u d y o f p . h . d o c t o r .t h e m a i n r e s u l t s a r e a s f o l l o ws : 1 . t h e r e s u l t s o f t h e o r e t i c a l r e s e a r c h : ( 1 )a n a p p r o a c h b a s e d o n l e a s t s q u a r e t h e o ry i s p r e s e n t e d f o r p r e d i c t i v e c o m p r e s s . t h e a p p r o a c h d i ff e r s fr o m o t h e r m e t h o d s a t t h a t i t d o e s n o t d e m a n d t h e r e s u l t o f c a l c u l a t i n g a u t o c o r r e l a t i o n m a t r i x . t h e r e c u r s i v e a l g o r i t h m i s p r e s e n t e d . i t c a n b e r e d u c e d c a l c u l a t i o n l o a d a n d u s e d o n l i n e . ( 2 ) r e s e a r c h i s d o n e o n p r e d i c t i v e c o m p r e s s o f t h e t e x t i m a g e . i t i s p o i n t e d o u t t h a t t h e m e t h o d o f p r e d i c t i v e c o m p r e s s i s n o t e ff e c t i v e f o r t h e t e x t i m a g e w h a t e v e r i t i s h o w p r e c i s i o n o f r e s u l t . ( 3 )r e s e a r c h i s d o n e o n w a v e l e t t r a n s f o r m o f t h e b i n a ry i m a g e . i t i s p o i n t e d o u t t h a t t h e m e t h o d i s n o t e ff e c t i v e f o r t h e b in a ry i m a g e , b u t i t i s e ff e c t i v e f o r t h e t e x t i m a g e . ( 4 ) d r a w e x p e r i e n c e s fr o m m u l t i - i n p u t a n d m u l t i - o u t p u t s y s t e m o n m o d e r n c o n t r o l t h e o ry . a n e w s t r u c t u r e n e u r a l n e t w o r k ( c n n ) i s p r e s e n t e d . i t i s u s e d t o p a tt e rn r e c o g n i t i o n f o r i m a g e c o m p r e s s . a s t h e c o u p l i n g o f d e f e r e n t i n p u t a n d o u tp u t a r e r a v e l e d o u t o n t h e s t r u c t u r e o f n e u r a l n e t w o r k , t h e c o m p l e x s t r u c t u r e h a s b e e n s i m p l i f i e d t o m a k e i t e a s i e r t o t r a in i n g a n d r u n n i n g o n - l i n e . t h e r e s u l t o f t e s t i n g i s t h a t c o r r e c t r a t e i s mo r e t h a n 0 . 9 9 7 %. ( 5 ) t h e t w o - d o u b l e c o m p r e s s a l g o r it h m i s p r e s e n t e d . i t i s b a s e d o n c n n , wt , l s , a n d ml a ( mu l t i - l i n e a r - m o d e l a p p r o a c h ) . a b i n a ry i m a g e i s c o m p r e s s e d , b u t i t s s t r u c tu r e o f b i t - m a p i s o u t o f c h a n g e . s o y o u c a n c o m p r e s s i t u s e d j b i g 2 a g a i n . t h e r e l e v a n t w o r k i s f e w i n l i t e r a t u r e . ( 6 ) a n e w f u l l t e x t r e t r i e v a l s y s t e m i s p r e s e n t e d . i t i s b a s e d o n s i n g l e c h i n e s e c h a r a c t e r . t h e s y s t e m d i ff e r s fr o m o t h e r o n e s a t t h a t i t d o e s n o t d e m a n d c o m p u t e r t o i d e n t i f y v o c a b u l a r y fr o m s e n t e n c e . a s it i s a v e ry d i ff i c u lt o n c o m p u t e r t o i d e n t i 行v o c a b u l a ry fr o m s e n t e n c e , o u r m e t h o d i s v e ry v a l u a b l e . w e a l s o o p t i m i z e t h e s y s t e m s o a s t o a d d e d s t o r a g e l e s s 1 .2 t i m e s t h a n p r i m o r d i a l o n e ( r 。 1 .2 ) 一 3 abs tract 2 . t h e r e s u l t s o f a p p l i c a t i o n r e s e a r c h : ( 1 ) d u r i n g t h e s t u d y o f p . h . d o c t o r , i p r e s i d e o v e r t h e p r o j e c t o f t h e t i a n j i n d i g i t a l l ib r a ry . i t i s a g o o d c h a n g e . i c a n p u t m y r e s u l t s o f t h e o r e t i c a l r e s e a r c h i n t o p r a c t i c e . i n t h e p r o j e c t , i w a s a w a r d t h e e x c e l l e n t p r o j e c t p r i z e i n t i a n j i n i n f o r m a t i o n p o r t . i w a n t t o i n t r o d u c e t h e d e t a i l a b o u t i t t o y o u a t c h a p t e r 8 . ( 2 ) d u r i n g t h e t h e n , i a l s o t a k e p u t in t h e p r o j e c t o f t h e g o v e r n m e n t o f t i a n j i n o n t h e i n t e rn e t . i n t h i s p r o j e c t , t h e y u s e d m y r e s u l t o f t h e f u l l t e x t r e t r i e v a l s y s t e m. i t i s a v e ry s u c c e s s f u l . i w a s n o t o n l y a w a r d t h e e x c e l l e n t p r o j e c t p r i z e i n t i a n j i n i n f o r m a t i o n p o r t , b u t a l s o a w a r d t h e t h i r d p r i z e o f g o v e r n m e n t o f t i a n j i n . i w a n t t o i n t r o d u c e t h e d e t a i l a b o u t i t t o y o u a t c h a p t e r 7 . ke y wo r d s :f u l l t e x t r e t r i e v a l , f u l l t e x t d a t a - b a s e ,wa v e l e t t r a n s f o r m, p r e d i c t i v e ne u r a l n e t w o r k , mu l t i - l i n e a r - mo d e l a p p r o a c h , v i r t u a l l o c a l n e t ,mi d d l e w a r e , 亘 第一章 绪论 妇.1问题的提出 计算机和互联网是 2 0世纪人类最重要的技术发明之一。经过近几十年从概 念提出，理论研究和产业化发展，到2 1 世纪人类己经进入信息时代。现代信息 处理技术也成为科学界关注的焦点。 在现代信息处理领域里有许多关键技术: 从 第二代i n t e rn e t 到现代通讯技术; 从人工智能到计算机视觉技术; 从自 然语言理 解到知识挖掘技术， 等等。 在这璀璨星空的一个角落里， 有一个重要的课题， 它并不引人注目 的， 但却是最基础性的， 这就是信息数字化。 这个问题看似简单， 其实不然。首先请看两个例子: 1 。古籍文献 几千年人类文明的发展， 留下了非常宝贵的文化遗产一古籍文献， 然而由于 年代久远、历代战乱和古代造纸术和印刷术的局限等原因，许多己经成为孤本。 所以无论从永久保留 还是从文献实用的角度出发， 都必须进行古籍文献数字化抢 救工作。 1 7 7 1 年， 乾隆皇帝动员了4 0 0 0 多名学者和工作人员， 对当时能够收集到的 书籍进行了大规模的整理和发掘工作，历时1 0 年，终于完成了一部宏伟巨著， 这就是著名的 四库全书 。 四库全书收录了历代典籍 3 4 6 1种共 7 9 3 0 9卷，存目 书籍 6 7 9 3种共 9 3 5 5 1 卷，全书共约7 亿汉字。由 此可见其数量之巨大。 四库全书 全部手抄， 先后缮写7 部， 分藏于文渊、 文源、文溯 、 文津、 文宗、文汇、 文澜7 阁， 现仅存文渊、文溯 、文津、文澜 4 部，其余均毁于战 火。由此可见其珍贵。 1 9 8 3 年， 台湾商务印书馆出 版了台北所藏文渊阁本， 经1 / 4 缩印后的影印 本。 全套图书总重量达2 .5 吨， 售价达几十万元。别说是普通研究人员， 就是一般的 图书馆也很难承受。即便承受的起也给阅读和研究带来极大的不便。试想一下， 从重达2 . 5 吨重的图书中找到需要的文献是何等的困难。 经计算机处理后得到的全文版 四库全书 只须数十张光盘， 这不仅为 读者 购买、 携带提供了 方便， 推动了文化的传播， 而且提供了 检索、 查找、 用字统计 等新的古籍研究手段【 1 0 2 .信息爆炸 据国 家图书馆提供的 研究报告显示 2 :全世界每年约有 7 5 0万种新文 献出 现。如果每份文献平均2 0 0 页，每页1 6 0 0 字节，则每年文件信息的 增长量 就高 达2 .4 x 1 0 1 字节，即: 2 4 0 0 g字节。1 9 9 4 年，美国政府曾发出 替告:全世界几 个大图书馆， 若不从今年开始计划将资料数字化， 图书馆将走入历史， 而成为“ 书 籍博物馆” 3 0 如此巨大的数据量， 是迄今为止任何系统都没有遇到的， 这个问题的解决是 刻不容缓的。 因为人类己经积累了大量的文献， 而每天又有大量新的文献不断产 生。如果没有一个好的解决方案，很快就会被信息的海洋所淹没。 如此海量信息数字化应该采取什么技术路线呢?只有工业化生产的方式才 是解决问题的唯一出路。 这就提出了生产目 标、质量、 规模、效率、成本和标准 等一系列的问 题汇 1 0 e 1 .人工录入文本方式【 1 1 一个专业的录入人员， 每天最多可以录入2 万汉字 ( 包括: 排版、改正录入 错误，但不包括校对) 。如果加上校对，每天的录入量只有 1 万字。这是因为现 在工程化的人工录入文本的工艺是:同一文本由两个不同的人各自独立录入一 遍，然后再由计算机对比校正。否则，质量和录入工的生产进度就无法控制。 2 .计算机文字识别方式【 8 1 0 计 算 机 文 字 识 别方 式 也叫o c r ( o p t ic a l c h a r a c t e r r e c o g n it i o n ) 方 式。 o c r 首先用扫描仪等光学设备获得文献的图像， 然后利用各种模式识别的算法去分析 其中文字的形态特征，从而判断出文字的a s c 1 1 码。 近年来，由于硬件发展很快， 价格不断地下降而性能却节节上升， 使普通的 快速扫描仪的扫描速度可以 达到 每分钟连续扫描 2 4 页a 4 幅面的文献。如果忽 略计算机识别的时间 ( 实际上二者是并行操作) ， 按每页平均8 0 0 字计算，普通 o c r每分钟可以 输入 1 9 2 0 0 字。这相当于人工录入一天的工作量。高级一些的 快速扫描仪每分钟的扫描量已经达到1 0 0 页， 有的甚至达到2 0 0 页。 从理论角度 讲， o c r肯定是文献数字化的一个方向。 但目前对大规模的文献数字化加工， 如: 数字图书加工 o c r还没有进入实用阶段。其主要原因是 o c r的准确率还不够 高， 由 此产生较高的人工校对成本。 目 前对中等以上印 刷质量的中英文混排文献， o c r识别率在9 8 % 左右。 这对普通的应用， 如:办公自 动化是足够了，但对工 业化方法文献数字化加工就远远不够了。 专业录入人员， 错误率应在万分之五以 下，而目前中文o c r还做不到这一点。 o c r的过程可分为三步: 首先作为中间产品产生文献图像，然后模式识别 产生文本文件， 最后由人工校对。 由 于必须由 人输入一次文本文件作为校对的教 师信号，所以校对过程是很慢的。 扫描 模 式识 别 文 献图像 文 献文 本 图1 . 1 o c r文献数字化过程 何时完全采用o c r进行工业化数字化加工取决于o c r技术的进一步发展。 但无论怎样，图 像扫描都是一步必不可少的工序， 而它已 经可以 工业化生产了。 既然电子文本生产代价太大， 人们很自 然的想到退而求其次， 直接使用文献的扫 描图像口这种做法并不会在将来技术成熟后造成信息资源重复录入， 只要在扫描 时遵守一定的 标准( 3 0 0 d p i 的分辨率， 图 像尽可能的清晰) 。 但是以扫描图 像为介 质的文献在使用上有它的局限性，这主要表现在: 1 .因为是最简单的数字化初级产品，所以只能当作是纸张文献的数字化拷 贝，不能提供任何检索手段。 2 .因为图像文件比文本文件要大的多，所以不方便网上传输。 综合考虑文献数字化的成本、 占用的硬件资源、 网络带宽、 检索需求等因素， 一一一一一一一一一一一一一一一一 文献的数字化输入可分成以下三种情况: 1 .全文本方式 文献中所有文字全部文本化。它的优点:是存储容量小，网上传输快。可 以实现各种检索和文献再利用功能。 缺点是: 录入成本太高， 速度太慢，失去文 献原始面貌。 采用这种方式数字化的是法律法规， 政府文件等需要经常查询和引 用的文献。 2 .纯图像方式 只须将文献扫描成图像后即可使用。它的优点:是数字化加工成本低，速 度快， 并且保持了 文献原始面貌。 缺点是: 只能浏览， 不能检索。 存储容量太大， 网上传输太慢。 3 .全文本+ 纯图像方式 它是全文本方式和纯图 像方式的混合体， 在文本和图像之间建立索引关系。 这种方式既可以 对文献进行全文检索， 又可以 对感兴趣的文献调出它的图像， 使 用起来非常方便。 用o c r制作的电 子文献就可以 达到这种效果。 它既包含了前 两 项的全部优点; 也包含了 它们的 全部缺点， 所以 它只适合于一些研究项目 ， 如: 前面提到的 四库全书 。 4 .元数据+ 对象数据方式 这是目 前工程界普遍采用的电 子图书加工方式，因为它综合了前面三种方 式的 优点。 关于元数据和对象数据， 它们更深刻的实际背景。 在本文第八章会对 它们作一简单介绍，这里只是讲一下具体做法。 首先， 文献从中抽取元数据。 元数据也被称为“ 说明 数据的数据” ， 如:篇 名、出 版社、 作者、 关键字、目 录和摘要等少量关键信息。 然后，以 文本方式将 元数据存入计 算机。 对 象数 据就是文 献的内 容， 将它以 扫描图 像的 方式存入计算 机。 元数据作为“ 说明 数据的 数据” 主要用于检索。 用元数据中的 篇名、出 版 社等 信 息 可以 对 对 象 数 据的 存 储 位 置定 位。 用 元 数 据中 篇 名、 作 者、 关 键字 等 信 息 建立的 索引 可以 对对象数 据进 行分类。 用元数据中的目 录可以 和对象数据中的 每一页的图 像之间 建立索引关系， 以 便对它们定位。 元数据中 摘要是对对象数据 概述性的 描述， 可以 用于 全文 检索。 抽取元数据， 对信息的 再利用有非常重要的 意义。 对象数据扫描成图像可以 使数字化加工成本大大降低。 但扫描图像必须经 过压缩， 否则无法在网 上使用。 一页b 5 幅面的文献用3 0 0 像素/ 英寸的分辨率扫 描， 如果每一个像素用1 个字节表示 ( 2 5 6 灰度) ， 其数据量约为8 m b / 页。即使 用 i 位表示 ( 黑白二 值) ， 也需i m b / 页。如果不经压缩在速率为 9 6 0 0 b p s的电 话线上传输约需要巧分钟。 方法4 的实 质是“ 牺 牲空间 换 取时间” 。 它的 可行性如何? 下 面 还是以国 家 图 书馆的 研究报告 2 作为基本数据进行分析: 1 .数据存储能力分析 如果将对象数据由文本转换成图像，其数据量由每页平均 1 6 0 0字节增加到 1 .0 6 m字节 ( 黑白 二值，没有压缩) 。即增加了7 2 5 倍。全世界每年的信息增长 量: 7 5 0 0 0 0 0 x 2 0 0 x l .0 6 m = 1 .6 5 x 1 0 5 = 1 5 0 0 t 字节 以现在计算机硬件发展水平来看没有问题。 当然如果能压缩n倍， 本降到 / n 最好。 2 .数字加工能力分析 ( 1 . 1 ) 使存储成 国家图书馆数字 化加工中 心现在的图 像扫描( 3 0 0 d p i 标准) 最高生产能力是 每天2 0 万页 8 1 。 全世界每年的文献增加量: 7 5 0 0 0 0 0 x 2 0 0 = 1 .5 x 1 0 9 页 ( 1 . 2 ) 相当于该中心7 5 0 天的生产量， 这意味着文献图像扫描加工能力没有问题。 假设每篇文献的元数据需占5 0 个字段，每个字段的平均长度为1 5 0 0 字节， 那么7 5 0 0 0 0 篇文献的元数据的数据量为: 7 5 0 0 0 0 0 x 1 5 0 0 = 1 . 1 2 5 x 1 0 = 1 0 .4 8 g ( 1 . 3 ) 这表明元数据的数据量不到 对象数据的0 .0 4 。显然， 全世界每年录入1 0 .4 8 g 的数据是没有问题的。 3 .检索需求分析 元数据涵盖了对象数据的大部分关键信息，可以在某种程度上满足检索需 要。 至于满足程度的高低这取决于元数据提取质量的高低， 不能过分苛求，因为 文献元数据毕竟只占 对象数据的1 / 2 0 0 0 4 .网络带宽分析 前面已 经提 到一幅黑白 二值图 像如果不经压缩在 9 6 0 0 b p s的电 话线上传输 需要 巧分钟，这是根本无法忍受的。 所以图像压缩是这个解决方案的关键。另 外，由于是在线解压， 所以算法不能太复杂。 综上所述: 1 . 面对越来越严重的 “ 信息爆炸”局面，以 信息图 像处理作为初级数字化 手段是非常有必要的。 2 .面对今天网络带宽仍然很 “ 狭窄”的局面，图像压缩是解决网上 “ 交通 堵塞”必不可少的技术手段。 3 .面对日 益庞大的信息资源，必须研究比传统的基于关键字的检索更加有 效的检索手段，对信息进行有效的“ 过滤”才能很好的加以利用。 所以，在众多的现代信息处理技术中有两项非常值得深入研究的关键技术， 这就是:图像压缩和信息检索。 1 .2 经典图像压缩 本节讨论的范围是经典压缩理论，主要包括: 1 . 统计方法 2 . 预测方法 3 . 变换方法 1 .2 . 1 统计方法 统计编码是利用信源中符号的出现概率来寻找符号与编码长度的最佳匹配 编码方法。 它也叫嫡编码 ( e n t r o p y c o d i n g ) . 根据信息论的原理，如果给出现概率小的编码赋给较多的 b i t ，给出现概率 大的编码赋给较少的b i t 就可以 达到压缩的目 的， 这就是变长编码 ( v l c )的原 理。1 9 4 8 年， 香农 ( c . e . s h a n n o n ) 提出的的无损编码定理 2 0 指出 这种压缩的 极限就是信源的嫡。1 9 5 2 年，霍夫曼 ( d . a . h u ff m a n )提出了一种统计编码方 案， 这就是至今仍广泛应用的 霍夫曼编码 2 1 1 。 它完全依照信源每个字符的出 现 概 率， 构 造了 平 均 长 度 最 短的 异 字 头 码 字。 当 信 源 符 号 的 出 现 概 率p 、 = 2 - 时 ， 霍夫曼编码的平均码字长度等于信源的嫡， 所以有时也叫最佳编码。 但霍夫曼编 码也有它的局限性，这主要表现在: i .需要事先知道信源符号的概率分布。 2 .译码复杂度高。 3 输入符号数受限制于可实现的霍夫曼码表大小。 另一个典型嫡编码是算术编码 ( a r i t h m e t ic c o d i n g ) 2 2 2 3 1 ， 与霍夫曼编码 不同， 算术编码跳出了 分组编码的圈子， 它从整个符号序列出发， 采用递推形式 连续编码。 在算术编码中， 它不是将信源符号和编码之间建立一一对应的关系， 而是将整个符号序列映射到 0 , 1 1 内的一个个小区间，每个小区间的长度等于该 序列的概率， 再在该小区间内找出一个代表性的二进制小数作为实际上的编码输 出。 算术编码的平均码字长度逼近信源的嫡。 算术编码的发展也离不开 s h a n n o n 的贡献。早在 1 9 4 8 年，他就提出将信源符号按概率降序排序，用符号序列累进 概率的二 进制表示作为对信源的 编码， 并从理论上论证了 它的 优越性 2 0 . 1 9 6 0 年， p . e l i as 发现排序是不需要的， 只要编、 解码端使用相同的符号顺序即可【 2 7 1 . 但当时人们认为算术编码需要精度很高的浮点运算， 所以 没有过多的理会。1 9 7 6 年， r . p as c o和j . r i s s a n a n 分别实现了有限精度的算术编码。 1 9 7 9 年r i s s a n e n和 g . g . l a n g d o n一起将它系统化，并于1 9 8 1 年实 现了二 进制编码 2 8 1 . 1 9 8 7 年 1 . h . wi tt e n等人发表了一个实用的算术编码程序 2 4 即c a c m8 7 ， 同期 i b m 公 司发表了著名的q 一 编码器 ( 后用于j p e g和j b i g图像压缩标准) ， 从此算术编 码迅速得到了广泛的应用。 比较霍夫曼编码和算术编码， 我国学者吴乐南教授认为【 1 9 : 当信源符号概 率比较接近时， 建议使用算术编码， 因为此时霍夫曼编码的结果趋于定长码， 效 率不高。但在实现上，算术编码比 霍夫曼编码复杂，特别是硬件实现。 1 . 2 . 2 预测方法 现代统计学和控制理论中常常用到“ 时间序列分析” 的方法， 来解决动态系 统输出状态问题。这些理论研究和通信工程的需求，逐渐形成了预测编码 ( p r e d i c t i v e c o d i n g ) 理论。 信息 论中己 经证明: 对于m种取值的 符号 序列 x k ) , 其第 l个符号的嫡满足下式: 1 0 9 2 m _ h ( x l ) ? h ( x l x , - , ) _ h ( x , x l - t x l - 2 ) 1 . 3 第二代图像压缩 回顾图像压缩几十年的发展历史， 科学家们提出了诸如 h u ff m a n , d p c m和 d c t等压缩方法，目 前的许多国际压缩标准也是基于上述技术的，图像压缩已 得到较为广泛的实际应用。 然而， 随着人们对这些传统编码方法的深入应用， 也 逐渐发现了这些方法的许多缺点:在高压缩比时，图像会出现严重的方块效应， 人 类视觉系统h v s ( h u m a n v i s u a l s y s t e m ) 的 特性不易 被引入到 压缩算法中 等 等。 为克服传统压缩方法中的上述缺点， 也为了寻求更高的压缩比和更高压缩质 量的压缩方法， 人们在不断探索新的图像编码方法。 这一探索从表面上看， 是不 断采用新的信源建模的方法， 从实质上看，反映了人类对图像本质的不断深入的 认识过程。 每一次认识上的突破， 都导致数学方法上的突破， 而数学家的工作又 反过来有为图像压缩提供了强有力的数学工具。 1 9 8 5 年，m. k u n t 提出第二代编码技术的概念【 3 5 1 . k u n t 把上边讨论的三 大类方法统称为第一代编码技术， 它们归结起来都是以图像的某种统计模型为基 础，对单独的像素或像素块进行操作，以达到除去冗余目的。 k u n t 把8 0 年代以 后提出的以更加复杂的结构化的图像模型和人类视觉系统模型为基础， 产生的新 一类编码方法称为第二代编码技术。 第二代编码技术可分为两类: 基于局部操作 ( l o c a l o p e r a t o r b a s e d ) 的压缩技术和面向 轮廓/ 特征( c o n t o u r / t e x t u r e o r i e n t e d ) 的压缩技术。 本节， 要讨论的子带编码和小波变换编码属于第一类， 分形图像压缩编码属 于第二类。 1 .3 . 1 子带编码 s b c ( s u b b a n d c o d i n g ) 是一 种基于傅立叶分析的频域技术， 但它不是针对 单独的像素块进行操作， 而是以整个图像为对象进行不同频率的图像分解， 即多 分辨率分解。 通过分解产生不同频带 ( 子带) 的子图像， 然后根据不同频率进行 不同级别的量化，达到数据压缩的目的。 s b c是第一代和第二代编码技术之间的过渡。它的思想产生于第一代而它 的多分辨率分解的方法又为后来的小波编码所吸收。k u n t之所以把它归类于第 二代， 是因为它有类似于人类视觉系统模型的地方， 如并行带通滤波器的使用和 选择与人类视觉系统中方向敏感单元相似【 3 5 1 . s b c最早起源于电话语音压缩传输的多路复用技术。 1 9 7 6 年r . e . c r o c h i e r e 等人首先将它引入美国的贝尔系统【 3 6 1 。 后来它又广泛应用于数字音频压缩， 使 它成为这个领域国际标准的主要技术框架【 1 6 1 . 1 9 8 5 年， s . d . o n e i l 在他的硕士论文中首先将它引入到图像编码 3 7 技术 中。n e i! 的基本思想是: 1 .频谱分解 通过一个低频分解滤波器和一个高频分解滤波器把整幅图像的傅立叶频谱 分解成两个互不重叠的低频子带和高频子带。 2 .子带图像 针对每一个子带进行反变换， 得到一个低频子图像和高频子图像。 如果没达 一一一一一升一一一七叁遗建叁汪一 到 预定 的 分 辨 率 ， 转 到1 . 继 续 分 解。 如 果 达 到 预 定的 分 辨率 ， 即 得 到 一 组 互 不 重叠的子带图像。 3 .二次采样 对每一个子带图像的进行二次采样。 4 .量化和编码 每个子带单独使用一个比 特率进行量化和编码， 这个比 特率要和各个子带的 概率以及主观视觉的要求相匹配。 ( 逐行处理)( 逐列交 lh 理) 图1 . 5 二维图像的子带分解 对2 维图 像 的 具 体 操 作是: 首 先按 行的 方向 通 过 低通 滤 波 器 h l ( n ) 和高 通 滤波器 h h ( n )将原图 像x ( n , m )分 解成低频和高 频两个子带， 为了 使分解后的 子带总数据量与原全带相同，要对它们进行 2 : 1抽取。然后再按列的方向进行 同样的分解。 这样就构成一棵四叉树结构的子带分解。 当然这种分解可以继续进 行下去。这种分解叫 “ 等宽子带分解” 。如果只对低频部分继续分解下去，则叫 “ 倍频程子带分解” 。合成是分解的逆过程。和分解时类似，1 : 2内插器的作用 是在其输入的每个采样值间都对应插入一个 0值，使每个子带信号都和全带信 号等长， 频谱的重复周期也和全带信号完全一致， 最后， 经过合成滤波器组的作 用并将输出相加得到恢复图像。 版加加姗 图1 . 6 二维图像的子带合成 子带 编 码的 关 键是低 通滤波器h l ( n ) , s l ( n ) 和高 通滤波 器h , ( n ) , 8 x ( n ) 的设计。 设:归 一化的 采样频率 f= 1 ， 理想状态下低通滤波器 k ( n )和高 通滤波 器 h ( n ) 的带宽分别为( 0 , 1 / 4 ) 和( 1 / 4 , 1 / 2 )。由 于2 : 1 抽取， 理想的滤波器是不 可实现的。 因此在分解时必须允许有一个重叠，以避免有任何频率间隙， 漏掉能 量信号。而分解引入的混叠在合成时必须严格消除。 1 9 8 7年， p . p . v a i d y a n a t h a n提出t正交镜像滤波器组 q m f b ( q u a d r a t u r e f i l t e r b a n k s ) 的设计方法 3 8 ， 后来m . v e t t e r l i 等人又作了 进一步的完善 他们的方法是: 将分解滤波器组和合成滤波器组作为一个整体考虑。 得到图像完全重建的条 件 g l ( f ) h l ( f ) + g( f ) h ( f ) = 2 g l ( f ) hl ( - f ) + g ( f ) h ( f ) = 0 ( 1 . 8 ) 其中 h e , g , , g 。分 别 是h l , h h i s l 1 s 。 的 频 率 相 应函 数。 h l ( f )是一个理想的 低通滤 波器，即 自.j .盆nu r!、月.eses!t hl ( f ) j- ( 1 . 9) 命:低通滤波器平移f= 1 / 2 得到高通滤波器，他们呈现f = 1 / 2 镜像对称。 由此解方程组 ( 1 . 8 )得到q m f b 设计的一个约束条件 h ( f ) = h l ( 一) = h l ( f + 1 / 2 ) g l ( f ) = 2 h l ( f ) g n ( f ) = - 2 h ( f ) ( 1 . 1 0 ) 系数 “ 2 ，是用于补偿合成过程中1 : 2 插值的增益因子。 将 ( 1 . 1 0 ) 代入 ( 1 . 8 ) 得到q m f b 设 计的另一个约束条件 h ( f ) 一 h 异 ( 力= 1 ( 1 . 1 1 ) 由完全重建的假设得: x( f ) = x ( f )( 1 . 1 2 ) 即: 1 ( f ) 一 h l (f ) 一 h h (f ) x (f ) ( 1 . 1 3 ) 这表明子带分解时由抽取引起的混叠， 被子带综合时由内插引起的镜像完全抵消 掉了。 p . p . v a i d y a n a t h a n 还证明: 线 性 相 位的f i r( 有限 冲激响 应) 滤波器是不能 同时满足 ( 1 . 1 0 ) 和 ( 1 . 1 1 ) 的。 因 此， q m f b允许有一些幅度失真。 所要做的 工作是选择适度规模的 f i r或 i i r ( 无限冲激响应) 滤波器，去逼近 ( 1 . 9 )和 ( 1 . 1 1 ) ，然后由 ( 1 . 1 0 )去求得各个滤波器。 今h l 翻 h b o 低带 1 1 4 1 1 2 图1 . 7 q m f s 混盈 镜像抵消示意图 l l 2 l l , l h 2 l l 1 l i 2 l hi l h 2 毛 h1 h l , l 玩 hh 2 l l 1 h l 2 儿 且1 h h 2 毛 hi l i 2 月 l 1 l h 2 h l i l l 2 月 五1 l h 2 h h 1 h i 2 1 刃 - i h h 2 1 到 - i h 玩 土 q hi h h 2 h月1 l l 2 l l 1 l h 2 毛 l il h 1 h i 2 l l i h h 2 l l , h l 1王 且 王 1 图1 . 8等宽子带分解图1 9 倍频程子带分解 最后，小结一下s b c和d c t的关系: 1 它们都是以量化高频系数作为数据压缩手段，都是以 傅立叶变换作为分 解工具， 所不同的是d c t 作用于分块子图 像而s b c作用于整个图像， 这是因为 s b c设计了一对滤波器组。由于作用的对象不同，s b c不会产生块效应，所以 s b c的分频更加细腻，这使它获得更高的压缩比。 2 . 如果把d c t每块的系数按频率排列成数组来选择参数形成某种滤波器， 并由它来实现子带分解，就会产生重叠块， 这相当 于 d c t中的l o t 。而 s b c 决没有这种现象，这是因为它的滤波器是按照q m f b的方法设计的。 妇.3 . 2 小波变换 小波变换 ( w a v e l e t t r a n s f o r m)是继傅立叶变换以来科学方法的重大突破， 从原则上讲传统使用傅立叶分析的地方， 现在都可以 用小波分析取代。 小波分析 优于傅立叶分析的地方是它在时间域和频率域同时具有良 好的局部化性质， 由于 对高频成份采用逐渐精细的时域或空域采样步长， 从而可以聚焦到对象的任意细 节。从这个意义上讲，它被人们誉为 “ 数学显微镜”。 傅立叶分析之所以被人们广泛使用一个重要原因是它把时间域复杂的微分、 积分和卷积等运算简化为频率域简单的代数运算。 在图像处理中这为快速算法创 造了条件。 另一个重要原因它在时间域和频率域之间建立了 桥梁。 许多在时间域 ( 图像处理中表现为空间域) 看不清楚的特征信息， 在频率域一目了然。 这就是 “ 时频分析”的方法。d c t , s b c利用的就是这一点。 虽然傅立叶分析在科学发展中做出了极大的贡献，但人们对它并不十分满 意。 这是因为 用傅立叶分 析只能 获 得 信号.f o 的 整 体特性， 而 难以 获得信号的 局 部特性。 特别是信号的突变信息， 被傅立叶变换的积分作用平滑掉了。 造成这一 点的原因是傅立叶变换的频谱“ 波” 在整个频域是均匀的， 也就是它说不具 备 “ 紧支撑性” 信号的局部特性分析，是非常重要的。拿图像压缩来说， d c t 的块效应就是 典型的例子。s b c虽然通过q m f b 用镜像的方法抵消了 频率重叠，并用傅立叶 分析的方法实现了多分辨率分解。但从小波分析的标准看 s b c的子带分解是粗 糙的。1 9 9 2 年，m. a n t o n in i 等人就发表文章 5 6 说，他们用小波分析设计的7 抽头滤波器组的性能和 w. w o o d s 和s . d . o n e i l l 使用q m f b方法设计的3 2 抽头滤波器组性能相接近【 3 7 1 。图像中边缘的突变信息 ( 局部高频) 对图像的清 晰程度是非常重要的，它被均匀掉，会导致压缩虚像发生。 在d c t的讨论的产 生压缩虚像的三点原因中， 有两点和丢失局部高频有关。 为了弥补傅立叶分析中的这些不足，1 9 4 6年，g r a b o r 提出了一个变通的办 法是加上滑动的时间窗【 5 5 。但 g r a b o : 的时域分辨率被相邻窗函数的中心距离 t固定下来，更精细的局部变化无法观测。 综和各种综述文章，小波变换理论的思想形成于本世纪初。1 9 1 0 年由h a a r 提出h a a r 基后来证明是一个小波基。 1 9 3 6 年l i tt e r w o o d和p a l e y对傅立叶级数 建立了二进制频率分量分组理论， 即 l - p理论，这就是多分辨率分析思想的最 早 起源。1 9 5 2 年以 后的1 0 多年时间里， c a l d e r o n , z y g m u n d , s t e r n和 w e i s s 等 人的工作将 l - p理论推广到高维，并且建立了奇异积分算子理论。1 9 6 5年， c a l d e r o n又给出了再生公式，1 9 7 5 年c a l d e r o n 用他的再生公式给出抛物型空间 上的原子分解， 这个公式后来成为许多函数分解的出发点， 它的离散形式已接近 小波展开， 只是还没有得到组成一正交系的结论。此后许多数学家分别对各种不 同的目的给出各类函数空间的 “ 原子分解”、 “ 分子分解”、 “ 拟正交展开”、 “ 弱正交 展开” 、 “ 框架展开 ” 等等。 直到1 9 7 6 年， p e e t r e 在用l - p 方 法给出b e s o v 空间统一描述时， 给出了 b e s o v空间的一组基，其展开系数的大小刻画了 b e s o v 空间 本身。 1 9 8 1 年 s t r o m b e r g通 过 对h a a r 系的 改 进，