任意形状林业目标物的像素级自动标注算法

陈瑞园，杨绪兵，范习健，张 礼，业巧林

南京林业大学信息科学技术学院，南京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的像素自动标注算法，可将任意形状的兴趣区域转化为多个凸区域问题处理，然后依次提取每个凸壳内的像素并进行标记。该方法无需如图像阈值化、去噪、去阴影等图像预处理工作，操作简便易行。以无人机航拍的森林高清图像为例，通过可视化标记图像方法，对图像中的树木样本实现了像素级的自动标注。当然，本文方法也有望在林冠分布、林冠颜色差异，以及林冠数量等方向进行扩展研究。

本项目的工作难点在于图像的实时处理问题。由于前期研究的数据均为无标记，且无法考量标记结果的正确性，故本项目的实施过程中模型和算法的性能评价主要依据图像可视化，即凭人的视觉观察衡量实验效果。可视化过程中耗费了较多人力和时间，需要进一步研究解决。