基于频率分级的指纹图像压缩摘要：指纹图像是由黑白相间的脊线、谷线排列在一起而构成的特殊灰度图像，反复出现的反差边缘、周围的背景区域使得指纹图像具备低、中、高三种不同的频率成分，本文利用小波包变换和频谱分析提出了一种基于频率分级的指纹图像压缩算法，对包含能量最多的低频子图像，采用无损差分脉冲编码(DPCM)算法：对包含能量较少的中频子图像，采用嵌入式小波零数编码（EZW)算法；对包含能量最少的高频子图像，采用集合分裂嵌入块编码(SPECK)算法。关键词：频率分级；DPCM；EZW；SPECK；指纹图像压缩Fingerprint Image Compression Based on GradedFrequencyAbstract: Fingerprint image is a special kind of gray image which consists with ridgeand valley lines in black and white.The fingerprint image has different frequencycomponent, low, medium and high frequency. The fingerprint image compressionalgorithm based on graded frequency is proposed. The low frequency sub-image,which contains the most energy, is encoded by lossless Differential Pulse CodeModulation (DPCM). The medium frequency sub-image, which contains less energy,is encoded by Embedded Zero-tree Wavelet (EZW).The high frequency sub-image,which contains the least energy, is encoded by Set Partitioning Embedded BlockCoder(SPECK)Key words:graded frequency,DPCM;EZW; SPECK;fingerprint imagecompression0引言目前，为减少存储空间和提高传输效率的高压缩比图像压缩算法有很多，如小波图像压缩、分形图像压缩、矢量量化、基于神经网络的压缩方法、基于形态学方法的图像压缩算法等。指纹图像由于有其固有的特点，这使得指纹图像压缩与一般的图像压缩既有相同的地方又有其本身的特性。不同之处就是指纹图像通常由交替出现的宽度大致相同的脊和谷组成，同性均匀区域、纹理区域以及剧烈变化的边缘和视觉上可以感知的边界使得其具有低、中、高三种不同的频率成分，小波变换的多分辨率分析仅将图像的低频部分逐级进行分解，而对高频部分不再继续分解，从而不能很好的表示包含大量细节信息的信号。针对普通小波分解的这一大缺陷，R.Coifman，R.Meyer，S.Quake及V.Wickerhauser等人在小波分析的基础上提出了小波包的概念[1-2]，小波包变换将多分辨分析没有细分的高频部分进一步分解，实现在高频段的更窄频带内观测局部信号，本文基于指纹图像不同的频率特点结合小波包变换和频谱分析进行分级，分别采用不同的压缩算法，力求在保证重建质量的前提下尽可能提高压缩率
基于频率分级的指纹图像压缩 摘 要：指纹图像是由黑白相间的脊线、谷线排列在一起而构成的特殊灰度图像， 反复出现的反差边缘、周围的背景区域使得指纹图像具备低、中、高三种不同的 频率成分，本文利用小波包变换和频谱分析提出了一种基于频率分级的指纹图像 压缩算法，对包含能量最多的低频子图像，采用无损差分脉冲编码(DPCM)算法； 对包含能量较少的中频子图像，采用嵌入式小波零数编码(EZW)算法；对包含能 量最少的高频子图像，采用集合分裂嵌入块编码(SPECK)算法。 关键词：频率分级；DPCM；EZW; SPECK; 指纹图像压缩 Fingerprint Image Compression Based on Graded Frequency Abstract: Fingerprint image is a special kind of gray image which consists with ridge and valley lines in black and white. The fingerprint image has different frequency component, low, medium and high frequency. The fingerprint image compression algorithm based on graded frequency is proposed. The low frequency sub-image, which contains the most energy, is encoded by lossless Differential Pulse Code Modulation (DPCM). The medium frequency sub-image, which contains less energy, is encoded by Embedded Zero-tree Wavelet (EZW). The high frequency sub-image, which contains the least energy, is encoded by Set Partitioning Embedded Block Coder (SPECK). Key words: graded frequency; DPCM; EZW; SPECK; fingerprint image compression 0 引 言 目前，为减少存储空间和提高传输效率的高压缩比图像压缩算法有很多，如 小波图像压缩、分形图像压缩、矢量量化、基于神经网络的压缩方法、基于形态 学方法的图像压缩算法等。指纹图像由于有其固有的特点，这使得指纹图像压缩 与一般的图像压缩既有相同的地方又有其本身的特性。不同之处就是指纹图像通 常由交替出现的宽度大致相同的脊和谷组成，同性均匀区域、纹理区域以及剧烈 变化的边缘和视觉上可以感知的边界使得其具有低、中、高三种不同的频率成分， 小波变换的多分辨率分析仅将图像的低频部分逐级进行分解，而对高频部分不再 继续分解，从而不能很好的表示包含大量细节信息的信号。针对普通小波分解的 这一大缺陷，R.Coifman，R.Meyer，S.Quake 及V.Wickerhauser等人在小波分析 的基础上提出了小波包的概念[1-2]，小波包变换将多分辨分析没有细分的高频部 分进一步分解，实现在高频段的更窄频带内观测局部信号，本文基于指纹图像不 同的频率特点结合小波包变换和频谱分析进行分级，分别采用不同的压缩算法， 力求在保证重建质量的前提下尽可能提高压缩率
1指纹图像频谱分析指纹图像是由基本等宽的具有一定方向性的谷和脊组成，反复出现的反差边缘、周围背景区域使得灰度指纹图像具备低、中、高三种不同的频率成分，如果在算法中针对不同的频率成分采用不同的编码，则压缩比和算法速度均可得到提高，因此本文提出了分级图像压缩算法。指纹图像经小波包分解后各子带对应的频率为{[0，f,/4'"]；[,/4'"，2f,/4′]；[2f,/4′，3f,/4/]；...；[(4/-1)f,/4′，f,J(f，为原图像的频率，为分解层数)，选取频带范围0~f,/10为低频带，频带范围f,/10~7f,/10为中频带，频带范围7f,/10~f为高频带，图1为各频带图像频谱图[3]。2002.000400060008.00010.000(a) The low frequency sub-imageAeiwnidaa2.0004.00010.00060008000(b) The medium frequency sub-image0.520004.00060008.00010000(c) The high frequency sub-image图1指纹图像各频带频谱图2基于频率分级的灰度指纹图像压缩算法2.1小波包分解层数的确定二维小波包变换是将原始图像分解成一个低频子图像和三个方向的高频子图像，即每一层分解为四个子带，故总的子带数为4，其中为分解层数，究竟分多少层不仅和图像的复杂程度以及小波滤波器长度有关，更重要的是要满足子带信息量熵值原理，要求分成的四个子带的熵值和应该小于分解前子带的熵值
1 指纹图像频谱分析 指纹图像是由基本等宽的具有一定方向性的谷和脊组成，反复出现的反差边 缘、周围背景区域使得灰度指纹图像具备低、中、高三种不同的频率成分，如果 在算法中针对不同的频率成分采用不同的编码，则压缩比和算法速度均可得到提 高，因此本文提出了分级图像压缩算法。指纹图像经小波包分解后各子带对应的 频率为{[0， j s f / 4 ]；[ j s f / 4 ， j s 2 f / 4 ]；[ j s 2 f / 4 ， j s 3 f / 4 ]；.；[ j s j (4 −1) f / 4 ， s f ]}( s f 为原图像的频率，j 为分解层数)，选取频带范围0~ fs /10为低频带，频 带范围 fs /10~ 7 fs /10 为中频带，频带范围7 fs /10 ~ s f 为高频带，图1 为各频带 图像频谱图[3]。 图1 指纹图像各频带频谱图 2 基于频率分级的灰度指纹图像压缩算法 2.1 小波包分解层数的确定 二维小波包变换是将原始图像分解成一个低频子图像和三个方向的高频子 图像，即每一层分解为四个子带，故总的子带数为 j 4 ，其中j 为分解层数，究竟 分多少层不仅和图像的复杂程度以及小波滤波器长度有关，更重要的是要满足子 带信息量熵值原理，要求分成的四个子带的熵值和应该小于分解前子带的熵值
（平均比特数），分解才有意义。在实际应用中，确定小波包分解的层数要兼顾不同方面的影响。图2为小波包分解层数对编码性能的影响，由图2可知，三层以上分解的压缩比提高的非常缓慢，焰值趋于平稳，考虑到算法复杂度及硬件实现难度，分解层数确认为三层，即j-3。288元2624uouue222041816012430312LevelLevel(a) The entropycharacter figure(b)Thecompressionratiocharacterfigure25100020800Jo rarars1560010400200420012340234LevelLevel(c)The running time character figure(d)Thesub-band numbercharacterfigure图2小波包分解层数对编码性能的影响2.2低频子带的编码低频子图像主要包含的是指纹图像平坦区域的信息，该分量的每个系数都很大且数值很接近，所占的能量最多，对该频率的各子带相应的系数进行比较取平均值，作为低频子带融合后的低频系数：(1)Fr(x,y)=ZCrxD(x,y)其中：C,=1/k，C,表示各子带的加权系数，K表示低频子带的数目，D(x,y)表示第k个子带系数，F（x,y)表示融合后的子带系数。考虑到低频成分相邻像素之间的差异性较小，而差分脉冲编码(DPCM)算法主要针对的就是相关性比较大，像素值变化范围较小的图像，非常适合用于指纹图像的低频子图像压缩编码，其思想是根据实际值与预测值之差进行量化编码
(平均比特数)，分解才有意义。 在实际应用中，确定小波包分解的层数要兼顾不同方面的影响。图2 为小波 包分解层数对编码性能的影响，由图2可知，三层以上分解的压缩比提高的非常 缓慢，熵值趋于平稳，考虑到算法复杂度及硬件实现难度，分解层数确认为三层， 即j=3。 图 2 小波包分解层数对编码性能的影响 2.2 低频子带的编码 低频子图像主要包含的是指纹图像平坦区域的信息，该分量的每个系数都很 大且数值很接近，所占的能量最多，对该频率的各子带相应的系数进行比较取平 均值，作为低频子带融合后的低频系数： = ∑ × K k k k k F (x, y) C D (x, y) （1） 其中：C k k = 1/ ，Ck 表示各子带的加权系数，K 表示低频子带的数目，D (x, y) k 表示第k 个子带系数， F (x, y) k 表示融合后的子带系数。 考虑到低频成分相邻像素之间的差异性较小，而差分脉冲编码(DPCM)算法 主要针对的就是相关性比较大，像素值变化范围较小的图像，非常适合用于指纹 图像的低频子图像压缩编码，其思想是根据实际值与预测值之差进行量化编码
从而降低计算量和存储的数据量，本文所采用的预测模型为：已知该子图像的像素个数为mxn，保留第一个像素值不变，其他像素值X(i,j)可预测为+-X(i-1, j+1)X(i-1,J)+X(i-1,j-1)+=X(i,j-1)+(2)X(i,j)=24″68式中：X(i,j)为当前所要预测的像素值，=1，2，…，m；j-1，2，，n。用当前值直接减去预测值即：X(i, j)'= X(i, j)-int[_X(i,j-1)+-X(i-1, j)+X(i-1, j-1)+ -X(i-1,j+D))1(3)82X8再对差值X(i,j)进行编码、存储和传输。同时考虑到指纹图像脊和谷像素微小的变化，并不改变人类视觉的判断，因此可以进一步忽略在不改变人类视觉效果下的差值而提高压缩比。2.3中频子带的编码采用基于区域的最大值法得到包含能量较少的中频子图像，该子带含有图像缓慢变化的非常重要的纹理信息，故小波系数大多不为零。考虑每个系数和周围相关系数，融合子带的每个系数处于考察区域的中心，将各个中频子带的参考区域内各个系数的绝对值进行求和，比较各个中频子带对应区域的和，并选取和最大的区域中的系数值作为融合后的中频系数。采用嵌入式零树编码(EZW)算法，该算法采用零树结构，充分利用不同尺度间的相关性，从而更有效的组织细尺度的小波重要系数优先被编码，可根据目标码率或失真度要求随时结束编码而很好的保护图像的纹理信息，非常适合用于指纹图像的中频子图像压缩编码。EZW算法实现步骤4如下：步骤1：选择阈值。应用一系列阈值T，T,，，TL--来确定变换后图像系数的重要性(其中T,=T-,/2，为扫描次数，i=0，1，2，….，L-1)，初始阈值T。=2 loe:(mx(ks/)」(其中，(c,)是L 变换的系数，L]为不小于该数的最大整数)。步骤2：主扫描。按Z形扫描顺序，将图像变换系数与阈值T-进行比较，系数幅值ci>T-标记为正重要系数(P)；系数幅值-C,>T-标记为负重要系数(N)；系数幅值ci<T-1，且存在子孙后代，其子孙后代也为不重要系数，就标记为零树根(T)；系数幅值ci,<T-，且存在子孙后代，其子孙后代存在重要系数，就标记为孤立零点(Z)。步骤3：辅扫描。对主扫描表进行顺序扫描，对其中输出符号为P或N的系数按其绝对值是否超过阈值的1.5倍附加一个比特1或0来描述其精度来进
从而降低计算量和存储的数据量，本文所采用的预测模型为：已知该子图像的像 素个数为m× n ，保留第一个像素值不变，其他像素值 X (i, j)可预测为 ( 1, 1) 8 1 ( 1, 1) 8 1 ( 1, ) 4 1 ( , 1) 2 1 X (i, j) = X i j − + X i − j + X i − j − + X i − j + （2） 式中： X (i, j)为当前所要预测的像素值，i=1，2，.，m；j=1，2，.，n。用当 前值直接减去预测值即： ( 1, 1)] 8 1 ( 1, 1) 8 1 ( 1, ) 4 1 ( , 1) 2 1 X (i, j)′ = X (i, j) − int[ X i j − + X i − j + X i − j − + X i − j + （3） 再对差值 X (i, j)进行编码、存储和传输。同时考虑到指纹图像脊和谷像素微 小的变化，并不改变人类视觉的判断，因此可以进一步忽略在不改变人类视觉效 果下的差值而提高压缩比。 2.3 中频子带的编码 采用基于区域的最大值法得到包含能量较少的中频子图像，该子带含有图像 缓慢变化的非常重要的纹理信息，故小波系数大多不为零。考虑每个系数和周围 相关系数，融合子带的每个系数处于考察区域的中心，将各个中频子带的参考区 域内各个系数的绝对值进行求和，比较各个中频子带对应区域的和，并选取和最 大的区域中的系数值作为融合后的中频系数。采用嵌入式零树编码(EZW)算法， 该算法采用零树结构，充分利用不同尺度间的相关性，从而更有效的组织细尺度 的小波重要系数优先被编码，可根据目标码率或失真度要求随时结束编码而很好 的保护图像的纹理信息，非常适合用于指纹图像的中频子图像压缩编码。EZW 算法实现步骤[4] 如下： 步骤 1：选择阈值。应用一系列阈值T0 ，T1，.，TL−1 来确定变换后图像 系数的重要性(其中Ti = Ti−1 / 2，i为扫描次数，i=0，1，2，.，L-1)，初始阈值 log (max{ }) 0 2 , 2 i j c T = (其中，{ } i, j c 是L 变换的系数， 为不小于该数的最大 整数)。 步骤 2：主扫描。按Z 形扫描顺序，将图像变换系数与阈值Ti−1 进行比较， 系数幅值 i, j > Ti−1 c 标记为正重要系数(P)；系数幅值− i, j > Ti−1 c 标记为负重要系数 (N)；系数幅值 i, j < Ti−1 c ，且存在子孙后代，其子孙后代也为不重要系数，就标 记为零树根(T)；系数幅值 i, j < Ti−1 c ，且存在子孙后代，其子孙后代存在重要系 数，就标记为孤立零点(Z)。 步骤 3：辅扫描。对主扫描表进行顺序扫描，对其中输出符号为P 或N 的 系数按其绝对值是否超过阈值的1.5 倍附加一个比特1 或0 来描述其精度来进
行量化。步骤4：对输出符号为P或N的数据重新排序。具体方法是将幅值在[1.5T-I，2T-]中的数据排在幅值位于[T-1，1.5T-,]中的数据之前。步骤5：输出编码。编码器输出的两类信息：一类是给解码器的信息，包括阅值、主扫描和辅扫描表；第二类是用于下次扫描的信息，保留的阅值及重新排序过的重要系数列。2.4高频子带的编码包含能量最少的高频子图像包含了图像剧烈变化的水平方向和垂直方向的边缘信息，小波系数大多为零，根据不同区域特征选择方法以及对应图像小波包系数的多窗口区域方差，来确定融合后高频小波包系数：将小波包变换后的高频子带分成一系列小区域，通过滑动领域操作分别计算各个小块的方差，作为融合的依据，不同尺度、不同分辨率的高频子带一般分为水平方向、垂直方向、对角线方向，代表水平方向边缘区域子窗口的小波包系数的方差大于整个区域窗口的小波包系数的方差，代表垂直区域子窗口的小波包系数的方差应当大于整个区域窗口的小波包系数的方差，代表对角线区域子窗口的小波包系数的方差大于整个区域窗口的小波包系数的方差，对各个高频子带不同边缘特性的系数进行融合确定高频子带。采用集合分裂嵌入块编码(SPECK)方法，该算法利用了同一子带中不重要系数的相关性，采用把所有的子带分裂的S集合的方式来有效的组织小波系数[5-6]，这样就能充分利用小波子带能量集中的特性，可以保证具有高信息量的小波系数能首先被编码，提高编码效率，结合人的视觉频率特性而保留图像重要的边缘位置信息，非常适合用于指纹图像的高频子图像压缩编码。SPECK算法主要步骤如下：步骤1：阈值和有序表的初始化。设置阈值T=2"，其中log2(maxlc,b)]将表LSP置空，表LIS用最低频子带初始化，初始化集合X由各子带构成，集合S由最低频子带初始化，剩余集合I=X-S。步骤2：排序。从最低频块开始，按Z字形扫描各子块，对子块进行重要性测试，即：[1 maxc,β≥2S,(T)=(4)[oother如果S,(T)=0，表示块T是不重要的，用一个符号表示；如果S,(T)=1，表示块T是重要的，则采用四叉树分裂的方法搜索重要系数；如此重复，直到找出块中所有的重要系数，并把它移入LSP表中，以进行进一步的量化。步骤3：细化。对于LSP中的每一个表项(i,j)，输出ci第n位比特值。步骤4：量化值更新。如果n=0则终止：否则将n减1，设定新阈值T=2"-，转至步骤2。综上所述，基于频率分级的灰度指纹图像压缩算法的原理框图可表示为图3
行量化。 步骤 4：对输出符号为P 或N 的数据重新排序。具体方法是将幅值在 [ 5 1 1. Ti− ，2Ti−1 ]中的数据排在幅值位于[Ti−1， 5 1 1. Ti− ]中的数据之前。 步骤 5：输出编码。编码器输出的两类信息：一类是给解码器的信息，包括 阈值、主扫描和辅扫描表；第二类是用于下次扫描的信息，保留的阈值及重新排 序过的重要系数列。 2.4 高频子带的编码 包含能量最少的高频子图像包含了图像剧烈变化的水平方向和垂直方向的 边缘信息，小波系数大多为零，根据不同区域特征选择方法以及对应图像小波包 系数的多窗口区域方差，来确定融合后高频小波包系数：将小波包变换后的高频 子带分成一系列小区域，通过滑动领域操作分别计算各个小块的方差，作为融合 的依据，不同尺度、不同分辨率的高频子带一般分为水平方向、垂直方向、对角 线方向，代表水平方向边缘区域子窗口的小波包系数的方差大于整个区域窗口的 小波包系数的方差，代表垂直区域子窗口的小波包系数的方差应当大于整个区域 窗口的小波包系数的方差，代表对角线区域子窗口的小波包系数的方差大于整个 区域窗口的小波包系数的方差，对各个高频子带不同边缘特性的系数进行融合确 定高频子带。采用集合分裂嵌入块编码(SPECK)方法，该算法利用了同一子带中 不重要系数的相关性，采用把所有的子带分裂的S 集合的方式来有效的组织小波 系数[5-6] ，这样就能充分利用小波子带能量集中的特性，可以保证具有高信息量 的小波系数能首先被编码，提高编码效率，结合人的视觉频率特性而保留图像重 要的边缘位置信息，非常适合用于指纹图像的高频子图像压缩编码。SPECK 算 法主要步骤如下： 步骤1：阈值和有序表的初始化。设置阈值 n T = 2 ，其中 log2 (max{ci, j })， 将表LSP置空，表LIS用最低频子带初始化，初始化集合X 由各子带构成，集合S 由最低频子带初始化，剩余集合I=X-S。 步骤 2：排序。从最低频块开始，按Z 字形扫描各子块，对子块进行重要 性测试，即： ≥ = other c S T N i j n 0 1 max{ } 2 ( ) , （4） 如果 Sn (T) = 0 ，表示块T 是不重要的，用一个符号表示；如果 Sn (T) =1， 表示块T 是重要的，则采用四叉树分裂的方法搜索重要系数；如此重复，直到找 出块中所有的重要系数，并把它移入LSP 表中，以进行进一步的量化。 步骤 3：细化。对于LSP 中的每一个表项(i, j) ，输出 i j c , 第n 位比特值。 步骤 4：量化值更新。如果n = 0 则终止；否则将n 减1，设定新阈值 1 2 − = n T ， 转至步骤2。 综上所述，基于频率分级的灰度指纹图像压缩算法的原理框图可表示为图3