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

fantomas

使用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：

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

复制代码

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

1. img = cv2.imread("image.jpg");
   
2. size = img.shape
   
3. rect = (0, 0, size[1], size[0])

复制代码

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

1. 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坐标。

1. import cv2
   
2. import numpy as np
   
3. import random
   
4. # 检查一个点是否在矩形内
   
5. def rect_contains(rect, point) :
   
6.     if point[0] < rect[0] :
   
7.         return False
   
8.     elif point[1] < rect[1] :
   
9.         return False
   
10.     elif point[0] > rect[2] :
    
11.         return False
    
12.     elif point[1] > rect[3] :
    
13.         return False
    
14.     return True
    
15. # 绘制一个点
    
16. def draw_point(img, p, color ) :
    
17.     cv2.circle( img, p, 2, color, cv2.cv.CV_FILLED, cv2.CV_AA, 0 )
    
18. # 绘制 delaunay 三角剖分
    
19. def draw_delaunay(img, subdiv, delaunay_color ) :
    
20.     triangleList = subdiv.getTriangleList();
    
21.     size = img.shape
    
22.     r = (0, 0, size[1], size[0])
    
23.     for t in triangleList :
    
24.         pt1 = (t[0], t[1])
    
25.         pt2 = (t[2], t[3])
    
26.         pt3 = (t[4], t[5])
    
27.         if rect_contains(r, pt1) and rect_contains(r, pt2) and rect_contains(r, pt3) :
    
28.             cv2.line(img, pt1, pt2, delaunay_color, 1, cv2.CV_AA, 0)
    
29.             cv2.line(img, pt2, pt3, delaunay_color, 1, cv2.CV_AA, 0)
    
30.             cv2.line(img, pt3, pt1, delaunay_color, 1, cv2.CV_AA, 0)
    
31. # 绘制 voronoi 图
    
32. def draw_voronoi(img, subdiv) :
    
33.     ( facets, centers) = subdiv.getVoronoiFacetList([])
    
34.     for i in xrange(0,len(facets)) :
    
35.         ifacet_arr = []
    
36.         for f in facets :
    
37.             ifacet_arr.append(f)
    
38.         ifacet = np.array(ifacet_arr, np.int)
    
39.         color = (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))
    
40.         cv2.fillConvexPoly(img, ifacet, color, cv2.CV_AA, 0);
    
41.         ifacets = np.array([ifacet])
    
42.         cv2.polylines(img, ifacets, True, (0, 0, 0), 1, cv2.CV_AA, 0)
    
43.         cv2.circle(img, (centers[0], centers[1]), 3, (0, 0, 0), cv2.cv.CV_FILLED, cv2.CV_AA, 0)
    
44. if __name__ == '__main__':
    
45.     win_delaunay = "Delaunay Triangulation"
    
46.     win_voronoi = "Voronoi Diagram"
    
47.     # 当绘制三角形剖分时打开动画画板
    
48.     animate = True
    
49.     # 定义绘制颜色
    
50.     delaunay_color = (255,255,255)
    
51.     points_color = (0, 0, 255)
    
52.     img = cv2.imread("image.jpg");
    
53.     img_orig = img.copy();
    
54.     # 创建用于Subdiv2D 的矩形
    
55.     size = img.shape
    
56.     rect = (0, 0, size[1], size[0])
    
57.     # 创建Subdiv2D 实例
    
58.     subdiv = cv2.Subdiv2D(rect);
    
59.     points = [];
    
60.     # 从 text 文件中读取点
    
61.     with open("points.txt") as file :
    
62.         for line in file :
    
63.             x, y = line.split()
    
64.             points.append((int(x), int(y)))
    
65.     # 将点依次插入subdiv中
    
66.     for p in points :
    
67.         subdiv.insert(p)
    
68.         # 展示动画画板
    
69.         if animate :
    
70.             img_copy = img_orig.copy()
    
71.             draw_delaunay( img_copy, subdiv, (255, 255, 255) );
    
72.             cv2.imshow(win_delaunay, img_copy)
    
73.             cv2.waitKey(100)
    
74.     # 绘制delaunay 三角剖分
    
75.     draw_delaunay( img, subdiv, (255, 255, 255) );
    
76.     for p in points :
    
77.         draw_point(img, p, (0,0,255))
    
78.     # 为Voronoi 图分配空间
    
79.     img_voronoi = np.zeros(img.shape, dtype = img.dtype)
    
80.     # 绘制 Voronoi 图
    
81.     draw_voronoi(img_voronoi,subdiv)
    
82.     cv2.imshow(win_delaunay,img)
    
83.     cv2.imshow(win_voronoi,img_voronoi)
    
84.     cv2.waitKey(0)

复制代码

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

网址：

https://www.learnopencv.com/delaunay-triangulation-and-voronoi-diagram-using-opencv-c-python/

Happy清子

藏着很多宝贝啊
这个内容
现在与GAN结合
火爆的一塌糊涂

shaoheshaohe

好久咩有恩关系了

shaoheshaohe

opencv是基础

shaoheshaohe

学会opencv 图像处理会了一大半

shaoheshaohe

再加上deep learning 就如虎添翼