Image steganography is the science and art of hiding secret information within an image using various methods and techniques (Kaur et al., 2022; Setiadi et al., 2023). Image steganography ensures that hidden data remain invisible to the human eye, allowing safe communication and data storage (Rahman et al., 2023a).

Least significant bit (LSB) substitution is one of the most well-known techniques in spatial domain steganography. In LSB, the least significant bit of each pixel in the carrier image is modified to embed one bit of the dichotomous secret message (Kurak and McHugh, 1992). These adjustments are almost imperceptible to the human eye. However, traditional bit plane analysis can easily uncover the hidden secret information (Wayner, 2009; Sahu and Sahu, 2020). In recent decades, various improvements of LSB steganography have been introduced making the detection of the concealed data more challenging. For example, two least significant bit (2LSB) technique enhances the conventional LSB method by embedding two bits of secret information into the last two bit planes of the carrier image (Khalind and Aziz, 2015). In the random 2LSB technique, a single secret bit is inserted randomly into either the first or the second bit plane. Different manipulations with the indices of the bit planes are used to enhance the existing LSB techniques (Abdulla et al., 2013; Al-Faydi et al., 2023; Njoum et al., 2024).

Multiple Bit Planes Based (MBPB) steganography extends LSB methods by employing the bit planes with greater complexity for embedding secret data (Nguyen et al., 2006). LSB Matching technique (LSB-M) is a variation of LSB substitution, which adds or subtracts 1 from the pixel value instead of directly replacing the least significant bit (Luo et al., 2010) what makes LSB-M technique more resistant to steganalysis than the standard LSB technique. Pixel Value Differencing (PVD) hides information by modifying the difference between two neighbouring pixel values (Hussain et al., 2015). Larger differences allow more bits to be hidden, while smaller differences allow fewer bits.

The main challenges in image steganography include achieving a high embedding capacity and ensuring a high level of security (Aini et al., 2019; Zhang et al., 2019; Li et al., 2024; Liu et al., 2024). The security of a steganographic scheme largely depends on the effectiveness of its embedding strategy and is based on two key factors: imperceptibility, meaning the hidden data remains undetectable within the medium, and confidentiality, ensuring that only the intended recipient can detect and extract the concealed information (Ghoul et al., 2023; Mukherjee and Paul, 2024). Together, these factors protect the hidden content from unauthorized detection and access (Luo et al., 2023; Sreenidhi et al., 2024).

The integration of adaptive embedding techniques, cryptography, and chaotic systems into the steganographic schemes can significantly enhance the security of the hidden information (Haverkamp and Sarmah, 2024; Mukherjee and Paul, 2024; Xing et al., 2022). For example, embedding the secret information in the sparse representation of the carrier image, in the edge or noisy areas conceals data where it is least noticeable, reducing the risk of detection (Nipanikar et al., 2018; Rashid and Majeed, 2019; Setiadi et al., 2024; George et al., 2024). Encrypting the hidden data before embedding ensures that the message remains unreadable, even if detected (Rahman et al., 2023b; Rajabi-Ghaleh et al., 2024; Haverkamp and Sarmah, 2024). Incorporating randomization and perturbations generated by different chaotic systems into steganographic schemes helps to hide the message in a way that makes it difficult to detect (Laimeche et al., 2020; EL-Hady et al., 2024; Aziz et al., 2015).

An alternative approach to the development of steganographic schemes is proposed in Saunoriene and Ragulskis (2023) where the concept of the Wada index is used to extend the classical LSB technique. In this scheme, the grayscale carrier image is covered by overlapping square windows of a specified size. The process of hiding secret information relies on manipulating the number of distinct grayscale levels within these overlapping windows (Saunoriene and Ragulskis, 2023). This scheme ensures that the bit planes of the resulting stego image do not reveal the hidden message. Furthermore, the stego image is resistant to steganalysis algorithms, and its payload capacity is comparable to that of grayscale LSB techniques (Saunoriene and Ragulskis, 2023).

However, according to the “no-free-lunch” theorems (Wolpert and Macready, 1997; Wolpert, 2013), every algorithm has its drawbacks. A possible drawback of the steganographic scheme based on the Wada index is a rather simple decoding process. One needs to use an observation window (the size of the window must be predefined) and count the number of different colours in that window (of course, one needs to know that the number of different colours must be counted).

The primary objective of this paper is to introduce the concept of a sparse observation window into the steganographic scheme based on the Wada index. Sparse observation windows with randomly distributed active cells could seriously increase the confidentiality of the scheme (the distribution of active cells would serve as an additional secret key for the proposed scheme).

However, the decoding algorithm of the steganographic scheme based on the Wada index is rather simple because it is based on the computation of the number of different colours in the current observation window. The main contribution of this paper is the introduction of sparse observation windows. A straightforward computation of the number of different colours in the current observation window becomes insufficient for decoding the secret. This paper also answers a number of other important questions about the existence of perfect coverings, the structure of dichotomous shares, and the robustness of the proposed scheme to different attacks.

The paper is structured as follows. Preliminaries on the steganographic scheme based on the Wada index are given in Section 2. Rectangular observation windows are discussed in Section 3. Sparse observation windows are introduced in Section 4. The security of the proposed steganographic scheme is investigated in Section 5. The robustness of the proposed scheme is presented in Section 6. Concluding remarks are given in the final section.

The steganographic scheme based on the Wada index is introduced in Saunoriene and Ragulskis (2023). The secret dichotomous image S is embedded into the grayscale carrier image C producing the grayscale stego image T. The size of the carrier and the stego images (measured in pixels) is n x × n y ; the size of the rectangular observation window is r x × r y ; the size of the secret image S is ( n x − r x + 1 ) × ( n y − r y + 1 ). The carrier image C is split into r x · r y dichotomous shares H k , k = 1 , 2 , … , r x · r y . The size of H k is ( n x − r x + 1 ) × ( n y − r y + 1 ).

As defined previously, P 2 × 2 ( 2 , 2 ) is a 2 × 2 perfect covering scheme with the modifying cell located at the local coordinates ( 2 , 2 ).

What happens if the observation window is initially placed at any other corner of the carrier image, not necessarily at the top left corner (Fig. 3(b)–(d))?

Positioning the observation window at the left-bottom corner of the carrier image can also result in a perfect covering (Fig. 3(b)) if the coordinates of the modifying cell are set to ( 1 , 2 ) and the travel direction is set from left to right (horizontal perfect covering) or from bottom to top (vertical perfect covering) as illustrated in Fig. 3(b). Such a covering scheme is denoted as P 2 × 2 ( 1 , 2 ) .

Similarly, a perfect covering can be constructed by setting the initial position of the observation window at the bottom right corner of the carrier image and placing the modifying cell at local coordinates ( 1 , 1 ) (Fig. 3(c)). Such a covering scheme is denoted as P 2 × 2 ( 1 , 1 ) .

Finally, placing the observation window at the top right corner of the carrier image and the modifying cell at local coordinates ( 2 , 1 ) also results in a perfect covering (Fig. 3(d)). Such a covering scheme is denoted as P 2 × 2 ( 2 , 1 ) .

Note that the horizontal and vertical perfect covering schemes depicted in Fig. 3(b) result in identical stego images (Saunoriene and Ragulskis, 2023). The same holds true for the horizontal and vertical perfect coverings depicted in panels (c)–(d). However, we will show that schemes P 2 × 2 ( 2 , 2 ) , P 2 × 2 ( 2 , 1 ) , P 2 × 2 ( 1 , 2 ) , and P 2 × 2 ( 1 , 1 ) do produce different stego images.

One should be careful with the selection of the horizontal and vertical travel directions for each particular perfect covering scheme. For example, a straightforward application of the horizontal left-to-right strategy may fail if the local coordinates of the modifying cell are not properly defined (Fig. 4). Figure 4(a) illustrates the perfect scheme P 2 × 2 ( 2 , 2 ) (the size of the carrier image is 3 × 3).

However, P 2 × 2 ( 1 , 2 ) is not a perfect covering scheme for the same left-to-right travel strategy (the first conflict occurs at the third step depicted in red in Fig. 4(b)). Analogously, P 2 × 2 ( 2 , 2 ) is not a perfect scheme if the horizontal right-to-left strategy is used (the first conflict is generated at the second step marked in red in Fig. 4(c)).

So far, only 2 × 2 observation windows have been discussed. It appears that the modifying cells should be placed only in the corners of the rectangular observation window (this condition is automatically fulfilled for 2 × 2 observation windows). For example, both left-to-right and right-to-left travel strategies fail for the P 3 × 3 ( 3 , 2 ) scheme (Fig. 5). The same holds true for the vertical bottom-to-top and top-to-bottom travel strategies. In other words, P 3 × 3 ( 3 , 2 ) is not a perfect covering scheme.

Let us consider a secret dichotomous city-map image ( 510 × 510 pixels) shown in Fig. 6. The city-map image is encoded into the grayscale Lena carrier image ( 512 × 512 pixels). The size of the observation window used for the encoding is fixed to 3 × 3 pixels. Four different perfect covering schemes P 3 × 3 ( 3 , 3 ) , P 3 × 3 ( 1 , 3 ) , P 3 × 3 ( 1 , 1 ) , P 3 × 3 ( 3 , 1 ) (Fig. 3(a)–(d)) are used to encode the secret city-map image into the carrier Lena image.

It is interesting to observe that four perfect covering schemes yield four different stego images (the middle row in Fig. 6). Although no differences can be noticed by a naked eye, the modifications in the carrier image made during the encoding of the secret image into the carrier image are different (the bottom row in Fig. 6).

The statistical measures such as the range of the performed changes, the mean error (ME), the mean absolute error (MAE), the mean square error (MSE), the peak-signal-to-noise ratio (PSNR), the structural similarity index (SSIM) describe the difference between the original carrier and stego images and help to evaluate the performance of the employed steganographic scheme. The values of these performance measures are presented in Table 1 for each perfect covering scheme P 3 × 3 ( 3 , 3 ) , P 3 × 3 ( 1 , 3 ) , P 3 × 3 ( 1 , 1 ) , and P 3 × 3 ( 3 , 1 ) . However, neither of the four coverings significantly outperforms the other.

Therefore, changing the position of the modifying cell does not significantly increase the effectiveness of the encoding strategy (Table 1). Also, it is important to observe that the decoding of the secret information from the stego image does not depend on a particular encoding scheme P 3 × 3 ( 3 , 3 ) , P 3 × 3 ( 1 , 3 ) , P 3 × 3 ( 1 , 1 ) , or P 3 × 3 ( 3 , 1 ) . The decoding process requires to cover the stego image by overlapping observation windows in any order (and evaluate the number of different colours in each observation window). Therefore, the individual selection of a scheme ( P 3 × 3 ( 3 , 3 ) , P 3 × 3 ( 1 , 3 ) , P 3 × 3 ( 1 , 1 ) , or P 3 × 3 ( 3 , 1 ) ) has no impact on the safety of the decoding scheme.

So far, the 2 × 2 and 3 × 3 observation windows have been used in the perfect covering schemes. A natural question is whether better performance measures could be achieved when the size of the observation window is increased. Unfortunately, the results shown in Fig. 7 do not indicate such an improvement. Computational experiments are continued with the secret dichotomous city-map image encoded into the grayscale Lena image using the perfect covering scheme P r × r ( r , r ) . The range of changes is not significantly decreased at r = 20 (Fig. 7). The minimum ME is reached at r = 2, the minimum of MAE and MSE – at r = 4. The maximum values of SSIM and PSNR are achieved at r = 4.

Therefore, larger rectangular observation windows do not help to achieve better performance features and a higher security of the decoding scheme. Another approach is required to achieve these purposes.

Up to now, rectangular observation windows have been used to count the number of different colours and to perform necessary modifications in the carrier image at the modifying cell located at one of the corners of this rectangle.

Let us introduce the concept of an active and a passive cell inside the observation window. Active cells are used to compute the number of different colours in the current observation window (passive cells are not used for counting). Also, the modifying cell must be one of the active cells (otherwise the number of different colours measured at the locations of the active cells of the current observation window would not change).

An observation window with at least one passive cell is defined as a rectangular sparse observation window (SOW). The notion of SOW is represented by the size of the rectangular observation window and the location of the modifying cell (the active cells are plotted in white, and the passive cells are shown in gray). For example, the SOW shown in Fig. 8(a) is denoted as P ˜ 3 × 6 ( 3 , 6 ) and two active cells are located at the top left and bottom right corners of the rectangular window.

Note that such a definition of SOW requires a proper placement of active cells inside the observation window. It is assumed that the size of the rectangular window of SOW is minimal (effective) to accommodate all active cells. For example, the effective size of SOW in Fig. 8(c) is 2 × 4, not 3 × 6.

The general concept of SOW-based scheme is somewhat similar to the steganographic scheme based on Wada index (Saunoriene and Ragulskis, 2023) (Fig. 14). The perfect covering scheme is employed to encode the secret image; the counting of different colours in the current observation window is used to decode the secret image. The major difference between the two schemes is in the structure of the observation window. Such a modification can be considered as a serious enhancement of the security of the proposed scheme.

Note that the statistical performance measures of the steganographic scheme based on the Wada index are comparable to the performance measures of the best LSB-type schemes (Saunoriene and Ragulskis, 2023). Moreover, this scheme is robust to the steganalysis algorithms (Saunoriene and Ragulskis, 2023), and the payload capacity of the carrier image is similar to the grayscale LSB schemes (Saunoriene and Ragulskis, 2023). The same holds true for the steganographic scheme based on SOW.

However, the major advantage of the SOW-based scheme is the extra security feature which is enabled by SOWs. Let us assume that the secret city-map image ( 509 × 509 pixels) is encoded into the Lena carrier image ( 512 × 512 pixels) using a perfect SOW scheme P ˜ 4 × 4 ( 4 , 2 ) (Fig. 15). Note, that the SOW used for encoding the secret image in Fig. 15 comprises 9 active and 7 passive cells. It is important to observe that the secret image can be correctly decoded from the stego image if only the SOW used for the decoding is identical to the SOW used for the encoding. The first column in Fig. 15 shows the SOW used to encode the city-map into the Lena image; the middle column – SOWs used to decode the secret information from the stego image. The decoded secret images are depicted in the third column in Fig. 15.

Figure 15(a) demonstrates a successful decoding, when the SOW used for the decoding matches the SOW used for the encoding. A single permutation of the active cells in the SOW disrupts the decoding of the secret image (Fig. 15(b)). Similarly, full observation windows P 3 × 3 ( 3 , 3 ) and P 4 × 4 ( 4 , 4 ) are unable to decode the secret (Fig. 15(c)–(d)).

Also note that statistical performance indicators for the encoding scheme based on the perfect SOW P ˜ 4 × 4 ( 4 , 2 ) (containing 9 active cells) are at least as good as the same statistical indicators of the encoding scheme P 3 × 3 ( 3 , 3 ) or P 4 × 4 ( 4 , 4 ) based on the Wada index (Fig. 7). For example, for the encoding in Fig. 15(a), the range of modifications in the stego image is [ − 78 , 77 ], M E = − 0.0210, M A E = 1.1031, M S E = 7.3853, S S I M = 0.9823, P S N R = 39.4471.

Further computational experiments are conducted with different standard carrier (Cameraman, Peppers, Jetplane) and secret images (Random, Checkerboard) (Table 2). Sparse observation window P ˜ 4 × 4 ( 4 , 2 ) presented in Fig. 15(a) is used for these computations.

Clearly, 9 active cells can be distributed in many different ways inside the 4 × 4 SOW. It is interesting to observe that there are 10564 distinct layouts of the 4 × 4 SOW consisting of 9 active cells and 7 passive cells ( C 16 9 − 4 · C 12 9 + 4 = 10564; Fig. 16). If the modifying cell is fixed at the bottom right corner of the 4 × 4 SOW with 9 active cells, the position of one active cell (out of 9) is already predefined. There are C 15 8 ways to distribute 8 active cells in the rest of 15 positions of the 4 × 4 observation window. However, some of these layouts consist of the first row and/or the first column containing only inactive cells, which produces the SOW of a smaller size than 4 × 4 (there are 2 · C 11 8 − 1 such inappropriate layouts). Thus, there are C 15 8 − 2 C 11 8 + 1 = 6106 ways to distribute 9 active cells in 4 × 4 observation window if the modifying cell is fixed at the bottom right corner of the SOW.

Robustness to partial destruction of the stego image is one of the main features of the steganographic scheme. The proposed scheme is robust against partial blocking of a stego image (Fig. 17, blocked areas are depicted in white). Although it is impossible to decode the secret information from the blocked part of the stego image (black areas in the decoded secret images), the remaining part of the secret image can be decoded correctly (Fig. 17).

The “salt and pepper” noise applied to the stego image has a negative impact on the quality of the decoded secret image (Fig. 18). The higher is the density of the “salt and pepper” noise, the larger is the amount of incorrectly decoded secret pixels (Fig. 18).

The Gaussian noise applied to the stego image affects the quality of the decoded secret image as well (Fig. 19). The higher is the variance of the Gaussian noise, the larger is the amount of incorrectly decoded secret pixels. For example, the secret image can be decoded and fully recognized if the stego is degraded by the Gaussian noise with zero mean and variance equal to 7.5 · 10 − 7 (Fig. 19(a)). Unfortunately, it is impossible to decode the secret image if the stego image is affected by the Gaussian noise with higher variances (Fig. 19(c)).

Let us suppose that the brightness of the stego image is adjusted by adding a constant c = 50 to the brightness of all pixels in the stego image (values greater than 255 are truncated to 255). The secret image is decoded correctly in those areas of the stego image where the original brightness of pixels is not greater than 255 − c (Fig. 20(a)).

If the brightness of the stego image is modified by subtracting a constant c = 50 (values lower than 0 are truncated to 0, the encoded secret image remains undamaged in the areas where the brightness of original pixels in stego image is not less than c (Fig. 20(b)).

Figure 20(c)–(d) demonstrates the influence of the multiplicative brightness adjustment of the stego image on the secret decoded image. The brightness of each pixel of the stego image is multiplied by c = 1.2 (values greater than 255 are truncated to 255; Fig. 20(c)). Similarly, the brightness of each pixel in the stego image is multiplied by c = 0.8 in Fig. 20(d). The damage to the secret decoded image is much greater in Fig. 20(d) than in Fig. 20(c) because the brightness range of the stego image is reduced to [ 0 , 204 ] when multiplied by c = 0.8 compared to the multiplication by c = 1.2 (the brightness range remains [ 0 , 255 ] then).

It is clear that the steganographic scheme based on the SOW outperforms the standard steganographic scheme based on the Wada index (Saunoriene and Ragulskis, 2023) in a sense of MAE, MSE, PSNR, and SSIM. The statistics of the scheme based on SOW is presented at the end of Section 5; the statistics of the standard scheme based on the Wada index proposed in Table 1. Comparison of the performance evaluation measures of the standard steganographic scheme and LSB, 2LSB, random 2LSB, improved 2LSB, random 3LSB, and random 4LSB steganographic schemes can be found in Saunoriene and Ragulskis (2023).

The proposed steganographic scheme has several other important advantages over the steganographic scheme based on the Wada index (Saunoriene and Ragulskis, 2023). The fact that the brightness of pixels is evaluated only in designated locations sparsely distributed in the current observation window yields a significant improvement in the security of the encoding scheme. For example, the 4 × 4 SOW comprising 9 active and 7 passive cells yields 10564 different layouts resulting into perfect coverings.

The apparent simplicity of the scheme is misleading. Several specific requirements are derived for the structure of the sparse observation windows capable of producing perfect coverings. A subtle interplay between the possible placement of the modifying cell and the active cells in the current observation window must be identified and properly introduced into the encoding process to guarantee the proper functioning of the proposed steganographic scheme.

The major advantages of the proposed scheme can be characterized by its ability to perform pixel modifications in different bit planes of the carrier image. The proposed scheme directly inherits this property from the steganographic scheme based on the Wada index (Saunoriene and Ragulskis, 2023). The robustness of this scheme to RS steganalysis is discussed in detail in Saunoriene and Ragulskis (2023). Analogous computational experiments demonstrate that the proposed scheme is also robust to RS steganalysis algorithms.

One of the limitations of the proposed steganographic scheme is the need to share information about the structure of the observation window between the communicating parties. In other words, the distribution of active cells and the location of the modifying cell must be exchanged between the parties before the secret image is decoded.

Another minor limitation of the proposed scheme is related to the payload capacity. In fact, the payload capacity of the scheme is comparable to LSB schemes. However, the proposed architecture of the observation window implies that some pixels lying on the borders of the carrier image are not employed in the process of encoding and decoding the secret image (Fig. 13).

Finally, one must keep in mind that not every distribution of active cells and the modifying cell inside the observation window results into a perfect SOW. Therefore, communicating party responsible for the encoding of the secret must know the basic rules governing the structure of a perfect SOW.

In the decoding stage, the number of different colours is estimated in each of the overlapping observation windows. There are ( n x − r x + 1 ) · ( n y − r y + 1 ) observation windows in the n x × n y stego image, covered by r x × r y SOW (with r a active cells). The time complexity to determine the number of different values within a single observation window and decode the brightness of the corresponding secret pixel is O ( r a log 2 r a ). In the encoding stage, one has to determine if the number of different colours in the current observation window is odd or even, and to make a decision if a modification is required ( O ( r a log 2 r a ) operations). Statistically, changes are required for around a half of the pixels in the carrier image. The number of operations needed to modify the number of colours in each observation window is also O ( r a log 2 r a ).

The encoding and decoding algorithms are implemented in Matlab and executed on a MacBook Air M2 (8-core CPU, 8-core GPU, 16-core Neural Engine, 100 GB/s memory bandwidth). The decoding of the 510 × 510 secret image from the 512 × 512 stego image employing 4 × 4 SOW with 9 active cells takes 15.23 seconds on average (based on 100 identical decoding runs). However, since the sequence in which the brightness of secret pixels is decoded does not have any influence on the reconstructed secret image, the process could be executed simultaneously across multiple CPU cores, which would result in a considerably higher processing speed. For the same 510 × 510 secret image to be encoded in the 512 × 512 carrier image (using 4 × 4 SOW with 9 active cells), the process takes 22.14 seconds on average (based on 100 identical encoding runs).

The time required to run the encoding algorithms using high-resolution digital images prevents a possible application of the proposed scheme on edge devices using video streams. However, the enhanced security measures of the proposed scheme (compared to the steganographic proposed in Saunoriene and Ragulskis (2023)) make it an attractive alternative to many classical steganographic schemes.

The proposed steganographic scheme is capable of encoding dichotomous secret images only. In principle, the scheme could be extended to grayscale secret images. However, the Wada membership function defining the decision to modify a pixel should be modified. The decision making process cannot be based on the odd or even number of different pixels in the current observation window (Saunoriene and Ragulskis, 2023). The ability to encode a grayscale image would immediately open the possibility to encode RGB color images (by hiding R, G, and B components of the colour image separately). Such modifications remain a definite objective of future research.