一种新的图像置乱算法 - 第27届中国数据库学术会 …

一种基于小波变换和骑士巡游的图像置乱算法题目三号 121

侯启槟 杨小帆 王阳生 黄向生1作者四号长仿宋 1

(中国科学院自动化研究所 北京 100080) 单位小五号 2

(重庆大学计算机学院 重庆 400044)

(qbhou@nlpr.ia.ac.cn) 小五号

摘要 由于图像或视频数据在网络中（特别是在无线网络中）进行传输时，很容易被非法截取，人们对多媒体数据传输的安全性提出了很高的要求。许多典型的图像加密方法都是对传输图像的像素直接进行置乱，这使图像置乱的程度受到了限制；也有一些方法是对变换域的变换系数置乱。提出了一种新的图像置乱加密算法，其基本思想是首先将原图像进行小波分解，然后以棋盘上的骑士巡游线路为工具，充分利用小波子带的特点将小波系数进行置乱。这为图像加密提供了一种全新的思路。通过与传统的置乱算法做比较，验证了本算法能够获得更好的置乱效果。并通过对实验数据的分析和解释得到了若干有益的结论，为进一步的研究工作奠定了基础。摘要小五楷

关键词 图像加密；置乱算法；骑士巡游；小波变换关键词小五宋

中图法分类号 TP391分类号小五号

An Image Scrambling Algorithm Based on Wavelet Transform Title四号

Hou Qibin1, Yang Xiaofan2, Wang Yangsheng1 , and Huang Xiangsheng1 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 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 algorithm 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 useful conclusions are obtained through the analysis and explanation of the experimental data, which lay a solid foundation for further research. Abstract小五号

Keywords image encryption; coefficient scrambling; knight’s tour; wavelet transform Key words小五号

正文五号宋体在日常生活中，网络多媒体数据应用变得越来越广泛，如多媒体邮件、视频点播、视频会议，和即将兴起的多媒体短信，等等。当图像或者视频通过网络传输时，对图像或者视频内容的有效加密和保护，也益发重要，因为所传输的图像，往往含有使用者私有的信息。在网络传输过程中，包含私有信息的图像有可能被截取、被复制，而导致严重的后果。可以说，私有信息的安全性是整个社会稳定的基石，也越来越受到人们的重视。

图像或视频信息的有效加密方法是传统保密学研究中遇到的新问题，因为图像数据有着与原有需要加密数据不同的特点。针对这个问题，近年来研究者们提出了许多解决方法，一般说来，这些方法可以分为两大类：一类是将需要保护的图像，隐藏加入另一幅不需要保护的目标图像中，在不能显露被保护图像的同时，目标图像并没有可以觉察的变

收稿日期：2006-05-25 Date六号 基金项目：(如有国家或省部级基金资助，请写上正确基金项目名称和编号)

2 计 算 机 研 究 与 发 展 2006年

化，即信息隐藏与伪装技术，包括数字水印等；另一类是采用密码学的基本思想和一些新的手段，将需要保护的图像直接进行置乱或分存等处理，使其在视觉效果上不包含任何有意义的内容。

已经有很多文献提出了图像置乱的方法[1-11]。其中文献[6-7]将骑士巡游用于图像细节隐藏，并指出其特点是具有一定的免疫性。文献[8]利用骑士巡游置乱方式多、时间快、求逆置换方便的优点，对图像像素进行置乱，达到加密的目的。并提出置乱度的概念，用以客观评估图像置乱程度。其缺点是为了达到较高的置乱度，需要进行比较多步数的置换。这些置乱方法[1-8]直接在原图像的像素空间域进行处理。在图像的安全传输中，如果在空间域直接对图像像素进行置乱，将大大降低像素之间的相关性，使低比特率图像编码变得困难。文献[10]提出频域加密算法，使用混沌序列生成的符号矩阵对DCT块排列变换而得到置乱结果。文献[11]提出对原图像使用四子树编码后再进行部分加密达到置乱效果。他们的工作都很有意义。

小波变换是对图像进行多尺度分析的强有力工具[12]

，已被广泛应用于图像压缩、边缘和特征检测以及纹理分析等领域[13]。图像的多尺度表示是依据多尺度分析，将图像分解成一个简单的多层次框架，框架中每一个分量具有独特的频率特性和空间取向特性，这些特性为图像的进一步分析和处理提供了良好的基础[14-16]。文献[17]提出采用多尺度小波分解进行图像压缩编码的方法。静态图像压缩标准JPEG2000中用小波变换替代离散余弦变换而呈现若干新特点[18]。

本文将探讨小波变换与骑士巡游相结合的图像置乱加密方法。

1 小波变换与骑士巡游结合用于图像加密基

本原理

1.1 骑士巡游的几个概念二级标题五黑 所谓骑士巡游（knight’s tour），就是在一块mn的国际象棋棋盘上，骑士从初始位置出发，不重复地遍历棋盘中每个方格的一种方案[19]。图是研究骑士巡游问题的有效工具。可以用一个图G = (V, E) （称为骑士巡游图）来表示nn棋盘上骑士的有效线路：其中V(i,j)|1i,jn，E={(i,j), (k,l)}| (|i-k|, |j-l|) = (1,2) or (2,1)}。则每种骑士巡游方案均可用图G中的一条Hamilton路径表示[19]。骑士巡游问题则是如何在骑士巡游图上有效地构建Hamilton路径（骑士巡游）。

一个88棋盘的骑士巡游路线如下面的矩阵T

所示，称为巡游矩阵，其中1表示巡游的起始点，64为巡游的终点。1，2，…，64的路线称为Hamilton路径。为了置换操作的方便，巡游矩阵T可用巡游线性列表L来替代。

1(8,1)564158355039603347445540593451382(7,3)3(8,5)42574649365332614(6,4)T4548435431623752205306322111613L =5(5,2)......296421417142510......6192278231215......63(5,4)图字六号12871832692464(6,2)

图1 88巡游矩阵及其对应线性列表图题小五号

文献[8]中已经指出骑士巡游可以适用于图像置换加密的性质，包括：

性质1. 当n5，且为偶数时，以任意点作为初始点，巡游矩阵总存在。

性质2. 巡游矩阵作为密钥，其个数足够多。对于一个88的棋盘，它拥有的不同巡游路径的个数大约是1.3051035[20]

。对于比88大的棋盘，笔者

尚未见到有关骑士巡游数目下界的文献。但有一点可以肯定：大棋盘上骑士巡游的数目一定远大于88棋盘上巡游的数目。事实上，88棋盘上骑士巡游矩阵的个数已经远大于Hilbert曲线、Peano方法、E-曲线、幻方置乱变换等方法的密钥个数[6]。可能会出现多个巡游矩阵置乱效果相近的情况；但除非置乱效果完全相同，否则不可能由其恢复出原始图像。两幅置乱图像每个像素值都一样的概率很小，因此对密钥空间的影响不大。

1.2 基于小波变换与骑士巡游的图像加密原理

对原始图像X{xij}mn进行多尺度小波分解，所得到的各个低频和高频子带，都可以看做是不同大小的棋盘，小波系数矩阵中的每个值对应于棋盘上的一个方格。用C{cij}ab表示小波系数矩阵，用巡游矩阵T{tij}ab对应的线性列表L={(num, row, col) | num=1 2,…, a×b;1≤row≤a;1≤col≤b}，对C作置

换，得到的置换系数矩阵为C{cij}ab，具体置换方

法如下：

将C与T按行列一一对应，将C中对应T中1位置（查对应的线性列表L获得位置坐标）的系数移到2对应的位置，将C中对应T中2位置的系数移

3 计 算 机 研 究 与 发 展 2006年

到3对应的位置，…，以此类推。最后将C中对应T中ab位置的系数移到1对应的位置，就得到按T置换一格后的系数矩阵。

对置换后的各系数矩阵进行逆二维离散小波变换。由于低频系数和高频系数都被置乱，逆变换后的

图像X{xij}mn将具有与原图像X{xij}mn不同的视觉效果，呈现出无规律的特点，从而使原图像的

内容得到保护。

2 基于小波变换与骑士巡游的图像置乱算法描

述

设原始图像为X{xij}mn，置乱后的图像为

X{xij}mn。对每个整数k 3，设(k)={T|T=(tij)2k2k是2k×2棋盘上的巡游矩阵}，

每个巡游矩阵对应的线性列表L(k) =

{(num,row,col)|num=1,2,…,2k×2k;1≤row≤2k;1≤col≤2k}。则我们的图像加密置乱算法表述如下：

算法1. Wavelet_Knighttour_Based_Image_Scrambling.

输入：原始图像X{xij}mn，巡游矩阵对应的线性列表L

输出：置乱图像X{xij}mn 第1步：图像分量预处理。如果原始图像是RGB

或YUV彩色图像，则对其每个颜色分量或色度、亮度分量，分别进行处理；

第2步：图像大小预处理。判断待处理图像

X{xij}mn的行列数m,n是否为2的幂次。如果不

是，则随机产生像素值增添到相应的行、列，使其行数和列数均为2的幂次且相等（记为X{xij}NN，其中N2k）；

第3步：图像的多尺度二维小波分解。使用选定的小波，对图像进行多尺度二维分解。C{cij}ab表示系数矩阵；

第4步：小波系数置乱，对每个子带分别进行如下处理：

随机产生置乱步数step；

for i = 1 to step

① 从{3, …, k}中随机选取一个值；将某个系数矩阵分成rr个不交叠的大小为22的系数块（rN/2），第a行第b列的系数块简称系数块(a, b)；

② 对每个系数块(a, b)，从()中随机选择巡游矩阵T(a, b)，其对应线性列表为L()，并随机生成整数(a,b)，(a,b)在[20-50]之间的均匀分布；

③ 对每个系数块(a, b)，依据L()，进行(a,b)格置换；

④ 将置换完的各个系数块拼合成系数矩阵； end for

第5步：在第4步对所有系数矩阵置乱完后，对置乱系数矩阵进行逆二维离散小波变换，得到置乱加

密的图像X{xij}mn。 当需要从置乱图像X{xij}mn恢复出原始输入图像X{xij}mn时，只需要对以上算法中每一步进行对应的逆处理即可。

3 实验结果与分析

3.1 置乱算法算例

下面以256256的Lena图像为例，说明Wavelet_Knighttour_Image_Scrambling算法的有效性。我们采用Roth[21]提出的算法来产生骑士巡游矩阵。例如：利用Roth的方法，分别产生规模为88、1616,3232，6464，128128的骑士巡游矩阵。

图2(a)为原始的Lena图像X{xij}mn,m=n=256；对图2(a)进行如下运算：

第1步：用Haar小波进行2尺度二维分解； 第2步：对分解后尺度1的3个高频部分，用128128巡游矩阵置换10格；对尺度2的3个高频 部分，用6464巡游矩阵置换10格；对尺度2的低

4 计 算 机 研 究 与 发 展 2006年

频系数，用6464巡游矩阵置换10格后再用3232巡游矩阵将系数矩阵分为44的小块，每个小块的置换格数在[20，50]间随机确定；

第3步：对置换后的系数矩阵进行逆变换，得到

{x置乱后的图像X如图2(b)所示。从视觉效果ij}mn，

来说，置乱图像相当接近于噪声图像。图2(c)是从置

乱图像恢复出的原始图像。图2从直观表明我们的图像置乱算法是可行的。

(a) (b) (c)

图2 置乱算法算例. (a) 原始图像；(b) 置乱图像图；(c) 恢复图像图题小五号

3.2 原始图像像素空间置乱和变换域系数置乱效果比较

使用文献[8]中定义的置乱度（SM）来评估图像的置乱程度，它的计算式为： 能对结果产生影响。本文中计算SM时，采用的是同一幅均匀分布噪声图像，因此不同计算结果具有可比性。

表1 各种巡游矩阵转动30格置乱图系数比较表题小五号 度量指标

8*8 0.1813 31.0785 0.9657

16*16 0.2891 33.1038 0.9454

32*32 0.3040 33.3227 0.9425

64*64 0.3390 33.7953 0.9359

128*128 0.3978 34.4899 0.9248

)SM(X,X(x(xi1j1i1j1mnmnijij)x2， (1)

ijSM 表字六号 NC

rij)2{xij}mn表示置其中X{xij}mn表示原始图像，X乱图像，R{rij}mn表示与原始图像相同大小的均匀分布噪声图像。

对同一幅图像，分别采用88,1616,3232, 6464，128128的巡游矩阵对原图像每个子块的每个像素转动30格。对得到的5幅置乱图像，按照式(1)～(3)分别计算其置乱度SM，峰值信噪比PSNR以及规范化互相关度NC(Normalized cross-correlation)。所得结果见表1。

(1) 直接对原始图像像素置乱 设定总置乱步数=2，第1步时，利用128128的巡游矩阵对原图像的每个22子块中每个像素转动10格；第2步，利用6464巡游矩阵对图像的每个44子块中每个像素转动10格。得到的置乱图像如图3(a)，SM = 0.3018，计算时间复杂度为O(N)，N为像素的个数。

255PSNR10log10i,ji,j2， (2) ~(xijxij)

(a) (b)

xNCi,ji,jij~xij2ijx. (3)

图3 像素空间与变换域系数置乱效果比较. (a)像素空间置乱; (b) 小波系数置乱

表1的结果表明，PSNR和NC不能很好地刻划图像的置乱程度；与之相比，SM能较好反映图像的置乱程度。置乱度的定义中，使用与原始图像相同大小的均匀分布噪声图像R做为参数，它的不同选择可

(2) 对原始图像的变换域系数置乱

对尺度1的高频部分，置乱步数=1，利用128128的巡游矩阵，分别对高频的水平部分、垂直部分、斜线部分中的系数转动10格。对尺度2的

5 计 算 机 研 究 与 发 展 2006年

高频部分和低频部分，置乱步数=1，利用6464的巡游矩阵，分别转动10格。对所有的置乱系数逆变换，得到的置乱图像如图3(b)，SM = 0.4031，计算时间复杂度为O(N) ，N为像素的个数。

现象1.与像素空间置乱相比较，小波系数置换计算复杂度相同，但置乱度有明显增加。这说明，小波系数置乱比像素空间置乱效率更高。

解释：由于小波系数反映的是原图像中对应位置周围像素分布的频率特征，对于小波系数的置换，影响的不仅仅是图像中的某一个像素，而是图像中的像素块。因此，在置换格数相同的情况下，小波系数置换必然比像素置换所引起的原图像的变化大，即置乱度增大。

3.3 各子带变换系数对置乱度的影响

本小节的目的是讨论各子带系数置乱对图像总体置乱程度的影响，从而在对各子带置乱时，通过更有效分配计算资源，达到更高的置乱度。

使用Haar小波，对原始图像进行尺度2的二维小波分解。提取尺度1中的低频系数、高频的水平部分、高频的垂直部分、高频的斜线部分。提取尺度2中的低频系数、高频的水平部分、高频的垂直部分、高频的斜线部分。

选取置乱步数=2，分别用128128和3232的巡游矩阵，对尺度1的低频系数进行置乱。选取置乱步数=1，用128128的巡游矩阵，对尺度1的高频（包括水平部分、垂直部分和斜线部分）进行置乱。选取置乱步数 = 1， 用6464巡游矩阵对尺度2的低频系数置乱。选取置乱步数 = 1，用6464巡游矩阵对尺度2的所有高频部分置乱。

讨论的8种情况及结果表2所示：

表2 各子带系数置乱对置乱度的影响

实验尺度1

尺度2

置乱度

次数 低频 高频 低频

高频

1 不置乱 置乱 0.0191 2 置乱 不置乱 0.3989 3 置乱

置乱 0.4180 4 不置乱 置乱 不置乱 0.3790 5 不置乱 置乱 不置乱 0.4043 6 置乱 不置乱 置乱 0.0524 7 置乱 置乱 不置乱 0.3900 8

置乱

置乱 置乱

0.4234

从表2，可以总结出如下现象：

现象2. 低频系数置乱对重构图像的置乱度影响最大。

现象3. 各尺度的高频系数置乱对置乱度影响不大，但为了不泄漏原始图像的轮廓信息，需要对所有尺度的高频，包括水平部分、垂直部分、斜线部分都进行置乱。

解释：与低频系数相比，高频系数绝对值一般都非常小，并集中在零点附近[16]。因此，置乱后的高频系数与置乱前的高频系数相比，各对应位置的系数值变化不大，对原图像的影响也就比较小。而原图像中像素值不发生突变的区域比较大，小波变换后低频系数携带有图像的大量细节信息，系数本身的变化也比较大[16]，因此，在低频系数置乱后，对应位置的系数值变化比较大，也必将对原图像的像素分布产生比较大的影响。

3.4 小波分解低频系数置乱次数与置乱度的关系

现象2表明：置换小波分解的低频子带对整幅图像的置乱度影响比较大。我们需要确切了解多级小波分解低频置乱格数与置乱度的关系。以2级二维小波分解为例，将所有高频子带的置乱格数固定。对尺度1的高频部分，取置乱步数=1，128128大小的巡游矩阵，置乱格数=30；对于尺度2的高频部分，取

置乱步数=1，6464大小的巡游矩阵，置乱格数=30；

设定低频子带的置乱步数为1，巡游矩阵规模选定为6464，置乱格数在0-50之间随机变动。由此所得置乱图像的置乱度随低频子带置换格数变化的曲线如图4所示：

图4. 尺度2的低频系数置换格数与置乱度关系图 现象4. 对低频子带进行置乱，置换格数在[0～10]间变化，所引起的置乱度变化较大。当置乱格数>10时，置乱图像的置乱度变化很小，它们的值在0.4～0.5之间变化，从视觉效果看，置乱图像很接近随机噪声图像。

解释：置换格数<10的置乱低频系数，与置换格数>10的置乱低频系数相比，相应位置的变化比较大，因此置乱图像的置乱度变化明显。当置换格数大于10后，各置乱低频系数相应位置的变化减小，因此置乱图像的置乱度变化减小。 3.5 小波分解级数与置乱度的关系

以Lena图为例，对它分别进行尺度1、尺度2、

6 计 算 机 研 究 与 发 展 2006年

尺度3二维Haar小波分解，将所得各度的各子带置换相同的格数。将置换后的系数逆变换，获得置乱图像。置乱图像的置乱度与不同级数的关系如表3（置乱步数=1，置乱格数=10）。

现象5. 在各子带系数置换格数相同的前提下，置乱度与尺度大小成正比。

表3 相同置乱格数下尺度与置乱度关系表

尺度 1 2 3

置乱度 0.3618 0.4031 0.4331

乱。对已经用6464巡游矩阵置换若干次（置换格数在[20，50]间随机选定）的尺度2低频系数，再分别用3232,1616巡游矩阵，将系数矩阵分为22,44个系数块，每个系数块的置换格数在[20，50]间随机选定，置乱步数 = 3，置乱后的视觉效果如图5所示，n表示组合的次数，其对应的SM值如表4所示:

表4 尺度2低频系数组合巡游置换后各图像的SM值

n 0 1 2

SM 0.4234 0.4490 0.4574

解释：随着分解层数的增加，小波系数的范围和能量都越来越大，说明大尺度分解的小波系数具有更重要的地位[16]。因此，如果进行相同程度的置乱，大尺度低频子带的变化对原图像的影响比小尺度低频子带的变化对原图像的影响更大。 3.6 低频子带组合置乱与置乱度的关系

尺度1所有高频部分置乱格数固定，尺度2所有高频部分置乱格数固定，尺度2低频系数进行组合置

现象6. 随着低频系数组合置乱次数的增加，置乱

度有所提高。对已经用巡游矩阵置换的系数矩阵，再用几个不同大小的巡游矩阵随机组合置换，置乱图像的置乱度增加。

解释：低频系数组合置乱的目的，是加大低频子带的置乱力度。它反映在置乱图像中，是置乱度的增加。

(a) (b) (c)

图5 尺度2低频系数组合巡游置换后的置乱图像. (a) n=0; (b) n=1; (c) n=2

4 结束语

本文将二维小波变换与骑士巡游相结合，提出一种图像置乱加密算法，并通过对置乱后的效果进行分析，得到了若干有指导意义的结论。与现有典型图像置乱方法相比[9]，本文提出在变换域利用巡游矩阵，对不同子带的系数进行不同置换，达到对图像进行置乱加密的目的。它为图像置乱与压缩编码相结合问题的研究提供了新的思路。如何将置乱加密与压缩编码有效结合，是一个值得深入研究的课题。一个解决的方法，可能是对压缩后的码流进行置乱，这方面的工作正在继续。另外，该方法在实际应用中还有若干问题有待解决，如巡游矩阵本身的安全性，以及在传输过程中错误恢复问题等都有待进一步研究。

参 考 文 献

[1] Matias Y, Shamir A. A video scrambling technique based on space filling curves. In: C Pomerance, ed. Lecture Notes in Computer Science 93:Advances in Cryptology

(CRYPTO’87). Berlin: Springer-Verlag, 1988. 398-417参考文献六号 [2] Qi Dongxu, Zou Jianchen, Han Xiaoyou. A new class of scrambling transformation and its application in the image information covering. Science in China: Series E, 2000, 43(3),

304-312

[3] 丁玮, 齐东旭. 数字图像变换及信息隐藏与伪装技术. 计算机学报,

1998, 21(9): 839-843

[4] 吴旻升, 王介升. 刘慎权，图像的排列变换. 计算机学报, 1998, 21(6): 514-519

[5] 曹长修. 一类基于行列式计算思想的图像置乱加密算法. 计算机工程与应用, 2002(8):37-39 [6] 柏森, 曹长修. 一种新的数字图像置乱隐藏算法. 计算机工程, 2001, 27(11): 37-39 [7] 柏森, 曹长修. 一种新的数字图像置乱隐藏算法. 计算机工程, 2001, 27(11): 37-39 [8] 侯启槟, 杨小帆, 王阳生. 一种新型的图像置乱加密算法. 2003

[9] Ding Wei, Yan Weiqi, Qi Dongxu. Digital image scrambling. Progress in Natural Science, 2001, 11(6): 454-460 [10] 孙鑫，易开祥，孙优贤. 基于混沌系统的图像加密算法. 计算机辅助设计与图形学学报, 2002, 14(2): 136-139 [11] Cheng H, Li X. Partial encryption of compressed images and videos. IEEE Trans on Signal Processing, 2000, 48(8): 2439-2451. [12] Alan Watt, Fabio Policarpo. The Computer Image. Essex: Addison Wesley Longman Limited, 1998 [13] Gerald Kaiser. A Friendly Guide to Wavelets. Boston: Birkhauser, 1997

[14] 胡昌华等编著. 基于MATLAB的系统分析与设计—小波分析. 西安：西安电子科技大学出版社, 1999 [15] 朱长青. 小波分析理论与影像分析. 北京：测绘出版社, 1998 [16] 程正兴. 小波分析算法与应用. 西安：西安交通大学出版社, 1998

[17] Jerome M Shapiro. Embedded image coding using zerotrees of wavelet coefficients. IEEE Trans on Signal Processing, 1993, 41(12): 3445-3462

[18] Charilaos Christopoulos, Athanassios Skodras, Touradj Ebrahimi. The JPEG2000 still image coding system: An overview. IEEE Trans on Consumer Electronics, 2000, 46(4):

1103-1127

[19] Ian Parberry. An efficient algorithm for the Knight’s tour problem. Discrete Applied Mathematics, 1997, (73): 251-260 [20] Ernesto Mordecki. On the number of Knight’s Tours. 2002. http://kolmogorov.cmat.edu.uy/~mordecki/articles/divisibility/ [21] Arnd Roth. A fast and simple algorithm. 2002. http://sunny.mpimf- heidelberg.mpg.de/people/roth/Mma/Knight.html

作者介绍小五号 侯启槟，男，1973年生，博士研究生，主要研究方向为图像/视频的安全传输。

杨小帆，男，1964年生，教授，1998年英国Reading University访问学者，先后在国内外发表论文80多篇。主要研究方向为图论、并行计算。

王阳生，男，1949年生，研究员，博士生导师，主要研究方向为模式识别、智能处理、计算机视觉。

黄向生，男，1975年生，博士研究生，主要研究方向为小波、图像压缩、智能处理。