一種基于非重疊正方形NAM的灰度圖像表示方法

賀杰 郭慧 何高明

【摘要】針對三角形子模式的不足，使用正方形作為NAM表示模型的預定義子模式，提出了一種新的灰度圖像表示方法。從單個子模式需記錄的參數(shù)、算法時間復雜度、編碼產(chǎn)生的總數(shù)據(jù)量等方面進行了理論分析，實驗表明：與灰度圖像的TNAMG表示方法和LQT表示方法相比，本文方法能夠顯著減少目標塊記錄的數(shù)量并節(jié)省數(shù)據(jù)存儲空間，是一種高效、緊湊的灰度圖像表示方法。

【關鍵詞】正方形子模式NAM灰度圖像表示方法

一、引言

圖像是人類最直接的、最主要的信息源，隨著互聯(lián)網(wǎng)的發(fā)展，多媒體應用也日益增多，由于圖像和視頻本身的數(shù)據(jù)量非常大，給存儲和傳輸帶來了很多不便，因而如何高效、實時地表示圖像成為了多媒體技術中的一個研究熱點[1，2]。圖像表示方法應能夠有效的節(jié)省存儲空間并具備高效的運算方式，支持圖像壓縮、特征提取、復原等各種處理過程[3]。最早得到普遍應用的二維數(shù)組表示方法難以在節(jié)省空間和加快算法速度方面做出進一步的改進。因此，邊界鏈碼、行程編碼等多種圖像表示方法先后被提出[4-6]。同等條件下與二維數(shù)組表示法相比，這些方法占用的存儲空間更少，但其本質(zhì)特點也使其在支撐某些圖像操作時出現(xiàn)問題[4，5]。如圖像的邊界鏈碼表示難以實現(xiàn)區(qū)域邏輯運算，行程編碼表示則會弱化邊界特征。隨后，依據(jù)圖像自身的二維相關性，人們采用樹形結構實現(xiàn)分層的表示圖像，并給出了一些可行的方法，如四元樹、線性四元樹、DF-expression、S-tree、二元樹及Bincodes等圖像表示方法[6-9]。這類方法顯著減少了冗余，保留了圖像的塊狀紋理特征，而且經(jīng)層次數(shù)據(jù)結構表示后，圖像運算可在“塊-塊”的模式下進行[10]，其過程最終可表征為對樹形數(shù)據(jù)結構的節(jié)點遍歷，使算法的計算總量與具有同一灰度級的圖像塊數(shù)量成線性關系，時間復雜度得到降低，因此能夠有效支撐各類圖像處理過程，提高算法效率。其中，Gargantini提出的線性四元樹（Linear Quadtree，LQT）表示方法[9]是目前得到最為廣泛研究和應用的圖像分層表示方法。

二、基于SNAMG的灰度圖像表示算法描述

灰度圖像中不同像素點可能會有多種灰度值，故其匹配、記錄過程必須將像素和子模式的灰度值納入考慮。因此SNAMG表示方法的原理可表述如下：預定義一個灰度正方形子模式框架，然后使用逆布局算法在給定的灰度圖像模式中提取出不同大小和灰度的正方形子模式，再用這些子模式的記錄組合來表示該給定灰度圖像。

根據(jù)上述所得出的SNAMG表示方法的抽象算法描述如下：

設原始模式為祝，重建后的非失真模式為祝，則SNAMG是由到的一個非失真變換：

祝=W（祝）（1）

其中，W（）是正向變換函數(shù)，或稱為編碼函數(shù)。

正向編碼過程為

三、實驗結果及分析

為了驗證基于SNAMG的灰度圖像表示算法的有效性，本文從實際的角度進行將其與基于TNAMG的灰度圖像表示算法[13]和基于LQT的灰度圖像表示算法[11]進行了比較。圖1是用來測試的4幅大小均為28×28、位深均為8的經(jīng)典灰度圖像，為體現(xiàn)算法在不同情況下的性能，這些圖像的復雜度均不相同，可以間接反映灰度圖像的SNAMG表示算法的適應性。另外，由于主要是和LQT表示方法進行對比，本實驗中計算圖像復雜度的仍然依據(jù)LQT的塊數(shù)來計算的。

對4幅圖像進行仿真編碼的結果，具體數(shù)據(jù)如表1所示，表中的參數(shù)Image：灰度圖像的名稱；Cg：灰度圖像的復雜度；N：子模式或節(jié)點的數(shù)量；濁：壓縮比；鬃LQT_T：LQT與TNAMG的總數(shù)據(jù)量之比；鬃LQT_S：LQT與SNAMG的總數(shù)據(jù)量之比。

從表中Cg的值可以看出，Building的復雜度最低，F(xiàn)lower的居中，F(xiàn)light和Peppers的復雜度最高。表中N的數(shù)值表明SNAMG、TNAMG表示逆布局后的子模式數(shù)量比LQT表示的節(jié)點數(shù)少得多，且作用于不同圖像產(chǎn)生的子模式數(shù)量與圖像復雜度對應，說明SNAMG和TNAMG具有很好的適應性。而且SNAMG的子模式數(shù)量比TNAMG的子模式還要少1056～4693個，故SNAMG在降低目標塊記錄數(shù)量方面要優(yōu)于TNAMG。最后，可通過表

中鬃LQT_T和鬃LQT_S數(shù)據(jù)比較一下SNAMG、TNAMG和LQT

這三種表示方法編碼后的總的數(shù)據(jù)量。對于測試的4幅圖像，LQT的總數(shù)據(jù)量是TNAMG表示的1.758～3.2119倍，是SNAMG表示的2.1102～4.8810倍，即TNAMG、SNAMG的編碼結果占用空間均比LQT少，且SNAMG比TNAMG還能再節(jié)省14.45%～34.20%的存儲空間。這說明 SNAMG對灰度圖像的表示能力總是優(yōu)于TNAMG對灰度圖像的表示能力，且能夠比TNAMG更有效地節(jié)省數(shù)據(jù)存儲空間。實驗數(shù)據(jù)表明：在用于灰度圖像表示時，本文提出的SNAMG表示方法性能優(yōu)于TNAMG表示方法和LQT表示方法，空間緊湊性更好。

四、小結

本文借助于正方形布局問題的思想，提出了基于SNAMG的灰度圖像表示方法，并給出了編碼、解碼算法的具體步驟。并通過使用標準‘Building和‘Peppers等4幅圖像處理領域里慣用的經(jīng)典圖像為典型測試對象進行仿真，實驗結果與理論分析結果一致。因此，灰度圖像的SNAMG表示方法是一種更為高效、緊湊的表示方法，在節(jié)省存儲空間和加快圖像處理操作方面具有較高的實用價值。

參考文獻

[1] W. Liu， W. Zeng， L. Dong. Efficient compression of encrypted grayscale images [J]. IEEE Transactions on Image Processing， 2010， 19（4）： 1097- 1102.

[2] S. Alcaraz-Corona， R.M. Rodriguez-Dagnino. Bi-level image compression estimating the markov order of dependencies [J]. IEEE Journal of Selected Topics in Signal Processing， 2010， 4（3）： 605- 611.

[3] Jie He， Yunping Zheng， Hui Guo. A Square NAM Representation Method for Binary Images [J]. Applied Mechanics and Materials Jounral，2011，（143-144）：755-759.

[4]鄭運平，陳傳波，黃巍等.一種改進的TNAM灰度圖像表示算法研究[J].小型微型計算機系統(tǒng)， 2009， 30（2）： 322-326.

[5]方少紅，鄭運平，陳傳波[J].改進的TNAM二值圖像表示方法.計算機科學， 2010， 37 （4）： 261- 264.