Abstract
Abstract
Data embedding in medical images require perfect reversibility with which the embedding distortions can be completely removed to achieve a high fidelity recovery of the cover images. Adaptive Pixel Pair Matching is a high capacity embedding scheme that allows data embedding in any desired larger notational system still achieving exact reconstruction of secret. The principle behind Extended Adaptive Pixel Pair Matching (EAPPM) is to use a pixel pair as the reference co-ordinate and select a co-ordinate in its neighbourhood set according to the secret digit, as the stego pixel pair using which the extraction function recovers the secret data. The cover image is then reconstructed using the Look-Up Table (LUT) built with values of modulus distance. This reversibility can lead to multiple layer embedding, but cannot be fully exploited to increase the payloads as the usage of larger notational systems reduces the quality of the image. Hence this paper extends the APPM process to be performed over coefficients of the Transform domain in a repetitive fashion improving embedding capacity still maintaining high image quality as required for medical images.
Introduction
High capacity schemes and reversible data hiding schemes have evolved separately in steganographic history. Conventional methods like Least Significant Bit Substitution techniques [1] are not reversible and if extended to higher bit planes, do not contribute towards image quality. Many of the reversible techniques like Pixel Value Differencing [2] do not lend themselves towards high capacity. Representing the secret stream using a notational system [3] to improve embedding capacity evolved as a new school of thought.
Data-hiding methods that employ two pixels as an embedding unit to conceal a message digit are termed as Pixel Pair Matching (PPM) methods. Exploiting Modification Direction (EMD) [4] is one such technique which can achieve a maximum embedding capacity of only 1.61 bits per pixel (bpp). Chao et al. proposed Diamond Encoding (DE) technique that extended the payload of EMD using larger notational systems [5]. DE increases the embedding capacity while still preserving good stego image quality. But the embedding capacity of the system is greatly influenced and controlled by a parameter ‘k’. For example, when k is 1, 2, 3, the notational systems are 5-ary, 13-ary, 25-ary respectively. Hence, as the base notation increases, high distortion results. Another significant problem arises from the shape of the neighbourhood set. The system possesses diamond shaped neighbourhood set ∅. The diamond shape is characterised by more extreme corners that introduces greater variations in the pixel value when compared to other co-ordinates.
In 2012, Wien Hong and Tung-Shou Chen proposed Adaptive Pixel Pair Matching (APPM) that reduces the Mean Square Error resulting due to poor design of neighbourhood set [6]. The neighbourhood set is specially designed and doesn’t possess a significant shape or pattern. But it holds the best possible coordinates that reduce the distortion significantly. The system is independent of the embedding parameter k. In other words, it allows the user to embed data in any notational system and usually the smallest possible notational system is chosen to reduce the distortion. Several reversible techniques have been proposed recently. But reversible techniques that are compatible for high payload embedding and methods involving usage of pixel pair units have not evolved yet successfully. The proposed system achieves a balanced trade-off between embedding capacity and image quality by repeatedly hiding data in transform domain coefficients. This paper also addresses the issues associated with larger notational systems by embedding within sub-bands.
The paper is organized as follows. Section 2 explains in detail the proposed approach which includes the neighborhood design, repeated embedding enabled due to the reversibility achieved and framing of coefficient pairs. Section 3 presents the experimental results and discussion highlighting the trade-off achieved between embedding capacity and image quality. Section 4 concludes the paper.
Proposed method
The APPM [6] system has been redefined to support transform domain embedding, reversibility, repeated embedding and colour image compatibility. As the algorithm is reversible, the distorted cover image can be successfully reconstructed at the receiver side. This, in turn, paves way to apply multiple embedding over the stego image where the stego image can be once again used as cover. The embedding capacity is a multiple of ‘n’, where n is the number of levels used in multiple embedding. To improve the security of the system and make steganalysis harder, embedding is performed using 2D Integer Wavelet Transform (IWT). IWT produces round integer values which create an appropriate platform for reversible embedding of data.
The basic theme behind PPM technique is to use a pixel pair (x, y) as the coordinate, and search a coordinate (x’, y’) within a predefined neighborhood set ∅ (x, y) such that f(x’, y’) = S B , where ‘f’ is the extraction function and S B is the message digit in a B-ary notational system to be concealed. Data embedding is performed by simply replacing (x, y) with (x’, y’).
Extraction function and neighborhood set
The design of neighbourhood set and extraction function should possess the following attributes.
There should be exactly B coordinates in ∅ (x, y).
All the values in the range 0: B-1 should be present in ∅ (x, y) and should be mutually exclusive.
The design of ∅ (x, y) and f (x, y) should be such that embedding digits in any notational system should achieve lower embedding distortion.
The design of extraction function f (x, y) and neighborhood set ∅ (x, y) has to fulfill the following requirements: all the values of f (x, y) in the embedding map M
E
have to be mutually exclusive, and the summation of the squared distances between all coordinates in ∅ (x, y) and (0, 0) has to be the smallest.
The solution of ∅ (x, y) and f (x, y) is indeed a discrete optimization problem. The problem is stated as:
Given a Base B and an integer pair (x, y), (1) can be solved to obtain a constant CB and B pairs of (x i , y i ). These B pairs of (x i , y i ) are denoted by ∅B = (x, y) which is the neighbourhood set of (x, y). Table 1 lists the constants satisfying (1) for base notation up to 64. For a given B, it is possible to have more than one CB and ∅B = (x, y) satisfying (1). Table 1 only lists the smallest.
Figure 1 shows some examples of embedding maps. Table 2 shows the generalized neighbourhood set that represents the increment / decrement designated by the corresponding modulus distance in the embedding map. The shaded region designates the neighbourhood set of Base = 41. It is clearly seen that this design of neighbourhood set has less number of extreme corners so that the resulting Mean Square Error will be very less when compared to Diamond Encoding. In Diamond Encoding, the neighbourhood set is characterized by diamond shape and has a large number of corners that result in high distortion.
Reversible algorithms not only extract all the secret data successfully, but also recover the original cover image after extraction. EAPPM is one such algorithm that can apply multiple embedding exploiting reversibility. In EAPPM, the values of the modulus distance are used to construct a LUT using which the original cover image is reconstructed at the extraction module. Modulus distance is the key factor for the modifications imposed on the cover coefficient pairs. So the same modulus distance can be used to reverse the effect of increment / decrement at the extraction module. At the extraction module, discrete optimization problem is solved and discrete optimization parameter CB and neighbourhood set ∅B are found. Then the signs of the neighbourhood set are reversed so as to restore the modified coefficient pairs.
For Ex: Consider a coefficient pair (x, y) = (30, 58). To embed a secret digit SB = 2141, f = (30 + 58 * 6) mod 41 = 9. Modulus distance, dt = (21 - 9) mod 41 = 12. The modulus distance 12 in the Embedding Map ME is mapped to the corresponding neighbourhood set as in the Table 2. The corresponding coordinate is (0, +2), so that the value of x is kept as such and the value of y is incremented by 2. The resulting stego coefficient pair is (x’, y’) = (30, 60). At the extraction module, using the same modulus distance from the LUT, the sign is reversed as (0, −2). The value of y’ is decremented by 2. Hence, the original coefficient pair (x, y) = (30, 58) is successfully obtained.
As the modulus distance values are retained in the LUT as a backup, the stego images can be used as cover image to support multiple embedding. But the limitation of the APPM scheme is that embedding distortion increases with larger base notation and the stego images do not yield themselves for embedding as the PSNR values decrease considerably. Hence, to make the technique to be applicable for medical images, coefficient pairs have been applied with repeated embedding, picking them from cross colored planes and also across sub-bands.
Coefficient pair selection
The paper proposes three different approaches of reversible data hiding where every approach considers transform domain coefficients paired from sub-bands that are obtained as a result of wavelet decomposition on colour planes individually.
Approach 1 embeds in coefficient pairs that belong to the same pixel. The embedding approach includes twelve pairs where every coefficient is considered twice. The twelve coefficients are gathered one each of the four sub-bands of all three colour planes and the order in which the coefficients are used for embedding is shown in Table 3. Here A, H, V and D represent the approximation, Horizontal, Vertical and Diagonal sub-bands of the cover image applied with IWT. Also r, g and b represent the three colour planes and each colour plane is individually applied with IWT. APPM considers non overlapping adjacent pixel pairs from the spatial domain while this proposed approach considers coefficient pairs from transform domain. The coefficient pair is selected in such a way that the coefficients which form a pair belong to different sub-bands as well as different colour planes.
Aiming to improve image quality by confining embedding distortions, Approach 2 has been framed to consider coefficient pairs from the same sub-band but do not correspond to the same colour plane and the choice of the coefficient pairs is as shown in Table 3. Approaches 1 & 2 embedded in 12 coefficient pairs where every coefficient has been used twice. Approach 3 reduced the payload used by embedding only in 4 coefficient pairs to solve the problem of working with higher base notations. The proposed approaches aim to achieve a balanced trade-off by having the improved embedding capacity and also meeting the benchmark required for medical images, say 48 dB.
Embedding procedure
Input: Cover image I of size M x N, secret bit stream S, and seed k.
Output: Stego image I’, Base Value B, Seed k and LUT.
Apply 2D Integer Wavelet transform to the cover image. Find the minimum B satisfying (2) and convert S into a list of digits with a B-ary notational system to embed all the secret digits in the given image
Convert the bit stream into list of digits in B - ary notational system. Solve the discrete optimization problem to find the Discrete Optimization Parameter CB and Neighbourhood Set ∅B
Construct a non-repeat random embedding sequence Q using a seed ‘k’. Embed a message digit SB, selecting two transform domain coefficients (x, y) of the cover image in the order specified in Table 3 and calculate f(x, y) = (x + (y * CB))modB Calculate the Modulus Distance d, d = (SB - f)modB. Find the location of obtained modulus distance in the embedding map and corresponding coordinate in the neighbourhood set. Replace the original coefficient pair (x, y) with the modified coefficient pair (x’, y’) as per the increment / decrement designated by the coordinate in the neighbourhood set. Treat overflow and underflow: If x’ >255, replace x’ by x’ - B | If x’ <0, replace x’ by x’ + B If y’ >255, replace y’ by y’ - B | If y’ <0, replace y’ by y’ + B Repeat Steps 6–9 until all the message digits are embedded. Apply 2D Inverse Integer Wavelet transform to obtain the stego image I’. Finally, take a back-up of all the modulus distance values and construct a LUT of size (3xMxN).
Input: Stego image I’, Base B, Seed k and LUT
Output: Secret bit stream S, reconstructed cover image I
Solve the discrete optimization problem to find the Discrete Optimization Parameter C
B
and Neighbourhood Set ∅
B
. Reverse the signs of the neighbourhood set for restoring the modification occurred during embedding. Apply 2D Integer Wavelet Transform to the stego image. Select a coefficient pair (x’, y’) in the reverse order specified in Table 3 and the corresponding modulus distance in LUT. Calculate f(x’, y’) = (x’ + (y’ * CB))modB as the embedded digit. Find the location of modulus distance in the embedding map and corresponding coordinate in the neighbourhood set. Replace the stego coefficient pair (x’, y’) with the original coefficient pair (x, y) as per the increment / decrement designated by the coordinate in the neighbourhood set. Repeat Steps 3 to 5 until all the message digits are extracted. To obtain the original secret bit stream, convert the extracted secret digits into binary. Apply 2D Inverse Integer Wavelet Transform to obtain the original cover image.
Despite achieving reversibility, the benefits cannot be immediately reaped as the embedding distortion gets increased with higher notational systems. This limits the capability of the system to employ multiple embedding. Hence the embedding algorithm has been enhanced to consider sub-band coefficients of the transformed cover image.
Experimental results and discussion
In our experiments, the quality of the stego-image is evaluated by the parameter PSNR, a well-known criterion to measure the distortion between the cover image and stego-image is defined as follows:
Here, the symbols I(i, j) and I’(i, j) represent the pixel values of the cover image and stego-image in the position (i, j), respectively, and m and n are the width and height of the original image.
Experimentation has been performed over four standard test images, namely Baboon, Boat, Peppers and Lena, each of size 512×512. All the images have been subjected to the proposed approaches for different values of base notation, say B = 41, 25, 13 and 5. The obtained results have been compared with a well known and equivalent high capacity hiding scheme, Diamond Encoding [5]. As DE and APPM [6] are spatial domain schemes and the proposed approaches frame coefficient pairs in the transform domain, a direct comparison cannot be made. Hence, for comparison sake, DE has been applied in the transform domain after enabling reversibility. The modified scheme is referred to as Reversible Diamond Encoding (RDE).
From Table 4, it is obvious that higher base notations reduce the PSNR below 48 dB as they introduce heavy embedding distortion. For the technique to be applicable for medical images, the base notation should be confined to smaller values. Approach 1 has considered 12 pairs of transform coefficients that belong to a single pixel after being applied with wavelet decomposition. Every coefficient has been considered twice and repeated embedding has been performed. Approach 1 has framed coefficient pairs across colour planes and also across sub-bands. As embedding distortions are allowed to extend over both colour planes and sub-bands by this approach, only base values B = 13 and 5 were observed to be fit for medical images.
Table 4 also presents the experimental details of approach 2. The PSNR values improve as the coefficient pairs have been selected from within sub-bands thus preventing the embedding distortion to be spread across sub-bands. By confining the embedding distortions, the technique is able to use higher base notations thus improving embedding capacity. By injecting secret digits into transform domain coefficients of same sub-band, this approach enabled B = 25 to be included for use with medical images.
The results of Approach 3 are presented in Table 4 where slightly improved PSNR values are obtained by reducing the payload. Approach 3 embeds thinner payloads by restricting transform domain coefficients that belong to a single pixel to be used only once. Approach 3 also intentionally leaves out 2 of the three possible pairings across colour planes. This reduction in payload enables all base notations to be used, but can achieve an embedding capacity of only2 bpp.
Out of the three approaches, Approach 2 emerged as the best by achieving a trade-off between two contradicting parameters namely, embedding capacity and image quality. For two images, namely Boat and Peppers, Approach 2 allows all bases to be used making the embedding capacity as high as 6 bpp. For the other images, the embedding capacity is limited to 5 bpp as for B = 41, the PSNR drops below 48 dB. On comparison with the spatial domain techniques DE [5] and APPM [6], pixel pairing is done with spatial neighbors, Approach 2 proved superior where the embedding capacity is improved by six times for the same image quality.
Table 5 presents the stego images obtained for the various approaches proposed for a base value of 41. The cover images were recovered with perfect fidelity indicated by a PSNR of ∞ measured between original cover image and recovered cover image.
Subjecting the stego images to Steganalysis [7] by a custom built Steganalyzer, the detection accuracy for RDE is 49% while that of EAPPM is 47. 4% indicating EAPPM scheme is more secure than RDE. EAPPM scheme produces better stego images than RDE scheme as the neighborhood of RDE possess sharp corners whereas EAPPM has carefully designed neighborhood. The effect of carefully designed neighborhood is still enhanced by the proposed approaches in the selection of coefficient pairs and confinement of payload to a minimum.
Thus EAPPM improves the embedding capacity considerably using repeated embedding in coefficient pairs. It allows users to select digits in any notational system for data embedding, and thus achieves a better stego image quality by reducing the impact of under flown and overflown pixel values. The proposed approaches embed within transform domain sub-bands to address the issues associated with higher base notation. This has paved the way for achieving a tradeoff between embedding capacity and image quality. The inherent limitations of a PPM scheme and the problems encountered with higher dimensional base notation to represent the secret digits have been addressed. Confining to lower base values and lean payloads have contributed to image quality, whereas reversibility enabled repeated embedding has enabled voluminouspayloads.