数字图像置乱算法的研究与比较

汪太月,戴燕青

(湖北理工学院 数学与物理学院，湖北 黄石 435003)

数字图像置乱算法的研究与比较

汪太月,戴燕青

(湖北理工学院 数学与物理学院，湖北 黄石 435003)

随着信息技术及互联网技术的快速发展，数字图像正逐渐成为传递和接收信息的主要载体。数字图像置乱技术能达到图像信息的保护及实时使用的目的。文章从数字图像置乱的理论及概念入手，对几种具有代表性的数字图像置乱算法进行分析、比较及改进，阐述了各自的优缺点，且通过实验实现了不同置乱方式的效果。

图像置乱；置乱变换；算法实现；分析比较

随着信息技术迅猛发展及互联网技术的普及，人们获取信息的方式正由传统的纸质书籍、报刊演变为电子文本及数字图像等。数字图像以其直观性及概括性，逐渐成为信息传播最常见的方式。而数字式产品易于复制和篡改为其致命的弱点。如何保证数字图像所携带信息的安全性和保密性成为了信息安全领域中的重要研究内容[1]。

对于文本资料，密码学能发挥较好的加密作用，而数字图像与文本资料的存储维度不同，数据量要大得多，且有一定的时效性要求，使用与文本资料相同的加密方式，视觉效果难以得到保障[2]。计算机图形学虽对图像加密起到一定作用，但难以满足安全性要求[3]。比较不同的加密技术，数字图像置乱算法能够最大限度地保障信息的传输以及存储安全，不失为稳定且高效的方法[4]。

数字图像置乱算法能很好实现图像像素的位置重排，呈现出与原图像不同的显示效果[5]，置乱图像的信息就自然无法被他人获取到，且置乱算法灵活，能更大限度地对图像进行加密处理，提升了图像的安全性。它是数学、信息学、密码学以及计算机科学等有机结合的产物，是一种融合技术面广、应用领域多元化的方法[6]。本文从置乱算法的原理、置乱效果等方面对几种数字图像置乱算法进行分析和改进，同时通过实验实现和比较置乱效果,最后归纳总结了不同算法的优缺点。

1 数字图像置乱的基本概念

图像是外界事物在大脑中形成的实体映像，如静态图像、动画照片以及视频图画等，是当今信息传播的最主要载体[7]。在日常生活中传输隐私度较高的信息时，当然不希望图像信息被他人轻易获取。在当前各种图像加密隐藏技术中，数字图像置乱技术越来越引起广泛关注和研究。数字图像置乱技术用途广泛，在用来加密的前提下，也能用于其他技术的预处理以及后续处理，如常用的图像水印、数字图像分存、版权保护技术等[8]。

数字图像置乱算法的本质就是利用数学变换以及各种算法对图像进行处理，通过移动像素点的位置或改变像素值，将图像的显示信息完全打乱而达到保密的效果。在实现算法的同时常引入密钥，能最大限度保证图像的安全性。对于大部分加密算法及技术，数学变换是这些技术方法的基础。对于数字图像置乱，有如下定义。

定义1[9]给定变换矩阵T，表达式为T=L[t(i,j)]m×n，即1,2,…,m×n的一种排列方式，图像A表达式为：A=[a(i,j)]m×n，将图像A依据变换矩阵T作图像置乱变换后即可得到图像B。其变换方式如下：

将图像A中位置1的像素灰度值或RGB分量值挪动到位置2，同理可将位置2的像素灰度值或RGB分量值挪动到位置3，以此类推，对图像A和矩阵T做逐一变换。在置乱变换的最后，将位置的像素灰度值挪动到位置1，就能得到置乱后图像B，该过程可记为B=TA。

定义2[9]给定图像A=[a(i,j)]m×n，设变换T是{(x，y):1≤x≤n，1≤y≤m，且x，y均为整数}到自身的一对一映射，即：将图像A中位置(x，y)处的元素变换到位置(x',y')处即可得到图像B，则称变换T是图像A的置乱变换，仍记为B=TA。

对比定义1与定义2，发现其实并没有本质的区别，但从使用的场合来说是有区别的。不同的置乱变换，其置乱矩阵T也是不同的，因此构造置乱矩阵T就是构造置乱变换。由定义2可以看出，构造置乱变换就是构造{(x，y):1≤x≤n，1≤y≤m，且x，y均为整数}到自身的一对一映射。

定义3[10]若存在一个大于1的正整数N能够满足表达式TNA=A，就称最小的正整数N为置乱变换T的周期。

图像处理时，阵列能以图像显示，图像以阵列存储。置乱程度是指数字图像被打乱的程度，一般而言，图像表现得越乱，置乱的效果就越好。数字图像置乱算法是置乱效果以及安全性的直接影响因素，好的算法更能保障图像信息的安全性以及保密性。根据置乱算法的易实现性和高效性，本文讨论和研究的置乱算法有Arnold变换、Hilbert曲线变换、Fibonacci变换及基于相邻像素间位异或的图像置乱算法。

2 常见的数字图像置乱算法及其实现

2.1 Arnold变换置乱算法

Arnold置乱变换是Arnold提出的一种置乱方法[11]，该方法最初是对猫脸图像进行操作，因此俗称为猫脸变换，对数字图像作如下操作：

(1)

式(1)中x,y∈{0,1,2,…,N-1}，表示的是置乱变换前像素点位置，而(x',y')表示的是像素经过置乱变换之后的位置，mod为模运算。数字图像可视为一个二维的矩阵，矩阵经变换后对应图像像素的位置发生变化，从而生成新的图像。该变换在遵循一定变换规律的条件下可持续执行，因此不仅能实现图像加密，而且能达到图像置乱的目的。

数字图像进行Arnold置乱时，置乱次数可人为控制且无上限，置乱后的图像难以辨识。在重复一定的迭代变换后，数字图形能够实现完美的还原，也就是说Arnold置乱变换具有周期性，因而得以广泛的应用。还原出原始图像信息的最少迭代次数即为置乱周期T。不同的像素N值与Arnold置乱变换的周期T之间存在一定关系。

Arnold置乱算法的周期与图像像素值之间的关系见表1。由表1可得，N与T并不是严格的正比例关系，对于给定的正整数N，当N>2时，它们满足如下不等式：

(2)

本研究采用图像处理中最常见的Lena图像为原始图像，利用MATLAB软件进行置乱处理，迭代10次的Arnold置乱图像及反置乱图像如图1所示。

表1 Arnold置乱算法的周期与图像像素值之间的关系

图1 Arnold置乱图像及反置乱图像

2.2 Hilbert曲线变换置乱算法

Hilbert曲线是德国科学家Peano在1891年发现的一种曲线，该算法是对正方形的边进行等分，将正方形一分为四。通过曲线的走向对原始图像中的每一个像素点实现遍历而生成一幅杂乱无章的新图像，这就是Hilbert曲线置乱变换[12]。对于最简单的四元素矩阵，元素的排列顺序为1，2，3，4。不同阶Hilbert曲线的遍历如图2所示，其二阶的Hilbert曲线如图2(a)所示，四阶Hilbert曲线及256阶Hilbert曲线分别如图2(b)、(c)所示。图像中元素的遍历从左下角的元素开始，遍历的次序为3,1,2,4，一直到右下角结束。对一个任意的N阶图像进行Hilbert曲线遍历操作，一定能将该N阶图像划分为4个N/2阶的曲线遍历，而每一个N/2阶曲线遍历又可以继续被划分为4个N/4阶的Hilbert曲线遍历，以此类推，直到划分成2×2的最小遍历像素矩阵。同为二阶的4个最基本的Hilbert曲线遍历，其形状是完全相同的，只是曲线的走向略有不同而已， 因而划分后的曲线遍历可直接依据二阶Hilbert曲线遍历的顺序依次完成。

图2 不同阶Hilbert曲线的遍历

将Lena图像按Hilbert曲线进行赋值，拉成一条一维数组，再reshape成一幅图像即为置乱图像。Hilbert曲线变换置乱图像及恢复图像如图3所示。

图3 Hilbert曲线变换置乱图像及恢复图像

为增强图像置乱的复杂性与安全性，先将Lena图像reshape成一维数组，然后再按Hilbert曲线进行赋值，且对其旋转90°生成一幅图像即为置乱图像。改进的 Hilbert曲线变换置乱图像及恢复图像如图4所示。

图4 改进的 Hilbert曲线变换置乱图像及恢复图像

2.3 Fibonacci变换图像置乱

公元1200年，由意大利著名数学家Leonardo Fibonacci研究提出的一个非常重要的数列，即Fibonacci数列，因其具有一些较为特别的性质而被广泛使用[13]。

定义4[14]设边长为N的方形数字图像的坐标分别为(x,y)和(x',y')，若(x,y)与(x',y')存在的映射满足公式(3)，同时有(x',y')∈[0,N]×[0,N]，且该数字图像具有周期性，就称其为二维等长图像，其中a，b，c，d为正整数或0；N代表图像矩阵的维度参数。

(3)

将式(3)中的参数分别取值为a=b=c=1，d=0,就称为二维等长Fibonacci图像置乱变换，即:

(4)

根据Fibonacci数列和矩阵的性质[13]，Fibonacci变换矩阵Q可由3个初等矩阵组合而成：

(5)

由式(5)可以得出，Fibonacci变换改变了像素点的位置，而图像像素点的灰度值变化不大。3个初等矩阵分别对图像进行了对称变换、错切变换及切割回填处理。在变换的过程中，2个区域内的像素的相对位置没有发生变化，图像局部联系也没有发生变化，也就是说，图像在经过置乱后其灰度值并没有改变。Fibonacci置乱也是具有周期性。Fibonacci变换图像像素大小与置乱周期的关系见表2。

表2 Fibonacci变换图像像素大小与置乱周期的关系

对Lena图像进行Fibonacci变换，不同迭代次数Fibonacci变换置乱图像如图5所示。图5(a)、 (b)分别为迭代次数为8,32的置乱图像，采用矩阵的逆运算可得反置乱图像。

图5 不同迭代次数Fibonacci变换置乱图像

由图5容易发现，随着置乱迭代次数增加，置乱图像变得更为零乱，与此同时，图像纹理也变得更均匀，波动性变得更小，充分反映了Fibonacci置乱变换是一种基于空间位置上的图像置乱算法。

2.4基于相邻像素间位异或的图像置乱算法

位异或是一种应用于逻辑操作的二进制数学运算，符号表示为“∧”，其运算的过程可以表示为：a∧b=a'b+ab'(a'、b'分别表示非a、非b)，当真异或假、假异或真时，其最后结果都为真；而当真异或真、假异或假时，其结果都为假[15]。通过分析总结即为：当运算符两端的2个值不相等时，则异或结果为真，反之则为假。将数字a与同一个数字b进行2次异或运算，其结果仍为原数值a，这就是异或运算符的特点，表达式为a=a∧b∧b。

置乱变换必须是可逆变换，这样才能准确无误地恢复原始图像。而异或运算是可逆的，同时异或运算简单灵活，方便高效，运用到数字图像置乱能取得较为理想的置乱效果。

以M×N像素图像为例，为了便于叙述，取M=256,N=256,即8 bit位图像，基于相邻像素间位异或的图像置乱算法的实现步骤描述如下：

1)记原始图像A，A(i,j) 表示图像中第i行、第j列元素的灰度值，置乱后得到的图像记为B,大小不变,也为M×N。

2)将原始图像的第一个像素的灰度值A(1,1)与M-1做异或运算，得到像素点A'(1,1)，然后对其进行交叉换位操作，即令A'(1,1)的第1 bit位与第8 bit位互换位置，第2 bit位与第4 bit位互换，第3 bit位与第7 bit位互换，第5 bit位与第6 bit位互换，最后得到B(1,1)，交叉换位操作示意图如图6所示。

图6 交叉换位操作示意图

3)将A(1,2)与它前一位B(1,1)做异或运算得到A'(1,2)，再按图6换位规则进行交叉换位操作得到B(1,2)。

4)依次对每一个元素A(i,j)与B元素(i,j-1)做异或运算得A'(i,j)，再对A'(i,j)进行交叉换位操作可得B(i,j)，以此类推，直到遍历A的整个像素点，即得到置乱后的图像B。

通过置乱算法的逆操作可还原原图像，具体操作是从置乱图像的最后一个像素的灰度值B(M,N)开始，依次向前分别进行位异或运算且进行交叉换位操作，重复操作直到B(1,1)，还原操作就算结束。逆过程的步骤描述与置乱实现步骤完全相反，最后得到A即为还原图像。基于相邻像素间位异或的置乱图像及还原图像如图7所示。

图7 基于相邻像素间位异或的置乱图像及还原图像

2.5置乱算法的分析与比较

不同图像置乱算法的比较见表3。

表3 不同图像置乱算法的比较

Arnold变换、Hilbert曲线变换以及Fibonacci变换置乱算法都是基于位置空间的图像置乱算法，从本质上来说，它们都是通过矩阵变换改变数字图像中各个像素点的位置和顺序，进而能够达到置乱的效果。置乱图像只是像素位置发生改变，而图像的像素总数、灰度值以及直方图并未发生变化，原理简单，算法高效。但重排置乱图像总能还原出原始图像，因此该类算法存在明显的缺陷，即安全性有待提高。基于相邻像素间位异或运算的图像置乱方法与基于位置空间的图像置乱方法的区别在于，该算法并不改变像素的位置和顺序，而是在色彩空间上对像素的灰度值进行处理，进而达到置乱的目的。与基于位置空间上的算法相比而言，安全性更强，效果也更优。不同方法产生的置乱效果不尽相同，一般来说，迭代次数越多，置乱效果越好。

3 结束语

图像置乱算法能较好地保证图像携带信息的安全性和保密性。本文从Arnold变换，Hilbert曲线变换，Fibonacci变换及基于相邻像素间位异或的图像置乱算法的原理、优缺点、置乱效果等方面进行分析比较及改进，同时给出置乱算法的实现及还原过程，为信息安全提供了理论和实践的保证。由于不同置乱算法效果不尽相同，今后将进一步探讨多种置乱算法的融合，且考虑与密码学、数字水印技术等相结合。

[1] 赵铁宇.基于相位恢复算法和公钥密码学的光学图像加密技术研究[D].哈尔滨：哈尔滨工业大学,2016.

[2] 高峰.密钥定位耦合有限域余弦变换的图像加密算法[J].计算机应用与软件,2016,33(7):318-320.

[3] Liang Y,Liu G,Zhou N,et al.Image encryption combining multiple generating sequences controlled fractional DCT with dependent scrambling and diffusion[J].Journal of Modern Optics,2015,62(4):251-264.

[4] Gopalakrishnan T,Ramakrishnan S,Balakumar M.An image encryption using chaotic permutation and diffusion[C].International Conference on Recent Trends in Information Technology.IEEE,2014:1-5.

[5] 黄兴,张敏瑞.图像置乱程度的研究[J].武汉大学学报(信息科学版),2008,33(5):465-468.

[6] Zhang W,Wong KW,Yu H,et al.An image encryption scheme using lightweight bit-level confusion and cascade cross circular diffusion[J].Optics Communications,2012,285(9):2343-2354.

[7] Ullagaddi V,Hassan F,Devabhaktuni V.Symmetric synchronous stream encryption using images[J].Signal Image and Video Processing,2015,9(1):1-8.

[8] Stoyanov B,Kolev M,Nachev A.Design of a new self-shrinking 2-adic cryptographic system with application to image encryption[J].European Journal of Scientific Research,2012,78(3):362-374.

[9] 黄仿元.基于Arnold变换的图像置乱算法及实现[J].贵州大学学报(自然科学版),2008,25(3):276-279.

[10] 张健,于晓洋,任洪娥,等.图像置乱程度的衡量方法[J].计算机工程与应用,2007,43(8):134-136.

[11] Kong T,Zhang T.A novel algorithm for inverse Arnold transforms[J].Journal of Software,2004,15(10):1558-1564.

[12] 林峰.基于HDFS的影像数据金字塔构建及存储技术研究[D].哈尔滨：东北林业大学,2016.

[13] 袁明豪.Fibonacci数列的模数列的周期性[J].数学的实践与认识,2007,37(3):119-122.

[14] 邵利平,覃征, 高洪江,等.二维非等长图像置乱变换[J].电子学报,2007,35(7):1290-1294.

[15] 朱淑芹,李俊青,葛广英.基于一个新的四维离散混沌映射的图像加密新算法[J].计算机科学,2017,44(1):188-193.

(责任编辑吴鸿霞)

Research and Comparison of Digital Image Scrambling Algorithm

WangTaiyue，DaiYanqing

(School of Mathematics and Physics,Hubei Polytechnic University,Huangshi Hubei 435003)

With the development of information technology and the Internet,Digital images gradually has become the main carrier of the transmission and receiving of information.Digital image scrambling technology can play a more and more important role in the protection of image information and achieve the purpose of real-time use.With the theory and concept of digital image scrambling,this paper analyzes,compares and summarizes the principles of several representative digital image scrambling algorithms,and their respective merits and demerits are elaborated,at last,the experimental results indicate the effect of different scrambling methods.

image scrambling;scrambling transformation;algorithm implementation;analysis and comparison

2017-06-15

国家自然科学基金项目(项目编号：61302138);湖北省教育厅科研基金项目(项目编号：B2015095)；湖北理工学院创新人才项目(项目编号：14xjz02C)；湖北理工学院重大教研项目(项目编号：2015A08)。

汪太月,副教授,博士,研究方向：广义高斯信号处理及图像处理、信息安全。

10.3969/j.issn.2095-4565.2017.04.006

TP391.9

：A

：2095-4565(2017)04-0025-06