汪太月,戴燕青

(湖北理工學(xué)院 數(shù)學(xué)與物理學(xué)院，湖北 黃石 435003)

數(shù)字圖像置亂算法的研究與比較

汪太月,戴燕青

(湖北理工學(xué)院 數(shù)學(xué)與物理學(xué)院，湖北 黃石 435003)

隨著信息技術(shù)及互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，數(shù)字圖像正逐漸成為傳遞和接收信息的主要載體。數(shù)字圖像置亂技術(shù)能達(dá)到圖像信息的保護(hù)及實(shí)時(shí)使用的目的。文章從數(shù)字圖像置亂的理論及概念入手，對(duì)幾種具有代表性的數(shù)字圖像置亂算法進(jìn)行分析、比較及改進(jìn)，闡述了各自的優(yōu)缺點(diǎn)，且通過實(shí)驗(yàn)實(shí)現(xiàn)了不同置亂方式的效果。

圖像置亂；置亂變換；算法實(shí)現(xiàn)；分析比較

隨著信息技術(shù)迅猛發(fā)展及互聯(lián)網(wǎng)技術(shù)的普及，人們獲取信息的方式正由傳統(tǒng)的紙質(zhì)書籍、報(bào)刊演變?yōu)殡娮游谋炯皵?shù)字圖像等。數(shù)字圖像以其直觀性及概括性，逐漸成為信息傳播最常見的方式。而數(shù)字式產(chǎn)品易于復(fù)制和篡改為其致命的弱點(diǎn)。如何保證數(shù)字圖像所攜帶信息的安全性和保密性成為了信息安全領(lǐng)域中的重要研究?jī)?nèi)容[1]。

對(duì)于文本資料，密碼學(xué)能發(fā)揮較好的加密作用，而數(shù)字圖像與文本資料的存儲(chǔ)維度不同，數(shù)據(jù)量要大得多，且有一定的時(shí)效性要求，使用與文本資料相同的加密方式，視覺效果難以得到保障[2]。計(jì)算機(jī)圖形學(xué)雖對(duì)圖像加密起到一定作用，但難以滿足安全性要求[3]。比較不同的加密技術(shù)，數(shù)字圖像置亂算法能夠最大限度地保障信息的傳輸以及存儲(chǔ)安全，不失為穩(wěn)定且高效的方法[4]。

數(shù)字圖像置亂算法能很好實(shí)現(xiàn)圖像像素的位置重排，呈現(xiàn)出與原圖像不同的顯示效果[5]，置亂圖像的信息就自然無法被他人獲取到，且置亂算法靈活，能更大限度地對(duì)圖像進(jìn)行加密處理，提升了圖像的安全性。它是數(shù)學(xué)、信息學(xué)、密碼學(xué)以及計(jì)算機(jī)科學(xué)等有機(jī)結(jié)合的產(chǎn)物，是一種融合技術(shù)面廣、應(yīng)用領(lǐng)域多元化的方法[6]。本文從置亂算法的原理、置亂效果等方面對(duì)幾種數(shù)字圖像置亂算法進(jìn)行分析和改進(jìn)，同時(shí)通過實(shí)驗(yàn)實(shí)現(xiàn)和比較置亂效果,最后歸納總結(jié)了不同算法的優(yōu)缺點(diǎn)。

1 數(shù)字圖像置亂的基本概念

圖像是外界事物在大腦中形成的實(shí)體映像，如靜態(tài)圖像、動(dòng)畫照片以及視頻圖畫等，是當(dāng)今信息傳播的最主要載體[7]。在日常生活中傳輸隱私度較高的信息時(shí)，當(dāng)然不希望圖像信息被他人輕易獲取。在當(dāng)前各種圖像加密隱藏技術(shù)中，數(shù)字圖像置亂技術(shù)越來越引起廣泛關(guān)注和研究。數(shù)字圖像置亂技術(shù)用途廣泛，在用來加密的前提下，也能用于其他技術(shù)的預(yù)處理以及后續(xù)處理，如常用的圖像水印、數(shù)字圖像分存、版權(quán)保護(hù)技術(shù)等[8]。

數(shù)字圖像置亂算法的本質(zhì)就是利用數(shù)學(xué)變換以及各種算法對(duì)圖像進(jìn)行處理，通過移動(dòng)像素點(diǎn)的位置或改變像素值，將圖像的顯示信息完全打亂而達(dá)到保密的效果。在實(shí)現(xiàn)算法的同時(shí)常引入密鑰，能最大限度保證圖像的安全性。對(duì)于大部分加密算法及技術(shù)，數(shù)學(xué)變換是這些技術(shù)方法的基礎(chǔ)。對(duì)于數(shù)字圖像置亂，有如下定義。

定義1[9]給定變換矩陣T，表達(dá)式為T=L[t(i,j)]m×n，即1,2,…,m×n的一種排列方式，圖像A表達(dá)式為：A=[a(i,j)]m×n，將圖像A依據(jù)變換矩陣T作圖像置亂變換后即可得到圖像B。其變換方式如下：

將圖像A中位置1的像素灰度值或RGB分量值挪動(dòng)到位置2，同理可將位置2的像素灰度值或RGB分量值挪動(dòng)到位置3，以此類推，對(duì)圖像A和矩陣T做逐一變換。在置亂變換的最后，將位置的像素灰度值挪動(dòng)到位置1，就能得到置亂后圖像B，該過程可記為B=TA。

定義2[9]給定圖像A=[a(i,j)]m×n，設(shè)變換T是{(x，y):1≤x≤n，1≤y≤m，且x，y均為整數(shù)}到自身的一對(duì)一映射，即：將圖像A中位置(x，y)處的元素變換到位置(x',y')處即可得到圖像B，則稱變換T是圖像A的置亂變換，仍記為B=TA。

對(duì)比定義1與定義2，發(fā)現(xiàn)其實(shí)并沒有本質(zhì)的區(qū)別，但從使用的場(chǎng)合來說是有區(qū)別的。不同的置亂變換，其置亂矩陣T也是不同的，因此構(gòu)造置亂矩陣T就是構(gòu)造置亂變換。由定義2可以看出，構(gòu)造置亂變換就是構(gòu)造{(x，y):1≤x≤n，1≤y≤m，且x，y均為整數(shù)}到自身的一對(duì)一映射。

定義3[10]若存在一個(gè)大于1的正整數(shù)N能夠滿足表達(dá)式TNA=A，就稱最小的正整數(shù)N為置亂變換T的周期。

圖像處理時(shí)，陣列能以圖像顯示，圖像以陣列存儲(chǔ)。置亂程度是指數(shù)字圖像被打亂的程度，一般而言，圖像表現(xiàn)得越亂，置亂的效果就越好。數(shù)字圖像置亂算法是置亂效果以及安全性的直接影響因素，好的算法更能保障圖像信息的安全性以及保密性。根據(jù)置亂算法的易實(shí)現(xiàn)性和高效性，本文討論和研究的置亂算法有Arnold變換、Hilbert曲線變換、Fibonacci變換及基于相鄰像素間位異或的圖像置亂算法。

2 常見的數(shù)字圖像置亂算法及其實(shí)現(xiàn)

2.1 Arnold變換置亂算法

Arnold置亂變換是Arnold提出的一種置亂方法[11]，該方法最初是對(duì)貓臉圖像進(jìn)行操作，因此俗稱為貓臉變換，對(duì)數(shù)字圖像作如下操作：

(1)

式(1)中x,y∈{0,1,2,…,N-1}，表示的是置亂變換前像素點(diǎn)位置，而(x',y')表示的是像素經(jīng)過置亂變換之后的位置，mod為模運(yùn)算。數(shù)字圖像可視為一個(gè)二維的矩陣，矩陣經(jīng)變換后對(duì)應(yīng)圖像像素的位置發(fā)生變化，從而生成新的圖像。該變換在遵循一定變換規(guī)律的條件下可持續(xù)執(zhí)行，因此不僅能實(shí)現(xiàn)圖像加密，而且能達(dá)到圖像置亂的目的。

數(shù)字圖像進(jìn)行Arnold置亂時(shí)，置亂次數(shù)可人為控制且無上限，置亂后的圖像難以辨識(shí)。在重復(fù)一定的迭代變換后，數(shù)字圖形能夠?qū)崿F(xiàn)完美的還原，也就是說Arnold置亂變換具有周期性，因而得以廣泛的應(yīng)用。還原出原始圖像信息的最少迭代次數(shù)即為置亂周期T。不同的像素N值與Arnold置亂變換的周期T之間存在一定關(guān)系。

Arnold置亂算法的周期與圖像像素值之間的關(guān)系見表1。由表1可得，N與T并不是嚴(yán)格的正比例關(guān)系，對(duì)于給定的正整數(shù)N，當(dāng)N>2時(shí)，它們滿足如下不等式：

(2)

本研究采用圖像處理中最常見的Lena圖像為原始圖像，利用MATLAB軟件進(jìn)行置亂處理，迭代10次的Arnold置亂圖像及反置亂圖像如圖1所示。

表1 Arnold置亂算法的周期與圖像像素值之間的關(guān)系

圖1 Arnold置亂圖像及反置亂圖像

2.2 Hilbert曲線變換置亂算法

Hilbert曲線是德國科學(xué)家Peano在1891年發(fā)現(xiàn)的一種曲線，該算法是對(duì)正方形的邊進(jìn)行等分，將正方形一分為四。通過曲線的走向?qū)υ紙D像中的每一個(gè)像素點(diǎn)實(shí)現(xiàn)遍歷而生成一幅雜亂無章的新圖像，這就是Hilbert曲線置亂變換[12]。對(duì)于最簡(jiǎn)單的四元素矩陣，元素的排列順序?yàn)?，2，3，4。不同階Hilbert曲線的遍歷如圖2所示，其二階的Hilbert曲線如圖2(a)所示，四階Hilbert曲線及256階Hilbert曲線分別如圖2(b)、(c)所示。圖像中元素的遍歷從左下角的元素開始，遍歷的次序?yàn)?,1,2,4，一直到右下角結(jié)束。對(duì)一個(gè)任意的N階圖像進(jìn)行Hilbert曲線遍歷操作，一定能將該N階圖像劃分為4個(gè)N/2階的曲線遍歷，而每一個(gè)N/2階曲線遍歷又可以繼續(xù)被劃分為4個(gè)N/4階的Hilbert曲線遍歷，以此類推，直到劃分成2×2的最小遍歷像素矩陣。同為二階的4個(gè)最基本的Hilbert曲線遍歷，其形狀是完全相同的，只是曲線的走向略有不同而已， 因而劃分后的曲線遍歷可直接依據(jù)二階Hilbert曲線遍歷的順序依次完成。

圖2 不同階Hilbert曲線的遍歷

將Lena圖像按Hilbert曲線進(jìn)行賦值，拉成一條一維數(shù)組，再reshape成一幅圖像即為置亂圖像。Hilbert曲線變換置亂圖像及恢復(fù)圖像如圖3所示。

圖3 Hilbert曲線變換置亂圖像及恢復(fù)圖像

為增強(qiáng)圖像置亂的復(fù)雜性與安全性，先將Lena圖像reshape成一維數(shù)組，然后再按Hilbert曲線進(jìn)行賦值，且對(duì)其旋轉(zhuǎn)90°生成一幅圖像即為置亂圖像。改進(jìn)的 Hilbert曲線變換置亂圖像及恢復(fù)圖像如圖4所示。

圖4 改進(jìn)的 Hilbert曲線變換置亂圖像及恢復(fù)圖像

2.3 Fibonacci變換圖像置亂

公元1200年，由意大利著名數(shù)學(xué)家Leonardo Fibonacci研究提出的一個(gè)非常重要的數(shù)列，即Fibonacci數(shù)列，因其具有一些較為特別的性質(zhì)而被廣泛使用[13]。

定義4[14]設(shè)邊長(zhǎng)為N的方形數(shù)字圖像的坐標(biāo)分別為(x,y)和(x',y')，若(x,y)與(x',y')存在的映射滿足公式(3)，同時(shí)有(x',y')∈[0,N]×[0,N]，且該數(shù)字圖像具有周期性，就稱其為二維等長(zhǎng)圖像，其中a，b，c，d為正整數(shù)或0；N代表圖像矩陣的維度參數(shù)。

(3)

將式(3)中的參數(shù)分別取值為a=b=c=1，d=0,就稱為二維等長(zhǎng)Fibonacci圖像置亂變換，即:

(4)

根據(jù)Fibonacci數(shù)列和矩陣的性質(zhì)[13]，F(xiàn)ibonacci變換矩陣Q可由3個(gè)初等矩陣組合而成：

(5)

由式(5)可以得出，F(xiàn)ibonacci變換改變了像素點(diǎn)的位置，而圖像像素點(diǎn)的灰度值變化不大。3個(gè)初等矩陣分別對(duì)圖像進(jìn)行了對(duì)稱變換、錯(cuò)切變換及切割回填處理。在變換的過程中，2個(gè)區(qū)域內(nèi)的像素的相對(duì)位置沒有發(fā)生變化，圖像局部聯(lián)系也沒有發(fā)生變化，也就是說，圖像在經(jīng)過置亂后其灰度值并沒有改變。Fibonacci置亂也是具有周期性。Fibonacci變換圖像像素大小與置亂周期的關(guān)系見表2。

表2 Fibonacci變換圖像像素大小與置亂周期的關(guān)系

對(duì)Lena圖像進(jìn)行Fibonacci變換，不同迭代次數(shù)Fibonacci變換置亂圖像如圖5所示。圖5(a)、 (b)分別為迭代次數(shù)為8,32的置亂圖像，采用矩陣的逆運(yùn)算可得反置亂圖像。

圖5 不同迭代次數(shù)Fibonacci變換置亂圖像

由圖5容易發(fā)現(xiàn)，隨著置亂迭代次數(shù)增加，置亂圖像變得更為零亂，與此同時(shí)，圖像紋理也變得更均勻，波動(dòng)性變得更小，充分反映了Fibonacci置亂變換是一種基于空間位置上的圖像置亂算法。

2.4基于相鄰像素間位異或的圖像置亂算法

位異或是一種應(yīng)用于邏輯操作的二進(jìn)制數(shù)學(xué)運(yùn)算，符號(hào)表示為“∧”，其運(yùn)算的過程可以表示為：a∧b=a'b+ab'(a'、b'分別表示非a、非b)，當(dāng)真異或假、假異或真時(shí)，其最后結(jié)果都為真；而當(dāng)真異或真、假異或假時(shí)，其結(jié)果都為假[15]。通過分析總結(jié)即為：當(dāng)運(yùn)算符兩端的2個(gè)值不相等時(shí)，則異或結(jié)果為真，反之則為假。將數(shù)字a與同一個(gè)數(shù)字b進(jìn)行2次異或運(yùn)算，其結(jié)果仍為原數(shù)值a，這就是異或運(yùn)算符的特點(diǎn)，表達(dá)式為a=a∧b∧b。

置亂變換必須是可逆變換，這樣才能準(zhǔn)確無誤地恢復(fù)原始圖像。而異或運(yùn)算是可逆的，同時(shí)異或運(yùn)算簡(jiǎn)單靈活，方便高效，運(yùn)用到數(shù)字圖像置亂能取得較為理想的置亂效果。

以M×N像素圖像為例，為了便于敘述，取M=256,N=256,即8 bit位圖像，基于相鄰像素間位異或的圖像置亂算法的實(shí)現(xiàn)步驟描述如下：

1)記原始圖像A，A(i,j) 表示圖像中第i行、第j列元素的灰度值，置亂后得到的圖像記為B,大小不變,也為M×N。

2)將原始圖像的第一個(gè)像素的灰度值A(chǔ)(1,1)與M-1做異或運(yùn)算，得到像素點(diǎn)A'(1,1)，然后對(duì)其進(jìn)行交叉換位操作，即令A(yù)'(1,1)的第1 bit位與第8 bit位互換位置，第2 bit位與第4 bit位互換，第3 bit位與第7 bit位互換，第5 bit位與第6 bit位互換，最后得到B(1,1)，交叉換位操作示意圖如圖6所示。

圖6 交叉換位操作示意圖

3)將A(1,2)與它前一位B(1,1)做異或運(yùn)算得到A'(1,2)，再按圖6換位規(guī)則進(jìn)行交叉換位操作得到B(1,2)。

4)依次對(duì)每一個(gè)元素A(i,j)與B元素(i,j-1)做異或運(yùn)算得A'(i,j)，再對(duì)A'(i,j)進(jìn)行交叉換位操作可得B(i,j)，以此類推，直到遍歷A的整個(gè)像素點(diǎn)，即得到置亂后的圖像B。

通過置亂算法的逆操作可還原原圖像，具體操作是從置亂圖像的最后一個(gè)像素的灰度值B(M,N)開始，依次向前分別進(jìn)行位異或運(yùn)算且進(jìn)行交叉換位操作，重復(fù)操作直到B(1,1)，還原操作就算結(jié)束。逆過程的步驟描述與置亂實(shí)現(xiàn)步驟完全相反，最后得到A即為還原圖像?；谙噜徬袼亻g位異或的置亂圖像及還原圖像如圖7所示。

圖7 基于相鄰像素間位異或的置亂圖像及還原圖像

2.5置亂算法的分析與比較

不同圖像置亂算法的比較見表3。

表3 不同圖像置亂算法的比較

Arnold變換、Hilbert曲線變換以及Fibonacci變換置亂算法都是基于位置空間的圖像置亂算法，從本質(zhì)上來說，它們都是通過矩陣變換改變數(shù)字圖像中各個(gè)像素點(diǎn)的位置和順序，進(jìn)而能夠達(dá)到置亂的效果。置亂圖像只是像素位置發(fā)生改變，而圖像的像素總數(shù)、灰度值以及直方圖并未發(fā)生變化，原理簡(jiǎn)單，算法高效。但重排置亂圖像總能還原出原始圖像，因此該類算法存在明顯的缺陷，即安全性有待提高?；谙噜徬袼亻g位異或運(yùn)算的圖像置亂方法與基于位置空間的圖像置亂方法的區(qū)別在于，該算法并不改變像素的位置和順序，而是在色彩空間上對(duì)像素的灰度值進(jìn)行處理，進(jìn)而達(dá)到置亂的目的。與基于位置空間上的算法相比而言，安全性更強(qiáng)，效果也更優(yōu)。不同方法產(chǎn)生的置亂效果不盡相同，一般來說，迭代次數(shù)越多，置亂效果越好。

3 結(jié)束語

圖像置亂算法能較好地保證圖像攜帶信息的安全性和保密性。本文從Arnold變換，Hilbert曲線變換，F(xiàn)ibonacci變換及基于相鄰像素間位異或的圖像置亂算法的原理、優(yōu)缺點(diǎn)、置亂效果等方面進(jìn)行分析比較及改進(jìn)，同時(shí)給出置亂算法的實(shí)現(xiàn)及還原過程，為信息安全提供了理論和實(shí)踐的保證。由于不同置亂算法效果不盡相同，今后將進(jìn)一步探討多種置亂算法的融合，且考慮與密碼學(xué)、數(shù)字水印技術(shù)等相結(jié)合。

[1] 趙鐵宇.基于相位恢復(fù)算法和公鑰密碼學(xué)的光學(xué)圖像加密技術(shù)研究[D].哈爾濱：哈爾濱工業(yè)大學(xué),2016.

[2] 高峰.密鑰定位耦合有限域余弦變換的圖像加密算法[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(7):318-320.

[3] Liang Y,Liu G,Zhou N,et al.Image encryption combining multiple generating sequences controlled fractional DCT with dependent scrambling and diffusion[J].Journal of Modern Optics,2015,62(4):251-264.

[4] Gopalakrishnan T,Ramakrishnan S,Balakumar M.An image encryption using chaotic permutation and diffusion[C].International Conference on Recent Trends in Information Technology.IEEE,2014:1-5.

[5] 黃興,張敏瑞.圖像置亂程度的研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2008,33(5):465-468.

[6] Zhang W,Wong KW,Yu H,et al.An image encryption scheme using lightweight bit-level confusion and cascade cross circular diffusion[J].Optics Communications,2012,285(9):2343-2354.

[7] Ullagaddi V,Hassan F,Devabhaktuni V.Symmetric synchronous stream encryption using images[J].Signal Image and Video Processing,2015,9(1):1-8.

[8] Stoyanov B,Kolev M,Nachev A.Design of a new self-shrinking 2-adic cryptographic system with application to image encryption[J].European Journal of Scientific Research,2012,78(3):362-374.

[9] 黃仿元.基于Arnold變換的圖像置亂算法及實(shí)現(xiàn)[J].貴州大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,25(3):276-279.

[10] 張健,于曉洋,任洪娥,等.圖像置亂程度的衡量方法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(8):134-136.

[11] Kong T,Zhang T.A novel algorithm for inverse Arnold transforms[J].Journal of Software,2004,15(10):1558-1564.

[12] 林峰.基于HDFS的影像數(shù)據(jù)金字塔構(gòu)建及存儲(chǔ)技術(shù)研究[D].哈爾濱：東北林業(yè)大學(xué),2016.

[13] 袁明豪.Fibonacci數(shù)列的模數(shù)列的周期性[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2007,37(3):119-122.

[14] 邵利平,覃征, 高洪江,等.二維非等長(zhǎng)圖像置亂變換[J].電子學(xué)報(bào),2007,35(7):1290-1294.

[15] 朱淑芹,李俊青,葛廣英.基于一個(gè)新的四維離散混沌映射的圖像加密新算法[J].計(jì)算機(jī)科學(xué),2017,44(1):188-193.

(責(zé)任編輯吳鴻霞)

Research and Comparison of Digital Image Scrambling Algorithm

WangTaiyue，DaiYanqing

(School of Mathematics and Physics,Hubei Polytechnic University,Huangshi Hubei 435003)

With the development of information technology and the Internet,Digital images gradually has become the main carrier of the transmission and receiving of information.Digital image scrambling technology can play a more and more important role in the protection of image information and achieve the purpose of real-time use.With the theory and concept of digital image scrambling,this paper analyzes,compares and summarizes the principles of several representative digital image scrambling algorithms,and their respective merits and demerits are elaborated,at last,the experimental results indicate the effect of different scrambling methods.

image scrambling;scrambling transformation;algorithm implementation;analysis and comparison

2017-06-15

國家自然科學(xué)基金項(xiàng)目(項(xiàng)目編號(hào)：61302138);湖北省教育廳科研基金項(xiàng)目(項(xiàng)目編號(hào)：B2015095)；湖北理工學(xué)院創(chuàng)新人才項(xiàng)目(項(xiàng)目編號(hào)：14xjz02C)；湖北理工學(xué)院重大教研項(xiàng)目(項(xiàng)目編號(hào)：2015A08)。

汪太月,副教授,博士,研究方向：廣義高斯信號(hào)處理及圖像處理、信息安全。

10.3969/j.issn.2095-4565.2017.04.006

TP391.9

：A

：2095-4565(2017)04-0025-06