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

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

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

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

1 置亂原理

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

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

(1)

是N上的一一映射。

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

另一方面，如果有x1≠x2(不妨設x1>x2)，使得f(x1)=f(x2)，則存在非負整數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的自然數s,刪除排列f(1),f(2),…,f(P-1)中大于s的整數，保持其他數的順序不變，就得到1,2,…,s的一個排列：t1,t2,…,ts。文獻[9]將圖像的點陣轉換成一維數組(b1,b2,…,bs)，把數組元素下標按t1,t2,…,ts重新排列，再將重排的一維轉換為二維點陣，這樣就得到置亂圖像。

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

圖1 Lena原圖Fig.1 Lena original image

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

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

圖3 原數組Fig.3 Original array

圖4 變換后的數組Fig.4 Transformed array

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

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

(2)

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

2 加密與解密算法

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

不妨假設m≤n，任意選取一個比2n大的素數P，任取一個小于P-n的自然數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 實例測試

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

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

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

(1)隨機數的置亂

如果原圖像的像素點在置亂圖像中是隨機均勻分布的，那是很理想的狀態。因此可以用隨機數產生的置亂圖像作為衡量一個置亂算法優劣的標準。

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

圖8 隨機數置亂圖像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

從視覺上看，本文算法產生的置亂圖像比Arnold變換產生的置亂圖像效果要好，與隨機數產生的置亂圖像效果相當。

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

4 算法評價

4.1 密鑰敏感性

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

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

取密鑰p=521,m=4,對置亂圖像(圖7)進行還原，得到圖像如圖14所示。取密鑰p=523,m=3,對置亂圖像(圖7)進行還原，得到圖像如圖15所示。可見算法對密鑰非常敏感。實際上，如果密鑰錯誤，則解密就相當于再次加密。

圖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%的像素點變為白色，如圖16所示。

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

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

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

(2)裁剪影響

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

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

在置亂圖像(圖7)四角裁剪掉面積30%正方形，即把圖像裁剪的像素點變為白色，如圖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%正方形，即把圖像裁剪的像素點變為白色，如圖22所示。圖22的還原圖像如圖23所示。

由此可見，不論裁剪置亂圖像哪個部分，原圖像(圖1)的主要信息和大部分細節在還原圖像(圖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]。筆者認為，應該從視覺上看，如果置亂圖像整體灰度分布比較均勻，那么置亂效果就比較好。下面給出置亂效果的定量描述。

將圖像點陣分成互補相交的子塊，每塊大小為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次迭代出現周期。第1，2，189，190，191次迭代的灰度均方差分別是：1 307.57，683.04，619.2，1 142.6，1 629.35，為了能看出其他迭代次數灰度均方差的變換情況，去掉這幾次特別大的。第3～188次迭代的灰度均方差對應的折線如圖24所示。灰度均方差最小12.27，灰度均方差最大1629.35，波動很大。用Arnold變換置亂圖像，需要在一個周期內迭代，才能找出置亂效果好的置亂圖像。

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

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

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

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

對于彩色圖像置亂效果的定量描述，可以根據式[12]：0.3R+0.59G+0.11B將(R,G,B)轉變為灰度，再計算灰度均方差。

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

5 結論

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