이진 2D 매트릭스 용 Python 윤곽

StackOverflow https://stackoverflow.com/questions/1601613

문제

이진 NXM 매트릭스의 모양 주위의 볼록 선체를 계산하고 싶습니다. 볼록한 선체 알고리즘은 좌표 목록을 기대하므로 Numpy.arg (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 Numpy 배열로, 나는 신경 쓰지 않습니다) : :

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

이 모양 (IM) 주변의 볼록한 선체는 이러한 점의 하위 집합 (개요)을 제시해야합니다. 다시 말해, "nomefunc ()"이 내부 지점을 필터링하는 데 효율적이면 볼록한 선체 계산의 시간을 절약합니다.

위의 트릭을 수행하는 코드가 있지만, 여러 번 실행해야하므로 누군가가 더 영리한 (더 빠른) 접근 방식을 가지고 있기를 바랍니다. 내가 가진 코드는 다음과 같습니다.

# 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 's Reduce ()를 사용하는 것이 었으므로 코디 목록을 한 번만 실행해야합니다. 그러나 좋은 감소 기능을 찾는 데 어려움이 있습니다.

모든 도움이 크게 감사하겠습니다!

편집하다

그 동안 나는 더 빠른 방법을 찾았습니다. im 직접 outline. 적어도 큰 이미지에서는 이것이 훨씬 빠릅니다. 외부 솔루션의 명백한 부재하에 나는이 질문에 대한 솔루션으로 그것을 묘사하고 있습니다.

그래도 누군가가 더 빠른 방법을 알고 있다면 말씀 해주십시오. :)

도움이 되었습니까?

해결책

허용 가능한 답변이 없으면 최상의 작업 코드를 솔루션으로 게시합니다.

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

다른 팁

이 과제는 마지막 두 단계와 동일한 것을 달성하는 것 같습니다.

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

그러나 더 빠른지 모르겠습니다.

보다 일반적인 솔루션을 위해서는 에지 감지 방법을 사용하여 에지 점만 찾을 수 있습니다. 나는 Numpy가 내장 된 소벨 필터를 가지고 있다고 믿습니다 (Google ..).

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top