Inpainting é o processo de reconstrução digital de partes perdidas ou deterioradas de imagens e vídeos, também conhecida como interpolação de imagens e vídeos. Refere-se à aplicação de algoritmos sofisticados para substituir partes perdidas ou corrompidas da imagem (principalmente pequenas regiões ou para remover pequenos defeitos).

Nesse projeto estudamos e implementamos técnicas de inpainting para a remoção automática de rabiscos inseridos artificialmente em imagens. Para realizarmos a detecção automática da região que devemos fazer inpainting usamos do fato de que os rabiscos são feitos com cores contrastantes que ocorrem com alta frequência nas imagens.

Aplicamos os métodos utilizados para a remoção de objetos em imagens também. Para isso é necessário desenhar em cima do objeto a ser removido com um pincel duro com uma cor contrastante como, por exemplo, o vermelho (255, 0, 0).

Parte do conjunto de imagens utilizado é apresentado abaixo. Todas as imagens utilizadas estão no formato Bitmap (.bmp) e estão organizadas na pasta images/.

As imagens abaixo estão em sua forma original.

Cachorro (retirada da internet)	Texto em foto (retirada de um artigo)	Forbes	Professor Moacir

As imagens abaixo foram rabiscadas artificialmente. A única imagem que não inserimos rabiscos foi a segunda imagem, que foi retirada de um artigo.

Cachorro (retirada da internet)	Texto em foto (retirada de um artigo)	Forbes	Professor Moacir

O primeiro passo para realizar inpainting é definir a região deteriorada. Para isso implementamos dois métodos simples para extrair a máscara automaticamente. Para essa etapa do trabalho queremos realizar inpainting em cores específicas, ou seja, assumimos como sendo parte da região deteriorada todos os pixels que possuem certas cortes determinadas pelos métodos descritos a seguir.

O primeiro passo de ambos os métodos é calcular o número de ocorrências de cada tripla de cor RGB. Optamos por ignorar cores muito próximas do branco absoluto (255, 255, 255) pois alguns dos experimentos foram feitos com imagens com excesso de luz. Ignoramos então as cores que possuem valor maior ou igual a 250 nos três canais.

Vale notar que os métodos podem ser melhorados para que a máscara obtida represente não só algumas cores pré-determinadas pelos métodos, mas que represente também a "penumbra" que muitas ferramentas de edição inserem nas bordas dos traços. Para isso podemos extrair a máscara usando os métodos abaixo e depois preencher todos os pixels não preenchidos adjacentes a um ou mais pixels preenchidos que possuem um tom parecido, utilizando uma certa medida de distância. Para esse projeto tentamos usar uma medida de distância usando os canais H e S do espaço de cores HSV, mas, como não obtivemos muita precisão, optamos por usar apenas riscos "duros" no projeto para focar na parte principal: o Inpainting.

Foto deteriorada	Máscara extraída

Nesse método assumimos que apenas uma cor deve ser removida: a mais frequente. Esse método funciona muito bem quando existe rabiscos de apenas uma cor.

Nesse método definimos um threshold e assumimos que todas as cores que ocorrem mais vezes do que esse threshold fazem parte da região de inpainting. Para essa etapa definimos o threshold como sendo 1% dos pixels da imagem, ou seja, se alguma cor ocorrer em mais do que 1% da imagem, ela é considerada "rabisco". Esse método não funciona tão bem quando existe rabiscos de apenas uma cor, mas é um método necessário para remover rabiscos de diferentes cores.

Nesse método a máscara será composta por todos os pixels vermelhos (255, 0, 0). Esse método é importante para melhorar a precisão da extração da máscara para a aplicação extra do projeto de remover objetos indesejados. Para isso basta o usuário pintar de vermelho (255, 0, 0) os objetos que deseja remover da imagem.

O algoritmo Gerchberg-Papoulis é um algoritmo de inpaiting por difusão que funciona por meio de cortes nas frequencias obtidas pela Transformada Discreta de Fourier (DFT), zerando parte das frequências das imagens.

Considerando uma Máscara M que possui valor 0 nos locais em que a imagem é conhecida e 255 nas regiões deterioradas, o algoritmo com T iterações é aplicado da seguinte maneira:

1. g_0 = Imagem inicial
2. Obtenção da DFT de M.
3. Para cada iteração k = 1, ..., T
   • G_k = DFT de g_{k-1}
   • Filtra G_k zerando coeficientes das frequências relativos a:
     • G_k >= 0.9 * max(M)
     • G_k <= 0.01 * max(G_k)
   • Convolução de G_k com um filtro de média k x k.
   • g_k = IDFT de G_k
   • Normalização de G_k entre 0 e 255.
   • Inserção dos pixels de gk somente na região referente a máscara.
     • g_k = (1 - M/255) * g_0 + (M/255) * g_k

Ao final do processo é obtida a imagem G_k restaurada.

Abaixo estão alguns dos resultados do algoritmo.

Cachorro (retirada da internet)	Texto em foto (retirada de um artigo)	Forbes	Professor Moacir

Os algoritmos de Inpainting por exemplos utilizados consistem em substituir cada pixel deteriorado Pd por um pixel não deteriorado P cuja janela KxK centrada em P maximiza uma certa medida de similaridade em relação a janela KxK centrada em Pd.

O K é definido automaticamente levando em consideração a "grossura" do rabisco da seguinte forma: Para cada pixel deteriorado Pd calcula-se sua distância de Manhattan para o pixel não-deteriorado mais próximo usando uma Multi-Source Breadth-First Search. Ao recuperar o máximo de todos esses valores, multiplica-lo por 2 e somar 3, obtemos um valor para K grande o suficiente para a região deteriorada nunca conter completamente uma janela KxK.

A medida de distância utilizada foi similar ao RMSE, mas calculado apenas entre pixels não-deteriorados. Vale dizer que para todo o projeto assumimos que os pixels fora da imagem são pretos (0, 0, 0).

Nesse algoritmo a busca pelo pixel P é feita em toda a imagem. Seu tempo de execução é altíssimo e, portanto, apenas conseguimos rodar para as imagens dogo1.bmp (100x100), dogo2.bmp (400x400), momo_fino.bmp (280x280) e momo.bmp (280x280).

Cachorro 100x100 reconstruído	Cachorro 400x400 reconstruído	Moacir com rabiscos finos reconstruído	Moacir com rabiscos grossos reconstruído

Nesse algoritmo fazemos a suposição de que as janelas mais similares não estão muito longe da região deteriorada, portanto a busca pelo pixel P é feita apenas em uma região 101x101 centrada em Pd. Isso permite que façamos inpainting em imagens maiores em tempo hábil, como a imagem abaixo.

Forbes 961x1280 deteriorado	Forbes 961x1280 reconstruído

Aprimorando um pouco a ideia do Brute Force Local, percebemos que atribuir a média entre os pixels cuja janela KxK mais se assemelham a janela do pixel Pd reduz o RMSE e resulta, em geral, em restaurações mais suaves. Usamos os 5 mais semelhantes para imagens menores e os 10 mais semelhantes para imagens maiores.

Além disso, ao começarmos a tentar remover rabiscos mais grossos ou objetos maiores observamos que poderíamos usar um valor de K dinâmico, ou seja, um valor de K para cada pixel deteriorado Pd com o objetivo de obter janelas mais representativas e reduzir o tempo de execução. Esse método se mostrou especialmente útil em máscaras mais grossas, ou seja, máscaras que produzem um valor de K elevado nos outros métodos.

A imagem abaixo é um bom exemplo da utilidade do K dinâmico, pois podemos ver que as regiões "deterioradas" são "grossas". Para as bordas dessas regiões o K usado é menor, o que reduz o tempo de execução.

Forbes-Perfil 934x1280 original	Forbes-Perfil 934x1280 "deteriorado"	Forbes-Perfil 934x1280 máscara	Forbes-Perfil 934x1280 restaurado

Nesse algoritmo rodamos uma Depth-First Search (DFS) a partir de cada componente conexa de pixels deteriorados. Para o primeiro pixel deteriorado Pd de uma componente fazemos a busca pelas 50 janelas KxK mais similares em uma região 101x101 centrada em Pd e guardamos em uma lista de candidatos. Passamos essa lista para os vizinhos de Pd de tal forma que os vizinhos precisem apenas calcular a distância para 50 janelas na maior parte das vezes. Quando a janela mais similar ao pixel atual não for tão similar (sua distância é maior que um threshold que definimos como sendo 5.0 para a maioria das imagens), buscamos uma lista com os 50 melhores candidatos novamente. Por fim atribuímos a cada pixel deteriorado a média dos 5 pixels cujas janelas são as mais similares dentre os candidatos.

A suposição feita para o desenvolvimento desse algoritmo se deve ao fato de que pixels deteriorados vizinhos devem ser similares entre si e, portanto, similares a uma mesma lista de candidatos.

Podemos ver pela imagem horse_car.bmp que usar o pixel cuja janela KxK possui distância mínima não é sempre a melhor escolha. A média entre os 5 melhores candidatos resulta em um inpainting mais suave, removendo parte do ruído produzido pelos outros métodos de força bruta descritos.

|| | | | |------------|------------|------------|------------| | Imagem deteriorada | Máscara | Local Brute Force | Smart Brute Force |

Para o problema de remoção de rabiscos a avaliação dos resultados foi feita, além de visualmente, pela raiz do erro quadrático médio (RMSE) calculado apenas nos pixels da região deteriorada e a partir de imagens geradas representando a diferença entre as imagens originais e as imagens restauradas. Quanto ao problema de remoção de objetos indesejados a avaliação se deu apenas visualmente.

Em geral observamos que os melhores resultados vieram do algoritmo Smart Brute Force enquanto os piores resultados vieram do Gerchberg Papoulis, visto que esse gera regiões visivelmente mais borradas (apesar de possuir o tempo de execução mais baixo) principalmente para imagens com vários detalhes como rostos. Podemos ver a diferença dos resultados entre esses dois algoritmos na imagem do Professor Moacir (momo.bmp) de dimensões 280x280:

|| | | | |------------|------------|------------|------------| | Smart Brute Force | Imagem da diferença Smart Brute Force | Gerchberg Papoulis | Imagem da diferença Gerchberg Papoulis |

Comparação do RMSE e do tempo de execução para esses algoritmos:

As tabelas abaixo sumarizam os resultados obtidos na remoção dos rabiscos para cada algoritmo.

Em seguida apresentamos alguns dos melhores resultados com comparativos visuais.

O algoritmo Local Dynamic Brute Force obteve o melhor resultado com 6.646 de RMSE e um tempo de execução de 3 segundos.

Original	Deteriorada	Restaurada	Diferença

O algoritmo Smart Brute Force obteve o melhor resultado com 11.384 de RMSE e um tempo de execução de 36 segundos.

Original	Deteriorada	Restaurada	Diferença

O algoritmo Smart Brute Force obteve o melhor resultado com 21.102 de RMSE e um tempo de execução de 2 minutos e 55 segundos.

Original	Deteriorada	Restaurada	Diferença

O algoritmo Smart Brute Force obteve o melhor resultado com 12.567 de RMSE e um tempo de execução 24 segundos.

Original	Deteriorada	Restaurada	Diferença

O algoritmo Smart Brute Force obteve o melhor resultado com 20.614 de RMSE e um tempo de execução 7 minutos e 48 segundos.

Original	Deteriorada	Restaurada	Diferença

O algoritmo Local Dynamic Brute Force obteve o melhor resultado com 6.964 de RMSE e um tempo de execução 7 minutos e 21 segundos.

Original	Deteriorada	Restaurada	Diferença

Abaixo estão os resultados do uso de Inpainting para a remoção de objetos de imagens. Os tempos de execução para cada algoritmo estão apresentados abaixo:

Para cada imagem é apresentada a imagem original a imagem com adição de vermelho (255, 0, 0) por cima da região indesejada e o resultado mais satisfatório obtido por algum dos algoritmos.

|| | | |------------|------------|------------| | Original | "Deteriorada" | Local Dynamic Brute Force |

|| | | |------------|------------|------------| | Original | "Deteriorada" | Smart Brute Force |

|| | | |------------|------------|------------| | Original | "Deteriorada" | Smart Brute Force |

|| | | |------------|------------|------------| | Original | "Deteriorada" | Smart Brute Force |

|| | | |------------|------------|------------| | Original | "Deteriorada" | Smart Brute Force |

|| | | |------------|------------|------------| | Original | "Deteriorada" | Smart Brute Force |

Obtivemos ótimos resultados com os algoritmos de Inpainting por exemplos para a remoção de rabiscos e de objetos maiores. Apesar disso percebemos que esses algoritmos não lidam muito bem com contornos e texturas (como podemos reparar pela imagem da praia) como os métodos descritos nesse artigo do Bertalmio.

É notável a importância de algoritmos e códigos eficientes para reduzir o tempo de execução dos métodos de Inpainting por exemplos. Podemos concluir que os resultados foram satisfatórios e que a maioria dos objetivos foram cumpridos, com exceção da extração de máscaras de imagens com rabiscos com cores não "duras".

O algoritmo de Gerchberg Papoulis foi implementado em Python 3 com Numpy e ImageIO, enquanto os algoritmos de Inpainting por exemplos foram implementados em C++ com OpenCV para obter tempos de execução menores.

A imagem de entrada deve estar na pasta project/images/deteriorated/, a máscara será salva em project/images/masks/ e a imagem de saída na pasta project/images/deteriorated/<inpainting_algorithm>/.

A compilação do código em C++ foi feita utilizando o cmake com o arquivo CMakeLists.txt, então para gerar o Makefile e compilar o executável é preciso executar os comandos dentro da pasta Project:

cmake .
make

A execução do código em C++ é feita pelo comando:

./main <image_in.bmp> <image_out.bmp> <mask_extraction_algorithm> <inpainting_algorithm> (compare)?

É possivel também executar somente a comparação, utilizando o comando:

./main compare <path/original.bmp> <path/inpainted.bmp> <path/mask.bmp>

A execução do código em Python é feita pelo comando:

python3 main.py <image_in.bmp> <image_out.bmp> <mask_extraction_algorithm> (compare)?

O código em Python contém apenas a implementação do algoritmo Gerchberg Papoulis, por isso não é necessário escolher o algoritmo de inpainting.

Os argumentos são:

• <image_in.bmp> - Nome da imagem de entrada.
• <image_out.bmp> - Nome da imagem de saída.
• <mask_extraction_algorithm> - Algoritmo de extração da máscara (most_frequent, minimum_frequency ou red).
• <inpainting_algorithm> - Algoritmo de inpainting (brute, local, dynamic ou smart).
• (compare) - Opcional. Realiza a comparação entre a imagem original, se houver, e a imagem restaurada produzindo o RMSE e a imagem da diferença.

Por exemplo, se quisermos executar o Local Brute Force para remover rabiscos de múltiplas cores da imagem dogo2.bmp e obter uma avaliação dos resultados (RMSE e imagem da diferença) basta colocar a imagem na pasta images/deteriorated/ e executar o comando:

./main dogo2.bmp dogo2.bmp minimum_frequency local compare

Após a execução a máscara é salva em images/masks/dogo2.bmp, a imagem restaurada é salva em images/inpainted/Local Brute Force/dogo2.bmp e a imagem da diferença é salva em images/difference/Local Brute Force/dogo2.bmp.

Outro exemplo seria executar o Local Dynamic Brute Force para remover marcas na pele na imagem forbes_profile.bmp. Para isso podemos pintar as marcas de pele com a cor vermelho (255, 0, 0), colocar essa imagem na pasta images/deteriorated/ e executar o comando:

./main forbes_profile.bmp forbes_profile.bmp red dynamic

Após a execução a máscara é salva em images/masks/forbes_profile.bmp e a imagem sem as marcas de pele é salva em images/inpainted/Local Dynamic Brute Force/forbes_profile.bmp.

OBS.: Apesar do cálculo do RMSE e da imagem da diferença não terem significado para a avaliação dos resultados para a aplicação de remoção de objetos ainda é possível fazê-los usando a diretiva compare.