TSNAM彩色圖像的格雷碼表示

鄭運平，張佳婧

(華南理工大學計算機科學與工程學院，廣東 廣州 510006)

布局問題包含了種類繁多的若干類問題如三角形布局問題、矩形布局問題和裝箱問題等，這些問題在許多領域里能夠得到廣泛的應用，有著巨大的理論價值和實際意義［1-2］.在Internet已成為最主要的信息傳輸途徑的今天，由于圖像信息所具有的大量性，其快速、實時傳輸的要求得不到滿足，已成為制約Internet發展的一個難題.許多實際的應用由于大量的圖像信息得不到快速傳輸而使系統的實時效果不是很理想.因此圖像表示方法的研究就變得非常重要，它是目前最活躍的研究領域之一［3-5］.四元樹(linear quadtree，LQT)表示是研究得最早、最多的一種圖像表示方法［6］.為了進一步減少存儲空間，Gargantini消除了指針方案，提出了線性四元樹表示方法［7］.一般情況下，LQT表示方法可節省66%的存儲空間;特殊情況下，可節省高于90%的存儲空間.借助于矩形布局問題的思想，通過使用位平面分解方法，文獻［8］提出了一種基于非對稱逆布局的模式表示模型(non-symmetry and anti-packing pattern representation model，NAM)的彩色圖像表示方法，這是彩色圖像的間接矩形NAM表示方法.隨后，文獻［9］提出了彩色圖像的直接矩形NAM表示方法.文獻［8-9］中用到的子模式均為矩形，對于具有塊狀性的圖像具有較好的表示效果.對于塊狀性不好或者沒有明顯塊狀性的圖像，三角形子模式是一個很好的選擇，鑒于此，筆者在文獻［10］中曾提出了灰度圖像的直接三角形NAM表示方法，而在文獻［11］中提出了灰度圖像的間接三角形NAM表示方法(IITNAM).最近，借助三角形和正方形布局問題的思想，通過在IITNAM表示方法中增加正方形子模式，文獻［12］提出了一種稱為TSNAM的圖像表示方法，并且也使用了BPD方法.盡管BPD方法是一種有效降低圖像復雜度的方法，但采用這種方法來分解位平面存在一個缺點，即像素點灰度值的微小變化會對位平面的復雜度產生較明顯的影響.例如，當空間相鄰的2個像素的灰度值分別為127=(01111111)2和128=(10000000)2時，圖像的每個位平面在這個位置處都會有從0到1(或從1到0)的傳輸，而由法國工程師 J.M.E.Baudot于1880年發明的格雷碼(Gray code)則沒有這一缺點，格雷碼在任意2個相鄰的數之間轉換時，只有一個數位發生變，它大大地減少了由一個狀態到下一個狀態時邏輯的混淆.

因此，為了進一步提高TSNAM的表示效率，同時也為了減小像素點灰度值的微小變化會對位平面的復雜度產生較明顯的影響，本文將格雷碼和BPD方法應用到彩色圖像的TSNAM表示方法中，提出了一種基于格雷碼的TSNAM彩色圖像表示方法(GTSNAM).理論分析和實驗結果表明了本文提出的GTSNAM表示方法的正確性和有效性.

1 彩色圖像的GTSNAM方法

1.1 TSNAM方法的思想

在TSNAM表示方法中，預先定義的子模式集合是三角形和正方形.其中，將三角形子模式分成了4類:上三角形、下三角形、對稱上三角形和對稱下三角形.這樣，對于任何一個三角形子模式，不需要存儲3個頂點的坐標，而只要存儲斜邊的2個端點和一個用于標識三角形子模式類型的標識符(比如上三角形、下三角形、對稱上三角形和對稱下三角形分別用“0”、“1”、“2”和“3”這4個數來標識)即可.相反，以斜邊的2個端點和三角形類型的標識符，也可以非常簡單地解碼出三角形子模式.

彩色圖像的TSNAM表示方法的主要思想是:對一幅彩色圖像，首先獲取其3幅由r、g、b顏色分量組成的灰度圖像，然后通過BPD方法對每幅灰度圖像進行分解，獲得相應的位平面二值圖像，最后用三角形和正方形子模式對所有二值圖像進行逆布局.事實上，TSNAM表示方法對IITNAM表示方法的改進主要體現在TSNAM表示方法中新增了一個正方形子模式.

1.2 彩色圖像的GTSNAM算法描述

設已經布局好的彩色圖像模式為C，位深為m，大小為2n×2n×3，其分解后的3幅灰度圖像模式為G［1］、G［2］和G［3］，大小均為 2n×2n.為方便起見，假定“0”為“black”，即黑色，表示區域，“1”為“white”，即白色，表示背景點.本算法只需記錄“black”像素點.GTSNAM表示算法中被逆布局的子模式對象是任意大小的三角形和正方形，其中三角形子模式t={triangle|triangle=(flag，point1_hyp，point2_hyp)}，flag占2 bit，flag=0時表示上三角形，flag=1時表示下三角形，flag=2時表示對稱上三角形，flag=4時表示對稱下三角形;point1_hyp和point2_hyp表示斜邊的2個端點;且正方形子模式s={square|square=(sp，edge)}中，sp和 edge分別代表正方形左上角的坐標及邊長.

以下給出了GTSNAM表示算法的具體步驟:

輸入:一幅2n×2n×3的彩色圖像模式C以及其位深m.

輸出:Q={Qt，Qs，Ql，Qp}，Qt={Qt0，Qt1，…，Qt3m－1}，Qs={Qs0，Qs1，…，Qs3m－1}，Ql={Ql0，Ql1，…，Ql3m－1}和Qp={Qp0，Qp1，…，Qp3m－1}.其中Qti、Qsi、Qli和Qpi(0≤i≤3m－ 1)分別表示第i個格雷碼位面圖CPi的三角形、正方形、線段和孤立點的編碼結果.

1)對于一個給定的大小為2n×2n×3的彩色圖像C，分別取得由它的r、g、b顏色分量組成大小為2n×2n的灰度圖像G［1］、G［2］和G［3］，并把三角形、正方形、線段和孤立點的計數變量tn、sn、ln和pn均賦值為0.

2)用灰度圖像的BPD方法依次將3幅灰度圖像G［1］、G［2］和G［3］各自分解為m幅二值圖像BPi(0≤i≤m－1)、BPi(m≤i≤2m－1)和 BPi(2m≤i≤3m－1).

3)當k=1，2，3 時，根據式(1)，依次計算出每m幅二值位面圖 BPi(0≤i≤m－1)、BPi(m≤i≤2m－1)和BPi(2m≤i≤3m－1)所分別對應的m幅格雷碼位面圖CPi(0≤i≤m－1)，CPi(m≤i≤2m－1)和 CPi(2m≤i≤3m－1)，并令j=0.

4)從CPj的第1個入口開始，首先用光柵掃描的方法確定一個未被標識的起始點(x，y)，再根據三角形子模式的匹配(逆布局)策略來盡可能地形成最大的三角形子模式.

5)如果以(x，y)為端點找到的最大三角形子模式為上三角形(或對稱上三角形)，則將flag賦為0(或2)，三角形的計數變量tn的值加1，且將這個三角形子模式作標識.

6)記錄斜邊端點的2個坐標(x1，y1)和(x2，y2)，然后對斜邊的2個端點作K碼降維變換，即point1_hyp←K(x1，y1)，point2_hyp←K(x2，y2)，最后將flag、point1_hyp、point2_hyp這3個變量存儲到隊列Qtj中，即有Qtj{tn}←{flag，point1_hyp，point2_hyp}.

7)如果以(x，y)為端點找到的最大三角形子模式為下三角形(或對稱下三角形)，則將flag賦為1(或3)，三角形的計數變量tn的值加1，且將這個三角形子模式作標識，記錄斜邊端點的2個坐標(x1，y1)和(x2，y2)，然后對斜邊的2個端點作K碼降維變換，即:point1_hyp←K(x1，y1)，point2_hyp←K(x2，y2)，最后將 flag、point1_hyp、point2_hyp 這 3 個變量存儲到隊列Qtj中，即有Qtj{tn}←{flag，point1_hyp，point2_hyp}.

8)如果以(x，y)為端點找到的最大上三角形(或對稱上三角形)子模式的面積和最大下三角形(或對稱下三角形)子模式的面積相等，且這2個三角形能構成一個正方形，則將tn的值減2，同時將sn的值加1.

9)記錄此最大正方形子模式的2個參數，即起始點坐標(x，y)和邊長edge;然后對起始點坐標(x，y)作K碼降維變換，即 sp←K(x，y);最后將sp和edge這2個變量存儲到隊列Qsj中，即有Qsj{sn}←{sp，edge}，并將此正方形在CPj中作標識.

10)循環執行4)～9)，直到不能形成新的三角形和正方形子模式為止.

11)按光柵掃描的順序，從標記過的CPj的第1個入口開始，首先確定1個未被標記的點，再根據子模式的匹配(逆布局)算法來盡可能地形成最長的線段，如果能形成線段，則將線段的計數變量ln的值加1，記錄線段端點的2個坐標(x1，y1)和(x2，y2)，然后對線段的2個端點作K碼降維變換，即l1←K(x1，y1)，l2←K(x2，y2).最后將l1和l2這 2 個變量存儲到隊列Qlj中，即有Qlj{ln}={l1，l2}，且將存儲過的此線段在CPj中作標識.否則，說明只能形成孤立點，執行12).

12)直接存儲孤立點的坐標(x，y)，將孤立點的計數變量pn的值加1，然后將這個點作K碼降維變換，即p←K(x，y).最后將p這個變量存儲到隊列Qpj中，即有Qpj{pn}={p}，并將此點在CPj中作標識.

13)循環執行11)～12)，直到不能形成新的線段和孤立點為止.

14)j=j+1.若j≤3m－1，則執行4).

15)輸出編碼結果Q={Qt，Qs，Ql，Qp}，其中Qt= {Qt0，Qt1，…，Qt3m－1}，Qs= {Qs0，Qs1，…，Qs3m－1}，Ql={Ql0，Ql1，…，Ql3m－1}和Qp= {Qp0，Qp1，…，Qp3m－1}.

1.3 算法復雜度分析

假定彩色圖像C中元素的總數為N，多子模式的類型數為n，位深為m.由于采用了BPD方法，一幅彩色圖像被分解為3m幅二值圖像來處理，因此，對GTSNAM算法來說，編碼所需的時間正比于mnNτ，其中τ表示圖像中每個像素平均分割的次數，且τ的上限為O(lbN).因此，在最壞情況，編碼算法時間復雜度為O(mnN×lbN).

在空間開銷方面，編碼算法除3m幅二值圖像矩陣外，只增加了為數非常少的中間變量，因而其空間復雜度與3m幅二值圖像的大小成正比，即為O(mN).

2 GTSNAM表示的存儲結構和數據量

2.1 GTSNAM表示的存儲結構分析

從GTSNAM表示算法不難看出，彩色圖像模式的編碼結果為隊列集合Q={Qt，Qs，Ql，Qp}，Qt={Qt0，Qt1，…，Qt3m－1}，Qs={Qs0，Qs1，…，Qs3m－1}，Ql={Ql0，Ql1，…，Ql3m－1}和Qp={Qp0，Qp1，…，Qp3m－1}.其中Qti、Qsi、Qli和Qpi(0≤i≤3m－ 1)分別表示第i個格雷碼位面圖CPi的三角形、正方形、線段和孤立點的編碼結果.Qti所存儲的每一條記錄均為一個三角形子模式，且有3個參數，即t={triangle|triangle=(flag，point1_hyp，point2_hyp)};Qsi所存儲的每一條記錄均為一個正方形子模式，且有2個參數，即s={square|square=(sp，edge)}.因此，三角形和正方形子模式的存儲結構分別如圖1和圖2所示.

圖1 三角形子模式的存儲結構Fig.1 Storage structure of a triangle subpattern

圖2 正方形子模式的存儲結構Fig.2 Storage structure of a square subpattern

就正方形子模式而言，設給定的彩色圖像模式C大小為2n×2n×3，從文獻［12］的分析可知:sp即為一個坐標對(x，y)，x和y的二進制碼長度都為n.具體存儲記錄用K碼表示.K用相對值來記錄，本次記錄的K域用本次K碼減去上一個K碼的差值來記錄，即 ΔK=Ki－Ki－1.在統計意義下其長度為n，在實際情況下，如果ΔK的長度確實超過了n，則可以將該塊拆分為2個塊，用2個記錄來表示.子模式的表示只有1個值，即邊長edge.按照K的定義，edge的最大長度為n.因此，存儲一個正方形子模式長度為2n.

通過類似的分析，易知存儲一個三角形、線段和孤立點記錄長度分別為2n+2、2n和nbit.

2.2 GTSNAM表示的數據量分析

設彩色圖像模式C的大小為2n×2n×3，位深為m，經彩色圖像的BPD后，可以將其分解為3幅大小為2n×2n的灰度圖像模式或者3m幅大小為2n×2n的二值圖像模式.令第i個色彩分量的第j個格雷碼位面圖逆布局后的三角形、正方形、線段、孤立點的子模式數分別為Mt(i，j)、Ms(i，j)、Ml(i，j)和Mp(i，j)，其中 1≤i≤3，且 0≤j≤m－1.

就GTSNAM表示方法而言，存儲一個三角形、正方形、線段和孤立點記錄分別占2n+2、2n、2n和n.因此，C用GTSNAM表示方法逆布局后的3m幅格雷碼位面圖的總數據量TGTSNAM為

對于LQT表示方法來說，存貯一個節點占3n－1+m［10］，設NLQT(i)表示第i個色彩分量，用 LQT 表示的總節點數，則LQT的總數據量TLQT為

令β為LQT的總數據量與GTSNAM的總數據量的比值，則有

通過β這一比值，可以比較GTSNAM相對于LQT的優劣.由于LQT表示是對稱分割，分割方法受到很大限制，而GTSNAM表示是非對稱分割，其分割方法更為靈活，且其目的是產生盡可能少的子模式數，因此，

因此β＞(3n－1+m)/(2n+2)＞1.比如在實驗中，當n=9，m=8 時，從理論上來說，β ＞1.7 ＞1.

綜上所述，理論分析表明，對彩色圖像模式而言，與經典的LQT表示方法相比，GTSNAM表示方法能夠更有效地減少數據存儲空間.

3 實驗與分析

為了驗證彩色圖像的GTSNAM表示方法的理論結果，本節從實驗的角度來說明其相對于無格雷碼的TSNAM表示方法和經典的LQT表示方法的明顯優勢.實驗中機器配置為:CPU為Celeron(R)2.4 GHz，內存為 Kingston DDR 2GB，OS 為 MS-Windows XP Service Pack 2.編程環境為 Matlab 7.0.圖3 是實驗中用來測試的4幅彩色圖像，其中圖3(a)、(b)是2幅機器人圖像，圖3(c)、(d)是2幅圖像處理領域里慣用的標準圖像“Flight”和“Lena”，且這些圖像的分辨率參數n=9，即29×29×3的彩色圖像模式，位深m=8，即28=256級.

圖3 4幅彩色圖像Fig.3 Four color images

通過編程，分別實現了彩色圖像的GTSNAM、TSNAM、及LQT表示算法，并對這3種算法的實驗結果進行了比較，相應的比較數據如表1所示，其中:N為子模式或節點個數，TSNAM為無格雷碼的TSNAM表示，GTSNAM為基于格雷碼的TSNAM表示，LQT為線性四元樹表示，δ為TSNAM與GTSNAM的子模式數之差，α為LQT與TSNAM的總數據量之比，β為LQT與GTSNAM的總數據量之比.圖4給出了LQT、TSNAM和GTSNAM表示方法的子模式數或結點數的對比.

圖4 LQT、TSNAM和GTSNAM的子模式數或節點數的對比Fig.4 Contrast of the subpattern or node number among the LQT，TSNAM，and GTSNAM

表1 LQT、TSNAM和GTSNAM的性能比較Table 1 Performance comparison among the LQT，TSNAM，and GTSNAM

從圖4中實驗數據N來看，TSNAM和GTSNAM在數據量方面的效果均是非常明顯的，其子模式數均小于LQT方法的節點數.而且從表1中δ的值可知，GTSNAM的子模式數比TSNAM的子模式還要少98 661～129 412個，同時，從表1中N的值不難算出，在子模式數上 GTSNAM比TSNAM下降了16.71% ～25.48%，效果是非常顯著的.因此，與LQT和TSNAM方法相比，GTSNAM方法能夠更有效地減少子模式的數量.而且，從β值不難看出，對于給定的4幅圖像而言，LQT的總數據量是GTSNAM的2.32～3.35倍，顯然，這些圖像均證實了理論分析的結果，即當n=9，m=8 時，β ＞1.7 ＞1.并且從表1也不難看出，β總是大于α，這表明，在數據存儲表示方面，GTSNAM能夠比LQT和TSNAM方法更有效地減少數據存儲空間.

因此，與LQT和TSNAM表示方法相比，GTSNAM方法能夠更有效地減少子模式數(節點數)和數據存儲空間.

4 結束語

位平面分解方法是一種有效降低圖像復雜度的方法.為了進一步提高TSNAM的表示效率，同時也為了減小像素點灰度值的微小變化會對位平面的復雜度產生較明顯的影響，本文將格雷碼和位平面分解方法應用到彩色圖像的TSNAM表示方法中，提出了一種基于格雷碼的TSNAM彩色圖像表示方法(GTSNAM).給出了GTSNAM算法的形式化描述，并對其存儲結構、總數據量和時空復雜性進行了詳細的分析.理論分析和實驗結果表明，與最新提出的TSNAM表示方法和經典的LQT表示方法相比，GTSNAM表示方法具有更少的子模式數(或節點數)，能夠更有效地減少數據存儲空間，因而是一種有效的彩色圖像表示方法.

［1］CHEN Chuanbo，HE Dahua.Heuristic method for solving triangle packing problem［J］.Journal of Zhejiang University:Science，2005，6(6):565-570.

［2］CHEN T G，RYCKELYNCK P.Improved dense packings of congruent squares in a square［J］.Discrete Comput Geom，2005，34(1):97-109.

［3］DAI D，YANG W.Satellite image classification via two-layer sparse coding with biased image representation［J］.IEEE Geoscience and Remote Sensing Letters，2011，8(1):173-176.

［4］ZHENG Yunping，SAREM M.A fast algorithm for computing moments of gray images based on NAM and extended shading approach［J］.Frontiers of Computer Science in China，2011，5(1):57-65.

［5］YAP P，JIANG X，KOT A C.Two-dimensional polar harmonic transforms for invariant image representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(7):1259-1270.

［6］KLINGER A.Data structure and pattern recognition［C］//Proc of First International Joint Conference on Pattern Recognition.Washington DC，USA，1973:497-498.

［7］GARGANTINI I.An effective way to represent quadtrees［J］.Communications of the ACM，1982，25(12):905-910.

［8］鄭運平，陳傳波.一種基于非對稱逆布局模型的彩色圖像表示方法［J］.軟件學報，2007，18(11):2932-2941.ZHENG Yunping，CHEN Chuanbo.A color image representation method based on non-symmetry and anti-packing model［J］.Journal of Software，2007，18(11):2932-2941.

［9］CHEN C B，ZHENG Y P，SAREM M.A direct non-symmetry and anti-packing model for color image［C］//Proc of the 4rd International Conference on Natural Computation and the 5th International Conference on Fuzzy Systems and Knowledge Discovery.Los Alamitos，USA，2008:347-351.

［10］ZHENG Y P，CHEN C B，SAREM M.A novel algorithm for triangle non-symmetry and anti-packing pattern representation model of gray images［C］//Proc of the 3rd International Conference on Intelligent Computing.Berlin，Germany，2007:832-841.

［11］ZHENG Y P，GUO X.An improved indirect triangle nonsymmetry and anti-packing model for gray image representation［C］//Proc of the 2011 International Conference on Multimedia and Signal Processing.Los Alamitos，USA，2011:117-121.

［12］ZHENG Y P，LI Z J，SAREM M，et al.A new IITNAM representation method of gray images［C］//Proc of the 8th International Conference on Fuzzy Systems and Knowledge Discovery.Los Alamitos，USA，2011:1897-1901.