A fast H.264 compressed domain watermarking scheme with minimized propagation error based on macro-block dependency analysis

Embedding watermark into H.264 bit-streams directly can simplify encoding procedure and reduce computational cost comparing with conventional encoder based watermarking algorithms. However, possible error propagation may occur due to the prediction mechanism of the H.264 codec and cause video quality degradation. Expensive computation is often needed to compensate such drift. Furthermore, compensation in compressed domain usually leads to significant increase in the size of the watermarked video. To address these problems, we have developed a novel paradigm that can minimize the error propagation due to the watermarking process with very low complexity, high fidelity, robustness and security. This new paradigm is based on careful analysis of the dependency relation among the macro-blocks. We first extract the macro-block dependencies from the H.264 prediction mechanism and cache them as a graph. We then select these macro-blocks that have the least impact to the overall sequence to embed the desired watermark. This new way of embedding shall intrinsically minimize the error propagation without post processing of drift compensation. Extensive simulations have been carried out to confirm that the proposed watermark embedding is indeed able to achieve the desired performance with low complexity, high fidelity, robustness and security.