An issue both LSB Replacement (LSBR) and LSB Matching (LSBM) have in common is the relationship between the size of the message and the number of bytes which must be changed. For example, if our secret message is 32 bytes (256 bits), we need to change roughly 128 bytes in the cover image. (The reason we change 128 bytes instead of 256 bytes is because half the bytes in the cover image will have LSBs which already match our desired message bits.) Matrix Embedding solves this problem by allowing us to embed secret messages using far fewer bytes - we only need to change one LSB to store two message bits. It also uses the same technique as LSBM for the LSB changes (addition and subtraction) which causes the image to retain most of its symmetry.
Let us explain this using a 3 x 3 pixel RGB image:
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27
As this is an RGB image, each pixel has three bytes (one byte representing the colour Red, one byte representing the colour Green, and one byte representing the colour Blue), hence why the image is a matrix of 3 x 9 bytes.
For simplicity let us assume our hidden message is just two bits long:
10
We need to define two formulas:
M1 = LSBB0 ⊻ LSBB1
M2 = LSBB1 ⊻ LSBB2
Looking at the above we can see we need to use three image bytes (B0, B1, B2) and the exclusive or (⊻) function.
First we will calculate LSBB0, LSBB1, and LSBB2. To keep things simple we will use sequential embedding, so we need to begin from the first byte in the image:
B0 = 00000001
LSBB0 = 1
B1 = 00000010
LSBB1 = 0
B2 = 00000011
LSBB2 = 1
We can then calculate M1 and M2:
M1 = LSBB0 ⊻ LSBB1 = 1 ⊻ 0 = 1
M2 = LSBB1 ⊻ LSBB2 = 0 ⊻ 1 = 1
We now define four rules:
(1) If both M1 and M2 match the bits we want to hide, we do nothing.
(2) If both M1 and M2 do not match the bits we want to hide, we randomly add or subtract one to LSBB1.
(3) If M1 is a match but M2 is not, we randomly add or subtract one to LSBB2.
(4) If M2 is a match but M1 is not, we randomly add or subtract one to LSBB0.
Let us remind ourselves of the values of M1, M2 and our secret message:
message = 10
M1 = 1
M2 = 1
Using the above four rules we can see M1 is a match, but M2 is not, therefore we need to follow rule three and randomly add or subtract one to LSBB2.
If we randomly add one, our stego-image will be as follows:
1 2 4 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27
As you can see, we have now embedded two bits using only one LSB change (we only changed the third byte). If our secret message was 11, we would not have to make any LSB changes, as rule one would apply.
Decoding the hidden message requires a little more work than LSBR and LSBM, but is still relatively straightforward. For each byte triplet, we can extract the embedded bits using the following formulas:
Bit 1 = (LSBB0 & 1) ⊻ (LSBB1 & 1)
Bit 2 = (LSBB1 & 1) ⊻ (LSBB2 & 1)
The LSBs of the first three bytes in the stego-image are 1, 0, 0. Plugging these numbers into the formulas gives us the hidden message, 10:
Bit 1 = (1 & 1) ⊻ (0 & 1) = 1 ⊻ 0 = 1
Bit 2 = (0 & 1) ⊻ (0 & 1) = 0 ⊻ 0 = 0
The disadvantage of Matrix Embedding is it reduces the number of bytes we can use to embed our secret message. This is because we use three bytes to store two message bits, which reduces the number of bytes available to us by one third.