9_7提升小波变换图像处理算法的高速FPGA实现

第 39 卷第 6 期 2009 年 12 月 微 电 子 学 Microelect ronics Vol139 , No . 6 Dec. 2009 收稿日期 : 2009204203 ; 定稿日期 : 2009206204 9/ 7 提升小波变换图像处理算法的高速 FP GA 实现 王 　巍 , 杜治芸 , 曾 　勇 , 唐政维 , 李 　凯 , 李 　博 (重庆邮电大学 光电工程学院 , 重庆 400065) 摘　要 : 　提升结构 (Lif ting Scheme)是一种新的双正交小波变换构造方法。这种方法使得计算复 杂度大大降低 ,有效地减少了运行时间。介绍了基于 FP GA 的高速 9/ 7 提升小波变换的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ,提 出采用多级流水线硬件结构实现一维离散小波变换 (12D DW T) 。该结构使系统吞吐量提高到原 来的 3 倍 ,面积仅增加 40 %。在实现二维离散小波变换 (22D DW T) 时采用基于行的结构 ,可以提 高片内资源利用率和运行速度 ,满足小波变换实时性的要求。 关键词 : 　离散小波变换 ; 提升结构 ; 图像处理 ; FP GA 中图分类号 : TN919. 81 文献标识码 :A 文章编号 :100423365 (2009) 0620852205 High2Speed FP GA Implementation of 9/ 7 Lif ting2Based DW T Image Processing Algorit hms WAN G Wei , DU Zhiyun , ZEN G Yong , TAN G Zhengwei , L I Kai , L I Bo ( College of Electronics Engineering , Chongqing University of Posts and Telecommunications , Chongqing 400065 , P. R. China) Abstract : 　Lifting scheme is a new method for biorthogonal discrete wavelet t ransform (DWT) , which greatly reduces the computational complexity. In this paper , an FP GA2based high2speed 9/ 7 lif ting DWT algorithm was presented. Using multi2stage pipelining st ructure , one2dimensional discrete wavelet t ransform (12D DWT) was real2 ized to improve system throughput by 3 times , with only 40 % increase in size. A line2based architecture was applied to realize 22D DWT , which features better performance in terms of throughput rate and hardware utilization. Key words :　Discrete wavelet t ransform (DWT) ; Lif ting scheme ; Image processing ; FP GA EEACC :　1265A 1 　引 言 近年来 , 离散小波变换 ( Discrete Wavelet Transform , DW T)已经广泛应用于许多领域 ,如信 号分析、图像处理、模式识别、医学成像与诊断、数字 水印等。与离散傅里叶变换 (DCT) 相比 ,它具有良 好的自适应时2频窗口特性和多分辨率分析特性。 提升小波变换被称为第二代小波变换。这种新方法 不仅具有传统小波变换多分辨率的优点 ,并且简化 了运算及易于硬件实现 ,可以实现更快速的小波变 换算法 ,一般通过提升方法可以达到比 Mallat 算法 快 2 倍的离散小波分解 ,在 J PEG2000 中被推荐为 计算 DW T 的首选方法。提升方法可以实现完全的 同址运算 ,这一点与 FF T 类似 ,利用提升方法 ,正向 小波变换和反向小波变换结构是非常一致的 ,仅有 正负号的区别[124 ] 。有损压缩比无损压缩能实现更 高的压缩比 ,因此 ,提升小波中能实现有损压缩的 9/ 7 提升小波在数字图像编码中得到广泛的应用。 在实时图像编码系统中 ,由于小波变换需要较 大的计算量 ,靠软件实现无法满足实时需要 ,其硬件 实现具有重大的实际意义。由于 FP GA 的高集成 度、高速处理和使用灵活的特点使其在数字信号处 理领域得到快速发展。现在已经提出不少实现 DW T 的 VL SI 结构[ 529 ] 。文献 [ 5 ]提出一种有效的 多级流水线结构来实现 12D DW T ,但采用的小波系 数比较复杂 ,计算量较大 ;文献 [ 6 ]提出基于块的四 处理器结构来实现 22D DW T ;文献 [ 7 ]提出基于块 的扫描算法来实现高效的计算。这些都是基于块的 结构 ,因此需要很大的数据缓冲存储单元。文献[ 8 ] 第 6 期 王 　巍等 :9/ 7 提升小波变换图像处理算法的高速 F PGA 实现 提出一种有效的基于行的 22D DW T 结构 ,该结构 采用空间组合提升算法来计算 9/ 7 小波 ,这种隔行 扫描的方式在实现多级小波变换时减少了存储器的 大小 ,但系统吞吐量变小 ,硬件利用率降低。本文根 据模块化的设计思想 ,在 12D DWT 中采用更合理的 小波系数和多级流水线技术 ,在 22D DWT 中采用基 于行的并行结构 ,用基于 Altera 公司的 FPGA 芯片进 行设计 ,并用 QuartusⅡ软件来进行综合和仿真。 2 　提升小波变换 提升方法的主要特征是把高通和低通小波滤波 器分解成一列小型滤波器 ,进而转化为一列上下三 角矩阵 ,基本思想是用数据相关去除冗余[9 ] 。给定 一个互补滤波器对 ( ‰h , Žg ) ,存在能归一化到上下三 角矩阵的 Laurent 多项式 „s i ( z) 和 „t i ( z) ( 1 ≤i ≤n ) 和多项矩阵 ŽP( z) 如下 :ŽP( z) = ∏m i =1 1 0 　„si ( z) 　　1 　1„ti ( z) 　01 K　0 01K (1) 其中 , K是缩放因子 ,为常量。因此 ,提升小波正 变换必须先对输入数据做惰性小波变换 (分裂成奇偶 分量) ,然后交替执行提升步 ,最后把输出数据流乘上 K或 1/ K ,相应地产生低通和高通子带。提升算法分 为三个主要阶段 :分裂、预测、更新 ,如图 1 所示。 图 1 　提升小波结构 Fig. 1 　Split , predict and update phases of lifting based DWT (1) 分解 将数据列λj +1 , k 分解成为两个小的子集λj , k 和 γj , k 。假定相邻的数据间有最大的相关性 (在实际 中也往往是这种情况) ,按照数据的奇偶序号 ,对数 据列进行间隔采样 ,即 : 　　 λ21 , k =λ0 ,2 k , k ∈ Z γ21 , k =λ0 ,2 k+1 , k ∈ Z (2) 奇偶分量被认为是惰性小波 ,因为这个过程没 有去掉数据的相关性。 (2) 预测 对于图像数据 ,经过第一步分解后的两组数据 具有很大的相似性 ,即存在数据冗余。在预测阶段 , 主要是消除第一步分解留下的冗余 ,给出更紧凑的 数据表示。保持偶数样本不变 ,利用插值细分来预 测奇数样本 ,奇数样本与测值之差称为细节系数 ,即 用偶序列λ21 , k 预测奇序列γ21 , k 。原始数据越相关 , 预测步产生的数据就越接近原始的γ21 , k 。预测数 据和原始数据的差值代替原始数据 : 　　γ21 , k =λ0 ,2 k+1 - P(λ21 , k ) (3) 其中 , P 是预测算子。 (3) 更新 更新是利用更新了的奇数样本γ21 , k 来更新偶 数样本λ21 , k ,即 : 　　λ21 , k =λ21 , k + U (γ21 , k ) (4) 其中 ,U 是更新运算符 ,更新的目的在于保持信 号的某些全局特性不变 ,如均值。 9/ 7 提升小波有两次预测和更新的过程 ,结构 如图 2 所示。图 2 中 ,α、β、γ、δ为提升小波系数 ,由 9/ 7 Daubechies 滤波器系数因式分解得到。 图 2 　9/ 7 提升小波结构 Fig. 2 　9/ 7 lif ting DW T 表 1 列出其十进制表示及十六位二进制表示。 由十进制小数转化为十六位二进制小数采用的是先 将十进制小数乘以 216 ,即 65536 ,然后再换算成二 进制的办法。这种方法和直接用 2 的负数幂次来 近似的结果有一些差别。这将会造成最后结果有一 定的偏差 ,但不会对变换的结果产生很大的影响。 表 1 　合理的提升小波系数及定点二进制表示 　Table 1 　Lifting coeff icients : rational 9/ 7 and f ixed point binary of rational 9/ 7 Coefficient Rational 9/ 7 Fixed point binary of rational 9/ 7 α 23/ 2 11. 1 β 21/ 16 10. 0001 γ 4/ 5 00. 1100110011001100 δ 15/ 32 00. 0111100000000000 k 4/ 5 00. 1100110011001100 1/ k 5/ 4 01. 01 358 王 　巍等 :9/ 7 提升小波变换图像处理算法的高速 F PGA 实现 2009 年 这个近似产生的误差可用 peak signal to noise ratio ( PSN R)矩阵来衡量。当有效位保留 4 位 (二进制 系数小数部分为 12 位) 时 ,在较小的压缩比下 ,重 构图像的 PSN R 值有一定的差别 ,但最大不会超过 0. 1 dB ;5 位 (二进制系数小数部分为 14 位) 时 ,二 者的结果已几乎没有差别。 3 　9/ 7 提升小波的 FP GA 设计 3. 1 　12D DW T 的 FP GA 实现 9/ 7 小波变换前向滤波提升算法的流水线结构 如图 3 所示。 图 3 　1D2DW T 的基本流水线结构 Fig. 3 　Basic pipeline architecture of 1D2DWT 该结构需要 6 个乘法 , 8 个加法和 14 个寄存 器。普通的乘法器通常要消耗大量的面积。当乘法 器中的比特数很大时 ,可用移位加法器来实现常数 乘法。实现γ的乘法操作需要 7 个加法器 ,第一个 执行 c6 + c8 ,后五个执行 c6 + c8 的移位部分积的 和 ,最后一个执行与 c9 的和。 小波系数α的乘法操作需要 4 个加法器 ,β需 要 3 个加法器 ,δ需要 5 个加法器。归一化常数 K 有 8 个高位 ,而这步只是一个乘法操作 ,因此只需要 7 个加法器。1/ K 需要 1 个加法器。提升结构 DW T 中的加法/ 移位寄存器级数决定了寄存器间 的最大延迟路径。对这些结构也采用流水线操作 , 能增加数据吞吐量。执行γ的乘法操作的原始结构 如图 4 (a)所示。这个结构能由 Horner 法则和树高 度来改进 ,算法见 (5) 式。Horner 法则能减小部分 积的截断误差 ,树高度能减小加法操作之间的延 时[10 ] 。令 x = c6 + c8 , 那么 ,γ的乘法操作可表 示为 : 　 x(221 + 222 + 225 + 226 + 229 + 2210 + 2213 + 2214) = 　　　221 ( ( (( x + 221 x) + 224 ( (( x + 221 x) + 　　　224 ( ( x + 221 x) + 224 ( x + 221 x))) ) (5) 原始的算法级结构执行乘法的过程如图 4 (a) 所示。在前向路径中插入一些寄存器的流水线结 构 ,如图 4 (b) 所示 ,每级流水线只执行一次加法操 作。表达式中的 22i可通过右移 i 位来实现。 因此 ,流水线虽然增加了结构的面积 ,但减少了 关键路径延时 ,增加了系统的吞吐量 ,同时减小了功 率消耗。 3. 2 　1 级 22D DW T 的 FP GA 实现 因为图像信号是二维的 ,因此必须研究二维离 散小波变换的硬件结构[11 ] 。目前有两种实现 22D DW T 的方法 :可分离和不可分离结构[12 ,13 ] 。可分 离的方法是指重复运用 12D DW T 来实现 22D DW T ,结构如图 5 所示。这种方法需要一个转移存 储器来保存 12D DW T 的中间值 ,而且有系统延时。 不可分离的方法是直接把图像分解成四个子图像 , 图 5 　可分离的 22D DWT 结构 Fig. 5 　Separable 2D2DWT architecture 458 第 6 期 王 　巍等 :9/ 7 提升小波变换图像处理算法的高速 F PGA 实现 而不需要先行后列的处理。这样就能通过直接计算 22D DWT 来提高性能 ,但是 ,4 个 22D 滤波器需要更 多的硬件资源。为了折中考虑速率和面积 ,可采用基 于行的结构来实现 22D DWT ,电路结构如图 6 所示。 图 6 　基于行的 2D2DWT 结构 (B1) Fig. 6 　Line2based 2D2DWT architecture (B1) 图 5 中 ,输入图像样本被存在存储器 ,存储控制 模块控制输入到 12D DW T 的系数和把变换后的系 数读入到存储器。对于离散小波变换的公式 ,隐含 的条件是 ,输入的序列是无限长的 ,而对于一幅数字 图像来说 ,它的行和列都是有限的数字序列 ,因此在 图像编码的实际应用过程中 ,需要考虑边界的问题。 边界处理模块可用来解决这个问题。一个简单的方 法就是用镜像延拓边界信号 ,这里不详细讨论。在 计算完这四个部分后 ,LL 部分的变换系数被输入 到下一级小波变换中。 基于行的二维提升小波变换结构如图 6 所示。 这是一个 4 输入 4 输出的结构 ,由输入缓存单元 ( IBU ) 和小波变换模块 ( W TM ) 组成。FIFO1、 FIFO2、FIFO3、FIFO4 分别存储偶数行偶数列、偶 数行奇数列、奇数行偶数列、奇数行奇数列的数据。 W TM 包含两个相同的行变换模块 ( R2DW T1 和 R2DW T2) ,两个相同的列变换模块 (C2DW T1 和 C2DW T2) 。 用 xee ( m , n) 、x eo ( m , n) 、x oe ( m , n) 、xoo ( m , n) 分别代表偶数行偶数列、偶数行奇数列、奇数行偶数 列、奇数行奇数列的序列 ,Le ( m , n)和 He ( m , n) [Lo ( m , n) ]、Ho ( m , n)分别代表偶数行和奇数行的低频 和高频分量。在每个内部时钟周期 , 4 个输入 x ee ( m , n) 、x eo ( m , n) 和 xoe ( m , n) 、x oo ( m , n) 分别 并行读入 R2DW T1 和 R2DW T2 , R2DW T1 产生低 频分量 Le ( m , n) 和高频分量 He ( m , n) , R2DW T2 产生低频分量 Lo ( m , n) 和高频分量 Ho ( m , n) ,然 后 ,Le ( m , n) 和 Lo ( m , n) 并行输入到 C2DW T1 ,产 生子带低频2低频分量 (LL)和低频2高频分量 (L H) ; 同时 , He ( m , n) 和 Ho ( m , n) 并行输入到 C2DW T2 , 产生子带高频2低频分量 ( HL ) 和高频2高频分量 ( H H) 。 4 　实验结果 前述两个 12D DW T 结构的执行结果列于表 2。 这两个设计在 Quart us Ⅱ7. 0 环境中编译和仿真。 表 2 给出面积消耗、最大执行频率和流水线的级数。 结构 1 是图 4 (a)结构 ,结构 2 是图 4 (b)所示的有整 数移位加法器的流水线结构。结构 2 的最大执行频 率是结构 1 的 3 倍。所以 ,综合资源消耗和吞吐量 来考虑 ,结构 2 有更好的性能。对比文献[5 ]中的设 计 ,由于本文采用了更合理的小波系数、Horner 法 则和树高度而导致执行频率是文献 [ 5 ]中最高执行 频率的 1. 2 倍。 表 2 　实验结果 Table 2 　Implementation results 结构 芯片面积 (L Es) 最大工作 频率 (M Hz) 流水线 级数 本文结构 1 550 60 3 本文结构 2 812 186 18 文献[5 ]中的结构 3 766 157 21 5 　结束语 本文介绍了基于 FP GA 的高速 9/ 7 提升小波 设计方法 ,采用多级流水线实现 12D DW T 的高速 处理 ,并且可减少功率消耗。在实现乘法操作时 ,采 用 Horner 法则和 树高度来减小截断误差和延时操 作 ;在 1 级二维小波变换时 ,采用基于行的变换来实 现并行处理。该系统可用来处理多级小波变换。 参 考 文 献 : [1 ] 　CALDERBAN K R , DAUBECHIES I , SWELDENS W , et al. Losless image compression using integer to integer wavelet t ransforms [ C] / / IEEE Int Conf Im2 age Processing. Santa Barbara , USA. 1997 , 1 : 5962599. [2 ] 　SWELDENS W. The lif ting scheme : a custom2design const ruction of biorthogonal wavelet s [ J ] . Applied and Computaional Harmonic Analysis , 1996 , 3 (15) : 1862200. [3 ] 　刘军伟 , 饶妮妮. 提升小波变换的 FP GA 设计与实现 [J ] . 微计算机信息 , 2005 , 21 : 1322134. [ 4 ] 　熊承义 , 田金文 , 柳健 , 等. 基于线扫格式的 J PEG2000 小波变换的 VL SI 结构 [J ] . 微电子学 , 2005 , 35 (1) : 47250. 558 王 　巍等 :9/ 7 提升小波变换图像处理算法的高速 F PGA 实现 2009 年 [5 ] 　SILVA S V , BAMPI S. Area and throughput t rade2 off s in the design of pipelined discrete wavelet t rans2 form architectures [ C] / / IEEE Conf and Exhib Au2 tomation and Test . Kyoto , Japan. 2005 , 3 : 32237. [6 ] 　ANDRA K , CHA KRABARTI C , ACHAR YA T. A VL SI architecture for lif ting2based forward and in2 verse wavelet t ransform [ J ] . IEEE Trans Signal Process , 2002 , 50 (4) : 9662977. [ 7 ] 　YAMAUCHI H , O KADA S , TA KETA K , et al. Im2 age processor capable of block2noise2f ree J PEG2000 compression with 30 f rame/ s for digital cameral appli2 cations [ C] / / IEEE Int Conf Sol Sta Circ. San Fran2 cisco , CA , USA. 2003 , 1 : 46247. [8 ] 　MEN G H , WAN G Z. Fast spatial combinative lif ting algorithm of wavelet t ransform using the 9/ 7 filter forimage block compression [J ] . Elec Lett , 2000 , 36 (21) : 176621767. [9 ] 　KHANFIR S , J EMN I M. Reconfigurable hardware implementations for lif ting2based DWT image process2 ing algorithms [ C] / / IEEE Int Conf Embedded Soft2 ware and Systems. Sichuan , China. 2008 : 2832290. [ 10 ] 　PARHI K K. VL SI digital signal processing sys2 tems : design and implementation [ M ]. New York : Wiley , 1999 : 5082510. [11 ] 　XION G C Y , TIAN J W. Efficient high speed/ low pow line2based architecture for two2dimensional dis2 crete wavelet t ransform using lif ting scheme [ J ] . IEEE Trans Circ and Syst for Video Technology , 2006 , 16 (2) : 3092312. [12 ] 　CHA KRABARTI C , V ISHWANA T H M , OWENS R M. Architectures for wavelet t ransforms : a sur2 vey [ J ] . J VL SI Signal Process , 1996 , 14 ( 44) : 1712192. [13 ] 　WEEK M , BA YOUMIM B. Discrete wavelet t rans2 form : architectures , design , and performance issues [J ] . J VL SI Signal Process , 2003 , 35 (2) : 1552178. 作者简介 : 王 　巍 (1967 —) ,男 (汉族) ,四川人 , 博士 ,教授 ,主要从事射频微波电路方向的 研究。 杜治芸 (1986 —) ,女 (汉族) ,湖北人 , 硕士研究生 ,主要从事数字信号处理 FP2 GA 实现的研究。 (上接第 851 页) 型。通过与 Medici 软件模拟结果的比较 ,验证了该 解析模型的准确性 ;通过与 B. J . Baliga 模型计算结 果的比较 ,显示了本模型的精确性、可行性。根据本 文提出的解析模型 ,设计者可以初步确定浮置场限 环注入窗口大小及与主结的间距等关键参数。 参 考 文 献 : [1 ] 　BAL IGA B J . Closed2form analytical solutions for the breakdown voltage of planar junctions terminated with a single floating field ring [J ] . Solid2State Elect ronics , 1990 , 33 (5) : 4852488. [2 ] 　BAL IGA B J . Power semiconductor devices [ M]. USA : PWS Pub. Co , 1996. [3 ] 　BOISSON V , L E H ELL EY M , CHAN TE J P. Ana2 lytical expression for the potential of guard rings of di2 odes operating in the punch2through mode [J ] . IEEE Trans Elec Dev , 1985 , 32 (4) : 8382840. [4 ] 　BREIGER K. P , GERLACH W , PEL KA J . Blocking capability of planar devices with field limiting rings [J ] . Solid2State Elect ronics , 1983 , 26 (8) : 7392745. [5 ] 　SU H KA2D , HON G S2W , L EE K , et al. An analysis for the potential of floating guard rings [ J ] . Solid2 State Elect ronics , 1990 , 33 (9) : 112521129. [ 6 ] 　BA E D2G , ChUN G S2K. An analytical model of planar junctions with multiple floating field limiting rings [J ] . Solid2State Elect ronics , 1998 , 42 (3) : 3492355. [ 7 ] 　H E J , HUN G R , ZHAN G X , et al. Analytical model of three2dimensional effect on voltage and edge peak field dist ributions and optimal space for planar junction with a single field limiting ring [J ] . Solid2State Elec2 t ronics , 2001 , 45 (1) : 79285. [8 ] 　何进 , 张兴. 场限环结构电压和边界峰值电场分布及 环间距优化 [J ] . 固体电子学研究与进展 , 2003 , 23 (2) : 1642169. 作者简介 : 孙伟锋 (1977 —) ,男 (汉族) ,江苏武进 人 ,博士 ,副教授 ,硕士生导师 ,获得江苏省 科技进步一等奖 1 项 ,已发表论文 40 余 篇 ,获得中国专利 21 项 ,现主要从事数模 混合电路、功率器件与功率集成电路、高压 射频器件等方向的研究。 658