Finding optimal least-significant-bit substitution in image hiding by dynamic programming strategy

報告論文：Chang, C. C., Hsiao, J. Y., & Chan, C. S. (2003). Finding optimal least-significant-bit substitution in image hiding by dynamic programming strategy. Pattern Recognition, 36(7), 1583-1595.

這篇論文，在資訊隱藏中算比較好入手的，但當時還是花了不少時間整理，文末會附上報告PPT

首先，在進入作者的方法前，先談談什麼是資訊隱藏(data hiding in image)，如果今天有個恐怖組織要傳遞一張地圖，他要怎麼傳遞才不會被駭客竊取，或是竊取後駭客也看不出這是張機密地圖？只要把這張機密地圖藏到一張風景照底下就好啦~

所以在論文中，我們把要藏的圖片稱作secret image，作為呼巄人的風景較稱作host image，藏好的圖片稱作stego image(secret 已經藏在 host底下)，但stego image要檔案大小不變大的情況下，一定會產生失真率，所以有幾篇論文就在開始研究如何降低stego image的失真率，而且計算時間不能太長，底下來介紹三種方法

• exhaustive least-significant-bit substitution scheme → 花費很大的計算時間
• genetic algorithm →僅能找到"近似"最佳解，計算時間縮小一點
• the dynamic programming strategy  → 最少的計算時間，且找到最佳解 (本篇論文提出的方法)

在介紹上面三種方法之前，先來談談Least-significant-bit substitution

Least-significant-bit substitution

在電腦中，每一個像素(pixel)都是由RGB(red,green,blue)所組成，各占8bits，讓我們來看看如果拋棄幾個8bit中的後面幾個bit會發生什麼事

上面那張圖就可以發現，如果將R後四個bit給刪除，其實沒仔細看是看不太出來的，而刪除後面比較不重要的bit的方法稱為simple LSB (Least Significant Bit,最低有效位元)，用在灰階圖上亦同

LSB的取代法中，我們先準備兩張圖片(secret image and host image)，secret image的大小要比host image 還要小喔~

假如說secret image是256*512，host image 512*512，代表說host image後面4個bits (k = 4)要被取代

簡單來說，就是secret image的失真率最後會是0，我們要把她所有的bit全部藏在host image，所以host image要夠大，才可以有足後的LSB bit可以藏secret image

上面這張圖很清楚地介紹LSB的做法，但是這種做法，其實得到的圖片失真度挺大的，因此我們接下來看看改善的Exhaustive LSB substitution

Exhaustive LSB substitution

在上圖中，橘色框框的部分就是LSB substitution 的部分，那紅色框框的部分就是 Exhaustive LSB substitution 新增加的兩的步驟

第一個部分就是【Positions Transform】

會有個一對一的映射函數f(x)，f(x)和輸入的變數x的結果都是一對一，一個x只會對應到唯一的f(x)，f(x)也只會對應到唯一的x，而在f(x)的公式中，要求k1和N要互值，第二個式子是論文中給的範例，這個部分主要目的是加密，把secret image的位置給打亂，傳送者和接收者有唯一的金鑰(k0、k1)，要同時擁有這兩把key才可以解碼出secret image

第二部分是【Substitution Matrices】

上面是一個Substitution Matrices的範例，假如說M[ i ][ j ] = 1，代表S"中所有數字 i 都要替換成數字 j  ，就是一個告訴你數字要替換成什麼的矩陣

上面的R是我們S要取代掉的東西，從這邊我們就會發現，S'''和R之間的差異比S"的差異還小，所以取代掉後得到的stego image失真率也會比較低

上面兩個步驟就是Exhaustive LSB substitution的核心，這個方法的缺點只在於計算時間過大，但可以求出取代最佳解，計算時間過大的原因是因為他找取代矩陣的方法是使用窮舉法

所以接下來就有基因演算法的改良版

The method of genetic algorithm

上圖紫色框框的部分是剛剛Exhaustive LSB substitution  的position transform，橘色圈圈的部分就是基因演算法的核心

基因演算法其實是利用reproduction, crossover and mutation來找到最適合的substitution matrix，和Exhaustive LSB substitution的差別就在於，一個是用窮舉法，一個是用基因演算法，前者找到最佳解，後者找到近似最佳解

The dynamic programming strategy 

現在來到論文所提出的方法了，先來講講DP和前面兩種方法的差別，她可以找到最佳解，也是花費最少時間的方法

橘色圈圈的部分就是DP在做的事情，也是在position transform後，他也是找一個最佳的 substitution matrix ，只是他重新定義了這個matrix，並稱為：Square Differences  Matrix

這裡比較特別的是 M[ i ][ j ]代表的是，數字 i 變成數字 j 所需要的代價 

舉個例子，我們看到S"[0][0] 數字 3 ，他對應到的R[ 0 ][0]數字3，如果今天S[0][0]要替換成數字 1 所會產生的誤差值/代價就會是 (1-R[0][0]) ^2 =  (1-3)^2 = 4，所以我們可以看到M[3][1] = 4

其他數字也可以依此類推的算出來 :)

接著是 Dynamic Programming Strategy，這部分就是找出最佳解，Square Differences  Matrix中要找到最佳解，每個數字都只能對應到某個數字假如說我今天1換成3，那2就不可以再換成3，2只能換成 0 、1、2，而DP就是根據他的代價找出代價最少的替換法

這張圖看不懂沒關係，我有寫個城市碼來實作，以下圖為例，根據Square Differences  Matrix所找到的所有取代路徑，代價最小的就是0123換成1023(BACD)

附上這次報告準備的PPT，如果有任何問題可以在底下留言 :)