基于arnold变换的非正方形图像置乱算法-学位论文.doc

基于Arnold变换的非正方形图像置乱算法(Scrambling algorithm for rectangle-Image based on Arnold transforms)项目组组长: 梁小勇 项目组成员: 薛成辉 王李芳 指导教师： 李香林 郭琳琴 吕梁学院数学系2012年2月摘 要随着网络技术的发展，数字图像的传输安全问题受到了越来越多的重视，图像置乱作为信息隐藏的手段得到了广泛的应用。在众多图像置乱算法中，Arnold变换置乱算法由于其简单、易于理解和实现，而得到了很好的应用，但二维Arnold变换一般只适用于等长图像，而当图像的长宽不等时，该变换过程不具有一一映射。文中对现有的非正方形图像置乱技术进行了分析，在此基础上给出了一种新的将二维Arnold变换应用于非正方形图像的方法，该算法首先将非正方形图像依据较短边长划分为多个有重合区域的正方形块，然后采取从左到右的顺序分别对每个区域块进行二维Arnold变换的置乱方式，从而完成对全图的置乱。置乱中正方形区域的划分办法综合考虑到置乱结果区域性和计算量问题，选取块间重合区域大小接近于原图较短边长的1/2。本算法适用于任意长方形图像，置乱恢复过程采用逆变换方法。实验结果表明，该算法简单，安全，有效，在少量的置乱迭代次数下即可达到较好的置乱效果。关键词 Arnold变换 非正方形 图像置乱AbstractArnold transform has wide range of applications in the image scrambling. Analysis of Arnold transformation matrix in image scrambling applications, on this basis, An Image scrambling algorithm for rectangle-Image based on Arnold transforms is proposed. in the algorithm, First, the original rectangular-image is divided into some square blocks which have overlapping area, and then from left to right order to scramble each block with Arnold transformation. Experimental results show that the algorithm is simple and safe, and in the small number of iterations can be achieved good scrambling effect. Key words： Arnold transform; Rectangle-Image; Image Scrambling 第一章 绪论图像作为人类认识和表达世界的基本方法，应用极为广泛，从古老的壁画、象形文字到今天的数字化图像，图像一直伴随着人类历史的发展，人们也期望从图像中得到直观的信息，“眼见为实”是再自然不过的事情。但是，在信息膨胀和普及的今天，事情并不是这么简单。随着多媒体技术的迅速发展和网络带宽限制的放松，越来越多的数字化图像在网络上传输。这些图像信息有些无关紧要，有些却至关重要，它们有可能涉及到个人的隐私、公司的利益、国家的安全，其价值无法衡量。另一方面，网络的普及使得任何人都有可能接触到其中的信息，并从中搜集，而无论这种搜集是善意还是恶意、合法还是非法。这就使得在网络上传输图像的安全性倍受关注，对图像进行加密也就成为重要的研究方向。图像置乱技术从一维的单表密码扩展而来， 应用到二维图像平面、甚至三维图像色彩空间中。它就是把数字化图像做一些“扰乱”，得到一幅完全杂乱无章、面目全非的图像，扰乱图像的组成部分，破坏图像的自相关性，使其所要表达的真实信息无法直观地得到，那么即使非法截获者注意到它，如果不知道置乱所采用的算法，就难以恢复原始图像，即使计算机用“穷举法”计算各种组合，也要耗费大量的时间，从而在一定程度上保护了图像信息。数字图像置乱还可以作为数字水印的预处理，用于增强图像伪装的鲁棒性。将置乱后的一幅无内容、无纹理、无形状的图像嵌入到另一幅普通图像时就不容易引起那幅图像太大改变，甚至不会发生改变，这样人眼就不易识别，从而增强了图像伪装的鲁棒性图像置乱包括位置置乱、灰度置乱以及两种方式的结合。位置置乱就是通过改变图像中各像素点的位置从而达到置乱的目的，灰度置乱则是通过改变图像的像素值而达到置乱目的。目前已有的数字图像置乱算法相当多1-5, 具体的置乱方法可以分为基于矩阵变换的图像置乱、基于伪随机序列的图像置乱和基于混沌理论的图像置乱。基于矩阵变换的方式包括Arnold变换、仿射变换、幻方变换和骑士巡游变换等，这些矩阵变换实际上是把图像进行拉伸、压缩、折叠及拼接的过程，通过这一过程将离散化的数字图像矩阵中的点进行重新排列，从而达到置乱的目的。为了达到比较好的加密状态可以进行多次迭代。基于伪随机序列的方式是通过软件或硬件设计一种伪随机序列发生器，它可以产生一定数值范围内的随机序列，通过将这些点与图像的像素点进行数学运算，从而改变像素值的大小，达到置乱的目的。第二章 基于Arnold变换的非等长图像置乱算法2.1 基于Arnold变换的图像置乱数字图像可以看作是平面区域上的二元函数在离散网格点处的采样值，这样就得到了一个表示图像的矩阵，矩阵中元素的值代表对应点处的信息（灰度值或RGB颜色分量）。对图像的加密实质上就是对这个二维矩阵进行加密。Arnold变换，俗称“猫脸变换” (Catmapping)，是V.J.Arnold在遍历理论的研究中提出的一类裁剪变换5，它可以抽象为在平面单位正方形内绘制一个猫脸图像，通过变换猫脸图像由清晰变模糊。定义1设有单位正方形上的点，将点变到另一点的变换为: (1)式中: (mod1)表示模1运算。此变换称作二维Arnold变换。考虑到数字图像的需要，把式(1)中的二维Arnold变换改写为: (2)下面所说的Arnold变换即式(2)。其中:，为数字图像矩阵的阶数。考虑到其可进行多次置乱，则得到如下迭代式:(3)式中:，代表迭代的次数， 。上述二维Arnold变换在图像置乱中应用相当广泛，但一般只适用于等长图像，因为它对任意方阵，变换周期都存在，而当图像的长宽不等时，变换周期不一定存在，无法应用周期方法解密，并且该过程不是一一映射，也无法采用逆方式解密。2.2 现有算法目前已有的二维Arnold变换应用于非等长图像的置乱方法有两种，一是图像扩充法，先将图像扩展为等长图像，然后用二维等长Arnold变换进行置乱处理；二是Arnold变换推广式，即修改了变换中的单一取模，扩展了二维Arnold变换的应用范围。2.2.1图像扩充法文献6提出了基于二维等长Arnold变换的非等长图像置乱算法。其基本思想是:将长方形图像按照较大的边长扩充为正方形图像，然后再应用二维Arnold变换进行置乱。被置乱后的图像和原图大小不一致，图像置乱恢复结束后需要进行裁剪才能得到原始图像。原图扩充后图像置乱后图像置乱恢复图像裁剪后图像图1 基于扩充算法置乱示例图2.2.2 Arnold推广式文献7考虑到数字图像长宽不等的问题，把式(2)中的二维Arnold变换变形为: (4)其中：为原始图像的像素点的坐标，表示置乱后的图像的像素点的坐标，为图像的高，为图像的宽。文中证明了图像高宽比或为整数或奇数时变换周期是存在的，即该变形公式将二维Arnold变换的应用范围进行了扩展。如下图,原图为400*800的灰度图,满足宽高比为整数,即可以采用推广式进行置乱。原图置乱后图像置乱恢复后图像图2 基于推广式算法的置乱示例图2.2.3现有两种算法的局限性上述第一种算法在图像置乱前将图像的属性进行了更改，在置乱恢复后还需要进行图像切割才能真正得到原图；第二种算法扩展了Arnold变换的应用范围，但仍不能适用于所有非等长图像。2.3 本文提出的算法本文从两种现有算法的基础上出发，在不改变图像本身属性的前提下提出一种新的基于Arnold变换的非等长图像置乱算法，该置乱算法适用于任意非等长图像。2.3.1算法思想对于任意长方形图像，总可以划分为有限多个有重合区域的正方形区域块，以长方形图像的较短边为边长的正方形区域，如图所示。图3 本文置乱算法示意图其中：为重合区域宽度，。则可以对上述划分的每个正方形区域从左到右顺序应用二维Arnold变换，从而实现对整个长方形图像的置乱变换。若，则最差的划分，即划分后产生正方形区域块最多的方式是重合区域。如有4*10的图像，采用的重合区域，则其置乱过程为： 图4 4*10大小图像的置乱顺序示意图图像划分的正方形区域块的大小为4*4，块和块间的重合大小为2，那么顺序的置乱源图像1-4行1-4列的区域、1-4行3-6列的区域、1-4行5-8列的区域、1-4行7-10列的区域，即完成了对整个图像的一次置乱过程。该置乱过程允许多次迭代，直到达到较好的置乱效果。2.3.2重合区域的选取可以看到在该算法中，不同的图像重合区域的划分不同，即使同一幅图像，重合区域的划分也可能会有多种。那么，计算可能的重合区域，以及如何从中选择合适的重合区域进行置乱，也就成为算法的核心部分。设待置乱图像为大小，且，若被划分为块正方形区域，则重合区域大小满足： 其中，的整数特别的，时，即待置乱图像为正方形图像。另外，重合区域最差情况下为，即那么，可能的重合区域大小为： 且的整数如待置乱图像大小150*200，则当时，；当时，；当时，所以；当时，所以；当时， ；当时，所以；那么，推导可得对于大小的图像，可能的划分为：表1 大小图像重合区域计算结果表236112651100125140145148149可以看到，对于同样大小的图像划分为多个正方形区域时可能的划分有多种，选择适当的重合区域应考虑如下因素：一是置乱均匀性。对于一些图像而言重合区域大小可以为0，但这样的正方形区域划分必然会使得置乱过程只在区域中发生，当然如果重合区域大小过小也会使得置乱后图像出现明显的区域痕迹，这需要通过大量的置乱次数来弥补才能得到较为均匀的置乱后图像。如下图像为256*128大小的灰度图，可能的重合区域值有：0，64，96，112，124，126，127,如取重合区域大小为0，则置乱后图像会看到有明显的区域性，且这种区域性一般需要较多次置乱才可能弥补。置乱 20 次置乱40 次置乱 60 次置乱 80 次重合区域值取0置乱结果原图置乱 1 次置乱 2 次置乱 3 次置乱 5 次重合区域值取64（较靠近1/2的值）图5 置乱结果区域性问题说明图二是计算量。如果重合区域较大，那么划分的正方形区域块数量也会增大，一次置乱的时间花费就会较大，即计算量会越大。以下为选取不同大小图像进行置乱的一次置乱时间比较结果，重合区域大小分别取较小的、中间的、较大的三种值。表2 置乱计算量问题说明比较表图像大小重合区域值一次置乱耗时图像大小重合区域值一次置乱耗时320*2401603.136000400*8002006.6120002244.69600032010.86400023930.99700038027.097000768*102451213.5570001200*200040029.52200073637.265000100051.106000760122.6470001160212.116000为了在较短时间较好的实现置乱，综合以上两各因素，我们选取最接近的重合区域大小，实验表明这样的选择是合理的。2.3.3置乱恢复一般Arnold变换的图像置乱恢复是借助于周期性来实现的，而本文算法由于存在重合区域，且置乱过程是按照划分的正方形区域块从左到右来依次进行的，这样就会导致一些点在一次完整的置乱中会经过一个或几个位置，事实上周期在许多划分情况下都是不存在的。以大小的图像为例，取重合区域大小，则原图被划分为2块，那么对于点的具体置乱过程如下：第一次置乱：第二次置乱：第三次置乱：第四次置乱：第四次置乱：可以看到置乱在内不断重复，不论置乱执行多少次总是不能回到原来的点。那么这就表明, 对于大小的图像，在被划分为2块正方形区域的情况下，本文算法不具有周期性。文献8中提出基于Arnold变换的正方形图像不仅可以借助于周期性进行置乱恢复，还是可以借助于Arnold逆变换进行置乱恢复。二维Arnold逆变换: (5)由于本算法的置乱基本思想是基于正方形划分，那么按照置乱的正方形区域块的划分方式，采用二维Arnold逆变换，从右到左依次来进行块的逆置乱，从而就可以实现对整个长方形图像的置乱恢复过程。第三章 仿真实验3.1算法有效性实验选取320*240大小的灰度图，其可能的重合区域值有：160，200，220，224，230 232，235，236，238。取接近于1/2的值160进行置乱。置乱结果如图所示：原图置乱 1 次置乱3 次置乱 5 次置乱恢复图6 算法有效性实验结果1选取120*240大小的灰度图，其可能的重合区域值有：60，80，90，96，100，105，108，110，112，114，115，116，117，118，119。取接近于1/2的值60进行置乱。置乱结果如图所示：原图置乱 1 次置乱 3 次置乱 5 次置乱恢复图6 算法有效性实验结果2从图可以看出，对于长方形图像在本算法下可以在经过较少次的置乱后得到一幅杂乱无章，无纹理的图像，能较好地隐藏图像信息。从图中也可以看到，在得知置乱过程的重合区域大小的情况下可以较快的对置乱后图像进行恢复。3.2 置乱均匀性实验选取大小为320*400的图像，取重合区域值240进行置乱并恢复的结果，如图所示：原图置乱后图像修改后图像置乱恢复图像图7 置乱均匀性实验结果从上图可以看出，本文算法的置乱是较为均匀的，经过较少的置乱次数后图像中的各点分布在整个长方形图像区域中。3.3算法安全性实验选取大小为280*180的图像，取重合区域值为80进行置乱，置乱恢复中取错误的重合区域大小的恢复结果。原图置乱后图像取重合区域值为155恢复结果取重合区域值为176恢复结果取重合区域值为正确的恢复结果图8 算法安全性实验结果从上图可以看到，对于置乱后图像，若不知道正确的重合区域大小值也不能正确的恢复图像，具有一定的安全性。3.4与现有算法的比较实验选取大小为：1200*2000的图像，在不同置乱算法下的置乱结果如图所示：原图扩充后图置乱结果图恢复图恢复结果图基于扩充方式的置乱算法原图置乱后图像置乱恢复图像基于Arnold变换扩展方式的置乱算法原图置乱后图像置乱恢复图像本文算法图9 三种置乱算法比较实验从上图可以看出，对于同一幅长方形图像采用扩充方式需要修改原图，置乱后传输图像与原图属性有较大差别，置乱恢复后还需要对其进行切割才可真正恢复。Arnold变换推广式的算法不适用所有图像，置乱过程中会有多点置乱后对应于一点的情况，因此置乱中会丢失图像信息，也不会正确恢复。而本文算法对于任意长方形图像均可以较好的置乱。第四章 结束语传统的二维Arnold变换只适用于正方形图像的置乱，而对于一般的长方形图像不能够直接使用。目前基于二维Arnold变换的非等长图像置乱算法有基于图像扩充的方法和基于推广的Arnold变换两种，但这两种算法各有局限性。本文基于二维Arnold变换提出将非等长图像划分成有限多个有重合区域的正方形块，对每个正方形块顺序进行置乱的方法，该方法适用于任意长方形图像，能够均匀的置乱图像。实验结果表明，该算法是有效的，安全的。参考文献1齐东旭.矩阵变换及其在图像信息隐藏中的应用研究J.北方工业大学学报,1999, 11(1):24-28.2丁玮,闫伟齐,齐东旭.基于置乱与融合的数字图像隐藏技术及应用J.中国图像图形学报,2000,5(8):644-648.3林学辉，蔡利栋.基于Hilbert曲线的数字图像置乱方法研究J.中国体视学与图像分析，2004,9(4):224-2274齐东旭,邹建成,韩效肴.一类新的置乱变换及其在图像信息隐蔽中的应用J.中国科学(E辑),2000,30(5): 440-448.5丁玮，闫伟齐，齐东旭.基于Arnold变换的数字图像置乱技术J. 计算机辅助设计与图形学学报,2001,13(4):338-3416孔涛,张亶.Arnold反变换的一种新算法J.软件学报,2004,15(10):1558- 1564.7邵利平,覃征.二维非等长图像置乱变换J.电子学报,2007,35(7):1290- 1294.8郭琳琴,张新荣,李震.基于Arnold逆变换的图像置乱恢复算法J.计算机应用与软件,2010,36(9):。17