[發(fā)明專利]一種基于局部平衡三叉樹理論的快速圖像置亂方法

有效

• 申請?zhí)枺?/td>: 201210246848.3
• 申請日: 2012-07-17
• 公開（公告）號: CN102843493A
• 公開（公告）日: 2012-12-26
• 發(fā)明（設(shè)計）人: 范鐵生;張忠清;朱紅寧;王青松
• 申請（專利權(quán)）人: 遼寧大學(xué)
• 主分類號: H04N1/44
• 分類號: H04N1/44;G06T1/00
• 代理公司: 沈陽杰克知識產(chǎn)權(quán)代理有限公司 21207
• 代理人: 羅瑩

技術(shù)領(lǐng)域

本發(fā)明涉及一種局部平衡三叉樹的快速圖像置亂方法，是一種信息隱藏預(yù)處理方法和圖像加密手段，屬于數(shù)字圖像處理領(lǐng)域。

背景技術(shù)

隨著圖像在社會生活各個方面的廣泛應(yīng)用，對圖像傳輸?shù)陌踩砸笤絹碓礁撸畔㈦[藏和偽裝技術(shù)是解決其安全性的主要手段，而數(shù)字圖像置亂技術(shù)是一種有效的信息隱藏預(yù)處理方法和圖像加密手段，置亂技術(shù)由此得到了較大的發(fā)展。其原理是按照一定的變換規(guī)則，將一幅給定的圖像在空間域或頻域進(jìn)行某種變換，使得變換后的圖像看似雜亂無章且毫無意義，從而達(dá)到圖像信息隱藏的目的。目前存在的置亂技術(shù)Arnold變換、Hilbert曲線、Fibonacci以及P-Fibonacci?變換等方法，主要大都存在取模運(yùn)算，計算量比較大，置亂較為費(fèi)時，置亂速度不太理想，效率比較低；而且它們主要用于方陣圖像，置亂的適用性不好；基于抽樣技術(shù)的置亂方法，具有抽樣周期，抽樣周期較短，但置亂效果不甚理想，置亂圖像能看到原始圖像的一些信息。

目前已有的置亂技術(shù)頗多，但存在的問題也不少，而且基于數(shù)據(jù)結(jié)構(gòu)中樹結(jié)構(gòu)的方法甚少，因此研究一種好的基于樹結(jié)構(gòu)的置亂方法目前頗具有挑戰(zhàn)性。

并且已存在的置亂方法大都是用矩陣變換、取模運(yùn)算、曲線掃描等方法，這些方法都較為費(fèi)時，而樹結(jié)構(gòu)的遍歷簡單且速度快，適用性很好。因此，研究一種基于樹結(jié)構(gòu)的快速置亂方法有較大的意義。

發(fā)明內(nèi)容

本發(fā)明的目的是提出一種局部平衡三叉樹理論的快速圖像置亂方法，該方法簡單易行，置亂穩(wěn)定且能快速達(dá)到理想的置亂效果，通用性好，并能抵抗一定的攻擊，可以很好的用于信息隱藏的預(yù)處理和圖像加密，而且可以滿足數(shù)字圖像加密和隱藏的魯棒性要求。

為了實現(xiàn)上述目的，本發(fā)明的目的是通過下述技術(shù)方案實現(xiàn)的：一種基于局部平衡三叉樹理論的快速圖像置亂方法，包括圖像正置亂與逆置亂兩個過程；

所述的圖像正置亂的方法：設(shè)原始圖像IMAGE，大小為M×N像素，將原始圖像IMAGE元素集合作為一棵局部平衡三叉樹，按照先遍歷根結(jié)點(diǎn)再按層次遍歷中左右子樹的遍歷方法對該局部平衡三叉樹進(jìn)行遍歷，共遍歷cycle次，將每次遍歷得到的一維數(shù)組fig轉(zhuǎn)換成與原始圖像IMAGE大小一樣的M????????????????????????????????????????????????N像素二維結(jié)構(gòu)，結(jié)果存儲到Fig中，然后將Fig賦值給原始圖像IMAGE，遍歷次數(shù)達(dá)到cycle次時，就得到了置亂后的圖像FIG；所述的遍歷次數(shù)cycle即為置亂密鑰；

所述的局部平衡三叉樹為：根有左、中、右三棵子樹，根的左右子樹各僅有一棵子樹，根的中子樹有左中右三棵子樹，依次類推，即樹的每一層只有最中間的中子樹有左中右三個孩子結(jié)點(diǎn)，中子樹兩邊的子樹都只有一棵子樹，且每一層的左中右子樹高度差的絕對值不超過1，如圖1（a）是一棵局部平衡三叉樹；

所述的局部平衡三叉樹的遍歷方法是：先遍歷根結(jié)點(diǎn)，然后遍歷每一層的所有結(jié)點(diǎn)，且每一層先遍歷最中間的結(jié)點(diǎn)，然后遍歷最外邊左右結(jié)點(diǎn)，接著遍歷次外邊的左右結(jié)點(diǎn)，直到該層的左右結(jié)點(diǎn)遍歷結(jié)束。

所述圖像逆置亂的方法：根據(jù)前述方法得到的置亂圖像FIG，大小為MN像素，將置亂圖像FIG轉(zhuǎn)換成一維數(shù)組結(jié)構(gòu)，并將該數(shù)組保存在out中；定義一個與置亂圖像FIG大小相同的二維數(shù)組Fig，用于存放逆遍歷置亂圖像的元素，逆遍歷次數(shù)cycle與正置亂遍歷次數(shù)相同；將二維數(shù)組Fig看作局部平衡三叉樹結(jié)構(gòu)，遍歷out中的元素按照正置亂方法的逆過程依次放到Fig中的相應(yīng)位置；將二維數(shù)組Fig轉(zhuǎn)換為一維結(jié)構(gòu)，保存到out中；最后將out中數(shù)據(jù)轉(zhuǎn)換成大小為MN像素的二維結(jié)構(gòu)Out，Out輸出還原圖像OUT，完成圖像逆置亂。

下面對本發(fā)明基于的三叉樹、局部平衡三叉樹等理論進(jìn)行說明：

1）三叉樹

①數(shù)學(xué)模型：三叉樹是一種數(shù)據(jù)結(jié)，three-?tree~?(D，R)。其中：D是具有相同特性的數(shù)據(jù)元素的集合，若D=Ф，則R=Ф，則three-tree為空的三叉樹；若D≠Ф，則R是D上某個二元關(guān)系H的集合，即R={H}，且

（1）D中存在唯一的稱為根的元素r，它在關(guān)系H下無前驅(qū)；

（2）若D-{r}≠Ф，則D-{r}={D₁,D₂,D₃},D₁|D₂=Ф，D₂|D₃=Ф；