魏小峰 耿則勛 濮國梁 王德永

三角形網(wǎng)格的鏈碼方法研究

魏小峰1,2,?耿則勛3濮國梁1王德永3

1.北京大學工學院, 北京 100871; 2.96633 部隊, 北京 100096; 3.平頂山學院, 平頂山 467000;? E-mail: weixiaofeng@pku.edu.cn

目前可以應(yīng)用于三角形網(wǎng)格的鏈碼方法只有頂點鏈, 而它對角相鄰情況的表達存在缺陷, 針對此問題, 提出 3 種鏈碼方法, 并進行特性分析和性能比較。首先將 Freeman 鏈碼擴展應(yīng)用到三角形網(wǎng)格, 根據(jù)兩種不同的三角形單元, 分別設(shè)計對應(yīng)的 12 方向 Freeman 鏈碼編碼規(guī)則; 然后, 基于外輪廓前進相對方向的變化, 提出相對方向鏈碼; 最后, 通過區(qū)分邊界網(wǎng)格在外輪廓上的邊數(shù)和內(nèi)部網(wǎng)格數(shù)的不同組合, 得到邊角組合鏈碼。通過實驗比較 3 種鏈碼的表達能力和壓縮率, 結(jié)果表明, 3 種鏈碼方法均能克服頂點鏈的缺陷, 準確完備地實現(xiàn)三角形網(wǎng)格形狀的邊界表達。其中, 邊角組合鏈碼的綜合性能最高, 平均碼數(shù)為 1, 壓縮率可達 0.75。

三角形網(wǎng)格; Freeman鏈碼; 邊角組合鏈碼; 壓縮率

鏈碼是通過一定的編碼方式對幾何形狀的邊界進行順序表達的方法。1961 年 Freeman[1]最早提出鏈碼方法, 即 Freeman 四方向和八方向鏈碼, 之后還出現(xiàn)頂點鏈碼(vertex chain code, VCC)[2]、直角三方向鏈碼(orthogonal three-direction chain code, 3OT)[3-4]和無符號曼哈頓鏈碼(unsigned manhattan chain code, UMCC)[5]等多種方法。目前, 鏈碼廣泛應(yīng)用于計算機視覺[6-7]、模式識別[8-9]、數(shù)字圖像處理[10-11]和地理信息系統(tǒng)[12]等各個領(lǐng)域。

通過依次記錄形狀輪廓上共頂點的邊界網(wǎng)格數(shù)進行邊界表達, 這是 VCC 的實現(xiàn)方法。對于正方形網(wǎng)格, VCC 只需要“1”, “2”, “3”這 3 個碼值即可完成邊界描述, 分別對應(yīng)邊界網(wǎng)格的凸角轉(zhuǎn)向、水平或垂直方向前進以及凹角轉(zhuǎn)向, 如圖 2 所示。類似地, VCC 可表示為∑(VCC)={1, 2, 3}。

此外, VCC 還可用于六邊形網(wǎng)格和三角形網(wǎng)格的形狀邊界表達, 這是目前唯一能夠直接應(yīng)用于非四邊形網(wǎng)格的鏈碼方法。例如, 對于三角形網(wǎng)格, 其輪廓上共頂點的邊界網(wǎng)格數(shù)最多為 5 個, 因此可以用“1”~“5”這 5 個碼值進行表達, 如圖 3 所示。

UMCC 于 2016 年提出, 該鏈碼只使用“0”和“1”兩個碼值記錄邊界網(wǎng)格中心連線沿和方向的前進, 并且利用 3 組“00”開頭的標識碼, 分別表示兩個方向上的單調(diào)性變化情況, 表示為∑(UMCC)= {0, 1}。

深色表示當前邊界網(wǎng)格, 淺色為可能的下一個邊界網(wǎng)格

圖2 頂點鏈碼

圖4 直角三方向鏈碼

除 VCC 外, 其他 3 種鏈碼均只考慮四邊形網(wǎng)格一種情況。對于連續(xù)圖像的離散化, 還可以按照三角形或六邊形進行采樣。這 3 種模式均有固定的規(guī)格, 并且能夠無縫地覆蓋 2D 平面。劉志坤等[13]證明, 規(guī)則正三角形網(wǎng)格(簡稱三角形網(wǎng)格)在有效覆蓋面積和覆蓋效率兩項指標上均優(yōu)于正四邊形, 更適用于 2D 和 3D 的幾何表達。但是, 目前還沒有針對三角形網(wǎng)格鏈碼的研究報道。

VCC 能夠表達三角形網(wǎng)格邊界, 但對一些特殊情況的處理存在缺陷。例如, 圖 5 展示 3 種不同的角相鄰情況,VCC 在斜線網(wǎng)格 3 個頂點上的碼值均為“211”, 無法對這 3 種情況進行有效的區(qū)分。3OT將形狀輪廓的前進方向分為 3 個相對變化的直角方向, 并加以分別表達。然而, 沿三角形網(wǎng)格外輪廓, 并不是簡單的直角轉(zhuǎn)折或回轉(zhuǎn)方向, 因此該方法無法直接應(yīng)用到三角形網(wǎng)格中。UMCC 記錄相鄰網(wǎng)格中心連線沿邊界前進時在和方向上的單調(diào)性變化, 但三角形網(wǎng)格的邊角關(guān)系復雜, 存在 3 種角相鄰和 9 種邊相鄰關(guān)系, 導致在笛卡爾坐標系下有多組相同的單調(diào)性變化情況, 無法通過“0”和“1”直接進行區(qū)分標識。如果增加標識碼, 會使編碼復雜, 造成過多冗余, 同樣也不適用于三角形網(wǎng)格鏈碼。在原有鏈碼方法中, 只有 Freeman 鏈碼可以較好地擴展應(yīng)用到三角形網(wǎng)格。

本文研究能夠應(yīng)用于三角形網(wǎng)格, 并準確完備地表達形狀邊界的鏈碼方法及其特性。首先, 分析現(xiàn)有的四邊形網(wǎng)格鏈碼方法在三角形網(wǎng)格中的適用性, 并通過擴展, 得到 12 方向的 Freeman 鏈碼。然后, 分別基于輪廓前進的相對方向變化和外輪廓上邊界網(wǎng)格的邊數(shù)與夾角特性, 提出兩種新的三角形網(wǎng)格鏈碼方法。在此基礎(chǔ)上, 分析 3 種鏈碼方法的幾何特性, 并通過實驗比較各鏈碼的表達能力和壓縮率。

圖5 三角形網(wǎng)格中的角相鄰情況

1 三角形網(wǎng)格鏈碼方法

1.1 12 方向 Freeman 鏈碼

與四邊形網(wǎng)格相比, 三角形網(wǎng)格的單元結(jié)構(gòu)和特性更復雜, 主要體現(xiàn)在兩方面: 1) 三角形單元方位不唯一, 根據(jù)其在笛卡爾坐標系中的方位, 可分別稱為正三角和倒三角單元(圖 6); 2) 鄰接關(guān)系更多樣, 存在 3 種邊相鄰及 9 種角相鄰的情況。

Freeman 鏈碼的編碼原理是基于相鄰邊界網(wǎng)格中心連線的絕對方向, 因此適用于三角形網(wǎng)格。通過增加碼值, 將 Freeman 鏈碼擴展到三角形網(wǎng)格。結(jié)合三角形網(wǎng)格的方位關(guān)系和鄰接關(guān)系, 應(yīng)用于三角形網(wǎng)格的 Freeman 鏈碼需要 12 個碼值, 并分兩種情況進行編碼。

首先, 對于正三角單元, 從其右側(cè)邊相鄰的網(wǎng)格起, 沿逆時針方向分別賦予碼值“0”~“9”以及“A”和“B”, 如圖 6(a)所示。其中, “0”, “4”, “8”對應(yīng) 3 個邊相鄰網(wǎng)格, “1”~“3”, “5”~“7”和“9”~“B”分別對應(yīng)共頂點的三組角相鄰網(wǎng)格。

然后, 將倒三角網(wǎng)格單元及其鄰域網(wǎng)格視為由正三角網(wǎng)格上下翻轉(zhuǎn)得到, 據(jù)此可直接得到倒三角網(wǎng)格的編碼結(jié)果。這相當于由當前單元右側(cè)邊相鄰的網(wǎng)格開始, 按順時針方向依次賦予碼值, 如圖 6 (b)所示。按這種方式, 無論是在正三角單元還是倒三角單元, 與當前網(wǎng)格邊相鄰的網(wǎng)格碼值均為“0”, “4”和“8”, 其余角相鄰網(wǎng)格碼值也相同, 因此可較好地保證正三角與倒三角單元編碼的一致性。

由于三角形網(wǎng)格鄰域內(nèi)在 0°和 180°方向的網(wǎng)格均不唯一, 如“0”與“B”以及“4”與“5”均為同一方向, 僅根據(jù)當前網(wǎng)格與下一網(wǎng)格中心連線的絕對方向無法區(qū)分, 需要利用相鄰網(wǎng)格距離進行判斷。

圖6兩種三角單元的F12編碼規(guī)則

綜上所述, 三角形網(wǎng)格的 12 方向 Freeman 鏈碼可以用∑(F12)={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B}來表示。確定起始網(wǎng)格后, 依次對其他邊界網(wǎng)格賦予唯一對應(yīng)的碼值, 每個碼需要 4bit 存儲空間。圖 7 給出利用 F12 按逆時針方向?qū)θ切尉W(wǎng)格形狀邊界的編碼示例。

1.2 相對方向鏈碼

多邊形網(wǎng)格的鄰接關(guān)系決定其可能的輪廓前進方向。四邊形網(wǎng)格上每個頂點由 4 個 90°角共有, 因此經(jīng)過該點的輪廓前進方向共 3 種: 向前(0°), 向左(逆時針 90°)或向右(順時針 90°)。相比之下, 三角形網(wǎng)格每個頂點由 6 個三角形的 60°角共有, 前進方向分為 5 種, 包括與當前方向相比無變化以及相對當前方向分別偏轉(zhuǎn)±60°和±120°(向左為正, 向右為負), 如圖 8 中虛線箭頭所示。

圖7 12方向Freeman鏈碼示例

圖8 三角形網(wǎng)格輪廓前進相對方向

由于 RDCC 記錄的是外輪廓每個頂點處的相對方向變化, 因此總碼數(shù)與形狀外輪廓上的頂點數(shù)相同, 平均每個碼占據(jù) 3bit 存儲空間。用 RDCC 對圖7中的形狀邊界進行編碼, 結(jié)果如圖 9 所示。

與 VCC 相似, RDCC 也通過依次記錄形狀外輪廓各頂點處的某種特性來完成邊界表達, 然而, RDCC 可避免 VCC 在特殊情況下的編碼缺陷。如圖 9 左側(cè)和右側(cè)的兩種角相鄰情況, 由于兩種情況在外輪廓上的相對前進方向不同, 得到的編碼結(jié)果也不同。因此, RDCC 比 VCC 更加完備和準確。

1.3 邊角鏈碼

形狀的外輪廓由各邊界網(wǎng)格在外輪廓上的邊組成, 因此可以通過統(tǒng)計邊界網(wǎng)格在外輪廓上的邊數(shù), 實現(xiàn)形狀邊界的表達。對于三角形網(wǎng)格, 各邊界網(wǎng)格在外輪廓上的邊數(shù)可能為 1, 2 或 3。由于三角形網(wǎng)格邊角關(guān)系復雜, 存在邊數(shù)相同但輪廓前進方向不同的情況, 需要進一步區(qū)分。

根據(jù)邊界網(wǎng)格在外輪廓上的邊數(shù)不同, 分以下兩種情況進行討論。

圖9 相對方向鏈碼示例

1)邊數(shù)為 1 或 2 時。此時分別對應(yīng) 4 種不同的輪廓前進方向, 如圖 10 所示。通過觀察可以發(fā)現(xiàn), 對不同的輪廓前進方向, 可以通過相鄰邊界網(wǎng)格之間的夾角進行區(qū)分。不同夾角的直接體現(xiàn)是相鄰邊界網(wǎng)格共頂點的形狀內(nèi)非邊界網(wǎng)格數(shù)不同, 即圖 10 中的陰影部分, 將其定義為內(nèi)部網(wǎng)格, 取值范圍為 0~3。由于三角形邊界網(wǎng)格的外輪廓邊數(shù)(1~2)與內(nèi)部網(wǎng)格數(shù)(0~3)存在 8 種組合, 因此每種組合可分別由 1 個碼值表示, 每個碼占用 3bit 存儲空間。因此, 8 種情況依次由“0”~“7”這 8 個碼值表示。

2)邊數(shù)為 3 時。此時對應(yīng) 3 種輪廓前進方向, 即圖 5 所示的 3 種角相鄰情況。這 3 種情況在實際應(yīng)用中出現(xiàn)的概率較小, 因此可考慮用冗余的碼值組合進行替換, 如圖 11 所示。

川貝母對哮喘模型小鼠氣道炎癥及ERK/MAPK信號通路的影響 …………………………………………… 張羽飛等（3）：343

注意到碼值組合“44”表示兩個三角形網(wǎng)格的自閉合, 但這種情況實際上并不存在(圖 12)。因此, 可將其作為邊數(shù)為 3 時的區(qū)分碼, 分別將圖 5 中的 3 種角相鄰情況用“441”, “442”和“443”這 3 個組合表達。

2 幾何特性分析

鏈碼的主要幾何特性包括可檢測直線段、與起始點無關(guān)性、旋轉(zhuǎn)不變性和翻轉(zhuǎn)不變性等。不同的三角形鏈碼, 幾何特性也有所區(qū)別。下面分別對F12, RDCC, VCC 和 EACC 這 4 種三角形網(wǎng)格鏈碼方法的幾何特性進行分析與比較。

圖10 邊數(shù)為1和2時三角形邊界網(wǎng)格的輪廓前進方向

圖11 邊數(shù)為3時三角形邊界網(wǎng)格的輪廓前進方向

圖12 組合“44”對應(yīng)的三角形網(wǎng)格

圖13 邊角鏈碼示例

2.1 F12特性分析

利用 F12 鏈碼可檢測不同方向的直線段, 并且編碼結(jié)果與起始點選擇無關(guān)。

1)F12 鏈碼的不同碼值代表邊界網(wǎng)格中心連線的不同方向, 因此, 同一碼值序列即表達邊界網(wǎng)格在該方向上的直線段。其中, 碼值序列“0404…04”表示方向直線段; 正三角單元的“1717…17”和“3939…39”分別表示與正方向夾角為 60°和 120°的直線段, 倒三角單元則相反; 序列“2828…28”近似地表示方向上的直線段。

與之相比, 四邊形 Freeman 鏈碼 F8 可檢測水平、垂直以及對角方向的直線段, 這個差異是由不同類型網(wǎng)格的鄰域關(guān)系決定的。

2)將鏈碼視為一個自然數(shù), 將其中各個碼值按某一個方向循環(huán), 使其構(gòu)成的自然數(shù)值最小, 這個過程就是歸一化。圖 7 中, F12 歸一化后為 08479 ABB9263283246465634477828266A0B109BA0B。

2.2 RDCC 和 VCC 特性分析

RDCC 的幾何特性主要包括可檢測直線段、與起始點無關(guān)、旋轉(zhuǎn)不變性、翻轉(zhuǎn)不變性以及方便計算曼哈頓距離下的輪廓周長。

1)由于外輪廓前進的相對方向無變化即為直線段, 因此根據(jù) RDCC 的定義, 直線段由序列“00…0”表示, 但與 F12 不同, 通過 RDCC 無法判斷直線段方向。

2)RDCC同樣可以通過歸一化來保證鏈碼結(jié)果與起始點無關(guān)。例如, 圖 9 中 RDCC 歸一化后結(jié)果為 00121222341102143021011140200433232021023121 202011。

3)經(jīng)旋轉(zhuǎn)或翻轉(zhuǎn)等操作后, 輪廓前進的相對方向不會發(fā)生改變, 因此, RDCC 具有旋轉(zhuǎn)和翻轉(zhuǎn)不變性。

4)用曼哈頓距離表示的輪廓周長即為邊界網(wǎng)格在外輪廓線上的邊數(shù)之和, 這也與其頂點數(shù)相同。因此, RDCC 的總碼數(shù)即為輪廓周長。

VCC 也是基于形狀外輪廓各頂點的屬性得到, 與輪廓前進的絕對方向無關(guān), 因此 VCC 的幾何特性與 RDCC 相同。

2.3 EACC 特性分析

EACC 的幾何特性包括可檢測直線段、與起始點選擇無關(guān)、旋轉(zhuǎn)以及翻轉(zhuǎn)不變性, 并能計算輪廓周長。

1)當外輪廓邊數(shù)與內(nèi)部網(wǎng)格數(shù)均為 1 時, 對應(yīng)邊界上的直線段, 此時碼值序列為“22…2”。但是, EACC 無法檢測不同方向的直線段.

2)通過歸一化, 可以實現(xiàn)鏈碼結(jié)果與起始點選擇無關(guān)。例如, 圖 12 中 EACC 的歸一化編碼結(jié)果為00031211443621201602021210011020224411012071201。

3)旋轉(zhuǎn)與翻轉(zhuǎn)操作不會改變邊界網(wǎng)格的外輪廓邊數(shù)及內(nèi)部網(wǎng)格數(shù), 因此 EACC 具有旋轉(zhuǎn)和翻轉(zhuǎn)不變性。

4)EACC 同樣能夠計算形狀的輪廓周長。根據(jù)EACC 的定義, “0”~“3”表示邊數(shù)為 1 的情況, “4”~ “7”表示邊數(shù)為 2 的情況, 因此其周長可以表示為+2×(?),表示值小于 4 的碼數(shù),為總碼數(shù)。

通過比較發(fā)現(xiàn), 3 種基于邊界網(wǎng)格外輪廓頂點或邊的鏈碼方法 RDCC, VCC 與 EACC 幾何特性相似, 而 F12 的特性相對較少。

3 表達能力與壓縮率比較

鏈碼研究的一個重要方向是鏈碼壓縮方法。針對四邊形鏈碼, 有多種無損壓縮方法[14-17]。不同鏈碼方法在表達效率和壓縮性能上存在較大的差異, 選擇表達能力較強或壓縮率較高的鏈碼, 有利于進一步的壓縮和優(yōu)化。

3.1 表達能力比較

鏈碼的表達能力可以通過每個邊界網(wǎng)格所需的平均碼數(shù)g來反映。對于 F12 和 EACC, 正常情況下每個碼均對應(yīng)唯一一個邊界網(wǎng)格(g=1)。每個三角形邊界網(wǎng)格的頂點數(shù)且可能為 1~3 (g≥1), 因此RDCC 和 VCC 的表達效率低于前兩種鏈碼。

為量化地比較 F12, VCC, RDCC 和 EACC 的表達能力和壓縮率, 本文選取 12 個不同類型的形狀進行實驗, 結(jié)果如圖 14 所示。

將這些形狀在三角形網(wǎng)格中進行離散化, 分別統(tǒng)計 4 種方法得到的鏈碼總碼數(shù)、均值以及平均碼數(shù)g, 結(jié)果如表 1 所示?？梢钥闯?EACC 和 F12 的碼數(shù)最少, 部分實驗中 EACC 的碼數(shù)略高于 F12。這是由 EACC 進行碼值組合的替換產(chǎn)生的, 總體上兩者表達效率最高; RDCC 和 VCC 的表達效率相同,g=1.28, 即平均需要 1.28 個碼來表達一個邊界網(wǎng)格。實驗結(jié)果驗證了前面對各鏈碼表達能力的分析結(jié)果。

圖14 實驗中用到的形狀

表1 不同方法得到的鏈碼總碼數(shù)

3.2 壓縮率比較

四邊形網(wǎng)格鏈碼及其壓縮方法的壓縮率一般指與 F8 鏈碼的總比特數(shù)之比。鏈碼的壓縮性能也可以通過總比特數(shù)與總邊界網(wǎng)格數(shù)之比來衡量, 這一比值稱為平均位數(shù)g。對于三角形網(wǎng)格鏈碼, 本文采用該指標進行對比分析。

根據(jù)前面的分析, F12 鏈碼共需要 12 個碼值, 因此每個碼值占 4bit 空間; RDCC 和 VCC 均有 5 個碼值, 因此各需要 3 bit; EACC正好有 8 個碼值, 平均位數(shù)同樣為 3。根據(jù)“碼數(shù)-位數(shù)”的轉(zhuǎn)換關(guān)系, 由表 1 直接得到對應(yīng)的以 bit 為單位的鏈碼總長度, 并基于實驗結(jié)果統(tǒng)計平均位數(shù)g, 結(jié)果如表 2 所示。可以看出, F12 雖然表達效率高, 但由于碼值過多, 平均每個碼需要 4bit 表示, 壓縮性能最低; RDCC和 VCC 的碼數(shù)比 F12 多 28%, 但由于每個碼占用位數(shù)更少, 整體壓縮率略高于 F12, 為 0.955; EACC的平均碼數(shù)和平均位數(shù)均最小, 與 F12 相比, 其壓縮率僅為 0.75, 同時具有表達效率和壓縮性能的優(yōu)勢。

表2 不同方法得到的鏈碼總長度(bit)

4 結(jié)語

對典型鏈碼方法的分析表明, 只有 Freeman 鏈碼能夠擴展應(yīng)用于三角形網(wǎng)格中, 但 VCC 對三角形網(wǎng)格形狀邊界角相鄰的表達存在缺陷。本文提出 3 種適用于三角形網(wǎng)格的鏈碼方法: 首先, 針對兩種不同的三角形單元類型, 分別設(shè)計 12 方向 Free-man 鏈碼, 使其盡量保持相對一致; 然后, 基于外輪廓前進方向的相對變化特性, 提出相對方向鏈碼; 最后, 基于外輪廓上邊界網(wǎng)格的邊數(shù)及內(nèi)部網(wǎng)格數(shù), 得到三角形網(wǎng)格的邊角鏈碼。分析 3 種鏈碼方法的幾何特性, 并通過實驗比較其表達能力和壓縮率。結(jié)果表明, 3 種鏈碼方法均能準確完備地對三角形網(wǎng)格形狀邊界進行表達, 其中邊角鏈碼的每個邊界網(wǎng)格平均僅需要一個碼值來表達, 壓縮率達 0.75, 表達能力和壓縮性能均最優(yōu)。

[1]Freeman H. On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Com-puters, 1961, 10(2): 260-268

[2]Bribiesca E. A new chain code. Pattern Recognition, 1999, 32: 235-251

[3]Sánchez-Cruz H, Rodríguez-Dagnino R M. Compres-sing bi-level images by means of a 3-bit chain code. SPIE Optical Eng, 2005, 44(9): 1-8

[4]Sánchez-Cruz H, Bribiesca E, Rodriguez-Diagnino M A. Efficiency of chain codes to represent binary ob-jects. Pattern Recognition, 2007, 40(6): 1660-1674

[5]Borut ?, Mongus D, Liu Y K, et al. Unsigned man-hattan chain code. Journal of Visual Communication and Image Representation, 2016, 38: 186-194

[6]Jain J, Sahoo S K, Prasanna S M, et al. Modified chain code histogram feature for handwritten charac-ter recognition // Advances in Computer Science and Information Technology, Networks and Communica-tions, Berlin: Springer, 2012: 611-619

[7]Ema R, Supriana I, Khodra M L. Bag-of-shapes descriptor using shape association based on Freeman chain code. Journal of Theoretical and Applied Infor-mation Technology, 2017, 95(5): 1142-1153

[8]Lee D, Kim S J. Modified chain-code-based object recognition. Electronics Letters, 2015, 51(24): 1996-1997

[9]Karczmarek P, Kiersztyn A, Pedrycz W, et al. An application of chain code-based local descriptor and its extension to face recognition. Pattern Recognition, 2017, 65: 26-34

[10]Madenda Y S, Prasetyo E. Object feature extraction of songket image using chain code algorithm. Interna-tional Journal on Advanced Science, Engineering and Information Technology, 2017, 7(1): 235-241

[11]Tawfiq A. Asadi A, Joda F A. Removing spatial re-dundancy from image by using variable vertex chain code. European Academic Research, 2014, 2(1): 179-192

[12]Ren M, Karimi H A. A chain-code-based map mat-ching algorithm for wheelchair navigation. Transac-tions in GIS, 2009, 13(2): 197-214

[13]劉志坤, 夏清濤. 無線傳感器網(wǎng)絡(luò)三維覆蓋策略研究. 武漢理工大學學報(交通科學與工程版), 2013, 37(3): 581-584

[14]Liu Y K, Zalik B. An efficient chain code with Huff-man coding. Pattern Recognition, 2005, 38(4): 553-557

[15]于國防, 王莉. 壓縮型頂點鏈碼的研究. 中國圖象圖形學報, 2010, 15(10): 1465-1470

[16]Sánchez-Cruz H. Proposing a new code by conside-ring pieces of discrete straight lines in contour shapes. Journal of Visual Communication and Image Repre-sentation, 2010, 21(4): 311-324

[17]?alik B, Mongus D, ?alik K R, et al. Chain code compression using string transformation techniques. Digital Signal Processing, 2016, 53(6): 1-10

Study on Chain Code Methods for Triangular Grids

WEI Xiaofeng1,2,?, GENG Zexun3, PU Guoliang1, WANG Deyong3

1. College of Engineering, Peking University, Beijing 100871; 2. Troop 96633, Beijing 100096; 3. Pingdingshan University, Pingdingshan 467000; ? E-mail: weixiaofeng@pku.edu.cn

Only vertex chain code can be applied to triangular grids, but it has defect in angle adjacent expression. Aimed at the problem of object border representation in triangular grid, three novel chain codes were proposed and compared in character and performance. Firstly, Freeman chain code was extended to triangular grids. For two different triangular elements, the corresponding 12-direction Freeman chain code encoding rules were designed respectively. Secondly, based on the relative direction changes of the contour, the relative direction chain code was proposed. Finally, the edge chain code could be obtained by differentiating the combinations of edges number and internal grids number of the boundary grids. The geometric properties, expressive abilities and compression ratios of three novel chain codes were compared and analyzed. Experiments show that the proposed methods can accurately and completely realize the shape boundary expression of triangular grids. Among them, edge chain owns the best performance, the average code number per grid is 1, and compression ratio can reach 0.75.

triangular grid; Freeman chain code; edge angle chain code; compression ratio

10.13209/j.0479-8023.2019.116

國家重點研發(fā)計劃(2017YFB0503700, 2018YFB0505300)、高分辨率對地觀測系統(tǒng)重大專項(11-Y20A02-9001-16/17, 30-Y20A01-9003-16/17)和國防科技創(chuàng)新特區(qū)項目(17-H863-01-ZT-005-015-02, 17-H863-01-ZT-005-022-01)資助

2018-11-20;

2018-12-22