改進(jìn)的Arnold恢復(fù)算法

馮光榮++于林韜

摘 要：隨著信息安全技術(shù)的發(fā)展，作為有效的圖像加密技術(shù)之一的Arnold變換，由于其周期性而被廣泛運(yùn)用于圖像置亂。但是，現(xiàn)有的Arnold恢復(fù)算法，特別是對于階數(shù)較大的圖像，耗時較大。針對此情況，本文提出改進(jìn)的Arnold恢復(fù)算法，綜合了周期法和逆矩陣算法的優(yōu)點。該算法將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進(jìn)行比較，當(dāng)N< Period/2時，逆運(yùn)算采取基于逆變換矩陣的恢復(fù)算法；當(dāng)N> Period/2時，逆運(yùn)算采取基于周期的Arnold變換恢復(fù)方法。經(jīng)過Matlab7.0實驗仿真，證明了本文算法較高的運(yùn)行效率。

關(guān)鍵詞：Arnold 周期法 逆矩陣法 Arnold恢復(fù)算法

中圖分類號：TN911 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2014）09（b）-0019-02

1 Arnold變換定義

Arnold變換最早是由V.I.Arnold1]等提出的一種圖像變換算法，又稱貓臉變換（cat mapping）。

貓臉變換核心在于變換矩陣，其定義為：設(shè)平面單位正方形內(nèi)的任一點為，對其作特定的變換[2][3]如式1。

Arnold變換主要應(yīng)用于數(shù)字圖像相關(guān)技術(shù)領(lǐng)域中，用以置亂數(shù)字圖像已達(dá)到保密的目的。其具體操作就是對數(shù)字圖像不斷地進(jìn)行迭代Arnold變換，經(jīng)過一定次數(shù)的變換后會有一個臨界迭代次數(shù)，在此次數(shù)下變換后的圖像會呈雜亂無章狀，毫無規(guī)律可言。如此，便可以將圖像進(jìn)行簡單的加密[4][5]。Arnold變換在數(shù)字圖像中的二維變換公式如2：

其中分別為數(shù)字圖像內(nèi)的點和變換后的點，N是數(shù)字圖像的階數(shù)。

以上只是標(biāo)準(zhǔn)的二維Arnold變換表示形式。從矩陣形式上看，一般的Arnold變換矩陣[6][7]如3：

2 Arnold變換的恢復(fù)算法

數(shù)字圖像應(yīng)用中的Arnold變換的恢復(fù)算法有兩種方式：基于周期的運(yùn)算方式和基于反變換的運(yùn)算方式。一般數(shù)字圖像需要進(jìn)行多次置亂才可以達(dá)到滿意的效果，經(jīng)過n次Arnold置亂的公式為4：

對于數(shù)字圖像的置亂都是有周期的，且周期隨著圖像階數(shù)不同而不同。當(dāng)置亂到一定次數(shù)時，又會從置亂圖像恢復(fù)到原圖。加密技術(shù)中也就是利用了Arnold變換的周期性對數(shù)字圖像進(jìn)行加解密。將圖像置亂的次數(shù)作為Key，用以解密。當(dāng)原圖將經(jīng)過n次Arnold置亂，則需要對圖像繼續(xù)進(jìn)行次置亂才能得以恢復(fù)。數(shù)字圖像的Arnold變換周期如表4所示。

由于數(shù)字圖像水印算法本身具有一定的復(fù)雜度，所以應(yīng)盡量減少各組成部分的復(fù)雜度，對此應(yīng)該尋求一種簡單快捷的Arnold逆運(yùn)算方法，對此可以參考[8]中的方法直接利用Arnold變換矩陣的逆矩陣直接迭代相同步數(shù)即可求得原圖像，這樣就可以節(jié)省不少時間。例如，對原圖進(jìn)行m次Arnold置亂，則需要其進(jìn)行m次逆運(yùn)算即可恢復(fù)原圖，其計算公式如5。

3 改進(jìn)的Arnold恢復(fù)算法

由已證明定理[9]可知，基于逆矩陣的Arnold恢復(fù)算法也可以寫成如式6：

但是在數(shù)字圖像的背景下需要滿足以下條件：

則可得到，由不等式的性質(zhì)可進(jìn)一步得到k=0、1。

故此，編程中令，當(dāng)時，取；當(dāng)時，取 。同理對y進(jìn)行設(shè)置。

Arnold恢復(fù)算法一般會采取周期法和逆矩陣變換法。周期法原理簡單，但是其Arnold算法本身計算量大，既復(fù)雜又耗時；逆矩陣法雖然簡單、無需檢測Arnold周期，但是其計算量大，耗時長。所以，本文提出了一種簡單快捷高效的Arnold逆運(yùn)算方法，綜合了兩種算法的優(yōu)點。算法中將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進(jìn)行比較，當(dāng)N Period/2時，逆運(yùn)算采取基于周期的Arnold變換恢復(fù)方法。通過此方法，大大提高了Arnold恢復(fù)算法的運(yùn)行效率。

4 改進(jìn)Arnold恢復(fù)算法的Matlab仿真結(jié)果

本文分別選取32×32的圖像Lena1、64×64的圖像shuiyin、128×128的圖像shuiyin1、256×256的圖像Lena2和512×512的圖像Lena作為實驗圖像，通過matlab仿真得到數(shù)據(jù)表如表2（a）、表2（b）、表2（c）。

由實驗數(shù)據(jù)可知，本文提出的改進(jìn)Arnold恢復(fù)算法在效率方面有很大的優(yōu)勢，在大圖像的Arnold置亂恢復(fù)上尤其明顯。該改進(jìn)算法通過比較圖像Arnold變換次數(shù)與Period/2的關(guān)系來決定恢復(fù)算法的選擇，進(jìn)而用最少的時間恢復(fù)出原圖像，提高了恢復(fù)算法的有效率。

參考文獻(xiàn)

[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].計算機(jī)應(yīng)用，2013，33（8）：2240-2243.

[3] 張穎，楊玥.Arnold雙置亂圖像加密算法[J].遼寧工程技術(shù)大學(xué)學(xué)報：自然科學(xué)版，2013，32（10）：1429-1432.

[4] 吳玲玲，張建偉，葛琪.Arnold變換及其逆變換[J].微計算機(jī)信息：嵌入式與 SOCT，2010，26（5-2）：206-208.

[5] 毛雷波.Arnold變換及其逆變換研究[J].重慶工程大學(xué)學(xué)報：自然科學(xué)版，2012，29（3）：16-21.

[6] 田云凱，賈傳熒，王慶武.基于Arnold變換的圖像置亂及其恢復(fù)[J].大連海事大學(xué)學(xué)報，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].電視技術(shù)，2012，36（3）：17-19.

[9] 郭琳琴，張新榮，李震.基于Arnold逆變換的圖像置亂恢復(fù)算法[J].計算機(jī)應(yīng)用與軟件，2010，27（9）：265-267.

摘 要：隨著信息安全技術(shù)的發(fā)展，作為有效的圖像加密技術(shù)之一的Arnold變換，由于其周期性而被廣泛運(yùn)用于圖像置亂。但是，現(xiàn)有的Arnold恢復(fù)算法，特別是對于階數(shù)較大的圖像，耗時較大。針對此情況，本文提出改進(jìn)的Arnold恢復(fù)算法，綜合了周期法和逆矩陣算法的優(yōu)點。該算法將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進(jìn)行比較，當(dāng)N< Period/2時，逆運(yùn)算采取基于逆變換矩陣的恢復(fù)算法；當(dāng)N> Period/2時，逆運(yùn)算采取基于周期的Arnold變換恢復(fù)方法。經(jīng)過Matlab7.0實驗仿真，證明了本文算法較高的運(yùn)行效率。

關(guān)鍵詞：Arnold 周期法 逆矩陣法 Arnold恢復(fù)算法

中圖分類號：TN911 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2014）09（b）-0019-02

1 Arnold變換定義

Arnold變換最早是由V.I.Arnold1]等提出的一種圖像變換算法，又稱貓臉變換（cat mapping）。

貓臉變換核心在于變換矩陣，其定義為：設(shè)平面單位正方形內(nèi)的任一點為，對其作特定的變換[2][3]如式1。

Arnold變換主要應(yīng)用于數(shù)字圖像相關(guān)技術(shù)領(lǐng)域中，用以置亂數(shù)字圖像已達(dá)到保密的目的。其具體操作就是對數(shù)字圖像不斷地進(jìn)行迭代Arnold變換，經(jīng)過一定次數(shù)的變換后會有一個臨界迭代次數(shù)，在此次數(shù)下變換后的圖像會呈雜亂無章狀，毫無規(guī)律可言。如此，便可以將圖像進(jìn)行簡單的加密[4][5]。Arnold變換在數(shù)字圖像中的二維變換公式如2：

其中分別為數(shù)字圖像內(nèi)的點和變換后的點，N是數(shù)字圖像的階數(shù)。

以上只是標(biāo)準(zhǔn)的二維Arnold變換表示形式。從矩陣形式上看，一般的Arnold變換矩陣[6][7]如3：

2 Arnold變換的恢復(fù)算法

數(shù)字圖像應(yīng)用中的Arnold變換的恢復(fù)算法有兩種方式：基于周期的運(yùn)算方式和基于反變換的運(yùn)算方式。一般數(shù)字圖像需要進(jìn)行多次置亂才可以達(dá)到滿意的效果，經(jīng)過n次Arnold置亂的公式為4：

對于數(shù)字圖像的置亂都是有周期的，且周期隨著圖像階數(shù)不同而不同。當(dāng)置亂到一定次數(shù)時，又會從置亂圖像恢復(fù)到原圖。加密技術(shù)中也就是利用了Arnold變換的周期性對數(shù)字圖像進(jìn)行加解密。將圖像置亂的次數(shù)作為Key，用以解密。當(dāng)原圖將經(jīng)過n次Arnold置亂，則需要對圖像繼續(xù)進(jìn)行次置亂才能得以恢復(fù)。數(shù)字圖像的Arnold變換周期如表4所示。

由于數(shù)字圖像水印算法本身具有一定的復(fù)雜度，所以應(yīng)盡量減少各組成部分的復(fù)雜度，對此應(yīng)該尋求一種簡單快捷的Arnold逆運(yùn)算方法，對此可以參考[8]中的方法直接利用Arnold變換矩陣的逆矩陣直接迭代相同步數(shù)即可求得原圖像，這樣就可以節(jié)省不少時間。例如，對原圖進(jìn)行m次Arnold置亂，則需要其進(jìn)行m次逆運(yùn)算即可恢復(fù)原圖，其計算公式如5。

3 改進(jìn)的Arnold恢復(fù)算法

由已證明定理[9]可知，基于逆矩陣的Arnold恢復(fù)算法也可以寫成如式6：

但是在數(shù)字圖像的背景下需要滿足以下條件：

則可得到，由不等式的性質(zhì)可進(jìn)一步得到k=0、1。

故此，編程中令，當(dāng)時，取；當(dāng)時，取 。同理對y進(jìn)行設(shè)置。

Arnold恢復(fù)算法一般會采取周期法和逆矩陣變換法。周期法原理簡單，但是其Arnold算法本身計算量大，既復(fù)雜又耗時；逆矩陣法雖然簡單、無需檢測Arnold周期，但是其計算量大，耗時長。所以，本文提出了一種簡單快捷高效的Arnold逆運(yùn)算方法，綜合了兩種算法的優(yōu)點。算法中將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進(jìn)行比較，當(dāng)N Period/2時，逆運(yùn)算采取基于周期的Arnold變換恢復(fù)方法。通過此方法，大大提高了Arnold恢復(fù)算法的運(yùn)行效率。

4 改進(jìn)Arnold恢復(fù)算法的Matlab仿真結(jié)果

本文分別選取32×32的圖像Lena1、64×64的圖像shuiyin、128×128的圖像shuiyin1、256×256的圖像Lena2和512×512的圖像Lena作為實驗圖像，通過matlab仿真得到數(shù)據(jù)表如表2（a）、表2（b）、表2（c）。

由實驗數(shù)據(jù)可知，本文提出的改進(jìn)Arnold恢復(fù)算法在效率方面有很大的優(yōu)勢，在大圖像的Arnold置亂恢復(fù)上尤其明顯。該改進(jìn)算法通過比較圖像Arnold變換次數(shù)與Period/2的關(guān)系來決定恢復(fù)算法的選擇，進(jìn)而用最少的時間恢復(fù)出原圖像，提高了恢復(fù)算法的有效率。

參考文獻(xiàn)

[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].計算機(jī)應(yīng)用，2013，33（8）：2240-2243.

[3] 張穎，楊玥.Arnold雙置亂圖像加密算法[J].遼寧工程技術(shù)大學(xué)學(xué)報：自然科學(xué)版，2013，32（10）：1429-1432.

[4] 吳玲玲，張建偉，葛琪.Arnold變換及其逆變換[J].微計算機(jī)信息：嵌入式與 SOCT，2010，26（5-2）：206-208.

[5] 毛雷波.Arnold變換及其逆變換研究[J].重慶工程大學(xué)學(xué)報：自然科學(xué)版，2012，29（3）：16-21.

[6] 田云凱，賈傳熒，王慶武.基于Arnold變換的圖像置亂及其恢復(fù)[J].大連海事大學(xué)學(xué)報，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].電視技術(shù)，2012，36（3）：17-19.

[9] 郭琳琴，張新榮，李震.基于Arnold逆變換的圖像置亂恢復(fù)算法[J].計算機(jī)應(yīng)用與軟件，2010，27（9）：265-267.

摘 要：隨著信息安全技術(shù)的發(fā)展，作為有效的圖像加密技術(shù)之一的Arnold變換，由于其周期性而被廣泛運(yùn)用于圖像置亂。但是，現(xiàn)有的Arnold恢復(fù)算法，特別是對于階數(shù)較大的圖像，耗時較大。針對此情況，本文提出改進(jìn)的Arnold恢復(fù)算法，綜合了周期法和逆矩陣算法的優(yōu)點。該算法將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進(jìn)行比較，當(dāng)N< Period/2時，逆運(yùn)算采取基于逆變換矩陣的恢復(fù)算法；當(dāng)N> Period/2時，逆運(yùn)算采取基于周期的Arnold變換恢復(fù)方法。經(jīng)過Matlab7.0實驗仿真，證明了本文算法較高的運(yùn)行效率。

關(guān)鍵詞：Arnold 周期法 逆矩陣法 Arnold恢復(fù)算法

中圖分類號：TN911 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2014）09（b）-0019-02

1 Arnold變換定義

Arnold變換最早是由V.I.Arnold1]等提出的一種圖像變換算法，又稱貓臉變換（cat mapping）。

貓臉變換核心在于變換矩陣，其定義為：設(shè)平面單位正方形內(nèi)的任一點為，對其作特定的變換[2][3]如式1。

Arnold變換主要應(yīng)用于數(shù)字圖像相關(guān)技術(shù)領(lǐng)域中，用以置亂數(shù)字圖像已達(dá)到保密的目的。其具體操作就是對數(shù)字圖像不斷地進(jìn)行迭代Arnold變換，經(jīng)過一定次數(shù)的變換后會有一個臨界迭代次數(shù)，在此次數(shù)下變換后的圖像會呈雜亂無章狀，毫無規(guī)律可言。如此，便可以將圖像進(jìn)行簡單的加密[4][5]。Arnold變換在數(shù)字圖像中的二維變換公式如2：

其中分別為數(shù)字圖像內(nèi)的點和變換后的點，N是數(shù)字圖像的階數(shù)。

以上只是標(biāo)準(zhǔn)的二維Arnold變換表示形式。從矩陣形式上看，一般的Arnold變換矩陣[6][7]如3：

2 Arnold變換的恢復(fù)算法

數(shù)字圖像應(yīng)用中的Arnold變換的恢復(fù)算法有兩種方式：基于周期的運(yùn)算方式和基于反變換的運(yùn)算方式。一般數(shù)字圖像需要進(jìn)行多次置亂才可以達(dá)到滿意的效果，經(jīng)過n次Arnold置亂的公式為4：

對于數(shù)字圖像的置亂都是有周期的，且周期隨著圖像階數(shù)不同而不同。當(dāng)置亂到一定次數(shù)時，又會從置亂圖像恢復(fù)到原圖。加密技術(shù)中也就是利用了Arnold變換的周期性對數(shù)字圖像進(jìn)行加解密。將圖像置亂的次數(shù)作為Key，用以解密。當(dāng)原圖將經(jīng)過n次Arnold置亂，則需要對圖像繼續(xù)進(jìn)行次置亂才能得以恢復(fù)。數(shù)字圖像的Arnold變換周期如表4所示。

由于數(shù)字圖像水印算法本身具有一定的復(fù)雜度，所以應(yīng)盡量減少各組成部分的復(fù)雜度，對此應(yīng)該尋求一種簡單快捷的Arnold逆運(yùn)算方法，對此可以參考[8]中的方法直接利用Arnold變換矩陣的逆矩陣直接迭代相同步數(shù)即可求得原圖像，這樣就可以節(jié)省不少時間。例如，對原圖進(jìn)行m次Arnold置亂，則需要其進(jìn)行m次逆運(yùn)算即可恢復(fù)原圖，其計算公式如5。

3 改進(jìn)的Arnold恢復(fù)算法

由已證明定理[9]可知，基于逆矩陣的Arnold恢復(fù)算法也可以寫成如式6：

但是在數(shù)字圖像的背景下需要滿足以下條件：

則可得到，由不等式的性質(zhì)可進(jìn)一步得到k=0、1。

故此，編程中令，當(dāng)時，取；當(dāng)時，取 。同理對y進(jìn)行設(shè)置。

Arnold恢復(fù)算法一般會采取周期法和逆矩陣變換法。周期法原理簡單，但是其Arnold算法本身計算量大，既復(fù)雜又耗時；逆矩陣法雖然簡單、無需檢測Arnold周期，但是其計算量大，耗時長。所以，本文提出了一種簡單快捷高效的Arnold逆運(yùn)算方法，綜合了兩種算法的優(yōu)點。算法中將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進(jìn)行比較，當(dāng)N Period/2時，逆運(yùn)算采取基于周期的Arnold變換恢復(fù)方法。通過此方法，大大提高了Arnold恢復(fù)算法的運(yùn)行效率。

4 改進(jìn)Arnold恢復(fù)算法的Matlab仿真結(jié)果

本文分別選取32×32的圖像Lena1、64×64的圖像shuiyin、128×128的圖像shuiyin1、256×256的圖像Lena2和512×512的圖像Lena作為實驗圖像，通過matlab仿真得到數(shù)據(jù)表如表2（a）、表2（b）、表2（c）。

由實驗數(shù)據(jù)可知，本文提出的改進(jìn)Arnold恢復(fù)算法在效率方面有很大的優(yōu)勢，在大圖像的Arnold置亂恢復(fù)上尤其明顯。該改進(jìn)算法通過比較圖像Arnold變換次數(shù)與Period/2的關(guān)系來決定恢復(fù)算法的選擇，進(jìn)而用最少的時間恢復(fù)出原圖像，提高了恢復(fù)算法的有效率。

參考文獻(xiàn)

[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].計算機(jī)應(yīng)用，2013，33（8）：2240-2243.

[3] 張穎，楊玥.Arnold雙置亂圖像加密算法[J].遼寧工程技術(shù)大學(xué)學(xué)報：自然科學(xué)版，2013，32（10）：1429-1432.

[4] 吳玲玲，張建偉，葛琪.Arnold變換及其逆變換[J].微計算機(jī)信息：嵌入式與 SOCT，2010，26（5-2）：206-208.

[5] 毛雷波.Arnold變換及其逆變換研究[J].重慶工程大學(xué)學(xué)報：自然科學(xué)版，2012，29（3）：16-21.

[6] 田云凱，賈傳熒，王慶武.基于Arnold變換的圖像置亂及其恢復(fù)[J].大連海事大學(xué)學(xué)報，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].電視技術(shù)，2012，36（3）：17-19.

[9] 郭琳琴，張新榮，李震.基于Arnold逆變換的圖像置亂恢復(fù)算法[J].計算機(jī)應(yīng)用與軟件，2010，27（9）：265-267.