Spreading - Disappearing Cryptography - page 281

mean the information can be spread out over more elements with
smaller changes. But after a certain point, the changes become
too small to measure. Imagine, for instance, the simplest case of a
grayscale image, where the values at each pixel range from 0 to 255 .
Adding a small amount, say

25 , is not going to change the value of
any pixel at all. No one is going to be able to recover the information
because no pixel is actually changed by the small additions.
This problem can be fixed with this algorithm. Let

.

be the
amount to be spread out over all of the elements in the block. If this
was spread out equally, the amount added to each block would be
less than the quantized value.
While

S

S is greater than zero, repeat the following:

1. Choose an element at random.

2.Increasetheelementbyonequanta. Thatis,ifitisasimple
linearly encoded data value like a pixel, add one quanta to it. If
it is a log-encoded value like an element in a sound file, select
the next largest quantized value.

3. Subtract this amount from S .

The average of all of the elements in the block will still increase,
but only a subset of the elements will change.

14.4.2 Perturbed Quantization

Another solution tominimizing the changes to an image is to choose
the pixels (or other elements) that don't show the change as readily as
the others. Here's a basic example. Imagine that you're going to turn
a nice grayscale image into a black andwhite image by replacing each
gray value between 0 and 255 with a single value, 0 or 255. This pro-
cess, often called half-toning , was used frequently when newspapers
could only print simple dots.
The easiest solution is to round off the values, turning everything
between 0 and 127 into a 0 and everything between 128 and 255 into
a 255 . In many cases, this will be a good approximation. Replacing a
232 with a 255 doesn't change the result too much. But there may
be a large collection of gray pixels that are close to the midpoint.
They could be rounded up or down and be just as inaccurate. The
perturbed quantization algorithms developed by Jessica J. Fridrich,
Miroslav Goljan, Petr Lisonek and David Soukal focus on just these
pixels. [FGS04, FGLS05, Spi05]
The problem is that while the sender will know the identities of
these pixels, the recipient won't be able to pick them out. There's no