In a previous work we proposed an algorithm to embed watermark bits directly in a compressed bitstream. The embedding algorithm is reversible, requires no decompression, causes no increase in file size, and is fast. The problem is that the watermarked bitstream will either lose format-compliance or suffer unacceptable visual degradation. We have now solved these problems for JPEG streams. The algorithm determines the AC VLC codespace that is actually used by the image. Watermarking specific VLCs places the resulting codewords outside of the used codespace, but still within the orignal VLC table specified in JPEG standard. To keep the watermarked stream format-compliant and visually acceptable, the run/size values of watermarked VLCs are remapped in a way to keep visual degradation to a minimum. Since watermarked VLCs are never used in the image, this remapping does not alter the image outside of watermarked VLC codespace.
Algorithms that perform data hiding directly in the compressed domain, without the need for partial decompression or transcoding, are highly desirable. We based this work on the recognition of the idea that only a limited amount of a possible codespace is actually used for any specific code. Therefore, if bits are chosen appropriately, watermarking them will place a codeword outside of the valid codespace. Variable length codes in compressed bitstreams, however, have virtually no redundancy to losslessly carry hidden data. Altered VLCs will likely remain valid. In this work, we examine the bitstream not as individual VLCs but as codeword-pairs. Pairing codewords conceptually shrinks the percentage of available codespace that is actually being used. This idea has a number of key advantages, including that the watermark embedding is mathematically lossless, file size is preserved and the watermarked bitstream will still remain format-compliant. This algorithm is most appropriate for compression algorithms that are error-resilient. For example, the error concealment property of MPEG-4 or H.263+ can also counter bit “errors” caused by the watermarking while playing the video. The off-line portion of the algorithm needs to be run only once for a given VLC table regardless of multiple mediums employing the table. This allows for the algorithm to be applied in real time, both in embedding and removal, due to implementation in the compressed domain.