宮海曉，賀 杰，郭 慧

(1.2.3.梧州學院 信息與電子工程學院，廣西 梧州 543002)

?

改進的正方形NAM二值圖像表示方法

宮海曉1，賀 杰2，郭 慧3

(1.2.3.梧州學院 信息與電子工程學院，廣西 梧州 543002)

借助非對稱逆布局思想，提出一種改進的正方形NAM二值圖像表示方法，對其存儲結構、數據量進行了理論分析，同時選取部分常用的二值圖像，對該方法進行了實驗測試。結果表明：與正方形NAM和線性四元樹圖像表示方法相比，該方法有效地降低了圖像的存儲空間、減少了子模式的數據量。

NAM；正方形；線性四元樹；子模式

隨著多媒體技術的快速發(fā)展，越來越多的圖像數據需要計算機進行處理，由于圖像數據量劇增，使得圖像數據的存儲和傳輸面臨極大挑戰(zhàn)。如何高效地表示圖像，降低圖像數據并提高圖像的處理速度成為了圖像處理、模式識別和計算機圖形學等領域中一個非常重要的問題，也是目前最活躍的研究內容之一[1]。目前常用的圖像表示方法是基于分層結構的線性四元樹(LQT)表示方法[2]和基于非對稱逆布局模型(NAM)的表示方法[3]。線性四元樹由于強調圖像分割的對稱性，所以產生的節(jié)點數量較多，在圖像處理效率上難以達到最佳，而陳傳波教授提出的NAM圖像表示方法強調圖像分割的非對稱性，因此在提高圖像的處理速度、降低圖像的存儲空間等方面都取得了顯著的成效。后續(xù)研究者在NAM的思想上，通過選取矩形、三角形等不同的子模式[4-5]，實現了多種圖像表示方法，本文在正方形NAM表示方法(SNAM)的基礎上[6]，對其存儲結構、殘渣模式等方面加以優(yōu)化改進，提出了改進的正方形NAM二值圖像表示方法，即ISNAM。

1算法的改進和描述

1.1算法的改進

雖然SNAM算法已經在理論和實驗方面均已證明優(yōu)于經典的線性四元樹圖像表示方法，但該方法仍然存在進一步優(yōu)化的空間，主要表現在以下三個方面。

1.1.1殘渣模式的處理和優(yōu)化

在SNAM表示方法中，首先對正方形進行逆布局，然后將剩余的線段和孤立點全部歸結為殘渣模式，未對殘渣模式進行二次優(yōu)化處理，因此形成的子模式數量較多。本文將SNAM表示方法中的殘渣模式，即線段和孤立點重新進行逆布局，形成新的等腰直角三角形子模式。

如圖所示，圖1(a)表示的是一幅未經過處理的二值圖像，尺寸為2n×2n(n=3)，圖1(b)表示的是一幅傳統的線性四元樹LQT算法對圖1(a)處理后的表示結果圖，形成的目標子塊總數為27個，圖1(c)是SNAM圖像表示方法對圖1(a)二值圖像的逆布局結果，逆布局形成的子模式數量為12個，圖1(d)改進的ISNAM圖像表示方法對圖1(a)二值圖像的逆布局結果，形成的子模式數量為10個，顯然ISNAM表示方法的子模式數量少于LQT和SNAM表示方法。

圖1 原始圖像及其用不同表示方法的編碼結果

1.1.2等腰直角三角形子模式的設計

在算法的設計中，首先對正方形子模式進行逆布局，對殘渣模式的逆布局是在最后進行，因此形成的等腰直角三角形的腰長均為1，同時根據等腰直角三角形直角頂點的位置，將其子模式分為4類，即左上、左下、右上、右下，如圖2所示。

圖2 等腰直角三角形的類型

1.1.3存儲結構的優(yōu)化

SNAM表示方法對逆布局的每一個正方形子模式和殘渣模式進行了單獨存儲，在存儲時不僅需要記錄每個正方形的左上頂點坐標及邊長，而且還需記錄每條線段的兩個端點坐標和孤立點的坐標，存儲結構設計簡單，因此占用了較大的存儲空間。本文將邊長相同的正方形子模式存儲到指定的隊列，實現了分類存儲，因此在存儲時只需記錄正方形的左上頂點坐標即可，同時將類型相同的等腰直角三角形，也進行了分類存儲，存儲時只需記錄等腰直角三角形子模式的直角頂點坐標。改進的ISNAM表示方法在逆布局后仍然存在線段和孤立點子模式，對孤立點子模式的存儲同SNAM表示方法一樣，但對線段的存儲結構的設計優(yōu)化為將長度相同的線段存儲到指定的隊列，因此只需記錄線段子模式的第一個端點坐標即可。

對于一幅2n×2n(n=3)的二值圖像，傳統的線性四元樹LQT表示方法存儲一個黑色節(jié)點塊占3(n-1)+2位的存儲空間[2]，圖1(b)中目標子塊總數為27個，故原始圖像的LQT表示將占用27×(3(n-1)+2)=27×8=216位的存儲空間。根據文獻[6]分析，存儲一個正方形子模式需要1.5n位的空間，存儲一個線段子模式需要2n位的空間，存儲一個孤立點子模式需要n位的空間，圖1(a)的SNAM表示方法中，存在7個正方形，3條線段，兩個孤立點，因此需占用存儲空間7×1.5n+3×2n+2×n=55.5位。而對存儲結構優(yōu)化改進后的ISNAM表示方法，存在7個正方形，兩個不同類型的等腰直角三角形，一條線段，根據下文分析，存儲一個正方形子模式需要n位的空間，存儲一個等腰直角三角形子模式需要n位的空間，存儲一個線段子模式需要n位的空間，存儲一個孤立點子模式需要n位的空間，因此圖1(b)的ISNAM表示方法，需占用存儲空間7×n+2×n+n=30位的存儲空間，因此ISNAM表示方法有效減少了圖像的存儲空間。

1.2算法的描述

在該方法中，預先定義邊長任意的正方形子模式，但在等腰直角三角形子模式的構成中，由于直角頂點位置的不同，所以定義為左上、左下、右下、右上四種類型。因此子模式的抽象描述為正方形s={square|square=(sp,side)}、等腰直角三角形t={triangle|triangle=(type,tp)}，其中sp和side分別代表正方形左上角起始點的坐標和邊長，type代表等腰直角三角形子模式類型的標示符，tp代表等腰直角三角形的直角端點的坐標，由于等腰直角三角形的四種類型腰長均相同，所以不需要存儲。同時在逆布局圖像時仍然會產生線段和孤立點，具體實現時也必須將它們納入考慮，不能將其當成殘渣模式丟棄，線段的抽象描述為l={segment|segment=(lp,side)}，孤立點的抽象描述為p={point|point=(p)}。以下是ISNAM圖像表示算法的編碼過程：

Input:二值圖像T，大小為2n×2n。

Output:正方形子模式隊列集合V_si、等腰直角三角形子模式集合V_ti、線段子模式集合V_li和孤立點子模式集合V_p，可以抽象描述為V={V_s,V_t,V_l,V_p}。

Step 1.采用正方形的逆布局算法，以形成面積最大的正方形為目標，按照光柵掃描的方式[7]，搜索二值圖像T中未作標記的點，提取出正方形后，在T中將該正方形覆蓋的像素點全部標記。

Step 2.記錄該正方形子模式的邊長和左上角的頂點坐標，將其二維坐標(x,y)通過降維變換為一維坐標sp，根據正方形的邊長，將sp存儲到指定的正方形子模式的集合V_si中，其中i為邊長。

Step 3.繼續(xù)循環(huán)執(zhí)行Step 1到Step 2提取新的正方形，當無法提取正方形時轉到Step 4。

Step 4.采用等腰直角三角形的逆布局算法，以形成等腰直角三角形為目標，搜索二值圖像T中未作標記的點，提取腰長為1的等腰直角三角形，然后在T中將該等腰直角三角形覆蓋的像素點全部標記。

Step 5.記錄該等腰直角三角形子模式的類型和直角頂點坐標，并將其二維坐標(x,y)通過降維變換為一維坐標tp，根據三角形子模式的類型，將tp存儲指定的等腰直角三角形子模式的集合V_ti中，其中i為等腰直角三角形的類型。

Step 6.繼續(xù)循環(huán)執(zhí)行Step 4到Step 5提取新的等腰直角三角形，當無法提取等腰直角三角形時轉到Step 7。

Step 7.以形成最長線段形為目標，按照光柵掃描的方式，搜索二值圖像T中未作標記的點，提取線段子模式，然后在T中將該線段覆蓋的像素點全部標記。

Step 8.記錄該線段子模式的左頂點坐標和長度，將其二維坐標(x,y)降維變換成一維坐標p，根據線段的長度，將p存儲到指定的線段子模式的集合V_li中，其中i為線段長度。

Step 9.繼續(xù)循環(huán)執(zhí)行Step 7到Step 7提取新的線段，當無法提取線段時轉到Step 10。

Step 10.記錄在T中剩余的未做標記的點坐標，即孤立點坐標(x,y)，并將其進行降維變換為ip，最后將ip存儲到孤立點子模式的集合V_p中。

Step 11.輸出T的逆布局編碼隊列集合V={V_si,V_ti,V_li,V_p}。

2算法的理論分析

2.1存儲結構分析

對于一個2n×2n的圖像子模式來說，本文將正方形子模式根據邊長的長度進行了分類存儲，即將相同邊長的正方形存儲到一個隊列中，同時以正方形的邊長長度命名隊列，因此對相同邊長的正方形來說，只需存儲其左上角頂點的坐標即可。在坐標存儲中，一般用K碼的相對值記錄，因此按照K碼的定義，頂點坐標的長度理論值為n位[3]，因此，存儲一個正方形需要n位。

對于等腰直角三角形子模式，同樣根據其直角頂點坐標位置進行分類存儲，即將相同類型的等腰直角三角形存儲到一個隊列中，該隊列以其等腰直角三角形的類型命名，由于等腰直角三角形的腰長均相同，所以腰長不需要存儲，只需存儲其直角頂點坐標即可，因此按照K碼的定義，頂點坐標的長度理論值為n位。因此，存儲一個等腰直角三角形需要n位。

對于剩余的線段和孤立點子模式而言，線段根據長度同樣進行分類存儲，即將相同長度的線段存儲到一個隊列中，該隊列以線段長度命名，所以只需記錄其左邊頂點坐標即可，因此存儲一個線段需要n位，存儲一個孤立點需要n位。

2.2數據量分析

對于給定的一幅大小為2n×2n的二值圖像來說，采用改進的正方形ISNAM圖像表示方法編碼，假設編碼后產生的正方形子模式數量是NS，等腰直角三角形子模式數量是NT，線段數量是NL，孤立點數量是NP，總的數據量是HIS，根據前面章節(jié)的分析，存儲正方形子模式需要n位、等腰直角三角形子模式需要n位、線段子模式需要n位、孤立點子模式需要n位的存儲空間。因此總的數據量為：

HIS=nNS+nNT+nNL+nNP

(1)

若使用線性四元樹編碼，記錄一個節(jié)點需3(n-1)+2位的空間[2]，設編碼后四元樹中目標(黑色)節(jié)點數量是NLQT，總的數據量是HLQT，故有：

HLQT=(3n-1)NLQT

(2)

設φLQT IS為LQT的總數據量與STNAM的總數據量的比值，則有：

(3)

由于線性四元樹是對稱性分割，而NAM圖像表示方法是非對稱性分割，所以LQT表示的節(jié)點數一般大于ISNAM逆布局算法，即NLQT>Ns+Nt+Nl+Np，所以φLQT IS>(3n-1)/n，比如當n=8時，φLQT IS>2.875>1，也就是說，LQT和ISNAM圖像表示在總數據量的比值上達到了2.875倍以上。

3算法的實驗分析

本節(jié)從實驗的角度分析了改進的正方形ISNAM圖像表示算法的相應數據，選取了4副大小為28×28的二值圖像，如圖3所示，該圖像是圖像處理中常用的圖像，且與文獻[6]中所用的圖像一致。

圖3 實驗測試圖像

實驗具體數據如下頁表1所示，其中Image表示圖像的名稱，C表示圖像的復雜度，N表示圖像的節(jié)點數或子模式數，φLQT IS表示線性四元樹與正方形NAM總數據量之比，φLQT IS表示線性四元樹與改進的正方形NAM總數據量之比。

表1 LQT、SNAM和ISNAM算法的性能比較

ImageCNLQTSNAMISNAM?LQT＿S?LQT＿ISBaboon0260117047866883463801342978Boat013138604351529914609452297Lena009816430307723674037659787Flight008505568225313324753762731

從實驗數據分析來看，當圖像復雜度提高時，三種圖像表示方法的子模塊(節(jié)點)數均有所提高，但改進的正方形NAM圖像表示方法在子模式數量上均少于LQT和SNAM表示方法。當圖像復雜度降低時，ISNAM表示方法的子模式數量相比較LQT和ISNAM表示方法明顯減少。同時，從總數據量的比值來看，改進的正方形NAM圖像表示方法也優(yōu)于LQT和SNAM表示方法。

綜上所述，對二值圖像模式而言，無論是從理論分析，還是實驗結果比較，在子模式數量的減少和存儲空間的節(jié)約方面而言，改進的ISNAM圖像表示方法與基于單模式的SNAM及LQT表示方法相比，均占有一定的優(yōu)勢。很顯然，ISNAM是一種性能優(yōu)良的二值圖像表示方法。

4結論

本文以SNAM圖像表示方法為基礎，提出了改進的正方形ISNAM圖像表示方法，該方法將SNAM剩余的殘渣模式重新構成新的等腰直角三角形子模式。在子模式的存儲方面，根據正方形的邊長，等腰直角三角形的類型和線段的邊長對子模式分類存儲。理論和實驗分析表明：改進的正方形ISNAM圖像表示方法具有更少的子模式數，有效地減少了圖像的存儲空間，是一種值得推廣的圖像表示方法。

[1]M.N.Do,M.Vetterli.The eontourlet transform:an effieient direetional multiresolution image represeniation.[J].IEEE Transactions on Image Proeessing,2005,14(12):2091-2106.

[2] W.Wong,F.Y.Shih,T.Su.Thinning algorithtns based on quadtree and oetree represeniations.[J].Information Seiences,2006,176(9):1379-1394.

[3] 陳傳波.非對稱逆布局模式表示方法研究[D].武漢:華中科技大學,2006.

[4] 鄭運平,陳傳波.三角形和矩形NAM的二值圖像表示方法[J].小型微型計算機系統,2009,30(8):1680-1684.

[5] 鄭運平,陳傳波,黃巍.一種新的基于TNAM的二值圖像表示方法[J].計算機科學,2008,35(11):220-224.

[6] 賀杰,張顯全,郭慧.一種基于正方形NAM的二值圖像表示方法[J].制造業(yè)自動化,2011,33(3):213-220.

[7] 鄭運平,陳傳波.基于光柵掃描的NAM優(yōu)化策略[J].華中科技大學學報：自然科學版，2008,36(8):1-4.

(責任編輯：覃華巧)

Representation Method for Binary Image UsingImproved NAM with Square

Gong Haixiao1, He Jie2, Guo Hui3

(1.2.3. College of Information and Electronic Engineering, Wuzhou University, Wuzhou 543002, China)

A representation method for binary image using improved NAM with square, which is based on the concept of non-symmetry anti-packing theory, is proposed in this paper. With the help of this method, a theoretical analysis has been conducted on its storage structure and data amount. Besides, some general binary images have been selected so as to test the method. The results show that, compared with the image representation method using NAM with square or linear quadtree, the method can decrease the image storage space effectively as well as reduce the data amount of subpatterns.

NAM; Square; Linear quadtree; Subpattern

2016-03-25

廣西自然科學基金項目(2013GXNSFBA019275，2013GXNSFBA019276)

TP391

A

1673-8535(2016)03-0001-06

宮海曉(1982-)，男，山西昔陽人，梧州學院信息與電子工程學院講師，研究方向：數字圖像表示、模式識別。

賀杰(1982-)，男，湖南益陽人，梧州學院信息與電子工程學院教研室主任，副教授，研究方向：模式識別、數字圖像處理。

郭慧(1981-)，女，廣西梧州人，梧州學院信息與電子工程學院副院長，副教授，研究方向：圖像壓縮、模式識別。