使用OpenCV進(jìn)行Delaunay三角剖分和Voronoi圖

?

圖1：左圖奧巴馬總統(tǒng)使用dlib檢測到標(biāo)志點伏嗜，中間Delaunay三角剖分的標(biāo)志點酪惭，右圖：相應(yīng)的Voronoi圖

? ? 在面部標(biāo)志的眾多應(yīng)用中，首先發(fā)現(xiàn)面部地標(biāo)的三角測量（參見圖1）椒丧，并且這些三角形被扭曲來一些有趣的事情土涝。這篇文章將幫助我們理解Delaunay三角剖分和Voronoi圖（又名Voronoi tesselation，Voronoi分解濒憋，Voronoi分區(qū)和Dirichlet曲面細(xì)分）何暇，并幫助我們發(fā)現(xiàn)OpenCV中幾乎沒有記錄的函數(shù)。

什么是Delaunay三角剖分凛驮？

?

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

? ?? ?給定平面中的一組點裆站，三角剖分指的是將平面細(xì)分為三角形，其中點為頂點黔夭。在圖1中宏胯，我們在左圖上看到一組標(biāo)志，在中間圖像中看到三角剖分本姥。一組點可以有很多可能的三角形肩袍，但Delaunay三角剖分因其具有一些不錯的屬性而脫穎而出。在Delaunay三角剖分中婚惫，選擇三角形使得任何三角形的外接圓內(nèi)都沒有點氛赐。圖2顯示Delaunay三角剖分的4個點A魂爪，B，C和D鹰祸。在上圖中甫窟，為了使三角剖分成為有效的Delaunay三角剖分，點C應(yīng)該在三角形ABD的外接圓之外蛙婴，并且點A應(yīng)該在三角形BCD的外接圓之外粗井。

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

圖2顯示了移動點時三角剖分如何變化以選擇“胖”三角形街图。在圖2左圖中浇衬，點B和D的x坐標(biāo)在x=1.5處，而在圖2右圖中餐济，它們向右移動到x=1.75耘擂。在圖2左圖中，角度ABC和ABD很大絮姆，并且Delaunay三角剖分在B和D之間產(chǎn)生邊緣醉冤，將兩個大角度分成更小的角度ABD，ADB篙悯，CDB和CBD蚁阳。另一方面，在圖2右圖中鸽照，角度BCD太大螺捐，并且Delaunay三角剖分產(chǎn)生邊緣AC以劃分大角度。

有許多算法可以找到一組點的Delaunay三角剖分矮燎。最明顯（但不是最有效）的是從任何三角測量剖分定血，并檢查任何三角形的外接圓是否包含另一個點。如果是這樣诞外，翻轉(zhuǎn)邊緣（如圖2所示）并繼續(xù)澜沟，直到?jīng)]有三角形的外接圓包含一個點。

任何關(guān)于Delaunay三角剖分的討論都必須包括Voronoi圖峡谊，因為一組點的Voronoi圖是其Delaunay三角剖分的數(shù)學(xué)雙重圖倔喂。

什么是Voronoi圖？

?

? ?? ? 給定平面中的一組點靖苇，Voronoi圖劃分空間席噩，使得邊界線與相鄰點等距。圖3顯示了用黑點計算的Voronoi圖的示例贤壁。你會注意到每條邊界線都穿過兩點的中心悼枢。如果連接相鄰Voronoi區(qū)域中的點，則會得到Delaunay三角剖分脾拆！Delaunay三角剖分和Voronoi圖以多種方式相關(guān)馒索。

OpenCV中的Delaunay三角剖分和Voronoi圖

給定一組點莹妒，你可以使用Subdiv2D類計算Delaunay三角剖分或Voronoi圖。這是操作步驟：

1.收集矢量中的所有點

Python：

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

2. 使用矩形（rect）定義要分區(qū)的空間绰上。如果在上一步中定義的點是在圖像上定義的旨怠，則此矩形可以是（0,0，width蜈块，height）鉴腻。否則，您可以選擇一個包含點的矩形百揭。

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

3.使用上一步中獲得的矩形創(chuàng)建Subdiv2D的實例

subdiv??= cv2.Subdiv2D(rect);

4.使用bdiv.insert（point）將點插入subdiv爽哎。上面的視頻顯示了三角測量的動畫，因為我們將細(xì)分添加到細(xì)分器一。

5.使用bdiv.getTriangleList獲取Delaunay三角形列表课锌。

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

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

這是一個完整的工作示例祈秕。我已經(jīng)從OpenCV附帶的示例中復(fù)制了一些代碼渺贤，并對其進(jìn)行了簡化和修改，以滿足我們的目的请毛。OpenCV附帶的python示例使用舊的（和丑陋的）接口志鞍，所以我從頭開始編寫它。此代碼假定圖像存儲在image.jpg中获印，點存儲在points.txt中述雾。points.txt的每一行包含由空格分隔的點的x和y坐標(biāo)街州。

import cv2

import numpy as np

import random

# 檢查一個點是否在矩形內(nèi)

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"

? ? # 當(dāng)繪制三角形剖分時打開動畫畫板

? ? animate = True

? ? # 定義繪制顏色

? ? delaunay_color = (255,255,255)

? ? points_color = (0, 0, 255)

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

? ? img_orig = img.copy();

? ? # 創(chuàng)建用于Subdiv2D 的矩形

? ? size = img.shape

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

? ? # 創(chuàng)建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)

得到的結(jié)果就是和圖1的中間圖和右圖一樣兼丰，如果想要看Dlaunay三角剖分的動態(tài)過程可以訪問這里，或者自己運行上述的代碼

openCV【實踐系列】5——使用OpenCV進(jìn)行Delaunay三角剖分

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

(出處: 易學(xué)智能)