بيثون كفاف الثنائية 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)

ثم مخطط يجب قراءة (في الصفوف أو 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]])

فكرة أخرى كان استخدام بايثون الحد() إذا كنت بحاجة إلى تشغيل أكثر من قائمة coords مرة واحدة فقط.ولكن لدي صعوبة في العثور على جيد والحد من وظيفة.

أي مساعدة سوف يكون موضع تقدير كبير!

تحرير

في هذه الأثناء كنت قد وجدت أسرع طريقة للذهاب من 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

للحصول على مزيد من الحل, هل يمكن استخدام سوميكيند حافة طريقة الكشف أن تجد فقط على حافة نقطة.أعتقد أن (جوجل..) التي NumPy وقد بنيت في سوبل المرشح الذي سوف نفعل ذلك.