контур python для двоичной 2D матрицы

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)

Затем outline должен быть прочитан (в виде кортежей или в виде числового массива 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]])

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

Мы были бы очень признательны за любую помощь!

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

Тем временем я нашел более быстрый способ перейти от 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

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

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

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

Answer 3

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