Python, OpenCVでドロネー図・ボロノイ図を描画
PythonとOpenCVを使って、ドロネー図とボロノイ図を描画する。
OpenCVのSubdiv2Dというクラスでドロネー図とボロノイ図の情報を算出し、OpenCVの描画機能で境界線を引いたり塗りつぶしたりできる。
ここでは以下の内容について説明する。
- ドロネー図とボロノイ図
- サンプルコードの下準備
Subdiv2Dオブジェクトを作成- ドロネー三角形の座標リストを取得:
getTriangleList() - ドロネー図を描画
- ボロノイ領域の座標リストを取得:
getVoronoiFacetList() - ボロノイ図を描画
- ボロノイ図を塗りつぶし
- ドロネー図とボロノイ図を同時に描画
SciPyとMatplotlibを使ってドロネー図およびボロノイ図を描画することも可能。
ドロネー図とボロノイ図
ドロネー図とボロノイ図についての説明はWikipediaなどを参照。英語版のほうが詳しい。
サンプルコードで最後に作成する図を先に示す。赤線がドロネー図、黒とグレーの塗りつぶしで分割されているのがボロノイ図。
ドロネー図とは
平面においては、複数個の点に対して、各点を結ぶ三角形の最小角度が最大になるようにして分割したものがドロネー図（ドロネー三角形分割）。
ボロノイ図とは
平面においては、複数個の点に対して、それ以外の他の点がどの点に近いかによって領域分けされた図がボロノイ図。領域の境界線は各々の母点の二等分線の一部となる。
サンプルコードの下準備
以下のように各ライブラリをインポート（pprintは出力を見やすくするために使用）し、対象領域の幅と高さを指定、その領域内のランダムな点を用意する。n個の点のx, y座標をn行2列のnumpy.ndarrayとする。
import cv2
import numpy as np
import pprint
w = h = 360
n = 6
np.random.seed(0)
pts = np.random.randint(0, w, (n, 2))
print(pts)
# [[172 47]
# [117 192]
# [323 251]
# [195 359]
# [ 9 211]
# [277 242]]
print(type(pts))
# <class 'numpy.ndarray'>
print(pts.shape)
# (6, 2)
階調が0（黒）のRGB画像に相当するnumpy.ndarrayを用意。ランダムな点を描画すると以下のようになる。原点(0, 0)は左上。
img = np.zeros((w, h, 3), np.uint8)
for p in pts:
cv2.drawMarker(img, tuple(p), (255, 255, 255), thickness=2)
cv2.imwrite('data/dst/opencv_random_pts.png', img)
これをもとにドロネー図やボロノイ図を描画していく。
OpenCVの描画機能については以下の記事を参照。
Subdiv2Dオブジェクトを作成
まずSubdiv2Dオブジェクトを作成する。コンストラクタcv2.Subdiv2D()の引数には矩形領域を示すタプル(左上のx座標, 左上のy座標, 右下のx座標, 右下のy座標)を指定する。
さらにinsert()メソッドで対象の点の座標を追加する。
rect = (0, 0, w, h)
subdiv = cv2.Subdiv2D(rect)
for p in pts:
subdiv.insert((p[0], p[1]))
ドロネー三角形の座標リストを取得: getTriangleList()
ドロネー三角形の座標リストはSubdiv2DのメソッドgetTriangleList()で取得できる。
[1個目のx座標 1個目のy座標 2個目のx座標 2個目のy座標 3個目のx座標 3個目のy座標]というドロネー三角形の座標リストを複数個含むnumpy.ndarrayが返される。
triangles = subdiv.getTriangleList()
print(triangles)
# [[ 1080. 0. 0. 1080. 323. 251.]
# [ 0. 1080. 1080. 0. -1080. -1080.]
# [ 0. 1080. -1080. -1080. 9. 211.]
# [-1080. -1080. 1080. 0. 172. 47.]
# [ 172. 47. 1080. 0. 323. 251.]
# [ 172. 47. 323. 251. 277. 242.]
# [-1080. -1080. 172. 47. 9. 211.]
# [ 172. 47. 117. 192. 9. 211.]
# [ 117. 192. 172. 47. 277. 242.]
# [ 9. 211. 195. 359. 0. 1080.]
# [ 195. 359. 9. 211. 117. 192.]
# [ 323. 251. 0. 1080. 195. 359.]
# [ 195. 359. 117. 192. 277. 242.]
# [ 323. 251. 195. 359. 277. 242.]]
scipy.spatial.Delaunayと異なり、領域外の点の座標もリストアップされる。
ドロネー図を描画
多角形を描画するcv2.polylines()を使ってドロネー図を描画する。
座標リストをreshape()メソッドでcv2.polylines()に合う形状に変換する。
cv2.polylines()に指定するには整数intである必要があるので注意。
pols = triangles.reshape(-1, 3, 2)
print(pols)
# [[[ 1080. 0.]
# [ 0. 1080.]
# [ 323. 251.]]
#
# [[ 0. 1080.]
# [ 1080. 0.]
# [-1080. -1080.]]
#
# [[ 0. 1080.]
# [-1080. -1080.]
# [ 9. 211.]]
#
# [[-1080. -1080.]
# [ 1080. 0.]
# [ 172. 47.]]
#
# [[ 172. 47.]
# [ 1080. 0.]
# [ 323. 251.]]
#
# [[ 172. 47.]
# [ 323. 251.]
# [ 277. 242.]]
#
# [[-1080. -1080.]
# [ 172. 47.]
# [ 9. 211.]]
#
# [[ 172. 47.]
# [ 117. 192.]
# [ 9. 211.]]
#
# [[ 117. 192.]
# [ 172. 47.]
# [ 277. 242.]]
#
# [[ 9. 211.]
# [ 195. 359.]
# [ 0. 1080.]]
#
# [[ 195. 359.]
# [ 9. 211.]
# [ 117. 192.]]
#
# [[ 323. 251.]
# [ 0. 1080.]
# [ 195. 359.]]
#
# [[ 195. 359.]
# [ 117. 192.]
# [ 277. 242.]]
#
# [[ 323. 251.]
# [ 195. 359.]
# [ 277. 242.]]]
img_draw = img.copy()
cv2.polylines(img_draw, pols.astype(int), True, (0, 0, 255), thickness=2)
cv2.imwrite('data/dst/opencv_delaunay.png', img_draw)
また、cv2.imwrite()で画像として保存する場合はRGBではなくBGRの並びとして扱われるので図形の色を指定する際は注意。
領域内の三角形だけでよい場合は領域外の座標を除外する。
print(np.all(pols[:, :, 0] < w, axis=1))
# [False False True False False True True True True True True True
# True True]
pols_inner = pols[np.all(pols[:, :, 0] < w, axis=1) &
np.all(pols[:, :, 0] > 0, axis=1) &
np.all(pols[:, :, 1] < h, axis=1) &
np.all(pols[:, :, 1] > 0, axis=1)]
print(pols_inner)
# [[[172. 47.]
# [323. 251.]
# [277. 242.]]
#
# [[172. 47.]
# [117. 192.]
# [ 9. 211.]]
#
# [[117. 192.]
# [172. 47.]
# [277. 242.]]
#
# [[195. 359.]
# [ 9. 211.]
# [117. 192.]]
#
# [[195. 359.]
# [117. 192.]
# [277. 242.]]
#
# [[323. 251.]
# [195. 359.]
# [277. 242.]]]
img_draw = img.copy()
cv2.polylines(img_draw, pols_inner.astype(int), True, (0, 0, 255), thickness=2)
cv2.imwrite('data/dst/opencv_delaunay_inner.png', img_draw)
なお、領域外の座標が必要ない場合はscipy.spatial.Delaunayを使って座標リストを取得する方が簡単。
ボロノイ領域の座標リストを取得: getVoronoiFacetList()
ボロノイ領域の座標リストはSubdiv2DのメソッドgetTriangleList()で取得できる。
ボロノイ領域を示す多角形の座標リストと母点の座標リストを返す。ボロノイ領域を示す多角形の座標リストは要素数がバラバラなので、numpy.ndarrayのリストとなる。母点の座標リストはSubdiv2Dのコンストラクタに指定した座標リストと等価。
facets, centers = subdiv.getVoronoiFacetList([])
pprint.pprint(facets)
# [array([[ 331.1972 , 87.04766],
# [ 218.6763 , 147.63583],
# [ 41.71519, 80.51266],
# [ -503.5626 , -461.44025],
# [ 540.8418 , -1621.6836 ],
# [ 618.2897 , -125.45706]], dtype=float32),
# array([[218.6763 , 147.63583],
# [182.60144, 263.07538],
# [ 82.09151, 310.02014],
# [ 41.71519, 80.51266]], dtype=float32),
# array([[ 282.99118, 333.434 ],
# [ 331.1972 , 87.04766],
# [ 618.2897 , -125.45706],
# [ 987.2233 , 987.2233 ],
# [ 759.8912 , 898.6488 ]], dtype=float32),
# array([[ 182.60144, 263.07538],
# [ 282.99118, 333.434 ],
# [ 759.8912 , 898.6488 ],
# [-183.30182, 643.555 ],
# [ 82.09151, 310.02014]], dtype=float32),
# array([[ 82.09151, 310.02014],
# [ -183.30182, 643.555 ],
# [-1793.752 , 626.876 ],
# [ -503.5626 , -461.44025],
# [ 41.71519, 80.51266]], dtype=float32),
# array([[218.6763 , 147.63583],
# [331.1972 , 87.04766],
# [282.99118, 333.434 ],
# [182.60144, 263.07538]], dtype=float32)]
print(centers)
# [[172. 47.]
# [117. 192.]
# [323. 251.]
# [195. 359.]
# [ 9. 211.]
# [277. 242.]]
ボロノイ図を描画
ドロネー図と同様に、多角形を描画するcv2.polylines()を使ってボロノイ図を描画する。
getTriangleList()で取得した座標リストを整数intに変換する必要があるので注意。
img_draw = img.copy()
cv2.polylines(img_draw, [f.astype(int) for f in facets], True, (255, 255, 255), thickness=2)
cv2.imwrite('data/dst/opencv_voronoi.png', img_draw)
ボロノイ図を塗りつぶし
塗りつぶしたい場合はcv2.fillPoly()を使う。以下の例では塗りつぶし階調を順番に0（黒）から255（白）に変化させている。
img_draw = img.copy()
step = int(255 / len(facets))
for i, p in enumerate(f.astype(int) for f in facets):
cv2.fillPoly(img_draw, [p], (step * i, step * i, step * i))
cv2.imwrite('data/dst/opencv_voronoi_fill.png', img_draw)
ドロネー図とボロノイ図を同時に描画
OpenCVの描画機能は単純に上書きしていくだけなので、ドロネー図とボロノイ図を同時に描画したい場合は順番に描画していけばOK。cv2.fillPoly()による塗りつぶしは最初にやらないとその前に描画したものの上から塗りつぶしてしまうので注意。
img_draw = img.copy()
step = int(255 / len(facets))
for i, p in enumerate(f.astype(int) for f in facets):
cv2.fillPoly(img_draw, [p], (step * i, step * i, step * i))
cv2.polylines(img_draw, pols_inner.astype(int), True, (0, 0, 255), thickness=2)
for c in centers:
cv2.drawMarker(img_draw, tuple(c), (255, 255, 255), thickness=2)
cv2.imwrite('data/dst/opencv_delaunay_voronoi.png', img_draw)