The pair-wise LSB matching steganography with a discrete quantum behaved Gravitational Search Algorithm

Abstract

This paper presents a discrete quantum behaved gravitational search algorithm (DQGSA) which is used to provide a novel steganographic algorithm based on the spatial domain: Least Significant Bits (LSB). This approach improves the LSB matching method proposed by Mielikaien. Whereas Mielikaien’s method uses a binary function to reduce the number of changed pixel values, in suggested method a three-score system is proposed to assess the performance of different orders for LSB matching. Afterward, the proposed DQGSA is employed to search for an optimal solution among all the permutation orders. By employing the proposed method, the distortion of the stegano image could be reduced while the probability of detection is decreased. The experimental results show that the proposed method achieves better performance than Mielikainen’s pair-wise LSB matching method in less distortion (means higher visual quality) and more preservation against steganalysis.

Keywords

Information hiding least significant bit (LSB) matching quantum gravitational search algorithm (QGSA)steganography

1 Introduction

Since the rise of the Internet, the security of information has become one of the most important aspects of communication and information technology [18]. Steganography is the art and science of hiding information by embedding messages within other media, seemingly innocent covers [4]. Steganography can be viewed as similar to cryptography. Both have been used to protect secure information. In comparison with cryptography, it could be said that cryptography is the science of writing in secret codes. On the other hand, cryptography is the study of hiding information, while steganography deals with composing hidden messages so that only the sender and the receiver know that the message even exists [33]. In other words, in steganography, only the sender and the receiver know the existence of the message, whereas in cryptography the existence of the encrypted message is visible to the world. Due to this, steganography removes the unwanted attention coming to the hidden message. The word steganography literally means covered writing as derived from Greek words steganos meaning “covered or protected” and graphei meaning “writing” [26].

The following formulation provides a simple description of the steganographic process:

$\begin{matrix} Cover - medium + hidden - data + stegano \\ - key = stegano - medium \end{matrix}$ where the cover-medium is the file behind which the hidden-data will be hidden, and may also be encrypted using the stegano-key. The resultant file is the stegano-medium (surely stegano-medium will be the same type of file as the cover-medium). The cover-medium is typically an image, a video or an audio file. In this paper, we will focus on image files, and therefore we will refer to the cover-image and stegano-image [4].

Simple steganographic techniques have been used for hundreds of years. But with the increasing use of files in an electronic format, new techniques for hiding information have become accessible. Steganography and watermarking are main parts of the fast developing area of information hiding and they are techniques to hide important information undetectably and/or irremovably in image, audio and video data. These two information hiding techniques are explained in next section in detail [31].

Steganography methods depend on in which domain the insertion is performed, could be divided into two main groups, namely transform domain and spatial domain. The transform domain methods consist of Discrete Cosine Transform (DCT), Discrete Fourier Transform (DFT) and Discrete Wavelet Transform (DWT). The transform domain steganography methods hide messages in more significant areas of the cover images which are explained completely in next section. The second group belongs to spatial domain methods. The spatial domain techniques embed messages in the intensity value of the pixels directly. The first attempt in spatial domain was least significant bit (LSB) substitution; LSB substitution steganography is a simple technique that hides message bits in LSB of image pixels. Against simplicity of this method, one significant drawback of this method is that the secret message could be detected very easily [5].

After some years an improved LSB based method was proposed which is called the LSB matching procedure [19]. As the main advantage, this method decreases the probability of detection. In the LSB matching method, introduced by Mielikainen, initially a matching process between secret message and the cover image is performed and then based on the maximum similarity; embedding data takes place [19].

In [15], a LSB matching method is developed that adjusts the matching order between the secret messages and the host image in order to obtain optimal solution. They found that using exhaustive search to find optimal solution is impractical because of time-consuming. Therefore, they used immune programming strategy to get nearly-optimal solution for LSB matching. They demonstrated that their experiments achieved better performance than Mielikainen’s method in terms of visual quality of stego-image and survival rate against detection.

Inspired by their method, the authors in [21] proposed a new method by using quantum gravitational search algorithm (QGSA) to search for a near-optimalsolution.

In this paper, first a new method of evaluating gain matrix is proposed to improve presented results in [21]. Afterward, a discrete version of quantum behaved gravitational search algorithm (DQGSA) is suggested and then employed to search into gain matrix in order to find the best matching order that improves Mielikainen’s method. Based on experimental results, the proposed method increases the speed of algorithm and simultaneously decreases the probability ofdetection.

The rest of the paper is organized as follows. InSection 2, related works are reviewed. The details of our proposed method are described in Section 3. InSection 4, the experimental results are given. Finally, the conclusions are presented in Section 5.

2 Basic concepts

Steganography is the art and science of hiding information such that no one, apart from the sender and receiver, suspects the existence of the message [6]. Secret information is encoded in such a way that the existence of the information is concealed in a human perception. The main goal of steganography is to communicate securely in a completely undetectable manner [13].

Many developments in steganography occurred during World War II. This included the development of invisible inks, microdots, and encoded messages [3]. It would be very instructive to compare first the basic groups of information hiding techniques in order to introduce the steganography in detail.

2.1 Cryptography vs. steganography

Cryptography is the science of encrypting data in such a way that nobody can understand the encrypted message, whereas in steganography nobody should suspect/discover the existence of data. On the other hand, the goal of cryptography is to make data unreadable by a third party, whereas the goal of steganography is to hide the data from a third party [11].

In steganography, the information to be hidden is embedded into the cover object which can be text, image, audio or video so that the appearances of cover object doesn’t vary unusually after information become hidden. In other words, cryptographic methods try to protect the content of a message, while steganography uses methods that would hide both the message as well as the content [35].

2.2 Steganography vs. watermarking

Watermarking is mainly used to avoid piracy in digital media. In steganography the data to be hidden is not at all related to the cover object. However, the main intention is secret communication. Whereas in watermarking the data to be hidden is related to the cover object. In other words, the main intention is to restrict piracy of digital data [23].

As another difference in watermarking process, any changes in the watermarked object should have no effect on the watermark. On the other hand, the watermark inside the image should survive the manipulations; otherwise the attackers can very easily remove the watermark [32].

Steganography is a very powerful tool because, as mentioned above, it can be very difficult to detect secret data.

2.3 A brief review of steganography’s method

Methods of image steganography can be divided into two main groups: Transform Domain methods (TD) and Spatial Domain methods (SD) [20]. In the transform domain methods, images are first transformed and afterward the message is embedded into the cover image. In other words, in transform domain methods, messages are hidden in more significant areas of the cover image, and therefore this make it more robust [34]. In order to hide information in a more significant area, the cover image is initially separated into high, middle and low frequency components.

One of the most important issues in steganography methods is being undetectable. Therefore, in order to avoid image distortion, the information has been embedded in higher frequencies, which have lessvisibility.

Discrete Cosine Transform (DCT), Discrete Fourier Transform (DFT) and Discrete Wavelet Transform (DWT) are the most common transforms that are used for data hiding [36]. Comparing with other methods in transform domain, the DCT approach is very robust to JPEG compression, since JPEG compression itself uses DCT [24].

The most of transform domain methods are independent of the image format [28]. As another advantage, security and robustness against statistical attacks and image manipulation can be mentioned. However, high computational complexity is the main disadvantage of these methods.

The second group is spatial domain methods. In these methods, messages are directly embedded in the pixels information. The main idea behind this group of methods is to insert the secret message’s bits into the least significant bits of the cover image pixels hence it has less effect on visibility. The first attempt in spatial domain is LSB substitution. LSB substitution steganography is a simple technique that hides message bits in LSB of image pixels [5].

Popular steganographic tools based on LSB embedding vary in the existing approaches for hiding information [9, 10]. Some algorithms change LSB of pixels visited in a random walk [8], others modify pixels in certain areas of images [14], or instead of just changing the last bit they increment or decrement the pixel value [30]. Another approach for embedding secret message in spatial domain was proposed by [17] which is based on statistical information of noise.

The major advantages of the LSB algorithms are their speed and simplicity. Because of computational efficiency, steganography software has been developed which uses LSB manipulation. Against simplicity of this method, one significant drawback of this method is that the secret message could be detected very easily [29].

Therefore, a new method which is called LSB matching method has been proposed and it is more robust against detection [1]. In this method, first a matching process between secret message and the cover image is done. Afterward, message is embedded based on the maximum similarity into cover image. Having a security key in this method decreases the probability of detection in comparison with LSB insertion.

The performance of the LSB matching was improved by Mielikainen [19]. In Mielikainen’s method, initially a matching process between secret message and the cover image is performed (which is explained in section 2.4 in detail) and then based on the maximum similarity; embedding data would take place [19]. In [15], in order to improve the quality of image, a three-score system is proposed to assess the performance of different orders for LSB matching. Then, an immune programming strategy is adopted to search for a near-optimal solution among all the permutation orders.

2.4 Mielikainen’s method

For starting the explanation of the proposed method Mielikainen’s method is described in detail. In Mielikainen’s method [19] the LSBs of the cover image are not just simply replaced with the LSB of the secret message. Instead, if the message bit does not match the LSB of the cover image, the value of the cover pixel is randomly either added or subtracted by one.

Assume that S, C and St are the matrixes of secret data, cover image and stegano-image, respectively. In Mielikainen’s method, first, by scanning left-to-right and top-to-bottom of matrixes of S, Cand St, they are converted into streams of C₀, S₀and St₀respectively, as shown in Equation (1).

$\begin{matrix} C_{0} & = & [c_{1} c_{2} \dots c_{i} \dots c_{r_{c} \times c_{c}}] \\ S_{0} & = & [s_{1} s_{2} \dots s_{i} \dots s_{r_{s} \times c_{s}}] \\ {St}_{0} & = & [{st}_{1} {st}_{2} \dots {st}_{i} \dots {st}_{r_{st} \times c_{st}}] \end{matrix}$ (1)

where r_c and c_cindicate numbers of row and column in the cover image, r_s and c_sindicate numbers of row and column in the secret data and r_st and c_stindicate numbers of row and column in the stegano-image. Then, each two consecutive elements in streams of C₀ and S₀ are selected. Assume that two cover pixels are c_i and c_i+1, two secret bits to be hidden are s_i and s_i+1and two stegano pixels are assumed st_i and st_i+1.

The Mielikainen’s method is performed as follows:

(i) The value of secret bit s_i is compared with the LSB of the first cover pixel c_i. If they are equal (LSB (c_i) = s_i), then the first cover pixel is kept, st_i = c_i, otherwise the second cover pixel is kept, st_i+1 = c_i+1.

(ii) In the case of st_i = c_i, s_i+1 is compared with f (c_i, c_i+1) where it is defined as: $f (c_{i}, c_{i + 1}) = LSB ([\frac{c_{i}}{2}] + c_{i + 1})$ (2)

If they are equal, then st_i+1 = c_i+1, otherwise, the second pixel st_i+1 is calculated by randomly incrementing/decrementing the second cover pixel c_i+1. If s_i is not equal with LSB(c_i), st_i+1 = c_i+1. Then, if s_i+1 = f (c_i - 1, c_i+1) the value of st_i+1 = c_i - 1, otherwise st_i+1 = c_i + 1. Mielikainen’s method is illustrated in Fig. 1.

3 DQGSA algorithm

3.1 A brief introduction to GSA algorithm

The Gravitational Search Algorithm (GSA) was first introduced in 2009 [7]. Up to now, many works have been done to improve the GSA algorithm [27]. As a population-based evolutionary technique, GSA is a stochastic optimization approach which maintains a collection of objects representing the candidate solutions to the problem at hand. Objects moves through a multidimensional search space to find the optima or sub-optima.

In the standard gravitational search algorithm (SGSA) with Nobjects in a D-dimensional search space, the potential solution could be represented by theobject’s position vector X_i (t). In GSA, the values of objects’ masses are calculated by computing the current population fitness, as follows: $M_{i} (t) = \frac{({fit}_{i} (t) - worst (t))}{\sum_{j = 1}^{N} ({fit}_{j} (t) - worst (t))}$ (3)

where M_i is the mass of i-th object (agent), fit_i (t) represents the fitness value of the agent i at time t, and worst (t) is defined as follows (for a minimization problem): $worst (t) = max ({fit}_{j} (t)) j = 1, 2, \dots, N$ (4)

To compute the acceleration of an agent, by using the law of motion, $a_{i}^{d} (t)$ is calculated as follows:

$\begin{matrix} a_{i}^{d} (t) = \sum_{j \notin Kbest, j \neq i} {rand}_{j} G (t) \frac{M_{j} (t)}{R_{ij} (t) + ɛ} (x_{j}^{d} (t) - x_{i}^{d} (t)) \\ d = 1, 2, \dots, D i = 1, 2, \dots, N \end{matrix}$ (5)

where, G (t) is gravitational constant at time t, note that G (t) is a decreasing function of time, which is set to G₀ at the beginning and decreased exponentially toward zero by lapse of time. ɛ is a small constant, R_ij (t) is the Euclidean distance between two agents i and j and rand_j is a uniformly distributed random number in the interval [0, 1]. In equation (5) Kbest is the set of K agents with the biggest masses,K is a function of time, initialized to K₀ at the beginning and decreased linearly with time. Afterward, the next velocity of an agent iscalculated as a fraction of its current velocity added to acceleration. $v_{i}^{d} (t + 1) = {rand}_{i} \times v_{i}^{d} (t) + a_{i}^{d} (t)$ (6)

Eventually, the agent’s position, X_i, is updated according to Equations (7). $x_{i}^{d} (t + 1) = x_{i}^{d} (t) + v_{i}^{d} (t + 1)$ (7)

This process is repeated until the stopping criterion is reached, usually a sufficiently good fitness or a maximum number of iterations.

3.2 The Quantum GSA algorithm

Physics is a foundation of modern science and technology. Recently, novel optimization methods have been motivated from the concepts of quantum mechanics and computation [23]. By quantum theoretical development, claims have been made that polynomial quantum computing algorithms exist for problems which are considered non-polynomial (i.e, NP-hard) on classical computer [25]. It is clear that the algorithm described by Shor represents a significant advance in knowledge of how to program quantum computational networks if they exist.

In [2], inspired by Shor’s quantum algorithm for factoring very large numbers, an extension to Shor’s method is described and this leads to provide a novel discrete algorithm. In other words, in this paper a brief outline of genetic algorithm for solving discrete problems is proposed namely quantum inspired genetic algorithm (QIGA). QIGA identifies and demonstrates the feasibility of a novel computational paradigm which is inspired by the principle of quantum mechanics and quantum computing. In QIGA new kinds of crossover and mutation for discrete computing inspired by Shor’s algorithm are presented.

QGSA is one of the novel optimization methods based on quantum mechanics. In quantum model of GSA, each object has quantum behavior. Thus, the state of the object is characterized by wave-function ω, where |ω|² is the probability density function of its position.

Employing Monte Carlo method, the objects in QGSA [22] move according to the following iterative equation: ${\begin{matrix} \begin{matrix} X_{i} (t + 1) = {Center}_{i} + δ \times | {Center}_{i} - X_{i} (t) | \times ln (\frac{1}{r_{1}}) & r_{2} > 0.5 \end{matrix} \\ \begin{matrix} X_{i} (t + 1) = {Center}_{i} - δ \times | {Center}_{i} - X_{i} (t) | \times ln (\frac{1}{r_{1}}) & others \end{matrix} \end{matrix}$ (8)

where r₁and r₂ are uniformly distributed random numbers in the interval [0,1] and Center_i is center of potential well. In QGSA to avoid local optima, we assume that each Kbest is center of an attractive potential field. Therefore, in each iteration, the number of attractive potential field is equal to Kbest. As mentioned above, Kbest is a function of time.

In this step, with a probabilistic mechanism, every agent chooses one of the Kbest members and moves towards it. This probabilistic mechanism is based on the masses of Kbest set. The way of selecting one of Kbest is so similar to the roulette wheel selection in genetic algorithm. In this kind of selection, objects are given a probability of selection that is directly proportionate to their masses (quality of the solutions).

It should be noted that QGSA is a real algorithm; in other words, it cannot be used for solving discrete problems in the current form.

3.3 The proposed discrete QGSA

As mentioned in the previous section, the QGSA cannot be used to generate discrete values for solving discrete problems since the positions definition (solutions) are real-valued.

For discrete optimization problem, conventional QGSA must address the following two issues:

How to change the position of the objects?

How to guarantee the position is reasonable?

Inspired by [2], we propose a novel discrete quantum behaved gravitational search algorithm (DQGSA) to tackle the discrete space problems. To do this, we redefine the position updating procedure in QGSA algorithm for the discrete problem.

The travelling salesman problem (TSP) is a well-known NP-hard problem in combinatorial optimization, operations research and theoretical computer science. In TSP, a list of cities and their pairwise distances are given and the task is to find the shortest possible route that visits each city exactly once and returns to the origin city.

For an D-ordered TSP problem, D cities are numbered 1, 2, 3, … and D respectively, denote $X_{i} = [x_{i}^{1}, x_{i}^{2}, \dots, x_{i}^{D}]$ as the i-th agent’s position in the swarm of DQGSA, which represents the traveling tour of $x_{i}^{1} \to x_{i}^{2} \to \dots \to x_{i}^{D} \to x_{i}^{1}$ .

To simplify the explanation, consider an example containing 7 cities with the names of A, B, C, E, F, G and H. In this example, a tour can be represented as an agent consisting of 7-dimensions (city) where each dimension is a city. The first dimension is the start of tour. The procedure of DQGSA is described as follows:

Step 1: Initialize a population of objects with random discrete position where each object contains 7-dimension and has the characters of a tour. In order to reach this aim, each agent contains all letter A, B, C, E, F, G and H with a randomized order.

Step 2: Evaluate the fitness function of all objects.

Step 3: Updating the value of center (select one of Kbestat random) for each object.

Step 4: Update the position of every agent according to Equation (8). It should be considered that because QGSA is a real algorithm, in this step the real position of agent doesn’t have characters of a tour. Therefore, it should be changed properly to have characters of a tour.

Step 5: Scale the position of each agent based on feasible space of the problem.

Step 6: discretize the position of each agent. In this step each agent’s dimension is discrete but agent is not a complete tour.

Step 7: Repair the agent to become a tour.

Scan the agent from first dimension to the last one and compare it with a basic agent containing all possible cities. As an example consider an agent as follow: $X_{i} = [A C H A G G H]$ (9)

And the basic agent [A B C E F G H] which contains all possible cities respected to feasible space.

In the tour represented by X_i in Equation (9), the first, second and third dimensions consist of ‘A’, ‘C’ and ‘H’ respectfully. Therefore, ‘A’, ‘C’ and ‘H’ are omitted from basic agent and the basic agent is changed to [B E F G].

The fourth position is ‘A’ which omitted before. The scanning procedure is continued. After scanning all dimensions the remaining letters in basic agent are ‘B’, ‘F’ and ‘E’ which mean that ‘B’, ‘F’ and ‘E’ are not available in sample agent X_i.

Afterward, the scanning procedure is started again in order to make a tour. The first, second and third dimensions are copied without any changes. At this point, the ‘A’ in the fourth dimension cannot be included since ‘A’ already occurs in the first dimension. Since the basic agent already contains ‘B’, ‘F’ and ‘E’, an arbitrary letter is chosen instead of ‘A’ in the fourth dimension.

It is suggested that the letter is chosen randomly in order to have the algorithm more exploration ability in the search space. Assume that ‘F’ is chosen. The chosen letter is omitted from basic agent. So, the basic agent is changed to ‘B’ and ‘E’. It will be continued until all dimensions are checked. Finally the rebuilt agent has the character of a tour. $X_{i}^{new} = [A C H F G B E]$ (10)

Step 8: If the stopping criterion is met, then the best position (tour) is reported; otherwise go back to step 2. The stopping criterion is considered as a fixed number of algorithm repetition (iteration).

4 The proposed steganography method

As shown in Fig. 1, in the Mielikainen’s method at first, the value of secret bit s_i is compared with the LSB of the first cover pixel c_i. If they are equal (s_i = LSB (c_i)), then the first cover pixel is kept unchanged, otherwise the second cover pixel would be kept unchanged. In the first branch, when st_i = c_i, s_i is compared with f (c_i, c_i+1). If they are equal, then st_i+1 = c_i+1, otherwise, the second pixel st_i+1 is calculated by randomly incrementing/decrementing the second cover pixel c_i+1; where f (c_i, c_i+1) is defined as Equation (2).

If s_i is not equal to LSB (c_i), st_i+1 = c_i+1. If st_i+1 = f (c_i - 1, c_i+1), then the value of st_i = c_i, otherwise st_i = c_i + 1.

The main drawback of this method is that this method may also distort stegano images. Therefore, in this paper, by finding the best matching order between cover image and secret data, we try to decrease the distortion of stegano images while a heuristic search algorithm is used to find this best matching order.

From the flowchart in Fig. 1, it could be declared that best matching with fewer changes of the cover image is achieved when s_i = LSB (c_i) and s_i+1 = f (c_i, c_i+1), which means values of stegano pixel s_i and s_i+1 and cover pixel c_i and c_i+1 are equal respectively, and as a result the difference between stegano image and cover image is minor.

In our proposed method, a four-tier state-scoring is used that operates as follows:

If two cover image pixels are similar to stegano image pixels and there is the first time they are used, score is T₁.

If two cover image pixels are similar to stegano image pixels and there is the Q-th time they are used, score is $T_{2} = \frac{T_{1}}{Q}$ .

If at least one pixel of the stegano image is changed related to cover image, score is T₃.

4. If both pixels are changed, score is T₄. In order to show the superiority of keeping the cover pixel values unchanged,T₁ is considered greater than 3T₃. In our proposed method, each pair pixels of cover image pixels which are similar to stegano image pixels can be used more than one. But after each use their score decreases to $\frac{T_{1}}{Q}$ when Q is the number of time they are used. It should be mentioned that in the first step for evaluating the score matrix, T₁, T₃ and T₄ just are considered and in the next step if two cover image pixels are utilized more than once, their score is decreased to $T_{2} = \frac{T_{1}}{Q}$ .

To distinguish the performances of these processes, they must be assigned hierarchical scores such as T₁ > T₃ > T₄ and as mentioned before T₁ > 3T₃ > T₂ which indicates that keeping the cover pixel values unchanged is better than changing them. The scores are given as follows: T₁ = 40,T₃ = 10,T₄ = 0.

Score matrix

In order to evaluate the performance of different matching order of secret image and cover image, first a matrix which is called score matrix SM is defined.

After converting matrix of C and Sinto streams of C₀ and S₀, for each two sequential pixels in the stream, the value of T is evaluated and then the score matrix SM_{L_c×L_S} is calculated as follows: ${SM}_{L_{c} \times L_{S}} = {\begin{matrix} sm (i, j) | sm (i, j) \in (T_{1}, T_{3}, T_{4}) \\ 1 \leq i \leq L_{c}, 1 \leq j \leq L_{s} \end{matrix}}$ (11)

where sm (i, j) is the i-th row and the j-th column element of this matrix SM, L_s is the length of secret stream and L_c is the length of cover stream. In order to finding the best matching order, we need to choose L_s element in different columns from the matrix SM. It should be noted that only one element from each column should be selected. But each row can be selected more than once. This situation may happen whenever the element of row is T₁, then this value is decreased to $T_{2} = \frac{T_{1}}{Q}$ where Q is the number of time each row are used

In addition to this, an adjustment list is evaluated from these selected L_s elements, namely J = [j₁, j₂, …, j_k, …, j_{L
_s}] where index k indicates the k-th column of SM and the value of j_k refers to j_kth element of k-th column.

It should be mentioned that many adjustment lists could be made by taking different elements, but the one with the highest score which means the best matching structure will be found by the DQGSA algorithms.

By having an adjustment list J, the fitness (total score) can be calculated by adding sm (j_k, k), where j_k is the kth element of J and k = 1, 2, …, L_s. For simplicity, the normalized fitness of J is introduced as follows: $f (J) = \frac{1}{f^{m}} \sum sm (i, j) |_{j} f^{m} = L_{s} \times T_{1}$ (12) where f^m is the maximum score for the adjustment list.

4.1 Data extraction

As said in [15], after finding the best adjustment list J, the secret data will be extracted as follows:

First, the stegano stream St₀ will be arranged by scanning the stegano image St as explained before. Afterward, for each consecutive two elements of the stream St₀ the position of J has been checked. At first, the value of second secret bit s_i+1 is calculated by using Equation (1). If s_i+1 = LSB (st_i), the first secret bit s_i is s_i+1. If s_i+1 is not equal to LSB (st_i), then s_i is calculated from s_i = f (st_i, st_i+1 ± 1). Eventually, when the entire secret bits are extracted, the secret stream is rearranged into the secret image.

5 Experimental results

To validate the performance of the proposed method, experimental results are presented and discussed in this section. In our experiment all images are 256 gray levels of size 512×512. In order to increase the speed of algorithm all images are resized into 128×128. We take the images Peppers, Barbara, Baboon and Lena, shown in Fig. 2(a), (b), (c), (d), respectively. The image coin (Fig. 2(e)) and a randomly generated secret binary stream data are taken as secret data.

5.1 Setting parameters

The proposed DQGSA has three main parameters, population size, δ which determines the balance between exploration and exploitation and the size of Kbest. Performance of each algorithm depends on suitable parameter values. In search algorithms setting parameters correctly has an effective influence on exploration and exploitation of the algorithm. But the main problem is how to set parameter values properly and how to vary them in order to maximize the searching ability of algorithms.

The proposed algorithm is tested with different population sizes to get the best performance. The results show that DQGSA with swarm size of 450–600 have good performance for this problem (Fig. 3). Thus, the swarm size is set to 500 in our experiment.

The next important parameter is δ. In DQGSA δ is a crucial parameter where can affect the precision of final solutions obtained. On the other hand, δ has a direct effect on the convergence behavior of the algorithm. In this paper because the problem is multimodal and based on our previous experiments, we set the parameter δ to 1.

It should be noted that since local exploitation and global exploration capabilities are always twisted together in the search process, it is difficult to fix the values for parameters. On the other hand, a good balance between exploration and exploitation abilities of a heuristic algorithm makes it more robust to avoid getting trap into local optima and also increases the convergence speed of the algorithm.

In this paper to control the exploration and exploitation of the proposed DQGSA, Kbest is considered as a function of time with the initial value at the beginning and is decreased with time by the linear control. It is set to N and the beginning and is decreased to 1 at the end.

5.2 Invisibility and capacity test

Figure 2 shows the cover image and secret data. The secret data is the image of Coin. Before embedding, both the cover image and the secret data are permutated randomly. The stegano images are shown in Fig. 4b after embedding data into the LSB planes by the proposed method. We find that the visual quality of the stegano images is not degraded much. Similar tests are also performed on the Baboon, Peppers and Woman images.

Table 1 shows the PSNR value of the proposed method compared with Mielikainen’s method and 3 other algorithms consist of GA, PSO and GSA. All algorithms were tested using similar parameters such as population size and the maximum number of iterations, the number of fitness evaluations. From the table, we find that with different embedding capacity, the PSNR value of our method is higher than other algorithm which proves the ability of DQGSA and proposed method in spotting acceptable optimum. As Table 1 shows, DQGSA increases the PSNR value of Mielikainen’s by about 9 dB, which is a significant result.

The results in Table 1 show clearly that by using the DQGSA in the proposed method, the number of changes of the LSB positions of the stegano image is considerably decreased. Hence, the visual quality of the stegano image and the PSNR value are enhanced compared with the original pair-wise LSB matching steganography and four other algorithms.

6 Conclusion

This paper presented a discrete quantum GSA in order to solve LSB matching method. The proposed solution evaluates different LSB matching orders to find the best matching order. It was shown that the proposed method could achieve higher PSNR values of stegano images and reduced number of changes in LSB position. To get good results, the parameters of the proposed DQGSA such as N, Kbest and δare investigated. In conclusion, experimental results show an improved visual quality of stegano images.

References

Ker

, Steganalysis of LSB matching in greyscale images, IEEE Signal Process 12 (2005), 441–444.

Narayanan

and Moore

, Quantum-inspired genetic algorithms, In International Conference on Evolutionary Computation, Nagoya, Japan, 1996, pp. 61–66.

Pfitzmann

, Information Hiding Terminology, Proc of First Int’l Workshop on Information Hiding, Lecture Notes in Computer Science 174 (1996), 347–356.

Cachin

, An information-theoretic model for steganography, Information and Computation 192(1) (2004), 41–56.

Chan

C.K.

and Chan

L.M.

, Hiding data in image by simple LSB substitution, Pattern Recognition 37 (2004), 469–467.

Artz

, Digital steganography: Hiding data within data, IEEE Journal of Internet Computing 5(3) (2001), 75–80.

Rashedi

, Nezamabadi-pour

and Saryazdi

, GSA: A gravitational search algorithm, Information Science 179 (2009), 2232–2248.

Collin

, http://www.winsite.com/bin/Info?500000033023, 2012.

Neil

, Digital watermarking and steganography: Fundamentals and Techniques, the computer journal, published at http://comjnl.oxfordjournal.org/, 2009.

10.

Neil

and Johnson

, Technical Report, Survey of steganography software 2002.

11.

Peticolas

F.A.P.

, Anderson

R.J.

and Kuhn

M.G.

, Information hiding– a survey, Proceeding of IEEE 87(7) (1999), 1062–1078.

12.

Bergh

F.V.D.

and Engelbrecht

A.P.

, A study of particle swarm optimization particle trajectories, Information Sciences 176 (2006), 937–971.

13.

Hay-ying

, Yin

, Xu

and Guo-qiang

, A steganographic algorithm for JPEGimage, International Conference on Computer Science and Software Engineering, Wuhan, Hubei, 5 2008, pp. 1263–1266.

14.

Pulcini

, http://www.geocities.com/SiliconValley/9210/gfree.html, 2012.

15.

, Wang

and Kim

, Near-optimal solution to pair-wise LSB matching via an immune programming strategy, Information Sciences 180(8) (2010), 1201–1217.

16.

Haupt

R.L.

and Haupt

, Practical Genetic Algorithms. John Wiley and Sons, 2004.

17.

Fridrich

and Goljan

, Digital image steganography using stochastic modulation. SPIE Symposium on Electronic Imaging, Security, Steganography, and Watermarking of Multimedia Contents, Santa Clara, California, 2003, pp. 191–202.

18.

Harmsen

and Pearlman

, Steganalysis of additive-noise modelable information hiding, Proceedings of the SPIE Security Watermarking Multimedia Contents, 2003, pp. 131–142.

19.

Mielikainen

, LSB matching revisited, IEEE Transaction on Signal Processing Letters 13 (2006), 285–287.

20.

Silman

, Steganography and Steganalysis: An Overview, SANS Institute, 2001.

21.

Soleimanpour-moghadam

, Nezamabadi-pour

, Farsangi

M.M.

and Mahyabadi

, A more secure steganography method based on pair-wise LSB matching via a quantum gravitational search algorithm, The 16th CSI International Symposiums on Artificial Intelligence & Signal Processing, Shiraz, Iran, 2012, pp. 34–38 .

22.

Soleimanpour-moghadam

, Nezamabadi-pour

and Farsangi

M.M.

, A quantum inspired gravitational search algorithm for numerical function optimization, Information Sciences 267 (2014), 83–100.

23.

Nielsen

M.A.

and Chuang

I.L.

, Quantum Computation and Quantum Information, Cambridge University Press, 2000.

24.

Provos

and Honeyman

, Hide and Seek: An introduction to steganography, IEEE Security and Privacy Journal 1(3) (2003), 32–44.

25.

Shor

P.W.

, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, Proc 35th Symposium on Foundations of Computer Science, 1994, pp. 124–134.

26.

Katzenbeisser

and Petitcolas

, Information hiding techniques for steganography and digital watermarking, Artech House Books, 1999.

27.

Sarafrazi

, Nezamabadi-pour

and Saryazdi

, Disruption: A new operator in gravitational search algorithm, Scientia Iranica 18 (2011), 539–548.

28.

Venkatraman

, Abraham

and Paprzycki

, Significance of Steganography on Data Security, Proceedings of the International Conference on Information Technology: Coding and Computing 2 2004, pp. 347–351.

29.

Moerland

, Steganography and Steganalysis. Leiden Institute of Advanced Computing Science, www.liacs.nl/home/tmoerl/privtech.pdf, 2012.

30.

Sharp

, An implementation of key-based digital signal steganography, Proc 4th International Workshop on Information Hiding, 2001, pp. 13–26.

31.

Sharp

, http://www.sharpthoughts.org, 2001.

32.

Sachnev

, Kim

, Nam

, Suresh

and Shi

, Reversible watermarking algorithm using sorting and prediction, IEEE Transactions on Circuits and Systems for Video Technology 19 (2009), 989–999.

33.

X.X.

and Wang

, A steganographic method based upon JPEG and particle swarm optimization algorithm, Information Sciences 15 (2007), 3099–3109.

34.

Wang

and Moulin

, Steganalysis of block-DCT image steganography, IEEE workshop on Statistical Signal Processing, IEEE Computer Society Press, 2003.

35.

Chu

Y.H.

and Chang

, Dynamical cryptography based on synchronized chaotic systems, Electronics Letters 35 (1999), 974–975.

36.

Shi

Y.Q.

and Sun

, Image and Video Compression for Multimedia Engineering, CRC Press, Taylor & Francis Group, LLC, Boca Raton, London, New York,Washing D.C., 2001.