Abstract: The conventional 2D matrix transform represented by 2D Arnold transform and 2D Fibonacci-Q transform is applied widely in the security of image information, because of its easily selected scrambling variables and its abilities in enduring erasing, cropping and compression attacks. However, this scrambling method can only be used to scramble square image. For any rectangle image with its width not equal to its height, it needs to be expanded into square image or divided into several square images before using 2D matrix transform to scramble it, which adds the extra space or increases the computation cost. To address this problem, this study proposes two kinds of 2D matrix transforms called 2D triangular mappings and also gives their corresponding inverse transforms. The proposed mappings can be used to scramble or recover rectangle image directly and their iterative cost is low. The cost to scramble or recover image for one time is only the numbers of pixels and our proposed mappings need not to compute the iterative period in advance. Experiments show the proposed mappings validity in scrambling rectangle image, low cost in scrambling and recovering rectangle image and robustness in enduring erasing, cropping and compressing attacks.
INTRODUCTION
With the development of computer science and internet technology, more and more digital image information is transmitted over the network and involved in our daily life and study. At the same time, due to the open nature of internet, the chances of image information being illegal intercepted, modified and ravaged are also being improved, which makes the security of digital image information in open network more important.
The security of image information is rarely been studied by traditional cryptology perhaps because image stores huge information. However, in recent years, with the rapid development of computer technology and especially digital image processing technology, people have obtained some useful results and the security of image is becoming an active research topic involving with mathematics, cryptology and information techniques. The proposed techniques include image watermarking, visual cryptology, information sharing, image scrambling etc. Among them, the scrambling technique is one of the basic means for covering huge image information, which can be used in pre-process or post-process of digital image processing, information hiding, digital watermarking, etc. The main purpose of image scrambling transform is to generate a chaos image, which prevents human visual or computer vision system from understanding the true meaning of the original image and the scrambled image can be recovered if the operator knows the scrambling method and scrambling variables.
At present, many kinds of different scrambling methods have been proposed, such as methods based on Fibonacci transform (Zou et al., 2004a, 2004b, 2006), Lucas transform (Zou et al., 2004b), 2D matrix transform (Zhu and Chen, 2005; Ma and Qiu, 2003; Zhang et al., 2006; Wang, 2006), 3D matrix transform (Qi et al., 2000; Hong and Zou, 2005), high dimensional matrix transform (Qi et al., 2000), Hilbert curve (Lin and Cai, 2004), John Conway`s game (Dai et al., 2004; Ding et al., 2000), knight`s tour (Hou et al., 2004), baker mapping (Han et al., 2006), magic square (Wang, 2005; Wang and Jin, 2005), magic cube (Shen et al., 2005; Zhang et al., 2005), etc. The conventional 2D matrix transform, represented by 2D Arnold transform (Qi et al., 2000; Kong and Dan, 2004; Yang et al., 2006) and 2D Fibonacci-Q transform (Qi et al., 2000), is applied widely in the security of image information, because of its easily selected scrambling variables and its abilities in enduring erasing, cropping and compression attacks. However, this method has no abilities to scramble rectangle image. For any rectangle image where its width is not equal to its height, it needs to be expanded into square image (Kong and Dan, 2004; Wang, 2006) or divided into several square images before using 2D matrix transform to scramble it, which adds the extra space and increases the computation cost (Yang et al., 2006).
To address this problem, in this study, we propose two kinds of 2D matrix transforms called 2D triangular mappings and give their corresponding inverse mappings. The proposed mappings can be used to scramble or recover rectangle image directly and their iterative cost is low. The cost to scramble or recover image for one time is only the numbers of pixels and in our proposed mappings, there is no need to compute the iterative period in advance because of the existed corresponding inverse mappings. Experiments show our methods validity in scrambling rectangle image, low cost in scrambling and recovering rectangle image and robustness in enduring erasing, cropping and compressing attacks.
RELATED WORK ABOUT 2D MATRIX TRANSFORM
2D matrix transform came from continuous 2D Arnold transform, which was originated by Arnold and Avez (1968) in their research of ergodic problems of classical mechanics. Because 2D continuous Arnold transform was usually shown by a cat image, it is also called the cat mapping. In this study, we only care about its discrete form.
Definition 1: Discrete 2D Arnold transform, 2D Arnold transform for short: For a given square matrix with m rows and m columns (mxm for short), let (x, y) denote the coordinate of pixel in row x and column y. The following is the 2D Arnold transform:
| (1) |
Qi et al. (2000) gave another 2D transform called 2D Fibonacci-Q transform, which replaced 2D Arnold transform matrix with 2D Fibonacci-Q transform matrix.
Definition 2: 2D Fibonacci-Q transform: For a given mxm square matrix, let (x, y) denote the pixel coordinate. The following is the 2D Fibonacci-Q transform:
| (2) |
Qi et al. (2000) also expanded the transform matrix into 2D matrix transform.
Definition 3: 2D matrix transform: For a given mxm square matrix, let (x, y) denote the pixel coordinate. The following is the 2D matrix transform:
| (3) |
Where, a, b, c, d are non negative integers and the determinant of transform matrix ad-bc is prime with m.
A picture can be regard as a matrix of pixels. By stretching and folding operation to rearrange the positions of pixels in the image matrix, 2D matrix transform can be used to scramble image and the shifted pixels determine 2D matrix transform has abilities in enduring erasing, cropping and compressing attacks. However, the matrices in definition 1~3 are limited to mxm dimensions. So conventional image scrambling methods based on 2D matrix transform can only be used to scramble square image. To expand (3) from mxm to mxn simply according to Eq. 4, can not guarantee the expanded 2D matrix transform can be used to scramble rectangle image directly.
| (4) |
To prove this, we use 2D Arnold transform matrix according to Eq. 4 to scramble 176x260 water-lilies test image for one time and the experimental result is shown in Fig. 1.
In Fig. 1a, the original image is stretched by 2D Arnold transform matrix and cut into six parts by modular arithmetic in Eq. 4 (Fig. 1b). The six parts of the stretched image are folded where part 1 overlaps part 4 and part 6 and part 2 intersects part 5 (Fig. 1c). The experiment in Fig. 1 shows to expand 2D matrix transform simply according to Eq. 4 can not guarantee the scrambled image can be recovered.
To address the problem above, there are two conventional scrambling methods applying 2D matrix transform into rectangle image: one is based on expanding rectangle image into square image (Kong and Dan, 2004; Wang, 2006) and the other is based on dividing rectangle image into square images (Yang et al., 2006).
In the first one, the original mxn image matrix is expanded into max (m,n)xmax (m,n) dimensions first and then the expanded image is scrambled by 2D matrix transform, so the one time iterative cost is O (max (m2, n2)), which adds the extra space and increases the computation cost. To prove this, we use 2D Arnold transform to scramble the expanded 260x260 water-lilies image for one time and the experiment result is shown in Fig. 2.
| Fig. 1: | Scrambling water-lilies image by the expanded 2D Arnold transform, (a) 176x260 water-lilies image, (b) the stretched water-lilies image by 2D Arnold transform matrix and (c) the folded water-lilies image |
| Fig. 2: | Scrambling the expanded 260x260 water-lilies image by
2D Arnold transform, (a) the expanded 260x260 water-lilies image,
(b) the one time scrambled image by 2D Arnold transform and (c) the
recovered image after obverse iterations by 2D Arnold transform for
209 times where the period is 210 |
| Fig. 3: | Scrambling 176x260 water-lilies by dividing rectangle
image into squares, (a) changing the original rectangle image into
squares, (b) scrambling the squares, respectively by 2D Arnold transform,
(c) 20x30 reorder curve and (d) the reordered scrambled image |
In Fig. 2, the original 176x260 water-lilies image (Fig. 1a) is expanded into 260x260 water-lilies image (Fig. 2a) and scrambled by 2D Arnold transform for one time (Fig. 2b). Figure 2c is the recovered image.
In the second one, the original mxn image matrix is divided into several square images and then these images are scrambled, respectively by 2D Arnold transform. To reduce the stripe phenomenon of the scrambled image, this method added the reorder process (Yang et al., 2006). The iterative cost for one time in the second one is O(((max(m,n)-min(m,n))/s+1)xmin (m,n)+mxn) (Fig. 3a), where, s is the offset between every two square images and s ε {1, 2, …, min (m,n)}. Although the second one need not add the extra space, it really increases the computation cost and operation complexity. To prove this, we divided the 176x260 water-lilies image into five square images where, s is equal to 21 and scrambled them for one time by 2D Arnold transform, respectively. The experiment result is shown in Fig. 3b and 3d and Fig. 3c is the process to reduce the stripe phenomenon.
In Fig. 3c, for clear purpose, we use 20x30 reorder curve to show the reorder process. In our experiment, we use 176x260 reorder curve to reorder the scrambled image. Although the reorder process is added, the strip phenomenon in Fig. 3d still exists.
Form the experiments shown in Fig. 2 and 3, we can see both of the proposed two methods are not good ideas to scramble rectangle image and we need to find another method to solve the problem.
2D TRIANGULAR MAPPINGS
In this section, we give two kinds of 2D triangular mappings that can be used to scramble rectangle image directly. Our scrambling methods are different from the two conventional methods.
Definition 4: 2D lower triangular mapping: For a given mxn matrix, let (x, y) denote the pixel coordinate. The following is the 2D lower triangular mapping:
| (5) |
Where, a, c, d are non negative integers; a is prime with m and d is prime with n.
Definition 5: 2D upper triangular mapping: For a given mxn matrix, let (x, y) denote the pixel coordinate. The following is the 2D upper triangular mapping:
| (6) |
Where, a, b, d are non negative integers; a is prime with m; d is prime with n.
The basic idea of 2D triangular mappings is to select a proper transform matrix to permutated every element in the mxn matrix, in other words, to map all elements with different coordinates into different positions. To ensure it, we give lemma 1 and theorem 1.
Lemma 1: Sequence {ei}, i`ε[0, m-1] is a permutation of sequence {ei}, i ε[0, m-1], if it satisfies (7):
(7) |
Where, a, b are non negative integers and a is prime with m
Proof: Give two different integers i1, i2 ε[0, m-1]. If we prove (ai1+b)mod m≠(ai2+b)mod m, then we can prove lemma 1. Suppose (ai1+b)mod m = (ai2+b)mod m, then ai1-ai2)mod m = 0. Because a and m are relative primes, we can get (i1-i2) mod m = 0. From i1, i2 ε[0, m-1], we can only get i1= i2, which is contrary to i1≠i2. So lemma 1 is proved.
Theorem 1: Elements with different coordinates in the mxn matrix are mapped to different positions by 2D triangular mapping.
Proof: Give two different coordinates (x1, y1) and (x2, y2), if we prove the mapped coordinates (x`1, y`1)≠(x`2, y`2) according to definition 4 and 5, then we can prove theorem 1. Suppose (x`1, y`1) = (x` 2, y`2), according to definition 4, we can get (ax1) mod m = (ax2) mod m and (cx1+dy1) mod n = (cx2+dy2) mod n. Because a is prime with m, from lemma 1, if x`1 = x`2, only x1 = x2.When x1 = x2 and d is prime with n, from lemma 1, if y`1= y`2, only y1= y2. Because x1 = x2 and y1 = y2, (x1, y1) = (x2, y2) which is contrary to two different coordinates (x1, y1) and (x2, y2). So 2D lower triangular mapping can be used to map different coordinate to different positions. Similarly, we can prove 2D upper triangular mapping can also be used to map different coordinate to different positions. So theorem 1 is proved.
From theorem 1, we can see the original matrix can be permutated by our proposed 2D triangular mappings. So the proposed mappings can be used to scramble rectangle image directly. From definition 4 and 5, we can also see: using our proposed mappings to map every element in the mxn matrix to a new position, the one time iterative cost is only O(mxn). So the proposed mappings one-time iterative cost is low. Because the proposed mappings are still based on permutating pixel coordinates, the proposed mappings can endure erasing, cropping and compressing attacks.
INVERSE MAPPINGS OF THE PROPOSED 2D TRIANGULAR MAPPINGS
In conventional scrambling methods, the iterative period takes an important role in recovering the scrambled image (Wang, 2006). Using the iterative period to recover the original image is usually a time-consuming work because the period is usually from hundreds to thousands or millions times or more and it need to compute the exact iterative period in advance. But, in our proposed 2D triangular mappings, we can also give their inverse mappings to avoid the expensive iterative cost. Therefore, in our mappings, it is no need to compute the iterative period.
Definition 6: Inverse 2D lower triangular mapping: For a given mxn matrix, let (x, y) denote the pixel coordinate. The following is the inverse 2D lower triangular mapping:
| (8) |
Where, (a-1a) mod m = 1 and (d-1d) mod n = 1.
Definition 7: Inverse 2D upper triangular mapping: For a given mxn matrix, let (x, y) denote pixel coordinate. The following is the inverse 2D upper triangular mapping:
| (9) |
Where, (a-1a) mod m = 1 and (d-1d) modn = 1.
To ensure it, we give theorem 2 and corollary 1.
Theorem 2: If we use 2D triangular mapping to scramble the given matrix for one time, the scrambled matrix can be recovered by the corresponding inverse 2D triangular mapping.
Proof: Given any coordinate of element (x1, y1) in the given original matrix, if we prove this coordinate is mapped to the same coordinate (x1, y1) by 2D triangular mapping and its corresponding triangular mapping, we can prove theorem 1. From Eq. 5, (x1, y1) is mapped to ((ax1) mod m, (cx1+dy1) mod n). In Eq. 8, substitute x` with (ax1) mod m, then we can get (a-1ax1) mod m. Because x1ε[0, m-1] and (a-1a) mod m =1, (a-1ax1)mod m = x1. In Eq. 8, substitute x with x1 and y` with (cx1+dy1) mod n, then we can get (d-1((cx1+dy1) mod n+[cm/n] n-cx1)) mod n. By the characteristic of modular arithmetic, this formula can be changed into (d-1(cx1+dy1+[cm/n] n-cx1)) mod n. By simplifying, we can get (d-1dy1) mod n. Because y1ε[0, n-1] and (d-1d) mod n =1, (d-1dy1)mod n = y1. Because any coordinate of element (x1, y1) in the given matrix is mapped to the same coordinate by 2D lower triangular mapping and its corresponding inverse 2D lower triangular mapping, 2D lower triangular mapping can be used to recover the original matrix which is scrambled by the corresponding 2D lower triangular mapping. Similarly, we can prove the inverse 2D upper triangular mapping can be used to recover the original matrix which is scrambled by the corresponding 2D upper triangular mapping. So theorem 2 is proved.
Corollary 1: If we use 2D triangular mapping to scramble the given matrix for several times, the scrambled matrix can be recovered by the corresponding inverse 2D triangular mapping with the same times.
Proof: From theorem 2, if we use 2D triangular mapping to scramble the given matrix for k times where, k>=, we can use the corresponding inverse 2D triangular mappings to return the state of k-1 times. Similarly, we can use it to return the state of k-2 times until the state of 0 times arriving. So the given matrix is recovered and corollary 1 is proved.
From theorem 2 and corollary 1, we can see, whenever the original image matrix is scrambled for any times by our proposed 2D triangular mapping, it can be recovered by its corresponding inverse matrix. From definition 6 and 7, in our inverse triangular mappings, the one time iterative cost is only O(mxn).
EXPERIMENTS
To testify the proposed mappings validity in scrambling rectangle image, we scrambled 176x260 water-lilies test images for several times by our proposed 2D triangular mappings and recovered them by the corresponding inverse mappings (Table 1 and Fig. 4).
In Table 1, the first two rows are used to testify 2D lower triangular mappings and the rest rows are used to testify 2D upper triangular mappings. The proposed triangular mappings can scramble rectangle image directly and the scrambled image can be recovered by their corresponding inverse mappings (Table 1 and Fig. 4).
To compare the proposed triangular mappings with the two conventional methods in scrambling and recovering cost, which are shown in Fig. 1 and 2, we gave the periods, one time iterative cost, scrambling times and recovering times of the three kinds of methods in Table 2, where the periods were computed by obverse iterations until the scrambled images are recovered.
In Table 2, row 1-4 are used to testify the proposed triangular mappings; row 5 is used to testify the first conventional method and row 6 is used to testify the second conventional method. From Table 2, we can see the proposed triangular mappings have the least one time iterative cost and the one time iterative cost is only O(176x260). From columns in scrambling times and recovering times, we can see, in our proposed mappings, the scrambling times is equal to the recovering times because of the existing inverse mappings. In our proposed mappings there is no need to compute the period and using the period by obverse iterations to recover the original images. Therefore, the recovering cost of our methods is low.
To testify the proposed mappings robust in enduring erasing and cropping attacks, we attacked the scrambled images shown in Fig. 4 a-d by random cropping square blocks and recovered them by their corresponding inverse mappings. The attack variables and experimental results are shown in Table 3 and Fig. 5, respectively.
The proposed triangular mappings have a favorable scrambling performance in enduring erasing and cropping attacks (Table 3 and Fig. 5).
| Table 1: | The experimental variables of scrambling and recovering 176x260 images |
| Table 2: | Comparing the proposed triangular mappings with the two conventional methods in scrambling and recovering cost |
| Table 3: | The attack variables of erasing and cropping experiments |
| Fig. 4: | The results of experiments to scrambling and recovering 176x260 images where, a-d are the scrambled images and e is the recovered image |
| Fig. 5: | The results of erasing and cropping attack experiments, a-d are the attacked images by random cropping square blocks and e-h are the recovered images |
To testify the proposed mappings robust in enduring compressing attacks, we compressed the scrambled images shown in Fig. 4 a-d, respectively where the compression qualities were set to 60. The attack variables and experimental results are shown in Table 4 and Fig. 6, respectively.
| Fig. 6: | The results of compressing attack experiments, a-d are the attacked images where the compression qualities are set to 60 and e-h are the recovered images |
| Table 4: | The attack variables of compressing experiments |
The proposed triangular mappings have a favorable scrambling performance in enduring compressing attacks (Table 4 and Fig. 6).
CONCLUSIONS AND FUTURE WORK
In this study, we proposed two kinds of 2D triangular mappings and their inverse mappings to address the problem of scrambling rectangle image. To compare with the conventional two scrambling methods, our scrambling methods need not to expand the rectangle image into square or dividing rectangle image into square images. The proposed mappings have their inverse mappings to avoid the expensive iterative cost which is brought by the iterative period and the one time iterative cost is low. From the experiments, we can see our proposed mappings have low cost in scrambling and recovering rectangle image and a wonderful scrambling performance in enduring erasing, cropping and compressing attacks.
The future work is to expand the proposed mappings into high dimensional and then use them to scramble image in the color and position space. The aim of our future work is to increase the couples of different elements in the different spaces in order to increase the security and scrambling performance.
ACKNOWLEDGMENT
This research was supported by the National Natural Science Foundation of China under grant No. 60673024.