DSP coprocessor adapts digital watermarking for real-time video

The ease of copying or modifying digital data, including audio, images, and video, coupled with the advent of high-speed Internet access and peer-to-peer networking, makes it difficult to protect copyrights and preserve the integrity of digitized multimedia content. Toward this end, digital watermarking is viewed by many - when encryption fails or is not practical - as the best barrier for copy-protecting content.

Digital watermarking can be used in several ways, such as to prevent illegal playing or copying and to trace illegal copies. It can also show modified parts of an image and invisibly carry information like the place and date of purchase, a document identifier, or the number of authorized viewings or copies.

During the last few years, research has focused mainly on creating attack-resistant watermarks for still pictures. In contrast, little attention has been paid to simplifying the platform needed to run the watermark algorithm. The platform is usually assumed to be a powerful Pentium-processor powered PC or a Unix workstation.

In the near future, however, more types consumer equipment will likely need to run watermark algorithms. Some MP3 players already do, with DVD players and recorders likely to follow soon. Ultimately, digital televisions and still cameras, set top boxes, and wireless appliances — indeed any device that can display or capture multimedia content — will likely include a watermark algorithm.

These algorithms are, for the most part, computationally intensive. Thus, for use in consumer products, they must do more than yield a robust watermark; that is, one that withstands manipulation, like JPEG compression. The watermark must have low visibility to preserve the look of the original content. It must also run on the host application platform, typically a 16- or 32-bit microprocessor, DSP or system-on-chip (SoC) having only a few hundred kilobytes of memory.

One starting point for producing a real-time video watermark is a still-picture watermark algorithm. The algorithm was adapted to both a 32-bit embedded DSP and a 32-bit very long instruction word (VLIW) multi-issue processor core. Either is well suited for wireless embedded applications. The adaptation was done at the algorithmic and C-code levels, and then fine-tuned for the specific target processor. Results were measured in terms of the execution times for different platform capabilities.

Next, the watermark algorithm was extended to digital video, in which different embedding strategies were compared to reach the best tradeoff between robustness and visibility. The last step was to describe a hardware accelerator needed to meet the time constraints of real-time video. In practice, the accelerator would attach to the main processor in a hypothetical system-on-chip MPEG codec designed to embed and extract the watermark.

The still-picture algorithm that served as the starting point rests on a foundation of fractal image-coding theory and, in particular, the notions of self similarity in which only one part of similar image parts are coded. The main idea of this approach is to use some invariance properties, such as the invariance of affine transformations, to ensure watermark robustness. What's more, the process of embedding a watermark consists of three steps: formatting and encrypting the watermark; generating the cover, which is the transformed image used to hide the watermark; and embedding the watermark into the cover.

In the first step, the message bits of the watermark to be hidden are redundantly distributed by oversampling and duplicating the message to obtain a watermark that matches the size of the image. Redundancy is necessary to ensure robustness. The watermark is then globally encrypted by performing an exclusive OR (XOR) function with a pseudorandom noise generated from a secret key. The result of the XOR function is the encrypted watermark.

The XOR operation performs two functions. First, it secures the hidden message through encryption and, second, it removes repetitive patterns that, if left in place, would affect the psycho-visual impact of embedding the watermark. In the second step, generating the cover, a fractal approximation, Iapprox, is computed from the original image, Ioriginal. The cover, Icover, corresponds to the error image.

In the final step of the embedding process, the cover is modulated with the watermark. Modulation consists of setting some of the cover pixels to zero — in this case, pixels are samples of the cover, having values between -255 to +255. Specifically, if the current pixel is positive and the watermark bit is zero, or if the pixel is negative and the bit is one, the pixel is zeroed.

The watermark extraction algorithm is similar to that for embedding. In fact, embedding and extraction are dual operations, meaning that extraction is achieved by reversing the embedding operation. Specifically, in extraction, a fractal approximation is calculated from the watermarked image, generating a cover that is close to the original. Next, the cover is decoded according to the modulation rules: a positive pixel carries a value of one, a negative pixel is a zero.

A crucial fact in this process is that most geometric transformations on the watermarked image are also transferred to the cover. As a result, the mark is not lost, however the ciphering noise must be correctly positioned with respect to the cover before performing the XOR operation. Therefore, additional bits, called resynchronization bits, are added to the watermark message.

Optimizing algorithms

The next task was to optimize the algorithms for an embedded processor. Before optimization it took about 40 seconds to watermark a 512-by-512-pixel image on a 733-MHz Intel Pentium III microprocessor. Optimization was done in two steps: first at the algorithmic level, and then at the C code level, with some fine tuning done to port the programs to the DSP or VLIW processor. The result of optimizing the algorithms alone was a reduction in computing time from 40 to 10 seconds.

Optimization focused on the fractal approximation part of the algorithm, which takes about 80 percent of the total computing time in both embedding and extraction. Fractal approximation is very similar to fractal coding. Specifically, the image is parsed into non-overlapping range blocks (each 8-by-8 pixels in our case), which in turn are matched with larger domain blocks (32-by-32 pixels, sub-sampled to 8-by-8 pixels), chosen in a limited neighborhood, and all their isometrics (domains transformed by reflections and rotations). In our research, we applied the eight classic isometries: identity, four reflections, and three rotations.

Next, we turned to algorithmic optimizations. To reduce the complexity of fractal coding, several variations or parameters were implemented or evaluated, including a different and simpler metric (the sum of absolute difference or SAD), the size of the blocks, and the computing method for brightness and contrast adjustments.

To assess each of these optimization variations required a precise methodology. As with any watermarking technology, there is a compromise among visibility, robustness, and bit capacity of the embedded watermark. For our tests, we fixed the capacity at 64 bits and evaluated the remaining two parameters.

Visibility was assessed by comparing the PSNR of the original with watermarked image for both the original and modified algorithms. We also performed a visual evaluation. Robustness was assessed by comparing the original and modified algorithms for cover stability, that is, the number of cover pixels that have the same sign in the modulated cover during embedding and in the extracted cover. The higher the number, the greater the robustness of the algorithm, since more correct bits will be extracted. The comparison of optimization methods was done after image manipulations like noise addition and blurring. As it turns out, the Euclidian norm gave overall better results than the SAD.

The first port was to a DSP from STMicroelectronics. Thanks to the prior generic optimization, only a small amount of work was needed to optimize the code for this target. Next the code was ported to a VLIW processor, also from STMicroelectronics. With four fixed-point arithmetic logic units (ALUs), this processor can handle four instructions in parallel, making it the better performing of the two processors.

The next step was to adapt the algorithm to video. Our assumption was that the video version would need to be as robust as the still-image version. Working at the algorithmic level, we merged the watermark with an MPEG-2 codec developed at STMicroelectronics. In this way, we could mark the video sequences during MPEG-2 coding and extract the watermark during decoding.

We tested the video algorithms robustness in the face of specific manipulations including MPEG-2 compression, overcompression, and cropping. For MPEG-2 compression, the watermark was extracted following compression down to 1.5 Mbits/sec. As for overcompression, which is likely to happen on an MPEG-2 sequence subject to a second compression at a lower bit rate, two things can happen: The group of pictures of both encodings can match or not. If they do match, the manipulation is very close to a single encoding, and the watermark can be found down to about 1.5 Mbits/sec. If the group of pictures do not match, the previous I and P frames can become B frames. In that case, the watermark, being much more compressed, can be extracted down to 2.5 Mbits/sec. with a frame accumulation of 100.