Matrix encoding implementation in the F5 steganography algorithm is unclear

Question

I need to implement my own F5 algorithm. I have read the F5 documentation and the paper can be found here.

In the section 6.2 Matrix Encoding of the paper, equations 16-18 define the change density, D(k), the embedding rate, R(k) and the efficiency rate, W(k), as follows:

D(k) = 1 / (n + 1) = 1 / 2**k

R(k) = k / n = k / (2**k - 1)

W(k) = R(k) / D(k) = k * 2**k / (2**k - 1)

Where n is the number of modifiable places in a code word and k the number of embedding bits. W(k) indicats the average number of bits we can embed per change.

In the source code we find the number of bits as stated below. Can someome please explain why usable and changed are calculated this way? I simply don't understand the logic.

    int _changed = 0;
    int _expected = 0;
    int _one = 0;
    int _large = 0;
    int _zero = 0;
    for (i = 0; i < coeffCount; i++) {
        if (i % 64 == 0) {
            continue;
        }
        if (coeff[i] == 1) {
            _one++;
        }
        if (coeff[i] == -1) {
            _one++;
        }
        if (coeff[i] == 0) {
            _zero++;
        }
    }
    _large = coeffCount - _zero - _one - coeffCount / 64;
    _expected = _large + (int) (0.49 * _one);
for (i = 1; i < 8; i++) {
    int usable, changed, n;
    n = (1 << i) - 1;
    usable = _expected * i / n - _expected * i / n % n;
    changed = coeffCount - _zero - coeffCount / 64;
    changed = changed * i / n - changed * i / n % n;
    changed = n * changed / (n + 1) / i;
    //
    changed = _large - _large % (n + 1);
    changed = (changed + _one + _one / 2 - _one / (n + 1)) / (n + 1);
    usable /= 8;
    if (usable == 0) {
        break;
    }
    if (i == 1) {
        System.out.print("default");
    } else {
        System.out.print("(1, " + n + ", " + i + ")");
    }
    System.out.println(" code: " + usable + " bytes (efficiency: " + usable * 8 / changed + "." + usable * 8
            / changed % 10 + " bits per change)");
}

coeff is an array that holds the DCT coefficients,coeffCount is the number of DCT coefficients,_large is the teoretical number of bits from the image that can be encoded and expected is the expected capacity of the image(with shrinkage).I don't understand what is the logic behind usable and changed variables

Answer 1

The last paragraph of the section 6.2 in the paper says the following and I quote:

We can find an optimal parameter k for every message to embed and every carrier medium providing sufficient capacity, so that the message just fits into the carrier medium. For instance, if we want to embed a message with 1000 bits into a carrier medium with a capacity of 50000 bits, then the necessary embedding rate is R = 1000 : 50000 = 2 %. This value is between R(k = 8) and R(k = 9) in Table 1. We choose k = 8, and are able to embed 50000 : 255 = 196 code words with a length n = 255. The (1, 255, 8) code could embed 196 · 8 = 1568 bits. If we chose k = 9 instead, we could not embed the message completely.

I believe this should be straightforward. If you can understand this, you can follow the steps below.

One more preliminary thing is the expression result = var - var % n; throughout the code. This means you make var exactly divisible by n by removing the remainder (modulo operation). Now onto the loop block.

n = 1 << i - 1

This is the code word length, as defined in the paper.

---

usable = _expected * i / n - _expected * i / n % n;

To understand this line, remember that i / n is the embedding rate, R(i). In simple words, the number of possibly available bits (_expected) times the embedding rate (i / n), gives the number of bit we can encode. In the example from the quote that's 50000 / 255 * 8 = 1568 bits.

---

changed = coeffCount - _zero - coeffCount / 64;
changed = changed * i / n - changed * i / n % n;
changed = n * changed / (n + 1) / i;

The first line says that the number of bits that we can go through (call this total) is the number of coefficients (coeffCount), while skipping any zeros and the DC component of each 8x8 block (coeffCount / 64). Each 8x8 block has 64 coefficients, but only one is the DC coefficient, so every 64 coefficients you have one more DC coefficient to skip.

The second and third lines go together. Notice than in the second line you multiply by the embedding rate and you make that result perfectly divisible by the code word length. In the third line you divide by the embedding rate, thereby cancelling the previous step, and then you multiply by the change density, 1 / (n + 1), to find the number of bits to be changed on average.

The reason you go through this whole process is because the order of divisions and multiplications matter. As a straightforward example, consider you have 150 bits and 7 items that you want to distribute evenly into as many bits as possible. How many bits will you need overall?

7 * (150 / 7) = 7 * 21 = 147

---

Note: The following lines overwrite the currently computed value of changed. The previous 3 lines and the following 2 independently tend to give similar answers when I make up my own _one, _zero, coeffCount values. One of these two versions may be old code which was not removed. Regardless, the logic is the following.

changed = _large - _large % (n + 1);
changed = (changed + _one + _one / 2 - _one / (n + 1)) / (n + 1);

The first line has to do with the change density, D(i), since you make the expression perfectly divisible by n + 1. Because of how _large is defined, this is similar to how changed is computed in the previous version.

_large = coeffCount - _zero - _one - coeffCount / 64;

Which bears close resemblance to this

changed = coeffCount - _zero - coeffCount / 64;

The next line is a little bit hazy to me, but this is what it seems to achieve. It reintroduces back the _one it substracted in _large and one half of the ones. This is due to shrinkage, since it replicates the idea in _expected = _large + int(0.49*_ones). I don't quite understand why you would substract ones / (n + 1), but multiplying this whole expression by the change density, 1 / (n + 1), you get the number of bits you expect to change.

Conclusion

The two ways for calculating the expected number of bits to change are not exact and it has to do with not knowing in advance exactly how many will be changed. They both seem to give similar results for given values of _zero, _one and coeffCount. None of this is really necessary as it just estimates the efficiency for different k as in the quote. You just need to find the maximum k for which you use as much of the carrier medium to embed your information. This is done by just calculating usable and breaking the loop as soon as you don't have enough bits to embed your message. And this exact thing is done a bit further down in the source code.