Dessin linéaire avec une matrice - Recherche originale par un réinventeur du traitement d'image Python -
Une histoire sur le dessin d'une ligne droite anti-aliasée ** à votre manière ** simplement en effectuant des opérations matricielles sans compter sur une bibliothèque de traitement d'image. Également possible avec Pythonista
** Cliquez ici pour les informations de base ** ** Cliquez ici pour le dessin **
Recherche originale!?
[Algorithme de Bresenham](https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AC%E3%82%BC%E3%83%B3%E3%83%8F%E3 Lire% 83% A0% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0) Si c'est le cas, il existe quelque chose qui s'appelle l'algorithme de Xiaolin Wu, et il y a aussi [l'algorithme de Gupta-Sproull](http: //d.hatena). Il y avait .ne.jp / ousttrue / 20090224/1235499257). Cependant, j'ai pensé que je ferais de mon mieux si j'utilisais le calcul matriciel. Je l'ai appelé ma propre recherche parce que je ne pouvais pas la trouver, mais je ne pense pas que ce soit unique. (En bref, réinvention)
concept
De là Emprunté
La figure ci-dessus montre qu'une ligne droite d'une épaisseur de 1 s'étend sur différents pixels. Je veux donner à chaque pixel une densité en fonction de cette zone de chevauchement.
Paramètres de situation
Excusez-moi à la main
La figure ci-dessus montre comment une ligne droite est dessinée dans le pixel. Autrement dit, les carrés indiquent les pixels et les trois lignes droites tracées en diagonale indiquent une ligne droite épaisse T (la ligne droite médiane M est la ligne centrale). Considérons un pixel dont le centre est le point A $ (n_x, n_y) $ et une droite T $ ax + by + c = 0 $ dont l'épaisseur est $ w / 2 $. Cependant, $ a \ geq-b \ geq0, a> 0 $. De plus, la pente de la droite est $ \ theta = - \ arctan \ frac {b} {a} $.
Ce pixel a quatre coins en haut à gauche $ A_ {ul} (n_x-0.5, n_y-0.5) $, En haut à droite $ A_ {ur} (n_x-0,5, n_y + 0,5) $, En bas à gauche $ A_ {dl} (n_x + 0,5, n_y-0,5) $, En bas à droite $ A_ {dr} (n_x + 0,5, n_y + 0,5) $.
Par contre, pour la ligne droite épaisse T, trois lignes, U indiquant la limite supérieure, D indiquant la limite inférieure, et M courant au centre, sont représentées sur la figure. Les lignes supérieure et inférieure sont séparées par $ w / 2 $ de la ligne centrale et l'épaisseur totale est de $ w $.
De plus, les lignes droites qui coïncident avec les extrémités gauche et droite du pixel au centre de A sont L et R, respectivement, et les indices des lettres L et R changent en fonction de la ligne droite qu'ils croisent.
Problème de réglage
Dans la situation ci-dessus, trouvez l'aire S de la partie commune (bleu clair) du pixel A et du quadrilatère parallèle B $ L_UR_UR_DL_D $ (le point B est un point sur la droite M dans la direction positive de l'axe des x de A).
Définition de S_X
Quand $ t = (coordonnée x de B) - (coordonnée x de A_ {ul} A_ {ur}) $, sous le segment de ligne $ A_ {ul} A_ {ur} $ (direction positive de l'axe x) Soit l'aire d'une certaine figure $ X $ soit $ S_X (t) $ (image du déplacement de la figure en parallèle de haut en bas)
S=S_B(t)-S_B(t-1)
Sera. Le deuxième terme est la zone sous le segment de ligne $ A_ {dl} A_ {dr} $. Par conséquent, $ S_B (t) $ doit être calculé.
Décomposition du quadrilatère parallèle B
Comme le montre la figure, le quadrilatère parallèle B $ L_UR_UR_DL_D $ peut être divisé en trois parties: un triangle rectangle rouge $ \ triangle Red $, un triangle rectangle bleu $ \ triangle Blue $ et un rectangle blanc $ \ Box White $. .. (Dans la figure ci-dessous, le rectangle blanc a une zone négative)
Puis
S_B(t) = S_{\triangle Red}(t) +S_{\triangle Blue}(t) +S_{\Box White}(t)
Sera.
Par conséquent, considérons $ S_X (t) $ pour chaque figure. De plus, il convient de noter
\tau_\triangle=\frac{1}{2}\left(w/\cos\theta +tan\theta\right)\\
\tau_\Box=\frac{1}{2}\left(w/\cos\theta -tan\theta\right)
Et. ($ \ Tau_ \ triangle $ correspond à la différence de coordonnées $ x $ entre B et $ R_D $ et $ L_U $, et $ \ tau_ \ Box $ correspond à la différence de coordonnées $ x $ entre B et $ R_U $ et $ L_D $. Est)
Premièrement, la superficie totale de ces trois parties est
\triangle Red=\triangle Blue = 0.5\tan\theta = \frac{\tau_\triangle-\tau_\Box}{2}\\
\Box White = 2\tau_\Box
\\
Ensuite, considérons chaque $ S_X (t) $. $ \ Triangle Red $ dépasse $ A_ {ul} A_ {ur} $ quand $ t = - \ tau_ \ triangle $, et la figure entière correspond quand $ t = - \ tau_ \ Box $. En outre, l'augmentation entre les deux est une fonction quadratique convexe vers le bas.
S_{\triangle Red}(t) =
\begin{cases}
0 &
(t<-\tau_\triangle)\\
\frac{1}{2}\frac{1}{\tau_\triangle-\tau_\Box}\left(t+\tau_\triangle\right)^2 &
(-\tau_\triangle\leq t\leq-\tau_\Box)\\
\frac{\tau_\triangle-\tau_\Box}{2} &
(-\tau_\Box<t)
\end{cases}
$ \ Box White $ dépasse $ A_ {ul} A_ {ur} $ quand $ t = \ min (- \ tau_ \ Box, \ tau_ \ Box) $, et $ t = \ max (- \ tau_ \ Box) , \ tau_ \ Box) Lorsque $, le chiffre entier correspond. De plus, puisque l'augmentation entre-temps est linéairement fonctionnelle,
S_{\Box White}(t) =
\begin{cases}
0 &
(t<-\tau_\Box)\\
t+ \tau_\Box &
(-\tau_\Box\leq t)\\
\end{cases}
+
\begin{cases}
0 &
(t<\tau_\Box)\\
-t+ \tau_\Box &
(\tau_\Box\leq t))\\
\end{cases}
$ \ Triangle Blue $ dépasse $ A_ {ul} A_ {ur} $ quand $ t = \ tau_ \ Box $, et la figure entière s'adapte quand $ t = \ tau_ \ triangle) $. De plus, l'augmentation entre-temps est une fonction quadratique convexe vers le haut. 
Par conséquent, cela équivaut à la fonction de déplacer $ S_ {\ triangle Red} (t) $ point-symétriquement vers la cible d'origine, puis d'ajouter $ \ frac {\ tau_ \ triangle- \ tau_ \ Box} {2} $. ..
S_{\triangle Blue}(t) = \frac{\tau_\triangle-\tau_\Box}{2}-S_{\triangle Red}(-t)
code
Les conditions initiales sont les suivantes.
import numpy as np
import matplotlib.pyplot as plt
x, y = np.mgrid[:10,:10]
a, b, c = 2, -1, -1
w = 1
Calcul de t
C'est facile. Ajoutez simplement 0,5 à la distance entre le pixel et la ligne droite.
import numpy as np
import matplotlib.pyplot as plt
x, y = np.mgrid[:10,:10]
a, b, c = 2, -1, -1
w = 1
t = - b/a * y - c/a - x + 0.5
Calcul de τ
Calculez sans passer par $ \ theta $.
tau_triangle = (w*(a**2 + b**2)**0.5/a - b/a)/2
tau_square = (w*(a**2 + b**2)**0.5/a + b/a)/2
Calcul de S_X
#S_Parce qu'il est également utilisé en bleu, S_Déclarer le rouge en tant que fonction
S_red_func = lambda t :\
np.where(t<-tau_triangle,0,
np.where(t<= -tau_square,(t+tau_triangle)**2/(2*(tau_triangle - tau_square)),
(tau_triangle - tau_square)/2))
S_red = S_red_func(t)
S_blue = (tau_triangle - tau_square)/2 - S_red_func(-t)
S_white = np.where(t<-tau_square,0, t+tau_square) + \
np.where(t<tau_square,0, -t+tau_square)
#S_Créer B
S_B = S_red + S_blue + S_white
Calculez la différence de S_X
Utilisez np.diff. Pour calculer $ S_B (t) -S_B (t-1) $, -np.diff (S_B)
utilisation.
Il effectue également une conversion pour créer une ligne droite noire sur un fond blanc.
img_how_long_did_it_take_to_get_this = -np.diff(S_B,axis = 0)
#La valeur maximale est de 1 zone de pixel=1
img_black = 1-img_how_long_did_it_take_to_get_this
plt.imshow(img_black, cmap = 'gray')
Notez que les pixels verticaux sont décrémentés de 1 en raison du diff.
Résumer en fonction
Créez une fonction après avoir supprimé la condition $ a \ geq-b \ geq0, a> 0 $. (De plus, le traitement des exceptions n'est pas effectué lorsque a et b sont 0)
def my_antialias(height, width, a, b, c, w=1):
'''Axe de ligne droite d'épaisseur w sur un plan de hauteur hauteur et largeur largeur+ by + c =Dessinez 0 avec antialiasing.'''
#Ajoutez le montant qui diminue lorsque vous prenez le différentiel en premier
x, y = np.mgrid[:height + 1,:width]
#Calculer t(une fois)
t = 0.5*a - (a*x + b*y + c)
#Calculer τ(une fois)
tau_triangle = (w*(a**2 + b**2)**0.5 +abs(b))/2
tau_square = (w*(a**2 + b**2)**0.5 - abs(b))/2
#Calcul de S
S_red_func = lambda t :\
np.where(t<-tau_triangle,0,
np.where(t<= -tau_square,(t+tau_triangle)**2/(2*(tau_triangle - tau_square)),
(tau_triangle - tau_square)/2))
S_red = S_red_func(t)
S_blue = (tau_triangle - tau_square)/2 - S_red_func(-t)
S_white = np.where(t<-tau_square,0, t+tau_square) + \
np.where(t<tau_square,0, -t+tau_square)
#t,Puisque τ est multiplié par a, divisez par a
S_B = (S_red + S_blue + S_white)*a
return -np.diff(S_B,axis = 0)
plt.imshow(my_antialias(20,20,-3,-7,60,1),cmap = 'gray',vmin = 0,vmax=1)
plt.show()
En passant, ce qui suit est [l'imitation de l'algorithme de Bresenham](http://qiita.com/secang0/items/b45272a6f1212510ef99#%E3%83%96%E3%83%AC%E3%82%BC%E3%83%B3% E3% 83% 8F% E3% 83% A0% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E6% 93% AC% E3% 81% 8D% E3% 81% AB% E3% 82% 88% E3% 82% 8B% E7% 9B% B4% E7% B7% 9A% E6% 8F% C'est une ligne droite générée par 8F% E7% 94% BB). 
Dans mon environnement d'exécution, l'utilisation de l'algorithme de Bresenham était 3 à 4 fois plus rapide.
Recommended Posts