任意形狀林業目標物的像素級自動標注算法

陳瑞園，楊緒兵，范習健，張 禮，業巧林

南京林業大學信息科學技術學院，南京210037

截至第九次森林資源清查（2014—2018年），全國現有森林面積2.2 億公頃，森林蓄積量175.6 億立方米，而我國當前森林覆蓋率僅為22.96%，遠遠低于全球30.6%的平均水平[1]，且存在地區分布不均的問題。為了提高森林資源調查的作業效率，引入了衛星遙感影像、機載雷達和無人機成像等信息化技術。現有的技術主要集中在宏觀調查方面，大量的圖像預處理工作如興趣區域選擇（ROI）、監督信息獲取、目標標定等仍主要依賴人力，且存在過度依賴于通用計算機軟件以及因處理效果不佳導致無法使用的現象[2]，而目標自動識別更是目前急需解決的難題。

ROI 是圖像預處理的重要步驟，嚴格來說，ROI 在

計算機視覺和基于對象的光學識別中是指圖像上感興趣對象的邊界。主流的定義為特定目標識別的數據集中的一組樣本，由此可將ROI定義為封閉邊界內的一組封閉像素集合。ROI 選擇關系到圖像邊界的劃分和圖像區域的分割，且其選擇質量和速度都將直接影響到后續的數據處理規模。就ROI選擇而言有很多方法，主要涉及基于幾何[3]、圖像分割[4]或檢索[5]、圖像摳圖[6]、圖像分類[7-8]和聚類[9]，基于深度學習的方法[10]等。從直觀性和可操作性來看，基于幾何的ROI選擇無疑是最簡單的方法。如文獻[3]中所述，其主要特征包括線性連通性、簡單連通性以及紋理特征、大小和形狀的相似性。常用的規則幾何形狀有圓形、三角形、矩形和多邊形等，其中基于矩形的邊界框法[11]（Bounding Box）應用最為廣泛。然而，由于Bounding Box的凸性要求，對于非剛性目標物的ROI選擇容易導致以下兩個問題：若矩形框定的面積小，則容易導致選中的興趣目標不完整；而面積過大又容易將非興趣元素誤標記為興趣目標（即噪聲），而這些錯誤的監督信息極易造成后續的標記工作錯誤甚至失效。文獻[12-15]提出了一種基于凸殼多邊形的目標分割算法，雖彌補了上述矩形框方法的不足，但受制于某些物體受限于非剛性目標物的特殊性，導致獲得的凸殼區域并非僅僅是針對興趣選擇區域。此外，對于圖像而言，判斷像素是否屬于ROI 區域，只需將像素坐標與之ROI邊界坐標比較即可，而該問題對于凸殼卻非易事。為了適應多種應用，旨在快速計算找出位于ROI的所有像素樣本，而不是像一階或二階統計量（通常以均值、中值和方差測量）等簡單的代表點。

因此，針對顏色不確定或無固定形狀的目標對象，提出了一種任意形狀興趣對象的圖像標注算法，該算法通過可視化人機交互來選擇ROI。將用戶選擇出的任意形狀ROI快速地轉化為多個凸殼區域，而對于每個凸殼與待測點集之間的位置關系都可以批量決策，且均可在線性時間內完成。然后將各個興趣區域中獲得訓練樣本使用SVDD 分類器訓練從而批量實現全圖的像素標記。

1 材料與方法

1.1 研究區

本次實驗以無人機航拍的森林高清圖像為例，研究區域是河北省造林項目的一部分，如圖1（a）所示。該航拍林地位于北緯38°59'49"至39°00'03''，東經116°02'02"至116°02'20"之間的區域，通過圖像估算該區域總面積約為13公頃。原圖是分辨率為29 988×35 547、3.95 GB的WCG84 格式TIF 圖像，為克服圖像占用內存過大從而導致的計算困難等問題，本文按2 400×2 840 大小對其進行分塊，結果如圖1（b）、（c）所示。

圖1 實驗航拍圖像及其分塊結果Fig.1 Experimental UAV aerial image and segmentation results

1.2 研究方法

1.2.1 凸殼計算方法

凸殼（convex hull）問題研究屬于計算幾何或計算機圖形學范疇。凸區域是指一組包含平面點集S中所有離散點的最小凸集，也稱為最小凸包，其邊界稱為凸殼[16]。從可視化角度，凸殼常用于二維和三維空間中的應用問題。S的凸殼是包含S中所有點的最小凸多邊形。將位于凸殼上且屬于該點集的點稱為凸殼頂點（convex vertex），根據凸線性組合，凸殼內的所有離散點均可由凸殼頂點線性表出。從凸殼的構造過程可知凸殼僅需保存凸殼頂點及頂點間的序，為了方便描述，將凸殼頂點點集記為，且按下標序排列（平面上的序是指順時針或逆時針），由S的凸線性組合的張成凸區域記為conv(S)，如下式：

確定任意點與凸區域的位置關系，首先重寫式（1），以矩陣形式表示為：

其中，V=(v1,v2,…,vl)，λ=(λ1,λ2,…,λl)T，0 和1 表示分量全為0或1的列向量。

對于空間中任一點v，它與凸殼的位置關系由方程v=Vλ的系數λ決定，即：

其中，V+是V的廣義逆。如：

對d×l階矩陣V，其秩Rand(V)≤min(d,l) 。而Rand(VTV)=Rand(V)，故VTV不可逆。因此式（3）表達式不唯一，無法得知點與殼的位置關系。本節中，先考慮任意點與凸殼的位置關系，凸殼興趣點集的計算問題分解為兩個部分，先給出單個興趣點的判定依據再考慮批量處理問題。

點與凸區域的位置關系判定，主要可分為兩步：第一步，計算凸殼中心在各邊界面（facet，二維下退化為線段）上的投影；第二步判定任意點與凸殼的位置關系。

圖2給出了該計算方法的幾何解釋。設v1,v2,…,vl表示凸殼的有序頂點，m為該凸殼的幾何中心，如圖2（a）所示。mi為中心m在邊界上的投影，如圖2（b）中所示。圖2（b）中θ為向量m-vi和向量vi+1-vi之間的夾角。為加快計算和避免計算反三角，問題求解將主要通過向量叉積實現。

圖2 點與凸殼位置關系計算示意圖Fig.2 Calculation of position relation between point and convex hull

第1步計算各邊界上投影mi

按余弦定理，有：

根據m和其投影mi的位置關系，有：

式（5）代入式（6），得式（7）：

而向量mi-vi的方向與vi+1-vi一致，將式（7）代入得：

則

由式（9）知，中心點在邊界上的投影僅僅依賴于凸殼區域邊界上的少量凸殼頂點，且計算量小。此外，由于它與任意點的位置判定無關，可在判定前完成計算。

第2步點與凸殼的位置關系判定設包含凸殼頂點vi，vi+1的第i個平面方程為：

其中，m-mi是平面法向量，x為該平面上的任一點。如圖2所示的二維問題，此時的平面退化為直線。

按點v到平面(m-mi)T(x-vi)=0 距離公式[17]，有：

當v-vi與m-mi的方向一致時，點v位于m-mi指向的半空間（正半空間），此時r大于0。反之，若r>0，則v必在正半空間。因此，若

對所有的i(=1,2,…,l)均成立，則v位于凸殼內。

由以上分析，判定規則總結如下：

（1）若對所有的i,(m-mi)T(v-vi)>0 均成立，則點v在凸殼內部。

（2）若存在某些i，使(m-mi)T(v-vi)<0 ，則點v在凸殼外部。

（3）若存在某一個j，有(m-mj)T(v-vj)=0 成立，而對其余的i(i≠j)均大于0，則點v位于凸殼邊界上。

矩陣形式表示如下，令

其中，M=(m-m1,m-m2,…,m-ml)，V=(v-v1,vv2,…,v-vl)，diag(?)表示矩陣對角化操作。

由于通常所說的凸殼區域是包含邊界的，因此對于點v，若式（13）非負（即η≥0），則v屬于該區域。對比式（3）可知，本文提出的方法無需考慮矩陣逆問題，且計算量主要集中在點與少數凸殼頂點的內積計算上，易于計算。

1.2.2 批量決策

以下考慮批量決策問題。設有n個待決策點，記為v(1),v(2),…,v(n)。凸殼頂點及投影符號定義同前。令U=(V(1),V(2),…,V(n)),其中V(i)=(v(i)-v1,…,v(i)-vl),i=1,2,…,n。記AT=(M,M,…,M)，計算：

算法1 凸多邊形區域興趣點集的快速選擇算法

輸入：有序凸殼頂點集S={v1,v2,…,vl}；待決策的興趣點集P={v(1),v(2),…,v(n)}；

輸出：位于凸區域內的興趣點集P。

1. 計算區域中心m，并按式（9）獲得它在殼上的投影mi。

2. 按式（13），計算矩陣M和V。

3. 構造矩陣U，按式（14）計算決策向量η′，實現批量決策。

4. 檢索η′中的負分量并記錄其位置，按轉換關系式t=■(k-1)/l■+1，從集合P中移除負分量對應的興趣點并返回P。

2 任意形狀ROI像素快速標記算法

2.1 興趣區域選擇

興趣區域（ROI）選擇是圖像預處理的重要步驟，ROI選擇的質量和速度將直接影響到圖像邊界的劃分、圖像區域的分割以及后續數據處理的規模。ROI 選擇方法有很多種，基于區域幾何形狀確定邊界的方法最為直觀，常用規則形狀如圓形、三角形、矩形和多邊形等，其中矩形或基于矩形的窗口法應用最為廣泛，上文的邊界框法（Bounding Box）大都是基于矩形的。對于某些特定對象而言，若矩形框定的面積小，則容易導致選中的興趣目標不完整；而面積過大又容易將非興趣元素誤標記為興趣目標（即噪聲）。同樣地，凸殼（Convex Hull）方法也存在著相同的問題。

根據函數逼近理論，任意形狀區域的邊界總可以通過折線逼近，且邊界封閉時折線恰好圍成多邊形。綜上，本文提出一種基于凸殼的任意形狀多邊形方法，它能夠將目標興趣對象形狀從凸形狀擴展到任意形狀。如圖3 所示，考慮到林業目標物的無固定形狀的特性，優先選取輪廓清晰且與其他區域分離的區域，在ROI相同的前提下，本文方法能最大程度上貼合ROI 的形狀，從而達到減少噪聲的目的。

圖3 三種ROI選擇方法對比圖Fig.3 Comparison of three ROI selection methods

2.2 任意形狀ROI分解

任意形狀ROI的分解過程包括以下兩點：一是快速檢測邊界上的凹點；二是根據檢測到的凹點將任意形狀的多邊形區域分解為多個凸殼區域，然后分別對每個凸殼區域進行計算。任意形狀多邊形的有序頂點仍記為S={v1,v2,…,vl}，與其對應的凸殼記為conv(S)。由式（14），計算S中的頂點與封閉邊界conv(S)之間的位置關系，可快速獲悉哪些頂點為凹點（位于凸殼內部的點），如圖4中黑色“o”表示的點，黑色虛線的集合即為分解結果（分解規則不做贅述）。最后，同樣按上述方法獲取分解后的每個凸區域的點集，并以上過程總結為算法2。

圖4 任意形狀ROI分解結果Fig.4 Arbitrary-shaped ROI decomposition results

算法2 任意形狀區域的興趣點集選擇算法

輸入：有序頂點集S={v1,v2,…,vl}；

輸出：選定區域興趣點集P。

1. 計算S的凸殼，記為conv(S)。

2. 按式（14），獲得位于凸殼內部的凹點集S′。

3. 按凸分解原則，將之分解為K個凸區域。

4. 調用算法1，獲得每個凸區域的興趣點集Pi并返回P=?Pi。

2.3 單分類像素標注

一幅含有K個目標的數字圖像，可由如下模型表示：

其中，z表示圖像像素，P(ωi)和p(z|ωi)為第i類目標的先驗概率和條件概率密度。對于RGB 圖像，像素z=(r,g,b)′。按圖像成像原理，各通道上的顏色分量彼此獨立，即：

以單分類圖像為例，如圖5 所示，圖5（b）是圖5（a）中ROI的像素提取，圖5（c）為其像素分布。為方便可視化，像素分布分別在RGB 三個顏色通道上展開。由文獻[18]知同類對象的像素分布通常是單峰的，如圖5（d）所示，目標“樹”的像素總體趨勢呈單峰分布。

圖5 RGB通道中選定ROI的像素分布和概率密度估計Fig.5 Pixel scatters and probability density estimations of selected ROI in RGB channels

通過提取的任意形狀ROI內像素，通過SVDD分類器[19]對其訓練，進而實現全圖的分類識別。此算法的思想是判斷任意點的像素值是否與ROI 內像素值相近進而判定是否屬于同類別，判斷方法通過確定點與凸殼的位置關系。

3 結果與分析

3.1 算法驗證及性能評估

以ROI 選擇方法（Bounding Box 或Convex Hull）、圖像分割以及圖像摳圖作為本次實驗的基準：（1）對于ROI 選擇方法，在基于像素且保證ROI 相同的前提下，在選定的興趣區域樣本上分別采用SVDD 方法訓練并用它進行目標檢測；（2）對于圖像分割方法，在監督下對用戶提供的ROI進行Otsu圖像分割，并從中選出離給定興趣區域最近的分割區域；（3）而對于圖像摳圖，每個trimap圖像構建在三個區域上，依據用戶提供的ROI及其凸包進行分割。

另外，可視化方法雖直觀，但主觀因素較重，加之個人喜好不同，判斷標準存在差別，這在一定程度上會增加評判的不確定性。為客觀評價，引入目標檢測率（TP：真陽性）和錯誤檢測率（FP：假陽性）來評估目標檢測精度[20]，而不是分類精度這樣的單一指標。另外，由于該應用問題沒有可用的ground-truth，實驗中采用文獻[21]的像素級圖像標注方法的結果作為此實驗的ground-truth，并為算法性能提供參考。

限于篇幅原因，隨機挑選八張分塊子圖進行對比實驗，如圖6所示，同時為了體現公平性，選擇了三張非無人機圖像。其次，為了視覺上更直觀，由于Im.1~Im.3的興趣對象為白云，所以采用像素值為（0，0，0）的黑色背景對其重組圖像進行填充，而Im.4~Im.11中由于陰影部分像素與黑色相近，采用像素值為（255，255，255）的白色背景填充。每組Im圖像從左到右、從上到下依次為：原圖、Ground-truth、ROI、Ours、Convex Hull、Bounding Box、Otsu、Matting。此外，為了視覺上更直觀，由于選取的ROI 區域相同，將三種ROI 選擇方法（Ours、Convex Hull、Bounding Box）選取的ROI 區域合并顯示在一張圖上，圖中分別用綠色、紫色、紅色突出顯示。基于圖像可以觀察出本文方法識別效果最接近于ground-truth。例如Im.1，Convex Hull、Bounding Box 以及Otsu 方法雖然也能大概識別出興趣區域（圖中顯示為白色云朵），但其中夾雜著大量非興趣區域即噪聲數據（圖中顯示為藍色天空），而Matting方法只能提取出ROI區域內的像素。同樣，Im.5中Convex Hull、Bounding Box以及Otsu方法也未能過濾掉噪聲數據，如圖中陰影、道路、草地等。因此，視覺上可以觀察出本文方法識別效果最佳。

圖6 實驗結果對比圖Fig.6 Comparison of experimental results

從表1 可以看出五種方法中本文方法（Ours）目標檢測率（TP）值最高，其次是凸包（Convex Hull）。Ours平均TP為87.3%，比第二個高0.6個百分點，但同時可以觀察到Convex Hull 的FP 均值約為Ours FP 均值的三倍。Bounding Box 是用戶提供的ROI 方法中最簡單、最快的一種，其運行速度是其他方法的數十倍甚至數百倍，但錯誤檢測率（FP）過高，平均值為51.6%，這意味著它很難用于非剛性目標檢測。其中Matting FP 值最小為0.4%，但是它無法檢測非剛性對象，因為它可能對單個小區域對象有效，但幾乎無法將檢測擴展到外部ROI。對于所關注的Otsu圖像分割方法似乎不穩定，其TP值在97.1%到12.7%之間波動，FP也不穩定。考慮到TP和FP，毫無疑問，本文方法優于其他四種方法。

表1 與現有方法比較的數值計算結果Table 1 Comparison between our method and state-of-the-art in numeric results

3.2 結果與分析

實驗結果表明此算法主要優點在于：（1）由于算法是針對任意形狀的興趣區域，所以能夠勝任圖像中的復雜目標物提取工作；（2）由于采用的凸分解方法可將興趣目標區域選擇轉化為低階矩陣運算同時對目標區域進行批量計算，因此計算量較小；（3）從最終識別效果來看，本文使用的基于凸殼的任意多邊形方法比Bounding Box以及Convex Hull更能準確地識別出興趣區域。

最后，將每個分塊子圖的標記結果合并為與原圖大小相同，最終的無人機航拍高清圖像的全圖標記結果如圖7所示。

圖7 無人機高清航拍圖像的標記結果Fig.7 Marking results of high-definition UAV image

4 討論

本文針對圖像目標形狀的非凸性，提出了任意形狀ROI的像素自動標注算法，可將任意形狀的興趣區域轉化為多個凸區域問題處理，然后依次提取每個凸殼內的像素并進行標記。該方法無需如圖像閾值化、去噪、去陰影等圖像預處理工作，操作簡便易行。以無人機航拍的森林高清圖像為例，通過可視化標記圖像方法，對圖像中的樹木樣本實現了像素級的自動標注。當然，本文方法也有望在林冠分布、林冠顏色差異，以及林冠數量等方向進行擴展研究。

本項目的工作難點在于圖像的實時處理問題。由于前期研究的數據均為無標記，且無法考量標記結果的正確性，故本項目的實施過程中模型和算法的性能評價主要依據圖像可視化，即憑人的視覺觀察衡量實驗效果。可視化過程中耗費了較多人力和時間，需要進一步研究解決。