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

self_concept.png 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 antiali.png

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)

triangles.png

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.

triangle_red.png

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. triangle_blue.png 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')

img_how_long.png

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

antinalias.png

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). bresenham.png

Dans mon environnement d'exécution, l'utilisation de l'algorithme de Bresenham était 3 à 4 fois plus rapide.

Recommended Posts

Dessin linéaire avec une matrice - Recherche originale par un réinventeur du traitement d'image Python -
Échelle de gris par matrice-Reinventor of Python image processing-
Dessin avec Matrix-Reinventor of Python Image Processing-
Traitement d'image par matrice Basics & Contents-Reinventor of Python image processing-
Traitement d'image par python (Pillow)
Bases du traitement d'images binarisées par Python
Traitement d'image par le remplacement du canal Python 100 Knock # 1
Traitement d'image par Python 100 Knock # 6 Traitement de réduction de couleur
Analyse d'image de microtomographie à rayons X par Python
Filtrage par convolution par matrice-Reinventor of Python image processing-
traitement d'image python
Traitement d'image? L'histoire du démarrage de Python pour
Traitement d'image par filtre de lissage Python 100 knock # 11 (filtre moyen)
Conversion d'affine par matrice (agrandissement / réduction / rotation / cisaillement / mouvement) -Réinventeur du traitement d'image Python-
[Traitement du langage 100 coups 2020] Résumé des exemples de réponses par Python
Traitement de la communication par Python
Premier traitement d'image Python
Traitement d'image avec Python
Divers traitements de Python
Traitement d'image avec Python (partie 2)
Traitement d'image avec Python (partie 1)
Traitement d'image avec Python (3)
Post-traitement de python (NG)
Collection de traitement d'image en Python
[Python] Traitement d'image avec scicit-image
Lire la sortie standard d'un sous-processus ligne par ligne en Python
Traitement d'image par Python 100 knock # 4 Binarisation Otsu (méthode d'analyse de discrimination)
Traitement des arguments de ligne de commande (docopt Python)
Erreur divisée par 0 Traitement de ZeroDivisionError 2
Extension du dictionnaire python par argument
Apprenez Python en dessinant (Turtle Graphics)
Notes personnelles pour le traitement d'images python
Traitement d'image avec la binarisation Python 100 knocks # 3
Tracé de la droite de régression par tracé des résidus
Introduction du package de dessin python pygal
Comportement de python3 par le serveur de Sakura
Implémentation du tri original en Python
100 traitement d'image par Python Knock # 2 Échelle de gris
100 Language Processing Knock Chapitre 1 par Python
Histoire d'approximation de puissance par Python
Traitement du japonais par Python3 (5) Apprentissage d'ensemble de différents modèles par Voting Classifier