Objetivo

Implementar o método “image quilting” proposto em:  Efros, Alexei A. & Freeman William T. Image Quilting for Texture Synthesis and Transfer - Proceedings of SIGGRAPH '01, Los Angeles, California, August, 2001.

Resumo

Trata-se de um método simples que gera uma nova aparência visual, ou seja, uma nova imagem é sintetizada "costurando-se" adequadamente blocos de uma imagem existente.

Este trabalho foi desenvolvido por Edinalda Souza (edinalda@inf.puc-rio.br) como projeto final para a disciplina Processamento de Imagens oferecida pelo IMPA - Instituto de Matemática Pura e Aplicada - durante o segundo semestre de 2001 e ministrada pelo professor Luis Velho.

Motivação

Um fato curioso sobre os algoritmos de síntese de imagens que sintetizam um pixel por vez é que, mesmo para texturas complexas, a maioria dos pixels já têm seu valor totalmente determinado pelos pixels que já foram sintetizados. Como exemplo considere um algoritmo que sintetiza um padrão de círculos no plano. Depois que o algoritmo começou a sintetizar um determinado círculo, todos os demais pixels daquele círculo já estão totalmente determinados. Tal fato também vale para texturas mais complexas. Isto leva a crer que a unidade de síntese deva ser algo maior que um único pixel, ou seja, provavelmente algo como um bloco ou remendo. Desta forma, o processo de síntese de textura seria análogo ao processo de juntar peças de um quebra-cabeças que, em seguida, seriam costuradas para assegurar que elas se ajustam adequadamente. Determinar precisamente quais blocos ou remendos devem ser colocados juntos é um problema que ainda permanece em aberto.

• Identifique na imagem de saída a posição em que o bloco deve ser inserido.
• Busque na imagem amostra(através de uma varredura pixel a pixel) o bloco que melhor se ajusta a tal posição (retorna menor erro entre as regiões de sobreposição).
• Insira o bloco escolhido e faça as “costuras” entre o bloco atual e seus vizinhos.
• Repita enquanto a imagem de saída não estiver totalmente preenchida com blocos da amostra.

O tamanho do bloco e da região de sobreposição são parâmetros controlados pelo usuário, pois dependem das propriedades da textura dada. O bloco deve ser suficientemente grande para capturar as estruturas relevantes na textura, mas ao mesmo tempo deve ser suficientemente pequeno para que a interação entre estas estruturas seja deixada para o algoritmo.

O erro entre duas regiões que se sobrepõem é calculado através da soma das diferenças absolutas entre os pixels nas posições correspondentes.

A costura é subdividida em costura horizontal e vertical. Na costura vertical, cada linha da região de sobreposição é percorrida ao mesmo tempo em que se vai verificando o erro absoluto entre os pixels correspondentes. Uma vez encontrado a posição da linha com menor erro entre pixels, procede-se da seguinte forma: os pixels da região mais antiga são mantidos até tal posição e a partir daí insere-se os pixels do bloco atual. A costura horizontal é análoga, só que a região sobreposição é percorrida coluna por coluna e não linha por linha.

Os desenhos abaixo ilustram o funcionamento do algoritmo descrito.
 
 

Imagem Amostra	Imagem Saída após inserção de um bloco
Imagem Saída preparada para receber bloco 2.	Imagem Preparada para receber bloco intermediário.
Imagem Saída Final.	Costuras.

Alguns Resultados Obtidos
 

• Imagem Toroidal

Amostra	Saída

• Imagem Não Toroidal

Melhorias

Resultados ainda melhores podem ser obtidos se um algoritmo de menor caminho for utilizado para auxiliar na  implementação das "costuras" entre blocos vizinhos, tal como proposto no artigo.