基于圖像森林變換的灰度目標周長估算

方盛，梁久禎，賈靚，侯振杰，許艷

(常州大學 信息科學與工程學院，江蘇 常州 213164)

基于圖像森林變換的灰度目標周長估算

方盛，梁久禎，賈靚，侯振杰，許艷

(常州大學 信息科學與工程學院，江蘇 常州 213164)

數字圖像中目標對象的周長是一個十分重要的目標形態特征，二維圖像中的目標周長估算在圖像特征提取、目標識別等方面具有十分重要的作用。目前已有的估算方法對二維灰度圖像目標邊界模糊和圖像含噪聲估算精確度不高，針對這一現狀，結合圖像森林變換(IFT)，提出基于IFT的改進的目標周長估算方法。利用IFT方法優化圖像目標厚度邊界信息來估算灰度圖像的邊界周長，從而提高周長估計的精確性和魯棒性。為了獲得圖像目標的標準周長，實驗采用人工合成的圖像。對具有不同邊界厚度的目標、含噪的圖像的目標進行周長估算實驗。提出的改進算法在圖像目標邊界模糊和含噪聲情況下所得的結果均具有較高的精確度。提出的改進的灰度周長估算方法，在模糊圖像與含噪圖像的處理中具有更好的適應性和穩定性。

特征提取；周長估計；IFT；模糊邊界；含噪圖像;灰度邊界；邊界厚度

中文引用格式：方盛，梁久禎，賈靚,等.基于圖像森林變換的灰度目標周長估算[J]. 智能系統學報， 2017, 12(3): 341-347.

英文引用格式：FANG Sheng， LIANG Jiuzhen, JIA Liang, et al. Perimeter estimation of target object boundary based on IFT[J]. CAAI transactions on intelligent systems, 2017, 12(3): 341-347.

在圖像分析領域中，二維圖像目標物體的邊界周長是一個十分重要的目標形態特征，并且在現實生活中具有廣泛的應用。一方面，目標邊界的模糊性和復雜性給計算帶來了很大的困難；另一方面，噪聲等外在因素也會干擾計算。因而，不少學者都圍繞這個問題展開了研究，探討如何精確地計算目標物體的邊界長度。目前，大部分文獻提出的方法都是基于二值圖像，即圖像中只存在表示目標和背景的兩類值。這類方法較常見的有數字化直線段片斷法(digital straight segment, DSS)[1]、最小多邊形法(minimum length polygon, MLP)[2]和基于B樣條曲線的曲線擬合方法[3-6]。這些方法估算目標周長時，雖然最終能獲得較精確的估算結果，但是需要先提取目標的邊界信息，這個過程需要將一般圖像轉換成二值圖像，在轉換過程中非二值圖像的目標邊界信息不可避免會產生丟失，最終導致估算結果的不精確。相比二值圖像，數字化灰度圖像包含的信息更加豐富[7-8]，因而直接用灰度圖像進行能使周長估算的結果更符合實際。

Sladoje和Lindblad提出了一種基于灰度圖像的高精度曲線長度估算方法，簡稱HPGL方法[9-11]。HPGL方法本身對分辨率較低和目標存在模糊的圖像的計算結果并不理想，其主要原因是對于邊界厚度超過1個像素寬度的目標邊界可能造成邊界重復計算的問題。對于這兩種情況，文獻[9]提出了一種基于圖像形態學的像素覆蓋雙閾值預處理方法，這種方法雖然避免了重復計算問題，但是沒有合理利用邊界像素信息，估算結果誤差較大。文獻[12-13]分別提出基于邊界跟蹤的BTHPGL方法和基于圖像粒的系列方法，兩類方法改進了HPGL方法在邊界模糊情況下的不足，在簡單的像素覆蓋預處理的基礎上，實現對目標周長較精確的估算。BTHPGL方法與基于圖像粒的方法在像素覆蓋數字化處理后，圖像并不能在所有情況下都排除噪聲的干擾，噪聲可能導致方法精確度下降甚至失效。并且這些方法并沒有考慮目標邊界像素之間的關系，可能導致最終估算結果精確度不高。

為了進一步提高算法的適應性和準確性，本文提出了一種基于圖像森林變換[14]的周長估算方法，將數字圖像看作包含節點和弧的圖結構，充分利用像素之間的灰度關系，優化像素覆蓋數字化后的圖像的邊界信息，結合經典的周長估算方法，得出最終的估算結果。本文設計的實驗，驗證了算法的有效性。

1 相關工作

1.1 像素覆蓋數字化

像素覆蓋數字化[9]是由文獻提出的高效的圖像分割方法。其核心思想是待分割目標中的像素所占百分比和目標所覆蓋面積通常成正比。

定義1 假定一個連續目標S?R2，投影到2維數字化網格平面上，每個網格對應一個像素pi,j,目標S的像素覆蓋數字化定義為

式中：A(X)表示集合X的面積；Z2表示2維數字化網格平面。

上述定義描述的是分配給網格像素的真實覆蓋值，而實際在計算機中處理的圖像會受灰度級限制，一般圖像處理系統中灰度共256級，因此引出下列定義。

定義2 假定一個連續目標S?R2，投影到2維數字化網格平面上，并給定一個n級的量化標準。量化級為n的目標S的像素覆蓋數字化定義為

式中?x」表示小于等于x的最大整數。

定義2將分配給網格的像素值限制在一個n級的量化數字化集合中。特別地，當n=1時表示二值圖像，n=255時表示8位的灰度圖像。由于目標與每個像素網格相交面積無法計算，式(1)、式(2)只能用于理論描述。因此本文使用文獻[10]中的雙閾值分割算法來獲得目標圖像的像素覆蓋數字化。

1.2DSS、MLP、HPGL和粒度化周長估算方法

DSS (digital straight segment)方法[1]是一種將數字曲線劃分為數字直線片段的幾何方法。該方法用數字化直線片段取代數字化邊界曲線，按一定規則使這些片段盡量長。DSS方法主要應用于具有封閉邊界的目標區域的周長計算。對于一個目標區域，把像素看作網格正方形結構，當其邊和頂點作為邊界時，只要目標區域連通，那么所求的目標區域的邊界就是閉合的。根據方向偏轉判別公式確定DSS點，然后累加相鄰DSS點的距離，得到最終周長。

MLP (minimum length polygon)方法[2]與DSS方法相似，也是一種幾何方法，其核心思想是找到最小多邊形使其包含數字化目標區域，初始化條件與DSS方法基本一致，不同的是在確定每個特征點的同時需要確定該點與該點相鄰的兩點連線的相對位置，根據這個位置確定一個凸性。最后，根據MLP點的位置和凹凸屬性累計局部線段長度，得到目標周長。

HPGL[8]方法利用數字化圖像中的灰度級信息進行邊界周長估計。與上述兩種求數字圖像周長方法相比，該方法能達到更高的計算精度和準確度。HPGL方法以半平面上直線段的長度計算理論為基礎，根據像素覆蓋數字化圖像中分配給每個像素的量化灰度值，進行局部周長估計，其局部周長計算依據公式：

式(3)可計算曲線在區間 [a,b] 上的曲線長度。

最后，對每一次局部計算求和并進行量化誤差的矯正，得到最終估算結果。HPGL方法在單像素寬度目標邊界的周長計算應用上能取得很高精度的結果。

2 結合IFT的目標周長估算

第1.1節闡述了像素覆蓋數字化的簡易方法，并用圖片直觀展示了處理效果。由圖1可知，在圖像覆蓋分割之后多獲得的圖像仍可能存在模糊現象，雖然該方法對噪聲不敏感，但噪聲的存在還是會對分割結果產生影響。從1.2節對不同周長估算方法的闡述可知，一般方法對模糊圖像不適用，而基于圖像粒的方法在確定邊界厚度時圖像中的噪聲因素會干擾算法確定的粒度大小，從而導致估算結果誤差變大。

針對在對灰度圖像像素覆蓋分割之后獲得的像素覆蓋數字化圖像可能仍存在模糊和噪聲，導致周長估算不精確的現象(見圖1)，結合經典的周長估算方法，提出基于圖像森林變換(IFT)的周長估算方法(IDSS、IMLP、IGL)。這類方法利用像素覆蓋數字化之后的目標邊界處覆蓋值與節點間的相互關系，對這些覆蓋值所代表的像素點進行優化分類，將模糊邊界轉換成清晰邊界，獲得理想的像素覆蓋數字化圖像。最后結合經典方法，估算出圖像中目標的周長。

(a)原始圖像

(b)覆蓋數字化結果

(c)圖(b)中的局部放大圖圖1 模糊圖像數字化效果圖Fig.1 Images during coverage digitalization

2.1 圖像森林變換

圖像森林變換(IFT)[12]是一種基于圖論的圖像處理方法，該方法將圖像處理問題簡化為在圖形中求最短路徑森林的統一有效方法。

對于一幅給定的二維灰度數字圖像I,圖像中的信息可表示為屬性對(DI,I)，其中DI∈Z2表示圖像域，即灰度圖像在二維空間的位置集合。向量I表示為I(p)=I1(p)∈N，其中p表示圖像中的像素，N表示非負數集合，對于每個p∈DI，I(p)表示圖像像素p所在的位置的灰度數值。

式中wxy表示節點x和y之間的弧的權值。

IFT的一般過程：進行圖像森林變換之前，將像素標簽L初始化；在變換過程中，計算每個非種子節點到種子節點的最短路徑，根據計算結果更新相應節點的L；最后，在變換結束之后，根據L的值后續處理圖像。具體的變換過程根據實際應用需求確定，變換的輸出是最短路徑的生成森林與由所有節點L值所確定的與輸入圖像對應的標簽字典，若輸入圖像是二維灰度圖像，則標簽字典是一個由L的數值填充的二維矩陣。圖2為文獻[14]作者展示的一般的算法效果。

(a)基于4鄰接表示的圖像

(b)以a、b為種子點的IFT結果圖2 圖像森林變換的實驗圖像Fig.2 IFT experiment images

2.2 基于IFT的周長估算方法

由1.1節闡述的內容可知，在對灰度圖像預處理過程中需要進行像素覆蓋數字化。而對于低分辨率與目標模糊的圖像，在進行覆蓋數字化后，其目標與背景之間可能仍存在一個過渡的像素覆蓋值過渡帶，為了獲得更加精確的周長估算結果，需要將這些覆蓋值點重新分類成目標或背景，從而獲得清晰的目標邊界。根據覆蓋像素值，計算邊界每個過渡帶的點到完全覆蓋的點(覆蓋值為1)和完全未覆蓋的點(覆蓋值為0)的最短路徑長度。若過渡帶的覆蓋點到完全覆蓋點的路徑長度小，則將其分類在完全覆蓋的點一類，否則分類給完全未覆蓋的點一類。若像素覆蓋數字化后圖像清晰，則圖像真實邊界應在覆蓋值為0和1的像素之間，否則真實邊界應在覆蓋值為0.5的像素附近。由此可以定義路徑代價函數f為

式中：px表示像素覆蓋值，即覆蓋數字化之后的新灰度值；ε表示極小的正數，用于確保路徑長度是遞增序列。為每個點對應添加一個用于記錄在變換過程中記錄當前最短路徑長度的屬性c。

為了簡化計算，記A為求像素的4鄰接像素，則A(p)表示p的4鄰接點的集合。根據以上描述，基于IFT的邊界優化算法的實現步驟如下：

1) 輸入一幅灰度圖像I,將圖像I進行簡單的像素覆蓋數字化。

2)將所有覆蓋值為0和1的點作為種子點集合S的元素。為所有點初始化標簽L,將表示目標節點的標簽初始化為0，表示背景節點的標簽初始化為1，其他覆蓋值點的標簽初始化為-1。定義隊列數據結構Q,將S中的點按序加入隊列Q,并將它們的屬性c初始化為0，將其余點的權值c屬性初始化為+∞。

3)從隊列Q中獲取隊列頭部的節點p，對它的所有鄰接節點q∈A(p)按公式(5)計算它們之間的路徑長度wpq，若wpq+cp小于q的權值cq,則將wpq+cp賦值給cq，將p的分類標簽Lp賦值給q的分類標簽Lq，將節點q也加入隊列Q。

4) 重復步驟3)直到隊列Q為空隊列。根據標簽變量L的值重新分配圖像灰度值，得到一幅目標邊緣清晰的二值圖像。

在本文的IFT方法處理過程中，以256個灰度級的圖像為例，獲得標簽集合L。按L中的標簽值生成新的圖像I′，I′中的像素值按式(6)計算：

式中：p′表示節點p對應的像素的位置；Lp表示p節點位置的標簽值；255和0表示最大灰度和最小灰度。

新的圖像為目標邊界清晰的二值圖像。該方法能消除圖像目標邊界上的噪聲對圖像目標周長產生的影響，并且確定了目標邊界的近似位置。本節算法的流程如圖3所示。

圖3 IFT算法流程圖Fig.3 The flow chart of the IFT

接下來就結合經典的方法(DSS、MLP、HPGL)，以IFT方法的處理結果作為后續算法輸入，對最后的圖像進行目標周長的估算。特別地,以變換后的圖片作為輸入圖像，結合HPGL估算周長需引入的誤差矯正參數yn，根據公式(7)[8]確定：

其中n為數字量化的級數,本文中n=1。

3 結合IFT的目標周長估算

為了驗證本文所提出的方法的準確性，對模糊圖像和含噪聲圖像目標周長估算的適應性，本節將該方法用于計算不同合成圖像的周長，并將所計算的結果與標準周長、BTHPGL方法[10]和對應的基于自適應圖像粒的ADSS、AMLP、AGL[11]方法實驗所得的結果進行比較。

實驗平臺為Intel(R) Core(TM) i5-3470M CPU @3.20 GHz RAM 8GB的PC機，64位Win7系統和MATLAB 2012b。實驗中的圖像是通過選擇適當的函數合成的簡單目標圖像，通過積分計算目標的標準周長。實驗中還進行以下操作：對圖像目標邊界進行人工加厚模糊化，選取不同的模糊核對圖像模糊，然后進行像素覆蓋數字化，用于驗證算法對模糊邊界的適應性。對圖像加入噪聲，用于驗證算法對含噪聲圖像的適應性。實驗都是以單位像素寬為單位。

3.1 模糊圖像周長實驗

實驗選取圓、弦月形、陰陽圖形的一半、正方形旋轉45°與正方形旋轉22.5°的5種形狀合成的正方形圖像，其中圓的直徑為圖像邊長的4/5，正方形邊長為圖像邊長的3/5。對每個圖形處理并分6類，名稱后綴為1的表示理想狀態的圖像，后綴為2的表示以散焦半徑為2的散焦模糊的圖像，后綴為3的表示圖像中目標物體按與水平方向成15°角以勻速直線運動方式產生5個像素寬模糊的圖像；后綴為4～6的分別表示以圖4、5所示的模糊核對原圖像進行模糊的圖像。由于DSS、MLP和HPGL方法對模糊圖像不適用，所以這里選取BTHPGL、ADSS、AMLP和AGL方法作為對比方法，本文所提出的改進方法為IDSS、IMLP和IGL。測試圖像和模糊核數據采用文獻[15-16]中的數據集，表1～5是部分實驗結果，選擇圖像規格為512×512個像素,統計的是與標準周長相對誤差的絕對值。

圖4 模糊圖像實驗數據集Fig.4 Blur image dataset

圖5 復雜模糊核Fig.5 Three complex blur kernels

Table 1 Perimeters of circle object %

表2 弦月周長估算

表3 陰陽圖形周長估算

表4 旋轉45°正方形周長估算

表5 旋轉22.5°正方形周長估算

3.2 模糊圖像實驗結果分析

圖6是實驗結果的平均相對誤差的折線圖，分析圖6和上述表格中的實驗數據不難發現，對于不同種類的模糊圖像目標周長估算使用ADSS、AMLP、AGL等方法產生的誤差很不穩定，這是由于基于圖像粒的方法適合邊界像素分布均勻的情況且經過粒度處理的圖像本身也會增加估算誤差。而基于IFT的方法總體上對周長的估算精確度更高：IDSS、IMLP方法相比ADSS和AMLP方法具有更好的穩定性，并且大部分情況下精確度更高，而IGL也比BTHPGL和AGL方法估算更加穩定，并且在對曲線的估計上精確度也更高。

圖6 模糊實驗折線圖Fig.6 Line chart of blur image

當圖像完全符合像素覆蓋數字化定義(本文中這類圖像名稱后綴為1)時，基于IFT的方法會將圖像先轉換為二值圖像，這會增加周長估算的誤差，但從表1～5中數據可以看出，誤差在可承受的范圍之內并且現實圖像經過像素覆蓋數字化后大部分情況下很難達到理想的效果。因此,可以認為基于IFT改進的周長估算方法優于基于圖像粒的方法。

3.3 復雜目標含噪圖像周長實驗

圖7 含噪圖像實驗數據集Fig.7 Noise image datase

實驗方法與3.1節中的實驗方法相同，圖片編號Pic1、Pic2、Pic3、Pic4、 Pic5和Pic6對應無噪聲、方差為0.01、0.02、0.03、0.04和0.05的圖像。表6為含噪聲的模糊圖像應用相應周長估算方法的實驗結果。

表6 含噪圖像周長估算

3.4 含噪圖像實驗結果分析

從表6的實驗數據可知，基于圖像粒的方法精確度明顯下降，分析其原理，這類方法會因噪聲的干擾，導致所求得的邊界寬度小于實際寬度，從而導致重復計算問題，求得的結果比實際大很多。基于IFT改進的方法對噪聲表現出了良好的適應性與穩定性，并且具有較高的精確度。從表7的實驗數據可以看出，基于圖像粒的方法需要根據其概率模型計算出估計的邊界寬度，從而確定粒度尺寸，計算過程耗時較多。然而基于IFT的方法雖然過程較復雜，但主要是需要輔助的數據結構，其運行速度相對很快。而BTHPGL、ADSS、AMLP等方法需要追蹤邊界，圖像中的噪聲會干擾邊界的獲取，導致估算失敗，因此未在表中列出。通過這些實驗可得出結論，本文算法相比現有的算法具有更好的抗噪性和更快的運行時間。

表7 含噪圖像周長估算時間

4 結束語

本文基于IFT理論，結合經典估算方法，提出具有高精確度和廣泛適應性的灰度目標邊界周長估算方法。該方法繼承了經典方法的高精確度，并且對模糊圖像具有適應性，解決了圖像在模糊情況下的周長難以估算問題。因此本文方法能達到良好的精確度、適應性和穩定性，在實際圖像特征提取中能得到廣泛應用。另外,本文所設計的方法考慮的情況并不全面，算法精確度仍有提升空間。而在更復雜的情況下估算出更精確的灰度圖像目標周長，這將是今后的研究方向。

[1]ROSENFELD A. Digital straight line segments[J]. IEEE transactions on computers, 1974, 23(12):1264-1269.

[2]SLOBODA F, ZAT′KO B, FERIANC P. The minimum perimeter polygon and its application[J]. Mathematical research, 1993, 69: 59-59.

[7]KIRYATI N, BRUCKSTEIN A. Gray-levels can improve the performance of binary image digitizers[J]. CVGIP:graphical models and image processing, 1991,53(1):31-39.

[8]EBERLY D, LANCASTER J,ALYASSIN A. On gray scale image measurements: II. surface area and volume[J]. VCGIP: graphical models and image processing, 1991,53(6):550-562.

[9]SLADOJE N, LINDBLAD J. High-precision boundary length estimation by utilizing gray-level information[J].IEEE transactions on pattern analysis and machine intelligence, 2009, 31(2): 357-363.

[10]SLADOJE N, LINDBLAD J. Pixel coverage segmentation for improved feature estimation[J]. Lecture notes in computer science, 2009, 5716: 929-938.

[11]LINDBLAD J, SLADOJE N. Coverage segmentation based on linear unmixing and minimization of perimeter and boundary thickness[J]. Pattern recognition letters, 2012, 33(6): 728-738.

[12]吳秦, 周琪, 梁久禎. 灰度級信息的目標邊界精確周長估算[J]. 中國圖象圖形學報, 2014, 19(10):1449-1458. WU Qin,ZHOU Qi,LIANG Jiuzhen.Accurate perimeter estimation of target boundary based on gray-level information[J].Journal of image and graphics,2014, 19(10):1449-1458

[13]周琪, 吳秦, 梁久禎. 基于自適應圖像粒的目標對象邊界周長估算[J]. 計算機工程, 2016, 42(4):235-241. ZHOU Qi,WU Qin,LIANG Jiuzhen． Perimeter estimation of target object boundary based on adaptive image granule[J].Computer Engineering，2016，42(4):235-241.

[15]Klette R, Yip B. The length of digital curves[J]. Machine graphics and vision, 2000, 9(12): 673-703.

[16]LEVIN A, WEISS Y, DURAND F, et al. Efficient marginal likelihood optimization in blind deconvolution[C]//IEEE Conference on Computer Vision and Pattern Recognition. IEEE Computer Society, 2011, 42(7): 2657-2664.

Perimeter estimation of target object boundary based on IFT

FANG Sheng， LIANG Jiuzhen, JIA Liang, HOU Zhenjie, Xu Yan

(College of Information Science and Engineering, Changzhou University, Changzhou 213164, China)

The perimeter of a target boundary in a 2D image is an essential object feature in image analysis. It plays an important role in image feature extraction and target recognition. However, this feature is usually inaccurately estimated owing to blurred target boundaries and noise. Many reported methods do not play well in these situations. Accordingly, this study proposes an improved method for perimeter estimation based on the image foresting transform (IFT). The proposed method utilized IFT to estimate the target perimeters for different boundary thicknesses and noise. The improved algorithm proposed in this paper has higher precision for the image targets having blurred boundary and noise. The experimental results demonstrate that our improved method provides better adaptability and stability while calculating the perimeter of targets having blurred boundary and noise.

feature extraction; perimeter estimation; the image foresting transform; blur image; noise image；gray boundary; boundary thickness

10.11992/tis. 201704019

http://kns.cnki.net/kcms/detail/23.1538.TP.20170508.0922.008.html

2017-04-18. 網絡出版日期：2017-05-08.

國家自然科學基金項目(61170121).

梁久禎. E-mail: jzliang@cczu.edu.cn.

TP391.4

A

1673-4785(2017)03-0341-07

方盛，男，1992年生，主要研究方向為計算機視覺。

梁久禎，男，1968年生，教授，主要研究方向為計算機視覺。發表學術論文196篇，出版專著2部。

賈靚，男，1982年生，碩士研究生，主要研究方向為圖像分割和機器學習。