4

バイナリ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 numpy配列として、私は気にしません）：

[(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]])

私が持っていたもう1つのアイデアは、Pythonのreduce（）を使用することでした。そのため、座標のリストを1回だけ実行する必要がありました。しかし、私は良い還元機能を見つけるのに苦労しています。

どんな助けでも大歓迎です！

編集

imその間に、私は直接からに行くより速い方法を見つけましたoutline。少なくとも大きな画像では、これは大幅に高速です。外部の解決策が明らかにない場合、私はそれをこの質問の解決策と見なしています。

それでも、誰かがもっと速い方法を知っているなら、声を上げてください:)

4

3 に答える 3

3

許容できる答えがない場合は、解決策として最善のコードを投稿します。

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
于 2009-11-12T11:41:43.227 に答える
0

この割り当ては、最後の2つのステップと同じことを達成しているようです。

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

ただし、もっと速いかどうかはわかりません。

于 2009-10-21T17:22:54.977 に答える
0

より一般的な解決策として、ある種のエッジ検出方法を使用して、エッジポイントのみを見つけることができます。私は（Google ..）NumPyにはsobelフィルターが組み込まれていると信じています。

于 2009-10-21T21:24:00.980 に答える