Une implémentation grossière du lasso magnétique dans Photoshop (basé sur Python)

Ceux qui utilisent fréquemment Photoshop doivent être familiers avec la fonction Lasso magnétique, qui est un outil auxiliaire de découpe guidé par l'homme. On ne l'appelle généralement pas ainsi dans le domaine de la R&D. Cette méthode d'extraction des bords est généralement appelée Intelligent Scissors ou Livewire.

Il s'agissait à l'origine d'un framework Python pour l'évaluation d'algorithmes d'un projet de segmentation d'images, j'ai trouvé cela un peu intéressant, alors je l'ai un peu étendu, j'ai ajouté un shell avec PyQt et j'ai simulé le lasso magnétique de manière très. manière brute. Pourquoi c'est simple : 1) Seule la recherche de contour la plus élémentaire est implémentée. Il n'y a pas de refroidissement du chemin, d'entraînement dynamique, de correction de la position de la souris, encore moins de fermeture de courbe, de découpe, d'Alpha Matting, etc. 2) Aucune spécification de performance n'est prise en compte, juste pour la commodité de l'écriture ; Qt, et je n'arrive toujours pas à écrire Signal-Slot, je ne sais pas si l'interface graphique est écrite de manière raisonnable 4) Pas de débogage ;

Algorithme de base

Je n'ai pas fait de recherches approfondies sur les algorithmes associés, mais je crois que ce type d'algorithme L'algorithme le plus influent en application vient de [1], qui est également la référence principale de cet article. L'idée de base est de considérer l'image comme un graphe non orienté, et un coût local peut être calculé entre pixels adjacents. , il est donc converti en Maintenant que le problème du chemin le plus court a été résolu, l'étape suivante consiste à générer un chemin basé sur l'algorithme de Dijkstra, qui est l'arête qui doit être extraite. Deux algorithmes principaux sont impliqués : 1) le calcul du coût des pixels adjacents ; 2) l'algorithme du chemin le plus court ;

Détection des contours

Le but ultime du calcul du coût des pixels adjacents est de trouver les contours, l'essence est donc la détection des contours. L'idée de base est de détecter les contours par divers moyens et de calculer une valeur pondérée basée sur l'intensité détectée comme coût. Du point de vue du chemin le plus court, plus l’avantage est évident, plus le coût est faible. La suggestion dans [1] est d'utiliser trois indicateurs pour la pondération : 1) opérateur de détection de bord ; 2) force du gradient (Magnitude du gradient) ; 3) direction du gradient (Direction du gradient). La méthode de cet article est légèrement différente de celle de [1]. En raison de la paresse, l'opérateur Canny dans OpenCV est utilisé pour détecter les bords au lieu de l'opérateur laplacien de passage à zéro. L'expression est la suivante :

[lleft( p,q right)={{w}_{E}}{{f}_{E}}left( q right) {{w}_{ G} }{{f}_{G}}gauche( q droite) {{w}_{D}}{{f}_{D}}gauche( p,q droite)]

Opérateur Canny

L'idée de base est d'abord de détecter de nombreux pixels connectés en fonction des informations de dégradé, puis de ne prendre que la partie la plus grande et connectée de chaque pixel connecté, de définir le l'environnement à zéro pour obtenir les bords initiaux (Edges), ce processus est appelé suppression non maximale. Utilisez ensuite une méthode à deux seuils pour diviser ces bords initiaux détectés en trois niveaux : Fort, Faible et Aucun. Comme son nom l'indique, Fort est définitivement un bord, Aucun n'est ignoré, puis ceux connectés à Fort sont sélectionnés parmi Faibles. Lorsque le bord est conservé, le résultat final est obtenu. Ce processus est appelé seuil d'hystérésis. Cet algorithme est tellement classique que je n’entrerai pas dans les détails dès que Google apporte beaucoup de détails. La formule est la suivante :

[{{f}_{E}}left( q right)=left{ start{matrix}
0;text{ if }qtext{ est sur une arête} \
1;text{ if }qtext{ n'est pas sur une arête} \
end{matrix} right.]

En fait, le calcul des poids est quelque peu répétitif avec le gradient maximum, parce que si le long du maximum, le chemin trouvé dans la direction du gradient est essentiellement le bord. Ma compréhension du rôle de cet élément est principalement de 1) éviter l'écart par rapport au bord évident dans les zones à forts gradients 2) assurer la continuité des bords extraits ; , dans une certaine mesure, il est également garanti d'être fluide.

Force du gradient

est simplement le module du gradient. Les carrés des valeurs de gradient dans les directions x et y sont ajoutés. à la racine carrée. La formule est la suivante ：

[{{I}_{G}}left( q right)=sqrt{{{I}_{x}}left( q right) { {I}_{y}}gauche( q droite)}]

Parce qu'un coût est requis, inversez et normalisez :

[{{f}_{G}}gauche( q droite )=1-frac{{ {I}_{G}}gauche( q droite)}{max gauche( {{I}_{G}} droite)}]

Direction du dégradé

Cet élément est en fait un élément de lissage, qui attribuera un coût relativement élevé aux bords qui changent radicalement, afin que les bords extraits puissent éviter l'influence du bruit. La formule spécifique est la suivante :

[{{f}_{D}}left( p,q right)=frac{2}{3pi }left( arccos left( {{d}_{p }}gauche ( p,q droite) droite) arccos gauche( {{d}_{q}}gauche( p,q droite) droite) droite)]

Parmi eux,

[{{d }_{p}}gauche( p,q droite)=leftlangle {{d}_{bot }}gauche( p droite),{{l}_{D}}gauche( p,q droite) angle droit ]

[{{d}_{q}}gauche( p,q droite)=leftlangle {{l}_{D}}gauche( p,q droite),{{d}_{ bot }}left ( q right) rightrangle ]

[{{l}_{D}}left( p,q right)=left{begin{matrix}
q-p;text{ if }leftlangle {{d} _{bot }}gauche( p à droite),q-p rightrangle ge 0 \
p-q;text{ if }leftlangle {{d}_{bot }}gauche( p à droite),q-p rightrangle <0 \
fin{matrice} à droite.]

({{d}_{bot }}left( p right)) doit prendre la direction verticale de p. Notez également que le jugement du signe dans la formule ci-dessus fera ({{d}_{bot. }}left( p right )) et ({{l}_{D}}left( p,q right)) sont limités à π/2.

[{{d}_{bot }}gauche( p droite)=gauche( {{p}_{y}},-{{p}_{x}} droite)]

Correction des coûts dans le sens diagonal

Dans les images bidimensionnelles, les pixels adjacents sont généralement divisés en deux types en fonction de la distance euclidienne : 1) Adjacent vers le haut , en bas, à gauche et à droite, l'intervalle est la longueur du côté du pixel ; 2) Adjacent en diagonale, l'intervalle est (sqrt{2}) fois la longueur du côté du pixel. Lors du calcul du coût local, l'impact de cette différence de distance doit généralement être pris en compte, comme l'image suivante :

Si l'influence de la position du pixel n'est pas prise en compte, alors lors de la recherche du coût minimum, le coût=2 dans le coin supérieur gauche sera considéré comme le minimum. Cependant, si nous considérons l'influence de l'espacement des pixels, regardons la direction du coin supérieur gauche, la différence par rapport au centre est de 6-2. Si nous effectuons une interpolation linéaire, la valeur de la distance unitaire du coin supérieur gauche par rapport au centre. le centre doit être (6-gauche (6- 2 droite) fois 1/sqrt{2} =3,17>3), donc celui directement au-dessus est la direction correcte du coût minimum.

Recherche du chemin le plus court

Dans le lasso magnétique, l'usage général est de cliquer d'abord sur un point, puis de déplacer la souris, entre la souris et le point A initialement cliqué Une ligne automatiquement proche du bord apparaîtra entre eux. Ici, nous définissons le point de pixel cliqué au début comme le point de départ (seed). Le lasso magnétique trouve en fait le point de départ en tenant compte du coût lié au bord mentionné dans la partie précédente. Le chemin le plus court de la souris actuelle. Comme le montre l'image ci-dessous, les rouges sont des points de départ, et lorsque vous déplacez la souris, la connexion entre le point de départ le plus proche du bord et les coordonnées de la souris sera affichée en temps réel. C'est pourquoi le lasso magnétique est également. appelé Livewire.

Il existe de nombreuses façons d'obtenir le chemin le plus court. De manière générale, il s'agit d'une programmation dynamique. Ce qui est présenté ici est une implémentation basée sur l'algorithme de Dijkstra. , étant donné un point de départ Enfin, l'algorithme de Dijkstra est exécuté pour parcourir tous les pixels de l'image afin d'obtenir le chemin le plus court de chaque pixel au point de départ. Prenons l'image ci-dessous comme exemple. Dans une matrice de coûts, après avoir utilisé l'algorithme de Dijkstra pour parcourir chaque élément, chaque élément pointera vers un élément adjacent, de sorte que n'importe quel pixel puisse trouver un chemin vers la graine, comme le coin supérieur droit. . Les pixels correspondant à 42 et 39 suivent la flèche vers 0.

L'algorithme est le suivant :

输入:
  s              // 种子点
  l(q,r)         // 计算局部cost

数据结构:
  L             // 当前待处理的像素
  N(q)          // 当前像素相邻的像素
  e(q)          // 标记一个像素是否已经做过相邻像素展开的Bool函数
  g(q)          // 从s到q的总cost

输出:
  p             // 记录所有路径的map

算法:
  g(s)←0; L←s;                 // 将种子点作为第一点初始化
  while L≠Ø:                   // 遍历尚未结束
    q←min(L);                  // 取出最小cost的像素并从待处理像素中移除
    e(q)←TRUE;                 // 将当前像素记录为已经做过相邻像素展开
    for each r∈N(q) and not e(r):
      gtemp←g(q)+l(q,r);        // 计算相邻像素的总cost
      if r∈L and gtemp<g(r):    // 找到了更好的路径
        r←L; { from list.}     // 舍弃较大cost的路径
      else if r∉L:
        g(r)←gtemp;             // 记录当前找到的最小路径
        p(r)←q;
        L←r;                    // 加入待处理以试图寻找更短的路径

Le processus de traversée donnera la priorité à la zone ayant le coût le plus bas, comme indiqué ci-dessous :

Une fois que le chemin le plus court vers le pixel graine correspondant à tous les pixels est trouvé, dessinez simplement le chemin le plus court vers la graine directement lorsque vous déplacez la souris.

Implémentation Python

La partie algorithme appelle directement la fonction Canny et la fonction Sobel d'OpenCV (pour le dégradé), et le traitement du RVB est également très simple , directement approché par la valeur maximale du gradient. De plus, en raison de la paresse, la carte des coûts et la carte du chemin utilisent directement des dictionnaires (dict), tandis que l'enregistrement des pixels agrandis utilise directement des ensembles (set). La partie GUI utilise le threading de Python car je ne sais pas comment utiliser QThread. Seule l'image affiche la zone interactive et l'invite de la barre d'état. Cliquez avec le bouton gauche pour définir le point de départ et cliquez avec le bouton droit pour terminer. une ligne verte et le bord extrait est une ligne bleue.

Code

Partie algorithme

from __future__ import division
import cv2
import numpy as np

SQRT_0_5 = 0.70710678118654757

class Livewire():
    """
    A simple livewire implementation for verification using 
        1. Canny edge detector + gradient magnitude + gradient direction
        2. Dijkstra algorithm
    """
    
    def __init__(self, image):
        self.image = image
        self.x_lim = image.shape[0]
        self.y_lim = image.shape[1]
        # The values in cost matrix ranges from 0~1
        self.cost_edges = 1 - cv2.Canny(image, 85, 170)/255.0
        self.grad_x, self.grad_y, self.grad_mag = self._get_grad(image)
        self.cost_grad_mag = 1 - self.grad_mag/np.max(self.grad_mag)
        # Weight for (Canny edges, gradient magnitude, gradient direction)
        self.weight = (0.425, 0.425, 0.15)
        
        self.n_pixs = self.x_lim * self.y_lim
        self.n_processed = 0
    
    @classmethod
    def _get_grad(cls, image):
        """
        Return the gradient magnitude of the image using Sobel operator
        """
        rgb = True if len(image.shape) > 2 else False
        grad_x = cv2.Sobel(image, cv2.CV_64F, 1, 0, ksize=3)
        grad_y = cv2.Sobel(image, cv2.CV_64F, 0, 1, ksize=3)
        if rgb:
            # A very rough approximation for quick verification...
            grad_x = np.max(grad_x, axis=2)
            grad_y = np.max(grad_y, axis=2)
            
        grad_mag = np.sqrt(grad_x**2+grad_y**2)
        grad_x /= grad_mag
        grad_y /= grad_mag
        
        return grad_x, grad_y, grad_mag
    
    def _get_neighbors(self, p):
        """
        Return 8 neighbors around the pixel p
        """
        x, y = p
        x0 = 0 if x == 0 else x - 1
        x1 = self.x_lim if x == self.x_lim - 1 else x + 2
        y0 = 0 if y == 0 else y - 1
        y1 = self.y_lim if y == self.y_lim - 1 else y + 2
        
        return [(x, y) for x in xrange(x0, x1) for y in xrange(y0, y1) if (x, y) != p]
    
    def _get_grad_direction_cost(self, p, q):
        """
        Calculate the gradient changes refer to the link direction
        """
        dp = (self.grad_y[p[0]][p[1]], -self.grad_x[p[0]][p[1]])
        dq = (self.grad_y[q[0]][q[1]], -self.grad_x[q[0]][q[1]])
        
        l = np.array([q[0]-p[0], q[1]-p[1]], np.float)
        if 0 not in l:
            l *= SQRT_0_5
        
        dp_l = np.dot(dp, l)
        l_dq = np.dot(l, dq)
        if dp_l < 0:
            dp_l = -dp_l
            l_dq = -l_dq
        
        # 2/3pi * ...
        return 0.212206590789 * (np.arccos(dp_l)+np.arccos(l_dq))
    
    def _local_cost(self, p, q):
        """
        1. Calculate the Canny edges & gradient magnitude cost taking into account Euclidean distance
        2. Combine with gradient direction
        Assumption: p & q are neighbors
        """
        diagnol = q[0] == p[0] or q[1] == p[1]
        
        # c0, c1 and c2 are costs from Canny operator, gradient magnitude and gradient direction respectively
        if diagnol:
            c0 = self.cost_edges[p[0]][p[1]]-SQRT_0_5*(self.cost_edges[p[0]][p[1]]-self.cost_edges[q[0]][q[1]])
            c1 = self.cost_grad_mag[p[0]][p[1]]-SQRT_0_5*(self.cost_grad_mag[p[0]][p[1]]-self.cost_grad_mag[q[0]][q[1]])
            c2 = SQRT_0_5 * self._get_grad_direction_cost(p, q)
        else:
            c0 = self.cost_edges[q[0]][q[1]]
            c1 = self.cost_grad_mag[q[0]][q[1]]
            c2 = self._get_grad_direction_cost(p, q)
        
        if np.isnan(c2):
            c2 = 0.0
        
        w0, w1, w2 = self.weight
        cost_pq = w0*c0 + w1*c1 + w2*c2
        
        return cost_pq * cost_pq

    def get_path_matrix(self, seed):
        """
        Get the back tracking matrix of the whole image from the cost matrix
        """
        neighbors = []          # 8 neighbors of the pixel being processed
        processed = set()       # Processed point
        cost = {seed: 0.0}      # Accumulated cost, initialized with seed to itself
        paths = {}

        self.n_processed = 0
        
        while cost:
            # Expand the minimum cost point
            p = min(cost, key=cost.get)
            neighbors = self._get_neighbors(p)
            processed.add(p)

            # Record accumulated costs and back tracking point for newly expanded points
            for q in [x for x in neighbors if x not in processed]:
                temp_cost = cost[p] + self._local_cost(p, q)
                if q in cost:
                    if temp_cost < cost[q]:
                        cost.pop(q)
                else:
                    cost[q] = temp_cost
                    processed.add(q)
                    paths[q] = p
            
            # Pop traversed points
            cost.pop(p)
            
            self.n_processed += 1
        
        return paths

livewire.py

livewire.py

Partie GUI

 from __future__ import division
import time
import cv2
from PyQt4 import QtGui, QtCore
from threading import Thread
from livewire import Livewire

class ImageWin(QtGui.QWidget):
    def __init__(self):
        super(ImageWin, self).__init__()
        self.setupUi()
        self.active = False
        self.seed_enabled = True
        self.seed = None
        self.path_map = {}
        self.path = []
        
    def setupUi(self):
        self.hbox = QtGui.QVBoxLayout(self)
        
        # Load and initialize image
        self.image_path = ''
        while self.image_path == '':
            self.image_path = QtGui.QFileDialog.getOpenFileName(self, '', '', '(*.bmp *.jpg *.png)')
        self.image = QtGui.QPixmap(self.image_path)
        self.cv2_image = cv2.imread(str(self.image_path))
        self.lw = Livewire(self.cv2_image)
        self.w, self.h = self.image.width(), self.image.height()
        
        self.canvas = QtGui.QLabel(self)
        self.canvas.setMouseTracking(True)
        self.canvas.setPixmap(self.image)
        
        self.status_bar = QtGui.QStatusBar(self)
        self.status_bar.showMessage('Left click to set a seed')
        
        self.hbox.addWidget(self.canvas)
        self.hbox.addWidget(self.status_bar)
        self.setLayout(self.hbox)
    
    def mousePressEvent(self, event):            
        if self.seed_enabled:
            pos = event.pos()
            x, y = pos.x()-self.canvas.x(), pos.y()-self.canvas.y()
            
            if x < 0:
                x = 0
            if x >= self.w:
                x = self.w - 1
            if y < 0:
                y = 0
            if y >= self.h:
                y = self.h - 1

            # Get the mouse cursor position
            p = y, x
            seed = self.seed
            
            # Export bitmap
            if event.buttons() == QtCore.Qt.MidButton:
                filepath = QtGui.QFileDialog.getSaveFileName(self, &#39;Save image audio to&#39;, &#39;&#39;, &#39;*.bmp\n*.jpg\n*.png&#39;)
                image = self.image.copy()
                
                draw = QtGui.QPainter()
                draw.begin(image)
                draw.setPen(QtCore.Qt.blue)
                if self.path_map:
                    while p != seed:
                        draw.drawPoint(p[1], p[0])
                        for q in self.lw._get_neighbors(p):
                            draw.drawPoint(q[1], q[0])
                        p = self.path_map[p]
                if self.path:
                    draw.setPen(QtCore.Qt.green)
                    for p in self.path:
                        draw.drawPoint(p[1], p[0])
                        for q in self.lw._get_neighbors(p):
                            draw.drawPoint(q[1], q[0])
                draw.end()
                
                image.save(filepath, quality=100)
            
            else:
                self.seed = p
                
                if self.path_map:
                    while p != seed:
                        p = self.path_map[p]
                        self.path.append(p)
                
                # Calculate path map
                if event.buttons() == QtCore.Qt.LeftButton:
                    Thread(target=self._cal_path_matrix).start()
                    Thread(target=self._update_path_map_progress).start()
                
                # Finish current task and reset
                elif event.buttons() == QtCore.Qt.RightButton:
                    self.path_map = {}
                    self.status_bar.showMessage(&#39;Left click to set a seed&#39;)
                    self.active = False
    
    def mouseMoveEvent(self, event):
        if self.active and event.buttons() == QtCore.Qt.NoButton:
            pos = event.pos()
            x, y = pos.x()-self.canvas.x(), pos.y()-self.canvas.y()

            if x < 0 or x >= self.w or y < 0 or y >= self.h:
                pass
            else:
                # Draw livewire
                p = y, x
                path = []
                while p != self.seed:
                    p = self.path_map[p]
                    path.append(p)
                
                image = self.image.copy()
                draw = QtGui.QPainter()
                draw.begin(image)
                draw.setPen(QtCore.Qt.blue)
                for p in path:
                    draw.drawPoint(p[1], p[0])
                if self.path:
                    draw.setPen(QtCore.Qt.green)
                    for p in self.path:
                        draw.drawPoint(p[1], p[0])
                draw.end()
                self.canvas.setPixmap(image)
    
    def _cal_path_matrix(self):
        self.seed_enabled = False
        self.active = False
        self.status_bar.showMessage(&#39;Calculating path map...&#39;)
        path_matrix = self.lw.get_path_matrix(self.seed)
        self.status_bar.showMessage(r&#39;Left: new seed / Right: finish&#39;)
        self.seed_enabled = True
        self.active = True
        
        self.path_map = path_matrix
    
    def _update_path_map_progress(self):
        while not self.seed_enabled:
            time.sleep(0.1)
            message = &#39;Calculating path map... {:.1f}%&#39;.format(self.lw.n_processed/self.lw.n_pixs*100.0)
            self.status_bar.showMessage(message)
        self.status_bar.showMessage(r&#39;Left: new seed / Right: finish&#39;)

gui.py

gui.py

fonction principale

import sys
from PyQt4 import QtGui
from gui import ImageWin

def main():
    app = QtGui.QApplication(sys.argv)
    window = ImageWin()
    window.setMouseTracking(True)
    window.setWindowTitle('Livewire Demo')
    window.show()
    window.setFixedSize(window.size())
    sys.exit(app.exec_())

if __name__ == '__main__':
    main()    

main.py

main. py

a été péniblement téléchargé sur Github (portail), bienvenue sur fork.

Améliorations de l'efficacité

Étant donné que le prototype de ce code est uniquement destiné à l'évaluation et à la vérification Python avant le développement en C, l'efficacité n'est pas du tout prise en compte et la vitesse d'exécution est complètement inacceptable. , en gros je ne supporte pas l'image 400x400... Quant à l'amélioration de l'efficacité basée sur la version Python, je n'y ai pas bien réfléchi, mais il semble qu'il y ait quelques endroits évidents :

1) Supprimer le coût minimum actuel de l'opération Pixel

p = min(cost, key=cost.get)

Bien que ce soit amusant à écrire , ce n'est évidemment pas possible. Au moins un tas min doit être utilisé. Parce que j'ai utilisé dict pour représenter à la fois les pixels à traiter et le coût, et que j'étais trop paresseux pour réfléchir à la façon de le combiner avec le heapq de Python, j'ai donc simplement utilisé le min() brut et sans problème.

2) Calcul de la direction du gradient

Le calcul des fonctions trigonométriques doit être évité autant que possible. De plus, l'article original peut être d'étendre la plage de valeurs à >π, donc q-p est également utilisé. L'élément a un petit poids, donc j'ai bien peur qu'il soit acceptable de simplement faire un produit scalaire des vecteurs de direction de dégradé des deux pixels, puis de normaliser le résultat. Même si vous souhaitez utiliser arccos, vous pouvez envisager d'écrire une approximation de table de recherche. Bien sûr, la dernière chose que je veux dire, c'est que je pense personnellement que ce n'est vraiment pas nécessaire. Un spilne adaptatif direct ou même un effet de lissage et de débruitage moyen en trois points sera bon.

3) Calculer la position des pixels adjacents

Si deux pixels sont adjacents, les 8 pixels adjacents autour d'eux coïncideront également. Ma méthode est relativement primitive et permet de calculer le taux directement sans modularisation.

4) Remplacer certaines structures de données

Par exemple, la carte de chemin donne essentiellement le pixel précédent sur le chemin le plus court pour chaque pixel, qui est une matrice. En fait, vous pouvez envisager d’utiliser une structure de données linéaire à la place, mais si vous faites cela, ce sera généralement en code C/C.

5) numpy

À mon avis, l'ordre d'appel de numpy affectera également l'efficacité. L'appel continu des méthodes intégrées de numpy semble entraîner une amélioration globale de l'efficacité, mais ensuite. encore une fois, s'il atteint cette étape dans l'application réelle, il devrait également entrer dans la catégorie du code C/C.

6) Améliorations au niveau de l'algorithme

Ce domaine n'a pas été étudié en profondeur. La première impression est que dans les applications pratiques, il n'est pas nécessaire de calculer l'image entière au début. Certaines divisions de blocs peuvent être effectuées en fonction de la position de départ, la souris elle-même quittera également une trajectoire, et vous pouvez également envisager d'effectuer une recherche heuristique uniquement dans la direction de la trajectoire de la souris. De plus, lors du calcul du chemin, vous pouvez envisager d'emprunter des idées similaires à Image Pyramid. Il n'est pas nécessaire de rechercher le chemin en pleine résolution dès le début. Comme les projets que j'ai réalisés plus tard n'utilisaient pas cet algorithme, je n'ai pas continué à l'étudier. Même si j'étais très curieux, il existe en fait beaucoup de codes prêts à l'emploi, comme GIMP, mais je n'avais pas l'énergie pour le faire. regarde-le.

Plus d'améliorations

Bien qu'aucune d'entre elles n'ait été réalisée, je vais les présenter brièvement et examiner les améliorations pratiques.

Refroidissement du chemin

Quiconque a utilisé Photoshop et GIMP Magnetic Lasso sait que même si la souris ne clique pas sur l'image, elle se déplacera automatiquement pendant le mouvement. Générez des points qui fixent la trajectoire de découpe. Ces points sont en fait de nouveaux points de départ. Cette méthode de génération automatique de nouveaux points de départ pendant l'utilisation est appelée Refroidissement du chemin. L'idée de base de cette méthode est la suivante : au fur et à mesure que la souris se déplace, si un chemin reste fixe pendant un certain temps, alors le point le plus éloigné de la graine dans ce chemin est défini comme la nouvelle graine. se cache derrière elle l'idée dynamique de la planification, l'optimalité de Bellman. Le nom est également assez vif, rafraîchissant le chemin.

Entraînement dynamique interactif

Lorsque vous utilisez la recherche simple du chemin le plus court, les bords souvent trouvés ne sont pas ceux que vous souhaitez. Par exemple, dans l'image ci-dessus, la ligne verte est le bord extrait dans la section précédente et la ligne bleue est le bord en cours d'extraction. Dans l'image de gauche, le bord du chapeau de Lena à l'extérieur du miroir est ce que nous voulons extraire. Cependant, comme le bord du chapeau de Lena dans le miroir a un coût inférieur, le segment de ligne bleue réellement extrait est collé à droite comme suit. sur la photo de droite. Ainsi, l'idée de l'entraînement dynamique interactif est de considérer le segment de ligne verte comme le bord correctement extrait, puis d'utiliser le segment de ligne verte comme données d'entraînement pour ajouter une valeur de correction à la fonction de coût de l'extraction de bord actuelle.

[1] consiste à compter l'histogramme de l'intensité du dégradé des points sur le bord du segment précédent, puis à pondérer les pixels de l'image actuelle en fonction de la fréquence d'apparition du dégradé. Par exemple, si l'intensité du gradient correspondant à tous les pixels du segment de ligne verte est comprise entre 50 et 100, alors 50 à 100 peuvent être divisés en 5 groupes par unités de 10, et la fréquence d'apparition dans chaque groupe peut être comptée. est un histogramme, puis pondère linéairement l'intensité du gradient actuellement détectée. Par exemple, s'il y a au plus 10 pixels correspondants dans la plage de 50 à 60, alors 10 est considéré comme la valeur maximale, et les pixels dont l'intensité de gradient est actuellement détectée entre 50 et 60 sont multipliés par un coefficient de 1,0 ; les données d'entraînement sont de 70 ~ Il y en a 5 entre 80, alors le coefficient de pondération des coûts est de 5/10 = 0,5, puis tous les pixels avec des forces de gradient actuellement détectées entre 70 et 80 sont multipliés par le coefficient de 0,5 s'il n'y a pas de pixels supérieurs à 100 dans ; les données d'entraînement, donc le coût est ajouté à 0/10=0, et le coefficient de pondération est 0, de sorte que même si un bord plus fort est détecté, il ne s'écartera pas du bord précédent. C'est l'idée de base. Bien entendu, la mise en œuvre réelle n'est pas si simple. En plus des pixels sur le bord, il faut également prendre en compte les deux pixels à gauche et à droite sur le bord vertical, garantissant ainsi le motif des bords. De plus, à mesure que la souris s'éloigne du bord d'entraînement, le motif du bord détecté peut apparaître différent, de sorte que l'entraînement peut avoir un effet contre-productif. Par conséquent, la portée de cet entraînement doit également prendre en compte la distance. la souris à partir du point de départ, et enfin Il doit y avoir un traitement de lissage et de débruitage. Les détails sont mentionnés dans [1]. C'est assez fastidieux (il semble qu'il n'y avait pas de SIFT à ce moment-là), donc je ne le ferai pas. entrer dans les détails.

Correction de la position du point de départ (Cursor Snap)

Bien que cet algorithme puisse trouver automatiquement le chemin le plus proche du bord entre le point de départ et la souris, cependant, l'humain Mes mains tremblent souvent, de sorte que les points de départ ne sont peut-être pas bien fixés au bord. Par conséquent, une fois que l'utilisateur a défini la position du point de départ, le pixel ayant le coût le plus bas peut être automatiquement recherché dans une petite plage autour de ses coordonnées, comme une zone 7x7, comme position réelle du point de départ. Ce processus est appelé accrochage du curseur.

Pour en savoir plus sur une implémentation simple du lasso magnétique dans Photoshop (basé sur Python), veuillez faire attention au site Web PHP chinois pour les articles connexes !