Implementação do problema Image Matching

Este repositório foi criado com o intuito de realizar uma nova implementação para resolver o problema do Image Matching, um problema NP-Completo. Abaixo é apresentado um breve resumo do que é o problema em si, para informações mais aprofundadas, verificar o docs/RelatorioParcial.pdf e docs/RelatorioFinal.pdf.

Sumário

• Image Matching (IM)
• Getting Started
  • Versões
  • Organização
  • Dependências
    • SIFT
  • Executando os algoritmos
  • Incluindo suas próprias imagens
• Autores
• Conhecimentos
  • Livros
  • Artigos

Image Matching (IM)

O problema do IM ou Correspondência de Imagem tem sido abordado por diversos autores, a fim de buscar melhores técnicas para uma solução mais rápida e precisa. O problema consiste em analisar duas imagens A e B, onde B é uma transformação geométrica de A. O resultado desta análise deve ser o encontro de características semelhantes entre elas, de forma que, no final, estas correspondências sejam realçadas e apresentadas para facilitar uma determinada investigação. O IM é um componente chave para diversos processos de análise de imagens e é muito importante para inúmeras aplicações, como navegação, orientação, vigilância automática, fotogrametria e visão robótica. Na medicina, por exemplo, é de grande importância para encontrar relações entre diferenças no posicionamento do paciente, modalidades e aquisição de imagens variadas.

Getting Started

Versões

• Python 3.6.12 (esta foi a versão utilizada, mas funciona para outras versões também)

Organização

Os principais arquivos encontram-se na pasta root. O main.py abre as imagens para dar como entrada ao algoritmo lr2Matching.py, que irá tentar encontrar correspondências entre as imagens. helpers.py contém diversas funções implementadas para serem utilizadas pelo algoritmo, o algoritmo SIFT está implementado no arquivo SIFT.py e o plotGraph.py é uma biblioteca usada para plotar o gráfico de comparação dos tempos em que cada algoritmo tomaram para resolver o problema. Na pasta assets, são organizadas todas as imagens que podem ser utilizadas como entrada do algoritmo. A pasta docs contém os relatórios com uma explicação melhor do problema em si e da proposta deste trabalho. A pasta graph contém o gráfico comparativo gerado pelo algoritmo depois de rodar a main.py. A pasta tests irá conter todos os resultados das correlações em imagens gerados pelos algoritmos para cada caso de teste.

assets/
    apple.jpg
    apple2.jpg
    ...
docs/
    RelatorioParcial.pdf
    RelatorioFinal.pdf
graph/
    comparison.png
tests/
    .gitkeep
    ...
main.py
lrMatching.py
SIFT.py
plotGraph.py
helpers.py

Dependências

Se você não tiver a biblioteca Pillow instalada, para instalar você pode utilizar os seguintes comandos:

$ pip install Pillow --user

Caso seu python3 não seja o padrão, pode ser que você precise usar pip3 ou pip3.6

$ pip3 install Pillow --user

Mais informações aqui na documentação da biblioteca.

SIFT

Para rodar o SIFT foi necessário utilizar algumas exatas versões de alguns pacotes.

$ pip3.6 install opencv-python==3.4.2.16

$ pip3.6 install opencv-contrib-python==3.4.2.16

$ sudo apt-get install python3.6-tk

$ pip3.6 install matplotlib

O código do algoritmo SIFT foi obtido através do site: https://www.analyticsvidhya.com/blog/2019/10/detailed-guide-powerful-sift-technique-image-matching-python/, aqui o funcionamento do algoritmo é explicado brevemente.

Executando os algoritmos

O arquivo principal é o main.py que, por sua vez, irá chamar o algoritmo lr2Matching.py. Para iniciar o primeiro teste, basta rodar o comando:

$ python main.py

ou

$ python3.6 main.py

Ao rodar o algoritmo, ele irá rodar as três implementações e gerar os resultados das correlações em imagens na pasta tests, também irá gerar um gráfico comparativo na pasta graph/ em relação ao tempo de execução que cada algoritmo levou para resolver o problema.

Incluindo suas próprias imagens

Para utilizar os algoritmos com outras imagens de teste, primeiramente você deve incluir as imagens na pasta assets. Depois é só abrir o arquivo main.py e incluir os nomes das imagens nas seguintes linhas:

[...]
srcImages = [
    ('mundi.jpg', 'mundi2.jpg'),
    ('cube.jpg', 'cube2.jpg'),
    ('many.jpg', 'many2.jpg'),
    ('apple.jpg', 'apple2.jpg'),
    ('appleCima.jpg', 'appleCima2.jpg'),
    ('novaImagem.jpg', 'novaImagem2.jpg'), #Novas imagens incluídas
    ]
[...]

Lembrando que as imagens precisam ser de mesmo tamanho e que devem ser quadradas para que todos os algoritmos rodem bem. Também a segunda imagem deve ser uma transformação geométrica da primeira, isto é, o mesmo objeto em um ângulo diferente ou deslocado na imagem. Depois só rodar o algoritmo com python3.6 main.py.

Autores

• Levy Santiago
• Marcos Pinheiro
• Rita Barreto

Conhecimentos

Livros

• Introduction to algorithms
• Programming Computer Vision with Python: Tools and algorithms for analyzing images
• Computer Vision with Python 3
• Hands-On Image Processing with Python: Expert techniques for advanced image analysis and effective interpretation of image data

Artigos

• Elastic image matching is NP-complete
• A monotonic and continuous two-dimensional warping based on dynamic programming
• Desenvolvimento de Algoritmos de Exploração e Mapeamento Visual para Robôs Móveis de Baixo Custo
• Distinctive image features from scale-invariant keypoints
• Structural indexing of infra-red images using statistical histogram comparison
• Digital image processing
• A novel approach to detecting duplicate images using multiple hash tables
• Variational methods for multimodal image matching
• Adaptive least squares correlation: a powerful image matching technique
• Medical image matching-a review with classification
• A nonlinear variational problem for image matching
• Variational problems on flows of diffeomorphisms for image matching
• Image matching from handcrafted to deep features: A survey
• Modification of blurred image matching method