Livewire , es una técnica de segmentación que permite al usuario seleccionar regiones de interés para extraerlas de forma rápida y precisa, mediante simples clics del mouse. [1] Está basado en el algoritmo de ruta de menor coste , de Edsger W. Dijkstra . En primer lugar, convoluciona la imagen con un filtro Sobel para extraer bordes. Cada píxel de la imagen resultante es un vértice del gráfico y tiene bordes que van hasta los 4 píxeles que lo rodean, como arriba, abajo, izquierda y derecha. Los costos marginales se definen en función de una función de costos. En 1995, Eric N. Mortensen y William A. Barrett realizaron algunos trabajos de ampliación de la herramienta de segmentación Livewire, conocida como tijeras inteligentes. [2]
El usuario establece el punto de partida haciendo clic en el píxel de una imagen, conocido como ancla. Luego, cuando comienza a mover el mouse sobre otros puntos, la ruta de costo más pequeña se dibuja desde el ancla hasta el píxel donde se encuentra el mouse, y cambia si el usuario mueve el mouse. Si quiere elegir la ruta que se muestra, simplemente vuelve a hacer clic en la imagen.
Se puede ver fácilmente en la imagen de la derecha que los lugares donde el usuario hizo clic para delinear la región de interés deseada están marcados con un pequeño cuadrado. También es fácil ver que el cable se ha roto en los bordes de la imagen.
Convoluciona la imagen con un filtro Sobel para extraer bordes. Usando esta imagen filtrada, cree un gráfico usando píxeles como nodos con bordes en cuatro direcciones (arriba, abajo, izquierda derecha). [1] Los bordes están ponderados con características recopiladas del filtro Sobel, lo que hace que sea menos costoso permanecer en un borde. Son posibles varios métodos de costos diferentes, pero el más importante es la magnitud del gradiente [1]
Algoritmo de búsqueda de gráficos DP 2-D Live-Wire en pseudocódigo [2]
Se ingresa el algoritmo Livewire : s {Píxel inicial (o semilla).} l( q, r ) {Función de costo local para el enlace entre los píxeles q y r.} estructuras de datos: L {Lista de píxeles activos ordenados por coste total (inicialmente vacía).} N( q ) {Conjunto de vecindarios de q (contiene 8 vecinos de píxel).} e( q ) {Función booleana que indica si q ha sido expandido/procesado.} g( q ) {Función de costo total desde el punto inicial hasta q.} salida: p {Puntero de cada píxel que indica la ruta de costo mínimo.} g(s) ← 0; L ← s; {Inicializar la lista activa con un píxel inicial de costo cero.} mientras que L≠∅ comienza {Mientras todavía apunta a expandirse.} q ← min(L); {Eliminar el píxel q de costo mínimo de la lista activa.} e( q ) ← VERDADERO; {Marcar q como expandido (es decir, procesado).} para cada r∈N(q) tal que no e( r ) comience gtmp ←g( q ) + l( q, r ); {Calcule el costo total para el vecino.} si r ∈L y gtmp < g( r ) entonces {Elimine los vecinos con costos más altos de la lista.} r ← L; si r∉L entonces comienza {Si el vecino no está en la lista,} g( r ) ← gtmp; {asignar el costo total del vecino, } pag( r ) ← q ; {establecer (o restablecer) el puntero hacia atrás, } L ← r ; {y colocar en (o regresar a) la lista activa.} end end endEn 2010, Leo Grady amplió el algoritmo Livewire al 3D. [3] Esta extensión trató el algoritmo 2D Livewire como si permitiera al usuario especificar un límite de dimensión 0 (dos puntos) y encontrar el colímite (curva) unidimensional mínimo que conecta esos puntos, donde el mínimo se define en términos de propiedades de la imagen. . Para extender el algoritmo a 3D, se le pide al usuario que especifique uno o más límites unidimensionales (curvas cerradas) y el algoritmo encuentra el colímite (superficie) bidimensional mínimo delimitado por las curvas unidimensionales, donde el La superficie mínima se define en términos de propiedades de la imagen. Esta extensión 3D de Livewire se basa en gran medida en conceptos de cálculo exterior discreto para reinterpretar el algoritmo 2D Livewire desde el punto de vista de los operadores de límite/colímite y luego aplicar estos conceptos en 3D. En el artículo de Grady también se proporciona un algoritmo eficiente para calcular la superficie mínima 3D.