不论是对face进行morph，还是swap，Delaunay Triangulation都是一个重要基础。其道理是，替换、变形等说到底是重新绘制，即将source的某部分经过变形绘制到target上来。就人脸来说，当然不能整个的复制过来，那样会造成图像的扭曲和失真。 Delaunay Triangulation就对人脸进行了切分，切分后形成了一个个对应的无重叠的三角区域，然后在每对之间基于仿射变换去做一些有趣的事情。

1. 什么是Delaunay Triangulation？
     给定一个平面和其上的若干点，通过某种形式地连接点，把平面切分成若干三角形，使得任一点都不在某个三角形的内部。该算法不倾向于产生“瘦小”的三角形。

   
   
   WX20190115-144015.png

2. 结合facial landmark的Delaunay Triangulation
     将人脸上68个landmark标好后，基于这些点进行Delaunay Triangulation，就能将人脸分割开，便于之后在对应三角形间进行仿射变换。

   
   
   delaunay.png
3. demo

def draw_delaunay(img, subdiv, delaunay_color ) :
    triangleList = subdiv.getTriangleList(); #do Delaunay Triangulation
    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.LINE_AA, 0)
            cv2.line(img, pt2, pt3, delaunay_color, 1, cv2.LINE_AA, 0)
            cv2.line(img, pt3, pt1, delaunay_color, 1, cv2.LINE_AA, 0)

img = cv2.imread("obama.jpg");
size = img.shape
rect = (0, 0, size[1], size[0])
subdiv = cv2.Subdiv2D(rect);
keypoints =[(a[0], a[1]) for a in  utils.get_facial_landmarks(img)]
for p in keypoints:
     subdiv.insert(p)
draw_delaunay(img, subdiv, (255, 255, 255))