摘要：SPIHT图像压缩方案是一种实用高性能图像压缩编码算法，但算法中使用的三个链表使其很难在FPGA中高速实现。而无链表SPIHT是对原SPIHT算法的改进，无链表SPIHT图像压缩算法使用标志位来取代链表，严格执行宽度优先的搜索策略，因此压缩性能比深度优先的搜索策略要好且能在FPGA中高速实现。为此，本文在深入研究无链表SPIHT图像压缩算法的基础上，设计了算法的FPGA实现结构。实验结果表明，该FPGA实现方案可以应用到高速实时图像压缩系统中。
关键词：无链表 SPIHT 图像压缩 FPGA
1 引言
基于变换的图像压缩方法当前应用最为广泛。小波变换以其优秀的能量集中能力而被JPEG2000标准所采用。而当前诸如countourlet、directionlets等具有多方向性的变换[1]由于具有非常高的非线性逼近能力很可能使图像压缩性能得到较大提高。然而非线性逼近能力强并不能直接使图像压缩性能得以提高，因为重要系数的位置还需要进行有效的熵编码[2]。SPIHT和EBCOT是熵编码器中最具代表性的编码方案。它们都具有编码效率高，生成的码流具有嵌入式的特点。
EBCOT是JPEG200中的核心编码器。它采用的是块编码技术，根据信源的特性对信源进行分类，然后进行MQ算术编码[5]，利用压缩后率失真优化(PCRD)策略产生嵌入式码流。SPIHT则是基于子带之间的自相似的特点通过零树结构进行重要性信息的编码。算法对集合进行重要性测试并按照一定的规则分裂．如果集合中所有元素的幅值小于某阈值(即该集合是不重要的)，则使用一个比特即可表示，这样就大大简化了集合的表示．由于变换系数在空间定位树结构中的相似性，使这种算法具有极高的效率，即使不使用算术编码也能达到较高的压缩效率。SPIHT与EBCOT相比，虽然没有EBCOT码流极其灵活的特点，但由于算法复杂度相对较低并且可以省去自适应算术编码过程，适用于对编码实时性要求较高的场合．因此研究SPIHT算法的FPGA实现具有重要意义。
但是，原始的SPIHT算法是通过3个有序的链表存储重要性信息实现对图像的编码．链表操作包括动态分配链表、添加和删除结点等，这非常不适于FPGA的有效实现。F. W. Wheeler和W. A. Pearlman随后提出了无链表SPIHT，并称之为NLS[3]。NLS则可以用FPGA加以实现。本文在深入研究无链表SPIHT图像压缩算法的基础上，设计了该算法的FPGA实现结构。
2 无链表SPIHT图像压缩算法
为了使SPIHT算法适应硬件的实现，无链表SPIHT算法对原算法进行了一些改进。在改进算法中采用了宽度优先的搜索策略。这是由于相对应深度优先的搜索策略，宽度优先的搜索策略会使重要系数更可能先被扫描到，从而能够提高压缩性能。
在无链表SPIHT算法中，采用特定的标志符来代替原SPIHT算法中的链表。当新的不重要集合生成时，这些稀疏的标志符就会被相应更新。通过稀疏的标志符标识，图像中的大部分不重要块被跳过，从而使编码时间大大减少。为了能够高效实现图像中不重要块被跳过，无链表SPIHT算法采用一维线性索引的寻址方式代替二维的寻址方式。
图1 线性索引示例，两级小波变换
对于无链表SPIHT算法，集合结构、分割规则和SPIHT相同。每个位平面有三个过程，不重要系数过程、重要集合过程、精细化过程。在编码过程中为了避免重复扫描系数，使用最大值表存储器来解决这个问题。在开始编码前，首先要计算出两个后代集合的最大值表。这两个最大值表分别存储后代集合最大值（记为DMax）和除了儿子外的后代集合最大值（记为GMax）。这两个最大值表可由下面两个公式求出。在求的过程中，按照从后向前的顺序扫描系数。其中在求DMax时，当GMax超出图像边界后应把它算作零。最大值函数max实际上可以用按位或运算来代替，这也非常利于硬件实现。
当完成最大值表求取完成后，接着对标志符存储器进行初始化。最后就可以进行正式编码了。编码的算法主流程请参考[3]。
3 FPGA算法实现结构
根据无链表SPIHT算法，设计了具体的FPGA实现结构。图2所示为系统的总体框图。整个系统以NLS Encoder为中心实现对小波系数的扫描编码。Coefficients存储了经过小波变换后的系数，而且按照线性索引的顺序已排列好。DMax用于存储所有结点的后代最大系数。GMax用于存储所有结点的除了儿子外的所有后代的最大系数。Marker存储了各个系数的当前状态标志，且在编码过程中相应的更新。
图2无链表SPIHT算法FPGA实现总体框图
算法实现中，使用一个有限状态机实现对编码过程的有效控制。图3所示为NLS编码器状态机的状态转换图。系统复位后进入Idle状态，当start信号有效后开始对图像系数进行编码处理进入Initial状态。在Initial状态里对标志符存储器进行初始化设置，设置完成后进入GetMax状态。在GetMax状态里对图像系数进行扫描，求出DMax和GMax并把他们存储到对应的存储器里，全部求完后进入SortingPixel状态。在SortingPixel状态里，完成对不重要系数的扫描编码并把编码结果输出，扫描完成后进入SortingSet状态。在SortingSet状态里，对不重要集合进行扫描测试，按照算法的规则输出相应的编码，完成相应扫描后，进入Refinement状态。在Refinement状态里对重要系数进行精细化过程，完成相应扫描后进入NextBitPlane状态。在NextBitPlane里把位平面测试变量切换到下一个位平面，并回到SortingPixel状态。其中在SortingPixel、SortingSet和Refinement状态里，都要判断输出的压缩码流是否达到了目标码率，如果达到则都直接返回到Idle状态，完成这幅图像的压缩编码，等待下一幅图像压缩的开始。
图3 NLS编码器状态机状态转换图
4 实验结果
为了验证该算法FPGA实现的正确性和高效性，采用了Altera公司的FPGA开发板。板上FPGA为Stratix II 系列，具体型号为EP2S60F672C5。首先，使用MATLAB对图像进行小波变换，然后把经过小波变换的系数以存储器初始化文件（*.mif格式）存储到Coefficients存储器中[4]。系统工作后，通过按键产生start信号启动一次压缩过程。为了观察压缩结果，把压缩后的码流仍然存储到片内存储器中，且把该存储器中的“Allow In-System Memory Content Editor to capture and update content independently of the system clock”选项设置为有效。那么当压缩完成后，就可以通过JTAG下载电缆，把该存储器的数据通过Quartus II 软件的In-System Memory Content Editor功能读回到计算机，并同样可以存储为*.mif格式文件。这样利用MATLAB读取该*.mif格式文件，进行解码操作，并进行小波逆变换，即可恢复解压缩的图像。
使用FPGA实现该算法时，完全使用FPGA片内存储器。对于256x256大小的图像，表1列出了FPGA片内存储器的使用情况，总计需要200K字节的存储器即可。如果把图像的压缩比设为8:1，则压缩码流存储器需要的存储容量为8K字节。
表1 FPGA片内存储器使用情况
模块
位宽
容量(字节)
Coefficients
16
128K
DMax
16
32K
GMax
16
8K
Marker
4
32K
总计
200K
5 结论
SPIHT算法是公认的高性能的图像压缩算法。为了能采用FPGA进行有效的高速实现，本文深入分析了其改进算法：无链表SPIHT算法（NLS）。由于无链表SPIHT算法采用状态标示符取代动态链表操作来记录集合分割信息，进而把整个编码过程都简化为简单的逻辑运算。在此基础上设计了NLS编码器的FPGA实现的高速高效硬件结构。并在Altera公司的FPGA上进行了实际验证。实验表明，该FPGA实现方案可以应用到高速实时图像压缩系统中。
本文作者创新点：使用FPGA实现了无链表SPIHT算法，该方案可以应用到高速实时图像压缩系统中。
参考文献
[1] 焦李成，谭山. 图像的多尺度几何分析：回顾和展望[J]. 电子学报. 2003, 12(A):1975-1981
[2] A. Cohen, I. Daubechies, O. Guleryuz, and M. Orchard, “On the Importance of Combining Wavelet-Based Non-linear Approximation with Coding Strategies,” in IEEE trans. information theory, vol. 48, no. 7, pp. 1895-1921
[3] F. W. Wheeler and W. A. Pearlman “SPIHT image compression without lists,” in Proc. of the International Conf. on [A]．Acoustics, Speech, and Signal Processing, pp. 2047-2050, June 2000.
[4] 余汉成，王成华，夏永君. 一种改进的无表SPIHT算法[J]. 数据采集与处理. 2005, 12. 第20卷第4期:444-448
[5] 王镇道，章兢，曾云，等. 一种高速JPEG2000 MQ编码器的VLSI实现[J] . 微计算机信息. 2006，9-3：213-233
(全文结束)
