Costura de entalhe - Seam carving
Seam carving (ou redimensionamento líquido ) é um algoritmo para redimensionamento de imagem com reconhecimento de conteúdo , desenvolvido por Shai Avidan , da Mitsubishi Electric Research Laboratories (MERL), e Ariel Shamir , do Centro Interdisciplinar e MERL. Ele funciona estabelecendo uma série de costuras (caminhos de menor importância) em uma imagem e remove costuras automaticamente para reduzir o tamanho da imagem ou insere costuras para estendê-la. O entalhe de costura também permite definir manualmente as áreas nas quais os pixels não podem ser modificados e possui a capacidade de remover objetos inteiros das fotografias.
O objetivo do algoritmo é o redirecionamento de imagem, que é o problema de exibir imagens sem distorção em mídias de vários tamanhos (telefones celulares, telas de projeção) usando padrões de documento, como HTML, que já suportam mudanças dinâmicas no layout da página e no texto, mas não nas imagens .
O retargeting de imagens foi inventado por Vidya Setlur, Saeko Takage, Ramesh Raskar, Michael Gleicher e Bruce Gooch em 2005. O trabalho de Setlur et al. ganhou o prêmio de impacto de 10 anos em 2015.
Costuras
As costuras podem ser verticais ou horizontais. Uma costura vertical é um caminho de pixels conectados de cima para baixo em uma imagem com um pixel em cada linha. Uma costura horizontal é semelhante com a exceção de que a conexão é feita da esquerda para a direita. A função importância / energia avalia um pixel medindo seu contraste com os pixels vizinhos.
Processar
O exemplo a seguir descreve o processo de escultura em costura:
| Etapa | Imagem |
|---|---|
| 1) Comece com uma imagem. |
|
| 2) Calcule o peso / densidade / energia de cada pixel. Isso pode ser feito por vários algoritmos: magnitude do gradiente, entropia, saliência visual, movimento do olhar. Aqui usamos a magnitude do gradiente. |
|
| 3) A partir da energia, faça uma lista de costuras. As costuras são classificadas por energia, sendo as costuras de baixo consumo as de menor importância para o conteúdo da imagem. As costuras podem ser calculadas por meio da abordagem de programação dinâmica abaixo. |
|
| 4) Remova as costuras de baixa energia conforme necessário. |
|
| 5) Imagem final. |
|
As costuras a serem removidas dependem apenas da dimensão (altura ou largura) que se deseja reduzir. Também é possível inverter a etapa 4 para que o algoritmo amplie em uma dimensão, copiando uma costura de baixa energia e calculando a média de seus pixels com seus vizinhos.
Computando costuras
Calcular uma costura consiste em encontrar um caminho de custo mínimo de energia de uma extremidade da imagem a outra. Isso pode ser feito através do algoritmo de Dijkstra , programação dinâmica, algoritmo guloso ou cortes de gráfico, entre outros.
Programaçao dinamica
A programação dinâmica é um método de programação que armazena os resultados de sub-cálculos para simplificar o cálculo de um resultado mais complexo. A programação dinâmica pode ser usada para calcular costuras. Se tentar calcular uma costura vertical (caminho) de energia mais baixa, para cada pixel em uma linha, calculamos a energia do pixel atual mais a energia de um dos três pixels possíveis acima dele.
As imagens abaixo mostram um processo DP para calcular uma costura ideal. Cada quadrado representa um pixel, com o valor superior esquerdo em vermelho representando o valor de energia desse pixel. O valor em preto representa a soma cumulativa das energias que levam até e incluindo esse pixel.
A linha superior não tem nada acima dela, então as energias são as mesmas da imagem de origem.
Para cada pixel no resto das linhas, a energia é sua própria energia mais a mínima das três energias acima. Repita até chegar ao fundo.
Para as energias mais baixas que temos no final, trabalhe de volta nos mínimos para recuperar a costura com o mínimo de energia.
O cálculo de energia é trivialmente paralelizado para funções simples. O cálculo da matriz DP também pode ser paralelizado com alguma comunicação entre processos. No entanto, o problema de fazer várias costuras ao mesmo tempo é mais difícil por dois motivos: a energia precisa ser regenerada para cada remoção para correção e simplesmente rastrear várias costuras pode formar sobreposições. O Avidan 2007 calcula todas as costuras removendo cada costura iterativamente e armazenando um "mapa de índice" para registrar todas as costuras geradas. O mapa contém um número de "enésima costura" para cada pixel da imagem e pode ser usado posteriormente para ajuste de tamanho.
Se ignorarmos os dois problemas, no entanto, uma aproximação gananciosa para o entalhe em costura paralela é possível. Para fazer isso, começa-se com o pixel de energia mínima em uma extremidade e continua escolhendo o caminho de energia mínima para a outra extremidade. Os pixels usados são marcados para que não sejam escolhidos novamente. Costuras locais também podem ser calculadas para partes menores da imagem em paralelo para uma boa aproximação.
questões
- O algoritmo pode precisar de informações fornecidas pelo usuário para reduzir erros. Isso pode consistir em pintar as regiões que devem ser preservadas. Com rostos humanos, é possível usar a detecção de rosto.
- Às vezes, o algoritmo, ao remover uma costura de baixa energia, pode acabar criando inadvertidamente uma costura de alta energia. A solução para isso é simular a remoção de uma costura e, em seguida, verificar o delta de energia para ver se a energia aumenta (energia direta). Em caso afirmativo, prefira outras costuras.
Implementações
A Adobe Systems adquiriu uma licença não exclusiva para tecnologia de entalhe de costura do MERL e a implementou como um recurso no Photoshop CS4, onde é chamado de Content Aware Scaling. Como a licença não é exclusiva, outros aplicativos de computação gráfica populares, entre os quais o GIMP , digiKam , ImageMagick , bem como alguns programas autônomos, entre os quais o iResizer, também possuem implementações dessa técnica, alguns dos quais são lançados como software livre e de código aberto .
Melhorias e extensões
- Melhor função de energia e aplicação ao vídeo, introduzindo costuras 2D (tempo + 1D).
- Implementação mais rápida na GPU.
- Aplicação desta função de energia direta a imagens estáticas.
- Multioperador: Combine com recorte e dimensionamento.
- Remoção muito mais rápida de várias costuras
Uma revisão de 2010 de oito métodos de redirecionamento de imagem descobriu que o entalhe da costura produziu uma saída que foi classificada entre os piores dos algoritmos testados. Era, no entanto, parte de um dos algoritmos de classificação mais alta: a extensão multioperadora mencionada acima (combinada com corte e escala).
Veja também
Referências
links externos
- Demonstração interativa de escultura em costura
- Vídeos de demonstração do Seam Carving:
- no YouTube
- nas páginas de Ariel Shamir no site do Centro Interdisciplinar (resolução superior)
- Explicação sobre o entalhe da costura (redimensionamento líquido) no site da ImageMagick
- Tutorial de implementação de escultura em costura
