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

宮海曉，賀 杰

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

0 引言

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

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

1 對角掃描的過程原理

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

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

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

2 對角掃描算法的編碼設計

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

對角掃描算法的詳細編碼步驟如下：

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

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

步驟3：定義一個循環變量i用于控制正方形的邊長變化，把i值賦給開始定義好的變量len。

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

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

步驟6：判斷對角的之間的坐標值的橫縱坐標之間的差值是否為0(為零說明最后一個頂點為黑點則能形成本次循環的最大正方形)，為0繼續下一步；不為0則返回步驟(5)繼續判斷下一對對角點。

步驟7：判斷正方形的最后一個像素點是否為0，為0則繼續下一步判斷；否則跳到步驟(10)進行判斷。

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

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

步驟10：最后一個點不為黑點，不能形成此循環內的最大正方形，要把標記變量flag賦值為1，中斷此循環，正方形邊長變量的值len減1，并返回步驟(9)進行記錄上一個形成的正方形。

線段和孤立點搜索的算法步驟類似，在此就不再重復介紹。

3 對角掃描算法的應用舉例

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

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

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

(a)二值圖像Q的正方形子模式表示結果 (b)算法產生數據的存儲結果圖3 二值圖像中正方形子模式存儲結果

4 算法分析

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

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

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

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

4 總結

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