El tallado de costuras (o reescalado líquido ) es un algoritmo para redimensionar imágenes según el contenido , desarrollado por Shai Avidan, de Mitsubishi Electric Research Laboratories (MERL), y Ariel Shamir , del Interdisciplinary Center y MERL. Funciona estableciendo un número de costuras (caminos de menor importancia) en una imagen y elimina automáticamente las costuras para reducir el tamaño de la imagen o inserta costuras para extenderla. El tallado de costuras también permite definir manualmente áreas en las que no se pueden modificar los píxeles y presenta la capacidad de eliminar objetos completos de las fotografías.
El objetivo del algoritmo es la reorientación de imágenes, que es el problema de mostrar imágenes sin distorsión en medios de varios tamaños (teléfonos celulares, pantallas de proyección) utilizando estándares de documentos, como HTML, que ya admiten cambios dinámicos en el diseño de la página y el texto, pero no en las imágenes. [1]
El retargeting de imágenes fue inventado por Vidya Setlur, Saeko Takage, Ramesh Raskar, Michael Gleicher y Bruce Gooch en 2005. [2] El trabajo de Setlur et al. ganó el premio de impacto de 10 años en 2015 [ ¿dónde? ] .
Las uniones pueden ser verticales u horizontales. Una unión vertical es una ruta de píxeles conectados de arriba a abajo en una imagen con un píxel en cada fila. [1] Una unión horizontal es similar con la excepción de que la conexión es de izquierda a derecha. La función de importancia/energía valora un píxel midiendo su contraste con los píxeles vecinos.
El siguiente ejemplo describe el proceso de tallado de costura:
Las costuras que se deben eliminar dependen únicamente de la dimensión (altura o anchura) que se desea reducir. También es posible invertir el paso 4 para que el algoritmo amplíe en una dimensión copiando una costura de baja energía y promediando sus píxeles con sus vecinos. [1]
El cálculo de una costura consiste en encontrar un camino de mínimo coste energético desde un extremo de la imagen hasta el otro. Esto se puede hacer mediante el algoritmo de Dijkstra , programación dinámica, algoritmo voraz o cortes de grafos , entre otros. [1]
La programación dinámica es un método de programación que almacena los resultados de subcálculos para simplificar el cálculo de un resultado más complejo. La programación dinámica se puede utilizar para calcular costuras. Si se intenta calcular una costura vertical (trayectoria) de menor energía, para cada píxel de una fila calculamos la energía del píxel actual más la energía de uno de los tres píxeles posibles que se encuentran por encima de él.
Las imágenes a continuación muestran un proceso de DP para calcular una costura óptima. [1] Cada cuadrado representa un píxel, y el valor superior izquierdo en rojo representa el valor de energía de ese píxel. El valor en negro representa la suma acumulada de energías que conducen hasta ese píxel e incluyen ese píxel.
El cálculo de energía se paraleliza de manera trivial para funciones simples. El cálculo de la matriz DP también se puede paralelizar con alguna comunicación entre procesos. Sin embargo, el problema de realizar múltiples costuras al mismo tiempo es más difícil por dos razones: la energía debe regenerarse para cada eliminación para que sea correcta y simplemente rastrear múltiples costuras puede formar superposiciones. Avidan 2007 calcula todas las costuras eliminando cada costura de manera iterativa y almacenando un "mapa de índice" para registrar todas las costuras generadas. El mapa contiene un número de "costura n" para cada píxel de la imagen y se puede usar más tarde para ajustar el tamaño. [1]
Sin embargo, si se ignoran ambos problemas, es posible realizar una aproximación codiciosa para el tallado de costuras paralelas. Para ello, se comienza con el píxel de energía mínima en un extremo y se sigue eligiendo la ruta de energía mínima hasta el otro extremo. Los píxeles utilizados se marcan para que no se vuelvan a seleccionar. [3] También se pueden calcular costuras locales para partes más pequeñas de la imagen en paralelo para lograr una buena aproximación. [4]
Adobe Systems adquirió una licencia no exclusiva para la tecnología de tallado de costuras de MERL, [6] y la implementó como una característica en Photoshop CS4, donde se llama Content Aware Scaling. [7] Como la licencia no es exclusiva, otras aplicaciones de gráficos de computadora populares (por ejemplo, GIMP , digiKam e ImageMagick ), así como algunos programas independientes (por ejemplo, iResizer) [8] también tienen implementaciones de esta técnica, algunas de las cuales se lanzan como software gratuito y de código abierto . [9] [10] [11]
En 2010, una revisión de ocho métodos de redireccionamiento de imágenes concluyó que el tallado de costuras producía resultados que se clasificaron entre los peores de los algoritmos probados. Sin embargo, era parte de uno de los algoritmos de mayor clasificación: la extensión multioperador mencionada anteriormente (combinada con recorte y escalado). [15]