контур питона для двоичной двумерной матрицы

Question

Я хочу вычислить выпуклую оболочку вокруг фигуры в двоичной матрице NxM. Алгоритм выпуклой оболочки ожидает список координат, поэтому я беру numpy.argwhere (im), чтобы иметь все координаты точки формы. Тем не менее, большинство из этих точек не способствуют выпуклой оболочке (они лежат внутри формы). Поскольку время вычисления выпуклого корпуса, по крайней мере, пропорционально количеству точек, которые оно получает в качестве входных данных, я разработал идею заранее отфильтровать множество бесполезных точек и пропустить только те, которые охватывают контур. Идея довольно проста, что для каждой строки в двоичной матрице NxM я беру только минимальный и максимальный индексы. Так, например:

im = np.array([[1,1,1,0],
              [1,0,1,1],
              [1,1,0,1],
              [0,0,0,0],
              [0,1,1,1]], dtype=np.bool)
outline = somefunc(im)

Тогда набросок должен читаться (в кортежах или в виде массива 5x2, я не против):

[(0,0),(0,2),(1,0),(1,3),(2,0),(2,3),(4,1),(4,3)]

Любая выпуклая оболочка, плотно прилегающая к этой форме (im), должна быть подмножеством этих точек (контур). Другими словами, если «somefunc ()» эффективно фильтрует внутренние точки, это экономит время для вычисления выпуклой оболочки.

У меня есть код, который выполняет вышеуказанный трюк, но я надеюсь, что у кого-то есть более умный (читай быстрее) подход, так как мне нужно запускать его много раз. Код у меня есть:

# I have a 2D binary field. random for the purpose of demonstration.
import numpy as np
im = np.random.random((320,360)) > 0.9

# This is my algorithm so far. Notice that coords is sorted.
coords = np.argwhere(im)
left = np.roll(coords[:,0], 1, axis=0) != coords[:,0]
outline = np.vstack([coords[left], coords[left[1:]], coords[-1]])

Еще одна идея, которая у меня возникла, заключалась в том, чтобы использовать Python Reduce (), поэтому мне нужно было бы просмотреть список координат только один раз. Но мне трудно найти хорошую функцию сокращения.

Любая помощь будет принята с благодарностью!

редактировать

Тем временем я нашел более быстрый способ перейти от im прямо к outline. По крайней мере, с большими изображениями это значительно быстрее. При очевидном отсутствии внешнего решения я ставлю его как решение этого вопроса.

Тем не менее, если кто-то знает еще более быстрый метод, пожалуйста, говорите:)

Answer 1

При отсутствии приемлемого ответа я выкладываю свой лучший рабочий код в качестве решения.

def outline(im):
    ''' Input binary 2D (NxM) image. Ouput array (2xK) of K (y,x) coordinates
        where 0 <= K <= 2*M.
    '''
    topbottom = np.empty((1,2*im.shape[1]), dtype=np.uint16)
    topbottom[0,0:im.shape[1]] = np.argmax(im, axis=0)
    topbottom[0,im.shape[1]:] = (im.shape[0]-1)-np.argmax(np.flipud(im), axis=0)
    mask      = np.tile(np.any(im, axis=0), (2,))
    xvalues   = np.tile(np.arange(im.shape[1]), (1,2))
    return np.vstack([topbottom,xvalues])[:,mask].T

Answer 2

Для более общего решения, вы можете использовать какой-то метод обнаружения ребер, чтобы найти только точки ребер. Я полагаю (Google ..), что NumPy имеет встроенный фильтр sobel, который сделает это.

Answer 3

Похоже, что это задание выполняет то же самое, что и два последних шага:

outline = np.array(dict(reversed(coords)).items() + dict(coords).items())

Однако не знаю, быстрее ли это.