基于NAM的圖像集合運算算法及其試驗研究

伍 鵬 (長江大學電子信息學院，湖北 荊州 434023)

陳傳波，鄭運平 (華中科技大學計算機科學與技術學院, 湖北 武漢 430074)

基于NAM的圖像集合運算算法及其試驗研究

伍 鵬 (長江大學電子信息學院，湖北 荊州 434023)

陳傳波，鄭運平 (華中科技大學計算機科學與技術學院, 湖北 武漢 430074)

非對稱逆布局圖像表示模型是一種新的圖像表示方法，由于采用了預定義子模式和非對稱的分割方法，獲得了較高的表示效率。在NAM基礎上，提出了一種實現(xiàn)快速的圖像集合運算的新方法，即在導航數(shù)組輔助下的分裂組合法，實現(xiàn)了基于NAM的圖像集合運算算法，并討論了算法的時空復雜度。試驗結果表明，基于NAM的集合運算算法的執(zhí)行速度是基于緊湊四元樹集合運算算法執(zhí)行速度的1.291到5.368倍。

圖像表示；非對稱逆布局模式表示模型；圖像集合運算；分裂組合法；緊湊四元樹

圖像分層表示是數(shù)字圖像編碼中的一個熱點問題，各種編碼方法層出不窮，但不外乎要解決2個方面的問題：一是為了節(jié)省存儲空間，實現(xiàn)更高的壓縮率；另一個是為了提高運算的速度，實現(xiàn)快速的圖像操作。在眾多的表示方法中，四元樹表示是研究得最早的、也是研究得最多的一種分層表示形式。早期的四元樹[1]表示都是基于指針的四元樹結構，為了進一步減少存儲空間，研究人員針對四元樹作了不同程度的改進，比較有代表性的是線性四元樹(Linear Quadtree)[2]、四元樹的深度優(yōu)先表示 (DF-Expression Linear Quadtree)[3]和定長線性四元樹 (Constant Bit-Length Linear Quadtree, CBLQ)[4]。一般情況下，線性四元樹可節(jié)省66%的存儲空間，特殊情況下可節(jié)省高于90%的存儲空間。緊湊四元樹(Compact Improved Quadtree,簡稱Compact-IQ)[5]是四元樹的最新研究成果，由于采用了只記錄灰色結點和熵編碼的方法，在壓縮率和圖像運算效率上都表現(xiàn)非常出色。

非對稱逆布局模式表示模型(Non-symmetry Anti-packing Image Representation Model,NAM)[8～10]是一種全新的模式表示方法，可以廣泛用于圖像、語音、文本和視頻等信息模式的表示。盡管相關研究人員圍繞NAM提出了多種模式表示和模式操作的算法，但總的來說，在對圖像的模式表示上，相對于其他圖像表示方法所對應的操作算法而言，還有很多工作需要繼續(xù)，有些工作還有待進一步完善，基于NAM的集合運算就是其中一種。

圖像的集合運算是圖像處理中的原子操作，在很多圖像處理算法中要直接或間接地調用。筆者充分利用圖像中普遍存在的非對稱性和相關性，提出了導航數(shù)組(Navigation Array, 簡稱NA)輔助下的分裂組合法(Split and Combination Method,SCM)，實現(xiàn)了圖像的集合運算。同現(xiàn)有的一些圖像表示方法下的集合運算相比，新的集合運算算法由于采用非對稱分割所形成的較少的子模式數(shù)，在性能上表現(xiàn)突出，它能夠極大地提高集合運算的運行速度，使得調用該集合運算算法的程序能夠得以快速執(zhí)行?？傊滤惴ㄊ菆D像集合運算上的一個創(chuàng)新，所提出的導航數(shù)組以及分裂組合法還可以應用到其他圖像處理中，因此既具有理論上的指導意義又具有實踐上的應用價值。

1 分裂組合法

圖1 二值圖像矩形NAM分割結果及其導航數(shù)組

在基于NAM的圖像集合運算中，經常涉及查找相鄰或相交的塊等操作，導航數(shù)組(Navigation Array)就是為了解決塊之間位置關系問題而設計的。圖1(a)所示是二值圖像的NAM表示示意圖，塊中的數(shù)字表示經過NAM分割所得的編號，圖1(b)是相應的導航數(shù)組示意圖。從圖中可以看出，導航數(shù)組就是將塊中的每個像素單元以塊號填充就可以了，其它則以0填充。在進行查找某個塊的近鄰運算中，只需將該塊的周圍一圈像素掃描一下，得到的幾種編號就是該塊的近鄰。在分裂組合法中，由于經常要查找一個圖像中某個塊中另一個圖像中相鄰或相交的塊，其作用就更加明顯。導航數(shù)組生成時是只需要遍歷NAM表，將每個塊的編號插入到二維數(shù)組的相應位置即可。根據(jù)統(tǒng)計，黑白二值圖像中黑色點將占一半，因此，對于總像素為NP的圖像，其導航數(shù)組生成算法的時間復雜度為O(NP)。

圖2 2塊相交部分示意圖

下面介紹分裂組合法。如圖2所示，其中(xi,yi)代表矩形的起點坐標，hi、wi代表矩形的高和寬，2個矩形的相交部分就是圖2中的黑色塊，設其起點坐標為(x3,y3)，高和寬為h3和w3，max和min 分別是：

(x3,y3)=(max(x1,x2),max(y1,y2))

(1)

h3=min(x1+h1,x2+h2)-max(x1,x2)

(2)

w3=min(y1+w1,y2+w2)-max(y1,y2)

(3)

求最大值和最小值函數(shù)，于是可以得到式(1)～(3)，用來確定相交塊的位置及大小，只有當h3和w3均大于零才表示2個塊相交，否則表示不相交。

圖3 空白塊和陰影塊分割與標注

在確定了相交部分的位置后，沿相交部分的邊將其中一個塊的剩余部分分裂成幾個子矩形塊，選擇要保留的部分，最后在所有塊分裂結束后，把相鄰的塊進行組合，這個方法就稱為分裂組合法。盡管這種分裂方式有很多種，為了表示的方便，作了一個約束：只添加水平分割線。圖3中的虛線就是在這個約束下所加入的分割線。這樣分割的好處是可以使得左右2邊分割出的矩形與相交部分等高，而上下2邊分割出的矩形與空白塊等寬，利用所求出的相交部分計算分裂出來的各個塊的位置大小就很方便了。在這些分割出的矩形中，還可以分為上、下、左、右4類，分別稱為Up塊、Down塊、Left塊和Right塊。在圖3中，將以上各種情況分割出的矩形作了一下標注。

經過大量的分析研究后發(fā)現(xiàn)，NAM表示的圖像的集合運算(交、差、并)完全可以通過分裂組合法來完成，其中的關鍵就是“選擇要保留的部分”。比如說，交運算只保留相交部分作為結果，其他部分分裂成新的塊，而差運算則是剔除相交部分，將其他部分不斷分裂，把最終剩下的塊(差運算中要保留的部分)作為結果。以圖3(a)為例，假設2個圖像中的NAM塊分別形成空白塊和陰影塊2個隊列，在求它們的交運算時，依次掃描陰影塊隊列，利用其導航數(shù)組，找到與各個陰影塊相交的空白塊，在圖3(a)的情況下，將一個空白塊分裂成3個空白塊：Left塊、Down塊和Right塊，將它們加入到空白塊隊列，并修改導航數(shù)組，把相交部分保存到結果隊列中，于是一個陰影塊處理完畢，再處理下一個陰影塊。等所有的陰影塊處理完畢，再將結果隊列中的塊進行優(yōu)化組合，使最終的塊數(shù)盡量達到最少。

2 基于NAM的圖像集合運算算法

基于NAM的圖像集合運算有多種實現(xiàn)的途徑，筆者將采用分裂組合法來實現(xiàn)。由于各種集合運算實現(xiàn)上有類似之處，下面僅以交運算為例，給出其詳細的算法描述。圖像A與圖像B的交運算實質上就是在圖像A和圖像B上查找它們都存在的黑色點，這些黑色點所形成的圖像就是它們進行交運算的結果。在該算法中，就是要把所求得的相交部分保留下來即可(Step 2～ Step 9采用了分裂組合法)。

輸入：2n×2n的二值圖像G1、G2的NAM表NAM1、NAM2。

輸出：2n×2n的二值圖像G3的NAM表IntersectionNAM。

Step 1 根據(jù)NAM1生成對應的導航數(shù)組NaviArray；

Step 2 依次循環(huán)掃描圖像G2中各黑色塊，借助導航數(shù)組NaviArray分別取出在圖像G2黑色塊內的編號，如果編號為0，則進入下一輪循環(huán)；如果編號不為0，則根據(jù)式(1)～(3)求出該編號塊與圖像G2黑色塊的相交部分坐標及大小，將相交部分保存到IntersectionNAM中，并在其導航數(shù)組ResultNaviArray中填入相應的編號；

Step 3 計算Up塊、Down塊的高以及Left塊、Right塊的寬；

Step 4 如果Up塊存在，修改NAM1中編號塊的大小即可；

Step 5 如果Down塊存在，在NAM1中添加一個等寬的高為Down的新塊，并在導航數(shù)組中更新新塊所在部分的編號；

Step 6 如果Left塊存在，在NAM1中添加一個與相交部分等高的寬為Left的新塊，并在導航數(shù)組中更新新塊所在部分的編號；

Step 7 如果Right塊存在，在NAM1中添加一個與相交部分等高的寬為Right的新塊，并在導航數(shù)組中更新新塊所在部分的編號；

Step 8 更新NAM1中的總塊號，如果G2中黑色塊沒掃描完，就返回Step 2；

Step 9 依次循環(huán)掃描IntersectionNAM中各黑色塊，借助其導航數(shù)組ResultNaviArray和組合規(guī)則判斷上下左右4個點，如果左右的塊等高或是上下的塊等寬，則可將它們組合成一個新的塊；

Step 10 去掉IntersectionNAM中高度為0的塊并設置塊頭。

差運算和交運算類似，與之不同的是，在判斷出2塊相交的情況下，去掉相交部分，而保留其它部分，最后剩下的就是差運算的結果。由于在算法上與交運算幾乎相同，為節(jié)省篇幅，在此僅說明它們不同的2個地方：①在Step 2中，相交部分不保存；②在Step 9中，把NAM1中的塊作為DifferenceNAM，代替IntersectionNAM進行組合優(yōu)化。并運算可以借助前面2個運算來實現(xiàn)?？梢詫?個圖像的差運算結果與第2個圖像的NAM塊進行合并，再進行優(yōu)化組合，就是最終并運算的結果。

下面討論上述3個集合運算算法的時間復雜度。設整個圖像的像素總數(shù)為NP，NAM2的結點數(shù)為NQ，在3個算法中都調用了生成導航數(shù)組的操作，復雜度為O(NP)，而在依次掃描NAM2各結點的循環(huán)中，復雜度為O(NQ)，由于只標注黑色像素塊，顯然有NPgt;NQ，因此總的算法時間復雜度為O(NP)。

3 試驗結果及分析

試驗環(huán)境為Intel Celeron 1.4GHz移動處理器、512MB內存、Windows XP Professional操作系統(tǒng)、Matlab 6.5編程環(huán)境。圖4是試驗所用的4幅二值圖像，大小均為256×256。

圖4 試驗使用的4幅28×28的二值圖像

表1給出了圖4所示的4幅數(shù)字圖像的實驗結果，Cp表示圖像復雜度，從表中可以看出，實驗結果以相應圖像的圖像復雜度的遞增序排列。從表1中可以觀察到，隨著圖像復雜度的增加，線性四元樹表示、緊湊四元樹表示的節(jié)點個數(shù)和NAM表示的矩形個數(shù)都在增加。對于復雜度較低的圖像，NAM表示相對于線性四元樹表示、緊湊四元樹表示的壓縮率一般都很高，它們的比值可以達到4.967，而對于復雜度高的二值圖像，NAM表示也不遜色，與其它2種表示的比值也達到了1.204和1.688。從這些數(shù)據(jù)可知：NAM表示相對于線性四元樹表示和緊湊四元樹表示需要更少的表示單元數(shù)。

表1 線性四元樹、緊湊四元樹表示與NAM表示的精簡性對比

表2 集合運算效率比較

從表2中的結果來看，在測試圖像上，基于NAM的集合運算算法比基于緊湊四元樹的集合運算算法運行效率都要高，這一點從加速比中表現(xiàn)得相當明顯。對于2組圖像，集合運算的加速比最低達到1.291，最高達到了5.368?？偟膩碚f，由于NAM表上的精簡性，使得處理個數(shù)上的減少，進而使循環(huán)次數(shù)減少，因此，在集合運算性能上比緊湊四元樹的效率更高。

4 結 語

筆者在非對稱逆布局圖像表示模型(Non-symmetry Anti-packing Image Representation Model, NAM)的基礎上，提出了基于NAM的集合運算算法，并對算法作了復雜性分析。試驗結果表明，基于NAM的集合運算算法的執(zhí)行速度是基于緊湊四元樹集合運算算法執(zhí)行速度的1.291到5.368倍。大量的研究表明，NAM能夠有效地減少表示一幅圖像所需要的存儲空間，是一種良好的圖像表示方法。

[1]Hunter G M. Operations on Images Using Quad Trees[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(2): 145～153.

[2]Bauer M A. Set Operation on Linear Quadtrees. Computer Graphic and Image Processing,1985, 29(2): 248～258.

[3]Kawaguchi E, Endo T. On a Method of Binary-Picture Representation and Its Application to Data Compression[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1980, PAMI-2(1): 27～35.

[4]Lin T W.Set Operations on Constant Bit-Length Linear Quadtrees[J]. Pattern Recognition, 1997, 30(7): 1239～1249.

[5]Yuh-Horng Yang, Kuo-Liang Chung, Yao-Hong Tsai. A Compact Improved Quadtree Representation with Image Manipulations[J]. Image and Vision Computing, 2000, 18(3): 223～231.

[6]陳傳波, 何大華, 黃文奇.求解單位等邊三角形 Packing問題的近似算法[J].計算機學報,2003, 26(2):212～220.

[7]Chen Chuan-bo, He Da-hua. Heuristic Method for Solving Triangle Packing Problem [J]. Journal of Zhejiang University, 2005, 6(6): 565～570.

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

[9]鄭運平, 陳傳波. 一種基于NAM的彩色圖像表示方法研究 [J]. 軟件學報, 2007, 18(11): 2932～2941.

[10]Yunping Zheng, Chuanbo Chen, Mudar Sarem. A novel algorithm for triangle non-symmetry and anti-packing pattern representation model of gray images[J]. Proceedings of the 3rd International Conference on Intelligent Computing (ICIC'07), 2007, LNCS 4681:832～841.

[編輯] 易國華

TP391

A

1673-1409(2009)02-N076-04

2009-03-01

國家高技術研究發(fā)展計劃(863)資助項目(2006AA04Z211)。

伍鵬(1978-)，男，2001年大學畢業(yè)，碩士，講師，現(xiàn)主要從事圖像處理與模式識別方面的教學與研究工作。