本文最后更新于：2024年9月3日 晚上

平面细分(Subdiv2D)是OpenCV中一个强大的类，用于在平面上进行细分操作，并提供了一系列函数来管理和操作这些三角形。在本文中，我们将详细介绍Subdiv2D类的使用方法，并提供相关的源代码。

简介

Subdiv2D 类用于对一组 2D 点（表示为 Point2f 向量）执行各种平面细分。OpenCV 使用 Delaunay 算法对平面进行三角剖分，该算法对应于 Voronoi 图的偶图。在下图中，Delaunay 三角剖分用黑线标记，Voronoi 图用红线标记。

Delaunay 三角剖分（黑色）和 Voronoi（红色）

使用方法

实例化对象 - Subdiv2D

1
2
import cv2
subdiv = cv2.Subdiv2D (Rect rect)

这里的 rect = [x_min, y_min, x_max, y_max]

表示这个 subdiv 对象仅在这个矩形范围内有效。

  • 示例代码：

    创建一个 500x500 的平面空间对象

1
2
3
rect = (0, 0, 500, 500)
# 创建Subdiv2D 实例
subdiv = cv2.Subdiv2D(rect)

插入数据 - insert

将单个点插入到Delaunay三角剖分中。

1
subdiv.insert(Point2f pt)
  • 示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
subdiv = cv2.Subdiv2D(rect)
points = []

points.append((100, 100))
points.append((100, 200))
points.append((200, 100))
points.append((200, 200))
points.append((200, 300))
points.append((400, 400))
points.append((300, 400))

# 将点依次插入subdiv中
for p in points :
    subdiv.insert(p)

也可以插入多个点到 Delaunay 三角剖分中。

1
2
3
4
5
6
7
8
subdiv.insert([
    (100, 100),
    (100, 200),
    (200, 100),
    (200, 200),
    (200, 300),
    (400, 400)
])

查找目标最近点 - findNearest

该函数是另一个用于在子划分中定位输入点的函数。它找到与输入点最近的一个子划分顶点。

1
cv2.Subdiv2D.findNearest(pt) ->	retval, nearestPt
返回变量 含义
pt query 点
retval 返回点 ID
nearestPt 最近点
  • 示例代码：
1
2
query_point = (180, 210)
retval, nearestPt = subdiv.findNearest(query_point)

注意：我在使用这个函数的时候出现了返回点 nearestPt 坐标均为 0 的情况，个人怀疑是这个函数的 bug （opencv 4.9.0.80) ，所以碰到需要使用 nearestPt 信息的时候建议不要直接用这个函数返回的 nearestPt，而是结合 getVertex() 函数共同使用。

1
2
3
query_point = (180, 210)
retval, _ = subdiv.findNearest(query_point)
nearestPt, _ = subdiv.getVertex(retval)

这套代码我在使用时没出过问题。

返回顶点位置 - getVertex

根据顶点 ID 返回顶点位置。

1
cv2.Subdiv2D.getVertex(	vertex	) ->	nearestPt, firstEdge
  • 参数含义：
返回变量 含义
vertex 顶点 ID。
nearestPt 最近点
firstEdge 可选。连接到顶点的第一个边ID。
  • 示例代码：
1
2
3
query_point = (180, 210)
retval, _ = subdiv.findNearest(query_point)
nearestPt, edge_index = subdiv.getVertex(retval)

边的终点 - edgeDst

1
cv2.Subdiv2D.edgeDst(	edge	) ->	retval, dstpt
  • 参数含义：
变量 含义
edge 分划边 ID。
retval 点 ID
dstpt 边终点位置。
  • 示例代码：
1
2
3
4
5
query_point = (180, 210)
retval, _ = subdiv.findNearest(query_point)
nearestPt, edge_index = subdiv.getVertex(retval)

dst_index, dst_point = subdiv.edgeDst(edge_index)

边的起点 - edgeOrg

返回边的起点。

1
cv2.Subdiv2D.edgeOrg(	edge	) ->	retval, orgpt
  • 参数含义：
变量 含义
edge 分划边 ID。
retval 点 ID
dstpt 边起点位置。
  • 示例代码：
1
2
3
4
5
query_point = (180, 210)
retval, _ = subdiv.findNearest(query_point)
nearestPt, edge_index = subdiv.getVertex(retval)

org_index, org_point = subdiv.edgeOrg(edge_index)

获取边 - getEdge

返回与给定边相关的边之一。

1
cv2.Subdiv2D.getEdge(edge, nextEdgeType) ->	retval

  • nextEdgeType

    • NEXT_AROUND_ORG 线原点周围（如果e是输入边，则图片下的 eOnext）

    • NEXT_AROUND_DST 边顶点周围（eDnext）

    • PREV_AROUND_ORG 线原点周围（eRnext的反转）

    • PREV_AROUND_DST 边终点周围（eLnext的反转）

    • NEXT_AROUND_LEFT 左面周围（eLnext）

    • NEXT_AROUND_RIGHT 右面周围（eRnext）

    • PREV_AROUND_LEFT 左面周围（eOnext的反转）

    • PREV_AROUND_RIGHT 右面周围（eDnext的反转）

  • 示例代码：
1
another_edge_id = subdiv.getEdge(edge_index, cv2.SUBDIV2D_NEXT_AROUND_DST)

返回边列表 - getEdgeList

返回所有边的列表。

1
cv2.Subdiv2D.getEdgeList() -> edgeList
  • 示例代码：
1
edge_list = subdiv.getEdgeList()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
-->

[[  200.   100. -1500. -1500.]
 [-1500. -1500.   100.   200.]
 [-1500. -1500.   100.   100.]
 [  200.   200.   200.   100.]
 [    0.  1500.   100.   200.]
 [  100.   100.   100.   200.]
 [ 1500.     0.   200.   100.]
 [  100.   200.   200.   100.]
 [  100.   100.   200.   100.]
 [  100.   200.   200.   200.]
 [  400.   400.   200.   100.]
 [  100.   200.   200.   300.]
 [    0.  1500.   200.   300.]
 [  200.   200.   200.   300.]
 [  400.   400.   200.   200.]
 [  200.   300.   400.   400.]
 [ 1500.     0.   400.   400.]
 [    0.  1500.   400.   400.]
 [  200.   300.   300.   400.]
 [  400.   400.   300.   400.]
 [    0.  1500.   300.   400.]]

返回所有三角形 - getTriangleList

返回所有三角形的列表。

1
cv2.Subdiv2D.getTriangleList() -> triangleList
  • 示例代码：
1
tri_list = subdiv.getTriangleList()
1
2
3
4
5
6
7
-->
[[200. 200. 200. 100. 400. 400.]
 [200. 100. 200. 200. 100. 200.]
 [100. 200. 100. 100. 200. 100.]
 [100. 200. 200. 200. 200. 300.]
 [200. 300. 200. 200. 400. 400.]
 [200. 300. 400. 400. 300. 400.]]

返回沃罗诺伊图 - getVoronoiFacetList

返回所有沃罗诺伊面元的列表。

1
cv2.Subdiv2D.getVoronoiFacetList(idx) -> facetList, facetCenters
  • 参数列表：
变量 含义
idx 要考虑的顶点ID向量。对于所有顶点，您可以通过空向量传递。
facetList 输出向量包含Voronoi面。
facetCenters 输出向量包含Voronoi面的中心点。
  • 示例代码：
1
facetList, facetCenters = subdiv.getVoronoiFacetList([])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
facetList -->
(array([[  150., -1550.],
       [  150.,   150.],
       [-1550.,   150.]], dtype=float32), array([[  150.    ,   250.    ],
       [ -414.2857,   814.2857],
       [-2116.6667,   683.3333],
       [-1550.    ,   150.    ],
       [  150.    ,   150.    ],
       [  150.    ,   150.    ]], dtype=float32), array([[  837.8049 ,  -108.53658],
       [  450.     ,   150.     ],
       [  150.     ,   150.     ],
       [  150.     ,   150.     ],
       [  150.     , -1550.     ],
       [  683.3333 , -2116.6667 ]], dtype=float32), array([[450., 150.],
       [350., 250.],
       [150., 250.],
       [150., 150.]], dtype=float32), array([[ 350.     ,  250.     ],
       [-242.85715,  842.8571 ],
       [-414.2857 ,  814.2857 ],
       [ 150.     ,  250.     ],
       [ 350.     ,  250.     ]], dtype=float32), array([[ 350.     , 1004.5455 ],
       [ 350.     ,  250.     ],
       [ 350.     ,  250.     ],
       [ 450.     ,  150.     ],
       [ 837.8049 , -108.53658],
       [1378.5714 , 1378.5714 ]], dtype=float32), array([[ 350.     , 1004.5455 ],
       [-242.85715,  842.8571 ],
       [ 350.     ,  250.     ]], dtype=float32))

facetCenters -->
[[100. 100.]
 [100. 200.]
 [200. 100.]
 [200. 200.]
 [200. 300.]
 [400. 400.]
 [300. 400.]]

初始化 - Delaunay

创建一个新的空Delaunay细分。

1
cv2.Subdiv2D.initDelaunay(rect) -> None

  • 参数说明：

    变量 含义
    rect 包含所有要添加到分划中的二维点的矩形。

  • 示例代码：

1
subdiv.initDelaunay(rect)

定位 - locate

返回点在Delaunay三角剖分中的位置。

该函数在细分中定位输入点，并给出一个三角形边或顶点。

1
cv2.Subdiv2D.locate(pt) -> retval, edge, vertex

  • 参数说明：

    变量 含义
    pt 要定位的点。
    edge 输出点所属的边或位于其右侧的边。
    vertex 可选输出顶点，如果输入点与该顶点重合。

  • 示例代码：

1
retval, edge, vertex = subdiv.locate([88,88])

  • 返回：

    一个整数，指定以下五种位置情况之一点位置

    • 点落在某个面片内。此函数返回PTLOC_INSIDE，且edge将包含面片的边之一。
    • 点落在边上。此函数返回PTLOC_ON_EDGE，且edge将包含此边。
    • 点与细分的一个顶点重合。此函数返回PTLOC_VERTEX，且vertex将包含顶点的指针。
    • 点位于细分参考矩形外部。此函数返回PTLOC_OUTSIDE_RECT，不会填充任何指针。
    • 一个输入参数无效。将引发运行时错误，或者如果选择静默或“父”错误处理模式，则返回 PTLOC_ERROR。

获取下一个边 - nextEdge

返回以边缘为起点的下一边缘。

1
cv2.Subdiv2D.nextEdge(edge) -> retval

  • 参数说明：

    变量 含义
    retval 下一个边缘的 ID。
    edge 输出点所属的边或位于其右侧的边。

  • 示例代码：

    1
    next_edge = subdiv.nextEdge(10)

旋转边缘 - rotateEdge

返回同一四边形的另一个边缘。

1
cv2.Subdiv2D.rotateEdge(edge, rotate) -> retval

  • 参数说明：

    变量 含义
    edge 分划边 ID。
    rotate 指定返回与输入quad-edge相同的边的参数。

    • 0 - 输入边（如果 e 是输入边，则下图中的 e）

    • 1 - 旋转边（ eRot ）

    • 2 - 反转边（绿色显示的反转e）

    • 3 - 反转旋转边（绿色显示的反转eRot）

  • 示例代码：

    1
    subdiv.rotateEdge(2, 0)

Vornoni 示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import cv2
import numpy as np
import random
import vvdutils as vv


# 检查一个点是否在矩形内
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, 2)

# 绘制 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 = (int(t[0]), int(t[1]))
        pt2 = (int(t[2]), int(t[3]))
        pt3 = (int(t[4]), int(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(img, pt2, pt3, delaunay_color, 1)
            cv2.line(img, pt3, pt1, delaunay_color, 1)

# 绘制 voronoi 图
def draw_voronoi(img, subdiv) :
    ( facets, centers) = subdiv.getVoronoiFacetList([])
    for i in range(0,len(facets)) :
        ifacet_arr = facets[i]
        center = centers[i].astype('int32')
        ifacet = np.array(ifacet_arr)
        color = (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))
        cv2.fillConvexPoly(img, ifacet.astype('int32'), color)
        ifacets = np.array([ifacet])
        cv2.polylines(img, ifacets.astype('int32'), True, (0, 0, 0), 1)
        cv2.circle(img, (center[0], center[1]), 3, (0, 0, 0), 1)


if __name__ == '__main__':
    # 定义绘制颜色
    delaunay_color = (255,255,255)
    points_color = (0, 0, 255)

    img = np.zeros([500,500,3],dtype=np.uint8)

    # 创建用于Subdiv2D 的矩形
    size = img.shape
    rect = (0, 0, size[1], size[0])

    # 创建Subdiv2D 实例
    subdiv = cv2.Subdiv2D(rect)
    points = []

    points.append((100, 100))
    points.append((100, 200))
    points.append((200, 100))
    points.append((200, 200))
    points.append((200, 300))
    points.append((400, 400))
    points.append((300, 400))

    # 将点依次插入subdiv中
    for p in points :
        subdiv.insert(p)
        # 展示动画画板

    img_copy = img.copy()
    draw_delaunay(img_copy, subdiv, (255, 255, 255))
    vv.PIS(img_copy)

    # 绘制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)
    vv.PIS(img_voronoi)
    pass

参考资料



文章链接：
https://www.zywvvd.com/notes/study/image-processing/opencv/subdiv2d/subdiv2d/

“觉得不错的话，给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信二维码

微信支付

支付宝二维码

支付宝支付

Image_Processing > OpenCV
#OpenCV #Image_Processing
OpenCV Subdiv2D 平面细分
https://www.zywvvd.com/notes/study/image-processing/opencv/subdiv2d/subdiv2d/
作者
Yiwei Zhang
发布于
2024年9月3日
许可协议