改進(jìn)的正方形NAM二值圖像表示方法

宮海曉，賀 杰，郭 慧

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

?

改進(jìn)的正方形NAM二值圖像表示方法

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

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

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

NAM；正方形；線性四元樹(shù)；子模式

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

1算法的改進(jìn)和描述

1.1算法的改進(jìn)

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

1.1.1殘?jiān)Ｊ降奶幚砗蛢?yōu)化

在SNAM表示方法中，首先對(duì)正方形進(jìn)行逆布局，然后將剩余的線段和孤立點(diǎn)全部歸結(jié)為殘?jiān)Ｊ剑磳?duì)殘?jiān)Ｊ竭M(jìn)行二次優(yōu)化處理，因此形成的子模式數(shù)量較多。本文將SNAM表示方法中的殘?jiān)Ｊ?，即線段和孤立點(diǎn)重新進(jìn)行逆布局，形成新的等腰直角三角形子模式。

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

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

1.1.2等腰直角三角形子模式的設(shè)計(jì)

在算法的設(shè)計(jì)中，首先對(duì)正方形子模式進(jìn)行逆布局，對(duì)殘?jiān)Ｊ降哪娌季质窃谧詈筮M(jìn)行，因此形成的等腰直角三角形的腰長(zhǎng)均為1，同時(shí)根據(jù)等腰直角三角形直角頂點(diǎn)的位置，將其子模式分為4類，即左上、左下、右上、右下，如圖2所示。

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

1.1.3存儲(chǔ)結(jié)構(gòu)的優(yōu)化

SNAM表示方法對(duì)逆布局的每一個(gè)正方形子模式和殘?jiān)Ｊ竭M(jìn)行了單獨(dú)存儲(chǔ)，在存儲(chǔ)時(shí)不僅需要記錄每個(gè)正方形的左上頂點(diǎn)坐標(biāo)及邊長(zhǎng)，而且還需記錄每條線段的兩個(gè)端點(diǎn)坐標(biāo)和孤立點(diǎn)的坐標(biāo)，存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)簡(jiǎn)單，因此占用了較大的存儲(chǔ)空間。本文將邊長(zhǎng)相同的正方形子模式存儲(chǔ)到指定的隊(duì)列，實(shí)現(xiàn)了分類存儲(chǔ)，因此在存儲(chǔ)時(shí)只需記錄正方形的左上頂點(diǎn)坐標(biāo)即可，同時(shí)將類型相同的等腰直角三角形，也進(jìn)行了分類存儲(chǔ)，存儲(chǔ)時(shí)只需記錄等腰直角三角形子模式的直角頂點(diǎn)坐標(biāo)。改進(jìn)的ISNAM表示方法在逆布局后仍然存在線段和孤立點(diǎn)子模式，對(duì)孤立點(diǎn)子模式的存儲(chǔ)同SNAM表示方法一樣，但對(duì)線段的存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)優(yōu)化為將長(zhǎng)度相同的線段存儲(chǔ)到指定的隊(duì)列，因此只需記錄線段子模式的第一個(gè)端點(diǎn)坐標(biāo)即可。

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

1.2算法的描述

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

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

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

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

Step 2.記錄該正方形子模式的邊長(zhǎng)和左上角的頂點(diǎn)坐標(biāo)，將其二維坐標(biāo)(x,y)通過(guò)降維變換為一維坐標(biāo)sp，根據(jù)正方形的邊長(zhǎng)，將sp存儲(chǔ)到指定的正方形子模式的集合V_si中，其中i為邊長(zhǎng)。

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

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

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

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

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

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

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

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

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

2算法的理論分析

2.1存儲(chǔ)結(jié)構(gòu)分析

對(duì)于一個(gè)2n×2n的圖像子模式來(lái)說(shuō)，本文將正方形子模式根據(jù)邊長(zhǎng)的長(zhǎng)度進(jìn)行了分類存儲(chǔ)，即將相同邊長(zhǎng)的正方形存儲(chǔ)到一個(gè)隊(duì)列中，同時(shí)以正方形的邊長(zhǎng)長(zhǎng)度命名隊(duì)列，因此對(duì)相同邊長(zhǎng)的正方形來(lái)說(shuō)，只需存儲(chǔ)其左上角頂點(diǎn)的坐標(biāo)即可。在坐標(biāo)存儲(chǔ)中，一般用K碼的相對(duì)值記錄，因此按照K碼的定義，頂點(diǎn)坐標(biāo)的長(zhǎng)度理論值為n位[3]，因此，存儲(chǔ)一個(gè)正方形需要n位。

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

對(duì)于剩余的線段和孤立點(diǎn)子模式而言，線段根據(jù)長(zhǎng)度同樣進(jìn)行分類存儲(chǔ)，即將相同長(zhǎng)度的線段存儲(chǔ)到一個(gè)隊(duì)列中，該隊(duì)列以線段長(zhǎng)度命名，所以只需記錄其左邊頂點(diǎn)坐標(biāo)即可，因此存儲(chǔ)一個(gè)線段需要n位，存儲(chǔ)一個(gè)孤立點(diǎn)需要n位。

2.2數(shù)據(jù)量分析

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

HIS=nNS+nNT+nNL+nNP

(1)

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

HLQT=(3n-1)NLQT

(2)

設(shè)φLQT IS為L(zhǎng)QT的總數(shù)據(jù)量與STNAM的總數(shù)據(jù)量的比值，則有：

(3)

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

3算法的實(shí)驗(yàn)分析

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

圖3 實(shí)驗(yàn)測(cè)試圖像

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

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

ImageCNLQTSNAMISNAM?LQT＿S?LQT＿ISBaboon0260117047866883463801342978Boat013138604351529914609452297Lena009816430307723674037659787Flight008505568225313324753762731

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

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

4結(jié)論

本文以SNAM圖像表示方法為基礎(chǔ)，提出了改進(jìn)的正方形ISNAM圖像表示方法，該方法將SNAM剩余的殘?jiān)Ｊ街匦聵?gòu)成新的等腰直角三角形子模式。在子模式的存儲(chǔ)方面，根據(jù)正方形的邊長(zhǎng)，等腰直角三角形的類型和線段的邊長(zhǎng)對(duì)子模式分類存儲(chǔ)。理論和實(shí)驗(yàn)分析表明：改進(jìn)的正方形ISNAM圖像表示方法具有更少的子模式數(shù)，有效地減少了圖像的存儲(chǔ)空間，是一種值得推廣的圖像表示方法。

[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] 陳傳波.非對(duì)稱逆布局模式表示方法研究[D].武漢:華中科技大學(xué),2006.

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

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

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

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

(責(zé)任編輯：覃華巧)

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

廣西自然科學(xué)基金項(xiàng)目(2013GXNSFBA019275，2013GXNSFBA019276)

TP391

A

1673-8535(2016)03-0001-06

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

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

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