# On Max-Plus Algebra and Its Application on Image Steganography

Authors: Kiswara Agung Santoso; Fatmawati; Herry Suprajitno
Journal: The Scientific World Journal
 (2018)

---

## Abstract

We propose a new steganography method to hide an image into another image using matrix multiplication operations on max-plus algebra. This is especially interesting because the matrix used in encoding or information disguises generally has an inverse, whereas matrix multiplication operations in max-plus algebra do not have an inverse. The advantages of this method are the size of the image that can be hidden into the cover image, larger than the previous method. The proposed method has been tested on many secret images, and the results are satisfactory which have a high level of strength and a high level of security and can be used in various operating systems.


---

## Body

## 1. Introduction

Recently information systems are developing very quickly, especially information systems through the Internet. It happens because the Internet can be accessed by anyone, anytime, and anywhere. Access to information through the Internet does not always bring benefits but also risks to the accuracy of information. This risk is vulnerable when information is accessible by hackers.Many efforts have been made to protect data transferred over the Internet, including encryption (protecting data before being transferred over the Internet) and authentication (verifying whether the received data is the same as the sent data). There is knowledge or art of data protecting transferred over the Internet, that is, cryptography (data encoding) and steganography (data disguise). The data to be discussed in this paper is image data.Many steganography methods in protecting information into an image have been published. The data or information that is hidden into an image can be text data or image data. Generally, to hide text data or image data into another image, the original text and original image should be converted into binary digits (bits). Then each digit of the original image or original text is substituted into the last bit of the cover image pixel. By using this method, information could be hidden into the cover image with little difference between the image stego image and the cover image. In this algorithm, every character (for text) or pixel (for image) is hidden into three pixels of cover image. The consequence of this method is, for the text data, the maximum number of characters that can be hidden into the cover image is one-third of the total pixels of the cover image. For image data, the image size that can be hidden into the cover image is one-third the size of the cover image (either long or wide).In modern world, all information communication is done online. It causes the security system when data transfer becomes very important. Steganography has its own mechanism in data protecting [1, 2]. In steganography, the information to be sent is hidden into other media, so that no one knows where the information is hidden. Watermarks and fingerprints are two technologies related to steganography, where steganography tends to hide data in other media [3].Currently research on image encoding generally focuses on the following aspects: image encoding with spatial domains, image coding with domain transformation, image coding based on neural network, chaotic image coding, image coding based on cellular automata, and quantum technology [4]. In cryptography, encoding is the process of transforming information using certain algorithms that make it unreadable by anyone except the one who knows the special information, commonly called a key. The result of this process is called encrypted information [5]. Bouquard et al. have introduced the image encoding algorithm using affine transformation [6]. In this algorithm, the encryption and decryption process pass through two stages; that is, the first stage encodes the image using XOR operations with four key bits and the second stage encodes the encoded image using affine transformation. The conclusion of the study states that the correlation of pixel values between the original image and the encrypted image decreased after transforming the affine transform.Tom has implemented data disguise using stenographic techniques. To make the technique safer they added a level of security by applying cryptography to confidential data before using steganography [7]. For cryptography, they use the Caesar algorithm while for steganography they use the adjacent pixel differences algorithm. Kulkarni and Jatgap substituted secret messages using a 14-square substitution algorithm [8]. Once the text was substituted, then this message was encoded with the RSA algorithm. The next step, this encoded message was hidden into an image by LSB (Least Significant Bit) method. This image works as a carrier file, which will be sent to the recipient. The receiver decrypts to get the original message by performing the same method but in reverse order. Here, it appears that they do two coding techniques, so the system becomes more powerful and secure in the face of hacker attacks. This technique makes it difficult for the troublemakers to manipulate the image and takes a long time to encrypt the message, so it is safe from various attacks through the Internet network.In measuring quality of an image objectively, some data are statistically calculated to determine quality of the reconstruction image. Image quality could be seen from how close the relationship of image forming pixels or by looking at how much the difference in pixel values are statistically distributed. In general, to compare two images, one could use mean square error (MSE) and Peak to Signal Noise Ratio (PSNR) [9, 10]. Choudhary applied the optimization process to a stego image by using the LSB method, so that quality of the stego can get better with lower computational complexity [11]. MSE between stego image and cover image can be derived. Experimental results show that visually the stego image cannot be distinguished from the cover image. The results also showed improvement compared to the previous one.In this paper, we propose a new steganography method to hide an image into another image using matrix multiplication operations on max-plus algebra. This is especially interesting because the matrix used in encoding or information disguises generally has an inverse, whereas matrix multiplication operations in max-plus algebra do not have an inverse. Another advantage of this method is the size of the image that can be hidden into the cover image which is greater than using the previous method.


## 2. Max-Plus Algebra

Max-plus algebra can be used to model disk events related to synchronization and time delays. The application of this theory has a very strong association with production problems [12, 13].The max-plus algebra [7] is a sequential pair (R,⊕,⊗), where R is the set of all real numbers, whereas ⊕ and ⊗ are binary operations on R defined as (1)a⊕b=max⁡a,b,a⊗b=a+bfor every a,b∈R. Operations ⊕ and ⊗ are extensions of matrices and vectors in the same way as conventional linear algebra.In the max-plus algebra [6], the matrix multiplier A⊗B is defined as follows: for any matrix A∈Rm×p, B∈Rp×n, we can obtain matrix C∈Rm×n by the formula(2)cij=⨁k=1paik⊗bkjfor i=1,…,m, j=1,…,n. For a square matrix with degree k, matrix A∈Rn×n denoted by A(k) and was defined by recursive operation on k=2,3,…: (3)Ak=A⊗Ak-1.The set of Rmax with operations ⊕ and ⊗ is called max-plus algebra and denoted by Rmax=(Rmax,⊕,⊗,ε,e). As conventional algebra, operations ⊗ have a higher priority than ⊕. For example, operation 5⊗-9⊕7⊗1 has an understanding like (5⊗-9)⊕(7⊗1).Note that(5⊗-9)⊕(7⊗1)=8, where 5⊗(-9⊕7)⊗1=13.In addition, there is −∞ such thatmax⁡(a,-∞)=max⁡(-∞,a)=a and a+(-∞)=-∞+a=-∞. For any a∈Rmax, there is a small number ε such that(4)a⊕ε=ε⊕a=a,a⊗ε=ε⊗a=ε.Let A∈Rεn×n and b∈Rεn. In general, the system of linear equations in max-plus algebra will have no solution, if A is square matrix or if the number of columns in A is more than the number of rows in A. Therefore, subsolutions concepts are introduced [7].Operator ⊗ is a commutative operator. Except 0, every element has an inverse. The inverse ofx is denoted by x-1 or 1/x. More precisely, we denote x/y or x⊗y-1. x⊗y multiplication could be denoted by xy. The operator allows it to be expanded to a m×m matrix on Rmax [14].LetA and B be two matrices of m×m, operator ⊕, and we define(5)A⊕Bi,j=Ai,j⊕Bi,j,∀i,j∈1,…,m2,A⊗Bi,j=⨁k=1mAi,k⊗Bk,j,∀i,j∈1,…,m2.It is not difficult to prove that the m×m matrix exists in Rmax. Based on the triangular matrix A of size m×m, where Ai,j=0 for i>j, it is indicated that the set of m×m triangular matrices exists in Rmax, but the operator ⊗ is not commutative. Furthermore, not all elements in max-plus algebra have inverse [6].


## 3. Literature Review

The image data character is very different from the text data because an image contains very large data, and all data has a very strong relationship and contains very high data loops [15].Conceptually, the difference between text data and image data can be seen in Table1.Table 1
The difference between text encoding and image encoding.
Type Secret data Encrypt data Remarks Text CSEMCKVIE DTENDLWJF Different  Image (RGB)   P 1 and P2 are different, but visually they are difficult to distinguish Pixel(P1) = (24,45,233) Pixel(P2) = (10,65,198)  Image (Gray)   P 1 and P2 are different, but visually they are difficult to distinguish Pixel(P1) = (87) Pixel(P2) = (114)An image is defined as a two-dimensional function,f(x,y), where x and y are spatial coordinates and f is the light intensity at coordinates (x,y) known as the gray degree. An image is called a digital image if, in position (x,y), there is an amplitude value. A digital image constitutes a finite number of elements, each of which has a particular location and a particular value. These elements are called picture elements or images of elements or pixels [16].The pixel of an image can be converted into 8 binary digits (bits). The first to fourth bit is called LSB (Least Significant Bit) where the bit value changes in this position have no impact on the image. The fifth to eighth bit is called MSB (Most Significant Bit), where changes in bit values in this position have an effect on image. Figure1 shows the bit positions of MSB and LSB.Figure 1
MSB and LSB bit.The maximum deviation of an image can be found by making a grayscale histogram and calculating its area. The larger the deviation is, the better the encoding will be. To find the area of deviation image can be seen from the following formula [17]:(6)L=h0+h2552+∑i=1254hi.Here,L is the area of deviation;hi is the number of pixels that have gray degree;i is the value of pixels.A simple example of hiding data into an image is called insertion of least significant bit (LSB). For 24-bit colored images, the number of changes will be minimized so that it is difficult to distinguish by the human eye. For example, suppose we have three adjacent pixels (nine bytes) by using RGB encoding. Suppose we will hide data 101101101. Put 9 bits of data in the LSB position, so the following pixels are obtained (bold font shows the changed bits):(7)100101010000110111001001100101100000111111001010100111110001000011001011Based on the formula, here is a snippet of the steganography process (see Figure 2).Figure 2
1D array representation.Application of stenographic LSB uses secret key. Kulkarni and Jatgap [8] take a binary representation to hide information and replace the LSB of each cover image bit. Here, a secret key is introduced to protect the hidden information by using the formula:(8)Coverimage+secretkey+hiddeninformation=stegoimage.To hide information, one should use cover image. Cover image is divided into three matrices (Red, Green, and Blue). Secret key is converted to 1D bit stream array. Secret key and Red matrix are used as decision-makers to replace hidden information into the Green matrix or Blue matrix. Every bit of the secret key is operated by operators XOR with every LSB bit on the Red matrix. The result of the XOR operation is used to determine the bit of the hidden information to be replaced in the Green matrix LSB or the Blue matrix. The same process is done until all information is successfully hidden [18]. In this method, every character (plain text) or every pixel (plain image) is hidden into three pixels of cover image. As a consequence of this method, for plain text, the maximum number of characters that can be hidden into the cover image is 1/3 of the total pixel cover image. The maximum size of plain image that can be hidden is 1/3 of the size of the cover image (for length and width).In the previous method, it is required that the size of the secret image should be smaller than the size of the cover image. In this article, we propose a new method so that the size of the secret image can be increased to the same size as the cover image.


## 4. The Proposed Method

The following algorithm is how to hide secret image into another image with maximal size equal to cover image size:(1)
Convert pixels from secret image and cover image into bitwise form.(2)
Change the MSB from the pixel cover to the 2 × 2 matrix form.(3)
Find the secret image matrix using
(a)
SR(i,j)=R(i,j)⊗G(i,j),(b)
SG(i,j)=G(i,j)⊗B(i,j),(c)
SBi,j=Bi,j⊗R(i,j),where
R(i,j) is the MSB of cover image matrix on the Red layer at position (i,j),G(i,j) is the MSB of cover image matrix on the Green layer at position (i,j),B(i,j) is the MSB of cover image matrix on the Blue layer at position (i,j).(4)
Substitute the MSB secret image into the LSB stego image with the following rules:
(a)
Ifa11>a12, then substitute the first bit of MSBsi into the second bit of LSBci and substitute the second bit of MSBsi to the first bit of LSBci.(b)
Ifa11≤a12, then substitute the first bit of MSBsi into the first bit of LSBci and substitute the second bit of MSBsi into the second bit LSBci.(c)
Ifa21>a22, then substitute the third bit of MSBsi into the fourth bit of LSBci and substitute the fourth bit of MSBsi into the third bit of LSBci.(d)
Ifa21<a22, then substitute the third bit of MSBsi into the third bit of LSBci and substitute the fourth bit of MSBsi into the fourth bit of LSBci.Hereaij is the element of matrix of the secret image at row I and column j.MSBsc is the MSB of secret image.LSBst is the LSB of stego image.For more details, the proposed coding system can be illustrated through the flowchart as in Figure3.Figure 3
Flowcharts to hide the secret image into the cover image.Here is an algorithm to display the secret image of the stego image.(1)
Convert pixels of stego image into 8-bit form.(2)
Calculate the secret image matrix by
(a)
SR(i,j)=R(i,j)⊗G(i,j),(b)
SG(i,j)=G(i,j)⊗B(i,j),(c)
SB(i,j)=B(i,j)⊗R(i,j).Here
R(i,j) is the LSB of stego image matrix on the Red layer at position (i,j).G(i,j) is the LSB of stego image matrix on Green layer at position (i,j).B(i,j) is the LSB of stego image matrix on the Blue layer at position (i,j).(3)
Exchange LSB bitwise LSB of stego image with the following rules:
(a)
Ifa11>a12, then exchange the first bit with the second bit.(b)
Ifa21>a22, then exchange the third bit with the fourth bit.Hereaij is the matrix element of the secret image matrix on the row I and column j.(c)
Convert LSB and MSB from the stego image.(d)
Exchange bit 1 with bit 5.(e)
Exchange bit 2 with bit 6.(f)
Exchange bit 3 with bit 7.(g)
Exchange bit 4 with bit 8.For more details, decryption algorithm that can be made through the flowchart as in Figure4.Figure 4
Flowchart to display the secret image of the stego image.In Table2, the example pixel data from the secret image and the cover image is presented.Table 2
Example data.
Image Layer Value Bit MSB LSB Secret image Red 79 00010001 0001 0001 Green 108 01101100 0110 1100 Blue 205 11001101 1100 1101  Cover image Red 28 00011100 0001 1100 Green 104 01101000 0110 1000 Blue 146 10010010 1001 0010We process the following operations:SR=R⊗GSG=G⊗BSB=B⊗R:(9)SR=0001⊗0110=1121,SG=0110⊗1001=1221,SB=1001⊗1001=2112.In the matrix column in Table 3, if element of the left matrix is larger than element of the right matrix, then the element will be exchanged. The results of the operation process in Table 3 are given in Table 4.Table 3
Operation process.
Secret image Matrix Stego image MSB Process Process LSB 0001 0001 SR: (a11=a12a21>a22) 0010 0010 0110 0110 SG: (a11<a12a21>a22) 0101 0101 1100 1100 SB: (a11=a12a21<a22) 1100 1100Table 4
The results.
Image Layer Value Bit MSB LSB Matrix Cover R 28 00011100 0001 1100 R = 1 0 0 1 G 104 01101000 0110 1000 G = 0 1 1 0 B 146 10010010 1001 0010 B = 1 0 0 1  Secret R 79 00010001 0001 0001 SR = 1121 G 108 01101100 0110 1100 SG = 1221 B 205 11001101 1100 1101 SB = 2112  Stego R 18 00010010 0001 0010 G 101 01100101 0110 0101 B 156 10011100 1001 1100


## 5. Experimental Results and Analysis

To test our method, an experiment was performed. Here the test is done by using a laptop with microprocessor core i3 and Microsoft Windows 10 operating system. Computer program was created by using MATLAB R2016b and it applied to an image of good quality. The results of our algorithm are shown in Figure5. We use the balloon image as a secret image and carrot image as the cover image. Cover image and secret image have the same size that is 163 × 133.Figure 5
Experimental result.Figure5 shows that the stego image (Figure 5(c)) is similar to the cover image (Figure 5(a)), although visually inside the cover image contains a secret image (Figure 5(b)). The result of stego image has a size of 163 × 133. It is proved that this method can hide the secret image that has size as same as the cover image. This needs to be demonstrated by using statistical analysis. Therefore, an ideal encoding must have power when there is an attack through its statistical model. To prove the power of this proposed method, we performed a statistical analysis by displaying a histogram and computing the correlation coefficient between two neighboring pixels on the cover image and stego image.The abscissa histogram shows the pixel value and the ordinate showing the frequency or how often the pixel value appears. The histogram of the cover image shown in Figure6(a) has a larger area. This area shows how often the pixel value appears in an image. Histogram of the secret image shown in Figure 6(b) has a smaller area. This shows that the cover image is clearer than the secret image. Histogram of the stego image shown in Figure 6(c) has a pattern similar to the cover image. This shows that the cover image has not significantly changed.Figure 6
Histogram analysis.In addition to histogram analysis, we also analyze the correlation coefficients of two vertically neighboring pixels, two horizontally neighboring pixels, and two pixels diagonally adjacent to the stego image and cover image. First, we select 10000 pixels on a neighboring image. Then we calculate the correlation coefficient with the following formula:(10)cov⁡x,y=Ex-Exy-Ey,rxy=cov⁡x,yDxDy.Here, x and y are the values of two neighboring pixels. In numerical computation, the correlation coefficient can be calculated using the following formula [19]:(11)Ex=1N∑i=1Nxi,Dx=1N∑i=1Nxi-Ex2,covx,y=1N∑i=1Nxi-Exy-Eyi.Based on the proposed method, the correlation coefficient between two vertically neighboring pixels for the cover image and stego image is 0.91432 and 0.91039, respectively. Similarity of the results to the vertical and diagonal directions is shown in Table5. It is apparent in Table 5 that there is a strong correlation between two neighboring pixels, or in other words the stego image and cover image are difficult to distinguish.Table 5
The correlation coefficient.
Image Horizontal Vertical Diagonal Cover 0.97028 0.91432 0.97337 Stego 0.96014 0.91039 0.92923In the image processing mean square error (MSE) is often used to determine how big the image quality difference between before and after coding process. The formula is presented as follows [15]:(12)MSEimage=1MN∑y=1M∑x=1NIx,y-I′x,y2,whereM is the length of image (in pixel),N is the width of image (in pixel),I(x,y) is the initial image pixel value,I′(x,y) is the resulting image pixel value.Based on the calculation, the MSE between the cover image and stego image is 361.7734Improving the visual quality of digital image can be subjective. Saying that one method provides better quality image could vary from person to person. Using same tests images, different image enhancement algorithm can be compared by peak signal to noise ratio (PSNR). The mathematical representation of the PSNR is as follows:(13)PSNR=20log10⁡MAXfMSE,where MAXf is the maximum signal value that exists in our original “known to be good” image. Two identical images will have a zero MSE value and an infinite PSNR value so the smaller the difference between the two images, the smaller the MSE value and the larger the PSNR value [19].From the calculation results obtained PSNR for cover image is 21.8295 and PSNR for stego image is 21.8142. Here it looks very small value difference so it can be said that the image between cover image and stego image is similar. With this similar result it can be said that the coding result goes well.Based on analysis of time, this algorithm has the time complexityO(n). This shows that the algorithm has execution time that increases linearly according to the number of pixels (image size).Comparison of Max-Plus Methods and Previous Methods. To compare the proposed coding method with the previous coding method, we use koala image (1024 × 768) as a secure image and tulips image (1024 × 768) as cover image.From Figures7 and 8, we can see that the encoding between the max-plus and the previous method produces the same stego image. Both methods can be used to hide the secret image that has same image size between the secret image and the cover image. Figures 9 and 10 show the results of decoding by max-plus and previous methods. Hence, we conclude that the decoding process of the Max-Plus method can return the stego image same as the secret image, while in the previous method it cannot return the stego image to the secret image perfectly but only a quarter of the part. It makes the previous method display a quarter of the secret image during the description process.Figure 7
Encoding by max-plus algebra.Figure 8
Encoding by previous method.Figure 9
Decoding by max-plus algebra.Figure 10
Decoding by previous method.


## 6. Conclusions

The proposed method has been tested on many secret images, and the results are satisfactory which have a high level of strength and a high level of security and it can be used in various operating systems. A pixel of the secret image is hidden in a cover image pixel by matrix multiplication operations in max-plus algebra, so that the message becomes safer. Maximum secret image size that can be hidden is the same as the size of cover image. This is the novelty of this method where, in the previous method, size of secret image is always smaller than the cover image. In our future research, we will construct an algorithm to hide a text into an image by using max-plus algebra.



---

*Source: 6718653-2018-05-15.xml*