1、导言
依据改换的图画紧缩办法当时运用最为广泛。小波改换以其优异的能量会集才能而被JPEG2000规范所选用。而当时比如countourlet、directionlets等具有多方向性的改换因为具有十分高的非线性迫临才能很或许使图画紧缩功能得到较大进步。可是非线性迫临才能强并不能直接使图画紧缩功能得以进步，因为重要系数的方位还需求进行有用的熵编码。SPIHT和EBCOT是熵编码器中最具代表性的编码计划。它们都具有编码功率高，生成的码流具有嵌入式的特色。
EBCOT是JPEG200中的中心编码器。它选用的是块编码技能，依据信源的特性对信源进行分类，然后进行MQ算术编码，运用紧缩后率失真优化（PCRD）战略发生嵌入式码流。SPIHT则是依据子带之间的自相似的特色经过零树结构进行重要性信息的编码。算法对调集进行重要性测验并依照必定的规矩割裂．假如调集中一切元素的幅值小于某阈值（即该调集是不重要的），则运用一个比特即可标明，这样就大大简化了调集的标明．因为改换系数在空间定位树结构中的相似性，使这种算法具有极高的功率，即便不运用算术编码也能到达较高的紧缩功率。SPIHT与EBCOT比较，尽管没有EBCOT码流极端灵敏的特色，但因为算法复杂度相对较低并且能够省去自习惯算术编码进程，适用于对编码实时性要求较高的场合．因而研讨SPIHT算法的FPGA完结具有重要意义。
可是，原始的SPIHT算法是经过3个有序的链表存储重要性信息完结对图画的编码．链表操作包含动态分配链表、增加和删去结点等，这十分不适于FPGA的有用完结。F. W. Wheeler和W. A. Pearlman随后提出了无链表SPIHT，并称之为NLS。NLS则能够用FPGA加以完结。本文在深入研讨无链表SPIHT图画紧缩算法的基础上，规划了该算法的FPGA完结结构。
2、无链表SPIHT图画紧缩算法
为了使SPIHT算法习惯硬件的完结，无链表SPIHT算法对原算法进行了一些改善。在改善算法中选用了宽度优先的查找战略。这是因为相对应深度优先的查找战略，宽度优先的查找战略会使重要系数更或许先被扫描到，然后能够进步紧缩功能。
在无链表SPIHT算法中，选用特定的标志符来替代原SPIHT算法中的链表。当新的不重要调集生成时，这些稀少的标志符就会被相应更新。经过稀少的标志符标识，图画中的大部分不重要块被越过，然后使编码时刻大大削减。为了能够高效完结图画中不重要块被越过，无链表SPIHT算法选用一维线性索引的寻址方法替代二维的寻址方法。
关于无链表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片内存储器。关于256×256巨细的图画，表1列出了FPGA片内存储器的运用情况，总计需求200K字节的存储器即可。假如把图画的紧缩比设为8:1，则紧缩码流存储器需求的存储容量为8K字节。
表1 FPGA片内存储器运用情况
5、定论
SPIHT算法是公认的高功能的图画紧缩算法。为了能选用FPGA进行有用的高速完结，本文深入分析了其改善算法：无链表SPIHT算法（NLS）。因为无链表SPIHT算法选用状况标明符替代动态链表操作来记载调集切割信息，进而把整个编码进程都简化为简略的逻辑运算。在此基础上规划了NLS编码器的FPGA完结的高速高效硬件结构。并在Altera公司的FPGA进步行了实践验证。试验标明，该FPGA完结计划能够运用到高速实时图画紧缩体系中。
本文作者立异点：运用FPGA完结了无链表SPIHT算法，该计划能够运用到高速实时图画紧缩体系中。
责任编辑：gt
