（计算机应用技术专业论文）图像检索的算法的研究图像检索中小波变换的fpga实现.pdf

摘要摘要基于内容的图像检索( c b i r ) 技术是当前研究的热点问题。它主要是利用图像的视觉特征，如图像的颜色、纹理、形状等特征来进行检索。它突破了传统的基于文本检索技术的局限，直接对图像内容进行分析并抽取特征，然后利用这些内容特征建立索引并进行检索。本文对一种常用的纹理分析方法小波变换做了研究，它是一种可达到时( 空) 域或频率域局部化的时频域或空频域的分析方法，其多尺度分解特性符合人类的视觉机制，更加适用于图像信息的处理。而提升小波变换又是一类不采用傅立叶变换作为主要分析工具的小波变换新方法，它的提出大大简化了小波变换的计算，使其在实时信号处理领域得到广泛的应用。通过提升的方法很容易构造一般的整数小波变换，由于图像一般用位数较低的整数表示，整数小波变换可以将整数序列的图像矩阵映射成整数小波系数矩阵，这就大大简化了小波变换的硬件电路设计。在当今数字化和信息化时代背景下，研究具有高速硬件处理功能的可编程逻辑器件在图像处理算法领域的应用已经成为当今研究的热点。本文采用a l t e r a 公司的c y c l o n ei i 系列芯片，根据提升小波算法设计图像检索的小波变换模块。文章最核心的算法一提升格式小波变换的一维变换模块设计和二维变换模块设计是我们研究的重点。一维提升小波变换模块采用流水线电路结构，即把提升小波的分解、预测和更新等计算过程分成各个模块独立实现以提高运算效率。同样，二维小波变换模块在一维提升小波的基础上实现的，针对周期镜像边界延拓的运算特点，采用了“内嵌边界延拓的电路结构，无需对输入数据进行预处理，并且在对电路时序进行详细分析的基础上，在关键路径上加入流水寄存器，提高了器件运行的速度。文章对提升小波变换的f p g a 实现中的大量细节问题进行了讨论，给出了提升小波变换模块的电路原理图，并对原理图进行了仿真测试，仿真测试结果不仅表明了模块功能的正确性，而且表明小波模块可以满足相应领域的实际要求。关键词：图像检索，f p g a ，小波变换，提升小波a b s t r a c ta b s t r a c ta tp r e s e n t ，c o n t e n t b a s e di m a g er e t r i e v a l ( c b i r ) i sb e c o m i n gah o tr e s e a r c ht o p i c i ti sar e t r i e v a lt e c h n o l o g yb a s e do nt h ev i s i o nf e a t u r e s ，s u c ha st h ec o l o r , t e x t u r ea n ds h a p eo ft h ei m a g e i ti sd i f f e r e n tf r o mt r a d i t i o n a lr e t r i e v a lt e c h n o l o g yb a s e do nt h et e x t t h i st e c h n o l o g yd i r e c t l ya n a l y z e si m a g ec o n t e n ta n de x t r a c t si m a g ef e a t u r e t h e s ef e a t u r et ob eb u i l ti n d e xa n db eu s e di nr e t r i e v a l t h ea r t i c l er e s e a r c hi n t oag e n e r a lm e t h o do ft e x tf e a t u r ea n a l y s i sb a s e do nt h ew a v e l e tt r a n s f o r m w a v e l e tt r a n s f o r mi sat i m e - f r e q u e n c yo rs p a c e - f r e q u e n c ya n a l y s i sm e t h o dw h i c hc a l ll o c a l i z et i m eo rs p a c ea n df r e q u e n c y m u l t i - m e a s u r ec h a r a c t e r i s t i co fw a v e l e tt r a n s f o r ma d a p tt ov i s u a lm e c h a n i s mo fh u m a na n di m a g ei n f o r m a t i o np r o c e s s i n g l i f t i n gw a v e l e tt r a n s f o r mi sn o taw a v e l e tr a d i xw h i c hi sc o n s t i t u t e do fs t r e t c h i n g ，m o v i n gam o t h e rw a v e l e tf u n c t i o n t h e ni ti san e ww a v e l e tt r a n s f o r mm e t h o dt h a tc a nn o tu s e sf o u r i e rt r a n s f 0 1 t na sm a j o ra n a l y s i st 0 0 1 p r o p o s i t i o no ft h el i f t i n gw a v e l e tt r a n s f o r ms i m p l i f yt h ec a l c u l a t i o no ft h ew a v e l e tt r a n s f o r mg r e a t l y s oi ti si m p l i c a t e de x t e n s i v e l yi nt h ea r e ao fr e a l t i m es i g n a lp r o c e s s i n g n l eg e n e r a li n t e g r a lw a v e l e tt r a n s f o r mc a nb ec o n s t r u c t e db yl i f t i n ga r i t h m e t i c b e c a u s et h ep i c t u r en o r m a l l ye x p r e s sa saf e wb i to fi n t e g e ri nc i r c u i ts y s t e m ，a n da ni n t e g r a lm a t r i xo fp i c t u r ec a nm a p p i n ga ni n t e g r a lm a t r i xo fw a v e l e tc o e f f i c i e n tb yi n t e g r a lw a v e l e tt r a n s f o r m ，d e s i g no fc i r c u i ts y s t e mo fl i f t i n gw a v e l e tt r a n s f o r mw a ns i m p l i f i e dg r e a t l y t o d a yi nb a c k g r o u n do fd i g i t a le r aa n di n f o r m a t i o ne r a , a p p l i c a t i o n si nt h ei m a g ep r o c e s s i n gf i l e do fp l dt h a th a sh i g h - s p e e dp r o c e s s i n gh a sb e c o m eah o tt o p i c n ea r t i c l e ，w h i c hu s et h ea l t e r ac y c l o n ei ic h i p ，d e s i g nt h ew a v e l e tt r a n s f o r mm o d u l eo fi m a g er e t r i e v a lb a s e do nl i f t i n gw a v e l e tt e c h n o l o g y n l el a s tp a r to ft h i sa r t i c l ei st h em a i nc o n t e n to ft h i sr e s e a r c h ，n a m e l y , o n e - d i m e n s i o n a lt r a n s f o r mm o d u l ea n dt w o d i m e n s i o n a lt r a n s f o r mm o d u l eo ft h em o s tc r u c i a la l g o r i t h mo fl i f t i n gw a v e l e tt r a n s f o r m o n e - d i m e n s i o n a lt r a n s f o r mm o d u l ew o r k sb a s e do np i p e l i n ea r c h i t e c t u r e n a m e l y , t h el i f t i n gw a v e l e ti n c l u d es p l i t ，p r e d i c ta n du p d a t ei no r d e rt oi m p r o v ee f f i c i e n c y a l s o ，t w o - d i m e n s i o n a lt r a n s f o r mm o d u l ed e s i g n sb a s e do no n e - d i m e n s i o n a lm o d u l e i te m p l o y e de m b e d d e de x t e n s i o na sb o u n d a r ye x t e n s i o nt oa v o i dt h ep r e p r o c e s s i n gc i r c u i t ；i n s e r t e dp i p e l i n er e g i s t e r si n t oc r i t i c a lp a t ht oi m p r o v et h et o pw o r k i n gf r e q u e n c yo fc i r c u i t ；e m p l o y e ds h i f t e r si n s t e a do fm u l t i p l i e r st os a v eh a r d w a r er e s o u r c e al o to fd e t a i l so fr e a l i z a t i o ni nf p g ao fl i f t i n gw a v e l e tt r a n s f o r ma r ed i s c u s s e di n t h i sp a r to fa r t i c l e ，a n dc i r c u i td i a g r a m so fl i f t i n gw a v e l e tt r a n s f o r mm o d u l ea r eg i v e n 1 1 1 ec i r c u i td i a g r a m sa r es i m u l a t e 1 1 1 er e s u l t so fs i m u l a t i o nn o to n l yi n d i c a t et h ec o r r e c t n e s so fm o d u l e sf u n c t i o n ，b u ta l s oi n d i c a t et h ew a v e l e tm o d u l ec a ns a t i s f yd i f f e r e n td e m a n d sa c c o r d i n gr e a ls i t u a t i o n k e y w o r d s ：i m a g er e t r i e v a l ，f p g a ，w a v e l e tt r a n s f o r m ，l i f t i n gw a v e l e t独创性：声明本人声明所呈交的学位论文是蠢人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签娅塞坐一日期：蝉墅尊丛关于论文使用授权的说明本学位论文作者完全了解江南大学有关保留、使用学位论文的规定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。签名：导师签名：第一章绪论第一章绪论1 1 研究的目的和意义随着多媒体技术，计算机通信技术及i n t e r n e t 网络的迅速发展，使得图像多媒体信息来源不断扩大，大容量高速存储系统为图像的海量存储提供了基本保障，各行业对图像的使用越来越广泛，如何从如此海量的图像信息中获取有用的信息即图像信息资源的管理和检索已显得日趋重要。图像的传统管理方式是以文件系统进行的【l 】，当用户查询一幅图像时，要逐一打开文件进行浏览才能找到其目标图像，随着图像文件数量的增加，查找效率急剧降低。因此图像检索的研究就显得很重要。近年来，基于内容的检索已成为一个研究热点，并成为多媒体数据库、数字图书馆等重大研究项目中的关键技术。1 9 9 2 年“基于内容的图像检索 一词开始在国际上使用。国内也很早就丌展了相关研究。l o 年来，这方面的研究和应用得到长足的进展。基于内容的图像信息检索自1 0 年前正式“冠名 以来，得到国内外信息领域科技人员的广泛重视和研究，迅速成为多媒体，特别是图像、视频和数据库技术中的研究热点之一。同时在一些有关图像理解和计算机视觉【2 】的书中，基于内容的视觉信息检索己占据了一席之地。基于内容的视觉信息的检索是一个挑战性的研究。它涉及许多领域，必须要考虑到许多问题，包括从获取和表达原始数据的方法到通过对这些数据和信息的处理、分析和理解以提供对内容的访问以及发送、显示和操作这些内容等。这里的每一个步骤都受到数据种类、应用领域和用户( 对系统有要求的人或信息代理) 的影响。由于上述问题的存在，基于内容的视觉信息检索的研究和应用还面临许多挑战。例如，如何建立语义层次的描述，使用户自然地与检索系统交互，又例如如何挖掘更多的实际应用场合，使视觉信息检索技术真正使用起来，都是推动基于内容的视觉信息检索所必须解决的问题。1 2 图像检索的研究现状经过几十年的研究，现在已经出现了很多商用和研究用的c b i r t 3 】系统。前者如i b m的q b i c 4 , - 5 , 6 】、v i r a g e 7 1 、a t r a s o r 公司的i m a g e f i n d e r 、y a h o o l 拘i m a g es u r f e r 等等。后者如麻省理工学院的p h o t o b o o k t 8 】和d l ：i 禾u 福尼亚大学的b l o b w o r l d ，伊利诺斯州大学的m a r s ，哥伦比亚大学的v i s u a l s e e k t 9 】等等。c b i r 的应用领域非常广泛，包括：犯罪预防。如在国家的安全部门中，可以建立图像数据库，存放有过犯罪纪录人的人脸图像和指纹图像等等，这样当有案件发生时，一旦找到嫌疑人的照片或指纹就可以搜索图像库进行人脸识别或者指纹识别，查询相关情况。知识产权保护。随着知识经济的到来，知识产权日益受到重视，并得到法律的保护。当注册商标的时候，需要对已有的数据库进行查询，检查是否已有重复或类似的图像。江南大学硕士学位论文这时就需要用到图像检索的方法。另外还有：军事用途、地理信息系统和遥感、医疗图像管理和辅助病情诊断、网络销售、时装设计、教育和培训、家庭娱乐等等。1 2 1 图像检索的主要方式基于内容的图像检索方式主要有三种，用户可以用任何一种适合的方式从图像数据库中查找自己需要的图像。这三种方式分别为：示例查询：即用户给出查询图像，系统根据查询图像提取特征进行查询。如用一幅人脸图像查询图像库中是否有另外一些该人的图像；主色查询：即用户给出查询图像的主要颜色或颜色的分布，系统根据主色的信息进行查询。如要查询蓝天下的雪山，就可以选择上面颜色为蓝色下面为白色的颜色分布来查询；轮廓查询：即用户借助系统提供的画图工具，画出所需图像的轮廓图，系统根据轮廓图查找相似的图像。其中示例查询为最通用也是最为方便的查询方式，一般的图像检索系统都为用户提供了这种方式。而主色查询一般用于彩色图像的检索，轮廓查询则多用于对于给定目标的查询，比如有意义的物体等。1 2 2 图像检索的主要技术因为图像使用者的需求不同，基于内容的图像检索可分为三个层次：1 利用原始特征，包括颜色、纹理【1 0 1 1 1 2 】、形状以及空间结构的查询，例如检索包含黄色或者蓝色的星星的图片；2 利用导出特征或逻辑特征的检索，其中加入了对于图像中目标的识别和描述，例如检索火车通过桥梁的图片；3 抽象语义特征如场景描述，包含对目标意义的复杂推理，例如检索壮观景色的图片。目前绝大多数检索系统，无论是商业系统还是实验系统，一般只能够在第一层次上取得较好的效果，少量的实验系统正在进行第二级的研究。特征抽取是基于内容的图像检索的基础，特征包括文字特征( 如关键字、注释等) 和视觉特征。视觉特征中，针对诸如人脸识别的特殊应用，有一些专用的基于知识的特征，而这里讨论的主要是一些可以广泛用于图像检索的原始视觉特征。目前比较成熟的特征是颜色、纹理、形状和物体之间的方位关系等，另外基于区域、目标以及语义描述方面的研究也逐渐增多。1 3 本课题的实际应用价值当代信息高速发展的社会中，图像是信息传播的重要方式之一。在如此多的图像信息中找到我们所需要的信息是一件很繁重的工作，这就需要找到一种高效的解决方法。f p g a 的出现正满足这种要求，它有以下的优点：1 容错性强对于做硬件设计和方案设计而言，硬件的特点决定设计需要考虑周全、细仔。如果2第一章绪论一旦硬件设计有错误，修改就比较困难。比如，d p s 的h p i v i 与a r m 的总线接口，你必须仔细地理解h p i 的时序和a r m 总线的时序。如果理解有误，将导致你调试的困难。但如果我们用f p g a 来完成接口的转换时序配合，一般我们只需要将h p i 和a r m 总线的口线等都与f p g a 相连接。这样就将硬件设计的风险转化为了软件设计( 我们的软件是可以修改的，并不是没有风险) 。对于一些较为复杂的功能需求，可以集成到一个c p l d f p g a中。使得硬件设计时没有考虑到或者考虑不周全的都可以以软件的方式弥补。2 灵活性对于设计过一板多用而言，硬件电路的灵活性就很重要了。比如设计一个通信控制板，它既用于m p e g 2 编码板，也用于m p e g 2 解码板。实现这个通用功能靠的是通信控制板上的一块f p g a 实现的。在f p g a 中灌入不同的代码，就实现了编解码的区别。这块板子还可以用于其它功能一致的项目，我们只需对接口做相应的修改。3 保密性对分离的逻辑器件组合，我们可以通过知道器件的功能和电路的连接，反向推出硬件原理图，从而得到设计的思路、实现方法。而对于采用c p l d f p g a 的电路，我只能从硬件电路上得到接口连接，而无法知道里面具体的实现。从而保护了自己的知识产权。4 效率高基于f p g a 的小波变换天生就有软件所无法比拟的优势硬件可以并行的运行。并且在硬件的适当位置加入流水线寄存器就可以构成流水线结构，运行效率可以提高好几倍，这是软件实现所无法可比的。因此硬件的实现常常用在实时处理领域里，如：数码相机中的图像压缩领域、实时图像采集系统、指纹识别等。而且我们还可以把设计好的电路封装起来，在其他的地方使用，这样不仅方便而且效率还很高。因此，基于f p g a 的小波变换是要设计一个效率高，灵活性强的一个电路。由于其灵活性，我们不仅可以把它用于实时图像检索而且还可以用于其他方面。这就是我们设计这个电路的主要目的。1 4 本文研究内容虽然图像检索研究近年来取得了比较大的进展，但现有的图像数据库检索系统仍然存在许多不足，从而离真正的实用还有一定的距离，需要进行更深入的研究工作。鉴于目前在计算机模拟人的视觉机理和特性方面存在相当的困难，我们难以获取图像的高层视觉特征，图像检索研究仍主要处于提取图像低层视觉特征的阶段上，因此，我们所进行的这项研究工作也不可能超越这一阶段。我们的目的不是建立一个完整的图像数据库检索系统，而是利用f p g a 来实现图像检索的一个部分。图像检索是一个应用前景很广泛的课题，所涉及的方面也很广。由于时间的限制我们只对图像检索的一个重要部分小波变换做了研究，使之能够在基于f p g a 的平台上得以实现。本文旨在探讨基于f p g a 的小波变换模块的实现方法。我们采用a l t e r a 公司的c y c l o n ei i 系列芯片。根据提升小波算法设计小波变换模块。论文的内容具体安排如下：第二章：简单介绍了小波变换的数学原理和物理意义，包括连续小波时频局域性的3江南大学硕+ 学位论文特征，离散小波变换系数的意义，多分辨分析引出的构造小波基的系统方法和计算离散小波的快速算法等。本章最后介绍了提升小波变换的基本思想，讨论了用提升方法构造小波基以及传统小波变换的提升实现。第三章：本章首先介绍了f p g a c p l d 器件的特征、发展趋势及f p g a c p l d 基本结构，然后重点介绍了本文用到的a l t e r a 公司c y c l o n ei i 系列芯片的结构特点，以及a l t e r a的f p g a 开发软件q u a r t u si i ，最后介绍了硬件描述语言v h d l 语言的特点。第四章：本章开始简单的介绍了5 3 提升小波的原理。然后根据提升理论实现了一维小波变换。并在实现一维小波变换的基础上根据e d a 的设计方法把二维提升小波变换分成了几个模块，并对每个模块都进行了详细的分析和仿真。第五章：总结。4第二章小波变换理论第二章小波变换理论小波变换( w a v e l e tt r a n s f o r m ) 是傅立叶变换的发展，中间经历了窗口傅立叶变换。原始数据一般是时间或空间信号，在时空上有最大分辨率。时空信号经傅立叶变换后得到频率信号，在频域上有最大分辨率，但其本身并不包含时空定位信息。窗口傅立叶变换通过对时空信号进行分段或分块进行时空一频谱分析，但由于其窗口的大小是固定的，不适用于频率波动大的非平稳信号。而小波变换可以根据频率的高低自动调节窗口大小，是一种自适应的时频分析方法，具有多分辨分析【1 3 , 1 4 功能。本节先讨论小波变换与( 窗口) 傅立叶变换的关系，然后依次介绍连续小波变换、离散小波变换、h a a r 小波变换1 5 】和第二代小波变换( 整数小波变换) 。2 1 傅立叶变换傅立叶变换是众多科学领域里( 特别是信号处理、图象处理) 重要的应用工具之一。从实用的观点看，当人们考虑傅立叶分析时，通常是指( 积分) 傅立叶变换和傅立叶级数。傅立叶变换是在实直线上定义的某个函数厂的傅立叶积分，。其中连续傅立叶变换的定义为：，( w ) = lf ( t ) e 叫 a r t( 2 - 1 )连续傅立叶变换的逆变换：1p f ( t ) = i ，( w ) e d w( 2 2 )z 刀。傅立叶变换是时域到频域互相转化的工具。从物理意义上讲，傅立叶变换的实质是把厂( z ) 这个波形分解成许多不同频率的正弦波的叠加和。这样我们就可以把对原函数f ( t ) 的研究转化为对其权系数即傅立叶变换f ( w ) 的研究。它对周期信号的分析具有良好的效果，对于大多数平稳信号傅立叶分析十分有效，因为信号的频率成分具有相当重要的作用。作为经典的信号分析方法傅立叶变换具有正交、完备等许多优点，并有e f t这样的快速算法，因此傅立叶变换方法在信号分析领域得到了广泛的应用。图2 - 1 原始信号f i g 2 - 1t h eo r i g i n a ls i g n a l江南大学硕士学位论文开图2 - 2 信号频率图f i g 2 - 2t h ef r e q u e n c yo fs i g n a l如图2 1 为一时域中的信号，将信号进行傅立叶变换后得到信号的频谱图如图2 2 所示。从图2 1 中我们看不出任何频域的性质。但从图2 2 中，我们可以明显地看出信号的频率特性。虽然傅立叶变换能够将信号的时域特征和频域特征联系起来，能分别从信号的时域和频域观察，但却不能把二者有机的结合起来。如上所述从图2 2 中可以看到信号的频率特性，但是却看不到信号的时域特性，因此傅立叶变换在将时域信号转换为频率信号后，时域信息则失去了。这是因为信号的时域波形中不包含任何频域信息。而其傅立叶谱是信号的统计特性，从其表达式中也可以看出，它是整个时间域内的积分，没有局部化分析信号的功能，完全不具备时域信息，也就是说，对于傅立叶谱中的某一频率，不知道这个频率是在什么时候产生的。这样的信号就面对一对基本的矛盾：时域和频域的局域化矛盾。在实际的信号处理中，尤其是对非平稳信号的处理中，信号在任一时刻附近的频域信息都是很重要。为了弥补傅立叶变换不能同时进行时域和频域局部分析的缺陷，加窗傅立叶变换 1 6 , 1 7 应运而生。2 2 加窗傅立叶变换加窗傅立叶变换的基本思想是：在傅立叶变换的框架中，把非平稳过程看成是一系列短时平稳信号的叠加，而短时性则是通过一个参数，的平移来覆盖整个时域，也就是说采用一个窗函数g ( t f ) 对信号厂( f ) 作乘积运算来实现在f 附近的开窗和平移，然后再进行傅立叶变换，其表达式为：s ( w , o = i 。f ( t ) g o - r ) e 一衍( 2 - 3 )在式2 3 中，其中” 表示复共扼，g ( t ) 是有紧支集的函数，f ( t ) 是待分析的信号。在这个变换中，e 一砌起着频限作用，g ( f ) 起着时限的作用。随着时间t 的变换，g ( f ) 确定的“时间窗 在，轴上移动，使f ( t ) 得到了仔细的分析。因此，g ( t ) 往往被称为窗e l函数，s ( w , r ) 大致反映了f ( t ) 在t 时刻，频率为w 的“信号成分”的相对含量。这样信号在窗函数上的展开就可以表示为在 f d ，f + d 】， w e ，w + e 这一区域内的状态，并把6第二章小波变换理论这一区域称为窗口，d 和e 分别称为窗口的时宽和频宽，表示了时频分析中的分辨率，窗宽越小则分辨率就越高。很显然，为了提高时域、频域的分辨率，d 和e 越小越好。但海森堡( h e i s e u b e r g ) 钡, 4不准原理指出，d * e c ( c 为一常数) ，即d 和e 是相互制约的，两者不可能同时都任意小。由此可见，加窗傅立叶变换虽然在一定程度上克服了标准傅立叶变换不具有局部分析能力的缺陷，但它也存在着自身不可克服的缺陷，即当窗函数g ( t ) 确定后，矩形窗口的形状就确定了，f 和w 只能改变窗口在相平面上的位置，而不能改变窗口的形状。可以说加窗傅立叶变换实质上是具有单一分辨率的分析，若要改变分辨率，则必须重新选择窗函数g ( f ) 。对非平稳信号，在信号波形变换剧烈的时刻，主频是高频，要求有较高的时间分辨率( 即d 要小) ，而波形变换比较平缓的时刻，主频是低频，则要求有较高的频率分辨率( 即e 要小) 。总之，由于加窗傅立叶变换的时一频窗口大小不能任意改变，因此只能分析所有特征大致相同的信号而不适合分析多尺度信号过渡过程和突变过程，且其离散形式不能实现正交展开，难以获得高效算法，因此造成其应用上的缺陷，限制其应用范围。2 3 连续小波变换 1 8 , 1 9 , 2 0 】将任意r ( 灭) 空间中的函数f ( t ) 在小波基下进行展开，称这种展开为函数f ( t ) 的连续小波变换，其表达式为v e r ( a , b ) 饨砒以) = 去l 巾旷( 等) a t( 2 4 )其中式2 4 中，口为尺度因子，b 为平移因子，g t ( t ) 为母小波。它通过伸缩和平移可生成函数族缈柚( f ) ) ；虬，6 ( f ) ： ( 堂) 口 o ，b r ( 2 - 5 )6 ( f ) 为虬。( f ) 的共轭。小波函数y ( f ) 的选择应满足以下条件：1 定义域是紧支撑的，即在一个很小的区间之外，函数值为零。此条件要求函数具有速降特性，以便获得空间局部化：2 满足容许条件，即q = e 箐d w 0 ，k 为整数。于是离散小波为u j , k = 专y ( 半) = a o - j 2 ( a o - j t - - 蛾)( 2 - 8 )相应的离散小波变换为：，l2 = lf ( t ) g k ( t ) d t( 2 - 9 )重构公式为：厂( f ) = c ，。，。( f )( 2 1 0 )式中c 是一个与信号无关的常数。通过改变a 和b 的大小，使小波变换具有可变的时间和频率分辨率，实现“变焦距功能，以适应待分析信号的非平稳特性。实际中常用的是离散二进正交小波变换2 2 2 3 1 ，及a 。= 2 ，6 0 = l ，相应的小波则为：i u j , k = 嘉( 半) = 2 - j 2 v ( 2 - j t - k 挺z( 2 - 1 1 )2 5 小波变换的两种实现技术m a l l a t 将计算机视觉领域内的多分辨率思想引入到小波分析中，提出了多分辨分析理论，并给出数学描述和一种子带滤波器结构的离散小波变换与重构算法m a l l a t算法【2 4 1 。该算法的本质是不需要知道尺度函数和小波函数的具体结构，由系数就可以实现信号的分解和重建，而且运用该算法可使信号每次分解的长度减半，是一种快速算法。后来，有人在此基础上，利用提升( l i f t i n gs c h e m e ) 方法，对其滤波器进行了提升，实现8第二章小波变换理论了整型变换。2 5 1 小波卷积模式m a l l a t 算法小波分解的公式1 2 5 1 为：c j ( n , 朋) = i l c j 一1 ( 七，) 勘坞咖( 2 - 1 2 ) 1 e z矿( 玎，m ) = i 1 c j 一，( 忌，) 勘啊勘( 2 - 1 3 )1 - 女，l e z( 玎，聊) = i 1 q 一。( 七，) 魂嘲g m 脚( 2 - 1 4 )k 1 e z刃( 朋) = i l q 一，( 七，j ) 嘲g t 一：。( 2 - 1 5 )- k d e z其中厅，g 分别为对应同一小波基的低通滤波器和高通滤波器，c 为原图像，c j ，彰，衫，巧为小波变换后的亮度和边缘子图像。二维m a l l a t 算法将函数( 图像) 分解成不同通道成分，每次小波分解实际上都将图像分解成为4 块子图，其中1 块对应平滑信息，另3 块对应细节信息。由于小波交换的减半抽样性质，经过若干次小波分解后，平滑信息系数和细节信息系数个数之和等于原始图像灰度系数个数，总数据量没有发生变化，因此如果用较少的比特数来表示它( 平滑信息基本保留，细节信息大大减少) ，即可达到图像数据压缩的目的。图2 3 中给出了图像数据基于二维小波分解的示意图。其中h o ，- , 为滤波器组，q ，口j ，为小波变换系数( f ，_ ，= o ，1 ) ，【2 为减半抽样。图2 - 3m a l l a t 小波变换示意图f i g 2 - 3m a i l a tw a v e l e tt r a n s f o r md i a g r a m小波变换的关键在于滤波器的选择上。d a u b e c h i e s 等人的9 7 基【2 6 】( c d f 9 7 ) 是许多研究者的首选，这组双正交小波基不仅具有良好的数学性质，也有良好的压缩性能。与小波变换相配套的零树编码算法也以它的高效而写进了m p e g 4 。常用的还有5 3 滤波器9江南大学硕+ 学位论文等。采用卷积运算方法，过程复杂，运算量大。c d f 9 7 确实压缩性能优良，消失距较大，能量集中性较好，但它的浮点系数加大了有关a s i c 设计的难度，不利于硬件的实现。当然，可以采用“近似整数化”来解决这一问题，但当a s i c 中的字长较短( 短于1 6 位)时，这种近似会带来不可忽略的误差。因而，有必要对此进行改进，l i f t i n gs c h e m e 应运而生。2 5 2 小波提升模式2 7 , 2 8 , 2 9 满足重构条件的紧支小波都可以分解成有限步简单的提升过程【3 0 】来实现。用矩阵表示时，一个提升步骤对应一个单元矩阵。分解的基本理论依据是矩阵代数，根据矩阵代数，任何具有多项式元素项且行列式为1 的矩阵都可以分解成一系列的单元矩阵。定理：若p ( z ) 的行列式等于1 ，即d e tp ( z ) = 1 ，则总存在l a u r e n t 多项式“，( z ) 和a ( z ) ( 1 i 聊) 及非零常数k ，使得：胁煎：z ) ) ( 只拼媾。足)p 式中，( z ) = 0 。由式( 2 1 6 ) 和小波滤波器的完全重构条件可推出：妒卜瞄抛，巩吲p x = x o ，五，x n 一，h ( z ) = “：z - k ，只( z ) = z _小d 卜1 ) ，= 矿一i d i - 。i七( p 7 幸s ，) ，= 巧一- z 吐。k( 2 - 1 8 )( 2 - 1 9 )( 2 - 2 0 )2 6 提升算法的优点相对于传统的小波变换，提升算法具有许多良好的、适合硬件实现的特点。不依赖于傅立叶变换，在空间域就能完成小波变换【3 1 , 3 2 】，实现对频率域信号的分析，此优点使得不需要很强的傅立叶分析背景便可以理解小波的特性和小波变换。同时，由于摒弃了传统的傅立叶变换，转而将高低通滤波器转化成一系列的预测和更新步骤，而预测和更新步骤的实现往往是很简单，并且具有很大的重复性，从而简化了小波分解和重构的实现结构，降低了运算复杂度。可以进行同址运算，大大减少了程序所需要的存储器开销。l o且引圳姚啦的姒mi io1，弘吩引。心l r 研d=，弘1j力力=墨4一予是分谚若“h力0“只吨卜力0以毛i iiz，(l，j - i 、一，一一”，旷研=i i彰，j、【第二章小波变换理论这个良好的特点使得提升算法非常适合于硬件实现，可以有效地提高硬件系统性能，以及硬件资源的利用效率。先分离、后运算的实现结构确保了不会产生冗余计算。传统的小波变换在实现时，首先进行滤波操作，然后进行抽样，滤波运算之后的结果数据只有一半得到了保留，即有一半的运算是无用的，提升算法由于采用的是先分离、后运算的方法，有效地解决了这个问题。这使得在硬件实现时，不仅提高了算法的实现速度和结果的产生速度，同时有效地降低了整个系统的功耗。提升算法的内部操作可以并行进行，有效地提高了小波变换运算速度。这个特点也使得提升算法非常适合于小波变换的硬件实现，流水线结构【3 3 】可以有效地将内部并行操作转化成为流水操作，从而成倍地提高运算速度。对于硬件实现而言，这就意味着非常可观的性能改善。基于提升算法构造的小波反变换可以很方便地由其正变换得到。从预测和更新的算法可以看出，二者的实现是非常类似的，除了计算的数据和参数不同，结构都是一样的。因而基于提升算法的小波反变换只是将正变换预测和更新的次序颠倒一下，以及反转系数前的正负号即可。这个优点使得我们在得n d , 波币变换的硬件架构的同时，可以很方便得到其反变换的硬件实现架构。通过提升算法，可以很方便地构造出整数到整数的小波变换。近年来，人们对整数小波变换在图像压缩领域中的应用研究越来越感兴趣。它是一种有限精度的计算，又是整数到整数的变换，它具有如下特点：( 1 ) 变换后的系数是整数，运算速度快：( 2 ) 计算时能最小限度地利用存储器；( 3 ) 能很方便地实现可逆换；( 4 )不依赖傅立叶变换，能保证重构，简单可靠；( 5 ) 同时继承了传统小波变换的多分辨率等特征。对于数字图像信号来说，其原始信号是整数，因此能较好地实现无损压缩，且已被j p e g 2 0 0 0 标准所采用，这不仅可以减少由于浮点数运算带来的计算量巨大和精度失真的问题，而且结构简单，有效地简化了算法的实现复杂度。下面给出几种图像处理中常用的小波的分解与重构步骤：( 1 ) h a a r d , 波h a a r d , 波滤波器组可表示为h ( z ) = 1 + z 一1g c z ，= 一三+ 三z - l柏= 1 2 + 歹1( 2 - 2 1 )( 2 - 2 2 )( 2 2 3 )g ( z ) = 一1 + z 。1( 2 - 2 4 )为了分解公式简单而说明问题，这里没有对滤波器进行归一化处理。多相位矩阵可表示为p c z ，= ( ：_ ：了? = ( ： ( 三一y 2 ( 2 - 2 5 ，比) 2 【ll 2j _ 【11j 【olj因此夕( z ，一= ；( z _ 1 ) ，= ( 三1 ：2 ) ( 二，? )c 2 - 2 6 ，由此可得小波分解算法江南大学硕十学位论文s t ( o ) 2 恐，码= x 2 ，+ l4 = 面们一而s ，2 s t ( o ) + 1 a r t由分解算法，通过反向进行操作，并改变相应的符号可得重构算法s ：s l 一d面o = d t + 唧，一j ( o ) 4 2 1 + 1 一“，x 2 ，= s i ( 0 )( 2 - 2 7 )( 2 - 2 8 )( 2 - 2 9 )( 2 3 0 )( 2 3 1 )( 2 - 3 2 )( 2 - 3 3 )( 2 3 4 )( 2 ) d 4 d 波d 4 小波可表示为：五( z ) = h o + z 卅+ 吃z - 2 4 - h 3 z - 3g ( z ) = - h 3 2 2 + z 1 一啊+ h o z - 1( 2 - 3 5 )其吣等加等加喾小错r1以力2k谁+ 每啦车剐彳1 ，44l l一1ll l司根据上述算法，与这个分解所对应的d 4 d x 波变换的提升实现如下：s o = x 2 ，d o - x 2 ，+ ld l = d o 4 3 s o霹计雩卅+ 宰以。1 2( 2 - 3 6 )( 2 3 7 )( 2 3 8 )( 2 3 9 )( 2 - 4 0 )o生压盟压。一一=咖“却矽如+觑。ll i、jz，lp。等等。-。_-_-i_-_-_-_l，川l0。l1joll_生压吐h q+ l i2研压了苗可砰旷第二章小波变换理论2 7 本章小结本章主要介绍了小波变换的基本原理，在回顾了小波变换的历史之后，给出了小波变换的定义，阐述了多分辩分析的思想，同时给出了小波变换的连续形式和离散形式。m a l l a t 算法和提升算法是小波变换的快速算法，正是快速算法的出现才把小波变换技术由理论推向了运用。本章还讨论了小波变换第二代小波变换一提升小波。首先介绍了提升小波的基本思想，然后介绍t n 用提升算法构造小波基的方法，通过提升算法的多相表示，对提升小波的概念和方法作了进一步的介绍，并通过因式分解技术对各种传统小波基转化为提升实现问题作了详细讨论，导出了更快速的小波变换算法。提升算法又有着结构简单，运算效率高，基于同址运算，便于硬件实现的优点。江南大学硕+ 学位论文第三章图像检索实验平台及开发环境3 1f p g a c p l d 简介在数字化、信息化高速发达的今天，数字集成电路得到广泛的应用，数字集成电路经历了从电子管、晶体管、中小规模集成电路、超大规模集成电路( v l s i ) 逐步发展为今天的专用集成电路( a s i c ) 。a s i c 的出现减少了产品的物理尺寸，提高了系统的可靠性，降低了产品的生产成本。但a s i c 的设计周期长，投入的费用高、风险大、灵活性差的缺陷限制了它的应用范围。硬件工程师希望有一种更灵活的设计方法，根据需要在试验室就能设计、更改大规模数字逻辑，研制自己的a s i c 并马上投入使用。这就是可编程逻辑器件( p l d ) 提出的基本思想。可编程逻辑器件随着微电子制造工艺的发展取得了长足的进步。可编程逻辑器件的发展可以分为三个阶段。早期的可编程逻辑器件只有存储少量数据，完成简单逻辑功能的可编程只读存储器( p r o m ) 、紫外线可擦除只读存储器( e p r o m ) 和电可擦除只读存储器( e e p r o m ) 三种。它们的工作原理为：将地址端作为逻辑函数输入变量，地址译码器作为固定与阵列来输出全部的最小项，而将它们的存储矩阵作为可编程的或阵列束把有关的最小项相或，然后由输出端得到输出变量，因此它们可以实现任何组合逻辑函数。其后，出现了能完成中大规模的数字逻辑功能的可编程器件，并正式称为可编程逻辑器件( p l d ) 。典型的p l d 主要有可编程阵列逻辑( p a l ) 和通用阵列逻辑( g a l ) 。p a l 是2 0 世纪末7 0 年代初出现的一种低密度、一次性可编写逻辑器件。p a l 基本是由可编程的与阵列、固定或阵列和输出反馈阵列构成。或门的输出可以通过触发器有选择地被置为寄存状态，因此它可以实现各种组合逻辑电路和时序逻辑电路。g a l 是2 0 世纪8 0年代中期推出地一种低密度可编程器件。它在结构上采用了输出逻辑单元( o l m c ，o u 印u tl o 西cm a c r oc e l l ) 结构形式。在工艺吸收了e e p r o m 的浮栅技术，从而使g a l器件具有可擦除、可重新编程、数据可长期保存和可重新组合结构的特点。因此，g a l器件比p a l