基于arnold變換的非正方形圖像置亂算法-畢業(yè)論文

1、<p>　　基于Arnold變換的非正方形圖像</p><p><b>　　置亂算法</b></p><p>　　(Scrambling algorithm for rectangle-Image </p><p>　　based on Arnold transforms)</p><p><b>　

2、　呂梁學院數(shù)學系</b></p><p><b>　　2012年2月</b></p><p><b>　　摘 要</b></p><p>　　隨著網(wǎng)絡技術的發(fā)展，數(shù)字圖像的傳輸安全問題受到了越來越多的重視，圖像置亂作為信息隱藏的手段得到了廣泛的應用。</p><p>　　在眾多圖像置

3、亂算法中，Arnold變換置亂算法由于其簡單、易于理解和實現(xiàn)，而得到了很好的應用，但二維Arnold變換一般只適用于等長圖像，而當圖像的長寬不等時，該變換過程不具有一一映射。</p><p>　　文中對現(xiàn)有的非正方形圖像置亂技術進行了分析，在此基礎上給出了一種新的將二維Arnold變換應用于非正方形圖像的方法，該算法首先將非正方形圖像依據(jù)較短邊長劃分為多個有重合區(qū)域的正方形塊，然后采取從左到右的順序分別對每個區(qū)域

4、塊進行二維Arnold變換的置亂方式，從而完成對全圖的置亂。置亂中正方形區(qū)域的劃分辦法綜合考慮到置亂結果區(qū)域性和計算量問題，選取塊間重合區(qū)域大小接近于原圖較短邊長的1/2。本算法適用于任意長方形圖像，置亂恢復過程采用逆變換方法。</p><p>　　實驗結果表明，該算法簡單，安全，有效，在少量的置亂迭代次數(shù)下即可達到較好的置亂效果。</p><p>　　關鍵詞 Arnold變換 非正方

5、形 圖像置亂</p><p><b>　　Abstract</b></p><p>　　Arnold transform has wide range of applications in the image scrambling. Analysis of Arnold transformation matrix in image scrambling applic

6、ations, 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 overl

7、apping area, and then from left to right order to scramble each block with Arnold transformation. Experimental results show that the algori</p><p>　　Key words： Arnold transform; Rectangle-Image; Image Scram

8、bling </p><p><b>　　第一章 緒論</b></p><p>　　圖像作為人類認識和表達世界的基本方法，應用極為廣泛，從古老的壁畫、象形文字到今天的數(shù)字化圖像，圖像一直伴隨著人類歷史的發(fā)展，人們也期望從圖像中得到直觀的信息，“眼見為實”是再自然不過的事情。但是，在信息膨脹和普及的今天，事情并不是這么簡單。隨著多媒體技術的迅速發(fā)展和網(wǎng)絡帶寬限制的放松

9、，越來越多的數(shù)字化圖像在網(wǎng)絡上傳輸。這些圖像信息有些無關緊要，有些卻至關重要，它們有可能涉及到個人的隱私、公司的利益、國家的安全，其價值無法衡量。另一方面，網(wǎng)絡的普及使得任何人都有可能接觸到其中的信息，并從中搜集，而無論這種搜集是善意還是惡意、合法還是非法。這就使得在網(wǎng)絡上傳輸圖像的安全性倍受關注，對圖像進行加密也就成為重要的研究方向。</p><p>　　圖像置亂技術從一維的單表密碼擴展而來， 應用到二維圖像平

10、面、甚至三維圖像色彩空間中。它就是把數(shù)字化圖像做一些“擾亂”，得到一幅完全雜亂無章、面目全非的圖像，擾亂圖像的組成部分，破壞圖像的自相關性，使其所要表達的真實信息無法直觀地得到，那么即使非法截獲者注意到它，如果不知道置亂所采用的算法，就難以恢復原始圖像，即使計算機用“窮舉法”計算各種組合，也要耗費大量的時間，從而在一定程度上保護了圖像信息。</p><p>　　數(shù)字圖像置亂還可以作為數(shù)字水印的預處理，用于增強圖像

11、偽裝的魯棒性。將置亂后的一幅無內容、無紋理、無形狀的圖像嵌入到另一幅普通圖像時就不容易引起那幅圖像太大改變，甚至不會發(fā)生改變，這樣人眼就不易識別，從而增強了圖像偽裝的魯棒性</p><p>　　圖像置亂包括位置置亂、灰度置亂以及兩種方式的結合。位置置亂就是通過改變圖像中各像素點的位置從而達到置亂的目的，灰度置亂則是通過改變圖像的像素值而達到置亂目的。</p><p>　　目前已有的數(shù)字圖像

12、置亂算法相當多[1-5], 具體的置亂方法可以分為基于矩陣變換的圖像置亂、基于偽隨機序列的圖像置亂和基于混沌理論的圖像置亂?；诰仃囎儞Q的方式包括Arnold變換、仿射變換、幻方變換和騎士巡游變換等，這些矩陣變換實際上是把圖像進行拉伸、壓縮、折疊及拼接的過程，通過這一過程將離散化的數(shù)字圖像矩陣中的點進行重新排列，從而達到置亂的目的。為了達到比較好的加密狀態(tài)可以進行多次迭代?；趥坞S機序列的方式是通過軟件或硬件設計一種偽隨機序列發(fā)生器，它

13、可以產(chǎn)生一定數(shù)值范圍內的隨機序列，通過將這些點與圖像的像素點進行數(shù)學運算，從而改變像素值的大小，達到置亂的目的。</p><p>　　第二章 基于Arnold變換的非等長圖像置亂算法</p><p>　　2.1 基于Arnold變換的圖像置亂</p><p>　　數(shù)字圖像可以看作是平面區(qū)域上的二元函數(shù)在離散網(wǎng)格點處的采樣值，這樣就得到了一個表示圖像的矩陣，矩陣中

14、元素的值代表對應點處的信息（灰度值或RGB顏色分量）。對圖像的加密實質上就是對這個二維矩陣進行加密。</p><p>　　Arnold變換，俗稱“貓臉變換” (Catmapping)，是V.J.Arnold在遍歷理論的研究中提出的一類裁剪變換[5]，它可以抽象為在平面單位正方形內繪制一個貓臉圖像，通過變換貓臉圖像由清晰變模糊。</p><p>　　定義1　設有單位正方形上的點，將點變到另一

15、點的變換為:</p><p><b>　　(1)</b></p><p>　　式中: (mod1)表示模1運算。此變換稱作二維Arnold變換。</p><p>　　考慮到數(shù)字圖像的需要，把式(1)中的二維Arnold變換改寫為:</p><p><b>　　(2)</b></p>&

16、lt;p>　　下面所說的Arnold變換即式(2)。其中:，為數(shù)字圖像矩陣的階數(shù)。</p><p>　　考慮到其可進行多次置亂，則得到如下迭代式:</p><p><b>　　(3)</b></p><p>　　式中:，代表迭代的次數(shù)， 。</p><p>　　上述二維Arnold變換在圖像置亂中應用相當廣泛，但一

17、般只適用于等長圖像，因為它對任意方陣，變換周期都存在，而當圖像的長寬不等時，變換周期不一定存在，無法應用周期方法解密，并且該過程不是一一映射，也無法采用逆方式解密。</p><p><b>　　2.2 現(xiàn)有算法</b></p><p>　　目前已有的二維Arnold變換應用于非等長圖像的置亂方法有兩種，一是圖像擴充法，先將圖像擴展為等長圖像，然后用二維等長Arnold

18、變換進行置亂處理；二是Arnold變換推廣式，即修改了變換中的單一取模，擴展了二維Arnold變換的應用范圍。</p><p>　　2.2.1圖像擴充法</p><p>　　文獻[6]提出了基于二維等長Arnold變換的非等長圖像置亂算法。</p><p>　　其基本思想是:將長方形圖像按照較大的邊長擴充為正方形圖像，然后再應用二維Arnold變換進行置亂。被置亂后

19、的圖像和原圖大小不一致，圖像置亂恢復結束后需要進行裁剪才能得到原始圖像。</p><p>　　圖1 基于擴充算法置亂示例圖</p><p><b>　　Arnold推廣式</b></p><p>　　文獻[7]考慮到數(shù)字圖像長寬不等的問題，把式(2)中的二維Arnold變換變形為:</p><p><b>　

20、　(4)</b></p><p>　　其中：為原始圖像的像素點的坐標，表示置亂后的圖像的像素點的坐標，為圖像的高，為圖像的寬。</p><p>　　文中證明了圖像高寬比或為整數(shù)或奇數(shù)時變換周期是存在的，即該變形公式將二維Arnold變換的應用范圍進行了擴展。</p><p>　　如下圖,原圖為400*800的灰度圖,滿足寬高比為整數(shù),即可以采用推廣式進行

21、置亂。</p><p>　　圖2 基于推廣式算法的置亂示例圖</p><p>　　2.2.3現(xiàn)有兩種算法的局限性</p><p>　　上述第一種算法在圖像置亂前將圖像的屬性進行了更改，在置亂恢復后還需要進行圖像切割才能真正得到原圖；第二種算法擴展了Arnold變換的應用范圍，但仍不能適用于所有非等長圖像。</p><p>　　2.3 本文提

22、出的算法</p><p>　　本文從兩種現(xiàn)有算法的基礎上出發(fā)，在不改變圖像本身屬性的前提下提出一種新的基于Arnold變換的非等長圖像置亂算法，該置亂算法適用于任意非等長圖像。</p><p><b>　　2.3.1算法思想</b></p><p>　　對于任意長方形圖像，總可以劃分為有限多個有重合區(qū)域的正方形區(qū)域塊，以長方形圖像的較短邊為邊長

23、的正方形區(qū)域，如圖所示。</p><p>　　圖3 本文置亂算法示意圖</p><p>　　其中：為重合區(qū)域寬度，。</p><p>　　則可以對上述劃分的每個正方形區(qū)域從左到右順序應用二維Arnold變換，從而實現(xiàn)對整個長方形圖像的置亂變換。</p><p>　　若，則最差的劃分，即劃分后產(chǎn)生正方形區(qū)域塊最多的方式是重合區(qū)域。</p

24、><p>　　如有4*10的圖像，采用的重合區(qū)域，則其置亂過程為：</p><p>　　圖4 4*10大小圖像的置亂順序示意圖</p><p>　　圖像劃分的正方形區(qū)域塊的大小為4*4，塊和塊間的重合大小為2，那么順序的置亂源圖像1-4行1-4列的區(qū)域、1-4行3-6列的區(qū)域、1-4行5-8列的區(qū)域、1-4行7-10列的區(qū)域，即完成了對整個圖像的一次置亂過程。該置亂過

25、程允許多次迭代，直到達到較好的置亂效果。</p><p>　　2.3.2重合區(qū)域的選取</p><p>　　可以看到在該算法中，不同的圖像重合區(qū)域的劃分不同，即使同一幅圖像，重合區(qū)域的劃分也可能會有多種。那么，計算可能的重合區(qū)域，以及如何從中選擇合適的重合區(qū)域進行置亂，也就成為算法的核心部分。</p><p>　　設待置亂圖像為大小，且，若被劃分為塊正方形區(qū)域，則重

26、合區(qū)域大小滿足：</p><p><b>　　其中，的整數(shù)</b></p><p>　　特別的，時，，即待置亂圖像為正方形圖像。</p><p>　　另外，重合區(qū)域最差情況下為，即</p><p>　　那么，可能的重合區(qū)域大小為：</p><p><b>　　且的整數(shù)</b>

27、</p><p>　　如待置亂圖像大小150*200，則</p><p><b>　　當時，；</b></p><p><b>　　當時，；</b></p><p><b>　　當時，，所以；</b></p><p><b>　　當時，，所以；

28、</b></p><p><b>　　當時， ；</b></p><p><b>　　當時，，所以；</b></p><p><b>　　……</b></p><p>　　那么，推導可得對于大小的圖像，可能的劃分為：</p><p>　　表1

29、 大小圖像重合區(qū)域計算結果表</p><p>　　可以看到，對于同樣大小的圖像劃分為多個正方形區(qū)域時可能的劃分有多種，選擇適當?shù)闹睾蠀^(qū)域應考慮如下因素：</p><p>　　一是置亂均勻性。對于一些圖像而言重合區(qū)域大小可以為0，但這樣的正方形區(qū)域劃分必然會使得置亂過程只在區(qū)域中發(fā)生，當然如果重合區(qū)域大小過小也會使得置亂后圖像出現(xiàn)明顯的區(qū)域痕跡，這需要通過大量的置亂次數(shù)來彌補才能得到較為均

30、勻的置亂后圖像。</p><p>　　如下圖像為256*128大小的灰度圖，可能的重合區(qū)域值有：0，64，96，112，124，126，127,如取重合區(qū)域大小為0，則置亂后圖像會看到有明顯的區(qū)域性，且這種區(qū)域性一般需要較多次置亂才可能彌補。</p><p>　　圖5 置亂結果區(qū)域性問題說明圖</p><p>　　二是計算量。如果重合區(qū)域較大，那么劃分的正方形區(qū)域

31、塊數(shù)量也會增大，一次置亂的時間花費就會較大，即計算量會越大。以下為選取不同大小圖像進行置亂的一次置亂時間比較結果，重合區(qū)域大小分別取較小的、中間的、較大的三種值。</p><p>　　表2 置亂計算量問題說明比較表</p><p>　　為了在較短時間較好的實現(xiàn)置亂，綜合以上兩各因素，我們選取最接近的重合區(qū)域大小，實驗表明這樣的選擇是合理的。</p><p><

32、;b>　　2.3.3置亂恢復</b></p><p>　　一般Arnold變換的圖像置亂恢復是借助于周期性來實現(xiàn)的，而本文算法由于存在重合區(qū)域，且置亂過程是按照劃分的正方形區(qū)域塊從左到右來依次進行的，這樣就會導致一些點在一次完整的置亂中會經(jīng)過一個或幾個位置，事實上周期在許多劃分情況下都是不存在的。</p><p>　　以大小的圖像為例，取重合區(qū)域大小，則原圖被劃分為2塊，

33、那么對于點的具體置亂過程如下：</p><p><b>　　第一次置亂：</b></p><p><b>　　第二次置亂：</b></p><p><b>　　第三次置亂：</b></p><p><b>　　第四次置亂：</b></p>&

34、lt;p><b>　　第四次置亂：</b></p><p><b>　　…</b></p><p>　　可以看到置亂在內不斷重復，不論置亂執(zhí)行多少次總是不能回到原來的點。那么這就表明, 對于大小的圖像，在被劃分為2塊正方形區(qū)域的情況下，本文算法不具有周期性。</p><p>　　文獻[8]中提出基于Arnold變換的

35、正方形圖像不僅可以借助于周期性進行置亂恢復，還是可以借助于Arnold逆變換進行置亂恢復。</p><p>　　二維Arnold逆變換:</p><p><b>　　(5)</b></p><p>　　由于本算法的置亂基本思想是基于正方形劃分，那么按照置亂的正方形區(qū)域塊的劃分方式，采用二維Arnold逆變換，從右到左依次來進行塊的逆置亂，從而就

36、可以實現(xiàn)對整個長方形圖像的置亂恢復過程。</p><p>　　第三章 仿真實驗</p><p>　　3.1算法有效性實驗</p><p>　　選取320*240大小的灰度圖，其可能的重合區(qū)域值有：160，200，220，224，230 232，235，236，238。取接近于1/2的值160進行置亂。置亂結果如圖所示：</p><p>　

37、　圖6 算法有效性實驗結果1</p><p>　　選取120*240大小的灰度圖，其可能的重合區(qū)域值有：60，80，90，96，100，105，108，110，112，114，115，116，117，118，119。取接近于1/2的值60進行置亂。置亂結果如圖所示：</p><p>　　圖6 算法有效性實驗結果2</p><p>　　從圖可以看出，對于長方形圖像在本

38、算法下可以在經(jīng)過較少次的置亂后得到一幅雜亂無章，無紋理的圖像，能較好地隱藏圖像信息。</p><p>　　從圖中也可以看到，在得知置亂過程的重合區(qū)域大小的情況下可以較快的對置亂后圖像進行恢復。</p><p>　　3.2 置亂均勻性實驗</p><p>　　選取大小為320*400的圖像，取重合區(qū)域值240進行置亂并恢復的結果，如圖所示：</p>&l

39、t;p>　　圖7 置亂均勻性實驗結果</p><p>　　從上圖可以看出，本文算法的置亂是較為均勻的，經(jīng)過較少的置亂次數(shù)后圖像中的各點分布在整個長方形圖像區(qū)域中。</p><p>　　3.3算法安全性實驗</p><p>　　選取大小為280*180的圖像，取重合區(qū)域值為80進行置亂，置亂恢復中取錯誤的重合區(qū)域大小的恢復結果。</p><p

40、>　　圖8 算法安全性實驗結果</p><p>　　從上圖可以看到，對于置亂后圖像，若不知道正確的重合區(qū)域大小值也不能正確的恢復圖像，具有一定的安全性。</p><p>　　3.4與現(xiàn)有算法的比較實驗</p><p>　　選取大小為：1200*2000的圖像，在不同置亂算法下的置亂結果如圖所示：</p><p>　　圖9 三種置亂算

41、法比較實驗</p><p>　　從上圖可以看出，對于同一幅長方形圖像采用擴充方式需要修改原圖，置亂后傳輸圖像與原圖屬性有較大差別，置亂恢復后還需要對其進行切割才可真正恢復。Arnold變換推廣式的算法不適用所有圖像，置亂過程中會有多點置亂后對應于一點的情況，因此置亂中會丟失圖像信息，也不會正確恢復。而本文算法對于任意長方形圖像均可以較好的置亂。</p><p><b>　　第四章

42、 結束語</b></p><p>　　傳統(tǒng)的二維Arnold變換只適用于正方形圖像的置亂，而對于一般的長方形圖像不能夠直接使用。目前基于二維Arnold變換的非等長圖像置亂算法有基于圖像擴充的方法和基于推廣的Arnold變換兩種，但這兩種算法各有局限性。</p><p>　　本文基于二維Arnold變換提出將非等長圖像劃分成有限多個有重合區(qū)域的正方形塊，對每個正方形塊順序進行

43、置亂的方法，該方法適用于任意長方形圖像，能夠均勻的置亂圖像。實驗結果表明，該算法是有效的，安全的。</p><p><b>　　參考文獻</b></p><p>　　[1]齊東旭.矩陣變換及其在圖像信息隱藏中的應用研究[J].北方工業(yè)大學學報,1999, 11(1):24-28.</p><p>　　[2]丁瑋,閆偉齊,齊東旭.基于置亂與融合的

44、數(shù)字圖像隱藏技術及應用[J].中國圖像圖形學報,2000,5(8):644-648.</p><p>　　[3]林學輝，蔡利棟.基于Hilbert曲線的數(shù)字圖像置亂方法研究[J].中國體視學與圖像分析，2004,9(4):224-227</p><p>　　[4]齊東旭,鄒建成,韓效肴.一類新的置亂變換及其在圖像信息隱蔽中的應用[J].中國科學(E輯),2000,30(5): 440-44

45、8.</p><p>　　[5]丁瑋，閆偉齊，齊東旭.基于Arnold變換的數(shù)字圖像置亂技術[J]. 計算機輔助設計與圖形學學報,2001,13(4):338-341</p><p>　　[6]孔濤,張亶.Arnold反變換的一種新算法[J].軟件學報,2004,15(10):1558- 1564.</p><p>　　[7]邵利平,覃征.二維非等長圖像置亂變換[J