本文介绍了一种新的矢量算法,用于将河流网络或其他类似图形的多边形简化为一条条轴线,即骨架(skeleton)。该研究由美国亚利桑那大学月球与行星实验室的 E.I. Schaefer 和地球科学系的 J.D. Pelletier 共同完成,发表在 Computers & Geosciences 期刊2020年第145卷,文章编号104554,于2020年7月28日在线发表。
在地貌学研究中,经常需要将具有有限宽度的多边形地表特征(如河网)简化为线性表示,以便测量长度、弯曲度或确定河谷轴线方向。虽然对于平行边界的简单情况可以手动提取中心线,但对于复杂形态,需要一种通用、客观且可重复的算法来自动生成骨架。随着遥感数据的激增,对自动化分析的需求也日益增长。现有的栅格算法在生成骨架时往往存在锯齿状、不连续、偏离中心线或产生大量虚假分支等问题。本研究的主要目标是提出一种新的矢量算法,能够生成平滑、连续且良好居中的骨架,并提供有效的剪枝准则以去除虚假部分,同时支持尺度无关的度量。
该算法包含两个主要阶段,每个阶段都会生成一个骨架。第一阶段生成“图骨架”(graph skeleton),第二阶段将图骨架分割为若干路径,生成“分割骨架”(partitioned skeleton)。在第一阶段中,首先以用户指定的规则间隔对输入多边形的边界进行采样,然后计算这些边界样本点的Voronoi图。Voronoi图中的每个片段都是相邻两个边界样本点连线的垂直平分线。接着,需要从Voronoi图中分离出构成合理骨架的片段集合。具体做法是:首先删除连接相邻边界样本点的边缘Voronoi片段;然后生成一个代理多边形(proxy polygon),其顶点为边界样本点;测试每个Voronoi片段交汇点(即枢纽,hub)是否位于代理多边形内部。拥有最多内部枢纽的图被选为“候选图骨架”。如果候选图骨架中有枢纽位于代理多边形外部,算法默认会失败,但用户可以选择启用一种名为“切割”(cutting)的启发式处理,移除这些外部枢纽及其相连片段,然后重复候选图骨架识别步骤,最多进行两次切割。这一阶段的关键在于通过代理多边形来更好地区分骨架及其补集,尤其是在输入多边形局部欠采样的情况下。
第二阶段开始时,利用Dijkstra算法对图骨架进行图遍历求解,计算每对节点之间的最短路径。默认情况下,两端均为端节点(stub)的最长路径被指定为“主干”(trunk)并被优先分割出来。然后,在主干的两个端节点处添加“尾部”(tail),使其延伸至输入多边形的边界样本点。尾部端点的选择基于Voronoi分析中与端节点等距的三个最近边界样本点中的中间一个。随后,重新求解剩余的图骨架,将任意两个枢纽之间的路径指定为“桥”(bridge)并分割出来。再次求解后,将枢纽与端节点之间最长的长度优化路径指定为“分支”(branch)并分割出来,在分支的端节点处添加尾部。重复桥和分支的查找步骤,直到图骨架被完全分割完毕。
为了剪除不重要的分支,算法引入了一种名为“归一化长度”(normalized length)的剪枝准则。归一化长度定义为分支(包括其尾部)的长度除以该分支茎部(即枢纽端)处输入多边形近似宽度的一半。分支长度由坐标直接计算,宽度则估计为茎部节点到最近边界样本点距离的两倍。归一化长度值接近1的分支通常跨越了局部半宽度,重要性较低;值越大,分支越重要。用户可指定最小归一化长度阈值,低于该阈值的分支及其依赖的分支或桥都会被剪除,以确保最终骨架的连通性。该准则近似尺度无关,且计算高效。
针对大规模数据集在精细采样间隔下内存占用过大的问题,算法还实现了一种称为“模板化”(templating)的启发式方法。该方法先在较粗采样间隔下生成一个带尾部的图骨架作为“模板”骨架,然后在较细采样间隔下生成第二个图骨架。将模板骨架的每个带尾端匹配到精细骨架中最近的端节点,删除精细骨架中匹配到未匹配端节点的边及其端节点,最终得到一个“混合”骨架。混合骨架旨在保留模板骨架的拓扑完整性,同时获得精细骨架更高的位置精度和平滑度。
研究通过与三种当前地貌学中常用的栅格算法——Zhang和Suen细化算法、RivWidthCloud以及DeepRiver——在四个实验中进行对比来验证本算法的性能。前三个实验使用分形二叉树的多边形缓冲区作为输入,分别采用恒定缓冲区、可变缓冲区和可变缓冲区加噪声。第四个实验使用阿拉斯加育空河一段高度辫状的河段。对于Zhang和Suen算法,使用scikit-image库中的实现;RivWidthCloud分别生成无分支移除和默认500像素分支移除两种骨架;DeepRiver采用伪概率阈值0.4并利用滑动窗口处理。本算法则分别生成无最小归一化长度和最小归一化长度为2的两种骨架,定量分析中仅使用后者。
在恒定缓冲区实验中,本算法生成的骨架通常最平滑且最接近源树,而DeepRiver骨架偏差最大且存在数百处不连续,导致23个分支被消除或严重缩短,E-W方向分支受影响尤为显著。RivWidthCloud的500像素分支移除消除了大多数第八和第九代分支,并截断了主干。本算法的骨架在末端附近产生分叉的短枝,这些虚假边的归一化长度均小于1.34,而合法分支的归一化长度均大于2.55。在可变缓冲区实验中,DeepRiver完全缺失主干、第一代分支和两个第二代分支,且其高伪概率脊在宽区间内明显偏离中心线。RivWidthCloud的分支移除再次影响第八和第九代分支。本算法的虚假边呈射线状集中在主干基部和大多数交叉口附近,其归一化长度均小于1.39,合法分支均大于3.67。在可变缓冲区加噪声实验中,所有骨架对噪声引起的曲折进行了圆滑处理,导致总长度约减少7–9%。DeepRiver仍有大量元素缺失或缩短,RivWidthCloud分支移除影响范围有所减小但也波及部分低代分支。本算法的虚假边同样呈射线状分布,但局部仅出现在交叉口的一侧。所有虚假边的归一化长度均小于1.39,合法分支均大于2.51,仅12个第九代分支在茎部合并的合法分支归一化长度低于4.59。归一化长度在1.39与2.51之间存在明显间隙,有效区分了虚假边与合法分支。
在育空河实验中,Zhang和Suen骨架存在大量虚假边且锯齿状明显,其边缘通常沿NE-SW或NW-SE方向,导致平滑弯曲辫状河道上出现突然的方向变化。RivWidthCloud骨架存在大量不连续,导致部分拓扑重要的区间被截断或孤立,500像素分支移除后总长度几乎减半。DeepRiver在约200米宽的河道中伪概率峰位于中心但时断时续,骨架因此不连续;在显著宽于200米的河段,高伪概率脊常沿两岸分布且低于阈值,骨架缺失。本算法生成的骨架中虚假边通常归一化长度小于2,且分布沿区域区间而非局部射线束状。模板化和切割的联合使用使得该骨架对小于约15米的边界不规则性不敏感,但少数极端情况下突出部分被截断达约50米。与RivWidthCloud骨架相比,本算法骨架与RivWidthCloud带分支移除的骨架非常接近,98.0%的前者位于后者1米范围内。此外,本算法骨架不可避免地终止于输入区域边界,而其他栅格算法骨架通常不延伸至边界。
讨论部分深入分析了观察到的骨架行为的原因。二叉树交叉口处骨架交叉点相对于树交叉点的远端偏移源于中轴定义中最大内切球(maximal inscribed ball)的几何特性,即骨架需通过填充交叉口的最大内切球中心。末端附近的分叉现象同样由局部最大内切球的漏斗效应解释,其吸引Voronoi片段趋向多边形角点。相对平滑性方面,本算法得益于矢量表示和更连续的边界几何映射,而栅格算法受限于像素分辨率和离散邻域运算。不连续的产生源于RivWidthCloud和DeepRiver中的阈值处理,DeepRiver对宽度的敏感性可能与其训练集最大宽度(255像素)有关,超过该宽度时伪概率脊偏离中心且骨架缺失。虚假边源于多边形顶点对Voronoi片段的吸引,剪枝因此成为地貌学骨架化的必要步骤。归一化长度在第三个实验中成功区分了4651条虚假分支(66.7%总骨架长度,值均<1.39)和495条合法分支(绝大多数值>4.59),显示出强大的区分能力。文中还指出,尽管切割和模板化启发式方法可能导致局部拓扑改变或截断,但它们通常能有效工作,如成功保留了超过500米长、宽度普遍小于30米的尖顶状突出部的拓扑结构。
本研究的结论包括:第一,所描述的矢量算法能够生成同时平滑且连续的骨架,优于三种对比的栅格算法;第二,新颖的归一化长度准则为地貌应用中去除不期望的骨架成分提供了非常有用的度量;第三,对于河流多边形,归一化长度可近似理解为河流长度与其汇入河流半宽的比值;第四,内置启发式方法显著促进了含噪声或复杂多边形的骨架化,但可能导致伪影。
本研究的亮点在于提出了一种基于Voronoi图的矢量骨架化算法,其生成的骨架平滑、连续且良好居中,避免了栅格算法常见的锯齿和不连续问题;同时引入尺度无关的归一化长度剪枝准则,能够有效区分虚假边与合法分支,显著优于传统的基于长度的剪枝方法;此外,算法仅需两个参数(采样间隔和剪枝阈值),易于使用和复现。该算法已作为开源Python包Numgeo实现,无商业依赖,可在https://github.com/eischaefer/numgeo获取,具有较高的实际应用价值。