Arnold恢复算法

2024-07-08

Arnold恢复算法（通用3篇）

Arnold恢复算法篇1

摘要：随着信息安全技术的发展, 作为有效的图像加密技术之一的Arnold变换, 由于其周期性而被广泛运用于图像置乱。但是, 现有的Arnold恢复算法, 特别是对于阶数较大的图像, 耗时较大。针对此情况, 本文提出改进的Arnold恢复算法, 综合了周期法和逆矩阵算法的优点。该算法将两种算法相结合, 先求取图像的Arnold变换周期Period, 然后将Arnold变换次数N与Period/2进行比较, 当N<Period/2时, 逆运算采取基于逆变换矩阵的恢复算法;当N>Period/2时, 逆运算采取基于周期的Arnold变换恢复方法。经过Matlab7.0实验仿真, 证明了本文算法较高的运行效率。

关键词：Arnold,周期法,逆矩阵法,Arnold恢复算法

1 Arnold变换定义

Arnold变换最早是由V.I.Arnold1]等提出的一种图像变换算法, 又称猫脸变换 (cat mapping) 。

猫脸变换核心在于变换矩阵, 其定义为:设平面单位正方形内的任一点为 (x, y) , 对其作特定的变换[2,3]如式1。

Arnold变换主要应用于数字图像相关技术领域中, 用以置乱数字图像已达到保密的目的。其具体操作就是对数字图像不断地进行迭代Arnold变换, 经过一定次数的变换后会有一个临界迭代次数, 在此次数下变换后的图像会呈杂乱无章状, 毫无规律可言。如此, 便可以将图像进行简单的加密[4,5]。Arnold变换在数字图像中的二维变换公式如2:

其中 (x, y) 、 (x', y') 分别为数字图像内的点和变换后的点, N是数字图像的阶数。

以上只是标准的二维Arnold变换表示形式。从矩阵形式上看, 一般的Arnold变换矩阵[6,7]如3:

2 Arnold变换的恢复算法

数字图像应用中的Arnold变换的恢复算法有两种方式:基于周期的运算方式和基于反变换的运算方式。一般数字图像需要进行多次置乱才可以达到满意的效果, 经过n次Arnold置乱的公式为4:

对于数字图像的置乱都是有周期的, 且周期随着图像阶数不同而不同。当置乱到一定次数时, 又会从置乱图像恢复到原图。加密技术中也就是利用了Arnold变换的周期性对数字图像进行加解密。将图像置乱的次数作为Key, 用以解密。当原图将经过n次Arnold置乱, 则需要对图像继续进行T-n次置乱才能得以恢复。数字图像的Arnold变换周期如表4所示。

由于数字图像水印算法本身具有一定的复杂度, 所以应尽量减少各组成部分的复杂度, 对此应该寻求一种简单快捷的Arnold逆运算方法, 对此可以参考[8]中的方法直接利用Arnold变换矩阵的逆矩阵直接迭代相同步数即可求得原图像, 这样就可以节省不少时间。例如, 对原图进行m次Arnold置乱, 则需要其进行m次逆运算即可恢复原图, 其计算公式如5。

3 改进的Arnold恢复算法

由已证明定理[9]可知, 基于逆矩阵的Arnold恢复算法也可以写成如式6:

但是在数字图像的背景下需要满足以

故此, 编程中令y=y'-x', 当x<0时, 取x=x+n;当x>n时, 取x=mod (

Arnold恢复算法一般会采取周期法和逆矩阵变换法。周期法原理简单, 但是其Arnold算法本身计算量大, 既复杂又耗时;逆矩阵法虽然简单、无需检测Arnold周期, 但是其计算量大, 耗时长。所以, 本文提出了一种简单快捷高效的Arnold逆运算方法, 综合了两种算法的优点。算法中将两种算法相结合, 先求取图像的Arnold变换周期Period, 然后将Arnold变换次数N与Period/2进行比较, 当N<Period/2时, 逆运算采取基于逆变换矩阵的恢复算法;当N>Period/2时, 逆运算采取基于周期的Arnold变换恢复方法。通过此方法, 大大提高了Arnold恢复算法的运行效率。

4 改进Arnold恢复算法的Matlab仿真结果

本文分别选取32×32的图像Lena1、64×64的图像shuiyin、128×128的图像shuiyin1、256×256的图像Lena2和512×512的图像Lena作为实验图像, 通过matlab仿真得到数据表如表2 (a) 、表2 (b) 、表2 (c) 。

由实验数据可知, 本文提出的改进Arnold恢复算法在效率方面有很大的优势, 在大图像的Arnold置乱恢复上尤其明显。该改进算法通过比较图像Arnold变换次数与Period/2的关系来决定恢复算法的选择, 进而用最少的时间恢复出原图像, 提高了恢复算法的有效率。

参考文献

[1]V.I.Arnold Avez A.Ergodic problems of classical mechanics.Mathematical Physics Monograph Series, W.A.Benjam in, INC.NewYork::1968.

[2]张海涛, 姚雪.基于分层Arnold变换的治置乱算法[J].计算机应用, 2013, 33 (8) :2240-2243.

[3]张颖, 杨玥.Arnold双置乱图像加密算法[J].辽宁工程技术大学学报:自然科学版, 2013, 32 (10) :1429-1432.

[4]吴玲玲, 张建伟, 葛琪.Arnold变换及其逆变换[J].微计算机信息:嵌入式与SOCT, 2010, 26 (5-2) :206-208.

[5]毛雷波.Arnold变换及其逆变换研究[J].重庆工程大学学报:自然科学版, 2012, 29 (3) :16-21.

[6]田云凯, 贾传荧, 王庆武.基于Arnold变换的图像置乱及其恢复[J].大连海事大学学报, 2006, 32 (4) :107-109.

[7]KINGSTON A., SVALBE I.Generalized finite radon transform for N×N images[J].Image and Vision Computing, 2007, 25 (10) :1620-1630.

[8]王圆妹, 李涛.基于Arnold变换的高效率分块图像置乱算法的研究[J].电视技术, 2012, 36 (3) :17-19.

[9]郭琳琴, 张新荣, 李震.基于Arnold逆变换的图像置乱恢复算法[J].计算机应用与软件, 2010, 27 (9) :265-267.

Arnold恢复算法篇2

信息加密是现代科技的重要课题, 加密方案需要保证信息不被第三方有效获取, 又能被合法接收者较易解密。图像信息由像素来表达, 像素呈二维分布, 总数巨大, 因而图像加密有独特性。基于Arnold变换的图像置乱技术[1]是一种行之有效的加密方案。V.J.Arnold研究遍历理论时提出了正方形区域的一种变换, 变换前后的点位置变乱但一一对应, 保证面积不变, 所以可通过周期性或逆变换变回原始图。

Arnold变换作用在方形图像上, 文献[2]提出了分块方法从而可处理非方形图像。文献[2]和[3]就运算时间对正反变换的效率做了讨论, 建议选用周期小的尺寸以及视情况采用反变换。但是运算量依然巨大, 并且变换矩阵行列式不等于1的广义Arnold变换[4]的逆矩阵会出现非整数, 不能在数字图像上使用。本文将从齐东旭[5]提出的有关原理出发, 探求广义Arnold变换的快速算法, 不管传统方法上多少次变换, 快速算法只需要在加密和解密端各进行一次全图的遍历即可完成, 根本上解决迭代运算耗时巨大的问题。

1 Arnold变换

1.1 经典Arnold变换

对于一个N×N的数字图像, 其经典二维Arnold变换由下式给出, (x, y) T和 (x′, y′) T分别是变换前后的像素坐标:

图像的每一个像素坐标按照 (1) 式变换, 得到新坐标, 新坐标的像素灰度 (或颜色) 使用变换前坐标上的像素灰度 (或颜色) 来设置。这样遍历图像的每一个像素就可获得一幅新图, 新图看起来是混乱的。多次迭代将加重置乱程度, 一般来说迭代10来次就使得图像面目全非。继续迭代又可以变回原图, 变回原图的最小迭代次数就是周期T。基于Arnold变换的加密方案就是发送方对数字图像置乱, 接收方利用变换的周期性再变换适当次数还原出清晰图。

1.2 广义Arnold变换

文献[5]研究了变换矩阵的元素是普通的正整数的变换, 即:

a, b, c和d是正整数, 并且证明行列式det=ad-bc与N互质的情况下, 使用该矩阵的变换就有周期性。

本文后面统一使用A来表示经典和广义变换矩阵。因而可统一使用下面 (3) 式来表示Arnold变换:

本文后面所述的Arnold变换包含经典和广义的Arnold变换。

2 Arnold二维变换的快速算法

2.1 Arnold二维变换的通常运算法

尺寸为N×N的图像置乱m次的算法有两种, 下面使用基于VB的伪代码表示。输入Img, 输出New Img。

算法1:

算法1对整图所有像素做Arnold二维变换形成新图, 迭代m次, 就完成了m次Arnold二维变换。算法2是对每个像素坐标迭代m次, 按最后的位置更新像素值。相比来说, 算法2的效率更高, 因为省掉了中间像素值更新动作。可是两种算法都有N×N×m次的坐标操作, 非常费时。还有一点, 算法2在实际编程时, 循环中可以连续两次变换, 一次 (x, y) T到 (x′, y′) T, 另一次 (x′, y′) T到 (x, y) T, 循环次数减半, 最后视奇偶情况看是否还要处理剩余的1次, 这样省去了中间坐标转存的动作。

2.2 Arnold二维变换的快速运算法

文献[5]证明, 以矩阵A对图像的m次Arnold变换可以使用中间矩阵Am对图像一次Arnold变换获得。所以, 上述算法中对坐标的迭代运算, 可简化为矩阵自己乘方运算。二阶矩阵只有4个元素, 运算量大减。优化算法如下, E为2×2的单位矩阵。

优化算法:

可是Am元素增大很快, 由于计算机的位宽有限, 很快就会溢出。本文的VB程序中使用Long型 (最大为2147483647) 存储矩阵元素, 对于经典Arnold矩阵:

可见22次方已经很大, 23次方时已经溢出。而经典二维Arnold变换周期一般都很大, 比如N=100的周期是150, 可见22次远远不够。下面讨论这个问题的解决方案。

为了普遍性, 设D为一个p阶方阵, 并定义D Mod N为对D的每个元素以N取模, D*N表示D中每个元素和N相乘。因而D可按下式分解。

kij∈{0, 1, 2, ...}, Dk是一个整数方阵。

当p=2时, 以D为变换矩阵的Arnold二维变换可化简如下:

所以变换矩阵在乘方过程中, 对结果的每个元素以N取模, 获得一个新变换矩阵, 使用这个新矩阵做Arnold二维变换和原始迭代算法的结果一致。

优化算法的计算中间矩阵的部分修改为如下。

前述的经典Arnold变换矩阵22次方结果:

这是一个很小巧的数字矩阵, 易于阅读和使用。

矩阵乘方运算量远小于矩阵和图像坐标逐个相乘的运算量, 复杂度从O (N×N×T) 减为O (N×N+T×2) 。对于解密, 产生C=AT-mMod N, C作为变换矩阵做一次Arnold二维变换即返回原图。综合来说, 基于Arnold二维变换的加解密总共只做两次Arnold变换。

3 Arnold三维变换及其快速算法

Arnold变换可以多维, 像素的灰度 (颜色) 值组成多维向量, 变换后的向量可通过逆变换或周期变换还原出原图。这里使用Arnold三维变换, 因为一般图像每个像素的颜色由R、G和B三个通道值组成, 每个通道最大值是256。设Q是一个3x3的方阵, (5) 式是Arnold三维颜色变换公式。

是很多文献使用的矩阵[5,6], 我们称基于该矩阵的变换为经典Arnold三维变换。

正如二维Arnold变换, 三维矩阵也可以有很多, 我们称它们为广义的Arnold三维变换矩阵。两类统称Arnold三维变换。

根据 (4) 式, m次Arnold三维变换可以使用QmMod 256矩阵的一次性Arnold三维变换来获取, 这就是三维变换的快速算法。

4 坐标和颜色的联合变换

使用 (2) 式对图片进行坐标变换得到中间图, 对中间图使用 (5) 式进行颜色变换得到最终加密图, 可以提高加密效果[7]。因为任何一个变换的矩阵参数或次数不知道就无法恢复出原图, 给攻击者增加了难度。有了快速算法, 联合变换变得切实可行, 否则的话耗时太长。

5 坐标和颜色变换周期的求法

向量和单位矩阵 (设为E) 的乘积是向量本身。因而对二维变换矩阵A和图像尺寸N, 若t次的AtMod N=E, 那么周期T=t。对三维变换矩阵Q和颜色阶数256, 若QtMod 256=E, 那么周期T=t。求A对N周期时, 先求A行列式, 若与N互质则周期存在, 然后按下面的伪代码求周期, 求Q对256的周期也类似。

表1列出了某些矩阵及相应图像尺寸对应的周期, 和文献[1,7,8]所列类似。第四个矩阵行列式是5, 与N=50, 100, 200不互质, 周期不存在。表2列出了一些Arnold三维变换矩阵以及对应N=256的周期。

6 快速Arnold变换的模拟

为了验证快速算法的可行性以及效率, 使用VB程序进行模拟。先通过逐图迭代 (算法1) 生成加密图, 再通过算法2和优化算法解密, 看是否能回到原图。

图1是使用经典Arnold变换矩阵的变换例子。 (a) 是一个200行200列的原图。使用经典Arnold二维变换22次得到 (b) , (b) 经过经典Arnold三维变换37次得到 (c) 。使用算法2对 (c) 进行经典Arnold三维变换411 (周期为448) 次返回 (b) , 再用算法2对 (b) 进行经典Arnold二维变换128次 (周期为150) 返回原图 (a) , 证明算法2和算法1效果一样, 都是正确的。按下列步骤检验优化算法, 首先计算

利用Q1对 (c) 做Arnold三维变换1次得到的图和 (b) 完全一样, 利用A1对 (b) 做Arnold二维变换1次得到的图和原图 (a) 完全一样, 证明优化算法是正确的。由于二维变换和三维变换的独立性, 可以对 (c) 利用A1进行1次Arnold二维变换得到 (d) , 再对 (d) 利用Q1做1次Arnold三维变换, 也可以返回到原图 (a) , (d) 其实就是 (a) 直接三维变换37次的结果。从 (c) 回到 (a) 使用算法2和优化算法耗时分别为4.855秒和0.042秒。

另外一方面, 我们要直接比较一下几个算法在加密端的同效性及效率。先计算:

利用A2对 (a) 做Arnold二维变换1次与使用算法1的经典Arnold变换22次结果一样, 都是图 (b) , 利用Q2对 (b) 做Arnold三维变换1次与使用算法1的经典Arnold三维变换37次结果一样, 都是 (c) 。证明了在加密端, 优化算法也是正确的。使用算法2做类似的事情也可以得到相应的结果, 算法2和优化算法耗时分别是0.539秒和0.051秒。算法2和优化算法加密和解密共耗时分别为5.394秒和0.093秒, 前者是后者的58倍, 可见效率有极大提高。

由于该二维变换周期是384, 需要做362次变换返回原图, 三维变换周期也是384, 需要再做347次变换返回原图。下面两式右边是解密时优化算法使用的矩阵。使用下面第二式右端的三维矩阵把 (c) 还原到 (b) , 再使用下面第一式右端的二维矩阵还原到 (a) 。

同时也试验了算法2, 可得到相同效果。算法2和优化算法分别耗时29.984秒和0.496秒, 两者相差60倍, 没有优化的话, 29.984秒可是很长的时间。

7 结论

研究了二维三维Arnold变换的快速算法。加解密过程把迭代各缩减为一次变换。使用VB程序进行模拟, 证明快速算法正确, 并且效率提高显著。一个尺度512的数字图像, 二维矩阵三维矩阵周期384情况下, 运算时间缩减为原来的1/60。优化算法效率和周期无关, 只和图像大小相关。快速算法使二维三维Arnold联合变换具有实际可操作性。

摘要：数字图像的每一次Arnold变换需要遍历每个像素, 由于图像是二维的, 像素个数很多, 因而每次变换都要消耗较多时间。基于Arnold变换的图像加密解密算法总共需要进行周期 (其值较大) 次数的变换, 时间的累积效应很大。研究发现, 先对变换矩阵n次乘方然后取余, 得到一个中间变换矩阵, 再使用它变换原图, 就可得到与n次原变换相同的结果。而变换矩阵的阶数远小于图像的尺度, 因而这种方法可显著提高基于Arnold变换的加解密运算速度。

关键词：Arnold变换,置乱周期,快速算法,联合变换

参考文献

[1]孙伟, 关于Arnold变换的周期性[J], 北方工业大学学报, 1999, 11 (1) :29-32

[2]单梁婷, 李敏, 何玉杰, 等, 基于Arnold变换的改进图像加密算法研究[J].计算机工程与应用:2013, 49 (11) :204-207

[3]吴玲玲, 张建伟, 葛琪, Arnold变换及其逆变换[J].微计算机信息, 2010, 26 (5-2) :206-208

[4]吴成茂, 离散Arnold变换改进及其在图像置乱加密中的应用[J].物理学报, 2014, 63 (9) :090504-01-090504-20

[5]QI D, WANG D, YANG, D, Matrix transformation of digital image and its periodicity[J].Progress in Natural Science2001, 11 (7) :542-549

[6]丁玮, 闫伟齐, 齐东旭, 基于Arnold变换的数字图像置乱技术[J].计算机辅助设计与图形学报, 2001, 13 (4) :338-341.

[7]郭琳琴, 张新荣, 基于二维Arnold变换的图像双置乱算法[J].计算机应用和软件, 2010, 27 (4) :264:266

Arnold恢复算法篇3

1 Arnold变换的定义及原理

Arnold变换(Catmapping),俗称“猫脸变换”,是V.J.Arnold在遍历理论的研究中提出的一类裁剪变换。

定义1[7]假设单位正方形上的点(x,y),将(x,y)变到另一点(x′,y′)的变换为:

此变换为二维Arnold变换。

在计算机上显示一副画面,实际上就是将构成画面的像素点上的灰度值及颜色的数值组成一个图像矩阵,即由像素点决定的二维离散点阵。这个点阵的点的坐标x和y用整数0,1,2,3…,N-1表示,运算按modN进行,这里N为数字图像矩阵的阶数。于是(1)式改写为:

因此,对图像作Arnold变换时,可以看作是图像像素位置的重新排列,这样经过Arnold变换后的图像会很混乱。如果把Arnold变换的这种性质用于图像信息的隐藏,将对隐藏图像有很好的加密效果。但Arnold变换具有周期性,对图像一直Arnold变换下去,一定会出现一幅与原图相同的图像。

利用Arnold变换对cameraman图像进行置乱的效果如图1所示。

2 三维Arnold变换极其n维推广

定义[8]如下变换称为三维变换。

(3)式中x,y,z∈{0,1,2,…,N-1},N为给定的自然数。

对于给定的正整数N,由

由归纳法可知,对(x,y,z)T进行n次Arnold变换得到

则

证毕!

由(3)式可将Arnold变换推广到n维情况。

对于给定的正整数N,下列变换称为n维Arnold变换:

其中,

由(4)式可推之对(x1,x2,…,xn-1,xn)T进行n次Arnold变换得到

3 基于图像色彩空间的三维Arnold置乱变换

一幅数字图像可用矩阵表示,其中m(i,j)表示图像在第i行第j列处象素RGB分量。在色彩空间中,将点(x,y)处像素的RGB颜色分量r,g,b进行相应变换得到点(x,y)处象素的另一组RGB颜色分量r′,g′,b′,达到图像置乱的目的。如果对一幅图像迭代使用三维Arnold变换,即可将(r′,g′,b′)T作为下一次相应变换的输入,重复这个过程一直做下去,依据Arnold变换周期性的特点就可以恢复原图像。在图像的色彩空间上进行三维置乱变换算法如下

我们对一幅256×256像素的图像在RGB色彩空间上进行三维Arnold置乱变换,如图2所示。

这种RGB色彩空间上进行三维Arnold置乱变换可以通过(6)式迭代变换,达到图像置乱效果。并且可以利用其周期性特点,来恢复原始图像。此外,三维Arnold变换作为数字图像色彩置乱的一般方法,虽然具有较好的置乱效果,但还存在明显的不足:就是对于不同位置的同一种颜色无法进行置乱。因为其r,g,b分量值是固定的,所以经过这种置乱变换(无论多少次迭代)后,这些不同位置点的颜色仍是一样的,这样就产生了原始图像(特别是颜色数比较少的图像)轮廓可见的问题。所以,针对上述问题,本文提出了一种改进算法:基于RGB色彩空间的图像置乱改进算法,该算法以图像中的行、列进行n维Arnold变换,置乱效果更好。

4 基于图像行、列的RGB色彩空间置乱算法

对于一个数字图像A,可以将它看作一个函数在矩形离散点上的函数值:A={Ai,j,i=0,1,2…,255;j=0,1,2,…,255},那么,数字图像可以表示为矩阵

以列为例,任取图像的某一列(Ai0,Ai1,…,Ai,255)T,由(5)式中n维Arnold变换的定义,做如下变换

得到一幅置乱图像。我们对图2中的原图像作基于行和列的n维Arnold变换,RGB色彩空间置乱的结果如图3所示。

显然,采用这种基于Arnold变换的置乱方法,即使是同一种颜色,只要它出现在图像的不同位置,就会生成新的颜色。这就使图像变得更加混乱,从而达到我们的要求,弥补由于RGB色彩空间的三维颜色置乱带来的不足。

5 结束语

本文通过对二维Arnold变换,三维Arnold变换及其在n维上的推广的讨论,给出了利用三维Arnold变换做数字图像色彩置乱的一般方法,分析了其存在的不足,并给出了相应的改进方法。这种改进方法,有不错的置乱效果,可以用于数字水印技术中水印图像的预处理,对水印图像的安全保护具有一定的价值。

参考文献

[1]赵学峰.基于面包师变换的数字图像置乱.西北师范大学学报,2003;39(2):26—29

[2]丁玮,齐东旭.数字图像变换及信息隐藏与伪装技术.计算机学报,1998;21(9):838—843

[3]齐东旭.矩阵变换及其在图像信息隐藏中的应用研究.北方工业大学学报,1999;11(1):24—28

[4]邹建成,李国富,齐东旭.广义Gray码及其在数字图像置乱中的应用.高校应用数学学报(A辑),2002;17(3):363—370