Método Eficiente

Agarwala (2007) publicou um método que diminui a escala do problema a ser resolvido. O método surgiu da observação da diferença entre a imagem final e a aproximação inicial, onde pôde-se notar que esta diferença é suave nos pontos que não estão sobre as juntas, como pode ser observado nas imagens abaixo:

Imagem original.

Resultado final.

Diferença entre a imagem final e a original.
Conhecendo esta característica, Agarwala decidiu dividir o domínio de uma forma adaptativa, de forma que haja mais variáveis nas juntas, e diminue-se a quantidade de variáveis à medida em que estas se afastam das juntas. Isto foi feito utilizando-se uma estrutura de Quadtree. A imagem abaixo ilustra a Quadtree utilizada por Agarwala para as imagens anteriores.

Quadtree utilizada para diminuir a escala do problema.
Uma vez tendo a Quadtree, é preciso selecionar os pixels que serão utilizados para a resolução do sistema. A Quadtree é calculada de forma que as quinas das células estão centralizadas em pixels da imagem original. Variáveis são colocadas em vértices da Quadtree que possuam quatro células vizinhas distintas, com exceção dos pixels que estejam na borda da imagem. A figura abaixo ilustra esse processo de seleção em uma parte da imagem. Os pontos azuis são referentes aos pixels que serão utilizados como variáveis num sistema. Após resolver o sistema, calculam-se os valores dos outros pixels (como o ponto laranja na figura) como combinação linear dos pixels usados como variáveis.

Seleção de pixels que serão utilizados na resolução do sistema.
Para resolver o sistema, geralmente é utilizado um processo iterativo, como Gauss-Seidel ou Gradiente Conjugado, sendo este último mais adequado neste caso, pois a matriz do sistema é esparsa e simétrica, além de que o Gauss-Seidel converge muito lentamente nas regiões suaves da imagem (que são grande parte da imagem nesta aplicação).

Ao se utilizar uma Quadtree, o tamanho do sistema é reduzido de acordo com o número de células da Quadtree obtida. Em nenhum momento é necessário carregar toda a imagem na memória. Inicialmente pode-se percorrer o arquivo da imagem copiando-se apenas os valores da imagem nas juntas. Uma vez que se tenham estes valores o sistema pode ser montado. Após encontrar os valores dos pixels selecionados, a solução final pode ser encontrada por partes, cada parte tendo um tamanho limitado, não sendo necessário portanto ter toda a imagem na memória.


anterior próximo