# Local Negative Base Transform and Image Scrambling

Authors: Gangqiang Xiong; Shengqian Zheng; Jiang Wang; Zhanchuan Cai; Dongxu Qi
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Scrambling transform is an important tool for image encryption and hiding. A new class of scrambling algorithms is obtained by exploiting negative integer as the base of number representation to express the natural numbers. Unlike Arnold transform, the proposed scrambling transform is one-dimensional and nonlinear, and an image can be shuffled by using the proposed transform to rearrange the rows and columns of the image separately or to permute the pixels of the image after scanned into a sequence of pixels; it can be also applied to shuffle certain part region of an image. Firstly, the transformation algorithm for converting nonnegative integers in baseB to the corresponding integers in base -B is given in this paper, which is the computational core of scrambling transform and the basis of studying scrambling transform. Then, the three kinds of transforms are introduced, that is, negative base transform (abbreviated as NBT), modular negative base transform (MNBT), and local negative base transform (LNBT) with three parameters, where NBT is an injection and MNBT a surjection and LNBT a bijection. The minimum transform periods of LNBT are calculated for some different values of the three parameters, and the algorithm for calculating the inverse transform of LNBT is given. The image scrambled by LBNT can be recovered by the transform period or the inverse transform. Numerical experiments show that LNBT is an efficient scrambling transform and a strong operation of confusing gray values of pixels in the application of image encryption. Therefore, the proposed transform is a novel tool for information hiding and encryption of two-dimensional image and one-dimensional audio.


---

## Body

## 1. Introduction

Because of the properties of visibility, intuitive, abundance in information expression and so on, digital images are widely applied in more and more fields such as remote sensing and geographical information, medical image, audiovisual art, radar navigation, copyright, and trademark; therefore, secure transmission and confidential storage of digital images have been gotten more and more attention by government, industry, and academia. Security protection of digital image includes mainly data encryption and information hiding. Image scrambling is a technique of image encryption or auxiliary encryption [1–9], and also an important method of preprocessing and postprocessing in image hiding, sharing, and digital watermarking [7, 10–17]. Particularly in the application of robust digital watermark, scrambling technique is a very effective method against cropping attack by shuffling watermark image so that the pixels are dispersed in the position space of carrier image. The popular image scrambling methods include Arnold transform [1–3, 10–12, 18], Fibonacci transform [7, 10, 13, 14], Peano-Hilbert space filling curve [19], knight's tour [8, 20], Lucas transform [16], magic square transform [9, 17], Gray code [21, 22], cellular automata [15, 23–25], Baker map [4–6, 26], subaffine transform [27], and sampling technology [28].Most of image scrambling transforms are two-dimensional, such as Arnold transform, baker map, Peano-Hilbert curve, John Conway game, knight's tour, magic square transform, and Fibonacci-Q transform [10]. For two-dimensional scrambling transforms, the popular scrambling transform is Arnold transform, but it requires the sizes of images are the form of N×N [10]; Fibonacci-Q transform is the special case of Arnold transforms [10]. Unlike Arnold transform, knight’s tour [8] and Peano-Hilbert curve [19], John Conway game [15], and magic square transform [9] are not easy to calculate and are rarely used in the application of image scrambling. In general, if using John Conway game to shuffle images we first need to generate a random matrix of 0 and 1, and thus there are difficulties to restore scrambled images. In fact, Baker map is usually exploited to generate chaotic sequence on the interval 0,1×0,1 [4], and if using baker map to shuffle images we must modify the formula of baker map.One-dimensional scrambling transform can also be used in two-dimensional image encryption and information hiding. Battisti used Fibonacci transform to construct Fibonacci-Haar matrix and then studied digital watermarking and encryption algorithms in Fibonacci-Haar domain [7], while Li and Tsai exploited Fibonacci transform to shuffle watermark information [13, 14]. Gunjal combined Fibonacci transform with Lucas transform to construct Fibonacci-Lucas transform which is applied to shuffle watermark image [16]. Zou investigated a class of generalized Gray code and applied it to scramble color image. Two-dimensional scrambling transform or higher-dimensional scrambling transform [10] generally require that the shape of the region of scrambled image must be rectangular (i.e., the size of m×n) or even square such as Arnold transform. One-dimensional scrambling transform can not only permute a sequence of data, but also permute the pixels in an image region of any shape. In fact, as long as the pixels in the image region are scanned into a sequence in accordance with certain rule, we can exploit one-dimensional scrambling transform to permute these pixels.In this paper, we use negative number as the base of numeral system to represent the natural numbers and then define negative base transform (abbreviated as NBT) with respect to radix-B; construct modular negative base transform (abbreviated as MNBT) with respect to radix -B; and modulo Bμ followed by constructing local negative base transform (abbreviated as LNBT) whose radix is -B and modulo Bμ and shift p, where B is an integer greater than 1 and μ, p are natural numbers. In particular, LNBT is a bijective map from the subset {p,p+1,…,p+Bμ-1} of natural numbers to the subset itself. Since LNBT is one-dimensional and nonlinear, we can use it to shuffle one-dimensional audio signal and also to shuffle two-dimensional image. The rest of the paper is organized as follows. Section 2 studies the conversion rules and conversion algorithms from base B integers to the corresponding base -B integers, which is the key of calculating NBT, MNBT, and LNBT. Section 3 gives the definitions of NBT, MNBT, and LNBT and then studies their properties and inverse transforms and last calculates the minimum transformation period of LNBT for some parameter values. Section 4 verifies the scrambling effect of LNBT by simulation experiments, which includes three kinds of scrambling algorithms: scrambling separately along x- and y-direction, scrambling a sequence of pixels after image scanned to a sequence line-by-line or scanned in zigzag order, and then tests the effect against cropping attack in digital watermarking application and the effect of image encryption by shuffling the binary bits of image pixels. Section 5 analyzes the scrambling effect and compares it with other scrambling algorithms; finally, the conclusion is given.


## 2. Using Negative Base to Express Nonnegative Integers

### 2.1. Principle of Number Representation with Negative Base

If selecting a negative integer-B (B>1) as the base of number representation, we only need B figures to express all nonnegative integers, that is, we can use the symbols {0,1,2,…} to express all nonnegative integers [29]. In this paper, for convenience, the notation (anan-1⋯a0)β is used to denote an (n+1)-digit integer in base β, where β is an integer of absolute value greater than 1, and ak=0,1,…,β-1, k=0,1,…,n. For the convenience of description, we also call ak the kth digit of (anan-1⋯a0)β. The rest of this paper, we always suppose B is an integer greater than 1. Next, we shall discuss the calculation for conversion from nonnegative integers in base B to integers in base -B.


### 2.2. Conversion Calculation from BaseB Integer to Base −B Integer

Assuming thatB is an integer greater than 1, a base -B integer can be converted directly to the corresponding decimal integer expressed by the sum of the product which the kth power of -B is multiplied by the kth digit value, as do a base B integer to decimal integer, namely,(1)anan-1⋯a0-B=an×-Bn+an-1×-Bn-1+⋯a0×-B0.The method of seeking remainder can achieve the conversion from decimal integers to base -B integers [29]. Next, we shall investigate the algorithm for converting base B integers to base -B integers. Although we can apply the method in [29] to convert successfully base B integers to base -B integers after the base B integers being converted to decimal integers, we still need to investigate the method of straightforward conversion of base B integers to base -B integers. There are two main reasons. First, Theorem 7 needs to use the conclusion of Theorem 1, that is, we need to get the relation of the digit capacities between any base B integer and the corresponding base -B integer. Second, sometimes we need to convert base B integers directly to base -B integers. The proposed algorithm can achieve simply the conversion from base B integers to base -B integers; especially the conversion method from binary integers to negabinary integers is simpler. We will consider the issue of the digit capacity of the base -B integer converted from a known base B integer, that is, there is Theorem 1 as follows.Theorem 1.
Suppose(anan-1⋯a0)B is a positive integer in base B to be converted, where an≠0, while (xNxN-1⋯x0)-B is the converted integer in base -B, where xN≠0, then n≤N≤n+2.Proof.
First,N≥n holds obviously, followed by N must be even, since (xNxN-1⋯x0)-B=∑k=0Nxk(-B)k<0 if N is odd, which contradicts (anan-1⋯a0)B>0.
Next, we proveN is not greater than n+2. Denoted by (xNxN-1⋯x0)-Bmin the minimum of N+1 digits integers in base -B for all satisfying xN≠0. It is obvious that the value of the positive integer as expressed by (xNxN-1⋯x0)-B is smallest only if xN=1, xN-1=xN-3=⋯=x1=B-1, xN-2=xN-4=⋯=x0=0, and there is(2)xNxN-1⋯x0-Bmin=-BN+∑k=0N/2-1x2k+1-B2k+1=BN+BB+1.Assume N>n+2, i.e., N≥n+3, since anan-1⋯a0B<Bn+1, we have, from (2)(3)xNxN-1⋯x0-Bmin-anan-1⋯a0B>xNxN-1⋯x0-Bmin-Bn+1=BN+BB+1-Bn+1≥Bn+3-Bn+2-Bn+1+BB+1≥Bn+2B-2+BB+1>0.The above inequality shows that anan-1⋯a0B cannot be converted to such a base -B integer of digit capacity greater than n+2.Theorem1 shows that anan-1⋯a0B can be converted to a base -B integer with (n+2)-digit at most, that is, when an be converted, there may be carries from thenth digit place to the (n+1)th digit place or the (n+2)th digit place, but not to the (n+3)th digit place. To be more exact, there is the following Corollary 2.Corollary 2.
Supposean≠0. If n is even, then anan-1⋯a0B can be converted to the forms of xn+2xn+1⋯x0-B or xnxn-1⋯x0-B; if n is odd, then anan-1⋯a0B can be only converted to the form of xn+1xn⋯x0-B.Proof.
It is obvious thatanan-1⋯a0B cannot be converted to the form of xmxm-1⋯x0-B such that m<n. Then according to Theorem 1, anan-1⋯a0B can be only converted to three forms as follows:(4)xn+2xn+1⋯x0-B,(5)xn+1xn⋯x0-B,(6)xnxn-1⋯x0-B.If n is even, it is clear that the form of (6) is likely to appear, for example, if an≠0, ak=0 (k=0,1,…,n-1), there is xn=an,  xk=0 (k=0,1,…,n-1) after converted to the corresponding integer in base -B. On the other hand, if taking an=B-1, an-1≠0, ak=0 (k=0,1,…,n-2), there is xn+2=1, xn+1=B-1, xn=0, xn-1=B-an-1, xk=0 (k=0,1,…,n-2); this indicates that anan-1⋯a0B can be possibly converted to the form of (4). Since it can be deduced from xn+1≠0 that xn+1xn⋯x0-B<0, the form of (5) cannot occur.
Ifn is odd, it is clear that anan-1⋯a0B cannot converted to the forms of (4) and (6); otherwise, there is anan-1⋯a0B<0. So anan-1⋯a0B is only converted to the form of (5).When an integeranan-1⋯a0B in base B is converted to the corresponding integer xmxm-1⋯x0-B in base -B, we suppose the conversion process is from right to left digit-by-digit. Then Corollary 2 shows that, when an being converted, there may be two carries need to be carried to the (n+1)th digit place and the (n+2)th digit place if n is even; otherwise, there is only a carry to the (n+1)th digit place. From Corollary 2, we can get the following conversion rules, namely, Corollary 3.Corollary 3 (conversion rules of baseB integer to base –B integer).
Supposeanan-1⋯a0B is a base B integer that needs to be converted, where an≠0, and xn+2xn+1⋯x0-B is the converted base -B integer, where xn+2 and xn+1 are likely to be zeros. Let bn+2,bn+1,…b0 be a sequence of carries in the process of conversion, and initial values bk=0 (k=0,1,…,n+2). Then, in accordance with the following rules, base B integer can be correctly converted to the corresponding base -B integer.
(i) Whenk is even, if bk+ak≥B, then xk←bk+ak-B, bk+2←1, bk+1←B-1; otherwise, xk←bk+ak.
(ii) Whenk is odd, if bk-ak≥0, then xk←bk-ak; otherwise, xk←bk-ak+B, bk+1←bk+1+1.The left arrow “←” in the above denotes that the value of the expression on the right side is assigned to the variable on the left side. In the following, we shall prove that Corollary 3, in fact, only proves that the converted integer in base -B is equal to the original base B integer.Proof.
Ifk is even and bk+ak≥B, there is(7)bk×-Bk+ak×Bk=bk+ak-B×-Bk+B-1×-Bk+1+1×-Bk+2.Corollary 2 indicates 0≤bk≤B-1, and from 0<ak≤B-1, we have 0≤bk+ak-B<B-1, i.e., xk←bk+ak-B. Corollary 2 tells us again that, when ak-1 is converted, there is only a carry from the (k-1)th digit place to thekth digit place, and when ak-2 is converted, there are two carries at most from the k-2th digit place to the (k-1)th digit place and the kth digit place. That is to say, when ak being converted, the initial values bk+1=bk+2=0. Therefore, it follows from (7) that bk+2←1, bk+1←B-1. If bk+ak<B, obviously, there is(8)bk×-Bk+ak×Bk=bk+ak×-Bk,i.e., xk←bk+ak.
Ifk is odd and bk-ak≥0, then bk×(-B)k+ak×Bk=(bk-ak)×(-B)k, and the inequality bk-ak<bk≤B-1 indicates that xk←bk-ak is true. If bk-ak<0, we have(9)bk×-Bk+ak×Bk=bk-ak+B×-Bk+1×-Bk+1.The inequality 0<B-ak≤bk-ak+B≤B-1 and (9) imply that xk←bk-ak+B and there is a carry 1 from the current digit place to the (k+1)th digit place. In addition, it can be known from Corollary 2 that, when ak-1 being converted, maybe there exist two carries from the (k-1)th digit place to the kth digit place and the (k+1)th digit place, namely, bk+1 may not be equal to 0 when ak being converted. Therefore, bk+1 need to accumulate the carry 1, i.e., bk+1←bk+1+1 is true.So we can obtain Algorithm1 from Corollary 3.Algorithm 1:Converting base B integer to base -B integeran,an-1,…,a0.
Require: a n ,  a n - 1 ,  … , a 0 % the sequence of digits of a base B integer B % the base of the numeral system Ensure: xn+2,xn+1,…,x0% the sequence of digits of the base -B integer Remark: xn+2,xn+1,…,x0% satisfying xn+2xn+1⋯x0-B=anan-1⋯a0B k = 0 While  k≤n+2  do x k = 0 k = k + 1 end while k = 0 while  k≤ndo if  k is even  then if  xk+ak≥B  then x k = x k + a k - B x k + 1 = B - 1 x k + 2 = 1 else  {xk+ak<B} x k = x k + a k end if else  kisodd if  xk-ak≥0  then x k = x k - a k else  {xk-ak<0} x k = x k - a k + B x k + 1 = x k + 1 + 1 end if end if k = k + 1 end whileFor binary, the conversion process is more concise, and the specific conversion rules are described in the following Corollary4.Corollary 4 (conversion rules of binary positive integers to negabinary integers).
Supposeanan-1⋯a02 is a binary positive integer to be converted, where an≠0; xn+2xn+1⋯x0-2 is the converted negabinary integer, and the initial values xk=0 for k=0,1,…,n+2. Then the following conversion rules hold.
(i) Whenk is odd and ak=1, if xk=0, then xk←1, xk+1←1; otherwise xk←0.
(ii) Whenk is even and ak=1, if xk=0, then xk←1; otherwise xk←0, xk+1←1, xk+2←1.
(iii) Ifak=0, then the value of xk keeps changeless.


## 2.1. Principle of Number Representation with Negative Base

If selecting a negative integer-B (B>1) as the base of number representation, we only need B figures to express all nonnegative integers, that is, we can use the symbols {0,1,2,…} to express all nonnegative integers [29]. In this paper, for convenience, the notation (anan-1⋯a0)β is used to denote an (n+1)-digit integer in base β, where β is an integer of absolute value greater than 1, and ak=0,1,…,β-1, k=0,1,…,n. For the convenience of description, we also call ak the kth digit of (anan-1⋯a0)β. The rest of this paper, we always suppose B is an integer greater than 1. Next, we shall discuss the calculation for conversion from nonnegative integers in base B to integers in base -B.


## 2.2. Conversion Calculation from BaseB Integer to Base −B Integer

Assuming thatB is an integer greater than 1, a base -B integer can be converted directly to the corresponding decimal integer expressed by the sum of the product which the kth power of -B is multiplied by the kth digit value, as do a base B integer to decimal integer, namely,(1)anan-1⋯a0-B=an×-Bn+an-1×-Bn-1+⋯a0×-B0.The method of seeking remainder can achieve the conversion from decimal integers to base -B integers [29]. Next, we shall investigate the algorithm for converting base B integers to base -B integers. Although we can apply the method in [29] to convert successfully base B integers to base -B integers after the base B integers being converted to decimal integers, we still need to investigate the method of straightforward conversion of base B integers to base -B integers. There are two main reasons. First, Theorem 7 needs to use the conclusion of Theorem 1, that is, we need to get the relation of the digit capacities between any base B integer and the corresponding base -B integer. Second, sometimes we need to convert base B integers directly to base -B integers. The proposed algorithm can achieve simply the conversion from base B integers to base -B integers; especially the conversion method from binary integers to negabinary integers is simpler. We will consider the issue of the digit capacity of the base -B integer converted from a known base B integer, that is, there is Theorem 1 as follows.Theorem 1.
Suppose(anan-1⋯a0)B is a positive integer in base B to be converted, where an≠0, while (xNxN-1⋯x0)-B is the converted integer in base -B, where xN≠0, then n≤N≤n+2.Proof.
First,N≥n holds obviously, followed by N must be even, since (xNxN-1⋯x0)-B=∑k=0Nxk(-B)k<0 if N is odd, which contradicts (anan-1⋯a0)B>0.
Next, we proveN is not greater than n+2. Denoted by (xNxN-1⋯x0)-Bmin the minimum of N+1 digits integers in base -B for all satisfying xN≠0. It is obvious that the value of the positive integer as expressed by (xNxN-1⋯x0)-B is smallest only if xN=1, xN-1=xN-3=⋯=x1=B-1, xN-2=xN-4=⋯=x0=0, and there is(2)xNxN-1⋯x0-Bmin=-BN+∑k=0N/2-1x2k+1-B2k+1=BN+BB+1.Assume N>n+2, i.e., N≥n+3, since anan-1⋯a0B<Bn+1, we have, from (2)(3)xNxN-1⋯x0-Bmin-anan-1⋯a0B>xNxN-1⋯x0-Bmin-Bn+1=BN+BB+1-Bn+1≥Bn+3-Bn+2-Bn+1+BB+1≥Bn+2B-2+BB+1>0.The above inequality shows that anan-1⋯a0B cannot be converted to such a base -B integer of digit capacity greater than n+2.Theorem1 shows that anan-1⋯a0B can be converted to a base -B integer with (n+2)-digit at most, that is, when an be converted, there may be carries from thenth digit place to the (n+1)th digit place or the (n+2)th digit place, but not to the (n+3)th digit place. To be more exact, there is the following Corollary 2.Corollary 2.
Supposean≠0. If n is even, then anan-1⋯a0B can be converted to the forms of xn+2xn+1⋯x0-B or xnxn-1⋯x0-B; if n is odd, then anan-1⋯a0B can be only converted to the form of xn+1xn⋯x0-B.Proof.
It is obvious thatanan-1⋯a0B cannot be converted to the form of xmxm-1⋯x0-B such that m<n. Then according to Theorem 1, anan-1⋯a0B can be only converted to three forms as follows:(4)xn+2xn+1⋯x0-B,(5)xn+1xn⋯x0-B,(6)xnxn-1⋯x0-B.If n is even, it is clear that the form of (6) is likely to appear, for example, if an≠0, ak=0 (k=0,1,…,n-1), there is xn=an,  xk=0 (k=0,1,…,n-1) after converted to the corresponding integer in base -B. On the other hand, if taking an=B-1, an-1≠0, ak=0 (k=0,1,…,n-2), there is xn+2=1, xn+1=B-1, xn=0, xn-1=B-an-1, xk=0 (k=0,1,…,n-2); this indicates that anan-1⋯a0B can be possibly converted to the form of (4). Since it can be deduced from xn+1≠0 that xn+1xn⋯x0-B<0, the form of (5) cannot occur.
Ifn is odd, it is clear that anan-1⋯a0B cannot converted to the forms of (4) and (6); otherwise, there is anan-1⋯a0B<0. So anan-1⋯a0B is only converted to the form of (5).When an integeranan-1⋯a0B in base B is converted to the corresponding integer xmxm-1⋯x0-B in base -B, we suppose the conversion process is from right to left digit-by-digit. Then Corollary 2 shows that, when an being converted, there may be two carries need to be carried to the (n+1)th digit place and the (n+2)th digit place if n is even; otherwise, there is only a carry to the (n+1)th digit place. From Corollary 2, we can get the following conversion rules, namely, Corollary 3.Corollary 3 (conversion rules of baseB integer to base –B integer).
Supposeanan-1⋯a0B is a base B integer that needs to be converted, where an≠0, and xn+2xn+1⋯x0-B is the converted base -B integer, where xn+2 and xn+1 are likely to be zeros. Let bn+2,bn+1,…b0 be a sequence of carries in the process of conversion, and initial values bk=0 (k=0,1,…,n+2). Then, in accordance with the following rules, base B integer can be correctly converted to the corresponding base -B integer.
(i) Whenk is even, if bk+ak≥B, then xk←bk+ak-B, bk+2←1, bk+1←B-1; otherwise, xk←bk+ak.
(ii) Whenk is odd, if bk-ak≥0, then xk←bk-ak; otherwise, xk←bk-ak+B, bk+1←bk+1+1.The left arrow “←” in the above denotes that the value of the expression on the right side is assigned to the variable on the left side. In the following, we shall prove that Corollary 3, in fact, only proves that the converted integer in base -B is equal to the original base B integer.Proof.
Ifk is even and bk+ak≥B, there is(7)bk×-Bk+ak×Bk=bk+ak-B×-Bk+B-1×-Bk+1+1×-Bk+2.Corollary 2 indicates 0≤bk≤B-1, and from 0<ak≤B-1, we have 0≤bk+ak-B<B-1, i.e., xk←bk+ak-B. Corollary 2 tells us again that, when ak-1 is converted, there is only a carry from the (k-1)th digit place to thekth digit place, and when ak-2 is converted, there are two carries at most from the k-2th digit place to the (k-1)th digit place and the kth digit place. That is to say, when ak being converted, the initial values bk+1=bk+2=0. Therefore, it follows from (7) that bk+2←1, bk+1←B-1. If bk+ak<B, obviously, there is(8)bk×-Bk+ak×Bk=bk+ak×-Bk,i.e., xk←bk+ak.
Ifk is odd and bk-ak≥0, then bk×(-B)k+ak×Bk=(bk-ak)×(-B)k, and the inequality bk-ak<bk≤B-1 indicates that xk←bk-ak is true. If bk-ak<0, we have(9)bk×-Bk+ak×Bk=bk-ak+B×-Bk+1×-Bk+1.The inequality 0<B-ak≤bk-ak+B≤B-1 and (9) imply that xk←bk-ak+B and there is a carry 1 from the current digit place to the (k+1)th digit place. In addition, it can be known from Corollary 2 that, when ak-1 being converted, maybe there exist two carries from the (k-1)th digit place to the kth digit place and the (k+1)th digit place, namely, bk+1 may not be equal to 0 when ak being converted. Therefore, bk+1 need to accumulate the carry 1, i.e., bk+1←bk+1+1 is true.So we can obtain Algorithm1 from Corollary 3.Algorithm 1:Converting base B integer to base -B integeran,an-1,…,a0.
Require: a n ,  a n - 1 ,  … , a 0 % the sequence of digits of a base B integer B % the base of the numeral system Ensure: xn+2,xn+1,…,x0% the sequence of digits of the base -B integer Remark: xn+2,xn+1,…,x0% satisfying xn+2xn+1⋯x0-B=anan-1⋯a0B k = 0 While  k≤n+2  do x k = 0 k = k + 1 end while k = 0 while  k≤ndo if  k is even  then if  xk+ak≥B  then x k = x k + a k - B x k + 1 = B - 1 x k + 2 = 1 else  {xk+ak<B} x k = x k + a k end if else  kisodd if  xk-ak≥0  then x k = x k - a k else  {xk-ak<0} x k = x k - a k + B x k + 1 = x k + 1 + 1 end if end if k = k + 1 end whileFor binary, the conversion process is more concise, and the specific conversion rules are described in the following Corollary4.Corollary 4 (conversion rules of binary positive integers to negabinary integers).
Supposeanan-1⋯a02 is a binary positive integer to be converted, where an≠0; xn+2xn+1⋯x0-2 is the converted negabinary integer, and the initial values xk=0 for k=0,1,…,n+2. Then the following conversion rules hold.
(i) Whenk is odd and ak=1, if xk=0, then xk←1, xk+1←1; otherwise xk←0.
(ii) Whenk is even and ak=1, if xk=0, then xk←1; otherwise xk←0, xk+1←1, xk+2←1.
(iii) Ifak=0, then the value of xk keeps changeless.


## 3. Scrambling Transform Based on Negative Base

Image scrambling, which can change a certain image into another meaningless image, is a special transform from a subset of natural numbers to the subset itself. Rearranging the position of the pixels in the position space of image by permutation on a finite set of the natural numbers can achieve the purpose of scrambling image, such as Arnold transform, baker map, and knight’s tour. Next, we define a new class of scrambling transforms based on the principle of number representation in negative bases.


### 3.1. Negative Base Transform

Unlike the common image scrambling transform, the scrambling transform studied in this paper is one-dimensional, which is such a transform of a certain subset of the natural numbers to the subset itself. First, we define negative base transform in the following.Definition 5 (negative base transform).
For anyx∈N, if transform T-B satisfies(10)T-Bx=∑k=0nxkBk,then T-B:N→N is referred to as negative base transform with respect to base –B, abbreviated as NBT, and B is called transformation parameter of NBT, where xk is the kth digit place of the converted integer xnxn-1⋯x0-B in base -B corresponding to x.From Definition5, we know that, for computing T-B(x), the natural number x must be converted to the form of xnxn-1⋯x0-B, and then calculate T-B(x)=∑k=0nxkBk. For example, since 7=(11011)-2, then T-2(7)=24+23+21+20=27. Table 1 gives the values of NBT with parameter -2 of the natural numbers from 0 to 15. According to Table 1, we can know that, after the natural numbers between 0 and 15 is transformed by NBT, the order of the transform T-2(x) is already different from the original order of independent variablex, and some of T-2(x) are no longer in the set {0,1,2,…,15}, e.g., T-2(7)=27.Table 1
NBT of the integers between 0 and 15 with parameter-2.
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 NBT 0 1 6 7 4 5 26 27 24 25 30 31 28 29 18 19


### 3.2. Modular Negative Base Transform

AssumeN[α,β]=x;x∈N∩[α,β] denote a subset of the natural numbers from α to β, where α,β∈N, α≤β, and N denotes the set of natural numbers. In general, Image scrambling transform is a bijective map from a finite set N[α1,β1]×N[α2,β2] to N[α1,β1]×N[α2,β2]. Unfortunately, NBT is an injective map from the set of natural numbers N to itself, but not surjective, and cannot be used directly in application of image scrambling. Hence we shall make some modifications for NBT so that the modified transform is a bijective map from N[α,β] to N[α,β]. According to the transform NBT, we shall introduce another new transform from N to N[0,Bμ-1] as follows.Definition 6 (modular negative base transform).
Forx∈N, if transform M-B,μ satisfies(11)M-B,μx=T-Bxmod⁡Bμ,then transform M-B,μ is called modular negative base transform with respect to base -B and modulo Bμ, abbreviated as MNBT, where μ is an integer greater than 0.Obviously, MNBT is a surjection fromN to N[0,Bμ-1], but not an injection. In order to make MNBT a bijection, it is necessary to restrict the definition domain of MNBT such that Theorem 7 is true in the following.Theorem 7.
If the definition domain of MNBT isN[p,p+Bμ-1], then MNBT is a bijective map from N[p,p+Bμ-1] to N[0,Bμ-1].Proof.
SupposeM-B,μ is an MNBT as defined in (11). In fact, we only need to prove that M-B,μ is injective if p=0, that is, prove that(12)for  anyx1,x2∈N0,Bμ-1satisfyingx1≠x2,thereisM-B,μx1≠M-B,μx2.Since any integer in N[0,Bμ-1] can only be expressed as a μ-digit integer in base B at most, it follows from Theorem 1 that x1and x2 only are represented as a (μ+2)-digit integer in base -B at most. Without loss of generality, we expressed x1 and x2 as (μ+2)-digit integers in base -B; if the number of digits is not enough, we fill 0 in front of them, that is,(13)x1=x1,μ+1x1,μ⋯x1,0-B,x2=x2,μ+1x2,μ⋯x2,0-B,where for j=1,2 and k=0,1,…,μ+1, xj,k is possibly equal to 0. Let (14)y1=T-Bx1=∑k=0μ+1x1,kBk,y2=T-Bx2=∑k=0μ+1x2,kBk.Assume M-B,μ is not an injection; there is x1≠x2 such that M-B,μ(x1)=M-B,μ(x2), namely, y1≡y2mod⁡Bμ. Therefore, we can infer that(15)x1,k=x2,k,k=0,1,…,μ-1.Since x1≠x2 implies y1≠y2, then there must be(16)x1,μ≠x2,μorx1,μ+1≠x2,μ+1.If we can prove that (16) is not true, the fact that M-B,μ is an injective map is proven, i.e., we complete the proof of the theorem.
In accordance with (15), there is(17)x1-x2=∑k=0μ+1x1,k-Bk-∑k=0μ+1x2,k-Bk=x1,μ+1-Bμ+1+x1,μ-Bμ-x2,μ+1-Bμ+1-x2,μ-Bμ=BμBx2,μ+1-x1,μ+1+x1,μ-x2,μ.If x1,μ+1≠x2,μ+1, then, from (17), there is(18)x1-x2=BμBx2,μ+1-x1,μ+1+x1,μ-x2,μ≥BμBx2,μ+1-x1,μ+1-x1,μ-x2,μ≥BμB-x1,μ-x2,μ≥Bμ.This contradicts obviously x1,x2∈N[0,Bμ-1]; thus this shows x1,μ+1=x2,μ+1.
Ifx1,μ≠x2,μ, then, from (17) and x1,μ+1=x2,μ+1, there is(19)x1-x2=BμBx2,μ+1-x1,μ+1+x1,μ-x2,μ=Bμx1,μ-x2,μ≥Bμ.This also contradicts x1,x2∈N[0,Bμ-1] and shows that x1,μ≠x2,μ is not true. Therefore we have already completed the proof of Theorem 7.It is noteworthy that MNBT is a bijective map fromN[p,p+Bμ-1] to N[0,Bμ-1], but not from N[p,p+Bμ-1] to the set itself. If taking p=0, then MNBT is a bijective map from N[0,Bμ-1] to N[0,Bμ-1], but in this case, MNBT will map some points to themselves, i.e., the transformation periods of these points are 1, for example, M-B,μ(0)=0. Thus MNBT cannot be used directly in the application of image scrambling and need to be modified further. In fact, combining MNBT with translational transform with respect to shift p, we can obtain a permutation from N[p,p+Bμ-1] to N[p,p+Bμ-1], which is of course a bijective map.


### 3.3. Local Negative Base Transform

Local negative base transform can be constructed by combining MNBT with a translational transform with shiftp.Definition 8 (local negative base transform).
If the mapf-B,μ,p:N[p,p+Bμ-1]→N[p,p+Bμ-1] satisfies(20)f-B,μ,px=M-B,μx+p,x∈Np,p+Bμ-1,then f-B,μ,p is called local negative base transform with respect to base -B, modulo Bμ, and shift p, abbreviated as LNBT.In Definition8, f-B,μ,p is also referred to as LNBT with parameter (B,μ,p). Obviously, if p=0, LNBT is simplified as MNBT. The following corollary is easily established in accordance with Theorem 7.Corollary 9.
LNBT is a bijective map fromN[p,p+Bμ-1] to N[p,p+Bμ-1], i.e., LNBT is a permutation on N[p,p+Bμ-1].Corollary9 shows that LNBT is a scrambling transform from N[p,p+Bμ-1] to itself. Next, we describe the calculation method of LNBT, shown as the Algorithm 2.Algorithm 2:Calculating LNBT x.
Require: x% the nonnegative integer B ,  μ ,  p % the parameters of LNBT Ensure: y=f-B,μ,p(x)% the value of LNBT Remark:y%  y satisfying y=f-B,μ,p(x) x n x n - 1 ⋯ x 0=Converting baseB integer to base−B integer  an,an-1,…,a0 %  x satisfying x=∑k=0nxk-Bk y=∑k=0nxkBkmod⁡Bμ+pFor example, if we take(B,μ,p)=(2,4,1), we can calculate easily the values of LNBT according to Algorithm 2, and the calculated results as shown in Table 2, where f-2,4,1 in Table 2 is defined as (20).Table 2
The results of LNBT.
x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 f - 2,4 , 1 x 2 7 8 5 6 11 12 9 10 15 16 13 14 3 4 1It is obvious that scrambling transform LNBT can map the subsetS of N[p,p+Bμ-1] to N[p,p+Bμ-1]; moreover, LNBT can map (scatter) uniformly the entries of the subset S to the set N[p,p+Bμ-1] after many times of LNBT. Figure 1 is the result after 19 times of permutation by LNBT, and it can be seen that the black pixels have been scattered uniformly onto the entire position space of the images; especially, the effect is better in the case of implementing transformation after the image is scanned into one-dimensional sequence (the form of row vector). Generally, as long as B is even and μ is large enough, the scrambling effect is very good. When the pixels are permuted along x-direction, the positional relationship between adjacent pixels at y-direction cannot be changed. Likewise, when permuting the pixels along y-direction, the positional relationship between adjacent pixels at x-direction cannot be changed. Therefore, the pixels shuffled along x- and y-directions separately will result in the black pixels aligned, as shown in Figures 1(b) and 1(f).Figure 1
Images of size 128 × 128 and black area of size 16 × 16, 19 times of LNBT: (a) black pixels in the center of an image, (e) black pixels in the upper-left of another image; (b) and (f) are the scrambled images of (a) and (e) with parameter(2,7,1) along x- and y-direction, respectively, (c) and (g) are the scrambled images of (a) and (e) with parameter (2,14,1) after scanned into a sequence line-by-line, and (d) and (h) are the scrambled images of (a) and (e) with parameter (2,14,1) after scanned into a sequence in zigzag order.
(a) (b) (c) (d) (e) (f) (g) (h)


### 3.4. Minimum Transformation Period and Inverse Transformation

In the application of digital watermarking and image encryption, it is often necessary to restore the scrambled image. There are two kinds of methods for restoring scrambled image, that is, by inverse scrambling transform and by minimum transformation period.


#### 3.4.1. Minimum Transformation Period

Like Arnold transform, MNBT and LNBT exist transformation periods, as shown in Theorem10. In Theorem 10, we use the notations M-B,μλ1(x) and f-B,μ,pλ2(x), which are defined by(21)M-B,μkx=M-B,μM-B,μk-1x,M-B,μ1x=M-B,μx,f-B,μ,pkx=f-B,μ,pf-B,μ,pk-1x,f-B,μ,p1x=f-B,μ,px,where M-B,μ and f-B,μ,p as defined by (11) and (20).Theorem 10 (period existence theorem for LNBT and MNBT).
There exists a positive integerλ1 such that M-B,μλ1(x)=x for any x∈N[0,Bμ-1] and a positive integer λ2 such that f-B,μ,pλ2(x)=x for any x∈N[p,p+Bμ-1].Proof.
We only prove thatf-B,μ,p exists the transformation period and can also use the same method to prove M-B,μ. Since the number of entries in the set N[p,p+Bμ-1] is finite, we only prove that, for any x∈N[p,p+Bμ-1], there is λx such that f-B,μ,pλx(x)=x; in fact, the transform period of f-B,μ,p is the common multiple of all λx.
Suppose for any positive integerλ there is x0 such that f-B,μ,pλ(x0)≠x0. Let z0=f-B,μ,p(x0), for any positive integer λ, we have, from the fact that f-B,μ,p is bijective,(22)z0=f-B,μ,px0≠f-B,μ,pf-B,μ,pλx0=f-B,μ,pλ+1x0=f-B,μ,pλf-B,μ,px0=f-B,μ,pλz0.On the other hand, let yk=f-B,μ,pk(x0), k=1,2,…,Bμ, from x0,yk∈N[p,p+Bμ-1] and pigeonhole principle; we know that there is i≠j such that yi=yj. Without loss of generality, assume j>i, then from the fact that f-B,μ,p is a bijective map and f-B,μ,pi(x0)=f-B,μ,pj(x0), we can conclude f-B,μ,p(x0)=f-B,μ,pj-i+1(x0), namely, z0=f-B,μ,pj-i(z0). This contradicts (22). Therefore, there must exist a positive integer λx such that f-B,μ,pλx(x)=x. The proof of this theorem has already completed.If using the periodicity of scrambling transform to restore scrambled image, we must find the minimum transformation period of LNBT, but Theorem10 does not give a calculation method of the minimum transform period. In general, it is not easy to determine the minimum transform period of MNBT and LNBT. Table 3 is the minimum transform periods of MNBT and LNBT with(23)B,μ,p∈i,j,k:i=2,3,…,10;j=2,3,4,5;k=1,2,3,4for x∈N[p,p+Bμ-1]. For example, for (B,μ,p)=(3,2,1), the minimum transformation periods of all entries on N[1,9] are 3 and 6, respectively. Then the minimum transformation period of LNBT with parameter (B,μ,p)=(3,2,1) is 6 as shown Table 3.Table 3
Transformation periods onN[p,p+Bμ-1].
μ p B=2 B=3 B=4 B=5 B=6 B=7 B=8 B=9 B=10 2 1 4 6 16 10 36 14 64 18 100 2 2 2 6 8 10 6 14 32 18 10 2 3 4 2 16 10 12 14 64 6 100 2 4 1 6 2 10 6 14 16 18 10 3 1 8 18 64 50 216 98 512 162 1000 3 2 2 18 32 50 18 98 256 162 50 3 3 8 6 64 50 72 98 512 54 1000 3 4 2 18 4 50 18 98 128 162 50 4 1 16 18 256 50 1296 98 4096 162 10000 4 2 4 18 128 50 108 98 2048 162 500 4 3 16 6 256 50 432 98 4096 54 10000 4 4 4 18 16 50 36 98 1024 162 500 5 1 32 54 1024 250 7776 686 32768 1458 100000 5 2 8 54 512 250 648 686 16384 1458 5000 5 3 32 18 1024 250 2592 686 32768 486 100000 5 4 8 54 64 250 216 686 8192 1458 5000Looking at Table3, we can get the conclusion as shown in Proposition 11.Proposition 11.
The setN[p,p+Bμ-1] is the definition domain of LNBT, where p is nonnegative. For different B and p, there is the following conclusion.
(i) The minimum transformation periods of LNBT are not greater thanBμ. IfB=2,4,8 and p is odd, or B is even and p=1, the minimum transformation periods of LNBT is equal to Bμ.
(ii) Ifp is even, the difference between Bμ and the minimum transformation period is bigger.
(iii) IfBis odd, the difference between Bμ and the minimum transformation period is also bigger.Conclusion (i) in Proposition11 is very important, and in the application of image scrambling, we often take B as an even number and p as an odd number; especially, take p=1 and B=2. In general, the effect is better if the difference between Bμ and the minimum transformation period is smaller. In fact, Bμ is often a transformation period of LNBT with parameter (B,μ,p), but is not necessarily the minimum transformation period. For example, LNBT with parameter (-2,3,1) is a cycle on the set N[1,8], namely, 12745638, and this shows that the minimum transformation period of LNBT with parameter (-2,3,1) is equal to 8. Figure 2 is the experimental results by using minimum transformation period to restore scrambled image, where the parameter values are (2,9,1) in (b) and (c).Figure 2
Restoring scrambled images by the minimum transformation period: (a) is an original images of size 512×512; (b) is the scrambled images of (a) using 22 times of LNBT to shuffle the pixels along x- and y-direction separately; (c) is the restored image using 490 times of LNBT to permute the pixels along x- and y-direction separately from (b).
(a) (b) (c)


#### 3.4.2. Inverse Transforms of MNBT and LNBT

It is not easy to compute the minimum transformation period of MNBT and LNBT for different parameters(B,μ,p); on the other hand, although the minimum transformation period is sometimes known, but the minimum transformation period is possibly large, so that the computational complexity of restoring scrambled image becomes large. For example, if we use LNBT with parameters (2,18,1) to shuffle the pixels of an image of size 512×512 after scanned into a sequence, then the minimum transformation period is 262144. Therefore, the calculation is sometimes difficult by using the periodicity of LNBT to restore scrambled image, while the calculation of restoring scrambled image is more concise and faster by inverse transform of LNBT.Lety=T-B(x); (10) implies y=∑k=0nxkBk, i.e., y=xnxn-1⋯x0B and x=xnxn-1⋯x0-B. Thus, from (10), the inverse map T-B-1 of NBT is obtained directly, namely,(24)x=T-B-1y=∑k=0nxk-Bk,and xk satisfies the condition y=xnxn-1⋯x0B. Equation (24) tells us the process of calculation, which convert y to an integer in base B and then calculate the expression of right side in (24).Suppose the definition domain of MNBT isN[0,Bμ-1]. Next, we consider the calculation for the inverse map of y=M-B,μ(x). According to Theorem 1 and (11), we can conclude that there exists a nonnegative integer k such that T-B(x)=kBμ+y. From (24), we can get the inverse map M-B,μ-1 of MNBT, namely,(25)x=M-B,μ-1y=∑k=0nxk-Bk,where xk satisfies kBμ+y=xnxn-1⋯x0B. In order to compute x in (25), we must first determine the value of k. In fact, the selected k must make the calculated x from (25) satisfy x∈N[0,Bμ-1], and from the fact that MNBT is permutation on N[0,Bμ-1], we know that k is uniquely determined.From (25) and (20), we can get the inverse map f-B,μ,p-1 of LNBT, namely,(26)x=f-B,μ,p-1y=∑k=0nxk-Bk+p,(27)kBμ+y-p=xnxn-1⋯x0B,(28)ksatisfyingx∈Np,Bμ+p-1inEquation26.Therefore, the inverse transform x=f-B,μ,p-1(y) can be calculated from (26), (27), and (28), and the specific details are depicted as Algorithm 3.Algorithm 3:Calculating inverse transform of LNBTy.
Require: y% non-negative integer B ,  μ ,  p % the parameters of inverse LNBT Ensure: x % the value of inverse LNBT Remark: x%  x satisfying x=f-B,μ,p-1y x = - 1 k = 0 while  x<p or x>p+Bμ-1  do z = k B μ + y - p x n x n - 1 ⋯ x 0 B = z % converting z into the sequence of base B x = ∑ j = 0 n x j - B j k = k + 1 7:end whileFigure3 is the experimental results of image scrambled by LNBT and image restored by inverse LNBT, where the parameter is (2,9,1) and the size of image is 512×512. Image (b) is the scrambled image by 19 times of LNBT along x- and y-direction separately and image (c) is the restored image by 19 times of inverse transform of LNBT.Figure 3
Restoring scrambled image by 19 times of inverse map of LNBT: (a) original image of size 512×512; (b) scrambled image; (c) restored image.
(a) (b) (c)


## 3.1. Negative Base Transform

Unlike the common image scrambling transform, the scrambling transform studied in this paper is one-dimensional, which is such a transform of a certain subset of the natural numbers to the subset itself. First, we define negative base transform in the following.Definition 5 (negative base transform).
For anyx∈N, if transform T-B satisfies(10)T-Bx=∑k=0nxkBk,then T-B:N→N is referred to as negative base transform with respect to base –B, abbreviated as NBT, and B is called transformation parameter of NBT, where xk is the kth digit place of the converted integer xnxn-1⋯x0-B in base -B corresponding to x.From Definition5, we know that, for computing T-B(x), the natural number x must be converted to the form of xnxn-1⋯x0-B, and then calculate T-B(x)=∑k=0nxkBk. For example, since 7=(11011)-2, then T-2(7)=24+23+21+20=27. Table 1 gives the values of NBT with parameter -2 of the natural numbers from 0 to 15. According to Table 1, we can know that, after the natural numbers between 0 and 15 is transformed by NBT, the order of the transform T-2(x) is already different from the original order of independent variablex, and some of T-2(x) are no longer in the set {0,1,2,…,15}, e.g., T-2(7)=27.Table 1
NBT of the integers between 0 and 15 with parameter-2.
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 NBT 0 1 6 7 4 5 26 27 24 25 30 31 28 29 18 19


## 3.2. Modular Negative Base Transform

AssumeN[α,β]=x;x∈N∩[α,β] denote a subset of the natural numbers from α to β, where α,β∈N, α≤β, and N denotes the set of natural numbers. In general, Image scrambling transform is a bijective map from a finite set N[α1,β1]×N[α2,β2] to N[α1,β1]×N[α2,β2]. Unfortunately, NBT is an injective map from the set of natural numbers N to itself, but not surjective, and cannot be used directly in application of image scrambling. Hence we shall make some modifications for NBT so that the modified transform is a bijective map from N[α,β] to N[α,β]. According to the transform NBT, we shall introduce another new transform from N to N[0,Bμ-1] as follows.Definition 6 (modular negative base transform).
Forx∈N, if transform M-B,μ satisfies(11)M-B,μx=T-Bxmod⁡Bμ,then transform M-B,μ is called modular negative base transform with respect to base -B and modulo Bμ, abbreviated as MNBT, where μ is an integer greater than 0.Obviously, MNBT is a surjection fromN to N[0,Bμ-1], but not an injection. In order to make MNBT a bijection, it is necessary to restrict the definition domain of MNBT such that Theorem 7 is true in the following.Theorem 7.
If the definition domain of MNBT isN[p,p+Bμ-1], then MNBT is a bijective map from N[p,p+Bμ-1] to N[0,Bμ-1].Proof.
SupposeM-B,μ is an MNBT as defined in (11). In fact, we only need to prove that M-B,μ is injective if p=0, that is, prove that(12)for  anyx1,x2∈N0,Bμ-1satisfyingx1≠x2,thereisM-B,μx1≠M-B,μx2.Since any integer in N[0,Bμ-1] can only be expressed as a μ-digit integer in base B at most, it follows from Theorem 1 that x1and x2 only are represented as a (μ+2)-digit integer in base -B at most. Without loss of generality, we expressed x1 and x2 as (μ+2)-digit integers in base -B; if the number of digits is not enough, we fill 0 in front of them, that is,(13)x1=x1,μ+1x1,μ⋯x1,0-B,x2=x2,μ+1x2,μ⋯x2,0-B,where for j=1,2 and k=0,1,…,μ+1, xj,k is possibly equal to 0. Let (14)y1=T-Bx1=∑k=0μ+1x1,kBk,y2=T-Bx2=∑k=0μ+1x2,kBk.Assume M-B,μ is not an injection; there is x1≠x2 such that M-B,μ(x1)=M-B,μ(x2), namely, y1≡y2mod⁡Bμ. Therefore, we can infer that(15)x1,k=x2,k,k=0,1,…,μ-1.Since x1≠x2 implies y1≠y2, then there must be(16)x1,μ≠x2,μorx1,μ+1≠x2,μ+1.If we can prove that (16) is not true, the fact that M-B,μ is an injective map is proven, i.e., we complete the proof of the theorem.
In accordance with (15), there is(17)x1-x2=∑k=0μ+1x1,k-Bk-∑k=0μ+1x2,k-Bk=x1,μ+1-Bμ+1+x1,μ-Bμ-x2,μ+1-Bμ+1-x2,μ-Bμ=BμBx2,μ+1-x1,μ+1+x1,μ-x2,μ.If x1,μ+1≠x2,μ+1, then, from (17), there is(18)x1-x2=BμBx2,μ+1-x1,μ+1+x1,μ-x2,μ≥BμBx2,μ+1-x1,μ+1-x1,μ-x2,μ≥BμB-x1,μ-x2,μ≥Bμ.This contradicts obviously x1,x2∈N[0,Bμ-1]; thus this shows x1,μ+1=x2,μ+1.
Ifx1,μ≠x2,μ, then, from (17) and x1,μ+1=x2,μ+1, there is(19)x1-x2=BμBx2,μ+1-x1,μ+1+x1,μ-x2,μ=Bμx1,μ-x2,μ≥Bμ.This also contradicts x1,x2∈N[0,Bμ-1] and shows that x1,μ≠x2,μ is not true. Therefore we have already completed the proof of Theorem 7.It is noteworthy that MNBT is a bijective map fromN[p,p+Bμ-1] to N[0,Bμ-1], but not from N[p,p+Bμ-1] to the set itself. If taking p=0, then MNBT is a bijective map from N[0,Bμ-1] to N[0,Bμ-1], but in this case, MNBT will map some points to themselves, i.e., the transformation periods of these points are 1, for example, M-B,μ(0)=0. Thus MNBT cannot be used directly in the application of image scrambling and need to be modified further. In fact, combining MNBT with translational transform with respect to shift p, we can obtain a permutation from N[p,p+Bμ-1] to N[p,p+Bμ-1], which is of course a bijective map.


## 3.3. Local Negative Base Transform

Local negative base transform can be constructed by combining MNBT with a translational transform with shiftp.Definition 8 (local negative base transform).
If the mapf-B,μ,p:N[p,p+Bμ-1]→N[p,p+Bμ-1] satisfies(20)f-B,μ,px=M-B,μx+p,x∈Np,p+Bμ-1,then f-B,μ,p is called local negative base transform with respect to base -B, modulo Bμ, and shift p, abbreviated as LNBT.In Definition8, f-B,μ,p is also referred to as LNBT with parameter (B,μ,p). Obviously, if p=0, LNBT is simplified as MNBT. The following corollary is easily established in accordance with Theorem 7.Corollary 9.
LNBT is a bijective map fromN[p,p+Bμ-1] to N[p,p+Bμ-1], i.e., LNBT is a permutation on N[p,p+Bμ-1].Corollary9 shows that LNBT is a scrambling transform from N[p,p+Bμ-1] to itself. Next, we describe the calculation method of LNBT, shown as the Algorithm 2.Algorithm 2:Calculating LNBT x.
Require: x% the nonnegative integer B ,  μ ,  p % the parameters of LNBT Ensure: y=f-B,μ,p(x)% the value of LNBT Remark:y%  y satisfying y=f-B,μ,p(x) x n x n - 1 ⋯ x 0=Converting baseB integer to base−B integer  an,an-1,…,a0 %  x satisfying x=∑k=0nxk-Bk y=∑k=0nxkBkmod⁡Bμ+pFor example, if we take(B,μ,p)=(2,4,1), we can calculate easily the values of LNBT according to Algorithm 2, and the calculated results as shown in Table 2, where f-2,4,1 in Table 2 is defined as (20).Table 2
The results of LNBT.
x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 f - 2,4 , 1 x 2 7 8 5 6 11 12 9 10 15 16 13 14 3 4 1It is obvious that scrambling transform LNBT can map the subsetS of N[p,p+Bμ-1] to N[p,p+Bμ-1]; moreover, LNBT can map (scatter) uniformly the entries of the subset S to the set N[p,p+Bμ-1] after many times of LNBT. Figure 1 is the result after 19 times of permutation by LNBT, and it can be seen that the black pixels have been scattered uniformly onto the entire position space of the images; especially, the effect is better in the case of implementing transformation after the image is scanned into one-dimensional sequence (the form of row vector). Generally, as long as B is even and μ is large enough, the scrambling effect is very good. When the pixels are permuted along x-direction, the positional relationship between adjacent pixels at y-direction cannot be changed. Likewise, when permuting the pixels along y-direction, the positional relationship between adjacent pixels at x-direction cannot be changed. Therefore, the pixels shuffled along x- and y-directions separately will result in the black pixels aligned, as shown in Figures 1(b) and 1(f).Figure 1
Images of size 128 × 128 and black area of size 16 × 16, 19 times of LNBT: (a) black pixels in the center of an image, (e) black pixels in the upper-left of another image; (b) and (f) are the scrambled images of (a) and (e) with parameter(2,7,1) along x- and y-direction, respectively, (c) and (g) are the scrambled images of (a) and (e) with parameter (2,14,1) after scanned into a sequence line-by-line, and (d) and (h) are the scrambled images of (a) and (e) with parameter (2,14,1) after scanned into a sequence in zigzag order.
(a) (b) (c) (d) (e) (f) (g) (h)


## 3.4. Minimum Transformation Period and Inverse Transformation

In the application of digital watermarking and image encryption, it is often necessary to restore the scrambled image. There are two kinds of methods for restoring scrambled image, that is, by inverse scrambling transform and by minimum transformation period.


### 3.4.1. Minimum Transformation Period

Like Arnold transform, MNBT and LNBT exist transformation periods, as shown in Theorem10. In Theorem 10, we use the notations M-B,μλ1(x) and f-B,μ,pλ2(x), which are defined by(21)M-B,μkx=M-B,μM-B,μk-1x,M-B,μ1x=M-B,μx,f-B,μ,pkx=f-B,μ,pf-B,μ,pk-1x,f-B,μ,p1x=f-B,μ,px,where M-B,μ and f-B,μ,p as defined by (11) and (20).Theorem 10 (period existence theorem for LNBT and MNBT).
There exists a positive integerλ1 such that M-B,μλ1(x)=x for any x∈N[0,Bμ-1] and a positive integer λ2 such that f-B,μ,pλ2(x)=x for any x∈N[p,p+Bμ-1].Proof.
We only prove thatf-B,μ,p exists the transformation period and can also use the same method to prove M-B,μ. Since the number of entries in the set N[p,p+Bμ-1] is finite, we only prove that, for any x∈N[p,p+Bμ-1], there is λx such that f-B,μ,pλx(x)=x; in fact, the transform period of f-B,μ,p is the common multiple of all λx.
Suppose for any positive integerλ there is x0 such that f-B,μ,pλ(x0)≠x0. Let z0=f-B,μ,p(x0), for any positive integer λ, we have, from the fact that f-B,μ,p is bijective,(22)z0=f-B,μ,px0≠f-B,μ,pf-B,μ,pλx0=f-B,μ,pλ+1x0=f-B,μ,pλf-B,μ,px0=f-B,μ,pλz0.On the other hand, let yk=f-B,μ,pk(x0), k=1,2,…,Bμ, from x0,yk∈N[p,p+Bμ-1] and pigeonhole principle; we know that there is i≠j such that yi=yj. Without loss of generality, assume j>i, then from the fact that f-B,μ,p is a bijective map and f-B,μ,pi(x0)=f-B,μ,pj(x0), we can conclude f-B,μ,p(x0)=f-B,μ,pj-i+1(x0), namely, z0=f-B,μ,pj-i(z0). This contradicts (22). Therefore, there must exist a positive integer λx such that f-B,μ,pλx(x)=x. The proof of this theorem has already completed.If using the periodicity of scrambling transform to restore scrambled image, we must find the minimum transformation period of LNBT, but Theorem10 does not give a calculation method of the minimum transform period. In general, it is not easy to determine the minimum transform period of MNBT and LNBT. Table 3 is the minimum transform periods of MNBT and LNBT with(23)B,μ,p∈i,j,k:i=2,3,…,10;j=2,3,4,5;k=1,2,3,4for x∈N[p,p+Bμ-1]. For example, for (B,μ,p)=(3,2,1), the minimum transformation periods of all entries on N[1,9] are 3 and 6, respectively. Then the minimum transformation period of LNBT with parameter (B,μ,p)=(3,2,1) is 6 as shown Table 3.Table 3
Transformation periods onN[p,p+Bμ-1].
μ p B=2 B=3 B=4 B=5 B=6 B=7 B=8 B=9 B=10 2 1 4 6 16 10 36 14 64 18 100 2 2 2 6 8 10 6 14 32 18 10 2 3 4 2 16 10 12 14 64 6 100 2 4 1 6 2 10 6 14 16 18 10 3 1 8 18 64 50 216 98 512 162 1000 3 2 2 18 32 50 18 98 256 162 50 3 3 8 6 64 50 72 98 512 54 1000 3 4 2 18 4 50 18 98 128 162 50 4 1 16 18 256 50 1296 98 4096 162 10000 4 2 4 18 128 50 108 98 2048 162 500 4 3 16 6 256 50 432 98 4096 54 10000 4 4 4 18 16 50 36 98 1024 162 500 5 1 32 54 1024 250 7776 686 32768 1458 100000 5 2 8 54 512 250 648 686 16384 1458 5000 5 3 32 18 1024 250 2592 686 32768 486 100000 5 4 8 54 64 250 216 686 8192 1458 5000Looking at Table3, we can get the conclusion as shown in Proposition 11.Proposition 11.
The setN[p,p+Bμ-1] is the definition domain of LNBT, where p is nonnegative. For different B and p, there is the following conclusion.
(i) The minimum transformation periods of LNBT are not greater thanBμ. IfB=2,4,8 and p is odd, or B is even and p=1, the minimum transformation periods of LNBT is equal to Bμ.
(ii) Ifp is even, the difference between Bμ and the minimum transformation period is bigger.
(iii) IfBis odd, the difference between Bμ and the minimum transformation period is also bigger.Conclusion (i) in Proposition11 is very important, and in the application of image scrambling, we often take B as an even number and p as an odd number; especially, take p=1 and B=2. In general, the effect is better if the difference between Bμ and the minimum transformation period is smaller. In fact, Bμ is often a transformation period of LNBT with parameter (B,μ,p), but is not necessarily the minimum transformation period. For example, LNBT with parameter (-2,3,1) is a cycle on the set N[1,8], namely, 12745638, and this shows that the minimum transformation period of LNBT with parameter (-2,3,1) is equal to 8. Figure 2 is the experimental results by using minimum transformation period to restore scrambled image, where the parameter values are (2,9,1) in (b) and (c).Figure 2
Restoring scrambled images by the minimum transformation period: (a) is an original images of size 512×512; (b) is the scrambled images of (a) using 22 times of LNBT to shuffle the pixels along x- and y-direction separately; (c) is the restored image using 490 times of LNBT to permute the pixels along x- and y-direction separately from (b).
(a) (b) (c)


### 3.4.2. Inverse Transforms of MNBT and LNBT

It is not easy to compute the minimum transformation period of MNBT and LNBT for different parameters(B,μ,p); on the other hand, although the minimum transformation period is sometimes known, but the minimum transformation period is possibly large, so that the computational complexity of restoring scrambled image becomes large. For example, if we use LNBT with parameters (2,18,1) to shuffle the pixels of an image of size 512×512 after scanned into a sequence, then the minimum transformation period is 262144. Therefore, the calculation is sometimes difficult by using the periodicity of LNBT to restore scrambled image, while the calculation of restoring scrambled image is more concise and faster by inverse transform of LNBT.Lety=T-B(x); (10) implies y=∑k=0nxkBk, i.e., y=xnxn-1⋯x0B and x=xnxn-1⋯x0-B. Thus, from (10), the inverse map T-B-1 of NBT is obtained directly, namely,(24)x=T-B-1y=∑k=0nxk-Bk,and xk satisfies the condition y=xnxn-1⋯x0B. Equation (24) tells us the process of calculation, which convert y to an integer in base B and then calculate the expression of right side in (24).Suppose the definition domain of MNBT isN[0,Bμ-1]. Next, we consider the calculation for the inverse map of y=M-B,μ(x). According to Theorem 1 and (11), we can conclude that there exists a nonnegative integer k such that T-B(x)=kBμ+y. From (24), we can get the inverse map M-B,μ-1 of MNBT, namely,(25)x=M-B,μ-1y=∑k=0nxk-Bk,where xk satisfies kBμ+y=xnxn-1⋯x0B. In order to compute x in (25), we must first determine the value of k. In fact, the selected k must make the calculated x from (25) satisfy x∈N[0,Bμ-1], and from the fact that MNBT is permutation on N[0,Bμ-1], we know that k is uniquely determined.From (25) and (20), we can get the inverse map f-B,μ,p-1 of LNBT, namely,(26)x=f-B,μ,p-1y=∑k=0nxk-Bk+p,(27)kBμ+y-p=xnxn-1⋯x0B,(28)ksatisfyingx∈Np,Bμ+p-1inEquation26.Therefore, the inverse transform x=f-B,μ,p-1(y) can be calculated from (26), (27), and (28), and the specific details are depicted as Algorithm 3.Algorithm 3:Calculating inverse transform of LNBTy.
Require: y% non-negative integer B ,  μ ,  p % the parameters of inverse LNBT Ensure: x % the value of inverse LNBT Remark: x%  x satisfying x=f-B,μ,p-1y x = - 1 k = 0 while  x<p or x>p+Bμ-1  do z = k B μ + y - p x n x n - 1 ⋯ x 0 B = z % converting z into the sequence of base B x = ∑ j = 0 n x j - B j k = k + 1 7:end whileFigure3 is the experimental results of image scrambled by LNBT and image restored by inverse LNBT, where the parameter is (2,9,1) and the size of image is 512×512. Image (b) is the scrambled image by 19 times of LNBT along x- and y-direction separately and image (c) is the restored image by 19 times of inverse transform of LNBT.Figure 3
Restoring scrambled image by 19 times of inverse map of LNBT: (a) original image of size 512×512; (b) scrambled image; (c) restored image.
(a) (b) (c)


## 3.4.1. Minimum Transformation Period

Like Arnold transform, MNBT and LNBT exist transformation periods, as shown in Theorem10. In Theorem 10, we use the notations M-B,μλ1(x) and f-B,μ,pλ2(x), which are defined by(21)M-B,μkx=M-B,μM-B,μk-1x,M-B,μ1x=M-B,μx,f-B,μ,pkx=f-B,μ,pf-B,μ,pk-1x,f-B,μ,p1x=f-B,μ,px,where M-B,μ and f-B,μ,p as defined by (11) and (20).Theorem 10 (period existence theorem for LNBT and MNBT).
There exists a positive integerλ1 such that M-B,μλ1(x)=x for any x∈N[0,Bμ-1] and a positive integer λ2 such that f-B,μ,pλ2(x)=x for any x∈N[p,p+Bμ-1].Proof.
We only prove thatf-B,μ,p exists the transformation period and can also use the same method to prove M-B,μ. Since the number of entries in the set N[p,p+Bμ-1] is finite, we only prove that, for any x∈N[p,p+Bμ-1], there is λx such that f-B,μ,pλx(x)=x; in fact, the transform period of f-B,μ,p is the common multiple of all λx.
Suppose for any positive integerλ there is x0 such that f-B,μ,pλ(x0)≠x0. Let z0=f-B,μ,p(x0), for any positive integer λ, we have, from the fact that f-B,μ,p is bijective,(22)z0=f-B,μ,px0≠f-B,μ,pf-B,μ,pλx0=f-B,μ,pλ+1x0=f-B,μ,pλf-B,μ,px0=f-B,μ,pλz0.On the other hand, let yk=f-B,μ,pk(x0), k=1,2,…,Bμ, from x0,yk∈N[p,p+Bμ-1] and pigeonhole principle; we know that there is i≠j such that yi=yj. Without loss of generality, assume j>i, then from the fact that f-B,μ,p is a bijective map and f-B,μ,pi(x0)=f-B,μ,pj(x0), we can conclude f-B,μ,p(x0)=f-B,μ,pj-i+1(x0), namely, z0=f-B,μ,pj-i(z0). This contradicts (22). Therefore, there must exist a positive integer λx such that f-B,μ,pλx(x)=x. The proof of this theorem has already completed.If using the periodicity of scrambling transform to restore scrambled image, we must find the minimum transformation period of LNBT, but Theorem10 does not give a calculation method of the minimum transform period. In general, it is not easy to determine the minimum transform period of MNBT and LNBT. Table 3 is the minimum transform periods of MNBT and LNBT with(23)B,μ,p∈i,j,k:i=2,3,…,10;j=2,3,4,5;k=1,2,3,4for x∈N[p,p+Bμ-1]. For example, for (B,μ,p)=(3,2,1), the minimum transformation periods of all entries on N[1,9] are 3 and 6, respectively. Then the minimum transformation period of LNBT with parameter (B,μ,p)=(3,2,1) is 6 as shown Table 3.Table 3
Transformation periods onN[p,p+Bμ-1].
μ p B=2 B=3 B=4 B=5 B=6 B=7 B=8 B=9 B=10 2 1 4 6 16 10 36 14 64 18 100 2 2 2 6 8 10 6 14 32 18 10 2 3 4 2 16 10 12 14 64 6 100 2 4 1 6 2 10 6 14 16 18 10 3 1 8 18 64 50 216 98 512 162 1000 3 2 2 18 32 50 18 98 256 162 50 3 3 8 6 64 50 72 98 512 54 1000 3 4 2 18 4 50 18 98 128 162 50 4 1 16 18 256 50 1296 98 4096 162 10000 4 2 4 18 128 50 108 98 2048 162 500 4 3 16 6 256 50 432 98 4096 54 10000 4 4 4 18 16 50 36 98 1024 162 500 5 1 32 54 1024 250 7776 686 32768 1458 100000 5 2 8 54 512 250 648 686 16384 1458 5000 5 3 32 18 1024 250 2592 686 32768 486 100000 5 4 8 54 64 250 216 686 8192 1458 5000Looking at Table3, we can get the conclusion as shown in Proposition 11.Proposition 11.
The setN[p,p+Bμ-1] is the definition domain of LNBT, where p is nonnegative. For different B and p, there is the following conclusion.
(i) The minimum transformation periods of LNBT are not greater thanBμ. IfB=2,4,8 and p is odd, or B is even and p=1, the minimum transformation periods of LNBT is equal to Bμ.
(ii) Ifp is even, the difference between Bμ and the minimum transformation period is bigger.
(iii) IfBis odd, the difference between Bμ and the minimum transformation period is also bigger.Conclusion (i) in Proposition11 is very important, and in the application of image scrambling, we often take B as an even number and p as an odd number; especially, take p=1 and B=2. In general, the effect is better if the difference between Bμ and the minimum transformation period is smaller. In fact, Bμ is often a transformation period of LNBT with parameter (B,μ,p), but is not necessarily the minimum transformation period. For example, LNBT with parameter (-2,3,1) is a cycle on the set N[1,8], namely, 12745638, and this shows that the minimum transformation period of LNBT with parameter (-2,3,1) is equal to 8. Figure 2 is the experimental results by using minimum transformation period to restore scrambled image, where the parameter values are (2,9,1) in (b) and (c).Figure 2
Restoring scrambled images by the minimum transformation period: (a) is an original images of size 512×512; (b) is the scrambled images of (a) using 22 times of LNBT to shuffle the pixels along x- and y-direction separately; (c) is the restored image using 490 times of LNBT to permute the pixels along x- and y-direction separately from (b).
(a) (b) (c)


## 3.4.2. Inverse Transforms of MNBT and LNBT

It is not easy to compute the minimum transformation period of MNBT and LNBT for different parameters(B,μ,p); on the other hand, although the minimum transformation period is sometimes known, but the minimum transformation period is possibly large, so that the computational complexity of restoring scrambled image becomes large. For example, if we use LNBT with parameters (2,18,1) to shuffle the pixels of an image of size 512×512 after scanned into a sequence, then the minimum transformation period is 262144. Therefore, the calculation is sometimes difficult by using the periodicity of LNBT to restore scrambled image, while the calculation of restoring scrambled image is more concise and faster by inverse transform of LNBT.Lety=T-B(x); (10) implies y=∑k=0nxkBk, i.e., y=xnxn-1⋯x0B and x=xnxn-1⋯x0-B. Thus, from (10), the inverse map T-B-1 of NBT is obtained directly, namely,(24)x=T-B-1y=∑k=0nxk-Bk,and xk satisfies the condition y=xnxn-1⋯x0B. Equation (24) tells us the process of calculation, which convert y to an integer in base B and then calculate the expression of right side in (24).Suppose the definition domain of MNBT isN[0,Bμ-1]. Next, we consider the calculation for the inverse map of y=M-B,μ(x). According to Theorem 1 and (11), we can conclude that there exists a nonnegative integer k such that T-B(x)=kBμ+y. From (24), we can get the inverse map M-B,μ-1 of MNBT, namely,(25)x=M-B,μ-1y=∑k=0nxk-Bk,where xk satisfies kBμ+y=xnxn-1⋯x0B. In order to compute x in (25), we must first determine the value of k. In fact, the selected k must make the calculated x from (25) satisfy x∈N[0,Bμ-1], and from the fact that MNBT is permutation on N[0,Bμ-1], we know that k is uniquely determined.From (25) and (20), we can get the inverse map f-B,μ,p-1 of LNBT, namely,(26)x=f-B,μ,p-1y=∑k=0nxk-Bk+p,(27)kBμ+y-p=xnxn-1⋯x0B,(28)ksatisfyingx∈Np,Bμ+p-1inEquation26.Therefore, the inverse transform x=f-B,μ,p-1(y) can be calculated from (26), (27), and (28), and the specific details are depicted as Algorithm 3.Algorithm 3:Calculating inverse transform of LNBTy.
Require: y% non-negative integer B ,  μ ,  p % the parameters of inverse LNBT Ensure: x % the value of inverse LNBT Remark: x%  x satisfying x=f-B,μ,p-1y x = - 1 k = 0 while  x<p or x>p+Bμ-1  do z = k B μ + y - p x n x n - 1 ⋯ x 0 B = z % converting z into the sequence of base B x = ∑ j = 0 n x j - B j k = k + 1 7:end whileFigure3 is the experimental results of image scrambled by LNBT and image restored by inverse LNBT, where the parameter is (2,9,1) and the size of image is 512×512. Image (b) is the scrambled image by 19 times of LNBT along x- and y-direction separately and image (c) is the restored image by 19 times of inverse transform of LNBT.Figure 3
Restoring scrambled image by 19 times of inverse map of LNBT: (a) original image of size 512×512; (b) scrambled image; (c) restored image.
(a) (b) (c)


## 4. Experiments of Image Scrambling

### 4.1. Scrambling along X- and Y-Direction Separately

Unlike Arnold transform, LNBT is a bijective map from the definition domainN[p,p+Bμ-1] to definition domain itself, and if using LNBT to shuffle two-dimension image, we can permute the pixels of image along x- and y-direction. Selection of parameter (B,μ,p) is relation to the size of image to be scrambled; suppose the size of image is M×N, we should select Byμy=M at y-direction and Bxμx=N at x-direction and take p as an odd number. For example, Figure 4(a) is an image of size 216×256; then we can select the parameter (2,8,1) at x-direction and (6,3,1) at y-direction. Figure 4(e) is another image of size 256×256; then we can select the same parameter (2,8,1) both x- and y-direction. From Figure 4, we find that the scrambled pixels are aligned along x- and y-direction, respectively.Figure 4
Image scrambling along x- and y-direction separately: (a) original image of size 216×256; (e) original image of size 256×256; (b), (c), and (d) scrambled images from (a) by once, 9 times and 25 times of LNBT, respectively; (f), (g), and (h) from (e) by once, 9 times, and 25 times of LNBT, respectively.
(a) (b) (c) (d) (e) (f) (g) (h)


### 4.2. Scrambling after Scanned into a Sequence

(i) Scan Line-by-Line.In order to eliminate the alignment phenomenon of pixels as described above after image was scrambled along x- and y-direction separately, the easiest method is that we use LNBT to permute the sequence of pixels after two-dimensional image is scanned into a one-dimensional sequence line-by-line. Figure 5(a) is an image of size 216×216, and after being scanned into a one-dimensional vector, the length of the corresponding one-dimension vector is 66; thus we select the parameter (6,6,1) to shuffle the pixels. Figure 5(e) is another image of size 256×256, and we can select the parameter (2,16,1) to shuffle the pixels after being scanned into a one-dimension vector. From Figures 4 and 5, we find that the smaller the parameter B is, the better the scrambling effect is.Figure 5
Image scrambling after scanned into a sequence line-by-line: (a) original image of 216×216; (e) original image of 256×256; (b), (c), and (d) scrambled images from (a) by once, 10 times, and 25 times of LNBT with parameter (6,6,1), respectively; (f), (g), and (h) scrambled images of (e) by once, 10 times, and 25 times of LNBT with parameter (2,16,1), respectively.
(a) (b) (c) (d) (e) (f) (g) (h)(  2) Scan in Zigzag Order. After scanning a two-dimension image into a sequence of pixels line-by-line, if taking B=2 we can obtain a good scrambling result by many times of LNBT, as shown in Figure 5(h), but if selecting B=6, the scrambling effect is not very good. In Figure 6, we first use the zigzag scan technique to change a two-dimension image into the corresponding one-dimension vector and then use LNBT to permute this sequence of pixels; last, we use the same zigzag order to arrange the scrambled sequence and obtain the corresponding scrambled image. Compared with Figure 5, we find the effect of image scrambling becomes better in Figure 6.Figure 6
Image scrambling after scanned into a row in zigzag order: (a) original image of size 216×216; (e) original image of size 256×256, (b), (c), and (d) scrambled images of (a) by 1-time, 10-time and 39-time of LNBT with parameter (6,6,1), respectively; (f), (g), and (h) scrambled images of (e) by 1 time, 10 times, and 39 times of LNBT with parameter (2,16,1), respectively.
(a) (b) (c) (d) (e) (f) (g) (h)


### 4.3. Irregular Region Scrambling of Image

We consider two cases that the size of image cannot express as the form ofB1μ1×B2μ2 and the image region to be shuffled is irregular. Since LNBT is a kind of one-dimensional scrambling transform from N[p,p+Bμ-1] to N[p,p+Bμ-1], if using LNBT to permute two-dimensional image, we must change the image into the corresponding one-dimensional sequence of pixels, and then we permute the sequence of pixels; of course, we can also permute an image along the horizontal and vertical direction separately. Therefore, we can shuffle image region of any shape and images of any size. In the application of part information hiding and encryption of image (e.g., sensitive area scrambling) [30–32], unlike Arnold transform, LNBT can shuffle image region of any shape.(i) Case  1: Irregular Size.If the size of image cannot be expressed as the form of B1μ1×B2μ2, we cannot use directly LNBT with parameter B1,μ1,p1 to permute the x-coordinate and with parameter B2,μ2,p2 to permute the y-coordinate. Therefore, such size of image is called irregular size in this paper. Suppose the size of an image is M×N, and for any positive integers B1 and μ1 satisfying M≠B1μ1 or any positive integers B2 and μ2 satisfying N≠B2μ2. Without loss of generality, we suppose M cannot be expressed as the form of Bμ, then there exist Bx, μx, X, and Rx such that M=X×Bxμx+Rx where 1≤Rx<Bxμx and thus the set N[1,M] can be divided into X+1 subsets. For the first X subsets, we select LNBT of parameters Bx,μx,k to shuffle N[αBxμx+1,(α+1)Bxμx] where k=αBxμx+1, α=0,1,…,X-1. For the last subset N[XBxμx+1,M], first, extend the left end of N[XBxμx+1,M] to N[M-XBxμx+1,M]; then shuffle the extended subset N[M-XBxμx+1,M] after the first X subsets were shuffled. Figure 7 is the scrambling result of the image of size 720×648. First, permute x-coordinate between 1 and 512 as shown in Figure 7(b), and next, permute x-coordinate between 209 and 720 as shown in Figure 7(c). The results of permuting y-coordinates are shown in Figures 7(d) and 7(e).Figure 7
Scrambling image of irregular size by 20 times of LNBT with (2, 9,p): (a) original image of size 720×648; (b) permuting x-coordinate withp=1; (c) permuting x-coordinate withp=209; (d) permuting y-coordinatep=1; (e) permuting y-coordinate withp=137.
(a) (b) (c) (d) (e)(  2) Case  2: Irregular Shape. Sometimes we require shuffling a certain region of image [30–32]; in this case, the region to be shuffled may be irregular with respect to size or shape, and therefore it is difficult for two-dimensional scrambling transform to shuffle such irregular region. Unlike Arnold transform, baker map, John Conway game, knight’s tour, magic square transform, and Peano-Hilbert curve, LNBT can be exploited to shuffle region with irregular shape of image, and specific operations are divided into two steps. First, the pixels of the region of image to be scrambled are scanned as one-dimensional sequence; second, use the above scrambling method for irregular size to shuffle the one-dimensional sequence. In Figure 8, we scan the pixels of image region into one-dimensional sequence and then permute these pixels of the sequence. Figure 8 is the results of three shapes by 19 times of LNBT.Figure 8
Scrambling the face region of Lena image, (a) diamond-shaped region, (b) triangular region, and (c) rectangular region.
(a) (b) (c)


### 4.4. Scrambling on Bit Plane along x- and y-Direction

Permuting the pixel position of an image can only destroy the correlation of adjacent pixels but cannot change the statistical properties of the image, such as histogram and information entropy. This is because scrambling transform based on pixels cannot change the gray value of pixels. If the binary bits of the image pixels are scrambled, it can cause the pixel values to change and thereby can change the statistical properties of the image. If we use binary number of 8 bits to express the value of a pixel, then we can use 0 and 1 to represent a certain image. Therefore the size of a gray image ofM×N is 8×M×N and each pixel can be represented by binary block of size 2 × 4 or 4 × 2, 1 × 8, 8 × 1. For example, if we use a binary block of 2 × 4 to express a pixel of a gray image of size M×N, we can get a binary matrix of size (2×M)×(4×N), and then use LNBT to permute the position of 0 and 1 in the binary matrix corresponding to the gray image. In Figure 9, we first convert original image to a binary matrix where the size of binary block of a pixel is 2 × 4; next, apply LNBT to shuffle the binary matrix along x- and y-direction separately; finally, we convert the scrambled binary matrix to a scrambled image, i.e., a binary block of size 2×4 is converted to a pixel. From Figure 9, we see that the scrambling transform based on bit plane not only makes the scrambled image meaningless but also changes the statistical properties of the original image. Thus this shows that LNBT is also a tool of image encryption.Figure 9
Image scrambling on bit plane by LNBT along x- and y-direction: (a) original image of 512×512l; (b) scrambled image from (a) by 11 times of LNBT at x- and y-direction; (c) scrambled image from (a) by 15 times of LNBT at y-direction and 19 times at x-direction; (d) histogram of (a); (e) histogram of (b); (f) histogram of (c).
(a) (b) (c) (d) (e) (f)


### 4.5. Digital Watermarking against Cropping Attack

In the robust watermarking of digital images, image scrambling is a powerful method for resisting cropping attack. LSB (least significant bit) algorithm is a simple digital watermarking technology, but as a large amount of data hiding method, LSB has a significant position. Figure10 is the experimental result of combining LNBT with LSB algorithm. The implementation process is as follows. First, use 19 times of LNBT to shuffle the carrier image, then embed the bits of the watermark image into the least significant bits of the scrambled carrier image, and finally, use the inverse transform of LNBT to obtain the watermarked image (b). Images (e), (g), (i), and (k) are the extracted watermarks from the watermarked imaged after attacked by cropping, and Figure 10 shows that LNBT is effective against cropping attack.Figure 10
Watermarking experiment based on LNBT and LSB: (a) original image; (b) watermarked image; (c) watermark image, (d), (f), (h), and (j) attacked images by cropping; (e), (g), (j), and (k) watermarks extracted from the attacked watermarked images.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k)


## 4.1. Scrambling along X- and Y-Direction Separately

Unlike Arnold transform, LNBT is a bijective map from the definition domainN[p,p+Bμ-1] to definition domain itself, and if using LNBT to shuffle two-dimension image, we can permute the pixels of image along x- and y-direction. Selection of parameter (B,μ,p) is relation to the size of image to be scrambled; suppose the size of image is M×N, we should select Byμy=M at y-direction and Bxμx=N at x-direction and take p as an odd number. For example, Figure 4(a) is an image of size 216×256; then we can select the parameter (2,8,1) at x-direction and (6,3,1) at y-direction. Figure 4(e) is another image of size 256×256; then we can select the same parameter (2,8,1) both x- and y-direction. From Figure 4, we find that the scrambled pixels are aligned along x- and y-direction, respectively.Figure 4
Image scrambling along x- and y-direction separately: (a) original image of size 216×256; (e) original image of size 256×256; (b), (c), and (d) scrambled images from (a) by once, 9 times and 25 times of LNBT, respectively; (f), (g), and (h) from (e) by once, 9 times, and 25 times of LNBT, respectively.
(a) (b) (c) (d) (e) (f) (g) (h)


## 4.2. Scrambling after Scanned into a Sequence

(i) Scan Line-by-Line.In order to eliminate the alignment phenomenon of pixels as described above after image was scrambled along x- and y-direction separately, the easiest method is that we use LNBT to permute the sequence of pixels after two-dimensional image is scanned into a one-dimensional sequence line-by-line. Figure 5(a) is an image of size 216×216, and after being scanned into a one-dimensional vector, the length of the corresponding one-dimension vector is 66; thus we select the parameter (6,6,1) to shuffle the pixels. Figure 5(e) is another image of size 256×256, and we can select the parameter (2,16,1) to shuffle the pixels after being scanned into a one-dimension vector. From Figures 4 and 5, we find that the smaller the parameter B is, the better the scrambling effect is.Figure 5
Image scrambling after scanned into a sequence line-by-line: (a) original image of 216×216; (e) original image of 256×256; (b), (c), and (d) scrambled images from (a) by once, 10 times, and 25 times of LNBT with parameter (6,6,1), respectively; (f), (g), and (h) scrambled images of (e) by once, 10 times, and 25 times of LNBT with parameter (2,16,1), respectively.
(a) (b) (c) (d) (e) (f) (g) (h)(  2) Scan in Zigzag Order. After scanning a two-dimension image into a sequence of pixels line-by-line, if taking B=2 we can obtain a good scrambling result by many times of LNBT, as shown in Figure 5(h), but if selecting B=6, the scrambling effect is not very good. In Figure 6, we first use the zigzag scan technique to change a two-dimension image into the corresponding one-dimension vector and then use LNBT to permute this sequence of pixels; last, we use the same zigzag order to arrange the scrambled sequence and obtain the corresponding scrambled image. Compared with Figure 5, we find the effect of image scrambling becomes better in Figure 6.Figure 6
Image scrambling after scanned into a row in zigzag order: (a) original image of size 216×216; (e) original image of size 256×256, (b), (c), and (d) scrambled images of (a) by 1-time, 10-time and 39-time of LNBT with parameter (6,6,1), respectively; (f), (g), and (h) scrambled images of (e) by 1 time, 10 times, and 39 times of LNBT with parameter (2,16,1), respectively.
(a) (b) (c) (d) (e) (f) (g) (h)


## 4.3. Irregular Region Scrambling of Image

We consider two cases that the size of image cannot express as the form ofB1μ1×B2μ2 and the image region to be shuffled is irregular. Since LNBT is a kind of one-dimensional scrambling transform from N[p,p+Bμ-1] to N[p,p+Bμ-1], if using LNBT to permute two-dimensional image, we must change the image into the corresponding one-dimensional sequence of pixels, and then we permute the sequence of pixels; of course, we can also permute an image along the horizontal and vertical direction separately. Therefore, we can shuffle image region of any shape and images of any size. In the application of part information hiding and encryption of image (e.g., sensitive area scrambling) [30–32], unlike Arnold transform, LNBT can shuffle image region of any shape.(i) Case  1: Irregular Size.If the size of image cannot be expressed as the form of B1μ1×B2μ2, we cannot use directly LNBT with parameter B1,μ1,p1 to permute the x-coordinate and with parameter B2,μ2,p2 to permute the y-coordinate. Therefore, such size of image is called irregular size in this paper. Suppose the size of an image is M×N, and for any positive integers B1 and μ1 satisfying M≠B1μ1 or any positive integers B2 and μ2 satisfying N≠B2μ2. Without loss of generality, we suppose M cannot be expressed as the form of Bμ, then there exist Bx, μx, X, and Rx such that M=X×Bxμx+Rx where 1≤Rx<Bxμx and thus the set N[1,M] can be divided into X+1 subsets. For the first X subsets, we select LNBT of parameters Bx,μx,k to shuffle N[αBxμx+1,(α+1)Bxμx] where k=αBxμx+1, α=0,1,…,X-1. For the last subset N[XBxμx+1,M], first, extend the left end of N[XBxμx+1,M] to N[M-XBxμx+1,M]; then shuffle the extended subset N[M-XBxμx+1,M] after the first X subsets were shuffled. Figure 7 is the scrambling result of the image of size 720×648. First, permute x-coordinate between 1 and 512 as shown in Figure 7(b), and next, permute x-coordinate between 209 and 720 as shown in Figure 7(c). The results of permuting y-coordinates are shown in Figures 7(d) and 7(e).Figure 7
Scrambling image of irregular size by 20 times of LNBT with (2, 9,p): (a) original image of size 720×648; (b) permuting x-coordinate withp=1; (c) permuting x-coordinate withp=209; (d) permuting y-coordinatep=1; (e) permuting y-coordinate withp=137.
(a) (b) (c) (d) (e)(  2) Case  2: Irregular Shape. Sometimes we require shuffling a certain region of image [30–32]; in this case, the region to be shuffled may be irregular with respect to size or shape, and therefore it is difficult for two-dimensional scrambling transform to shuffle such irregular region. Unlike Arnold transform, baker map, John Conway game, knight’s tour, magic square transform, and Peano-Hilbert curve, LNBT can be exploited to shuffle region with irregular shape of image, and specific operations are divided into two steps. First, the pixels of the region of image to be scrambled are scanned as one-dimensional sequence; second, use the above scrambling method for irregular size to shuffle the one-dimensional sequence. In Figure 8, we scan the pixels of image region into one-dimensional sequence and then permute these pixels of the sequence. Figure 8 is the results of three shapes by 19 times of LNBT.Figure 8
Scrambling the face region of Lena image, (a) diamond-shaped region, (b) triangular region, and (c) rectangular region.
(a) (b) (c)


## 4.4. Scrambling on Bit Plane along x- and y-Direction

Permuting the pixel position of an image can only destroy the correlation of adjacent pixels but cannot change the statistical properties of the image, such as histogram and information entropy. This is because scrambling transform based on pixels cannot change the gray value of pixels. If the binary bits of the image pixels are scrambled, it can cause the pixel values to change and thereby can change the statistical properties of the image. If we use binary number of 8 bits to express the value of a pixel, then we can use 0 and 1 to represent a certain image. Therefore the size of a gray image ofM×N is 8×M×N and each pixel can be represented by binary block of size 2 × 4 or 4 × 2, 1 × 8, 8 × 1. For example, if we use a binary block of 2 × 4 to express a pixel of a gray image of size M×N, we can get a binary matrix of size (2×M)×(4×N), and then use LNBT to permute the position of 0 and 1 in the binary matrix corresponding to the gray image. In Figure 9, we first convert original image to a binary matrix where the size of binary block of a pixel is 2 × 4; next, apply LNBT to shuffle the binary matrix along x- and y-direction separately; finally, we convert the scrambled binary matrix to a scrambled image, i.e., a binary block of size 2×4 is converted to a pixel. From Figure 9, we see that the scrambling transform based on bit plane not only makes the scrambled image meaningless but also changes the statistical properties of the original image. Thus this shows that LNBT is also a tool of image encryption.Figure 9
Image scrambling on bit plane by LNBT along x- and y-direction: (a) original image of 512×512l; (b) scrambled image from (a) by 11 times of LNBT at x- and y-direction; (c) scrambled image from (a) by 15 times of LNBT at y-direction and 19 times at x-direction; (d) histogram of (a); (e) histogram of (b); (f) histogram of (c).
(a) (b) (c) (d) (e) (f)


## 4.5. Digital Watermarking against Cropping Attack

In the robust watermarking of digital images, image scrambling is a powerful method for resisting cropping attack. LSB (least significant bit) algorithm is a simple digital watermarking technology, but as a large amount of data hiding method, LSB has a significant position. Figure10 is the experimental result of combining LNBT with LSB algorithm. The implementation process is as follows. First, use 19 times of LNBT to shuffle the carrier image, then embed the bits of the watermark image into the least significant bits of the scrambled carrier image, and finally, use the inverse transform of LNBT to obtain the watermarked image (b). Images (e), (g), (i), and (k) are the extracted watermarks from the watermarked imaged after attacked by cropping, and Figure 10 shows that LNBT is effective against cropping attack.Figure 10
Watermarking experiment based on LNBT and LSB: (a) original image; (b) watermarked image; (c) watermark image, (d), (f), (h), and (j) attacked images by cropping; (e), (g), (j), and (k) watermarks extracted from the attacked watermarked images.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k)


## 5. Analysis and Conclusions

### 5.1. Correlations between Adjacent Pixels

The goal of image scrambling is to remove the correlation between the pixels of a plaintext image, and therefore the correlation value between adjacent pixels of image is an important index for evaluating the performance of the image scrambling algorithm. Assuming thatxn and yn are two sequences consisted of horizontal or vertical or diagonally adjacent pixels, their correlation value can be calculated by [6](29)Corr=N∑i=1Nxi×yi-∑i=1Nxi×∑i=1NyiN∑i=1Nxi2-∑i=1Nxi2×N∑i=1Nyi2-∑i=1Nyi2where N is the length of sequences. Obviously, if the correlation value is close to 1, it indicates that there is a higher correlation between adjacent pixels. If the correlation value is close to 0, then the two adjacent pixel sequences have a lower correlation. Therefore, the smaller the correlation value is, the better the performance of the scrambling algorithm is.To measure the performance of LNBT scrambling algorithm by using the correlation values of neighboring pixel sequences. First, we use other common scrambling algorithms and the proposed algorithm in this paper to perform a 32-round scrambling transformation on the Lena image. Then pick out the largest value of GDD (see Section5.2) in the 32-round transforms as the last results of each scrambling algorithm for comparison. Finally, we randomly select 5000 pairs of horizontally adjacent pixels, vertically adjacent pixels, and diagonally adjacent pixels and then calculate the correlation values of the neighboring pixel sequences of the three directions in the original image and the correlation values of the three directions in the scrambled images, respectively. Columns 4, 5, and 6 of Table 4 are correlation values of adjacent pixel sequences of the three directions in the original image and in the scrambled images, where LNBT-1 denotes the LNBT scrambling algorithm of permuting separately along x- and y-direction; LNBT-2 denotes the LNBT scrambling algorithm after scanned line-by-line; LNBT-3 denotes the LNBT scrambling algorithm after scanned in zigzag order. We can know from Table 4 that the LNBT scrambling transform can successfully remove the correlation between adjacent pixels. Figures 11(a), 11(b), and 11(c) display the gray-scale distributions of 5000 pairs of horizontally adjacent pixels, of vertically adjacent pixels, and of diagonally adjacent pixels, respectively, which are selected randomly from original image. (d), (e), and (f) are the gray-scale distributions of an adjacent pixel sequence pairs for horizontal, vertical and diagonal directions in the scrambled image using LNBT-1; (g), (h), and (i) show the gray distributions of an adjacent pixel sequence pairs for the three directions in the scrambled image using LNBT-2; (j), (k), and (l) are the gray-scale distributions using LNBT-3. The results of Table 4 and Figure 11 show that LNBT can successfully remove the correlation between adjacent pixels of plaintext imageTable 4
GDD and correlation values.
Method name rounds GDD Correlation values Horizontal Vertical Diagonal Original image ∖ ∖ 0.9273 0.9590 0.9062 2D Arnold [10] 6 0.8995 0.1239 0.06369 0.0003 Discrete Baker map [26] 11 0.8972 0.0696 0.0384 0.0483 Sub-affine [27] 13 0.8985 0.0807 0.0921 0.0071 CA [15] 13 0.8908 0.0114 0.0270 0.0080 Fibonacci-Q [10] 32 0.7280 0.2968 0.9570 0.3012 Hilbert curve [19] 19 0.8910 0.0083 0.0013 0.0146 Magic cube [9] 27 0.8959 0.0670 0.0514 0.1107 2×2 sampling [28] 1 ∗ 0.8957 0.1225 0.0352 0.0770 LNBT-1 32 ∗ 0.8864 0.0749 0.1456 0.0431 LNBT-2 32 0.8884 0.0323 0.0170 0.0016 LNBT-3 24 0.8909 0.00005 0.0227 0.0057 ∗Remark: visually, the scrambling performance of the third round of 2x2 sampling transform is best, and the 29th round of LNBT-1 has the best scrambling effect. Figures 12(i) and 12(j) are the scrambled images of the third round of 2x2 sampling transform and of the 29th round of LNBT-1, respectively.Figure 11
Gray-scale distributions of adjacent pixel sequence pairs: (a) horizontal of original image, (b) vertical of original image, (c) diagonal of original image, (d) horizontal of scrambled image using LNBT-1, (e) vertical of scrambled image using LNBT-1, (f) diagonal of scrambled image using LNBT-1, (g) horizontal of scrambled image using LNBT-2, (h) vertical of scrambled image using LNBT-2, (i) diagonal of scrambled image using LNBT-2, (j) horizontal of scrambled image using LNBT-3, (k) vertical of scrambled image using LNBT-3, and (l) diagonal of scrambled image using LNBT-3.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l)


### 5.2. Scrambling Degree

Unlike correlation values, scrambling degree can be used to evaluate the correlation of adjacent pixels of a whole scrambled image. If a scrambling algorithm can obtain a large scrambling degree, the algorithm can achieve high confusion and diffusion properties. Image scrambling degree is determined by the gray difference between adjacent pixels [25]. Assuming that p(i,j) is the gray value of the pixel at position (i,j), the gray difference of pixel p(i,j) can be calculated using [23–25](30)GDi,j=14∑s,t∈i-1,j,i+1,j,i,j-1,i,j+1pi,j-ps,t2,where i=2,3,…,M-1, j=2,3,…,N-1, and the image size is M×N. We use E(GD) to represent the average gray-scale difference of whole image; obviously, E(GD) can be calculated using (31)EGD=1M-2N-2∑i=2M-1∑j=2N-1GDi,j.Assume that E(GD) represents the average gray-scale difference of plaintext image and E′(GD) represents the average gray-scale of the scrambled image. Then, according to paper [25], image scrambling degree can be calculated as follows:(32)GDD=E′GD-EGDE′GD+EGD.From (32), it can be seen that the value of GDD is between -1 and 1, and the larger the value of GDD is, the better the performance of the scrambling algorithm is. The data in the third column of Table 4 is the maximum value in 32-round transform for each scrambling algorithm. The remark below Table 4 shows that GDD does not accurately evaluate the performance of a scrambling algorithm, and sometimes there is a large visual difference. Figure 12 is the scrambled images using scrambling algorithms to shuffle Lena image. The scrambling effect of Figures 12(e), 12(g), 12(k), and 12(l) is obviously better. Therefore, it can be seen from Table 4 and Figure 12 that LNBT has good image scrambling performance.Figure 12
Scrambled images: (a) original image, (b) 6-round 2D Arnold transform, (c) 11-round discrete Baker map, (d) 13-round subaffine transform, (e) 13-round cellular automata transform, (f) 32-round Fibonacci transform, (g) 19-round Hilbert curve transform, (h) 27-round magic cube transform, (i) 3-round 2×2 sampling, (j) 29-round LNBT-1, (k) 32 LNBT-2, and (l) 24-round LNBT-3.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l)


### 5.3. Conclusions

This paper gives a new kind of scrambling transform, which is one-dimensional and is called LNBT with three parameters. LNBT is bijective, and thus LNBT is invertible and is a permutation on a finite subset of the natural numbers. Since LNBT has good scrambling performance, it can be used to shuffle two-dimensional image; in fact, it can be directly used to scrambled one-dimensional audio signal and also used as a tool of encryption.


## 5.1. Correlations between Adjacent Pixels

The goal of image scrambling is to remove the correlation between the pixels of a plaintext image, and therefore the correlation value between adjacent pixels of image is an important index for evaluating the performance of the image scrambling algorithm. Assuming thatxn and yn are two sequences consisted of horizontal or vertical or diagonally adjacent pixels, their correlation value can be calculated by [6](29)Corr=N∑i=1Nxi×yi-∑i=1Nxi×∑i=1NyiN∑i=1Nxi2-∑i=1Nxi2×N∑i=1Nyi2-∑i=1Nyi2where N is the length of sequences. Obviously, if the correlation value is close to 1, it indicates that there is a higher correlation between adjacent pixels. If the correlation value is close to 0, then the two adjacent pixel sequences have a lower correlation. Therefore, the smaller the correlation value is, the better the performance of the scrambling algorithm is.To measure the performance of LNBT scrambling algorithm by using the correlation values of neighboring pixel sequences. First, we use other common scrambling algorithms and the proposed algorithm in this paper to perform a 32-round scrambling transformation on the Lena image. Then pick out the largest value of GDD (see Section5.2) in the 32-round transforms as the last results of each scrambling algorithm for comparison. Finally, we randomly select 5000 pairs of horizontally adjacent pixels, vertically adjacent pixels, and diagonally adjacent pixels and then calculate the correlation values of the neighboring pixel sequences of the three directions in the original image and the correlation values of the three directions in the scrambled images, respectively. Columns 4, 5, and 6 of Table 4 are correlation values of adjacent pixel sequences of the three directions in the original image and in the scrambled images, where LNBT-1 denotes the LNBT scrambling algorithm of permuting separately along x- and y-direction; LNBT-2 denotes the LNBT scrambling algorithm after scanned line-by-line; LNBT-3 denotes the LNBT scrambling algorithm after scanned in zigzag order. We can know from Table 4 that the LNBT scrambling transform can successfully remove the correlation between adjacent pixels. Figures 11(a), 11(b), and 11(c) display the gray-scale distributions of 5000 pairs of horizontally adjacent pixels, of vertically adjacent pixels, and of diagonally adjacent pixels, respectively, which are selected randomly from original image. (d), (e), and (f) are the gray-scale distributions of an adjacent pixel sequence pairs for horizontal, vertical and diagonal directions in the scrambled image using LNBT-1; (g), (h), and (i) show the gray distributions of an adjacent pixel sequence pairs for the three directions in the scrambled image using LNBT-2; (j), (k), and (l) are the gray-scale distributions using LNBT-3. The results of Table 4 and Figure 11 show that LNBT can successfully remove the correlation between adjacent pixels of plaintext imageTable 4
GDD and correlation values.
Method name rounds GDD Correlation values Horizontal Vertical Diagonal Original image ∖ ∖ 0.9273 0.9590 0.9062 2D Arnold [10] 6 0.8995 0.1239 0.06369 0.0003 Discrete Baker map [26] 11 0.8972 0.0696 0.0384 0.0483 Sub-affine [27] 13 0.8985 0.0807 0.0921 0.0071 CA [15] 13 0.8908 0.0114 0.0270 0.0080 Fibonacci-Q [10] 32 0.7280 0.2968 0.9570 0.3012 Hilbert curve [19] 19 0.8910 0.0083 0.0013 0.0146 Magic cube [9] 27 0.8959 0.0670 0.0514 0.1107 2×2 sampling [28] 1 ∗ 0.8957 0.1225 0.0352 0.0770 LNBT-1 32 ∗ 0.8864 0.0749 0.1456 0.0431 LNBT-2 32 0.8884 0.0323 0.0170 0.0016 LNBT-3 24 0.8909 0.00005 0.0227 0.0057 ∗Remark: visually, the scrambling performance of the third round of 2x2 sampling transform is best, and the 29th round of LNBT-1 has the best scrambling effect. Figures 12(i) and 12(j) are the scrambled images of the third round of 2x2 sampling transform and of the 29th round of LNBT-1, respectively.Figure 11
Gray-scale distributions of adjacent pixel sequence pairs: (a) horizontal of original image, (b) vertical of original image, (c) diagonal of original image, (d) horizontal of scrambled image using LNBT-1, (e) vertical of scrambled image using LNBT-1, (f) diagonal of scrambled image using LNBT-1, (g) horizontal of scrambled image using LNBT-2, (h) vertical of scrambled image using LNBT-2, (i) diagonal of scrambled image using LNBT-2, (j) horizontal of scrambled image using LNBT-3, (k) vertical of scrambled image using LNBT-3, and (l) diagonal of scrambled image using LNBT-3.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l)


## 5.2. Scrambling Degree

Unlike correlation values, scrambling degree can be used to evaluate the correlation of adjacent pixels of a whole scrambled image. If a scrambling algorithm can obtain a large scrambling degree, the algorithm can achieve high confusion and diffusion properties. Image scrambling degree is determined by the gray difference between adjacent pixels [25]. Assuming that p(i,j) is the gray value of the pixel at position (i,j), the gray difference of pixel p(i,j) can be calculated using [23–25](30)GDi,j=14∑s,t∈i-1,j,i+1,j,i,j-1,i,j+1pi,j-ps,t2,where i=2,3,…,M-1, j=2,3,…,N-1, and the image size is M×N. We use E(GD) to represent the average gray-scale difference of whole image; obviously, E(GD) can be calculated using (31)EGD=1M-2N-2∑i=2M-1∑j=2N-1GDi,j.Assume that E(GD) represents the average gray-scale difference of plaintext image and E′(GD) represents the average gray-scale of the scrambled image. Then, according to paper [25], image scrambling degree can be calculated as follows:(32)GDD=E′GD-EGDE′GD+EGD.From (32), it can be seen that the value of GDD is between -1 and 1, and the larger the value of GDD is, the better the performance of the scrambling algorithm is. The data in the third column of Table 4 is the maximum value in 32-round transform for each scrambling algorithm. The remark below Table 4 shows that GDD does not accurately evaluate the performance of a scrambling algorithm, and sometimes there is a large visual difference. Figure 12 is the scrambled images using scrambling algorithms to shuffle Lena image. The scrambling effect of Figures 12(e), 12(g), 12(k), and 12(l) is obviously better. Therefore, it can be seen from Table 4 and Figure 12 that LNBT has good image scrambling performance.Figure 12
Scrambled images: (a) original image, (b) 6-round 2D Arnold transform, (c) 11-round discrete Baker map, (d) 13-round subaffine transform, (e) 13-round cellular automata transform, (f) 32-round Fibonacci transform, (g) 19-round Hilbert curve transform, (h) 27-round magic cube transform, (i) 3-round 2×2 sampling, (j) 29-round LNBT-1, (k) 32 LNBT-2, and (l) 24-round LNBT-3.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l)


## 5.3. Conclusions

This paper gives a new kind of scrambling transform, which is one-dimensional and is called LNBT with three parameters. LNBT is bijective, and thus LNBT is invertible and is a permutation on a finite subset of the natural numbers. Since LNBT has good scrambling performance, it can be used to shuffle two-dimensional image; in fact, it can be directly used to scrambled one-dimensional audio signal and also used as a tool of encryption.



---

*Source: 8087958-2018-06-25.xml*