使用OpenCV进行Delaunay三角剖分和Voronoi图

​

图1：左图奥巴马总统使用dlib检测到标志点，中间Delaunay三角剖分的标志点，右图：相应的Voronoi图

    在面部标志的众多应用中，首先发现面部地标的三角测量（参见图1），并且这些三角形被扭曲来一些有趣的事情。这篇文章将帮助我们理解Delaunay三角剖分和Voronoi图（又名Voronoi tesselation，Voronoi分解，Voronoi分区和Dirichlet曲面细分），并帮助我们发现OpenCV中几乎没有记录的函数。

什么是Delaunay三角剖分？

​

图2：有益于小角度的Delaunay三角剖分

      给定平面中的一组点，三角剖分指的是将平面细分为三角形，其中点为顶点。在图1中，我们在左图上看到一组标志，在中间图像中看到三角剖分。一组点可以有很多可能的三角形，但Delaunay三角剖分因其具有一些不错的属性而脱颖而出。在Delaunay三角剖分中，选择三角形使得任何三角形的外接圆内都没有点。图2显示Delaunay三角剖分的4个点A，B，C和D。在上图中，为了使三角剖分成为有效的Delaunay三角剖分，点C应该在三角形ABD的外接圆之外，并且点A应该在三角形BCD的外接圆之外。

Delaunay三角剖分的一个有趣特性是它不支持“瘦”三角形（即具有一个大角度的三角形）。

图2显示了移动点时三角剖分如何变化以选择“胖”三角形。在图2左图中，点B和D的x坐标在x=1.5处，而在图2右图中，它们向右移动到x=1.75。在图2左图中，角度ABC和ABD很大，并且Delaunay三角剖分在B和D之间产生边缘，将两个大角度分成更小的角度ABD，ADB，CDB和CBD。另一方面，在图2右图中，角度BCD太大，并且Delaunay三角剖分产生边缘AC以划分大角度。

有许多算法可以找到一组点的Delaunay三角剖分。最明显（但不是最有效）的是从任何三角测量剖分，并检查任何三角形的外接圆是否包含另一个点。如果是这样，翻转边缘（如图2所示）并继续，直到没有三角形的外接圆包含一个点。

任何关于Delaunay三角剖分的讨论都必须包括Voronoi图，因为一组点的Voronoi图是其Delaunay三角剖分的数学双重图。

什么是Voronoi图？

​

       给定平面中的一组点，Voronoi图划分空间，使得边界线与相邻点等距。图3显示了用黑点计算的Voronoi图的示例。你会注意到每条边界线都穿过两点的中心。如果连接相邻Voronoi区域中的点，则会得到Delaunay三角剖分！Delaunay三角剖分和Voronoi图以多种方式相关。

OpenCV中的Delaunay三角剖分和Voronoi图

给定一组点，你可以使用Subdiv2D类计算Delaunay三角剖分或Voronoi图。这是操作步骤：

1.收集矢量中的所有点

Python：

points = []# 添加每一组points.append((x, y))

2. 使用矩形（rect）定义要分区的空间。如果在上一步中定义的点是在图像上定义的，则此矩形可以是（0,0，width，height）。否则，您可以选择一个包含点的矩形。

img = cv2.imread("image.jpg");size = img.shaperect = (0,0, size[1], size[0])

3.使用上一步中获得的矩形创建Subdiv2D的实例

subdiv  = cv2.Subdiv2D(rect);

4.使用bdiv.insert（point）将点插入subdiv。上面的视频显示了三角测量的动画，因为我们将细分添加到细分。

5.使用bdiv.getTriangleList获取Delaunay三角形列表。

6.使用bdiv.getVoronoiFacetList获取Voronoi方面的列表。

Delaunay三角剖分和Voronoi图的OpenCV示例

这是一个完整的工作示例。我已经从OpenCV附带的示例中复制了一些代码，并对其进行了简化和修改，以满足我们的目的。OpenCV附带的python示例使用旧的（和丑陋的）接口，所以我从头开始编写它。此代码假定图像存储在image.jpg中，点存储在points.txt中。points.txt的每一行包含由空格分隔的点的x和y坐标。

import cv2

import numpy as np

import random

# 检查一个点是否在矩形内

def rect_contains(rect, point) :

    if point[0] < rect[0] :

        return False

    elif point[1] < rect[1] :

        return False

    elif point[0] > rect[2] :

        return False

    elif point[1] > rect[3] :

        return False

    return True

# 绘制一个点

def draw_point(img, p, color ) :

    cv2.circle( img, p, 2, color, cv2.cv.CV_FILLED, cv2.CV_AA, 0 )

# 绘制 delaunay 三角剖分

def draw_delaunay(img, subdiv, delaunay_color ) :

    triangleList = subdiv.getTriangleList();

    size = img.shape

    r = (0, 0, size[1], size[0])

    for t in triangleList :

        pt1 = (t[0], t[1])

        pt2 = (t[2], t[3])

        pt3 = (t[4], t[5])

        if rect_contains(r, pt1) and rect_contains(r, pt2) and rect_contains(r, pt3) :

            cv2.line(img, pt1, pt2, delaunay_color, 1, cv2.CV_AA, 0)

            cv2.line(img, pt2, pt3, delaunay_color, 1, cv2.CV_AA, 0)

            cv2.line(img, pt3, pt1, delaunay_color, 1, cv2.CV_AA, 0)

# 绘制 voronoi 图

def draw_voronoi(img, subdiv) :

    ( facets, centers) = subdiv.getVoronoiFacetList([])

    for i in xrange(0,len(facets)) :

        ifacet_arr = []

        for f in facets :

            ifacet_arr.append(f)

        ifacet = np.array(ifacet_arr, np.int)

        color = (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))

        cv2.fillConvexPoly(img, ifacet, color, cv2.CV_AA, 0);

        ifacets = np.array([ifacet])

        cv2.polylines(img, ifacets, True, (0, 0, 0), 1, cv2.CV_AA, 0)

        cv2.circle(img, (centers[0], centers[1]), 3, (0, 0, 0), cv2.cv.CV_FILLED, cv2.CV_AA, 0)

if __name__ == '__main__':

    win_delaunay = "Delaunay Triangulation"

    win_voronoi = "Voronoi Diagram"

    # 当绘制三角形剖分时打开动画画板

    animate = True

    # 定义绘制颜色

    delaunay_color = (255,255,255)

    points_color = (0, 0, 255)

    img = cv2.imread("image.jpg");

    img_orig = img.copy();

    # 创建用于Subdiv2D 的矩形

    size = img.shape

    rect = (0, 0, size[1], size[0])

    # 创建Subdiv2D 实例

    subdiv = cv2.Subdiv2D(rect);

    points = [];

    # 从 text 文件中读取点

    with open("points.txt") as file :

        for line in file :

            x, y = line.split()

            points.append((int(x), int(y)))

    # 将点依次插入subdiv中

    for p in points :

        subdiv.insert(p)

        # 展示动画画板

        if animate :

            img_copy = img_orig.copy()

            draw_delaunay( img_copy, subdiv, (255, 255, 255) );

            cv2.imshow(win_delaunay, img_copy)

            cv2.waitKey(100)

    # 绘制delaunay 三角剖分

    draw_delaunay( img, subdiv, (255, 255, 255) );

    for p in points :

        draw_point(img, p, (0,0,255))

    # 为Voronoi 图分配空间

    img_voronoi = np.zeros(img.shape, dtype = img.dtype)

    # 绘制 Voronoi 图

    draw_voronoi(img_voronoi,subdiv)

    cv2.imshow(win_delaunay,img)

    cv2.imshow(win_voronoi,img_voronoi)

    cv2.waitKey(0)

得到的结果就是和图1的中间图和右图一样，如果想要看Dlaunay三角剖分的动态过程可以访问这里，或者自己运行上述的代码

openCV【实践系列】5——使用OpenCV进行Delaunay三角剖分

https://bbs.easyaiforum.cn/thread-704-1-1.html

(出处: 易学智能)