基于Delaunay三角网的边缘检测

1、背景介绍

      Delaunay三角网是一种在平面上对一组点构造三角网格的方法，其中任何点都不在由其周围点形成的任何三角形的外接圆内部。这种方法确保了三角形尽可能接近等边三角形，从而避免了狭长的三角形。如下图所示，为利用平面上点集构建生成的 Delaunay三角网，包括若干个三角形，而每个三角形所处位置不同，比如有的位于三角网边缘处，有的位于内部。因此，根据这一特性，可以根据Delaunay三角网进行边缘检测，实现效果如右图所示，其将边缘点连接起来线段。

2、Delaunay属性及边界点提取原理

      python中专门构建Delaunay的第三方库，在scipy库中。生成的三角网，其包括2类属性：三角形顶点索引、近邻三角网索引。

2.1 三角形顶点索引

      三角形顶点索引是记录组成三角形顶点，在原始点中的序列号。如下图所示，总共5个点，编号分别为0、1、2、3、4。Delaunay共生成4个三角。那么三角形索引，则是记录每个三角形中三个顶点，由这5个顶点中哪3个顶点组成。可知：

三角形 1：4 1 0

三角形2:    4 2 1

三角形3： 4 1 3

三角形4:    4 2 3

2.2 三角形邻域信息

      三角形邻域信息，则是记录与该三角形相邻的信息。上述Delaunay三角网的三角形邻域信息如下。对于非零数字，表示与之相邻的三角形，其索引号；对于-1数字，则表明没有邻域三角形与之对应。

第一行[1, 3, -1]表示第一个三角形的邻域信息

• 第一个邻域三角形的索引是1
• 第二个邻域三角形的索引是3
• 第三个边没有邻域三角形（因为它位于整个Delaunay三角剖分的边界上），所以标记为-1

  第二行[0, 2, 3]表示第二个三角形的邻域信息：

• 第一个邻域三角形的索引是0
• 第二个邻域三角形的索引是2
• 第三个邻域三角形的索引是3

Neighbors: [[1, 3, -1],
            [0, 2, 3],
            [1, 3, -1],
            [0, 1, 2]]

3.3 基于Delaunay三角网提取边缘点原理

        因此，根据上述介绍，可以采用如下步骤提取边缘点：对于每个三角形，对其每个邻域信息进行判断。若邻域信息中存在-1，则表明该三角网中存在边界边。将边界边提取出来，即可实现边缘点提取。

3、代码测试与结果分析

    本程序基于python代码进行编写，在pycharm平台上进行运行，结合三方库scipy中Delaunay构建三角网。源代码下载链接：​​​​​​https://download.csdn.net/download/qq_32867925/89562829

 3.1  简单图形测试

     使用5个点构成的简单图形进行测试，测试结果如下图所示。5个点共生成4个三角形，提取的边界点连接，生成的多边形如右图，提取效果比较理想

Delaunay三角网	边界点连接成的边（红色）

 3.2  简单图形测试

       随机生成100个平面点，生成的三角网如下。利用提取的边界点，生成的边界边效果还算比较理想。

Delaunay三角网	边界点连接成的边（红色）

4、总结

     介绍了利用Delaunay三角网提取点云边缘的原理，并给出测试结果。