Rate and Distortion Optimization for Reversible Data Hiding Using Multiple Histogram Shifting Source: IEEE Transactions On Cybernetics, Vol. 47, No. 2,February 2017:315-326 Authors: Junxiang Wang, Jiangqun Ni, Xing Zhang, and Yun-Qing Shi Speaker: Lin Jiang-Yi Date: 11/02/2017 前三個作者都是 Information Science and Technology,Sun Yat-sen University, Guangdong,廣東中山大學 Department of Electronics and Computer Engineering,New Jersey Institute of Technology, Newark, NJ 07102, USA

Outline Introduction Proposed Scheme --Rate and Distortion Model --Rate and Distortion Optimization using GA --Embedding and Extraction Process Experimental Results Comments

Prediction error after embedding 𝑒 ′ Introduction（1/3） 1、Histogram Shift（HS） I - I’ -2 1 6 -3 7 Cover Image I Prediction Image I’ Prediction error 𝑒 I’ + e’ embedding -3 2 1 7 -4 8 Prediction error after embedding 𝑒 ′ Prediction error Histogram Stego Image I’’

Introduction（2/3） 2、Genetic Algorithm（GA） selection crossover mutation

Introduction（3/3） 1、Multiple 2、Multilayer P1 P2 Z1 Z2 P P Z1 Z2 1中一次性選擇這麼多個P和Z，所以P和Z各不相同 2中是一次選擇一個P和Z，做完一次shift，接著繼續選擇合適的P和Z，繼續做shift。所以可能這一次的P還是下一次的P（如果histogram很陡） Z1 Z2

Rate and Distortion Model(1/11) 1、HS Embedding With Single Pair of Peak and Zero Bins 假設P1是Peak Point Z1是Zero Point +1/2 不是表示移動了1/2的位置，而是指有一半的P1移動到了P1+1（這裡假設embedding的數據是均勻分佈，也就是0，1值各占一半） represents the shift of the ith bin

Rate and Distortion Model(2/11) 1、HS Embedding With Single Pair of Peak and Zero Bins Suppose the secret message w = {w} of length C. The distortion is computed as： h(i)： denotes the frequency of occurrence for value i in histogram。

Rate and Distortion Model(3/11) P Example: Z Suppose P = 0,Z=4,C=12 h(0)=13,h(1)=9,h(2)=5,h(3)=2,h(4) = 0 -2 -1 0 1 2 3 4 h(i)： denotes the frequency of occurrence for value i in histogram。 D=h(1)+h(2)+h(3)+0.5*C=9+5+2+0.5*12=22

Rate and Distortion Model(4/11) 2、 HS-Based Multiple Embedding vector Note：Peak point p2 is shift to p2+1 after the [p1,z1] embedding，which is referred to as ‘peak-bin drift’.Similarly we have ‘zero-bin drift’ [-255,255]因為我們使用的carrier image一般是用Predictition Error 所以只會在這個範圍內。 represents the accumulated shifts of the ith bin

Rate and Distortion Model(5/11) 2、 HS-Based Multiple Embedding Z1是Zero Point，所以直方圖上該點的值為0，所以binZ1 雖然有移動，但是不影響Distortion，所以不用計算。

Rate and Distortion Model(6/11) 2、 HS-Based Multiple Embedding

Rate and Distortion Model(7/11) 2、 HS-Based Multiple Embedding

Rate and Distortion Model(8/11) 2、 HS-Based Multiple Embedding(m pairs) The final Distortion can be evaluated：

Rate and Distortion Model(9/11) Two important issues： a、The computation involves the tracking of both peak-bin drift and zero-bin drift, dynamically updating the peak and zero bins for each embedding level and the actual implementation of m-level multiple shifting. b、The evaluation of distortion when different peak and zero bins are paired and sequentially arranged in the process of multiple embedding.

Rate and Distortion Model(10/11) 2、 HS-Based Multiple Embedding Z1是Zero Point，所以直方圖上該點的值為0，所以binZ1 雖然有移動，但是不影響Distortion，所以不用計算。

Rate and Distortion Model(11/11) l指的是直方圖中h(i)=0的所有的i，個數一般非常的多，l >> m 。所以Zero point 就是從其中獲取的。 除了這些l，其他的i都可以做為Peak point的候選者。 m：the number of peak and zero bin pairs . Mmax：maximal pair number

Rate and Distortion Optimization using GA (1/3) The solution space size： Chromosome Encoding：

Rate and Distortion Optimization using GA (2/3)

Rate and Distortion Optimization using GA (3/3) Empirical Chromosomes Addition P從peak_set中獲取，對應的Z是與該P最近的Z

Embedding and Extraction Process V. Sachnev, H. J. Kim, J. Nam, S. Suresh, and Y. Q. Shi, “Reversible watermarking algorithm using sorting and prediction,” IEEE Trans.Circuits Syst. Video Technol., vol. 19, no. 7, pp. 989–999, Jul. 2009. D. M. Thodi and J. J. Rodriguez, “Reversible watermarking by prediction-error expansion,” in Proc. IEEE Southwest Symp. Image Anal.Interpretation, Lake Tahoe, CA, 2004, pp. 21–25.

Experimental Results(1/5) Empirical Chromosomes Addition

Experimental Results(2/5)

Experimental Results(3/5)

Experimental Results(4/5)

Experimental Results(5/5)

Comments GA may not find out a global optimal solution Suitable for small payload.