numpy二进制光栅图像到多边形变换

Question

我想将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]

它大部分时间都有效,但速度不够快.我的第二个代码很少工作,但我没有修复它,因为它比第一个代码慢很多倍:

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

如何进一步提高速度？

编辑:似乎numpy蒙面数组非常慢.这个实现几乎和第一个一样快:

#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毫秒内完成.我将修改pygame.mask.outline的源代码以使用numpy数组并在此处发布.

Answer 1

这就是：一种获取二进制 numpy 数组轮廓的极快方法。

\n\n

大纲.py：

\n\n

from scipy.weave import inline, converters\n\n_code = open("outline.c", "r").read()\n\ndef outline(data, every):\n    width, height = data.shape\n    return inline(_code, [\'data\', \'width\', \'height\', \'every\'], type_converters=converters.blitz)\n

\n\n

大纲.c:

\n\n

/*\nModifioitu pygame.mask.Mask.outline\nInput: data, width, height, every\n*/\n\nPyObject *plist, *value;\nint x, y, e, firstx, firsty, secx, secy, currx, curry, nextx, nexty, n;\nint a[14], b[14];\na[0] = a[1] = a[7] = a[8] = a[9] = b[1] = b[2] = b[3] = b[9] = b[10] = b[11]= 1;\na[2] = a[6] = a[10] = b[4] = b[0] = b[12] = b[8] = 0;\na[3] = a[4] = a[5] = a[11] = a[12] = a[13] = b[5] = b[6] = b[7] = b[13] = -1;\n\nplist = NULL;\nplist = PyList_New (0);\n/*if (!plist) En ymm\xc3\xa4rr\xc3\xa4 mihin t\xc3\xa4t\xc3\xa4 tarvii\n    return NULL;*/\n\nevery = 1;\nn = firstx = firsty = secx = x = 0;\n\n/*if(!PyArg_ParseTuple(args, "|i", &every)) {\n    return NULL;\n}\n\n by copying to a new, larger mask, we avoid having to check if we are at\n   a border pixel every time.  \nbitmask_draw(m, c, 1, 1); */\n\ne = every;\n\n/* find the first set pixel in the mask */\nfor (y = 1; y < height-1; y++) {\n    for (x = 1; x < width-1; x++) {\n        if (data(x, y)) {\n             firstx = x;\n             firsty = y;\n             value = Py_BuildValue("(ii)", x-1, y-1);\n             PyList_Append(plist, value);\n             Py_DECREF(value);\n             break;\n        }\n    }\n    if (data(x, y))\n        break;\n}\n\n\n\n/* covers the mask having zero pixels or only the final pixel\nPikseleit\xc3\xa4 on ainakin kymmenen\nif ((x == width-1) && (y == height-1)) {\n    return plist;\n}        */\n\n/* check just the first pixel for neighbors */\nfor (n = 0;n < 8;n++) {\n    if (data(x+a[n], y+b[n])) {\n        currx = secx = x+a[n];\n        curry = secy = y+b[n];\n        e--;\n        if (!e) {\n            e = every;\n            value = Py_BuildValue("(ii)", secx-1, secy-1);\n            PyList_Append(plist, value);\n            Py_DECREF(value);\n        }\n        break;\n    }\n}       \n\n/* if there are no neighbors, return\nPikseleit\xc3\xa4 on ainakin kymmenen\nif (!secx) {\n    return plist;\n}*/\n\n/* the outline tracing loop */\nfor (;;) {\n    /* look around the pixel, it has to have a neighbor */\n    for (n = (n + 6) & 7;;n++) {\n        if (data(currx+a[n], curry+b[n])) {\n            nextx = currx+a[n];\n            nexty = curry+b[n];\n            e--;\n            if (!e) {\n                e = every;\n                if ((curry == firsty && currx == firstx) && (secx == nextx && secy == nexty)) {\n                    break;\n                }\n                value = Py_BuildValue("(ii)", nextx-1, nexty-1);\n                PyList_Append(plist, value);\n                Py_DECREF(value);\n            }\n            break;\n        }\n    }\n    /* if we are back at the first pixel, and the next one will be the\n       second one we visited, we are done */\n    if ((curry == firsty && currx == firstx) && (secx == nextx && secy == nexty)) {\n        break;\n    }\n\n    curry = nexty;\n    currx = nextx;\n}\n\nreturn_val = plist;\n

\n