Arnold变换的快速高效恢复算法一直是人们追求的目标,特别当图像维数较大、置乱次数较多时,如何高效恢复图像尤为重要.根据Arnold变换的周期性和模运算的性质,人们归纳出迭代置乱法、一步反变换法和解方程组方法3种Arnold变换恢复算法.下面从效率和应用条件上对其进行对比分析.

问题描述 假设某个大小为N×N的图像用Arnold变换置乱了k次,Arnold变换周期为m_N, 求解其恢复图像或恢复矩阵T_k.

迭代置乱法实质上是利用Arnold变换的周期性,有2种具体操作方式:① 向前计算法,即向前继续一步步做m_N-k次Arnold变换,可以得到原图像; ② 向后计算法,即采用式(2)的Arnold逆变换R做k次变换即还原原图.显然,向前法需已知周期m_N, 才知道要向前变换多少次; 向后法则无需知道m_N. 虽然Arnold变换计算简单,但从图像还原效率考虑,向前法更适于k≥m_N/2的情况,而向后法则当k较小时更有效.

但总的来说,迭代置乱法的计算效率分别与置乱次数k和图像大小正相关,图像越大,迭代置乱操作耗时越长.

孔涛等^[2]通过分析式(1)中的像素位置范围,得到2种情况下的各2个方程组,求解联立方程组的解,两种情况解集的并就是所求的反变换.该方法仍需反复迭代k步,效率不高.

依据式(3)可得一步反变换为

[x

y]=T_k[x_k

y_k]modN(5)

求解式(5)可得3种求逆变换Tk为</sub>

T_k1=(A^k)^-1modN(6)

T_k2=R^kmodN(7)

T_k3=A^m_N-kmodN(8)

如果事先计算好对应各种置乱次数k的一步还原逆矩阵 T_k1或 T_k2或 T_k3, 可采用一步反变换高效恢复原图.在实时性要求高的场合,牺牲一点内存换取恢复速度是值得的.

以上3种求取恢复矩阵 T_k的方法中都涉及矩阵乘方问题.采用Matlab进行计算时,对较大的置乱次数k,矩阵元素很快就大到超出计算精度的范围,从而得到错误结果.以N=25为例,当k=38时,矩阵A^k为

A³⁸=[2111485077978050 3416454622906707

3416454622906707 5527939700884757]

当k=39时, A^k太大,超出了Matlab精度范围,致使求模结果出错

A³⁹modN=[7 14

14 20](9)

而正确的恢复矩阵是把式(9)中的矩阵元素20改为21.所谓差之毫厘,失之千里,之后的结果怎么都不正确了,变换周期为50也无法验证.因此,本研究提出一种迭代取模伴随矩阵新方法,以期解决直接计算变换矩阵乘方的一步反变换法存在的这些问题.

迭代取模伴随矩阵新方法的基本思路是:不直接用Matlab求矩阵的k次乘方,而是在迭代相乘的每一步都进行求模运算.迭代k步后求得一步变换矩阵C, C的伴随矩阵求模即为一步恢复矩阵.算法如图1.

Input(k)

N←25;

i←0

A←[1,1; 1,2] ‘A为Arnold变换

C←[1,0; 0,1] ‘C初始化为单位矩阵

Do while i<k

C←(C*A)mod N;

i←i+1

End while

图1 迭代取模求一次性Arnold变换矩阵的伪代码
Fig.1 Algorithm pseudo-code for finding the one-step Arnold tronsform by iterative moduloing

由图1步骤,求得一次性Arnold变换矩阵为

C=[c₁₁ c₁₂

c₂₁ c₂₂],c_ij∈{0,1,…,N-1},i,j∈{1,2}(10)

文献[1]指出,逆变换矩阵可以用正变换的伴随矩阵来求得,而Arnold变换属于矩阵变换的一种,且对于Arnold变换,det(A)=1, 则

R=adj(A^k)modN(11)

其中,adj(A)为A的伴随矩阵.所以, k步Arnold变换的一步逆变换矩阵为

T_k=[c₂₂ -c₁₂

-c₂₁ c₁₁]modN(12)

几次求模乘后,恢复矩阵的det(T_k)已不再为1,但不断求模使得它并不影响最终结果.

从上可见,此迭代取模伴随矩阵求逆变换方法与图像内容无关,适用于任何图像,包括二值图像和灰度图像.

图2是一张白色背景中含10个黑像素的10×10二值图像经Arnold变换逐步置乱的结果.由表1可知,Arnold变换周期为30.然而,原图经15次置乱后就恢复到原图,可见图像置乱周期为15,是Arnold变换周期的一半.说明图像置乱周期与Arnold变换周期是两个不同概念.

图2 经Arnold变换的10×10二值图像(置乱次数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变换图像置乱度的半周期现象和上半周期与下半周期的图像置乱效果具有一定对称性^[10-11].

对多种不同大小、或黑底或白底、具有少数前景色像素的图像,在Matlab环境下进行Arnold变换实验,置乱次数为1个周期,测试传统全部像素参与置乱运算和只有少数前景像素参与运算2种方法的时间,结果见表2.

表2 二值图像Arnold置乱计算效率对比实验
Table 2 Comparison of time costs for different scrambling strategies

由表2可见,对大小不同、黑白像素数量比例也不同的图像,以相应的置乱周期为置乱次数,只对少数点置乱的快速置乱策略可提高置乱速度,但并非与参与运算的像素个数成正比,究其原因是:Arnold矩阵变换的运算时间只占一次置乱变换整个运算时间的一小部分,取模运算需要时间,特别是循环条件判断、开辟缓存区等操作占去了大部分时间.同时,图像大小差异导致更显著的运算时间差异,运算时间更多地依赖于图像大小,进一步说明循环判断和开辟缓存数组上所花的时间占比较大.

对大小为25×25的图像置乱k次,表3给出2种求取一步恢复矩阵方法的结果对照.

表3 直接求Ak取模法和迭代取模伴随
矩阵法求得的Tk(N=25)
Table 3 Comparison of Tk for different

k 直接求A^k取模法 迭代取模伴随矩阵法37 [0 7

7 7] [0 7

7 7]38 [7 18

18 0] [7 18

18 0]39 [20 11

11 7] [21 11

11 7]49 [16 5

5 21] [1 1

1 2]50 [18 5

5 23] [1 0

0 1]

由表3可见:

1)当k≤38时,2种方法求得同样的一步恢复矩阵,但从k=39开始,直接求A^k取模法由于运算精度限制而得不到正确的恢复矩阵,致使直接求A^k取模法无法恢复原图.

2)本研究提出的迭代取模伴随矩阵法验证了阶数N为25时求取Arnold变换一步逆阵的正确性及其周期为50.

3)迭代取模伴随矩阵法所求恢复矩阵的行列式值大部分不再为1,但每步的求模运算保证了行列式值非1对最终结果无影响.

下面用256×256的白底图像含少数个黑色像素的图像进行实验,考察该改进方法在时间效率上的表现.

取k=87和113,置乱周期为192.依据迭代取模伴随矩阵法,分别求得一步恢复矩阵为T₈₇=[189 24

24 213], T₁₁₃=[73 153

153 226].

首先,对图3的原图分别进行87次和113次置乱,在置乱图像上随意画上一笔来模拟污损,分别用T₈₇和 T₁₁₃对有无污损的置乱图像进行相应一步反置乱.结果如图3,对无污损置乱图像,所求恢复矩阵可一步还原原图; 对有污损置乱图像,一步恢复矩阵同样可以恢复原图主要信息,同时说明了Arnold置乱加密的鲁棒性.

图3 二值图像经87次和113次Arnold置乱与恢复实验
Fig.3 Scrambled images with/without defects and their recovery images for N=256, k=87 and k=113

表4列出了全部像素和少数像素参与运算2种情况下常规迭代法与一步恢复算法所花时间.迭代方法还分为向前迭代和向后迭代.

由表4可见,采用迭代取模伴随矩阵法与少点置乱策略相结合恢复原图有明显效率优势.由于置乱次数都接近半周期次数96,所以向前、向后的迭代恢复耗时相差不多; 就迭代取模伴随矩阵的一步恢复法来说,只在少数黑像素上进行恢复计算比逐个像素运算,效率大大提高,这也验证了少点置乱法的效果.

表4 二值图像Arnold置乱恢复效率对比实验结果(N=256,nB=256)
Table 4 Recovery efficiency comparison for a 256×256 binary image with 256 black pixels