基于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、　呂梁學(xué)院數(shù)學(xué)系</b></p><p><b>　　2012年2月</b></p><p><b>　　摘 要</b></p><p>　　隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，數(shù)字圖像的傳輸安全問(wèn)題受到了越來(lái)越多的重視，圖像置亂作為信息隱藏的手段得到了廣泛的應(yīng)用。</p><p>　　在眾多圖像置

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

4、塊進(jìn)行二維Arnold變換的置亂方式，從而完成對(duì)全圖的置亂。置亂中正方形區(qū)域的劃分辦法綜合考慮到置亂結(jié)果區(qū)域性和計(jì)算量問(wèn)題，選取塊間重合區(qū)域大小接近于原圖較短邊長(zhǎng)的1/2。本算法適用于任意長(zhǎng)方形圖像，置亂恢復(fù)過(guò)程采用逆變換方法。</p><p>　　實(shí)驗(yàn)結(jié)果表明，該算法簡(jiǎn)單，安全，有效，在少量的置亂迭代次數(shù)下即可達(dá)到較好的置亂效果。</p><p>　　關(guān)鍵詞 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>　　圖像作為人類認(rèn)識(shí)和表達(dá)世界的基本方法，應(yīng)用極為廣泛，從古老的壁畫(huà)、象形文字到今天的數(shù)字化圖像，圖像一直伴隨著人類歷史的發(fā)展，人們也期望從圖像中得到直觀的信息，“眼見(jiàn)為實(shí)”是再自然不過(guò)的事情。但是，在信息膨脹和普及的今天，事情并不是這么簡(jiǎn)單。隨著多媒體技術(shù)的迅速發(fā)展和網(wǎng)絡(luò)帶寬限制的放松

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

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

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

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

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

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

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

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

17、般只適用于等長(zhǎng)圖像，因?yàn)樗鼘?duì)任意方陣，變換周期都存在，而當(dāng)圖像的長(zhǎng)寬不等時(shí)，變換周期不一定存在，無(wú)法應(yīng)用周期方法解密，并且該過(guò)程不是一一映射，也無(wú)法采用逆方式解密。</p><p><b>　　2.2 現(xiàn)有算法</b></p><p>　　目前已有的二維Arnold變換應(yīng)用于非等長(zhǎng)圖像的置亂方法有兩種，一是圖像擴(kuò)充法，先將圖像擴(kuò)展為等長(zhǎng)圖像，然后用二維等長(zhǎng)Arnold

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

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

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

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

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

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

24、><p>　　如有4*10的圖像，采用的重合區(qū)域，則其置亂過(guò)程為：</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ū)域，即完成了對(duì)整個(gè)圖像的一次置亂過(guò)程。該置亂過(guò)

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

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

27、</p><p>　　如待置亂圖像大小150*200，則</p><p><b>　　當(dāng)時(shí)，；</b></p><p><b>　　當(dāng)時(shí)，；</b></p><p><b>　　當(dāng)時(shí)，，所以；</b></p><p><b>　　當(dāng)時(shí)，，所以；

28、</b></p><p><b>　　當(dāng)時(shí)， ；</b></p><p><b>　　當(dāng)時(shí)，，所以；</b></p><p><b>　　……</b></p><p>　　那么，推導(dǎo)可得對(duì)于大小的圖像，可能的劃分為：</p><p>　　表1

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

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

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

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

33、那么對(duì)于點(diǎn)的具體置亂過(guò)程如下：</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>　　可以看到置亂在內(nèi)不斷重復(fù)，不論置亂執(zhí)行多少次總是不能回到原來(lái)的點(diǎn)。那么這就表明, 對(duì)于大小的圖像，在被劃分為2塊正方形區(qū)域的情況下，本文算法不具有周期性。</p><p>　　文獻(xiàn)[8]中提出基于Arnold變換的

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

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

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

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

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

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

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

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

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

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

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