Pesquise imagens semelhantes, analisando um único algoritmo

Recentemente, tive que resolver o problema de otimizar a pesquisa de imagens duplicadas.

A solução existente é executada em uma biblioteca Python bastante conhecida, Image Match , com base em UMA ASSINATURA DE IMAGEM PARA QUALQUER TIPO DE IMAGEM, de autoria de H. Chi Wong, Marshall Berna e David Goldberg.

Por várias razões, foi decidido reescrever tudo no Kotlin, ao mesmo tempo em que abandonava o armazenamento e a pesquisa no ElasticSearch, o que requer significativamente mais recursos, tanto de ferro quanto humanos, para suporte e administração, em favor da pesquisa no cache da memória local.

Para entender como ele funciona, eu tive que mergulhar no código Python de "referência", pois o trabalho original às vezes não é totalmente óbvio e, em alguns lugares, me faz lembrar de "como desenhar uma coruja". Na verdade, quero compartilhar os resultados deste estudo, ao mesmo tempo informando sobre algumas otimizações, tanto em termos de volume de dados quanto de velocidade de pesquisa. Talvez alguém venha a calhar.

Exoneração de responsabilidade: Existe a possibilidade de eu estragar tudo em algum lugar, de fazer errado ou não de uma maneira ideal. Bem, ficarei feliz em receber críticas e comentários. :)

Como isso funciona:

1. A imagem é convertida para o formato preto e branco de 8 bits (um ponto é um byte no valor 0-255)
2. A imagem é cortada de maneira a descartar 5% da diferença acumulada (mais abaixo) de cada um dos quatro lados. Por exemplo, uma moldura preta ao redor da imagem.
3. Uma grade de trabalho é selecionada (9x9 por padrão), cujos nós servirão como pontos de referência da assinatura da imagem.
4. Para cada ponto de referência, com base em uma determinada área ao seu redor, seu brilho é calculado.
5. Para cada ponto de referência, calcula-se quanto é mais brilhante / mais escuro que seus oito vizinhos. São usadas cinco gradações, de -2 (muito mais escura) a 2 (muito mais brilhante).
6. Toda essa "alegria" se desdobra em uma matriz unidimensional (vetor) e é chamada pela assinatura da imagem.

A semelhança das duas imagens é verificada da seguinte forma:



Quanto menor o d, melhor. De fato, d <0,3 é quase uma garantia de identidade.

Agora com mais detalhes.

Primeiro passo

Eu acho que falar sobre converter em escala de cinza faz pouco sentido.

Segundo passo

Digamos que temos uma imagem como esta:


Pode-se ver que há um quadro preto de 3 pixels à direita e à esquerda e 2 pixels na parte superior e inferior, dos quais não precisamos em comparação

A borda de corte é determinada pelo seguinte algoritmo:

1. Para cada coluna, calculamos a soma das diferenças absolutas dos elementos vizinhos.
   
2. Cortamos à esquerda e à direita o número de pixels cuja contribuição para a diferença acumulada total é inferior a 5%.

Fazemos o mesmo para colunas.

Um esclarecimento importante: se as dimensões da imagem resultante forem insuficientes para a etapa 4, não cortamos!

Passo três

Bem, tudo é bem simples aqui, dividimos a imagem em partes iguais e selecionamos os pontos nodais.

Quarto passo

O brilho do ponto de ancoragem é calculado como o brilho médio de todos os pontos na área quadrada ao redor dele. No trabalho original, a seguinte fórmula é usada para calcular os lados deste quadrado:

Quinto passo

Para cada ponto de referência, é calculada a diferença em seu brilho com o brilho de seus oito vizinhos. Para os pontos para os quais não há vizinhos (linhas superior e inferior, colunas esquerda e direita), a diferença é considerada 0.

Além disso, essas diferenças são reduzidas para cinco gradações:


Acontece algo como esta matriz:

Sexto passo

Eu acho que nenhuma explicação é necessária.

E agora sobre otimização

No trabalho original, ressalta-se, com razão, que a partir da assinatura resultante é possível apagar completamente os valores zero ao longo das bordas da matriz, pois serão idênticos para todas as imagens.


No entanto, se você observar com atenção, poderá ver que para dois vizinhos suas gradações mútuas serão iguais em valor absoluto. Portanto, de fato, você pode jogar com segurança quatro valores duplicados para cada ponto de referência, reduzindo o tamanho da assinatura pela metade (excluindo zeros laterais).


Obviamente, ao calcular a soma dos quadrados, para cada x , haverá definitivamente um módulo x ' igual e a fórmula para calcular a norma pode ser escrita da seguinte forma (sem se aprofundar na reindexação):


Isso é verdade tanto para o numerador quanto para os dois termos do denominador.

Além disso, no trabalho original, note-se que três bits são suficientes para armazenar cada gradação. Isto é, por exemplo, no Não assinado longo caberá em 21 gradações. Essa é uma economia bastante grande, mas, por outro lado, aumenta a complexidade ao calcular a soma dos quadrados da diferença entre as duas assinaturas. Devo dizer que essa ideia realmente me engoliu com algo e não me soltou por alguns dias, até que certa noite ocorreu como comer um peixe , um lugar para salvar e simplificar o cálculo. Assista suas mãos.

Usamos esse esquema para armazenamento, 4 bits por gradação:

Sim, apenas 16 gradações caberão em um comprimento não assinado, contra 21, mas a matriz da diferença das duas assinaturas será calculada com um xor e 15 turnos à direita com o cálculo do número de bits definido para cada iteração do turno. I.e.


O sinal não importa para nós, pois todos os valores serão quadrados.

Além disso, se o valor limite da distância for determinado previamente, cujos valores não são mais interessantes para nós, depois de dançar um pouco na fórmula de cálculo, você poderá derivar uma condição de filtragem bastante leve para um número simples de bits definidos.

Mais detalhes sobre a otimização desse algoritmo, com exemplos de código, podem ser encontrados no artigo anterior . Eu recomendo separadamente a leitura de comentários sobre ele - o masyaman residente de Khabrovsk propôs vários métodos bastante interessantes para calcular, incluindo empacotar gradações em três bits, usando mágica de bits.

Na verdade, é tudo. Obrigado pela atenção. :)