A New Image Watermarking Scheme Using Genetic Algorithm and Residual Numbers with Discrete Wavelet Transform ()
1. Introduction
The internet provides the opportunity for people to copy, process and transmit multimedia content including text, graphics, images and videos, making it easy and convenient for content creators to market their products to clients. However, acts by some individuals such as piracy, infringement and stealing of online content tend to damage intellectual property rights and affect the market order of content owners [1] . This, therefore, makes it necessary to employ techniques for information hiding. Information hiding is the process of embedding a secret message into cover content in order to make the information imperceptible and conceal the existence of the secret message [2] . Information hiding includes steganography, digital watermarking and convert communication. Among these three technologies, digital watermarking is the best solution to copyright protection for digital content [3] . Digital watermarking is the ability to embed information (either visible or invisible) into the cover information [4] . Digital watermarking can be classified based on the domain for spatial or spectral; the type of document for text, image, audio or video; or human perception for robust and fragile [5] . There exist various forms of attacks (active, passive collusion, forgery and so on) on watermarks. More prevalent are these attacks recently as a result of the growth in the digital ecosystem especially, internet technology. Attempts have been made over the years to handle these attacks by building robust watermark schemes. Indeed, robustness is a requirement for digital watermarking. However, in order to achieve robustness, there has always been a trade-off with imperceptibility. Imperceptibility and robustness can be achieved by leveraging techniques that can bring imperceptibility but at the same time increase the computational layers to build robust schemes. This paper, therefore, seeks to proffer a solution to these threats in the modern era by leveraging the selection and crossover operators of the genetic algorithm (GA) and at the same time, the inherent properties of the residue number system (RNS) to encrypt an image before it will be embedded in a cover image using a three-level Discrete Wavelet Transforms (3-DWT). The rest of the paper is organised as follows: Section 2 presents the necessary background information as well as a review of some related works; the proposed scheme is presented in Section 3. The results of the scheme are analysed in Section 5 as well as an evaluation of its performance whiles Section 3 concludes the paper.
2. Background and Related Works
Watermarking is a technique that has been in existence for several centuries now. Watermarks were found initially in plain paper and in paper bills. However, digital watermarking emerged in recent years [5] [6] . The main purpose of digital watermarking is for copyright protection, so that when pirated products emerge, content owners are able to extract some hidden information in the content to prove ownership of the content in a court of law [7] .
GA is a search technique used to find true and approximate solutions to optimisation and search problems. It forms part of the Evolutionist Algorithm (EA) category which makes use of evolution theory in solving problems. These algorithms are biologically inspired because they mimic how living creatures try to fit into their environment for survival. The basic operators of GA are selection, crossover and mutation. It begins with the selection of chromosomes from a population of chromosomes which undergoes modification (recombination and mating) to form a new population. GAs have seen significant applications in solving complex real world computation problems including Neural networks, Vehicle routing problems, and Task scheduling among others.
A residue number system (RNS) is a number system that represents integers as a vector of remainders of a given pairwise co-prime integers called the moduli. The residue number system is a non-weighted number system which is different from the weighted number systems like binary or decimal number systems. This number system possesses inherent properties such as parallelism, fault tolerance, and modularity that make it suitable for application in many research areas. RNS has been widely applied in the area of subtraction, multiplication and addition such as Digital Signal Processing (DSP) due to its computational speed. However, it has not gained much popularity in areas of division such as Signal Detection, Magnitude Comparison and Overflow Detection [8] . Given a set of relatively prime moduli
, such that the greatest common divisor (gcd) between any pair is one, i.e.
, for
. We can compute
, where S and M are the base and the dynamic range of the RNS respectively. In the RNS, any number X which is less than M can be denoted as a vector
, where
. Such an integer X is a legitimate number and has a unique representation within the dynamic range, M [9] . Assume that two integers
for RNS representation are
, and
, respectively. With a single step, we can compute
where
denotes an addition, subtraction, or multiplication. This property provides parallel operation on all digits without any carry between different residue digits [9] .
Forward conversion in RNS refers to the decomposition of a weighted number into RNS representation. This process is relatively a straight forward operation where modulus operation is performed on the weighted number with respect to the moduli set. For example, given a moduli set
, then the weighted number (in this case, binary or decimal) is represented in RNS as
. The reverse (RNS-to-binary/decimal) conversion on the other hand is a more complex operation which is computed generally by two techniques; the Chinese Remainder Theorem (CRT) and the Mixed Radix Conversion (MRC).
The CRT is computed as [10] ;
(1)
where,
Wavelet Transform is a modern technique which is recently being used in digital image processing, watermarking, compression, and other applications, [11] . The transforms are based on the wavelet of varying frequency and limited duration. A wavelet is a mathematical function that is used in image processing. Wavelets consist of two fundamental properties: scale and location. The scale refers to how stretched or “squeezed a wavelet is. Location defines where the wavelet is positioned in time. The properties of the wavelet are capable of decomposing an original signal into wavelet transform coefficients. The original signal can be reconstructed by performing an Inverse Wavelet Transformation on these coefficients. There are two types of Wavelet Transforms, Continuous Wavelet Transform (CWT) and DWT [12] .
Many researchers have proposed various schemes for digital image watermarking by combining GA and other techniques or RNS and other techniques. The work by [13] presented a Wavelet-Hadamard GA and decision tree-based image watermarking scheme. The GA was used in the search for optimization to satisfy the tradeoff between robustness and imperceptibility. According to the proposed scheme, embedding a secret image into a cover image will involve a modification of the frequency coefficients. The paper, therefore, utilized GA to modify the coefficients of the host image. However, this technique was proven to be convenient for only offline applications and cannot withstand attacks when applied to online content. Another work by [14] also presented a watermarking technique that is based on Redundant Wavelet Transform (RWT) and the GA. In this work, RWT is employed to reduce the information loss in the extracted image as this is the case, according to the paper in conventional wavelet transforms. The GA was used here to optimize a watermarking constant. The approach achieved resilience towards attacks but it is costly in terms of computational time. Also, [15] reported on a digital signature-based watermarking scheme which uses integer wavelet transform and singular value decomposition. The proposed approach employed two algorithms, GA and Particular Swarm Optimisation (PSO). The signature generation and embedding procedure was based on singular values. However, the approach adopted a lot of methods which introduced computational complexities and delays in the execution time. Again, [16] also established a coding scheme which can be used to insert data into an image and to extract the data from the image without changing the image file. This scheme is established based on Discrete Cosine Transform (DCT) and GA. In their work, the cover image is decomposed into 3-level using DCT then GA is used for the embedding process. However, the problem with DCT is that images are broken into blocks of 8 × 8, 16 × 16 or bigger. Therefore, when the image is reduced to higher compression ratios, the blocks become visible.
The work in [17] resorted to the use of Data Encryption Standard (DES) and RNS for image watermarking. The secret image was taken through a Simple-DES (SDES) using a key image, then the encrypted image was watermarked using another image and a matrix. The work then applied RNS to produce a DES watermarked RNS encoded image. The scheme showed some form of robustness but utilized only one key. The scheme in [18] proposed a high payload watermarking using RNS. The proposed approach takes pixel values from three watermarked images and embeds them into the cover image. The researchers converted the colour image into 3 gray planes (Red, Blue and Green) and applied RNS on the Blue plain and went further to do more RNS arithmetic on the bits of the chosen plain in order to watermark. This is, however, a single layer scheme since it utilizes only residue numbers for the watermarking process. Also, the work by [19] discussed the use of Advance Encryption Standard (AES) with a hybrid of DWT and DCT watermarking techniques and RNS for image watermarking. In this work, a grayscale image is given as an input to AES-128 using a key. The output is then watermarked using DWT and DCT and the watermarked image is then passed through the RNS procedure for security. However, the AES technique has a simpler algebraic structure and encrypts every block the same way. Therefore, when an attacker succeeds in decrypting one block, it becomes simpler to get the remaining blocks. From the ensued, GA has been combined with other techniques in some cases, and the RNS has also been used with some other techniques as well. However, both the GA and RNS have not been utilized for watermarking. This paper, therefore, seeks to leverage both techniques and in addition, DWT to develop a robust watermark scheme without compromising on the throughput.
3. Proposed Scheme
The proposed scheme utilizes a combination of three techniques, namely, GA, RNS and DWT in a three-layered manner to achieve its objective. The RNS component comprises a forwarded and reverse conversion process, where the decimal/binary values are converted into residues using the moduli set
, where
,
and
; the residual bits are then used in the choice of pixel vectors for single point crossover operations and embedding using a 3-DWT. These are the encoding processes that result in the pixel scramble (encryption), which is eventually watermarked. The decoding involves a reversal of these processes; the residual bits are converted back to the binary/decimal representation for the recomposition of pixel values of the original image. The moduli set for the RNS conversion processes and manipulation in [10] are adopted in this paper. Generally the encoding processes of the proposed scheme are as follows:
1. For any
image, extract pixel values
2. Given the moduli set
, choose n such that
in order that every pixel can be represented.
3. Find
,
is a representation of
in binary and of length
.
is a random key for the purpose of encryption whilst
is the encryption key.
4. Determine
subkeys,
by splitting
into equal n-bits starting from the LSB.
5. Note that the pixels of the image forms a matrix starting from location 0 to location
. The subkeys are then used as a selection criterion for crossover operation.
6. To further scramble the image, map bits in
to pixel locations from left to right; and compute RNS forward conversion on pixel locations where
.
7. The residual values are then replaced with corresponding pixel values to form the new encrypted image.
8. Finally, to embed, decompose both host image and encrypted image of sizes
into four non-overlapping 3-DWT sub-bands as shown in Figure 1. Thereafter, use Equation (2);
(2)
and
are scaling factors for the host image and watermark respectively. The scaling factors are varied from 0.0 to 1.0 to get the optimal values for embedding the image [20] . As the value of
increases the value of
decreases so that the host image becomes more visible whiles the scrambled image becomes invisible.
And that for the decoding processes will be to find a reverse process for each stage of the encoding processes. Equation 3 is used to extract the encrypted image through to the RNS reverse conversion stage where the reverse converter in [10] is adopted.
(3)
These processes are summarised as a pseudocode in Algorithm 1.
The proposed scheme was simulated using MATLAB on a Core i5 processor. Firstly, the image referred to in this paper as “Pepper” was taken through the encryption process. The results of this experiment are shown in Figure 2. From the experiment, it can be observed that the image is totally distorted. Regarding the security of the image, the attacker will have to first know the moduli set used to generate the random key and how the GA process was conducted with the sub-keys obtained from the expanded key.
Next, the encrypted image was embedded into the Host image, “Lena” using the Equation 2 with scaling factors,
and
as shown in Figure 3. These scaling factors were chosen after conducting series of tests on
the two images by varying between 0.0 to 1.0. This provided a suitable blend of the two images and conceals the existence of the encrypted image and leaves no traces of suspicion to an attacker.
To extract the encrypted image from the host image, DWT is applied on both the watermarked image and host image and then alpha blending. Equation 3 is applied on the low frequency sub-bands of both images. After extraction, the inverse DWT is applied on the encrypted image. The encrypted image is then taken through reverse GA and RNS procedure to obtain the original image. Figure 4 shows the experiment conducted on the extraction process. It is obvious that the decrypted image produced a similar image as the original and does not cause any distortion as a result of the encryption process.
4. Results Analysis
The results from the simulation of the proposed scheme were analyzed based on standard metrics on imperceptibility and robustness for watermarking schemes.
4.1. Visual Testing
As shown in Figure 3, it is obvious that the encrypted image looks very chaotic at sight and does not provide any clue that points to the original image. Therefore, it can be concluded that there are no perceptual similarities between the original image and the encrypted image. It can also be observed from Figure 4 that the watermarked image is similar to the original “Lena” image from the human visual perspective and does not reveal any clue to the fact that there is an embedded image in it. The decrypted image in Figure 5 also looks exactly the same as the original “Pepper”, showing no form of distortion as a result of the encryption process.
4.2. Sensitivity Analysis
In order to affirm the claim that the encrypted image differ significantly from the original image, the following statistical measures were performed:
A. MSE and PSNR Analysis
The Mean Square Error (MSE) is the average of the squares of the “errors” between the original image and the encrypted image. The error is the measure of the extent to which the values of the original image differ from the encrypted
Figure 4. Extraction of encrypted image.
image. This can be represented mathematically as [1] ;
(4)
where
represents the original image whiles C(i,j) represents the watermarked image, M and N are the number of rows and columns of the two images. The MSE values indicates the measure of the difference between the original and the watermarked image. The higher the MSE value, the larger the difference between the original image and the watermarked image and vice versa.
Peak Signal to Noise Ratio (PSNR) is an expression of the ratio of peak signal power to noise power. This can be represented mathematically as [3] ;
(5)
where
is the maximum signal value of the input image (I) data type. For example, if the input image has a double-precision floating point data type, then
, else if it has an 8-bit unsigned integer data type,
. The lower the PSNR value, the larger the distortion between the original and the watermarked image.
B. NPCR and UACI Analysis
Number of Pixel Change Rate (NPCR) means the percentage difference of pixels among the original image and the encrypted image. The NPCR can be defined mathematically as [21] ;
(6)
(7)
Let
be the pixel values of the one image (original, encrypted or watermarked) and
, another image (original, encrypted or watermarked) in the two experiments conducted at the ith pixel row M and jth column N . The value of NPCR shows the degree to which the pixels have been randomly changed. Therefore, the higher the value, the more the change in pixel locations and vice versa.
The Unified Average Changing Intensity (UACI) is the average intensity of difference in pixels. The UACI can also be defined mathematically as [4] ;
(8)
The UACI values from Table 1 depicts that most of the pixel values of the encrypted image have been changed as compared to the original image and vice versa on one hand and that for the watermarked image and the original shows a minimal change.
Table 1 depicts the analysis of the proposed algorithm based on the MSE, PSNR, NPCR and UACI metrics. The higher value of MSE recorded in the Original & Encrypted image shows the larger difference between the original image and the encrypted while the lower value of MSE recorded in the Original & Watermarked image also shows the similarities between the original image and the watermarked image. On the other hand, the lower value of PSNR recorded in the Original & Encrypted indicates larger visual distortion between the original and the encrypted image, whiles the higher values of PSNR in the Original & Watermarked image show how negligible the distortion between the Original and Watermarked image is.
The high measure recorded for the NPCR in Original & Encrypted indicates that the majority of the pixel positions have been randomly changed while that of the Original & Watermarked shows that, just a few of the pixels have been changed. The lower UACI value in the Original & Encrypted image also depicts the higher change in pixel intensity of the encrypted image as compared to the original image while the higher value of the Original & Watermarked image shows minimal change in pixel intensity as compared to the original. This makes it difficult to associate the encrypted image to the original image which could provide clues for attackers. On the other hand, attackers are not able to identify that there is a hidden image in the “watermarked Lena” image since there is no much distortion in the watermarked image.
4.3. Statistical Analysis
The statistical analysis of an encrypted or watermarked image provides much information about the security of the image.
A. Histogram Analysis
An encrypted image is secured against attacks if its histogram is entirely different from the histogram of its original image. Thus, the two images do not contain statistical similarities [22] . An analysis of the results from Figure 5 reveal that the histogram of the encrypted image is totally different from the histogram
Table 1. PSNR, MSE, NPCR AND UACI comparison.
Figure 5. Histogram of original and encrypted images.
of its original image. It does not contain any statistical similarities that may provide any clue about its original image. Therefore, the proposed scheme is secure against histogram attacks.
Figure 5 shows the histogram of the original image and the encrypted image. The histogram of the original image contains large sharp rises and declines whiles the histogram of the encrypted image shows uniform distribution making them differ significantly from each other and has no statistical similarities.
Figure 6 shows the histogram of the original and watermarked images. It can be seen clearly that, both histograms possesses statistical similarities making it difficult for an attacker to detect that there is an embedded image.
4.4. Speed Test
The speed test is a measure of the time taken to execute the proposed scheme. How complex the scheme is, is determine by its execution time. Table 2 shows the time taken (in seconds) for encrypting and embedding the encrypted image and the extraction and decryption of the encrypted image. The execution time of the algorithm from the table shows optimal performance.
4.5. Performance Evaluation
The performance of the scheme is compared with existing schemes by [23] whose work utilised nonlinear spatiotemporal chaotic map and integer wavelet
Figure 6. Histogram of original and watermarked images.
Table 2. Encrypted vs. watermarked: MSE and PSNR comparison.
transform (IWT) to encrypt an image. The proposed scheme was also compared with the existing scheme by [24] which, also employed DWT to perform image watermarking. Table 2 depicts the level of noise or changes introduced into the encrypted images. The values for the encrypted image in the table indicates that, there is much distortion in the proposed scheme as compared to the existing scheme whiles that of the watermarked image indicates that minimal distortion exists in the watermarked image of the proposed scheme as compared to the existing scheme.
Table 3 also compares the NPCR and UACI values of the proposed scheme with the existing scheme by [25] whose work focused on the use of hash function with two-round diffusion process to encrypt an image whiles The NPCR and UACI values of the proposed scheme on the watermarked image was also compared with the existing scheme by [26] . The existing scheme leveraged on non sub-sampled contourlet transform (NSCT), redundant discrete wavelet transform (RDWT) and singular value decomposition (SVD) approach. The results indicates that the proposed scheme performed favourably better as compared to the existing schemes.
Table 3. Encrypted vs. watermarked: NPCR and UACI comparison.
5. Conclusion
Privacy in this era of technological dispensation has become a challenge in the film and TV industry. In this paper, a new digital watermarking scheme using GA and Residual Numbers (GARN) was proposed. The results of the simulation show that the proposed scheme is imperceptible and robust.