मैं संख्यात्मक सरणी में रेखा कैसे खींच सकता हूं?

Question

मैं ऑन-लाइन हस्तलेख मान्यता के लिए ऑफलाइन सुविधाओं को प्राप्त करने के लिए संख्यात्मक सरणी में रेखाएं खींचने में सक्षम होना चाहता हूं। इसका मतलब है कि मुझे छवि की बिल्कुल आवश्यकता नहीं है, लेकिन मुझे एक सुस्त सरणी में कुछ पदों की आवश्यकता है, जो किसी दिए गए आकार की एक छवि दिखाई देगी।

मैं और एक छवि का आकार निर्दिष्ट करने में सक्षम हो तो इस तरह स्ट्रोक आकर्षित करने के लिए करना चाहते हैं:

import module 
im = module.new_image(width=800, height=200) 
im.add_stroke(from={'x': 123, 'y': 2}, to={'x': 42, 'y': 3}) 
im.add_stroke(from={'x': 4, 'y': 3}, to={'x': 2, 'y': 1}) 
features = im.get(x_min=12, x_max=15, y_min=0, y_max=111) 

संभव ऐसा ही कुछ सरल (numpy/scipy साथ अधिमानतः सीधे) है?

जवाब के लिए जो Kington को

Answer 1

धन्यवाद (कृपया ध्यान दें कि मैं ग्रे पैमाने पर प्रक्षेप चाहते हैं। तो features [0, 255]। में मूल्यों के एक मैट्रिक्स होना चाहिए)! मैं skimage.draw.line_aa की तलाश में था।

import scipy.misc 
import numpy as np 
from skimage.draw import line_aa 
img = np.zeros((10, 10), dtype=np.uint8) 
rr, cc, val = line_aa(1, 1, 8, 4) 
img[rr, cc] = val * 255 
scipy.misc.imsave("out.png", img) 

Answer 2

मैंने समाधान की तलाश करते समय इस प्रश्न पर ठोकर खाई, और प्रदान किया गया उत्तर इसे काफी हल करता है। हालांकि, यह वास्तव में मेरे उद्देश्यों के अनुरूप नहीं था, जिसके लिए मुझे एक "tensorizable" समाधान की आवश्यकता थी (यानी स्पष्ट लूप के बिना numpy में लागू), और संभवतः एक लाइनविड्थ विकल्प के साथ। मैंने अपना खुद का संस्करण लागू करना समाप्त कर दिया, और अंत में यह line_aa से भी काफी तेज है, मैंने सोचा कि मैं इसे साझा कर सकता हूं।

यह दो स्वादों में आता है, बिना लाइनविड्थ के। असल में पूर्व उत्तरार्द्ध का सामान्यीकरण नहीं है, और न ही पूरी तरह से line_aa से सहमत है, लेकिन मेरे उद्देश्यों के लिए वे ठीक हैं और भूखंडों पर वे ठीक दिखते हैं।

def naive_line(r0, c0, r1, c1): 
    # The algorithm below works fine if c1 >= c0 and c1-c0 >= abs(r1-r0). 
    # If either of these cases are violated, do some switches. 
    if abs(c1-c0) < abs(r1-r0): 
     # Switch x and y, and switch again when returning. 
     xx, yy, val = naive_line(c0, r0, c1, r1) 
     return (yy, xx, val) 

    # At this point we know that the distance in columns (x) is greater 
    # than that in rows (y). Possibly one more switch if c0 > c1. 
    if c0 > c1: 
     return naive_line(r1, c1, r0, c0) 

    # We write y as a function of x, because the slope is always <= 1 
    # (in absolute value) 
    x = np.arange(c0, c1+1, dtype=float) 
    y = x * (r1-r0)/(c1-c0) + (c1*r0-c0*r1)/(c1-c0) 

    valbot = np.floor(y)-y+1 
    valtop = y-np.floor(y) 

    return (np.concatenate((np.floor(y), np.floor(y)+1)).astype(int), np.concatenate((x,x)).astype(int), 
      np.concatenate((valbot, valtop))) 

मैं इस "अनुभवहीन" क्योंकि यह काफी Wikipedia में अनुभवहीन कार्यान्वयन के लिए समान है, लेकिन कुछ विरोधी aliasing के साथ कहा जाता है, हालांकि बेशक सही नहीं है (जैसे बहुत पतली विकर्ण करता है)।

भारित संस्करण अधिक मोटा लाइन अधिक स्पष्ट एंटी-एलियासिंग देता है।

def trapez(y,y0,w): 
    return np.clip(np.minimum(y+1+w/2-y0, -y+1+w/2+y0),0,1) 

def weighted_line(r0, c0, r1, c1, w, rmin=0, rmax=np.inf): 
    # The algorithm below works fine if c1 >= c0 and c1-c0 >= abs(r1-r0). 
    # If either of these cases are violated, do some switches. 
    if abs(c1-c0) < abs(r1-r0): 
     # Switch x and y, and switch again when returning. 
     xx, yy, val = weighted_line(c0, r0, c1, r1, w, rmin=rmin, rmax=rmax) 
     return (yy, xx, val) 

    # At this point we know that the distance in columns (x) is greater 
    # than that in rows (y). Possibly one more switch if c0 > c1. 
    if c0 > c1: 
     return weighted_line(r1, c1, r0, c0, w, rmin=rmin, rmax=rmax) 

    # The following is now always < 1 in abs 
    slope = (r1-r0)/(c1-c0) 

    # Adjust weight by the slope 
    w *= np.sqrt(1+np.abs(slope))/2 

    # We write y as a function of x, because the slope is always <= 1 
    # (in absolute value) 
    x = np.arange(c0, c1+1, dtype=float) 
    y = x * slope + (c1*r0-c0*r1)/(c1-c0) 

    # Now instead of 2 values for y, we have 2*np.ceil(w/2). 
    # All values are 1 except the upmost and bottommost. 
    thickness = np.ceil(w/2) 
    yy = (np.floor(y).reshape(-1,1) + np.arange(-thickness-1,thickness+2).reshape(1,-1)) 
    xx = np.repeat(x, yy.shape[1]) 
    vals = trapez(yy, y.reshape(-1,1), w).flatten() 

    yy = yy.flatten() 

    # Exclude useless parts and those outside of the interval 
    # to avoid parts outside of the picture 
    mask = np.logical_and.reduce((yy >= rmin, yy < rmax, vals > 0)) 

    return (yy[mask].astype(int), xx[mask].astype(int), vals[mask]) 

वजन समायोजन इसलिए किसी को भी उनके स्वाद है कि समायोजित कर सकते हैं, काफी मनमाने ढंग से बेशक है। तस्वीर के बाहर पिक्सेल से बचने के लिए अब rmin और rmax की आवश्यकता है। एक तुलना:

आप देख भी w = 1 के साथ कर सकते हैं, weighted_line थोड़ा मोटा है, लेकिन सजातीय रास्ते से एक वस्तु के रूप में; इसी तरह, naive_line एकरूप थोड़ा पतला है।

बेंचमार्किंग के बारे में अंतिम नोट: मेरी मशीन, विभिन्न कार्यों (w = weighted_line के लिए 1) line_aa के लिए 90 μs, weighted_line के लिए 84 μs की एक समय में हुई के लिए %timeit f(1,1,100,240) चल (पर हालांकि वजन के साथ पाठ्यक्रम बढ़ जाती है की समय) और naive_line के लिए 18 μs। फिर तुलना के लिए, शुद्ध पायथन (पैकेज में साइथन के बजाय) में लाइन_एए को फिर से कार्यान्वित करना 350 μs लिया।