基于點陣行列變換的圖像置亂算法

石玲玉，吳雁南，周 銘，鄒艷妮

(1.浙江廣廈建設(shè)職業(yè)技術(shù)大學(xué)信息學(xué)院,浙江 金華 322100；2.南昌醫(yī)學(xué)院,江西 南昌 330004；3.南昌大學(xué)數(shù)學(xué)與計算機學(xué)院，江西 南昌 330031)

隨著計算機網(wǎng)絡(luò)技術(shù)和通信技術(shù)的發(fā)展，圖像傳輸?shù)男畔踩珕栴}被很多學(xué)者研究。目前,圖像加密算法按加密思路主要分為以下幾類：基于空間域的像素置亂、基于混沌的加密、基于變換域的加密、基于秘密分割與秘密共享的加密、基于神經(jīng)網(wǎng)絡(luò)和元胞自動機的加密、基于盲源分離的加密[1]?；诳臻g域的置亂變換，有Arnold變換及其擴展變換、幻方變換、魔方變換等，用這些變換置亂圖像，一般需要迭代若干次，而且有周期性[2-7]。文獻[8]采取分?jǐn)?shù)傅里葉變換和小波分解對彩色圖像分級加密，克服了基于空間域的置亂變換的周期性，但算法比較復(fù)雜。文獻[9]提出了基于素數(shù)的圖像置亂技術(shù)，用雙密鑰(P,M)對圖像進行加密，實現(xiàn)算法和密鑰分離，提高了置亂圖像的安全性，但其置亂效果依賴于密鑰M的選取。針對這些不足，本文設(shè)計了一種基于點陣行列變換的圖像置亂算法，利用變換：f(x)=x*(M+k) modP(其中k是點陣的行號或列號)，對圖像點陣逐行逐列置亂。由于該算法中的每行每列的變換都不相同，徹底打亂了像素點的空間位置，使得原圖像的像素點在置亂圖像中的排列雜亂無章。

1 置亂原理

定理1設(shè)P是素數(shù)，集合N={1,2,…,P-1},M∈N，則映射

f(x)=x*MmodP,x∈N

(1)

是N上的一一映射。

證明顯然0≤f(x)≤P-1。假設(shè)f(x)=0，則存在非負(fù)整數(shù)k，值得x*M-k*p=0，即x*M=k*p，因為P是素數(shù)，所以P整除x或P整除M，但x

另一方面，如果有x1≠x2(不妨設(shè)x1>x2)，使得f(x1)=f(x2)，則存在非負(fù)整數(shù)k1與k2，值得x1*M-k1*p=x2*M-k2*P，即(x1-x2)*M=(k1-k2)*P，所以P整除(x1-x2)或P整除M，但0<(x1-x2)

綜上述，f(x)是N上的一一映射。

定理1表明，f(1),f(2),…,f(P-1)是1,2,…,P-1的一個排列。對于小于P的自然數(shù)s,刪除排列f(1),f(2),…,f(P-1)中大于s的整數(shù)，保持其他數(shù)的順序不變，就得到1,2,…,s的一個排列：t1,t2,…,ts。文獻[9]將圖像的點陣轉(zhuǎn)換成一維數(shù)組(b1,b2,…,bs)，把數(shù)組元素下標(biāo)按t1,t2,…,ts重新排列，再將重排的一維轉(zhuǎn)換為二維點陣，這樣就得到置亂圖像。

選用經(jīng)典測試用例Lena圖像,大小256*256，如圖1所示。用文獻[9]的置亂算法，取素數(shù)p=521,當(dāng)m=3時的置亂圖像如圖2所示。由此看出，如果M選取不合適，置亂圖像呈現(xiàn)分塊狀。所以M不能隨意選取，要想找出效果好的置亂圖像，M需要遍歷2,3,…,P-1，所以該算法效率很低。

圖1 Lena原圖Fig.1 Lena original image

圖2 lena置亂圖像Fig.2 lena scrambling image

下面簡單分析一下置亂圖像呈現(xiàn)分塊狀的原因。對于1,2,…,36組成的二維數(shù)組(如圖3所示)，取p=37，m=2，作變換f(x)=2*xmod 37，x=1,2,…,36，變換后的數(shù)組如圖4所示。由于取模運算的規(guī)律，圖4就分成4塊，每一小塊都保留著原數(shù)組的“全息”。因為圖像的像素點很多，作這樣的變換后，每一小塊都有原圖像“完整”的像素點，只是像素點稀疏了，這樣置亂圖像就成塊狀。

圖3 原數(shù)組Fig.3 Original array

圖4 變換后的數(shù)組Fig.4 Transformed array

針對上述情況，下面設(shè)計的算法分別對點陣的每行每列作變換：

f(x)=x*(M+k) modP，(x=1,2,…,P-1)

(2)

其中k是行、列號，這樣每行、每列的變換規(guī)律就不相同，從而完全打亂了原圖像素點的分布，達到好的置亂效果。

2 加密與解密算法

設(shè)A=(aij)mn是原圖像的像素點二維數(shù)組,B=(bij)mn是A置亂圖像的像素點二維數(shù)組，C=(cij)mn是B還原圖像的像素點二維數(shù)組。

不妨假設(shè)m≤n，任意選取一個比2n大的素數(shù)P，任取一個小于P-n的自然數(shù)M，P和M作為密鑰保存。

2.1 加密算法

先對行進行加密，即從第1行開始逐行置亂；

再對列進行加密，即從第1列開始逐列置亂。置亂算法流程如圖5所示。

2.2 解密算法

解密過程正好和加密過程相反，先對列進行還原，即從第n列開始逐列還原；再對行進行還原，即從第m行開始逐行還原。還原算法流程如圖6所示。

圖5 置亂算法流程圖Fig.5 Flow chart of scrambling algorithm

圖6 還原算法流程圖Fig.6 Flow chart of reduction algorithm

3 實例測試

仍選用經(jīng)典測試用例Lena圖像(圖1)，任取大于512的素數(shù)P=521和自然數(shù)M=3，對圖1用本文的加密算法進行置亂，得到置亂圖像如圖7所示。

圖7 本文算法置亂圖像Fig.7 The algorithm scrambles images

為了評估本文算法的優(yōu)劣，用隨機數(shù)和Arnold變換對圖1進行置亂，將其置亂圖像與本文算法的置亂圖像做比較。

(1)隨機數(shù)的置亂

如果原圖像的像素點在置亂圖像中是隨機均勻分布的，那是很理想的狀態(tài)。因此可以用隨機數(shù)產(chǎn)生的置亂圖像作為衡量一個置亂算法優(yōu)劣的標(biāo)準(zhǔn)。

利用隨機函數(shù)，將圖1的像素點隨機變換位置，得到置亂圖像如圖8所示。

圖8 隨機數(shù)置亂圖像Fig.8 Random numbers scramble the image

(2) Arnold變換置亂

用Arnold變換[2]對圖1進行置亂，2次迭代置亂圖像如圖9所示，20次迭代置亂圖像如圖10所示，50次迭代置亂圖像如圖11所示。

圖9 2次迭代置亂圖像Fig.9 Scrambles the image in sub-iteration

從視覺上看，本文算法產(chǎn)生的置亂圖像比Arnold變換產(chǎn)生的置亂圖像效果要好，與隨機數(shù)產(chǎn)生的置亂圖像效果相當(dāng)。

用本文算法得到灰度圖像的置亂圖像，灰白像素點分布很均勻，絲毫看不出原圖像的痕跡。那么對于彩色圖像置亂效果怎樣呢？我們選擇色彩比較豐富的花卉圖像(如圖12所示)，其置亂圖像的彩色像素點分布也是非常均勻的，如圖13所示。

4 算法評價

4.1 密鑰敏感性

圖像置亂目的是使圖像非法獲得者，難以還原圖像的本來面目，即不易猜中密鑰，這就需要密鑰敏感性非常高。

圖12 花卉原圖像Fig.12 Original image of flowers

取密鑰p=521,m=4,對置亂圖像(圖7)進行還原，得到圖像如圖14所示。取密鑰p=523,m=3,對置亂圖像(圖7)進行還原，得到圖像如圖15所示?？梢娝惴▽γ荑€非常敏感。實際上，如果密鑰錯誤，則解密就相當(dāng)于再次加密。

圖13 花卉置亂圖像Fig.13 Scrambled images of flowers

圖14 錯誤密鑰還原圖像1Fig.14 Error key restores image 1

圖15 錯誤密鑰還原圖像2Fig.15 Error key restores image 2

4.2 抗干擾性

(1) 噪聲影響

在置亂圖像(圖7)中加入30%的噪聲，即隨機把圖像30%的像素點變?yōu)榘咨鐖D16所示。

圖16 加入噪聲圖像Fig.16 Add noise image

圖16的還原圖像如圖17所示。

圖17 噪聲還原圖像Fig.17 Noise reduction image

(2)裁剪影響

在置亂圖像(圖7)中間裁剪掉面積30%正方形，即把圖像裁剪的像素點變?yōu)榘咨?，如圖18所示。圖16的還原圖像如圖19所示。

圖18 中間裁剪圖像(30%)Fig.18 Middle cropped image (30%)

在置亂圖像(圖7)四角裁剪掉面積30%正方形，即把圖像裁剪的像素點變?yōu)榘咨?，如圖20所示。圖20的還原圖像如圖21所示。

圖19 中間裁剪還原圖像(30%)Fig.19 Middle clipping restores image (30%)

圖20 四角裁剪圖像(30%)Fig.20 Quadrangle cropped image (30%)

圖21 四角裁剪還原圖像(30%)Fig.21 Cut corners to restore image (30%)

在置亂圖像(圖7)四邊裁剪掉面積30%正方形，即把圖像裁剪的像素點變?yōu)榘咨?，如圖22所示。圖22的還原圖像如圖23所示。

由此可見，不論裁剪置亂圖像哪個部分，原圖像(圖1)的主要信息和大部分細(xì)節(jié)在還原圖像(圖17，19，21，23)中還能保留。

噪聲和裁剪實驗表明，置亂圖像抗干擾能力強。這也說明原圖像的像素點在置亂圖像中的分布是均勻的，置亂圖像的任何部分都有原圖的“全息”。

圖22 四邊裁剪圖像(30%)Fig.22 Cropped image on four sides (30%)

圖23 四邊裁剪還原圖像(30%)Fig.23 Restore image by clipping on four sides (30%)

4.3 置亂效果定量描述

對于置亂效果的定量描述，一般有兩種方式。一種是基于距離的，即點(x,y)變換到(x′,y′)的距離d越大越好[10]；另一種是基于灰度的，即點(x,y)的灰度與其周邊點的灰度差越大越好[11]。筆者認(rèn)為，應(yīng)該從視覺上看，如果置亂圖像整體灰度分布比較均勻，那么置亂效果就比較好。下面給出置亂效果的定量描述。

將圖像點陣分成互補相交的子塊，每塊大小為s×t,令m′=m/s,n′=n/t，記每個子塊為Bkl,(k=1,2,…,m′,l=1,2,…,n′)。

整個圖像的灰度平均值：

每個子塊Bkl,(k=1,2,…,m′,l=1,2,…,n′)的灰度平均值：

所有子塊的灰度平均值與整個圖像的灰度平均值的均方差：

很明顯，均方差σ2越小表示每子塊的灰度平均值就越接近整個圖像的灰度平均值，置亂效果就越好。子塊的大小要合適，不能過大過小，下面測試取8×8。

用Arnold變換對圖1進行置亂，在第192次迭代出現(xiàn)周期。第1，2，189，190，191次迭代的灰度均方差分別是：1 307.57，683.04，619.2，1 142.6，1 629.35，為了能看出其他迭代次數(shù)灰度均方差的變換情況，去掉這幾次特別大的。第3～188次迭代的灰度均方差對應(yīng)的折線如圖24所示。灰度均方差最小12.27，灰度均方差最大1629.35，波動很大。用Arnold變換置亂圖像，需要在一個周期內(nèi)迭代，才能找出置亂效果好的置亂圖像。

迭代次數(shù)圖24 Arnold變換置亂均方差Fig.24 Arnold transform scrambles mean square deviation

用隨機數(shù)分別對圖1進行200次置亂，置亂圖像的灰度均方差都在30-40之間，如圖25所示。

隨機次數(shù)圖25 隨機數(shù)置亂均方差Fig.25 Random number scrambling mean square deviation

任取4個素數(shù)P=512，769，2 579，12 809，取M=1,2,…,200,用本文算法對圖1進行置亂，分別計算置亂圖像的灰度均方差，得到4條折線，如圖26所示。所有灰度均方差都在30～40之間，波動很小，對應(yīng)的置亂圖像效果差異難以區(qū)分。因此圖像的置亂效果與密鑰(P，M)的選取無關(guān)。

對于彩色圖像置亂效果的定量描述，可以根據(jù)式[12]：0.3R+0.59G+0.11B將(R,G,B)轉(zhuǎn)變?yōu)榛叶龋儆嬎慊叶染讲睢?/p>

m取值圖26 本文算法置亂均方差Fig.26 The algorithm scrambles the mean square error

5 結(jié)論

基于點陣行列變換的圖像置亂算法，置亂效果與密鑰(P,M)的選取無關(guān)，表現(xiàn)出算法的魯棒性。原圖的像素點在置亂圖像中分布均勻，任何子塊都保留著原圖的“全息”，因此抗干擾能力強，顯示了算法的穩(wěn)定性。同時置亂一次成功，無需多次迭代。另外，本文定義的灰度均方差來描述圖像置亂效果，測試表明灰度均方差越小，置亂效果越好，這表明用灰度均方差來描述圖像置亂效果是合理的。