一種基于SNAM二值圖像表示方法的正方形子模式搜索策略

宮海曉，賀 杰

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

0 引言

圖像表示[1]是圖像處理領(lǐng)域中的一個(gè)重要的研究方向，隨著多媒體技術(shù)的發(fā)展，圖像數(shù)據(jù)量變得越來(lái)越大，為了減少數(shù)據(jù)存儲(chǔ)量和提高處理效率，陳傳波教授提出了一種新的圖像表示方法，即非對(duì)稱逆布局模型的圖像表示方法[2]，該方法不僅解決了四元樹(shù)等圖像表示方法存在的對(duì)稱分割問(wèn)題，而且在降低圖像的存儲(chǔ)空間、提高算法的運(yùn)算速度等方面都取得了顯著的成效。后續(xù)研究者陸續(xù)提出了基于矩形、三角形、梯形等的圖像表示方法，其中賀杰教授在NAM的基礎(chǔ)上提出了基于正方形的非對(duì)稱逆布局表示方法[3]，即SNAM圖像表示方法，該方法通過(guò)光柵掃描[4]的方式對(duì)正方形子模式進(jìn)行搜索，然后對(duì)搜索到的子模式進(jìn)行逆布局，最終形成了圖像的表示。

光柵掃描適用于塊狀特征不明顯的圖像，是一種通用的掃描方式，但該掃描策略對(duì)SNAM的正方形子模式的搜索具有一定的局限性，因此，作者針對(duì)正方形子模式獨(dú)有的結(jié)構(gòu)特征，提出了對(duì)角掃描策略。

1 對(duì)角掃描的過(guò)程原理

對(duì)角掃描方式依據(jù)正方形獨(dú)特的結(jié)構(gòu)特征，通過(guò)判斷對(duì)角的兩個(gè)像素點(diǎn)特征是否一致進(jìn)行搜索，具體過(guò)程為，在二值圖像矩陣中的第一行開(kāi)始找到一個(gè)像素值為0且未被標(biāo)記的點(diǎn)，把此點(diǎn)當(dāng)基準(zhǔn)點(diǎn)A，A的坐標(biāo)值為(x，y)。以A為正方形的左上角頂點(diǎn)開(kāi)始尋找第一個(gè)正方形，以i(i=1，2，3...)為正方形邊長(zhǎng)開(kāi)始搜索；接下來(lái)開(kāi)始掃描基準(zhǔn)點(diǎn)A正右方對(duì)應(yīng)的頂點(diǎn)B和正下方的對(duì)應(yīng)頂點(diǎn)C的值是否同時(shí)為0(B和C點(diǎn)正方形左上角頂點(diǎn)存在一定的數(shù)學(xué)關(guān)系，B和C在一條對(duì)角線上)，其中j是控制在i內(nèi)的變量邊長(zhǎng)，(x+j-1，y+i)、(x+i，y+j-1)分別對(duì)應(yīng)B點(diǎn)和C點(diǎn)的坐標(biāo)。B和C點(diǎn)的值若都為0，則判斷B點(diǎn)和C點(diǎn)的橫坐標(biāo)和縱坐標(biāo)的差值是否為x-y；當(dāng)條件不成立，繼續(xù)尋找下一個(gè)新的基準(zhǔn)點(diǎn)A。若B，C同時(shí)為0則判斷正方形的最后一個(gè)點(diǎn)D的像素值是否為0，為0，判斷正方形是否已經(jīng)到達(dá)邊界，不為邊界則i值變化，j隨著i變化，繼續(xù)類似于B、C的對(duì)角點(diǎn)值進(jìn)行更大的正方形搜索；否則記錄此次所能形成的最大正方的數(shù)據(jù)。不斷重復(fù)上述描述的掃描過(guò)程，直到所有正方形子模式搜索完成。

圖1(a)是一幅原始二值圖像，圖像中黑點(diǎn)代表像素值為0，白點(diǎn)代表像素值為1。以第一行所在位置設(shè)為坐標(biāo)軸的x軸，第一列所在位置為y軸，則第一行和第一列形成了一個(gè)二維的坐標(biāo)軸。第一個(gè)點(diǎn)值從(1，1)開(kāi)始進(jìn)行掃描。圖1(b)是反角掃描方式掃描過(guò)程示意圖。

(a)原始二值圖像 (b)對(duì)角掃描方式掃描過(guò)程走向圖1 對(duì)角掃描正方形子模式算法的解析

2 對(duì)角掃描算法的編碼設(shè)計(jì)

首先定義正方形、線段以及孤立點(diǎn)等子模式，對(duì)于一幅二值圖像的矩陣，依照對(duì)角掃描方式的過(guò)程，從二值圖像的矩陣中提取出黑色像素形成的大小不同的正方形、長(zhǎng)短不同的線段和孤立點(diǎn)，并記錄下這些子模式的數(shù)據(jù)。

對(duì)角掃描算法的詳細(xì)編碼步驟如下：

步驟1：以x，y為變量，用兩層嵌套循改變像素值的變化，其中變化范圍為1到n。

步驟2：定義一個(gè)標(biāo)記變量flag并賦給初值0，從圖像矩陣的起始點(diǎn)開(kāi)始找到第一個(gè)像素值為0且未被標(biāo)記為2的點(diǎn)。把坐標(biāo)值(x，y)賦給(sp_x，sp_y)。

步驟3：定義一個(gè)循環(huán)變量i用于控制正方形的邊長(zhǎng)變化，把i值賦給開(kāi)始定義好的變量len。

步驟4：判斷標(biāo)志變量flag是否為1，值為1，則跳出i循環(huán)，跳到步驟(1)；否則繼續(xù)下一步。

步驟5：判斷能形成正方形對(duì)角頂點(diǎn)所在位置的像素值是否為0，其中有不為0，說(shuō)明此循環(huán)中判斷的正方形不能形成，要返回上一步記錄比這個(gè)小的正方形，即跳到步驟(10)；否則繼續(xù)下一步。

步驟6：判斷對(duì)角的之間的坐標(biāo)值的橫縱坐標(biāo)之間的差值是否為0(為零說(shuō)明最后一個(gè)頂點(diǎn)為黑點(diǎn)則能形成本次循環(huán)的最大正方形)，為0繼續(xù)下一步；不為0則返回步驟(5)繼續(xù)判斷下一對(duì)對(duì)角點(diǎn)。

步驟7：判斷正方形的最后一個(gè)像素點(diǎn)是否為0，為0則繼續(xù)下一步判斷；否則跳到步驟(10)進(jìn)行判斷。

步驟8：判斷步驟(7)的最后一個(gè)像素點(diǎn)是否為以(x，y)為左上角頂點(diǎn)所達(dá)到最大正方形的邊界點(diǎn)，是邊界點(diǎn)繼續(xù)下一步；否則回到步驟(3)，i的值增1進(jìn)入下一個(gè)循環(huán)。

步驟9：判斷邊長(zhǎng)變量len是否大于0，大于0能形成一個(gè)有效的正方形則計(jì)數(shù)變量Num的值增加1，把定點(diǎn)坐標(biāo)(sp_x，sp_y)和邊長(zhǎng)值len存到元胞數(shù)組中，然后用兩個(gè)嵌套循環(huán)把此正方形所包含的像素值點(diǎn)全部賦值為2作為標(biāo)記。返回步驟(2)，繼續(xù)尋找下一個(gè)正方形，直到所有的圖像模型中的正方形子模式全部被抽取出來(lái)為止。

步驟10：最后一個(gè)點(diǎn)不為黑點(diǎn)，不能形成此循環(huán)內(nèi)的最大正方形，要把標(biāo)記變量flag賦值為1，中斷此循環(huán)，正方形邊長(zhǎng)變量的值len減1，并返回步驟(9)進(jìn)行記錄上一個(gè)形成的正方形。

線段和孤立點(diǎn)搜索的算法步驟類似，在此就不再重復(fù)介紹。

3 對(duì)角掃描算法的應(yīng)用舉例

圖2(a)是一幅大小為9×9的原始二值圖像，圖2(b)運(yùn)用對(duì)角掃描方式進(jìn)行對(duì)圖像(a)的NAM正方形子模式搜索逆布局結(jié)果，從原圖中抽取出了5個(gè)正方形子模式、2條線段和2個(gè)孤立點(diǎn)。

(a)9×9的原始二值圖像 (b)反對(duì)角掃描正方形逆布局結(jié)果圖2 對(duì)角掃描策略對(duì)二值圖像正方形逆布局的過(guò)程

在搜索過(guò)程中產(chǎn)生的數(shù)據(jù)，對(duì)于正方形子模式，將左上頂點(diǎn)坐標(biāo)和邊長(zhǎng)存儲(chǔ)即可。線段則把起始端點(diǎn)的坐標(biāo)和長(zhǎng)度存儲(chǔ)即可。孤立點(diǎn)將坐標(biāo)存儲(chǔ)即可。圖3是對(duì)二值圖像的正方形對(duì)角掃描的逆布局存儲(chǔ)結(jié)果。下頁(yè)圖3(a)是所有子模式的搜索結(jié)果，即5個(gè)正方形，2條線段和2個(gè)孤立點(diǎn)，下頁(yè)圖3(b)子模式的存儲(chǔ)方式，如正方形子模式s1，其存儲(chǔ)記錄為s1={(2，4)，1}，表示其左上角頂點(diǎn)坐標(biāo)為(2，4)，邊長(zhǎng)為1個(gè)的正方形所包含的像素點(diǎn)；線段子模式l1，其存儲(chǔ)記錄為l1={(1，1)，1}，表示其線段起始頂點(diǎn)坐標(biāo)為(1，1)，長(zhǎng)度為1個(gè)的線段所包含的像素點(diǎn)；孤立點(diǎn)子模式p1，其存儲(chǔ)記錄為p1={(2，1)}，表示其坐標(biāo)為(2，1)的像素點(diǎn)。

(a)二值圖像Q的正方形子模式表示結(jié)果 (b)算法產(chǎn)生數(shù)據(jù)的存儲(chǔ)結(jié)果圖3 二值圖像中正方形子模式存儲(chǔ)結(jié)果

4 算法分析

對(duì)角掃描算法的時(shí)間復(fù)雜度主要取決于算法中的4個(gè)嵌套循環(huán)，因此對(duì)于一幅規(guī)模為N的二值圖像P，N就是P的像素總數(shù)，利用對(duì)角掃描算法進(jìn)行編碼，算法消耗時(shí)間與像素總數(shù)N成正比，因此反對(duì)角掃描算法的時(shí)間復(fù)雜度為O(Nn4)。

在對(duì)角掃描算法中，用于存儲(chǔ)輸入數(shù)據(jù)和在執(zhí)行過(guò)程中緩存的存儲(chǔ)空間對(duì)算法的復(fù)雜度的分析影響較小，算法在執(zhí)行過(guò)程中所需要的額外空間與圖像像素總數(shù)大小的有著正比的關(guān)系，圖像的像素總量為N，則對(duì)角掃描算法的空間復(fù)雜度可以表示為O(N)。

而在數(shù)據(jù)量方面，對(duì)于一幅大小為n×n的二值圖像模型，在對(duì)角掃描算法編碼后產(chǎn)生Ns個(gè)正方形子模式，Nl條線段，Np個(gè)孤立點(diǎn)，總的子模式數(shù)據(jù)量設(shè)為A，依據(jù)賀杰教授的SNAM表示方法，存儲(chǔ)這些子模式的存儲(chǔ)空間正方形需要2n位、線段2n位、孤立點(diǎn)n位。因此總的存儲(chǔ)空間為：As=2nNs+2nNl+nNp。

如采用線性四元樹(shù)LQT表示方法編碼[5]，文獻(xiàn)1指出，記錄一個(gè)像素點(diǎn)需要3n-1位的空間，假設(shè)黑色像素?cái)?shù)量是NLQT，ALQT表示數(shù)據(jù)總量，則總的數(shù)據(jù)量為：ALQT=(3n-1)NLQT。

4 總結(jié)

本文以SNAM圖像表示方法為依據(jù)，利用正方形的特殊形狀結(jié)構(gòu)，在光柵掃描的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了對(duì)角掃描策略，并詳細(xì)分析了該掃描算法的原理、對(duì)算法進(jìn)行了編碼設(shè)計(jì)，然后結(jié)合實(shí)例進(jìn)行詳細(xì)闡述，最后在理論上對(duì)算法的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)量、時(shí)間復(fù)雜度等幾個(gè)方面[7]，與經(jīng)典的線性四元樹(shù)表示方法進(jìn)行了比較和分析。理論分析和實(shí)驗(yàn)結(jié)果表明，基于對(duì)角掃描的SNAM圖像表示方法相對(duì)于線性四元樹(shù)表示方法，在子模式數(shù)量、搜索速度等方面都具有一定的優(yōu)勢(shì)。