改進的Arnold恢復(fù)算法
2014-12-03 11:17:46馮光榮于林韜
科技資訊 2014年26期
馮光榮++于林韜
摘 要：隨著信息安全技術(shù)的發(fā)展，作為有效的圖像加密技術(shù)之一的Arnold變換，由于其周期性而被廣泛運用于圖像置亂。但是，現(xiàn)有的Arnold恢復(fù)算法，特別是對于階數(shù)較大的圖像，耗時較大。針對此情況，本文提出改進的Arnold恢復(fù)算法，綜合了周期法和逆矩陣算法的優(yōu)點。該算法將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進行比較，當(dāng)N< Period/2時，逆運算采取基于逆變換矩陣的恢復(fù)算法；當(dāng)N> Period/2時，逆運算采取基于周期的Arnold變換恢復(fù)方法。經(jīng)過Matlab7.0實驗仿真，證明了本文算法較高的運行效率。
關(guān)鍵詞：Arnold 周期法 逆矩陣法 Arnold恢復(fù)算法
中圖分類號：TN911 文獻標(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ù)字圖像已達到保密的目的。其具體操作就是對數(shù)字圖像不斷地進行迭代Arnold變換，經(jīng)過一定次數(shù)的變換后會有一個臨界迭代次數(shù)，在此次數(shù)下變換后的圖像會呈雜亂無章狀，毫無規(guī)律可言。如此，便可以將圖像進行簡單的加密[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ù)算法有兩種方式：基于周期的運算方式和基于反變換的運算方式。一般數(shù)字圖像需要進行多次置亂才可以達到滿意的效果，經(jīng)過n次Arnold置亂的公式為4：
對于數(shù)字圖像的置亂都是有周期的，且周期隨著圖像階數(shù)不同而不同。當(dāng)置亂到一定次數(shù)時，又會從置亂圖像恢復(fù)到原圖。加密技術(shù)中也就是利用了Arnold變換的周期性對數(shù)字圖像進行加解密。將圖像置亂的次數(shù)作為Key，用以解密。當(dāng)原圖將經(jīng)過n次Arnold置亂，則需要對圖像繼續(xù)進行次置亂才能得以恢復(fù)。數(shù)字圖像的Arnold變換周期如表4所示。
由于數(shù)字圖像水印算法本身具有一定的復(fù)雜度，所以應(yīng)盡量減少各組成部分的復(fù)雜度，對此應(yīng)該尋求一種簡單快捷的Arnold逆運算方法，對此可以參考[8]中的方法直接利用Arnold變換矩陣的逆矩陣直接迭代相同步數(shù)即可求得原圖像，這樣就可以節(jié)省不少時間。例如，對原圖進行m次Arnold置亂，則需要其進行m次逆運算即可恢復(fù)原圖，其計算公式如5。
3 改進的Arnold恢復(fù)算法
由已證明定理[9]可知，基于逆矩陣的Arnold恢復(fù)算法也可以寫成如式6：
但是在數(shù)字圖像的背景下需要滿足以下條件：
則可得到，由不等式的性質(zhì)可進一步得到k=0、1。
故此，編程中令，當(dāng)時，取；當(dāng)時，取 。同理對y進行設(shè)置。
Arnold恢復(fù)算法一般會采取周期法和逆矩陣變換法。周期法原理簡單，但是其Arnold算法本身計算量大，既復(fù)雜又耗時；逆矩陣法雖然簡單、無需檢測Arnold周期，但是其計算量大，耗時長。所以，本文提出了一種簡單快捷高效的Arnold逆運算方法，綜合了兩種算法的優(yōu)點。算法中將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進行比較，當(dāng)N
4 改進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ù)可知，本文提出的改進Arnold恢復(fù)算法在效率方面有很大的優(yōu)勢，在大圖像的Arnold置亂恢復(fù)上尤其明顯。該改進算法通過比較圖像Arnold變換次數(shù)與Period/2的關(guān)系來決定恢復(fù)算法的選擇，進而用最少的時間恢復(fù)出原圖像，提高了恢復(fù)算法的有效率。
參考文獻
[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].計算機應(yīng)用，2013，33（8）：2240-2243.
[3] 張穎，楊玥.Arnold雙置亂圖像加密算法[J].遼寧工程技術(shù)大學(xué)學(xué)報：自然科學(xué)版，2013，32（10）：1429-1432.
[4] 吳玲玲，張建偉，葛琪.Arnold變換及其逆變換[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].計算機應(yīng)用與軟件，2010，27（9）：265-267.
摘 要：隨著信息安全技術(shù)的發(fā)展，作為有效的圖像加密技術(shù)之一的Arnold變換，由于其周期性而被廣泛運用于圖像置亂。但是，現(xiàn)有的Arnold恢復(fù)算法，特別是對于階數(shù)較大的圖像，耗時較大。針對此情況，本文提出改進的Arnold恢復(fù)算法，綜合了周期法和逆矩陣算法的優(yōu)點。該算法將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進行比較，當(dāng)N< Period/2時，逆運算采取基于逆變換矩陣的恢復(fù)算法；當(dāng)N> Period/2時，逆運算采取基于周期的Arnold變換恢復(fù)方法。經(jīng)過Matlab7.0實驗仿真，證明了本文算法較高的運行效率。
關(guān)鍵詞：Arnold 周期法 逆矩陣法 Arnold恢復(fù)算法
中圖分類號：TN911 文獻標(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ù)字圖像已達到保密的目的。其具體操作就是對數(shù)字圖像不斷地進行迭代Arnold變換，經(jīng)過一定次數(shù)的變換后會有一個臨界迭代次數(shù)，在此次數(shù)下變換后的圖像會呈雜亂無章狀，毫無規(guī)律可言。如此，便可以將圖像進行簡單的加密[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ù)算法有兩種方式：基于周期的運算方式和基于反變換的運算方式。一般數(shù)字圖像需要進行多次置亂才可以達到滿意的效果，經(jīng)過n次Arnold置亂的公式為4：
對于數(shù)字圖像的置亂都是有周期的，且周期隨著圖像階數(shù)不同而不同。當(dāng)置亂到一定次數(shù)時，又會從置亂圖像恢復(fù)到原圖。加密技術(shù)中也就是利用了Arnold變換的周期性對數(shù)字圖像進行加解密。將圖像置亂的次數(shù)作為Key，用以解密。當(dāng)原圖將經(jīng)過n次Arnold置亂，則需要對圖像繼續(xù)進行次置亂才能得以恢復(fù)。數(shù)字圖像的Arnold變換周期如表4所示。
由于數(shù)字圖像水印算法本身具有一定的復(fù)雜度，所以應(yīng)盡量減少各組成部分的復(fù)雜度，對此應(yīng)該尋求一種簡單快捷的Arnold逆運算方法，對此可以參考[8]中的方法直接利用Arnold變換矩陣的逆矩陣直接迭代相同步數(shù)即可求得原圖像，這樣就可以節(jié)省不少時間。例如，對原圖進行m次Arnold置亂，則需要其進行m次逆運算即可恢復(fù)原圖，其計算公式如5。
3 改進的Arnold恢復(fù)算法
由已證明定理[9]可知，基于逆矩陣的Arnold恢復(fù)算法也可以寫成如式6：
但是在數(shù)字圖像的背景下需要滿足以下條件：
則可得到，由不等式的性質(zhì)可進一步得到k=0、1。
故此，編程中令，當(dāng)時，?。划?dāng)時，取 。同理對y進行設(shè)置。
Arnold恢復(fù)算法一般會采取周期法和逆矩陣變換法。周期法原理簡單，但是其Arnold算法本身計算量大，既復(fù)雜又耗時；逆矩陣法雖然簡單、無需檢測Arnold周期，但是其計算量大，耗時長。所以，本文提出了一種簡單快捷高效的Arnold逆運算方法，綜合了兩種算法的優(yōu)點。算法中將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進行比較，當(dāng)N
4 改進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ù)可知，本文提出的改進Arnold恢復(fù)算法在效率方面有很大的優(yōu)勢，在大圖像的Arnold置亂恢復(fù)上尤其明顯。該改進算法通過比較圖像Arnold變換次數(shù)與Period/2的關(guān)系來決定恢復(fù)算法的選擇，進而用最少的時間恢復(fù)出原圖像，提高了恢復(fù)算法的有效率。
參考文獻
[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].計算機應(yīng)用，2013，33（8）：2240-2243.
[3] 張穎，楊玥.Arnold雙置亂圖像加密算法[J].遼寧工程技術(shù)大學(xué)學(xué)報：自然科學(xué)版，2013，32（10）：1429-1432.
[4] 吳玲玲，張建偉，葛琪.Arnold變換及其逆變換[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].計算機應(yīng)用與軟件，2010，27（9）：265-267.
摘 要：隨著信息安全技術(shù)的發(fā)展，作為有效的圖像加密技術(shù)之一的Arnold變換，由于其周期性而被廣泛運用于圖像置亂。但是，現(xiàn)有的Arnold恢復(fù)算法，特別是對于階數(shù)較大的圖像，耗時較大。針對此情況，本文提出改進的Arnold恢復(fù)算法，綜合了周期法和逆矩陣算法的優(yōu)點。該算法將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進行比較，當(dāng)N< Period/2時，逆運算采取基于逆變換矩陣的恢復(fù)算法；當(dāng)N> Period/2時，逆運算采取基于周期的Arnold變換恢復(fù)方法。經(jīng)過Matlab7.0實驗仿真，證明了本文算法較高的運行效率。
關(guān)鍵詞：Arnold 周期法 逆矩陣法 Arnold恢復(fù)算法
中圖分類號：TN911 文獻標(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ù)字圖像已達到保密的目的。其具體操作就是對數(shù)字圖像不斷地進行迭代Arnold變換，經(jīng)過一定次數(shù)的變換后會有一個臨界迭代次數(shù)，在此次數(shù)下變換后的圖像會呈雜亂無章狀，毫無規(guī)律可言。如此，便可以將圖像進行簡單的加密[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ù)算法有兩種方式：基于周期的運算方式和基于反變換的運算方式。一般數(shù)字圖像需要進行多次置亂才可以達到滿意的效果，經(jīng)過n次Arnold置亂的公式為4：
對于數(shù)字圖像的置亂都是有周期的，且周期隨著圖像階數(shù)不同而不同。當(dāng)置亂到一定次數(shù)時，又會從置亂圖像恢復(fù)到原圖。加密技術(shù)中也就是利用了Arnold變換的周期性對數(shù)字圖像進行加解密。將圖像置亂的次數(shù)作為Key，用以解密。當(dāng)原圖將經(jīng)過n次Arnold置亂，則需要對圖像繼續(xù)進行次置亂才能得以恢復(fù)。數(shù)字圖像的Arnold變換周期如表4所示。
由于數(shù)字圖像水印算法本身具有一定的復(fù)雜度，所以應(yīng)盡量減少各組成部分的復(fù)雜度，對此應(yīng)該尋求一種簡單快捷的Arnold逆運算方法，對此可以參考[8]中的方法直接利用Arnold變換矩陣的逆矩陣直接迭代相同步數(shù)即可求得原圖像，這樣就可以節(jié)省不少時間。例如，對原圖進行m次Arnold置亂，則需要其進行m次逆運算即可恢復(fù)原圖，其計算公式如5。
3 改進的Arnold恢復(fù)算法
由已證明定理[9]可知，基于逆矩陣的Arnold恢復(fù)算法也可以寫成如式6：
但是在數(shù)字圖像的背景下需要滿足以下條件：
則可得到，由不等式的性質(zhì)可進一步得到k=0、1。
故此，編程中令，當(dāng)時，??；當(dāng)時，取 。同理對y進行設(shè)置。
Arnold恢復(fù)算法一般會采取周期法和逆矩陣變換法。周期法原理簡單，但是其Arnold算法本身計算量大，既復(fù)雜又耗時；逆矩陣法雖然簡單、無需檢測Arnold周期，但是其計算量大，耗時長。所以，本文提出了一種簡單快捷高效的Arnold逆運算方法，綜合了兩種算法的優(yōu)點。算法中將兩種算法相結(jié)合，先求取圖像的Arnold變換周期Period，然后將Arnold變換次數(shù)N與Period/2進行比較，當(dāng)N
4 改進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ù)可知，本文提出的改進Arnold恢復(fù)算法在效率方面有很大的優(yōu)勢，在大圖像的Arnold置亂恢復(fù)上尤其明顯。該改進算法通過比較圖像Arnold變換次數(shù)與Period/2的關(guān)系來決定恢復(fù)算法的選擇，進而用最少的時間恢復(fù)出原圖像，提高了恢復(fù)算法的有效率。
參考文獻
[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].計算機應(yīng)用，2013，33（8）：2240-2243.
[3] 張穎，楊玥.Arnold雙置亂圖像加密算法[J].遼寧工程技術(shù)大學(xué)學(xué)報：自然科學(xué)版，2013，32（10）：1429-1432.
[4] 吳玲玲，張建偉，葛琪.Arnold變換及其逆變換[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].計算機應(yīng)用與軟件，2010，27（9）：265-267.
