Arnold變換在二值圖像置亂應(yīng)用中若干問題討論

?

Arnold變換在二值圖像置亂應(yīng)用中若干問題討論

廖日軍，李雄軍，徐健杰，李金龍，冼建標(biāo)，何小雨

深圳大學(xué)物理科學(xué)與技術(shù)學(xué)院，深圳518060

摘要:針對(duì)二值圖像的特點(diǎn)，討論了二維Arnold變換在二值圖像置亂中的置亂周期問題，提出一種快速Arnold變換策略，即少點(diǎn)置亂法，分析比較Arnold逆變換方法，針對(duì)一步恢復(fù)原圖中直接求矩陣乘方會(huì)產(chǎn)生當(dāng)矩陣元素過大超出運(yùn)算精度限制時(shí)的結(jié)果錯(cuò)誤問題，提出一種迭代取模伴隨矩陣逆變換法．研究結(jié)果表明，經(jīng)Arnold置亂的二值圖像，其置亂周期有可能是Arnold變換周期的1/2;只對(duì)二值圖像中占像素比例較小的像素進(jìn)行置亂的變換策略，可提高置亂速度;對(duì)變換矩陣迭代取模后再求伴隨矩陣，可得到正確的一步恢復(fù)矩陣．二值圖像Arnold變換中，綜合應(yīng)用少點(diǎn)置亂法和一步恢復(fù)圖像方法，可顯著提高變換與反變換的速度．

關(guān)鍵詞:計(jì)算機(jī)應(yīng)用;置亂變換; Arnold變換;二值圖像; Arnold逆變換;圖像加密

Received: 2015-05-03; Accepted: 2015-06-09

Foundation: University Students' Innovation and Entrepreneurship Training Program Foundation of Shenzhen University(201510590079)

圖像置亂通過變換把圖像變得雜亂無章，從而達(dá)到隱藏或加密信息的目的，通過相應(yīng)逆變換反置亂可恢復(fù)原始圖像．置亂變換有多種，其中Arnold變換因?yàn)槠渌惴ê?jiǎn)單、周期性和非線性佳，在圖像加密、信息隱藏和數(shù)字水印中廣泛應(yīng)用．目前，對(duì)Arnold變換的周期性、恢復(fù)算法和向三維、四維等多維擴(kuò)展的研究比較多見［1-8］，但對(duì)其在二值圖像上的具體應(yīng)用研究仍較少［9］．與灰度圖像Arnold變換相比，二值圖像Arnold變換在圖像置亂周期、變換與逆變換操作方法、密鑰選擇策略等方面的顯著特點(diǎn)，使其在圖像加密解密、版權(quán)保護(hù)、數(shù)字水印等領(lǐng)域有著廣泛的應(yīng)用價(jià)值．

目前Arnold變換恢復(fù)算法基本分為3種:基于周期性的向前或向后迭代置亂法［3，6］、一步反變換法［1，9］和解多個(gè)方程組［2，4］的方法，但在實(shí)際應(yīng)用中各種方法的效率和具體操作鮮見研究．

本研究結(jié)合新型微點(diǎn)二維碼研究項(xiàng)目的具體實(shí)踐，針對(duì)二值圖像的特點(diǎn)，討論Arnold變換的置亂周期問題、快速運(yùn)算策略和恢復(fù)變換計(jì)算問題，最后給出了實(shí)驗(yàn)驗(yàn)證結(jié)果．

1　二值圖像快速置亂策略與置亂周期

圖像Arnold置亂變換常表示為

其中，x、y、x1和y1∈{ 0，1，…，N－1}，(x，y)和(x1，y1)是大小為N×N的數(shù)字圖像一次Arnold置亂前及置亂后的像素坐標(biāo)，記

則圖像Arnold逆變換R使得

從而實(shí)現(xiàn)從(x1，y1)恢復(fù)出(x，y)．

若對(duì)原圖進(jìn)行k次Arnold置亂變換，依據(jù)模運(yùn)算性質(zhì)，有

由于二值圖像只有黑白兩種像素，即0和1兩種灰度值，因此只適于進(jìn)行位置置亂，置亂前后黑像素或白像素?cái)?shù)量不變，只是位置發(fā)生了變化．人們通常對(duì)圖像中的每個(gè)像素依次進(jìn)行置換，得到一次Arnold置亂的結(jié)果圖像．置換后某黑像素可能被移到了原圖像中某個(gè)白像素的位置，也可能是其他黑像素的位置，前一種情況能被視覺覺察到，但后一種情況則不可能察覺;白像素置亂亦如此．由此得到二值圖像置亂變換的快速運(yùn)算策略，即少點(diǎn)置亂法:統(tǒng)計(jì)圖像中黑白像素的個(gè)數(shù)，若m = min(nB，nW)，其中nB和nW分別為大小為N×N的二值圖像中黑白像素的個(gè)數(shù)．若置亂時(shí)只對(duì)占少數(shù)的像素進(jìn)行運(yùn)算，與全圖像計(jì)算比較，在置亂變換上花的時(shí)間減少到原來的m/N2，在黑白像素?cái)?shù)相差懸殊的情況即m＜＜N2/2時(shí)特別有效．注意:置亂圖像時(shí)必須先以原圖中占多數(shù)像素的顏色作為背景來初始化，對(duì)原圖中少數(shù)個(gè)像素進(jìn)行置亂計(jì)算后，再把置亂圖像中對(duì)應(yīng)位置的像素用前景顏色代替．以上策略既可用于二值圖像置亂變換，也可用于反置亂逆變換．

Arnold變換是周期變換，周期的大小一般與圖像大小即模值N有關(guān)，且與之呈非線性關(guān)系，見表1．對(duì)于給定自然數(shù)N，如式(1)的Arnold變換的周期mN是使式(4)成立的最小自然數(shù)n．

表1　不同階數(shù)N下二維Arnold變換周期mNTable 1 mNfor Arnold transformation under different N

圖像置亂周期是指原圖像經(jīng)過周期次置亂變換后，置亂圖像恢復(fù)為原圖．同樣由于二值圖像只有黑白兩種像素，很有可能不到Arnold變換周期就已還原出原圖．所以二值圖像置亂周期ms不僅與Arnold變換周期有關(guān)，還與二值圖像內(nèi)容結(jié)構(gòu)有關(guān)，即ms≤mN．根據(jù)Arnold變換圖像置亂程度的半周期特性，ms最可能是Arnold變換周期mN的1/2，甚至1/4．

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

2.1 Arnold變換恢復(fù)算法對(duì)比分析

Arnold變換的快速高效恢復(fù)算法一直是人們追求的目標(biāo)，特別當(dāng)圖像維數(shù)較大、置亂次數(shù)較多時(shí)，如何高效恢復(fù)圖像尤為重要．根據(jù)Arnold變換的周期性和模運(yùn)算的性質(zhì)，人們歸納出迭代置亂法、一步反變換法和解方程組方法3種Arnold變換恢復(fù)算法．下面從效率和應(yīng)用條件上對(duì)其進(jìn)行對(duì)比分析．

問題描述假設(shè)某個(gè)大小為N×N的圖像用Arnold變換置亂了k次，Arnold變換周期為mN，求解其恢復(fù)圖像或恢復(fù)矩陣Tk．

迭代置亂法實(shí)質(zhì)上是利用Arnold變換的周期性，有2種具體操作方式:①向前計(jì)算法，即向前繼續(xù)一步步做mN－k次Arnold變換，可以得到原圖像;②向后計(jì)算法，即采用式(2)的Arnold逆變換R做k次變換即還原原圖．顯然，向前法需已知周期mN，才知道要向前變換多少次;向后法則無需知道m(xù)N．雖然Arnold變換計(jì)算簡(jiǎn)單，但從圖像還原效率考慮，向前法更適于k≥mN/2的情況，而向后法則當(dāng)k較小時(shí)更有效．

但總的來說，迭代置亂法的計(jì)算效率分別與置亂次數(shù)k和圖像大小正相關(guān)，圖像越大，迭代置亂操作耗時(shí)越長(zhǎng)．

孔濤等［2］通過分析式(1)中的像素位置范圍，得到2種情況下的各2個(gè)方程組，求解聯(lián)立方程組的解，兩種情況解集的并就是所求的反變換．該方法仍需反復(fù)迭代k步，效率不高．

依據(jù)式(3)可得一步反變換為

求解式(5)可得3種求逆變換Tk為

如果事先計(jì)算好對(duì)應(yīng)各種置亂次數(shù)k的一步還原逆矩陣Tk1或Tk2或Tk3，可采用一步反變換高效恢復(fù)原圖．在實(shí)時(shí)性要求高的場(chǎng)合，犧牲一點(diǎn)內(nèi)存換取恢復(fù)速度是值得的．

以上3種求取恢復(fù)矩陣Tk的方法中都涉及矩陣乘方問題．采用Matlab進(jìn)行計(jì)算時(shí)，對(duì)較大的置亂次數(shù)k，矩陣元素很快就大到超出計(jì)算精度的范圍，從而得到錯(cuò)誤結(jié)果．以N = 25為例，當(dāng)k = 38時(shí)，矩陣Ak為

當(dāng)k = 39時(shí)，Ak太大，超出了Matlab精度范圍，致使求模結(jié)果出錯(cuò)

而正確的恢復(fù)矩陣是把式(9)中的矩陣元素20改為21．所謂差之毫厘，失之千里，之后的結(jié)果怎么都不正確了，變換周期為50也無法驗(yàn)證．因此，本研究提出一種迭代取模伴隨矩陣新方法，以期解決直接計(jì)算變換矩陣乘方的一步反變換法存在的這些問題．

2.2迭代取模伴隨矩陣法求一次性反變換

迭代取模伴隨矩陣新方法的基本思路是:不直接用Matlab求矩陣的k次乘方，而是在迭代相乘的每一步都進(jìn)行求模運(yùn)算．迭代k步后求得一步變換矩陣C，C的伴隨矩陣求模即為一步恢復(fù)矩陣．算法如圖1．

圖1　迭代取模求一次性Arnold變換矩陣的偽代碼Fig.1 Algorithm pseudo-code for finding the one-step Arnold tronsform by iterative moduloing

由圖1步驟，求得一次性Arnold變換矩陣為

文獻(xiàn)［1］指出，逆變換矩陣可以用正變換的伴隨矩陣來求得，而Arnold變換屬于矩陣變換的一種，且對(duì)于Arnold變換，det(A ) = 1，則其中，adj(A )為A的伴隨矩陣．所以，k步Arnold變換的一步逆變換矩陣為

幾次求模乘后，恢復(fù)矩陣的det(Tk)已不再為1，但不斷求模使得它并不影響最終結(jié)果．

從上可見，此迭代取模伴隨矩陣求逆變換方法與圖像內(nèi)容無關(guān)，適用于任何圖像，包括二值圖像和灰度圖像．

3　結(jié)果與分析

為考察本研究有關(guān)方法的實(shí)際使用效果，采用Matlab進(jìn)行實(shí)驗(yàn)驗(yàn)證，測(cè)試電腦配置如下: Dell OptiPlex 9010 Mini Tower，處理器:英特爾，第3代酷睿i7-3770@ 3.40 GHz四核，Windows 7專業(yè)版32 位SP1(DirectX 11)，內(nèi)存為4 Gbit．

3.1二值圖像置亂周期

圖2是一張白色背景中含10個(gè)黑像素的10×10二值圖像經(jīng)Arnold變換逐步置亂的結(jié)果．由表1可知，Arnold變換周期為30．然而，原圖經(jīng)15次置亂后就恢復(fù)到原圖，可見圖像置亂周期為15，是Arnold變換周期的一半．說明圖像置亂周期與Arnold變換周期是兩個(gè)不同概念．

圖2　經(jīng)Arnold變換的10×10二值圖像(置亂次數(shù)k，圖像置亂周期為15)Fig.2 10×10 binary images scrambled by Arnold transformation from scrambling time k=1 to k=15(with scrambling cycle of 15)

從圖2也可觀察到，Arnold變換圖像置亂度的半周期現(xiàn)象和上半周期與下半周期的圖像置亂效果具有一定對(duì)稱性［10-11］．

3.2二值圖像快速置亂變換效率實(shí)驗(yàn)

對(duì)多種不同大小、或黑底或白底、具有少數(shù)前景色像素的圖像，在Matlab環(huán)境下進(jìn)行Arnold變換實(shí)驗(yàn)，置亂次數(shù)為1個(gè)周期，測(cè)試傳統(tǒng)全部像素參與置亂運(yùn)算和只有少數(shù)前景像素參與運(yùn)算2種方法的時(shí)間，結(jié)果見表2．

表2　二值圖像Arnold置亂計(jì)算效率對(duì)比實(shí)驗(yàn)Table 2 Comparison of time costs for different scrambling strategies

由表2可見，對(duì)大小不同、黑白像素?cái)?shù)量比例也不同的圖像，以相應(yīng)的置亂周期為置亂次數(shù)，只對(duì)少數(shù)點(diǎn)置亂的快速置亂策略可提高置亂速度，但并非與參與運(yùn)算的像素個(gè)數(shù)成正比，究其原因是: Arnold矩陣變換的運(yùn)算時(shí)間只占一次置亂變換整個(gè)運(yùn)算時(shí)間的一小部分，取模運(yùn)算需要時(shí)間，特別是循環(huán)條件判斷、開辟緩存區(qū)等操作占去了大部分時(shí)間．同時(shí)，圖像大小差異導(dǎo)致更顯著的運(yùn)算時(shí)間差異，運(yùn)算時(shí)間更多地依賴于圖像大小，進(jìn)一步說明循環(huán)判斷和開辟緩存數(shù)組上所花的時(shí)間占比較大．

3.3一步恢復(fù)矩陣的求解與效率實(shí)驗(yàn)

對(duì)大小為25×25的圖像置亂k次，表3給出2種求取一步恢復(fù)矩陣方法的結(jié)果對(duì)照．

表3　直接求Ak取模法和迭代取模伴隨矩陣法求得的Tk(N=25)Table 3 Comparison of Tkfor different methods(N=25)

由表3可見:

1)當(dāng)k≤38時(shí)，2種方法求得同樣的一步恢復(fù)矩陣，但從k = 39開始，直接求Ak取模法由于運(yùn)算精度限制而得不到正確的恢復(fù)矩陣，致使直接求Ak取模法無法恢復(fù)原圖．

2)本研究提出的迭代取模伴隨矩陣法驗(yàn)證了階數(shù)N為25時(shí)求取Arnold變換一步逆陣的正確性及其周期為50．

3)迭代取模伴隨矩陣法所求恢復(fù)矩陣的行列式值大部分不再為1，但每步的求模運(yùn)算保證了行列式值非1對(duì)最終結(jié)果無影響．

下面用256×256的白底圖像含少數(shù)個(gè)黑色像素的圖像進(jìn)行實(shí)驗(yàn)，考察該改進(jìn)方法在時(shí)間效率上的表現(xiàn)．

取k = 87和113，置亂周期為192．依據(jù)迭代取模伴隨矩陣法，分別求得一步恢復(fù)矩陣為

首先，對(duì)圖3的原圖分別進(jìn)行87次和113次置亂，在置亂圖像上隨意畫上一筆來模擬污損，分別用T87和T113對(duì)有無污損的置亂圖像進(jìn)行相應(yīng)一步反置亂．結(jié)果如圖3，對(duì)無污損置亂圖像，所求恢復(fù)矩陣可一步還原原圖;對(duì)有污損置亂圖像，一步恢復(fù)矩陣同樣可以恢復(fù)原圖主要信息，同時(shí)說明了Arnold置亂加密的魯棒性．

圖3　二值圖像經(jīng)87次和113次Arnold置亂與恢復(fù)實(shí)驗(yàn)Fig.3 Scrambled images with/without defects and their recovery images for N=256，k=87 and k=113

表4列出了全部像素和少數(shù)像素參與運(yùn)算2種情況下常規(guī)迭代法與一步恢復(fù)算法所花時(shí)間．迭代方法還分為向前迭代和向后迭代．

由表4可見，采用迭代取模伴隨矩陣法與少點(diǎn)置亂策略相結(jié)合恢復(fù)原圖有明顯效率優(yōu)勢(shì)．由于置亂次數(shù)都接近半周期次數(shù)96，所以向前、向后的迭代恢復(fù)耗時(shí)相差不多;就迭代取模伴隨矩陣的一步恢復(fù)法來說，只在少數(shù)黑像素上進(jìn)行恢復(fù)計(jì)算比逐個(gè)像素運(yùn)算，效率大大提高，這也驗(yàn)證了少點(diǎn)置亂法的效果．

表4　二值圖像Arnold置亂恢復(fù)效率對(duì)比實(shí)驗(yàn)結(jié)果(N=256，nB=256)Table 4 Recovery efficiency comparison for a 256×256 binary image with 256 black pixels

結(jié)論

1)二值圖像置亂與反置亂變換都只需對(duì)原圖中所占比例少的像素進(jìn)行計(jì)算，可提高置亂速度．

2)二值圖像Arnold置亂周期不同于Arnold變換周期，它不僅與圖像大小有關(guān)，而且與圖像結(jié)構(gòu)內(nèi)容有關(guān)．當(dāng)置亂周期小于Arnold變換周期時(shí)，最可能為1/2周期值，甚至1/4周期值．

3) Arnold變換恢復(fù)算法最快的是一步反置亂法．對(duì)維數(shù)大的圖像，預(yù)先計(jì)算好對(duì)應(yīng)不同置亂次數(shù)的恢復(fù)矩陣，在實(shí)時(shí)性要求高的場(chǎng)合不失為一種明智的選擇．該恢復(fù)矩陣的求取不能直接求矩陣的冪，應(yīng)該迭代相乘取模，再求其伴隨矩陣即得對(duì)應(yīng)某置亂次數(shù)的恢復(fù)矩陣．

4) Arnold變換在二值圖像中同樣存在半周期性現(xiàn)象和前后半周期一定的對(duì)稱性，限于篇幅，我們將另文發(fā)表．

引文:廖日軍，李雄軍，徐健杰，等．Arnold變換在二值圖像置亂應(yīng)用中若干問題討論［J］．深圳大學(xué)學(xué)報(bào)理工版，2015，32(4) : 428-433．

參考文獻(xiàn)/References:

［1］Li Xiongjun．A generalized matrix-based scrambling transformation and its properties［C］//Proceedings of the 9th International Conference for Young Computer Scientists．Huangshan(China) : China Computer Federation，2008: 1429-1434．

［2］Kong Tao，Zhang Dan．A new anti-Arnold transformation algorithm［J］．Journal of Software，2004，15(10) : 1558-1563．(in Chinese)孔濤，張亶．Arnold反變換的一種新算法［J］．軟件學(xué)報(bào)，2004，15(10) : 1558-1563．

［3］Zou Jiancheng，Tie Xiaoyun．Arnold transformation of digital image with two dimensions and its periodicity［J］．Journal of North China University of Technology，2000，12(1) : 10-14．(in Chinese)鄒建成，鐵小勻．?dāng)?shù)字圖像的二維Arnold變換及其周期性［J］．北方工業(yè)大學(xué)學(xué)報(bào)，2000，12(1) : 10-14．

［4］Mao Leibo．Research on Arnold transformation algorithm and anti-arnold transformation algorithm［J］．Journal of Chongqing Technology and Business University Natural Science Edition，2012，29(3) : 16-21．(in Chinese)毛雷波．Arnold變換及其逆變換［J］．重慶工商大學(xué)學(xué)報(bào)自然科學(xué)版，2012，29(3) : 16-21．

［5］Wu Faen，Zou Jiancheng．Some necessary conditions for the periodicity of Arnold transformation of digital image with two dimensions［J］．Journal of North China University of Technology，2001，125(6) : 66-69．(in Chinese)吳發(fā)恩，鄒建成．?dāng)?shù)字圖像二維Arnold變換周期的一組必要條件［J］．北方工業(yè)大學(xué)學(xué)報(bào)，2001，125(6) : 66-69．

［6］Arnold V J，Avez A．Ergodic problems of classical mechanics，mathematical physics monograph series ［M］．New York: W A Ben-jamin Inc，1968．

［7］Sun Xiaolong，Wang Zhengyong，He Xiaohai．Application of Arnold transformation in non-square image scrambling［J］．Journal of Terahertz Science and Electronic Information Technology，2014(2) : 248-251．(in Chinese)孫曉龍，王正勇，何小海．Arnold變換在非方陣圖像置亂中的應(yīng)用［J］．太赫茲科學(xué)與電子信息學(xué)報(bào)，2014(2) : 248-251．

［8］Liang Ting，Li Min，He Yujie，et al．Method of improved image scrambling based on Arnold transform ［J］．Computer Engineering and Applications，2013，49(11) : 204-207．(in Chinese)梁婷，李敏，何玉杰，等．基于Arnold變換的改進(jìn)圖像加密算法研究［J］．計(jì)算機(jī)工程與應(yīng)用，2013，49(11) : 204-207．

［9］Xu Haibo．Arnold transform algorithm for binary images ［J］．Software Guide，2011，10(10) : 68-70．(in Chinese)徐海波．基于Arnold變換的二值圖像算法［J］．軟件導(dǎo)刊，2011，10(10) : 68-70．

［10］Wang Xinxin，Bu Ting．An evaluation alorithm of image scrambling degree based on the image area［J］．Journal of Anhui University Natural Science Edition，2011，35(4) : 48-52．(in Chinese)王新新，布挺．基于圖像表面積的置亂程度評(píng)價(jià)算法［J］．安徽大學(xué)學(xué)報(bào)自然科學(xué)版，2011，35(4) : 48-52．

［11］Xu Jiangfeng，Yang You．Analysis of scrambling performance of encrypted image［J］．Computer Science，2006，33(3) : 110-113．(in Chinese)徐江峰，楊有．加密圖像置亂性能分析［J］．計(jì)算機(jī)科學(xué)，2006，33(3) : 110-113．

【中文責(zé)編:英子;英文責(zé)編:雨辰】

【電子與信息科學(xué)/Electrics and Electronics Information】

Corresponding author: Associate professor Li Xiongjun．E-mail: lixj@ szu.edu.cn

Citation: Liao Rijun，Li Xiongjun，Xu Jianjie，et al．Discussions on applications of Arnold transformation in binary image scrambling［J］．Journal of Shenzhen University Science and Engineering，2015，32(4) : 428-433．(in Chinese)

Discussions on applications of Arnold transformation in binary image scrambling

Liao Rijun，Li Xiongjun，Xu Jianjie，Li Jinlong，Xian Jianbiao，and He Xiaoyu

College of Physics Science and Technology，Shenzhen University，Shenzhen 518060，P．R．China

Abstract:Considering the characteristics of binary images scrambled by Arnold transformation，we discuss the scrambling period for binary images and propose an efficient Arnold transformation strategy，namely scrambling on fewer pixels(SFP)．By analyzing and comparing different anti-Arnold transformation methods，we present a one-step image recovery method，the adjoint matrix recovery after iteratively moduloing(AMRAIM)，which aims to avoid the error caused by accuracy limitations when directly computing the transform matrix power．Experimental results show that the scrambling period for scrambled binary images may be one half of that of the Arnold transformation depending on the image contents．The calculation speed is improved by scrambling pixels with less proportion in constituting the binary image．By iteratively moduloing the transformation matrix，we obtain the one-step Arnold transformation and its adjoint matrix for anti-Arnold transformation，which recovers the original image in a single step．Combining SFP and ARMAIM in binary image scrambling by Arnold transformation，the computational efficiency is improved．

Key words:computer application; scrambling transform; Arnold transformation; binary image; anti-Arnold transformation; image encryption

作者簡(jiǎn)介:廖日軍(1992—)，男(漢族)，廣東省梅州市人，深圳大學(xué)本科生．E-mail: 2012180045@ email.szu.edu.cn

基金項(xiàng)目:深圳大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201510590079)

doi:10．3724/SP．J．1249．2015．04428

文獻(xiàn)標(biāo)志碼:A

中圖分類號(hào):U 491.1