2D numpy 配列をポリゴンに変換したい。パフォーマンスは私にとって非常に重要ですが、C 拡張を作成することは避けたいと考えています。バイナリ アウトライン イメージは、浸食で作成できます。それから私はこれを見つけました。速度が遅すぎて、侵食によって発生するスパイクに対応できませんでした。スパイク:
000100
000100
000100
111011
私の最初の試み：
mat = mat.copy() != 0
mat = mat - scipy.ndimage.binary_erosion(mat)
vertices = np.argwhere(mat)
minx = vertices.min(axis=0)[0]
maxx = vertices.max(axis=0)[0]
vertices_sorted = {}
for x in xrange(minx - 1, maxx + 2):
vertices_sorted[x] = []
for vertex in vertices:
vertices_sorted[vertex[0]].append(vertex[1])
vertex_loop = [(minx, vertices_sorted[minx][0])]
while True:
x, y = vertex_loop[-1]
for column, row in ((x, y + 1), (x, y - 1),
(x + 1, y), (x + 1, y + 1), (x + 1, y - 1),
(x - 1, y), (x - 1, y + 1), (x - 1, y - 1)):
if row in vertices_sorted[column]:
vertices_sorted[column].remove(row)
vertex_loop.append((column, row))
break
else:
vertex_loop.pop()
if vertex_loop[-1] == vertex_loop[0]:
break
return vertex_loop[:-1]
ほとんどの場合は機能しますが、十分に高速ではありません。私の 2 番目のコードはめったに機能しませんが、最初のコードよりも数倍遅いため、修正していません。
mat = mat.copy() != 0
mat = mat - scipy.ndimage.binary_erosion(mat)
xs, ys = np.nonzero(mat)
ys = np.ma.array(ys)
vertex_loop = [(xs[0], ys[0])]
ys[0] = np.ma.masked
while True:
x, y = vertex_loop[-1]
start = np.searchsorted(xs, x-1, side="left")
end = np.searchsorted(xs, x+1, side="right")
for i in xrange(start, end):
if ys[i] == y or ys[i] == y + 1 or ys[i] == y - 1:
vertex_loop.append((xs[i], ys[i]))
ys[i] = np.ma.masked
break
else:
if np.all(ys.mask):
break
else:
vertex_loop.pop()
return vertex_loop
どうすればさらに速度を向上させることができますか?
編集: でこぼこのマスクされた配列は非常に遅いようです。この実装は、最初の実装とほぼ同じ速度です。
#import time
#t1 = time.time()
mat = mat.copy() != 0
mat = mat - scipy.ndimage.binary_erosion(mat)
xs, ys = np.nonzero(mat)
#t2 = time.time()
minx = xs[0]
maxx = xs[-1]
# Ketju pakosti käy läpi kaikki rivit minx:n ja maxx:n välissä, sillä se ON KETJU
xlist = range(minx - 1, maxx + 2)
# starts ja ends ovat dictit jotka kertovat missä slicessä x == key
tmp = np.searchsorted(xs, xlist, side="left")
starts = dict(zip(xlist, tmp))
tmp = np.searchsorted(xs, xlist, side="right")
ends = dict(zip(xlist, tmp))
unused = np.ones(len(xs), dtype=np.bool)
#t3 = time.time()
vertex_loop = [(xs[0], ys[0])]
unused[0] = 0
count = 0
while True:
count += 1
x, y = vertex_loop[-1]
for i in xrange(starts[x - 1], ends[x + 1]):
row = ys[i]
if unused[i] and (row == y or row == y + 1 or row == y - 1):
vertex_loop.append((xs[i], row))
unused[i] = 0
break
else:
if abs(x - xs[0]) <= 1 and abs(y - ys[0]) <= 1:
break
else:
vertex_loop.pop()
#t4 = time.time()
#print abs(t1-t2)*1000, abs(t2-t3)*1000, abs(t3-t4)*1000
return vertex_loop
私が見つけられなかった scipy でこれを行う簡単な方法があるのだろうか。
EDIT2：pygameには、0.025ミリ秒で必要なことだけを行うマスクオブジェクトがありますが、私のソリューションには35ミリ秒が必要で、インターネットで見つけたfind_contoursは4〜5ミリ秒で実行します。numpy 配列を使用するように pygame.mask.outline のソース コードを変更して、ここに投稿します。