计算机视觉的计算几何及Python实现
计算几何领域出现于20世纪70年代，研究解决几何问题的数据结构和算法。这其中包括，在图像上的拓扑结构的确定，或者是更高维度的表示，例如点邻域，这可以帮助推导出几何意义，例如，数字图像数据。
计算机视觉主要涉及静止或运动图像的处理、理解和重建。由于深度神经网络驱动的算法提供了令人印象深刻的超人类结果，计算机视觉在对象识别(分类)、对象检测(分类与定位)和对象分割(分类、定位与边界检测)等领域的应用越来越受到研究和行业的重视。
计算几何可以为计算机视觉领域以及与之对应的计算机图形学提供有用的概念。一组点的Voronoi图（又名Dirichlet曲面细分，Voronoi曲面细分或Voronoi分区）及其对偶的Delaunay三角剖分（又名Delone三角剖分）就是这些有用概念的例子[1,2]。相关的计算机视觉应用包括面部识别，面部变形，图像合成和表面建模。在这篇博文中，我们展示了图像中面部的Delaunay三角剖分/ Voronoi图的使用，作为面部识别或面部变形等应用的前身。
甲Voronoi图划分出域到最接近的邻域的区域为一组点。考虑点的集合P = {P 1，P 2，...，pₙ} ∈ ℝ²。定义平分线BS（pᵢ，pⱼ）的pᵢ，pⱼ ∈ P，pᵢ≠pⱼ，相对于作为等距离轨迹到pᵢ，pⱼ在距离函数d，即，BS（pᵢ，pⱼ） = { q ∈ ，P：d（ pᵢ，q）= d（pⱼ，q） }。令pᵢ的优势区域相对于pⱼ，D（pᵢ，pⱼ），表示包含pᵢ的区域由BS（pᵢ，pⱼ）界定。给定P的pᵢ的Voronoi区域定义为
并且由所有点针对于距离的pᵢ小于或等于所述距离的任何其它点pⱼ ∈ P。由一对Voronoi区域共享的边界称为Voronoi边缘。Voronoi边缘在Voronoi顶点相遇。P的Voronoi图由下式给出
其中∂ R（pᵢ，P）表示的边界R（pᵢ，P） 。术语有界Voronoi图是指VD（P）与其底层域的结合。
图1：欧几里德平面中不同点集的Voronoi图和（红色）示例点上的（蓝色）所谓的自然邻域关系
我们在欧几里得平面域限制自己来分，参见，例如，图1 Voronoi图定义可以，但是，被概括为点P获得的，而不脱离歧管噪声中号，即，更一般的情况下P ⊂ M.例如，参见图2，其中3D流形上的点的内在（非欧几里得）Voronoi图。
图2：3D流形表面上（红色）点的Voronoi图：扫描 斯坦福兔子原始（左），相等的测地距离轮廓（中心）和相应的测地线Voronoi图（右）
类似地，我们没有相对于距离函数d定义距离度量：Voronoi图定义适用于在流形M上定义的任何测地距离度量。因此，例如，在欧几里得平面域情况下，标准欧几里德距离函数可用于计算d（ ⋅，⋅ ）。
的Delaunay三角点的设定P = {P 1，P 2，...，pₙ} ∈ ℝ²通过的对偶图给出VD（P） ，与所述Delaunay三角剖分的每个边缘被带的一个边缘相关联的VD（P），即，Delaunay边缘连接VD（P）中的（自然）相邻点。有关示例，请参见图3。Delaunay三角测量通常存在于欧几里德距离度量以外的度量，但不保证存在或定义明确。
图3：欧几里德平面中（黑色）点集的（黑色）Delaunay三角剖分及其双（红色）Voronoi图
我们参考[1,2]概述了许多Voronoi图和Delaunay三角剖分变化，例如最远点和加权Voronoi图。出于我们的目的，我们可以限制自己的标准定义。我们接下来看看他们的计算实现。
我们的实施基于以下核心要素：
- Python 3（在Juypter Notebook环境中使用）
- OpenCV 3.4.4.19 wrapper package for Python
为了确定面部标志，我们使用Face ++的演示功能。
如果您更喜欢基于C ++的实现，我们建议您查看CGAL及其Voronoi和Delaunay类。这些应该将以下Python编码“转换”成C ++，相当简单。
除了OpenCV包之外，我们使用numpy进行数组处理，使用matplotlib进行可视化。
辅助函数rectContains确定一个点是否属于矩形描述的图像域，从而确定是否应该将其视为图像的Delaunay triangulation的输入。
drawPoint函数正是如此，即在输入图像img上以彩色圆的形式显示人脸landmark p。
voronoi函数使用subdiv成员函数getVoronoiFacetList获取输入图像img的voronoi图，并根据输入图像img的初始OpenCV subdivision subdiv绘制voronoi图。我们为Voronoi facet可视化设置了随机颜色方案。
同样的,delaunay函数利用subdiv成员函数getTriangleList确定并绘制输入图像img的初始化delaunay subdivision subdiv的三角形。
我们将这些函数应用于图4所示的样本图像。面部边界框和相应的面部landmark由Face ++演示应用程序生成。
该演示服务返回JSON文件，其中包含由图像域内的服务检测到的面部landmark的（x，y）坐标。上面显示了图4中输入图像的JSON提取。
图4：Face ++生成的原始样本图像（上）以及面部边界框（中）和相关的面部标志（下）
这些面部landmark坐标表示OpenCV subdivision函数的输入点。我们通过使用标准的OpenCV imread方法读入输入图像来启动展示生成。输入图像的矩形形状确定存储在rect中的细分域。标记点以“Face2Points.txt”的形式上载到点数组中。然后实例化subdivision本身，并随后通过使用subdivision insert 方法逐个插入面部landmark点来生成subdivision本身。
剩下要做的就是调用delaunay和voronoi函数来传递输入图像及其新生成的subdivision。结果如图5所示。
图5：输入图像的Delaunay三角剖分（左）及其双Voronoi图（右）
图6中的动画演示了输入图像一次一个面部landmark 的Delaunay三角剖分过程。
图6：输入图像的Delaunay三角剖分的动画
OpenCV subdiv对象提供了各种成员函数，用于检索Delaunay或Voronoi边和顶点。有关详细信息，请参阅OpenCV标准文档。这样，这些相当通用的几何结构的各种元素可以容易地传递到随后的图像处理或计算机视觉应用，例如面部分割，识别和变形。
虽然我们在本文中专注于计算机视觉应用，但请注意，这些几何结构存在许多用例，这些用例远远超出了计算机视觉领域，尤其包括应用AI的其他领域，如机器人导航。