Come posso disegnare linee in array numpy?

Question

Mi piacerebbe essere in grado di disegnare linee in array numpy per ottenere funzionalità off-line per il riconoscimento della grafia on-line. Ciò significa che non ho bisogno dell'immagine, ma ho bisogno di alcune posizioni in una matrice numpy che assomigli ad un'immagine di una certa dimensione.

Mi piacerebbe essere in grado di specificare una dimensione dell'immagine e quindi disegnare i tratti in questo modo:

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) 

è qualcosa di semplice come quello possibile (preferibilmente direttamente con NumPy/SciPy)?

(Si prega di notare che voglio interpolazione scala di grigi. Quindi features dovrebbe essere una matrice di valori in [0, 255].)

Answer 1

Grazie a Joe Kington per la risposta! Stavo cercando 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

Mi sono imbattuto in questa domanda mentre cercavo una soluzione, e la risposta fornita la risolve abbastanza bene. Tuttavia, non si adattava ai miei scopi, per i quali avevo bisogno di una soluzione "tensoriale" (cioè implementata in numpy senza cicli espliciti) e possibilmente con un'opzione di larghezza di riga. Ho finito per implementare la mia versione e dato che alla fine è anche più veloce di line_aa, ho pensato di poterlo condividere.

È disponibile in due versioni, con e senza larghezza di riga. In realtà il primo non è una generalizzazione di quest'ultimo, e nemmeno è perfettamente d'accordo con line_aa, ma per i miei scopi stanno bene e sulle trame sembrano okay.

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))) 

Ho chiamato questa "naive" perché è abbastanza simile all'implementazione naif in Wikipedia, ma con alcuni anti-aliasing, anche se certamente non perfetto (ad esempio fa diagonali molto sottili).

La versione ponderata fornisce una linea molto più spessa anti-aliasing più pronunciato.

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

L'adeguamento del peso è certamente abbastanza arbitrario, quindi chiunque può adattarlo ai propri gusti. Ora rmin e rmax sono necessari per evitare i pixel all'esterno dell'immagine. Un confronto:

Come si può vedere, anche con w = 1, weighted_line è un po 'più spessa, ma in una sorta di modo omogeneo; allo stesso modo, naive_line è omogeneamente leggermente più sottile.

Nota finale sull'analisi comparativa: sulla mia macchina, correndo %timeit f(1,1,100,240) per le varie funzioni (w = 1 per weighted_line) ha determinato un tempo di 90 ms per line_aa, 84 S per weighted_line (anche se il tempo, naturalmente, aumenta con il peso) e 18 μs per naive_line. Sempre per il confronto, il reimplementing di line_aa in puro Python (invece di Cython come nel pacchetto) ha richiesto 350 μs.