Approaching optimal value expansion for reversible watermarking

We investigate in this paper several recently proposed reversible watermarking algorithms based on value expansion schemes: bitshifting, histogram modification, spread spectrum, companding and prediction-error expansion, and present a general model - histogram expansion - for all value expansion based reversible watermarking algorithms, which demonstrates a unified view of these different algorithms and gives them a performance comparison in terms of watermarking distortion and embedding capacity from this unified view. With this general model of histogram expansion, performance of different value expansion algorithms can be evaluated and compared directly from their value expansion modes. A better value expansion mode has an advantage in performance from its inherent value expansion structure, which is stable to different input testing media. We deduce from this general model a formulated distortion estimation, which in form guarantees the existence of the optimal value expanding scheme for a specific media to be watermarked. The optimal value expansion can be achieved by optimization methods if the relevant computational complexity is permitted in practical applications. For simplicity, we propose a sub-optimal but efficient value expanding scheme to approach the best performance of reversible watermarking. In the later part of this paper, we investigate the possibility to further increase the performance by improving the histogram generating patterns in the sense of clearer separation of scale values in different ranges. All ideas proposed above are perfectly demonstrated in our experiments.