Methods of the steganography are characterized by such efficiency rates as invisibility, robustness and capacity. There is considered the maximum capacity support of the information embedding into the DCT-domain. It is investigated the known algorithm that realizes the adaptive information embedding into the digital images frequency domain. The adaptivity is reached due to the image partition into the unequal blocks using a quad-tree. There is received the improved modification of the algorithm based on the reference point variation in case of the image partition into the blocks. The received modification allows to provide the better invisibility at the same capacity.
Providing of an acceptable level of invisibility of embedding is the mandatory requirement to all steganographic methods and algorithms. Therefore it is possible to consider the contrast of two indexes of embedding effectiveness instead of three: capacity and robustness. The given contrast corresponds to the separation of methods of information embedding in digital objects into methods of arbitrary message embedding and methods of digital watermark embedding.
The methods which refer to the first class correspond to the classical concept of steganography and are designed for providing of confidentiality of the embedded information. In the second case, it is a question of copyright protection of digital objects. Digital watermarks represent special marks which contain information on the owners of the given objects. Digital watermarks are used for authentication of owners of digital objects, as well as for authentication of digital objects themselves including detection of falsifications.
It is necessary to note, that often embedding of digital watermarks does not refer to digital steganography and is not considered as a separate direction in the field of data hiding. However, such division is not always appropriate. Many methods of embedding of digital watermarks can be also used for embedding of limited capacity arbitrary messages into digital objects. Besides, there are methods enabling the control of the ratio between capacity and robustness of embedding. Therefore, further, we will equate methods of data hiding and methods of digital steganography.
Apart from tasks being solved, methods of digital steganography are classified according to the types of digital o bjects they process. Mainly, they are audio and video data and digital images. In the given paper we consider digital images as digital objects.
The methods of digital steganography operating with digital images divide on two big groups on domain of data embedding: embedding in the spatial domain and embedding in the frequency domain. The pixel matrix of a digital image is named as the spatial domain, and the frequency domain is the matrix of values received from a digital image by application of any frequency transform. The given data are also named as coefficients of frequency transform. In digital image processing including the embedding information into images the following transforms are used: discrete Fourier transform (DFT), discrete cosine transform (DCT), Walsh-Hadamard transform (WHT), various versions of discrete wavelet transform (DWT).
Image Processing, Geoinformation Technology and Information Security / O.O. Evsutin, A.O. Osipov
In the present paper, providing the maximum capacity of embedding in the frequency domain of discrete cosine conversion at maintenance of comprehensible quality of the cover image is considered. The known algorithm of high-density embedding is investigated and a new improved algorithm is offered.
There exist many algorithms where information embedding is carried out in the frequency domain of digital images.
Frequency transforms associate the matrix of pixels of a digital image with the matrix of frequency coefficients. Frequency
coefficients can be divided on significant (carrying the basic information of a source image), and insignificant (that can be
discarded or modified without any noticeable distortions in the initial image) [
Let us note some research papers of last years.
Algorithms based on DFT are mainly used for embedding of digital watermarks. It is connected to properties of the given transform which do not permit to ensure the high capacity of embedding; however, they ensure resistance against some types of attacks on cover images. The majority of such algorithms operate with elements of the amplitude Fourier spectrum.
In the algorithm presented in [
In paper [
In [
Another large class of steganographic algorithms works with DCT frequency domain. This class contains both algorithms of digital watermark embedding and algorithms of arbitrary message embedding. Besides, all algorithms of embedding of information into compressed JPEG images also operate with DCT coefficients because the given frequency transform is the basis of an appropriate compression method.
The papers [
The QIM method presented in [7] has capacity. It operates with low-frequency DCT coefficients. The given method uses two different quantizers for embedding zero and on-bits of the secret message into DCT coefficients of the cover image.
Paper [8] presents an instance where the increase of the effectiveness of digital watermark embedding is considered as an optimisation problem. The genetic algorithm is applied to its solution. It is used for sampling of an optimal order of embedding of parts of a digital watermark into DCT coefficients of the cover image.
Papers [9–11] present algorithms based on discrete wavelet transform.
Paper [9] considers embedding of biometric data of the owner into a digital image. The digital watermark represents a picture of a retina of an eye. Details wavelet coefficients are used for embedding. The digital watermark is converted to a character sequence existing in alphabet 1, 1 , and embedding is carried out in an additive way. The choice of certain coefficients for embedding is carried out by means of a key.
Paper [10] presents the algorithm of embedding of semi fragile digital watermarks. Such digital watermarks are used for protection of images against falsification. They are resistant to usual processing of images (compression, resizing, filtering), but are destroyed in the case of modification of the image content, for example, when adding or removing of objects. The algorithm presented in [10] divides the image into blocks of an equal size, transfers them in the frequency domain by means of DWT, then low-frequency components of certain blocks are embedded in the high-frequency components of other blocks. The recombination of blocks is carried out by means of the generalized cat map. In [10] an elementary representative of DWT set — Haar transform — is used as frequency transform.
The algorithm of embedding presented in [11] is based on block quantization of DWT coefficients in the quadrant middlefrequency sub-band LH2. One bit of the message is built in into the block of k DWT coefficients. Embedding consists in the modification of summarised energy of coefficients of the block so that depending on the value of the built-in bit, it meets certain condition. The modification of value k changes the ratio between capacity and robustness. If k is increased, the built-in message obtains properties of a digital watermark.
In paper [12] embedding is carried out in the WHT frequency domain. For this purpose the image is divided into blocks by 4×4 pixels; and WHT is applied to each block. The algorithm of embedding is built using a linear predictor function. Values o f AC-coefficients of WHT of each block are predicted on the basis of DC-coefficient values of 8 adjacent blocks. The message bits are built in prediction errors according to the LSB method. To determine the weighting coefficients of the linear predictor function the neural network is used.
A series of publications [13–15] represents results of research directed on reaching the maximum capacity of embedding in the frequency domain of discrete cosine transform.
Image Processing, Geoinformation Technology and Information Security / O.O. Evsutin, A.O. Osipov
In paper [13], the cover image is divided into non-overlapping blocks by the size of m m pixels; DCT is applied to each block. For embedding, a part of the DCT-coefficient block is used, that forms a square in the right lower angle. This square corresponds to the least significant high-frequency coefficients and has a different size for different blocks. The size of embedding area is defined by the quantization matrix. Embedding consists in replacement of DCT-coefficients in the area of embedding by elements of the secret message. The secret message is also a digital image; and pixels of this image are exposed to additional quantization before embedding.
The given approach is developed in papers [14, 15]. The algorithm presented in [14] represents a different method of the secret image processing before embedding it. In [15], the cover image is divided into homogeneous blocks of pixels having unequal size by using quad-tree, that allows to raise the efficiency of embedding.
The present paper develops the offered in [13–15] approaches to high-capacity embedding of information into the frequency domain of discrete cosine transform. In the following section of the paper a more detailed description of algorithm [15] is given; probable ways of its improvement are defined and a new more effective algorithm is offered.
Let's consider the QTAR embedding algorithm presented in article [12] in more details.
Square cover image I ; secret image S ; homogeneity threshold of block Th ; minimum block size m ; square matrix of quantization of a size 8×8 Q ; scale factor k .
Cover image containing a secret image I .
Step 1. To execute recursive partition of each inhomogeneous square pixel block of the cover image into four equal subblocks. The cover image is taken as an initial block. The block partition stops if its size (the square side) is less or equal to m or if it is homogeneous. The block is recognized as inhomogeneous if the difference between the maximum and minimum values of pixels is higher than 255Th value.
Step 2. To execute the scaling of the secret image pixels by formula ~si k 255 si .
Step 3. For j 1, N , where N — is amount of blocks in the quad-tree to execute as follows: Step 3.1. To execute two-dimensional DCT of the j-th block of pixels of the size m j m j .
Step 3.2. To expand matrix Q to the extent of m j m j using interpolation and to divide the DCT-coefficients of the block into elements of the given matrix with the subsequent round-off.
Step 3.3. To select a square area of the greatest possible size n j n j , consisting only of nulls in the right lower angle of each block of the quantized DCT-coefficients.
Step 3.4. In the initial block of DCT-coefficients (before quantization) to substitute area of embedding n2j with pixels of ~ modified secret image S .
Step 3.5. To execute inverse two-dimensional DCT.
Step 4. To return stego image I and key sequence n1, n2 , , nN and complete the algorithm.
The algorithm of extraction of the secret message is as follows.
stego image I ; key sequence n1, n2 , , nN ; threshold of block homogeneity Th ; minimum block size m ; scale factor k .
extracted secret image S .
Step 1. To represent the stego image in the form of a quad-tree out of N blocks with the size not less than m m pixels with the threshold value Th .
Step 2. For j 1, N to execute as follows: Step 2.1. To execute two-dimensional DCT of the j-th block of pixels with the size m j m j .
Step 2.2. To select in the right lower angle of the received block of DCT coefficients a square block of embedded data elements with the side n j .
Step 2.3. To execute an inverse scaling of the selected block elements using the formula sp 255 ~s , p 1, n 2j , to derive k p the block of pixels of the secret image.
Step 3. To restore secret image S from separate blocks of pixels.
Step 4. To return the extracted secret image S and to complete algorithm.
Generally, extracted image S does not coincide with initial secret image S . The pixels of the secret image are restored inaccurately because of the round-offs originating at the scaling, but these distortions do not lead to considerable losses of
Image Processing, Geoinformation Technology and Information Security / O.O. Evsutin, A.O. Osipov quality.
Here it is necessary to note that the use of not compressed digital image as an secret message is an atypical solution because digital images differ with high redundancy. However, in the case of QTAR algorithm, the given solution is reasonable as the mentioned redundancy of images allows one to avoid considerable distortions during the scaling. Besides, restoring of the cover image from the modified DCT spectrum requires a round-off at the transition from real values to integer pixels, which leads to additional distortions of the embedded data.
Fig. 2 shows the partition of image “Lenna” onto homogeneous blocks with a quad-tree and the selection of embedding areas for various values of the threshold of homogeneity Th . It is accepted that the minimum block size in each case equals to 8.
The increase of the homogeneity threshold of the block leads to quad-tree simplification. Thus, the capacity decreases. In the instances presented in Fig. 2, the image capacity “Lenna” equals to 5,77, 5,76 and 4,86 bits per pixel accordingly.
The QTAR algorithm considers the cover image as the initial square block of pixels.Coordinates of the top left corner of the given initial block are named as an index point and designated as x, y . In the initial algorithm the given point has coordinates 0, 0 and cannot be changed. However, if the digital image is presented in the form of torus, for example as in cellular automata models [16], it is possible to choose any point of the cover image as an index point. The index point modification will change the form of the quad-tree and will affect the distribution of parts of the secret image on the cover image blocks.
The example is shown in Fig. 3. The index point is marked white. Other parameters of the algorithm of quad-tree construction in the above-mentioned example coincide with the analogous parameters of the example shown in Fig. 2a. 35,5 35,0 34,5 34,0 33,0 32,5 R PSN 33,5 29,50 29,25 29,00 R N PS28,75 28,50 28,25 33,0 32,5 R 32,0 N S P 31,5 31,0 31,5 31,0 30,5 30,0
6,55 7,25 BPP BPP
Image Processing, Geoinformation Technology and Information Security / O.O. Evsutin, A.O. Osipov
It is possible to see that the index point modification changes the quad-tree form, and it leads to the modification of indexes of capacity and quality of embedding.
Fig. 4 shows the modification of the given indexes at the index point modification by the example of four various images: “F15”, “Clouds”, “Jellyfish”, and “House”. The image “Baboon” was a secret image in each case. The parameters of algorithm of quad-tree construction were set as follows: Th 0,4 , m 8 . The embedding quality index is the peak signal-to-noise ratio (PSNR). The index of embedding capacity is the bits per pixel amount (BPP).
It is possible to see that the maximum capacity for the image “F15” is by default given by the index point, but the PSNR value can be increased approximately by 1,0 dB when maintaining capacity, which is essential. The capacity of embedding distinct from the maximum is given by the index point for the images “Clouds” and “Jellyfish”. Besides, in the case of the image “Clouds” the appropriate PSNR value is close to greatest possible one for the given capacity, and in case of the image “Jellyfish” the PSNR value can be essentially increased. The image “House” represents a cover image instance where the index point by default gives the greatest possible capacity and the PSNR value which is the greatest possible for the given capacity. However, in this case, it is possible to obtain quality improvement of embedding by 0,5–1,0 dB at the expense of insignificant decrease of capacity.
The presented instances show that the index point modification allows us to increase value PSNR at equal or comparable BPP value, and on occasion to raise both given indexes.
The second possible approach to improvement of QTAR algorithm is connected to selecting of the threshold value. Since the brightness of an image makes essential impact on perception of the given image by human sight, in the present paper it is offered to introduce different threshold values for blocks of the image with different brightness. For this purpose, let us divide all brightness range of pixels on three equal sub-bands 0, 255 0,85 85, 170 170, 255 define the threshold value of block homogeneity for each part and designate them as Th1 , Th2 , Th3 accordingly.
The instance is shown in Fig. 5. For the cover image “House” and the secret image “Baboon” the introduced threshold values were set as follows: Th1 0,9 , Th2 0,1 , Th3 0,4 . The graph shows the modification of PSNR and BPP indexes at the index point modification by analogy with the previous instances. It is possible to see that the given graph differs from the graph shown 7,0
BPP 6,70
BPP RN 31,0 S P 30,5 30,0 6,30
Thus, all given instances obviously confirm that the parameters introduced in the present paper make essential impact on effectiveness of embedding process. Besides, the given parameters can be used as the additional key information.
Exhaustive search of every possible value of an index point and homogeneity threshold of blocks is inconvenient, since it requires a great number of calculations. Therefore in the present research differential evolution (DE) is used for the solution of the given problem. It is the known metaheuristics widely used for solving the problems of optimization in various application areas, including digital steganography [17]. It allows to optimize sets of real heterogeneous parameters.
Since DE is a well-known optimization method, it is not described in the present article. Let us only mention that the DE algorithm operates with the following parameters: the size of population N , mutation coefficient F , probability of crossing over CR , number of calculations of objective function K .
Objective function is defined by the following formula: PSNR PSNRQTAR f PSNRQTAR 0,
BPP BPPQTAR
BPPQTAR , if PSNR PSNRQTAR and BPP BPPQTAR , otherwise, (1) where PSNRQT AR and BPPQTAR are values of efficiency indexes at embedding according to the initial QTAR algorithm.
Then the new algorithm of high-capacity embedding of the information in the frequency domain of discrete cosine transform of digital images on the basis of algorithm QTAR can be represented as follows:
Square cover image I ; secret image S ; minimal block size m ; matrix of quantization of the size 8×8 Q ; scale factor k ; parameters of DE algorithm.
Cover image containing the secret image I .
Step 1. To execute the scaling of the secret image pixels by formula ~si k 255 si .
Step 2. To build in the secret image S into the cover image I being the QTAR algorithm. To record the received values of quality indexes and embedding capacity as PSNR QT AR and BPP QTAR . To calculate the value of objective function by formula (1) and to record it as f max .
Step 3. To generate N vectors of form xi x, y, Th1, Th2 , Th3 , i 1, N .
Step 4. For i 1, N to execute the following:
Step 4.1. To represent the cover image in the form of a quad-tree consisting of M i blocks of pixels, using the vector of parameters xi x, y, Th1, Th2 , Th3 .
Step 4.2. For j 1, M i to execute the following:
Step 4.2.1. To execute the two-dimensional DCT of the j-th block of pixels with the size m j m j .
Image Processing, Geoinformation Technology and Information Security / O.O. Evsutin, A.O. Osipov
Step 4.2.2. To expand the matrix Q to the extent of m j m j using interpolation; and to divide the DCT-coefficients of a block into elements of the given matrix with the subsequent round-off.
Step 4.2.3. To select a square area of the greatest possible size n j n j , consisting only of nulls in the right lower angle of each block of quantized DCT-coefficients.
Step 4.2.4. In the initial block of DCT-coefficients (before quantization) to substitute the area of embedding n2j with pixels ~ of the modified secret image S .
Step 4.2.5. To execute the inverse two-dimensional DCT.
Step 4.3. To calculate values of quality indexes and capacity of embedding PSNR i and BPP i , and to calculate the value of objective function f i by formula (1).
Step 4.4. If f i f max , then to assign f max f i and to record the vector x i as the best solution x best . Step 5. To renew the population by rules of differential evolution.
Step 6. If the amount of evaluations of objective function does not exceed K , then to pass to step 4. Otherwise to pass to step 7.
Step 7. To build in secret image S into cover image I using the vector of parameters x best , then return stego image I and key sequence n1, n2 , , nM , x, y, Th1, Th2 , Th3 and complete the algorithm.
The extraction algorithm of the secret message is as follows.
stego image I ; key sequence n1, n2 , , nM , x, y, Th1, Th2 , Th3 ; minimum block size m ; scale factor k .
extracted secret image S .
Step 1. To represent the stego image in the form of a quad-tree out of M blocks of pixels with the size not less than m m pixels with the index point x, y and the threshold values Th1 , Th2 , Th3 .
Step 2. For j 1, M to execute the following: Step 2.1. To execute two-dimensional DCT of j-th block of pixels with the size of m j m j .
Step 2.2. To select in the right lower angle of the received block of DCT factors a square block of embedded data elements with the side n j .
Step 2.3. To execute an inverse scaling of the elements of the selected block using the formula sp 255 k ~sp , p 1, n 2j in order to derive the block of pixels of the secret image.
Step 3. To restore secret image S from separate blocks of pixels.
Step 4. To return extracted secret image S and to complete the algorithm.
In the following section of the present article, the results of computing experiments with the given algorithm and its comparison to the QTAR algorithm are presented.
Computing experiments with the QTAR algorithm and the offered algorithm were carried out on the test sampling including 19 grey-scale and 3 full-color images with the resolution of 512×512 of pixels. The given sampling was formed from base of images [18]. The examples of test images are shown on Fig. 6.
Image Processing, Geoinformation Technology and Information Security / O.O. Evsutin, A.O. Osipov
Fig. 7 shows the results of three experiments with the obtained algorithm for various values of embedding parameters. The images have the following order in each line: the cover image; the cover image divided into square homogeneous blocks; the stego image; the secret image extracted after embedding.
It is possible to see that stego image does not contain appreciable artefacts of embedding in each case. The secret image contains some distortions with the level comprehensible to human perception. Fig. 7. Experiments: a) the image “Peppers” is embedded in the image “Boat”, m = 32; k = 10; (x, y) = (269, 0); Th1 = 0,41; Th2 = 0,42; Th3 = 0,28; b) the image “Jellyfish” is embedded in the image “Cat”, m = 16; k = 10; (x, y) = (96, 400); Th1 = 0,02; Th2 = 0,11; Th3 = 0,26; c) the image “Baboon” is embedded in the image “Clouds”, m = 16; k = 4; (x, y) = (17, 192); Th1 = 0,07; Th2 = 0,13; Th3 = 0,38.
Table 1 shows the results of the efficiency estimation of our algorithm in comparison with the initial QTAR algorithm. For each image, the optimal parameters of embedding are specified, which were found by means of differential evolution. Parameters of differential evolution were set according to the guidelines presented in [19] for the optimization problem of dimensions 5. Last three table lines correspond to full-color images; the rest of the images are grey-scale.
One can see that in most cases our algorithm surpasses the QTAR algorithm and only on occasion shows comparable results. For example, it refers to images “Arctichare”, “Clouds”, “F15”. In those cases the proposed algorithm cannot reach substantia l improvement. Also, if one parameter increases, other parameters decrease. It is possible to explain in the following way: the point by default 0, 0 for the given images gives the solution that belongs to Pareto-frontier. For images “Cat”, “Peppers”, “Baboon” the proposed algorithm noticeably surpasses QTAR in terms of BPP at the comparable value of PSNR. But for the majority of images the proposed algorithm surpasses the QTAR algorithm in terms of both considered indexes. As a result, the maximum advantage of PSNR over the best value of BPP is 1,07 dB, and the maximum advantage of BPP over comparable value of PSNR is 1,1 bits, which is significant improvement.
Regarding the stability against steganalysis, the offered algorithm also surpasses the QTAR algorithm, since the embedding operation in both cases is the same, but additional parameters used by the offered algorithm increase the private key size.
Image Processing, Geoinformation Technology and Information Security / O.O. Evsutin, A.O. Osipov Table 1. Comparison of the proposed algorithm and the QTAR algorithm.
QTAR Proposed algorithm PSNR, dB
The given paper presents the new algorithm of high-capacity embedding of the information into the frequency domain of discrete cosine transform received on the basis of known QTAR algorithm [15]. The QTAR algorithm ensures high capacity of embedding at the expense of representation of the cover image in the form of a quad-tree of homogeneous blocks of pixels. The frequency spectrum of such blocks contains a small number of significant elements and high number of insignificant elements. Replacement of insignificant frequency coefficients with data elements of the secret image does not lead to appreciable distortions of the cover image.
A distinctive feature of the offered modification of the QTAR algorithm is a new approach to representation of the cover image in the form of a quad-tree of homogeneous blocks of pixels. New parameters are introduced into algorithm of quad-tree construction. The cover image is represented in the form of torus which allows one to arbitrarily choose an index point that corresponds to the left top angle in the initial algorithm. Besides, for blocks of pixels with various levels of brightness, the different threshold values defining the homogeneity criterion are set.
Deriving of optimal parameters for each concrete cover image is carried out by means of differential evolution.
Computing experiments have shown that the offered algorithm differs with greater effectiveness on quality and embedding capacity in comparison with QTAR algorithm.
Development of the given paper will consist in the search of new approaches to partition of the cover image into homogeneous blocks of pixels and synthesis of new algorithms of embedding.
Besides, the transfer of the initial approach to the achievement of high-capacity embedding on other transforms applied in digital image processing, except discrete cosine transform, is interesting.
The given paper is completed with the support of the Ministry of Education and Science of the Russian Federation within the limits of the project part of the state assignment of TUSUR in 2017 and 2019 (project 2.3583.2017/4.6) and of the Russian Foundation for Basic Research (project 16-47-700350 r_a).