?

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

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

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

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

關(guān)鍵詞:計算機應(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變換因為其算法簡單、周期性和非線性佳，在圖像加密、信息隱藏和數(shù)字水印中廣泛應(yīng)用．目前，對Arnold變換的周期性、恢復(fù)算法和向三維、四維等多維擴(kuò)展的研究比較多見［1-8］，但對其在二值圖像上的具體應(yīng)用研究仍較少［9］．與灰度圖像Arnold變換相比，二值圖像Arnold變換在圖像置亂周期、變換與逆變換操作方法、密鑰選擇策略等方面的顯著特點，使其在圖像加密解密、版權(quán)保護(hù)、數(shù)字水印等領(lǐng)域有著廣泛的應(yīng)用價值．

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

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

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

圖像Arnold置亂變換常表示為

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

則圖像Arnold逆變換R使得

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

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

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

Arnold變換是周期變換，周期的大小一般與圖像大小即模值N有關(guān)，且與之呈非線性關(guān)系，見表1．對于給定自然數(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ù)算法對比分析

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

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

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

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

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

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

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

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

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

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

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

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

迭代取模伴隨矩陣新方法的基本思路是:不直接用Matlab求矩陣的k次乘方，而是在迭代相乘的每一步都進(jì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變換屬于矩陣變換的一種，且對于Arnold變換，det(A ) = 1，則其中，adj(A )為A的伴隨矩陣．所以，k步Arnold變換的一步逆變換矩陣為

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

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

3　結(jié)果與分析

為考察本研究有關(guān)方法的實際使用效果，采用Matlab進(jìn)行實驗驗證，測試電腦配置如下: 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個黑像素的10×10二值圖像經(jīng)Arnold變換逐步置亂的結(jié)果．由表1可知，Arnold變換周期為30．然而，原圖經(jīng)15次置亂后就恢復(fù)到原圖，可見圖像置亂周期為15，是Arnold變換周期的一半．說明圖像置亂周期與Arnold變換周期是兩個不同概念．

圖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)象和上半周期與下半周期的圖像置亂效果具有一定對稱性［10-11］．

3.2二值圖像快速置亂變換效率實驗

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

表2　二值圖像Arnold置亂計算效率對比實驗Table 2 Comparison of time costs for different scrambling strategies

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

3.3一步恢復(fù)矩陣的求解與效率實驗

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

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

由表3可見:

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

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

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

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

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

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

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

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

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

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

結(jié)論

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

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

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

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

引文:廖日軍，李雄軍，徐健杰，等．Arnold變換在二值圖像置亂應(yīng)用中若干問題討論［J］．深圳大學(xué)學(xué)報理工版，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é)報，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é)報，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é)報自然科學(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é)報，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é)報，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］．計算機工程與應(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)王新新，布挺．基于圖像表面積的置亂程度評價算法［J］．安徽大學(xué)學(xué)報自然科學(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］．計算機科學(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

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

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

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

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

中圖分類號:U 491.1