1、计 算 机 研 究 与 发 展 DOI:10.7544/issn1000-1239.2015.*Journal of Computer Research and Development 卷(期):起止页,年收稿日期：yyyy-mm-dd Date 六号 修回日期：yyyy-mm-dd Date 六号基金项目：如有国家或省部级基金资助，请写上正确基金项目名称和编号一种基于小波变换和骑士巡游的图像置乱算法 题目三号杨小帆 1,2 王阳生 1 作者四号 （注：文章中所有字号均以红框所示为准，请直接套用模板。 ）1 中科院自动化所，北京 100080 单位小五号2 重庆大学计算机学院，重庆 40004
2、4()小五号 An Image Scrambling Wavelet Transform and Knights Tour Title 四号Yang Xiaofan1,2 and Wang Yangsheng1 Name 五号1 (Institute of Automation, Chinese Academy of Science, Beijing 100080) Depart.Correspond 小五号2 (College of Computer Science, Chongqing University, Chongqing, 400044)Abstract Image secure
3、transmission is one of the main research issues in the field of network communications. Many typical image encryption techniques take the direct way of scrambling the transmitted image itself, which may limit the scrambling effect that is achievable. In the present paper, a new image encryption algo
4、rithm is proposed. This algorithm uses various knight-tours on the chessboard as the basic tool for image scrambling, and scrambles the wavelet coefficients of the transmitted image instead of the image itself. Experimental results show that our algorithm can achieve better scrambling effect. Some u
5、seful conclusions are obtained through the analysis and explanation of the experimental data, which lay a solid foundation for further research. Abstract 五号，至少200 字，影响 EI 索引Key words image encryption; coefficient scrambling; knights tour; wavelet transform Key words 五号摘要 由于图 像或视频数据在网 络中（特别是在无线网络 中）进
6、行传输时，很容易被非法截取，人 们对多媒体数据传输的安全性提出了很高的要求。许多典型的图像加密方法都是 对传输图像的像素直接进行置乱， 这使图像置乱的程度受到了限制；也有一些方法是对变换域的变换系数置乱。本文提出了一种新的 图像置乱加密算法，其基本思想是首先将原图像进行小波分解，然后以棋 盘上的 骑士巡游线路为工具，充分利用小波子 带的特点将小波系数进行置乱。这为图像加密提供了一种全新的思路。通过与传统的置乱算法做比较，验证了本算法能够获得更好的置乱效果。并通过对实验 数据的分析和解释得到了若干有益的 结论， 为进一步的研究工作奠定了基础。 摘要五号楷体，300 字左右关键词 图像加密；置乱算
7、法；骑士巡游；小波变换 关键词五号楷体中图法分类号 TP391 分类号五号正文五号宋体 在日常生活中，网络多媒体数据应用变得越来越广泛，如多媒体邮件、视频点播、视频会议，和即将兴起的多媒体短信，等等。当图像或者视频通过网络传输时，对图像或者视频内容的有效加密和保护，也益发重要，因为所传输的图像，往往含有使用者私有的信息。在网络传输过程中，包含私有信息的图像有可能被截取、被复制，而导致严重的后果。可以说，私有信息的安全性是整个社会稳定的基石，也越来越受到人们的重视。图像或视频信息的有效加密方法，是传统保密2 计 算 机 研 究 与 发 展 2014 年收稿日期：yyyy-mm-dd Date 六
8、号 修回日期：yyyy-mm-dd Date 六号基金项目：如有国家或省部级基金资助，请写上正确基金项目名称和编号学研究中遇到的新问题，因为图像数据有着与原有需要加密数据不同的特点。针对这个问题，近年来研究者们提出了许多解决方法，一般说来，这些方法可以分为两大类：一类是将需要保护的图像，隐藏加入另一幅不需要保护的目标图像中，在不能显露被保护图像的同时，目标图像并没有可以觉察的变化，即信息隐藏与伪装技术，包括数字水印等；另一类是采用密码学的基本思想和一些新的手段，将需要保护的图像直接进行置乱或分存等处理，使其在视觉效果上不包含任何有意义的内容。已经有很多文献提出了图像置乱的方法 111 。其中文
9、献67将骑士巡游用于图像细节隐藏，并指出其特点是具有一定的免疫性。文献8利用骑士巡游置乱方式多、时间快、求逆置换方便的优点，对图像像素进行置乱，达到加密的目的。并提出置乱度的概念，用以客观评估图像置乱程度。其缺点是为了达到较高的置乱度，需要进行比较多步数的置换。这些置乱方法 18 直接在原图像的像素空间域进行处理。在图像的安全传输中，如果在空间域直接对图像像素进行置乱，将大大降低像素之间的相关性，使低比特率图像编码变得困难。文献10提出频域加密算法，使用混沌序列生成的符号矩阵对DCT 块排列变换而得到置乱结果。11提出对原图像使用四子树编码后再进行部分加密达到置乱效果。他们的工作都很有意义。小
10、波变换是对图像进行多尺度分析的强有力工具12，已被广泛应用于图像压缩、边缘和特征检测以及纹理分析等领域13。图像的多尺度表示，是依据多尺度分析，将图像分解成一个简单的多层次框架，框架中每一个分量具有独特的频率特性和空间取向特性，这些特性为图像的进一步分析和处理提供了良好的基础141516 。 17提出采用多尺度小波分解进行图像压缩编码的方法。静态图像压缩标准 JPEG2000 中用小波变换替代离散余弦变换而呈现若干新特点18 。本文将探讨小波变换与骑士巡游相结合的图像置乱加密方法。本文的第二部分，将简述小波变换与骑士巡游结合用于图像加密基本原理；第三部分，描述我们的基于小波变换和骑士巡游的图像
11、置乱算法；第四部分，给出实验结果，并对实验结果加以分析；最后，在第六部分，对本文加以总结，并指出进一步的工作方向。1. 小波变换与骑士巡游结合用于图像加密基本原理 一级标题小四黑1.1 骑士巡游的几个概念 二级标题五黑所谓骑士巡游（knights tour） ，就是在一块的国际象棋棋盘上，骑士从初始位置出发，nm不重复地遍历棋盘中每个方格的一种方案19。图是研究骑士巡游问题的有效工具。可以用一个图 G = (V, E) （称为骑士巡游图）来表示 棋盘上骑士n的有效线路：其中 ，E=(i,j), jijiV,1|),(k,l)| (|i-k|, |j-l|) = (1,2) or (2,1)。则
12、每种骑士巡游方案均可用图 G 中的一条 Hamilton 路径表示19 。骑士巡游问题则是如何在骑士巡游图上有效地构建Hamilton 路径（骑士巡游） 。 公式用 office2003 编辑器或者 mathtype一个 棋盘的骑士巡游路线如下面的矩阵 T8所示，称为巡游矩阵，其中 1 表示巡游的起始点，64 为巡游的终点。1，2，64 的路线称为Hamilton 路径。为了置换操作的方便，巡游矩阵可用巡游线性列表来替代。图字六号，分图题用英文 249631872115960436263052527184 149738506038156T 1(8,)735(6,2)244(6,)235.L =
13、图 1 巡游矩阵及其对应线性列表Fig.1 8*8 matrix and its list图题小五号，中英文图题文献8中已经指出骑士巡游可以适用于图像置换加密的性质，包括：性质 1.当 ，且为偶数时，5n以任意点作为初始点，巡游矩阵总存在。性质 2.巡游矩阵作为密钥，其个数足够多。对于一个 的8棋盘，它拥有的不同巡游路径的个数大约是20。对于比 大的棋盘，笔者尚未3510.83 计 算 机 研 究 与 发 展 2014 年见到有关骑士巡游数目下界的文献。但有一点可以肯定：大棋盘上骑士巡游的数目一定远大于 棋8盘上巡游的数目。事实上， 棋盘上骑士巡游矩8阵的个数已经远大于 Hilbert 曲线、
14、Peano 方法、E-曲线、幻方置乱变换等方法的密钥个数6。可能会出现多个巡游矩阵置乱效果相近的情况；但除非置乱效果完全相同，否则不可能由其恢复出原始图像。两幅置乱图像每个像素值都一样的概率很小，因此对密钥空间的影响不大。1.2 基于小波变换与骑士巡游的图像加密原理对原始图像 进行多尺度小波分解，nmijxX所得到的各个低频和高频子带，都可以看作是不同大小的棋盘，小波系数矩阵中的每个值对应于棋盘上的一个方格。用 表示小波系数矩阵，baijcC用巡游矩阵 对应的线性列表 L=(num, ijtTrow, col) | num=1 2, ab;1 row a;1 col b，对 C 作置换，得到的
15、置换系数矩阵为 ，baijcC具体置换方法如下：将 C 与 T 按行列一一对应，将 C 中对应 T 中 1位置（查对应的线性列表 L 获得位置坐标）的系数移到 2 对应的位置，将 C 中对应 T 中 2 位置的系数移到 3 对应的位置，以此类推。最后将 C 中对应 T 中 位置的系数移到 1 对应的位置，就得到ba按 T 置换一格后的系数矩阵。对置换后的各系数矩阵进行逆二维离散小波变换。由于低频系数和高频系数都被置乱，逆变换后的图像 将具有与原图像 不同的nmijxXnmijxX视觉效果，呈现出无规律的特点，从而使原图像的内容得到保护。 、2 基于小波变换与骑士巡游的图像置乱算法描述设原始图像
16、为 ，置乱后的图像为nmijxX。对每个整数 k ，设 =T|T=nmijxX3)(k是 2k2 棋盘上的巡游矩阵，每个巡游矩kijt)(阵对应的线性列表 L(k) = (num,row,col)|num=1,2,2k2k;1 row2 k;1col2 k。则我们的图像加密置乱算法表述如下：算 法 1. Wavelet_Knighttour_Based_Image_Scrambling输入：原始图像 ，巡游矩阵对应nijxX的线性列表 L输出：置乱图像 nmij第一步： 图像分量预处理。如果原始图像是RGB 或 YUV 彩色图像，则对其每个颜色分量，或色度、亮度分量，分别进行处理。第二步： 图
17、像大小预处理。判断待处理图像的行列数 是否为 2 的幂次。如果nmijxX,不是，则随机产生像素值增添到相应的行、列，使其行数和列数均为 2 的幂次且相等（记为，其中 ） ；Nijxk第三步： 图像的多尺度二维小波分解。使用选定的小波，对图像进行多尺度二维分解。表示系数矩阵baijcC第四步： 小波系数置乱，对每个子带分别进行如下处理：【随机产生置乱步数 step；FOR i = 1 to step 从3, , k中随机选取一个值 ；将某个系数矩阵分成 个不交叠的大小为 的系r2数块（ ） ，第 a 行第 b 列的系数块简2/N称系数块(a, b)； 对每个系数块(a, b)，从 中随机选择巡
18、)(游矩阵 (a, b)，其对应线性列表为 ，并随TL机生成整数 ， 在20-50之间的均,),(匀分布； 对每个系数块(a, b)，依据 ，进行)(L格置换；)b 将置换完的各个系数块拼合成系数矩阵；END FOR】第五步： 在第四步对所有系数矩阵置乱完后，对置乱系数矩阵进行逆二维离散小波变换，得到置4 计 算 机 研 究 与 发 展 2014 年乱加密的图像 。nmijxX当需要从置乱图像 恢复出原始输入nij图像 时，只需要对以上算法中每一步nmijx进行对应的逆处理即可。3 实验结果与分析3.1 置乱算法算例下面以 的 Lena 图像为例，说明256Wavelet_Knighttour
19、_Image_Scrambling 算法的有效性。我们采用 Roth21提出的算法来产生骑士巡游矩阵。例如：利用 Roth 的方法，分别产生规模为 、8、 、 、 的骑士巡163412游矩阵。图 2(a)为原始的 Lena 图像m=n=256；对图 2(a)首先 Haar 小波进,ijXx行 2 尺度二维分解；第二步，对分解后尺度 1 的三个高频部分，用 巡游矩阵置换 10 格；对128尺度 2 的三个高频部分，用 巡游矩阵置换 10 格；对尺度 2 的64低频系数，用 巡游矩阵置换 10 格后再用巡游矩阵，将系数矩阵分为 的小块，34每个小块的置换格数在20， 50间随机确定；第三步，对置换
20、后的系数矩阵进行逆变换，得到置乱后的图像 ，如图 2(b)所示。从视觉效果来说，nmijxX置乱图像相当接近于噪声图像。图 2(c)是从置乱图像恢复出的原始图像。图 2 从直观表明我们的图像置乱算法是可行的。(a) Original image (b) scramblingiamge (c) recover image图 2 置乱算法算例 图题小五号，中英文图题Fig.2 Recover Algorithm3.2 原始图像像素空间置乱和变换域系数置乱效果比较使用8中定义的置乱度（SM ）来评估图像的置乱程度，它的计算式为：， (1)minjijijijijrxXSM12)(),(其中 表示原始
21、图像， 表示nijxnmij置乱图像， 表示与原始图像相同大小的mijrR均匀分布噪声图像。对同一幅图像，分别采用 、 、816、 、 的巡游矩阵对原图像326412每个子块的每个像素转动 30 格。对得到的 5 幅置乱图像，按照公式(1)-(3)分别计算其置乱度 SM，峰值信噪比 PSNR 以及规范化互相关度 NC(Normalized Cross-Correlation)。所得结果见表 1。， (2)jiijijxPSNR,210)(5log， (3)jijiijxC,2,表 1 各种巡游矩阵转动 30 格置乱图系数比较Table1 Comparison of Matrix 表题小五号,中
22、英文图题Metric 8*8 16*16 32*32 64*64 128*128SM 0.1813 0.2891 0.3040 0.3390 0.3978表字六号 31.0785 33.1038 33.3227 33.7953 34.4899NC 0.9657 0.9454 0.9425 0.9359 0.92485 计 算 机 研 究 与 发 展 2014 年表 1 的结果表明，PSNR 和 NC 不能很好地刻划图像的置乱程度；与之相比，SM 能较好反映图像的置乱程度。置乱度的定义中，使用与原始图像相同大小的均匀分布噪声图像 R 做为参数，它的不同选择可能对结果产生影响。本文中计算 SM 时
23、，采用的是同一幅均匀分布噪声图像，因此不同计算结果具有可比性。(1) 直接对原始图像像素置乱设定总置乱步数=2，第一步时，利用的巡游矩阵对原图像的每个 子块中1282每个像素转动 10 格；第二步，利用 巡游矩64阵对图像的每个 子块中每个像素转动 10 格。4得到的置乱图像如图 3(a)，SM = 0.3018，计算时间复杂度为 O(N)，N 为像素的个数。(2) 对原始图像的变换域系数置乱对尺度 1 的高频部分，置乱步数=1，利用的巡游矩阵，分别对高频的水平部分、垂28直部分、斜线部分中的系数转动 10 格。对尺度 2 的高频部分和低频部分，置乱步数=1，利用 的64巡游矩阵，分别转动 1
24、0 格。对所有的置乱系数逆变换，得到的置乱图像如图 3(b)，SM = 0.4031，计算时间复杂度为 O(N) ，N 为像素的个数。现象 1：与像素空间置乱相比较，小波系数置换计算复杂度相同，但置乱度有明显增加。这说明，小波系数置乱比像素空间置乱效率更高。此处省略解释：由于小波系数反映的是原图像中对应位置周围像素分布的频率特征，对于小波系数的置换，影响的不仅仅是图像中的某一个像素，而是图像中的像素块。因此，在置换格数相同的情况下，小波系数置换必然比像素置换所引起的原图像的变化大，即置乱度增大。3.3 各子带变换系数对置乱度的影响本小节的目的是讨论各子带系数置乱对图像总体置乱程度的影响，从而在
25、对各子带置乱时，通过更有效分配计算资源，达到更高的置乱度。使用 Haar 小波，对原始图像进行尺度 2 的二维小波分解。提取尺度 1 中的低频系数、高频的水平部分、高频的垂直部分、高频的斜线部分。提取尺度 2 中的低频系数、高频的水平部分、高频的垂直部分、高频的斜线部分。选取置乱步数=2，分别用 和128的巡游矩阵，对尺度 1 的低频系数进行置乱。3选取置乱步数=1 ，用 的巡游矩阵，对尺度281 的高频（包括水平部分、垂直部分和斜线部分）进行置乱。选取置乱步数 = 1， 用 巡游矩64阵对尺度 2 的低频系数置乱。选取置乱步数 = 1，用 巡游矩阵对尺度 2 的所有高频部分置乱。64讨论的八
26、种情况及结果表 2 所示。 此处省略从表 2，可以总结出如下现象：现象 2：低频系数置乱对重构图像的置乱度影响最大。现象 3：各尺度的高频系数置乱，对置乱度影响不大，但为了不泄漏原始图像的轮廓信息，需要对所有尺度的高频，包括水平部分、垂直部分、斜线部分，都进行置乱。解释：与低频系数相比，高频系数绝对值一般都非常小，并集中在零点附近16。因此，置乱后的高频系数与置乱前的高频系数相比，各对应位置的系数值变化不大，对原图像的影响也就比较小。而原图像中像素值不发生突变的区域比较大，小波变换后低频系数携带有图像的大量细节信息，系数本身的变化也比较大16，因此，在低频系数置乱后，对应位置的系数值变化比较大
27、，也必将对原图像的像素分布产生比较大的影响。3.4 小波分解低频系数置乱次数与置乱度的关系现象 2 表明：置换小波分解的低频子带，对整幅图像的置乱度影响比较大。我们需要确切了解多级小波分解低频置乱格数与置乱度的关系。以 2 级二维小波分解为例，将所有高频子带的置乱格数固定。对尺度 1 的高频部分，取置乱步数=1， 大18小的巡游矩阵，置乱格数=30；对于尺度 2 的高频部分，取置乱步数=1， 大小的巡游矩阵，置乱64格数=30；设定低频子带的置乱步数为 1，巡游矩阵规模选定为 ，置乱格数在 0-50 之间随机变64动。由此所得置乱图像的置乱度随低频子带置换格数变化的曲线如图 4 所示：图 4.
28、 尺度 2 的低频系数置换格数与置乱度关系图Fig.4 Something and Something 图题小五号，中英文图题现象 4：对低频子带进行置乱，置换格数在6 计 算 机 研 究 与 发 展 2014 年010间变化，所引起的置乱度变化较大。当置乱格数10 时，置乱图像的置乱度变化很小，它们的值在 0.40.5 之间变化，从视觉效果看，置乱图像很接近随机噪声图像。解释：置换格数10 的置乱低频系数相比，相应位置的变化比较大，因此置乱图像的置乱度变化明显。当置换格数大于 10 后，各置乱低频系数相应位置的变化减小，因此置乱图像的置乱度变化减小。3.5 小波分解级数与置乱度的关系以 Le
29、na 图为例，对它分别进行尺度 1、尺度 2、尺度 3 二维 Haar 小波分解，将所得各度的各子带，置换相同的格数。将置换后的系数逆变换，获得置乱图像。置乱图像的置乱度与不同级数的关系如表3（置乱步数=1 ，置乱格数=10） 。现象 5：在各子带系数置换格数相同的前提下，置乱度与尺度大小成正比。 表题小五号，中英文表题表 3 相同置乱格数下尺度与置乱度关系表Table 3 Just an Examle尺度 置乱度1 0.36182 0.40313 0.4331解释：随着分解层数的增加，小波系数的范围和能量都越来越大，说明大尺度分解的小波系数具有更重要的地位16。因此，如果进行相同程度的置乱，
30、大尺度低频子带的变化对原图像的影响，比小尺度低频子带的变化对原图像的影响更大。3.6 低频子带组合置乱与置乱度的关系尺度 1 所有高频部分置乱格数固定，尺度 2 所有高频部分置乱格数固定，尺度 2 低频系数进行组合置乱。对已经用 巡游矩阵置换若干次（置换64格数在20 ，50间随机选定）的尺度 2 低频系数，再分别用 、 巡游矩阵，将系数矩阵分32为 、 个系数块，每个系数块的置换格数在20， 50间随机选定，置乱步数 = 3，置乱后的视觉效果如图 5 所示，n 表示组合的次数，其对应的SM 值如表 4 所示。表题小五号，中英文表题表 4 尺度 2 低频系数组合巡游置换后各图像的 SM 值Ta
31、ble4 Just an Examlen 0 1 2SM 0.4234 0.4490 0.4574现象 6：随着低频系数组合置乱次数的增加，置乱度有所提高。对已经用巡游矩阵置换的系数矩阵，再用几个不同大小的巡游矩阵随机组合置换，置乱图像的置乱度增加。解释：低频系数组合置乱的目的，是加大低频子带的置乱力度。它反映在置乱图像中，是置乱度的增加。(a) n=0 (b) n=1 (c) n=2图 5 尺度 2 低频系数组合巡游置换后的置乱图像 图题小五号，中英文图题Fig .5 Just an Examle4 结束语本文将二维小波变换与骑士巡游相结合，提出 i一种图像置乱加密算法，并通过对置乱后的效果
32、进行分析，得到了若干有指导意义的结论。与现有典型图像置乱方法相比9，本文提出在变换域利用巡游矩阵，对不同子带的系数进行不同置换，达到对图像进行置乱加密的目的。它为图像置乱与压缩编码相结合问题的研究提供了新的思路。如何将置乱加密与压缩编码有效结合，是一个值得深入研究的课题。一个解决的方法，可能是对压缩后的码流进行置乱，这方面的工作正在继续。另外，该方法在实际应用中还有若干问题有待解决，如巡游矩阵本身的安全性，以及在传输过程中错误恢复问题等，都有待进一步研究。7 计 算 机 研 究 与 发 展 2014 年参 考 文 献1 Roman S. The Umbral Calcus M. New Yor
33、k: Academic Press, 1984:100-1302 Singh G, Serra L, Ping W, et al. BrickNet: Sharing object behaviors on the Net C /Proc of IEEE VRAIS95. Piscataway, NJ: IEEE, 1995: 19-253 Ebcioglu K, Altman E. DAISY: Dynamic compilation for 100 percent architectural compatibility C /Proc of the 24th Annual Int Symp
34、 on Computer Architecture. New York: ACM, 1997:135-1554 Lie Wennung, Lin Guoshiang. A feature-based classification technique for blind image steganalysis J. IEEE Trans on Multimedia, 2005, 7(6): 1007-10205 Li Xiaofeng, Feng Dengguo, He Yongzhong. Research on preprocessing policies in XACML Admin J.
35、Journal of Computer Research and Development, 2007, 44(5): 729-736(in Chinese)（李晓峰, 冯登国, 何永忠. XACML Admin 中的策略预处理研究J. 计算机研究与发展, 2007, 44(5): 729-736）6 Ji Qingguang. Study on formalization design for high-level secure operating system D. Beijing: Institute of Software, Chinese Academy of Sciences, 20
36、04 (in Chinese)(季庆光. 高安全等级操作系统形式设计的研究D. 北京: 中国科学院软件研究所, 2004)7 U S Department of Transportation Federal Highway AdministrationGuidelines for handling excavated acid-producing materials, PB 91-194001 RSpringfield：U S Department of Commerce National Information Service, 19908 Chiueh T, Huang L. Effici
37、ent real-time index updates in text retrieval systems R. New York: Stony Brook, 19989 Aberer KP-grid：A self-organizing access structure for P2P information systems G / LNCS 2172: Proc of the 6th Int Conf on Cooperative Information SystemsBerlin: Springer, 2001：179-19410 PACS-1： public-access compute
38、r systems forum EB/OLHouston,Tex ：University of Houston Libraries, 1989 1995-05-17http:/info.lib.uh.edu/pacsl.html11 Dublin Core Metadata Initiative. Dublin Core Metadata Element Set, Version 1.1: Reference Description EB/OL. (2003-06-02)2005-03-21. http:/dublincore.org/documents/2003/08/26/usageguide参考文献六号作者介绍小五号照片 Yang xiaofan,borun in 1964. Professor and PhD supervisor. His research iterests include game theory, parallel computing and machine learning. 照片 Wang Yangsheng,born in 1949, PhD supervisor.His mainresearch interest include pattern recognition and machine learning.
