改进的Arnold恢复算法

冯光荣++于林韬

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

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

中图分类号：TN911 文献标识码：A 文章编号：1672-3791（2014）09（b）-0019-02

1 Arnold变换定义

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

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

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

其中分别为数字图像内的点和变换后的点，N是数字图像的阶数。

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

2 Arnold变换的恢复算法

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

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

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

3 改进的Arnold恢复算法

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

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

则可得到，由不等式的性质可进一步得到k=0、1。

故此，编程中令，当时，取；当时，取 。同理对y进行设置。

Arnold恢复算法一般会采取周期法和逆矩阵变换法。周期法原理简单，但是其Arnold算法本身计算量大，既复杂又耗时；逆矩阵法虽然简单、无需检测Arnold周期，但是其计算量大，耗时长。所以，本文提出了一种简单快捷高效的Arnold逆运算方法，综合了两种算法的优点。算法中将两种算法相结合，先求取图像的Arnold变换周期Period，然后将Arnold变换次数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变换，由于其周期性而被广泛运用于图像置乱。但是，现有的Arnold恢复算法，特别是对于阶数较大的图像，耗时较大。针对此情况，本文提出改进的Arnold恢复算法，综合了周期法和逆矩阵算法的优点。该算法将两种算法相结合，先求取图像的Arnold变换周期Period，然后将Arnold变换次数N与Period/2进行比较，当N< Period/2时，逆运算采取基于逆变换矩阵的恢复算法；当N> Period/2时，逆运算采取基于周期的Arnold变换恢复方法。经过Matlab7.0实验仿真，证明了本文算法较高的运行效率。

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

中图分类号：TN911 文献标识码：A 文章编号：1672-3791（2014）09（b）-0019-02

1 Arnold变换定义

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

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

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

其中分别为数字图像内的点和变换后的点，N是数字图像的阶数。

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

2 Arnold变换的恢复算法

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

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

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

3 改进的Arnold恢复算法

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

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

则可得到，由不等式的性质可进一步得到k=0、1。

故此，编程中令，当时，取；当时，取 。同理对y进行设置。

Arnold恢复算法一般会采取周期法和逆矩阵变换法。周期法原理简单，但是其Arnold算法本身计算量大，既复杂又耗时；逆矩阵法虽然简单、无需检测Arnold周期，但是其计算量大，耗时长。所以，本文提出了一种简单快捷高效的Arnold逆运算方法，综合了两种算法的优点。算法中将两种算法相结合，先求取图像的Arnold变换周期Period，然后将Arnold变换次数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变换，由于其周期性而被广泛运用于图像置乱。但是，现有的Arnold恢复算法，特别是对于阶数较大的图像，耗时较大。针对此情况，本文提出改进的Arnold恢复算法，综合了周期法和逆矩阵算法的优点。该算法将两种算法相结合，先求取图像的Arnold变换周期Period，然后将Arnold变换次数N与Period/2进行比较，当N< Period/2时，逆运算采取基于逆变换矩阵的恢复算法；当N> Period/2时，逆运算采取基于周期的Arnold变换恢复方法。经过Matlab7.0实验仿真，证明了本文算法较高的运行效率。

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

中图分类号：TN911 文献标识码：A 文章编号：1672-3791（2014）09（b）-0019-02

1 Arnold变换定义

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

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

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

其中分别为数字图像内的点和变换后的点，N是数字图像的阶数。

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

2 Arnold变换的恢复算法

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

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

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

3 改进的Arnold恢复算法

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

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

则可得到，由不等式的性质可进一步得到k=0、1。

故此，编程中令，当时，取；当时，取 。同理对y进行设置。

Arnold恢复算法一般会采取周期法和逆矩阵变换法。周期法原理简单，但是其Arnold算法本身计算量大，既复杂又耗时；逆矩阵法虽然简单、无需检测Arnold周期，但是其计算量大，耗时长。所以，本文提出了一种简单快捷高效的Arnold逆运算方法，综合了两种算法的优点。算法中将两种算法相结合，先求取图像的Arnold变换周期Period，然后将Arnold变换次数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.