# A Formula Adaptive Pixel Pair Matching Steganography Algorithm

Authors: Min Long; Fenfang Li
Journal: Advances in Multimedia
 (2018)

---

## Abstract

Pixel pair matching (PPM) is widely used in digital image steganography. As an important derivation, adaptive pixel pair matching method (APPM) offers low distortion and allows embedded digits in any notational system. However, APPM needs additional space to store, calculate, and query neighborhood set, which needs extra cost. To solve these problems, a formula adaptive pixel pair matching (FAPPM) method is proposed in this paper. The basic idea of FAPPM is to use the formula to get the stego image pixel pair without searching the neighborhood set for the given image pixel pair. This will allow users to embed secret message directly without storing and searching the look-up table. Experimental results and analysis show that the proposed method could embed secret data directly without searching the neighborhood sets by using a formula and it still maintains flexibility in the selection of notional system, high image quality, and strong anti-steganalysis ability.


---

## Body

## 1. Introduction

Information hiding is a technology of embedding secret data into the media for covert communication [1]. With the rapid development of Internet, a large number of data are transmitted over the Internet. At present, the main media using for data hiding includes images, audio, and video, where digital image is the most widely used media [2]. Researchers have shown a great interest in image steganography for the last decade [3]. LSB replacement [4] is one of the most commonly used steganographic techniques, which makes full use of the characteristics that the human visual system is not sensitive to small changes in pixels and the negligible contribution of the low bit plane of the pixel to the image quality. However, this method can only add 1 or remain unchanged for the even pixels and can only decrease 1 or remain unchanged for the odd pixels. Therefore, this unbalanced embedding distortion leads to the histogram attack to the images [5, 6]. Chan et al. [7] proposed an optima pixel adjustment process (OPAP) method, which adjusted the pixels to reduce the distortion caused by least significant bit (LSB) embedding. The LSB and OPAP methods both employed one pixel as an embedding unit to embed secret message. As the development of steganography, methods using two or more pixels as a basic unit for B-ary secret information embedding were put forward. This kind of stenographic algorithm can improve the embedding capacity and image quality by subtle modifying the pixel.In 2006, Miekikainen [11] proposed a LSB matching method. It employed two pixels as embedding unit. In this method, when payload was 1 bit per pixel, the mean square error (MSE) is 0.375, while the MSE of LSB [4] was 0.5. Zhang and Wang [12] proposed exploiting modification direction (EMD) method, which added and subtracted 1 in one pixel and embedded 2n + 1-ary secret message inn pixels. Whenn = 2, a quinary number was embedded in each pair of pixels. The capacity can reach the maximum (1/2)log25=1.161 bit per pixel (bpp). Chao et al. [13] extended this method and proposed a diamond encoding (DE) method. It can embed 2k2+2k+1-ary information to each pair of pixels and achieve high embedding efficiency by adding and subtracting 1 operation inn pixels. In [8], the author used a codebook to improve the EMD scheme, and one secret (2n+x-1)-ary digit was hidden in a group of pixels in an image as a modified secret digit. In [9], the authors proposed a method to modify a group of pixels by ±1 to embed a secret digit, but it is only applicable to 3n-ary notational system. Kuo et al. [14] proposed a formula diamond encoding (FDEMD) data hide scheme, and it could conceal a digit in (2k2+2k+1)-ary system. It simplified the embedding procedure and embedded secret data without storing and calculating characteristic value matrix. Hong et al. [10] designed a new extraction function and new neighborhood set of two pixels called adaptive pixel pair matching (APPM). It allowed embedding digits in arbitrary notational system and the distortion caused by embedment using APPM was minimized; therefore the resultant marked image quality could be well preserved [15]. In [16], secure adaptive pixel pair matching (SAPPM) was proposed to hide multiple data types such as text, image, and audio which incorporated cryptography along with steganography. A transformed version of adaptive pixel pair matching (APPM) was used for image steganography to get lower distortion [17]. However, APPM need to calculate, store, and query the modified neighborhood set table.Based on the above methods, this paper simplifies the embedding procedure and designs an extraction function to construct a formula adaptive pixel pair matching (FAPPM) method. It does not need to calculate, store, and query the modified neighborhood set table, and it can realize the data hiding in any notional system.


## 2. A Review of Adaptive Pixel Pair Matching (APPM)

The APPM method [10] used a pair of pixels (x,y) as a coordinate, where an extraction function fAPPM(x,y) was designed. Then a neighborhood set Φ(x,y) of (x,y) was established.(1)fAPPMx,y=x+cBymodBwhere f(x,y) and Φ(x,y) satisfied the following three conditions:(i)
In the neighborhood setΦ(x,y), there are exactly B pairs of coordinates.(ii)
In the neighborhood setΦ(x,y), the extracted function values for each coordinate are mutually exclusive.(iii)
According tof(x,y) and Φ(x,y), a digit can be embedded in any notional system.The way to find the extraction function coefficientcB and Φ(x,y) can be converted to find the following optimal solution:Minimize∑i=0B-1[(xi-x)2+(yi-y)2], subject to f(xi,yi)∈{0,1,…,B-1}, where f(xi,yi)≠f(xj,yj), if i≠j and 0≤i,j≤B-1.According to the above,cB and Φ(x,y) can be calculated with differentB-ary. For APPM proposed by Hong [10], cB corresponding toB-ary is listed in Table 1. Meanwhile, parts of Φ(x,y) corresponding toB-ary are illustrated in Figure 1.Table 1
Extraction Function CoefficientcB of APPM.
c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 10 c 11 c 12 c 13 c 14 c 15 c 16  1 1 2 2 2 2 3 3 3 3 4 5 4 4 6  c 17 c 18 c 19 c 20 c 21 c 22 c 23 c 24 c 25 c 26 c 27 c 28 c 29 c 30 c 31  4 4 4 8 4 5 5 5 5 10 5 5 5 12 12  c 32 c 33 c 34 c 35 c 36 c 37 c 38 c 39 c 40 c 41 c 42 c 43 c 44 c 45 c 46  7 6 6 10 15 6 16 7 7 6 12 12 8 7 7  c 47 c 48 c 49 c 50 c 51 c 52 c 53 c 54 c 55 c 57 c 58 c 59 c 60 c 61 c 62  7 7 14 14 9 22 8 12 21 16 24 22 9 8 8  c 63 c 64  14 14Figure 1
Neighborhood set (shaded region) for APPM.
(a)
Φ 4, c4=2 (b)
Φ 5, c5=2 (c)
Φ 6, c6=2 (d)
Φ 9, c9=3 (e)
Φ 13, c13=5 (f)
Φ 16, c16=6 (g)
Φ 25, c25=5Compared with DE and EMD method, APPM has the flexibility to choose a better notational system for data embedding to decrease the image distortion. The selection ofB-ary system is determined by the size of the cover imageC. Given the size ofC isM×N,B is the minimum value satisfying M×N/2≥sB. However, it needed to calculate, store, and query the neighborhood set as shown in Figure 1.


## 3. The Proposed Formula Adaptive Pixel Pair Matching Method (FAPPM)

In order to solve the above shortcomings, this paper puts forward a formula adaptive pixel pair matching embedding method to find the stego-pixel pair without a neighborhood set.


### 3.1. Embedding Procedure

In the embedding procedure, four vectors at most are produced. Two vectors are calculated whenD>0, and the other two vectors are calculated whenD<0. In Algorithm 1,i represents vectors 1 to 4 in turn. Figure 2 shows the embedding process overview.Algorithm 1
Input: A pixel pair (x1,x2), extraction function coefficient cB and secret data s. Output: Stego pixel pair (x1′,x2′). Step  1: Set f=(x1+cBx2)modB Step  2: Set k=(B-1)/2 Step  3: Set D=s-f Step  4: If D<0 then D=D+B Step  5:Set next_t1=DmodcB Step  6: While i=1 to 4 do Set t1=next_t1 Set t2=D-t1/cB If t1≤k & & t2≤k then Set x1′=x1′+t1 Set x2′=x2′+t2 Else Switch (i) Case 1: Set next_t1=t1-cB Case 2: Set D=D-B Set next_t1=-(DmodcB) Case3: Set next_t1=t1+cB Case4: Print “Error” End Switch End if End WhileFigure 2
The embedding process.Example 1.
For a cover pixels pair(5,6), secret data s=8(16), and extraction function coefficient c16=6, the stego image pixels pair (x1′,x2′) = (4,6)  is obtained by using Algorithm 1.Step 1.
Calculatef=(5+6×6)mod16=9, k=B-1/2=2.Step 2.
CalculateD=s-f=-1. As D<0, D=D+B=15 is obtained.Step 3.
Calculatenext_t1=Dmodc16=3.(1)
Round 1:t1=3,t2=2.(2)
t1>k & & t2>k, then next_t1=t1-cB=-3.(3)
Round 2:t1=-3, t2=3.(4)
t1>k & & t2>k, then D=D-B=-1,next_t1=-(Dmodc16)=-1.(5)
Round 3:t1=-1, t2=0.(6)
t1≤k & & t2≤k, then return (4,6).


### 3.2. Extraction Procedure

Through extraction function, secret digits can be extracted from the stego image. The detailed process is given in Algorithm2.Algorithm 2
Input:stego image S. Output: Secret data. Step  1: Divide the stego image S into non overlapping pixel pairs (xi′,yi′). Step  2: Calculate si=f(xi′,yi′)=(xi′+cByi′)modB, where i represents the i-th pixel pair. Step  3: Calculate all si and convert them to binary stream m.


### 3.3. Overflow Problem and Solution

If an overflow or underflow problem occurs, that is,(x′,y′)<0 or (x′,y′)>255, a nearest (x′′,y′′) should be found in the neighborhood of (x,y) such that f(x′′,y′′)=sB. This can be done by solving the optimization problem(2)Minimize:x-x′′2+y-y′′2,Subject to:fx′′,y′′=sB,0≤x′′,y′′≤255.


## 3.1. Embedding Procedure

In the embedding procedure, four vectors at most are produced. Two vectors are calculated whenD>0, and the other two vectors are calculated whenD<0. In Algorithm 1,i represents vectors 1 to 4 in turn. Figure 2 shows the embedding process overview.Algorithm 1
Input: A pixel pair (x1,x2), extraction function coefficient cB and secret data s. Output: Stego pixel pair (x1′,x2′). Step  1: Set f=(x1+cBx2)modB Step  2: Set k=(B-1)/2 Step  3: Set D=s-f Step  4: If D<0 then D=D+B Step  5:Set next_t1=DmodcB Step  6: While i=1 to 4 do Set t1=next_t1 Set t2=D-t1/cB If t1≤k & & t2≤k then Set x1′=x1′+t1 Set x2′=x2′+t2 Else Switch (i) Case 1: Set next_t1=t1-cB Case 2: Set D=D-B Set next_t1=-(DmodcB) Case3: Set next_t1=t1+cB Case4: Print “Error” End Switch End if End WhileFigure 2
The embedding process.Example 1.
For a cover pixels pair(5,6), secret data s=8(16), and extraction function coefficient c16=6, the stego image pixels pair (x1′,x2′) = (4,6)  is obtained by using Algorithm 1.Step 1.
Calculatef=(5+6×6)mod16=9, k=B-1/2=2.Step 2.
CalculateD=s-f=-1. As D<0, D=D+B=15 is obtained.Step 3.
Calculatenext_t1=Dmodc16=3.(1)
Round 1:t1=3,t2=2.(2)
t1>k & & t2>k, then next_t1=t1-cB=-3.(3)
Round 2:t1=-3, t2=3.(4)
t1>k & & t2>k, then D=D-B=-1,next_t1=-(Dmodc16)=-1.(5)
Round 3:t1=-1, t2=0.(6)
t1≤k & & t2≤k, then return (4,6).


## 3.2. Extraction Procedure

Through extraction function, secret digits can be extracted from the stego image. The detailed process is given in Algorithm2.Algorithm 2
Input:stego image S. Output: Secret data. Step  1: Divide the stego image S into non overlapping pixel pairs (xi′,yi′). Step  2: Calculate si=f(xi′,yi′)=(xi′+cByi′)modB, where i represents the i-th pixel pair. Step  3: Calculate all si and convert them to binary stream m.


## 3.3. Overflow Problem and Solution

If an overflow or underflow problem occurs, that is,(x′,y′)<0 or (x′,y′)>255, a nearest (x′′,y′′) should be found in the neighborhood of (x,y) such that f(x′′,y′′)=sB. This can be done by solving the optimization problem(2)Minimize:x-x′′2+y-y′′2,Subject to:fx′′,y′′=sB,0≤x′′,y′′≤255.


## 4. Experimental Results and Analysis

### 4.1. Experimental Results

The experiments are performed using Matlab R2013a, and eight512×512 grayscale images are used as shown in Figure 3. The stego images are shown in Figure 4, where B=27.Figure 3
The eight gray cover images.
(a)
Lena (b)
Barbara (c)
Pepper (d)
Boat (e)
Tiffany (f)
Baboon (g)
Zelda (h)
AirplaneFigure 4
The eight stego images (B=27, PSNR=45dB).
(a)
Lena (b)
Barbara (c)
Pepper (d)
Boat (e)
Tiffany (f)
Baboon (g)
Zelda (h)
AirplaneAs seen from Figures3 and 4, the difference between the cover images and the corresponding stego images is very little and can not be distinguished by human’s eyes. It illustrated the good imperceptibility of the proposed method.As message embedding, it will introduce the distortion in the image. Peak signal-to-noise ratio (PSNR) is usually used to measure the quality of image. The definition of PSNR is as follows:(3)PSNR=10×log10⁡2552MSEwhere MSE is the mean square error between the cover image and stego image; it is defined as follows:(4)MSE=1M×N∑i=0M∑j=0Npi,j-pi,j′2Here, the symbols pi,j and pi,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.As the proposed method can embed secret digit in any notional system, experiments are done to test the relationship between embedding payload and image quality, and the results are shown in Figure5. It can be found that the PSNR is decreased as the embedding capacity is increased. However, the PSNR still achieved a high value when the embedding capacity reached 1%.Figure 5
The relationships between embedding payload and image quality.


### 4.2. Comparison with Other Methods

Here EMD [8], EMD-3 [9], APPM, and FAPPM are compared from six aspects: the embedding method, the national system, payload, capacity, PSNR, and the storage space. The results are listed in Table 2. As seen from Table 2, FAPPM method uses a mathematical method to embed secret data and it does not need any space to store neighbor table; furthermore, it does not affect the capacity and image quality.Table 2
Comparison of results.
Contents of comparison EMD[8] EMD-3[9] APPM[10] Proposed FAPPM Embedding method Matrix and search Matrix and search table look-up Mathematic method Notational systems of B-ary fixed fixed arbitrary arbitrary Payload (bpp) B=25 2.471 2.471 2.32 2.32 PSNR (dB) 43.9 42.9 48.1 48.1 Need the storage space Yes Yes Yes No


### 4.3. Analysis of the Security

Anti-steganalysis is one of the most important criteria to measure the performance of a steganographic method. In this paper, a detection method based on histogram differential statistics analysis proposed by Zhao [18] is used to test the security of the FAPPM method. Normally, in an image with no hiding message, the horizontal difference histogram H^h and the vertical difference histogram H^v are coincident. But, when the message is embedded in a pair of pixels, its H^h and H^v will be changed. The distance between H^h and H^v is used to construct a statistical detector to detect the variation between histograms. The distance is defined as follows:(5)D=∑i=-2T2TH^hi-H^vi1/2where T is a predefined threshold and D represents the difference between H^h and H^v. The larger the D is, the greater the difference between H^h and H^v is. That is, the probability that the image contains secret information is high. Here experiments are done to compare the histogram variation of FAPPM and FDEMD under high payload. Both FAPPM and FDEMD methods are used to generate 100 stego images, respectively. H^h, H^v, and their average value are calculated, respectively. The parameters are B=53, B=211, and T=20. All the test images were fully embedded. The experiment results are shown in Figure 6. It can be seen that there is almost no difference between H^h and H^v for FAPPM, while that for FDEMD is significant, which indicates the probability that the successful steganalysis for FDEMD is higher than that of the proposed method.Figure 6
Comparison of the averaged vertical and horizontal difference histograms of FAPPM and FDEMD.
(a)
FAPPM B=53, D=134 (b)
FDEMD B=53,D=936 (c)
FAPPM B=221, D=189 (d)
FDEMD B=221, D=1449The RS attack method can detect LSB secret data embedding in grayscale or color images. Each pixel block is classified into the regular groupR, the singular group S, and the unusable group U by a flipping function and mask M. Rm, Sm, and Um denote the number of R, S, and U, respectively. For inverse mask -M, R-m,S-m, and U-m denote the number of R, S, and U, respectively. When no information is embedded, Rm-R-m≈0 and Sm-S-m≈0. The RS attack results are shown in Figures 7 and 8. It can be seen that the algorithm of this paper can guarantee Rm-R-m≈0 and Sm-S-m≈0, and the existence of secret information cannot be detected by RS steganalysis method.Figure 7
The difference ofRm andR-m for RS attack.Figure 8
The difference ofSm andS-m for RS attack.


## 4.1. Experimental Results

The experiments are performed using Matlab R2013a, and eight512×512 grayscale images are used as shown in Figure 3. The stego images are shown in Figure 4, where B=27.Figure 3
The eight gray cover images.
(a)
Lena (b)
Barbara (c)
Pepper (d)
Boat (e)
Tiffany (f)
Baboon (g)
Zelda (h)
AirplaneFigure 4
The eight stego images (B=27, PSNR=45dB).
(a)
Lena (b)
Barbara (c)
Pepper (d)
Boat (e)
Tiffany (f)
Baboon (g)
Zelda (h)
AirplaneAs seen from Figures3 and 4, the difference between the cover images and the corresponding stego images is very little and can not be distinguished by human’s eyes. It illustrated the good imperceptibility of the proposed method.As message embedding, it will introduce the distortion in the image. Peak signal-to-noise ratio (PSNR) is usually used to measure the quality of image. The definition of PSNR is as follows:(3)PSNR=10×log10⁡2552MSEwhere MSE is the mean square error between the cover image and stego image; it is defined as follows:(4)MSE=1M×N∑i=0M∑j=0Npi,j-pi,j′2Here, the symbols pi,j and pi,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.As the proposed method can embed secret digit in any notional system, experiments are done to test the relationship between embedding payload and image quality, and the results are shown in Figure5. It can be found that the PSNR is decreased as the embedding capacity is increased. However, the PSNR still achieved a high value when the embedding capacity reached 1%.Figure 5
The relationships between embedding payload and image quality.


## 4.2. Comparison with Other Methods

Here EMD [8], EMD-3 [9], APPM, and FAPPM are compared from six aspects: the embedding method, the national system, payload, capacity, PSNR, and the storage space. The results are listed in Table 2. As seen from Table 2, FAPPM method uses a mathematical method to embed secret data and it does not need any space to store neighbor table; furthermore, it does not affect the capacity and image quality.Table 2
Comparison of results.
Contents of comparison EMD[8] EMD-3[9] APPM[10] Proposed FAPPM Embedding method Matrix and search Matrix and search table look-up Mathematic method Notational systems of B-ary fixed fixed arbitrary arbitrary Payload (bpp) B=25 2.471 2.471 2.32 2.32 PSNR (dB) 43.9 42.9 48.1 48.1 Need the storage space Yes Yes Yes No


## 4.3. Analysis of the Security

Anti-steganalysis is one of the most important criteria to measure the performance of a steganographic method. In this paper, a detection method based on histogram differential statistics analysis proposed by Zhao [18] is used to test the security of the FAPPM method. Normally, in an image with no hiding message, the horizontal difference histogram H^h and the vertical difference histogram H^v are coincident. But, when the message is embedded in a pair of pixels, its H^h and H^v will be changed. The distance between H^h and H^v is used to construct a statistical detector to detect the variation between histograms. The distance is defined as follows:(5)D=∑i=-2T2TH^hi-H^vi1/2where T is a predefined threshold and D represents the difference between H^h and H^v. The larger the D is, the greater the difference between H^h and H^v is. That is, the probability that the image contains secret information is high. Here experiments are done to compare the histogram variation of FAPPM and FDEMD under high payload. Both FAPPM and FDEMD methods are used to generate 100 stego images, respectively. H^h, H^v, and their average value are calculated, respectively. The parameters are B=53, B=211, and T=20. All the test images were fully embedded. The experiment results are shown in Figure 6. It can be seen that there is almost no difference between H^h and H^v for FAPPM, while that for FDEMD is significant, which indicates the probability that the successful steganalysis for FDEMD is higher than that of the proposed method.Figure 6
Comparison of the averaged vertical and horizontal difference histograms of FAPPM and FDEMD.
(a)
FAPPM B=53, D=134 (b)
FDEMD B=53,D=936 (c)
FAPPM B=221, D=189 (d)
FDEMD B=221, D=1449The RS attack method can detect LSB secret data embedding in grayscale or color images. Each pixel block is classified into the regular groupR, the singular group S, and the unusable group U by a flipping function and mask M. Rm, Sm, and Um denote the number of R, S, and U, respectively. For inverse mask -M, R-m,S-m, and U-m denote the number of R, S, and U, respectively. When no information is embedded, Rm-R-m≈0 and Sm-S-m≈0. The RS attack results are shown in Figures 7 and 8. It can be seen that the algorithm of this paper can guarantee Rm-R-m≈0 and Sm-S-m≈0, and the existence of secret information cannot be detected by RS steganalysis method.Figure 7
The difference ofRm andR-m for RS attack.Figure 8
The difference ofSm andS-m for RS attack.


## 5. Conclusion

This paper proposed a simple and convenient data embedding method based on APPM. Compared with the APPM method, it has the advantage of no needing to compute and store the neighborhood set. Compared with the FDEMD method, the secret data of any notional system is realized by the FAPPM method, which makes the embedding notational system selection more flexible. The experimental results showed that FAPPM method has high image quality and the strong anti-steganalysis ability. Our future work will be concentrated on the use of the formula method of the adjacent three pixels as the embedding unit.



---

*Source: 7682098-2018-07-05.xml*