基于SPIHT编码过程的图像选择加密算法

随着多媒体技术和网络通信技术的快速发展，图像数据的安全问题越来越受到人们的关注。由于图像具有数据量大、冗余度高、要求实时传输等特点，采用普通的文本加密效果不理想。图像压缩技术成熟之后出现了更加安全高效的加密方案：基于压缩编码的加密方式能够同时完成加密和压缩的功能，加密效率高、格式兼容性好；选择加密是针对多媒体信息特点的加密方案，它选取多媒体信息中的重要部分进行加密，有效地减少了加密数据量。目前，选择加密和基于压缩编码的加密技术已经成为了研究热点。

SPIHT编码作为一种优越的嵌入式小波编码，在各种图像压缩中应用广泛。它能够支持图像渐进传输、压缩效率高，比特流按照重要性排序并且能够随时结束编码，允许达到一个目标比特率或失真。该算法充分挖掘了小波图像不同子带之间的相似性，是公认的一种高效图像压缩编码，因此研究SPIHT编码并更好地利用它是非常必要的。提出了只加密SPIHT压缩编码前两层数据的灰度图像部分加密方法；基于SPIHT提出了一种彩色图像的部分加密算法，基于SPIHT提出了一种灰度图像部分加密算法。与编码过程相结合的加密方案能够在编码的同时完成加密，提高了效率，并且能够满足格式兼容性，适应网络实时传输。该算法的实质类似于将码流中的某些关键数据用随机比特替换，容易受到已知明文攻击和选择明文攻击。因此在设计此类加密算法时要考虑如何提高这方面的安全性。

本文研究了SPIHT压缩编码的4种数据类型，分析了不同类型编码数据对图像重建的作用，确定了其中的重要数据类型，并将其用流密码进行了加密。其次，改变加密层数K控制加密强度，进一步减少了加密数据量。此外，本文在对LIS扫描过程中引入了混乱机制，降低了码流相关性，从而使得算法更加安全。仿真实验结果表明，本文方法在保障了图像加密安全性的同时进一步减少了加密数据量，满足格式兼容性要求并且能够适应网络实时传输。

二、SPIHT编码原理概述

1、编码过程

SPIHT算法是一种嵌入式编码，将待编码的比特流按重要性的不同进行排序根据目标码率或失真度大小要求随时结束编码。它具有良好的渐进传输特性，利用集合划分以及有序的位平面传输，优先传输重要系数，优先传输重要系数的重要比特位，其主要步骤如下：

1)初始化：对图像进行小波分解，用固定比特位数表示变换后的系数Ci,j，输出n=|log2 (max(i,j)){|ci,i|}到信道；

2)排序过程：输出满足条件2n≤|ci,j|<2n+1的系数Ci,j的个数Z，以及对应系数的Z对坐标和Z个符号位；

3)细化过程：对于所有满足|ci,j|≥2n+1系数，输出第n位的值；

4)迭代：如需迭代，则n-1转到2）。

2、排序过程

排序过程是SPIHl编码过程中最重要的部分，它采用集合分裂过程来决定码流如何按照重要性进行排序。集合的分割过程是不断将一个集合分为4个子集，然后分别对各个子集进行重要性测试，若该集合是不重要的，则用一个符号表示，反之，则继续将集合进行分割并进行重要性测试。集合的结构如图1所示，其中：H，空间方向树的所有树根的坐标集合（最高层）；D(i,j)，结点(i，j)的所有直接后代结点的坐标集合；O(i，J)，结点(i,J)的直接后继（儿子）的坐标集合。L(i,J)=D(i,J)-O(i,J)，结点（i,j)直接后继外所有后继的坐标集合。

集合分裂规则可以简单地表示。

1)将图像初始化为单一元素集合{(i,j)}和它们的后代D(i,j)，所有的(i，j)∈H；

2)如果D(i,j)是重要的，把它分裂为L(i,j)和四个单元素集合，每个集合元素(k,j)∈O(i,j)；

3)如果三(i胡是重要的，把它分裂为四个集合D(i，j)，其中(k,j')∈O(i，J)直图像进行离散小波变换后，将小波系数根据一定规则划分为空间方向树SOT，在编码过程中需要维持三个链表，不重要系数链表LIP，不重要集合链表LIS和重要系数链表LSP，并用小波系数矩阵中LL层的小波系数初始化LIP，用所有的SOT初始化LIS，初始化LSP为空集。

SPIHT编码由扫描3个链表完成。当阈值为Tk，k∈(0，K)，时，扫描过程如下：

1)LIP扫描：将不重要系数保留在UP中，重要系数移入LSP，并输出表示系数重要性判定值Sk,LIP-sig和系数符号Sk,LIP-sig；

2)LIS扫描：扫描LIS中所有的集合D(i,j)，如果集合中不包括重要系数（即集合不重要）将其保留在LIS中；反之，则将它分裂为4个直接后代和更小的子集，将小的集合加入到LIS链尾，并判断4个直接后代系数的重要性，不重要系数放入LIP中，重要系数放入LSP。同时，输出集合重要性判定值Sk,LIP-sig、集合中重要系数判定值与符号Sk,LIP-sig、Sk,LIP-sig；

3)细化过程：输出LSP中每个系数第n（n=lgTk）个位平面的比特skq。到压缩数据中。至此一个循环扫描完成，改变阈值T= T/2进入下一次扫描。如此迭代，直到输出数据达到要求的压缩率为止。

二、基于SPIHT编码的选择加密算法

SPIHT压缩码流包含了多种类型数据，它们对于解码所起的作用也各不相同。有些重要系数对解码起着非常关键的作用，如果把这部分数据加密也许能够起到很好的保护作用。

1、SPIHT压缩码流数据分析

根据前面对编码过程的分析，SPIHT算法在编码过程中需要维持三个链表：LIP、LIS、和LSP，算法过程分为排序过程和精化过程，具体的编码过程是对上述三个链表扫描并产生比特的过程，如图2所示。

将码流分解为四个部分：系数重要性判定值pixel-sig，系数符号pixel-sgn，集合重要性判定值set-sig，细化值value。这四类数据的意义不同，对图像重构起着不同的作用，下面将结合实验对这四个部分的重要性进行分析。

采用一组随机比特分别替换这4部分码流，利用码流重构图像，分别研究各部分数据对解码的影响。图像重构情况如图3所示。

通过前面的分析和实验，我们得出：系数重要性判定值和集合重要性判定值对解码和获得重构图像具有非常显著的影响。

系数重要性判定值的改变将会直接影响后续比特的类型和意义，最终会影响解码后的重构图像。由于SPIHT的编码过程是对集合的划分过程：如果集合是重要的，则将该集合分裂成四个单独节点与剩余后代，然后继续对各个节点与集合进行判断；反之，则用一个符号对该集合进行编码。由此可见，集合重要性判定对后续节点的划分非常重要，会产生连锁反应，这部分数据能否正确解码对于图像重构至关重要。

 2、选择加密方案

1)加密重要数据

根据上节的分析可知，系数重要性判定值和集合重要性判定值在SPIHT编码中是重要值，这两类数据直接影响其他类型数据的意义。仅仅对这两部分数据进行加密就能够使得重构图像失去可读性，从而达到保密的目的和要求。此外，SPIHT编码属于嵌入式编码，按位平面从高到低进行编码，压缩码流越向前，包含的信息量越大。因此可以只加密前M次扫描码流中的重要部分，进一步减少所需加密的数据量。

2)选择加密安全性分析

基于SPIHT的选择加密算法虽然具有较高的加密效率，能满足编码格式的兼容性要求，但仍然存在缺陷。该加密算法实质上是用01比特替换部分码流数据，替换的比例越小则密文码流与明文码流的相关度越高。码流的相关性比较大，可能会给攻击者提供一些重要的分析信息，攻击者可能会采用一些图像处理方法基于图像相关性进行恢复，存在不安全隐患。因此，需要增强码流的混乱程度来克服这个缺点。

3)引入置乱机制

原始图像经小波变换后得到系数矩阵，系数可看成一棵四叉树。如果在编码前直接对四叉树结构进行整体置乱的话会改变多分辨率小波系数的特性，会对压缩性能造成很大的影响。因此，最佳的方法是在压缩过程中引入混乱。

SPIHT编码过程中会将重要集合进行进一步分解，并将后代中的四个集合加入LIS以便于继续扫描判断。因此LIS中的数据不断增长，并决定了对后续节点的扫描顺序。若LIS的元素代表D(i,j)则定义为A类，若代表L(i，j)则定义为B类，并且同一类型的节点在四叉树中的高度是一致的。因此本文提出了置乱方案：对LIS中相同类型的节点进行置乱，这样等价于将重要四又树中同一高度的节点进行置乱。与整体之乱相比，这种方案不仅能够与压缩过程相结合，更重要的是能减少对系数分布的影响，依旧能够满足渐进传输的要求。

4)选择加密方案设计

采用RC4算法生成的密钥序列为K；加密前m次扫描码流中的系数重要性判定值和集合重要性判定值。在对LIS的扫描过程中，若当前节点为A类并且下一个节点为B类，统计当前节点之后有几个连续的B类节点并对它们进行置乱；若当前节点为B类并且下一个节点为A类，统计当前节点之后有几个连续的A类节点并对它们进行置乱。其中，置乱的方式借鉴RC4的算法原理。假设需要置乱的序列为S[n]，密钥长度为n，算法过程为：

for ('i=O;i<n；i++)

{

s[i]=i；

}

for (i=0；i<n；i++)

{

j=(j+s[i]+k[i])%256；

swap( s[i]，s[j])；

}

在算法的过程中，密钥的主要功能是将S[n]搅乱，i确保S[n]的每个元素都得到处理，j保证S[n]的搅乱是随机的。

三、实验结果与性能分析

本算法基于VS2008平台采用MFC编程进行数据仿真实验，选用RC4算法生成加密密钥，实验参数设置为：8位密钥12345678，小波分解级数为4，比特率为1.0。本文对uscSIPI标准测试图库中的灰度图像进行了仿真实验，对前6次扫描产生码流中的重要部分进行加密，并置乱LIS中的同类集合，当码流长度为65 536 bit时结束编码。

1、实验结果

加解密图像如图5所示。从图中可以看出图像加密后失去了原始明文的信息，密文直方图分布均匀，能够有效地抵抗统计分析。

2、性能分析

（1）安全性分析

SPIHT算法中要精准地确定数据类型非常困难，如果加密的数据量非常庞大，更是难上加难。如果一副256*256大小的图像有5%的数据被加密，约有3276比特的数据被加密。穷举攻击的计算量为23276，可以保证数据的安全性。

（2）密钥敏感性分析

对于一个优秀的加密系统而言，明文应具备密钥敏感性。即使密钥发生微小的改变也会使得密文千差万别。在对lena的密文图像进行解密时，将原始密钥由12345678改为12345679，其余参数不变，对应的解密结果如图6所示。解密图像呈现随机分布，其直方图很均匀。

为了进一步验证密钥敏感性，我们随机生成3 000个密钥（只有其中一个是正确的）分别对密文图像进行解密并计算重构图像与原始图像的PSNR，结果如图7所示。从图中可以看出，只有用正确的密钥解密才能得到理想的PSNR(约为35.94 dB)，其余的均为10dB左右。即使加密密钥和解密密钥有微小的差别也不能正确解密，说明该算法能够抵抗各种基于密钥敏感性的攻击。

（3）格式兼容性分析

传统的加密算法将图像看成二进制流，加密后破坏了文件结构。因此，如果没有正确的密钥便无法正常解码。本文提出的加密算法与压缩编码相结合，遵从SPIHT的编码格式通过加密重要的编码控制信息从而改变输出码流。因此，本文算法加密效率高并且能够满足SPIHT标准的格式兼容性，即使密钥错误，解码端的处理仍然能够正常进行，但无法获得原始图像的正确信息。

（4）相关性分析

相关系数，是衡量两个随机变量之间线性相关程度的指标。如果明文与密文相关系数显著，可能会泄露明文信息从而为攻击者提供线索，存在安全隐患。因此，本文在对USCSIPI标准测试图库中的图像加密后，分别统计了码流相关性与图像相关性。码流相关性指的是加密码流与原始码流的相关系数；图像相关性指的是从分别从图像的水平、垂直以及对角方向分别抽取一定数量的像素对（这里取1024对）并分别计算相关系数，统计结果如表1所示。从表中可以看出：采用本文提出的选择加密算法加密后，码流相关性和图像相关性很小，达到了理想的标准，起到了很好的置乱效果。

（5）压缩性能与效率分析

本文提出的加密算法与压缩编码相结合，没有改变编码前的数据分布，对编码性能影响很小。此外，在选择加密的基础上引入了置乱机制，降低了码流相关性从而使得加密更加安全，仅需加密前6轮扫描编码中的系数重要性判定值和集合重要性判定值便可以保证图像的安全性。表2分析了USC-SIPI标准测试图库加密和解密后的PSNR，并统计了每幅图像所需要加密的数据量，平均比例约为原图数据量的2.28%。

3、几种加密算法性能对比

表3对几种加密算法的时间效率进行了对比（这里统计的时仅仅是压缩编码时间，不包括小波变换部分）。对比的算法分别为：1)采用SPIHT对图像编码（不加密）；2）采用RC4加密前两层压缩码流；，3）采用Arnold算法对前2层码流进行置乱；4）采用本文提出的选择加密算法。从表中可以看出，本文提出的选择加密算法具有很高的加密效率。