Encontrando similaridades entre imagens com SIFT

Um dos desafios de se vender pela internet está em lidar com dados não estruturados ou gerados de forma “natural”. Este é o caso das imagens de produtos, onde não há uma estrutura definida. Para um ser humano, encontrar estruturas similares entre duas imagens é uma tarefa simples. Porém para um computador esta tarefa era bastante complexa. Nos últimos dez anos, uma área de pesquisa conhecida como visão computacional, que vivia trancada nas bibliotecas e laboratórios de universidades, ganhou aplicações reais e largamente utilizadas, inclusive para ajudar a vender produtos pela internet.

Uma de suas aplicações é a comparação de uma imagem de produto com uma ou mais imagens, para encontrar similaridades entre elas. A busca por equivalência de produtos é um campo de pesquisa com ótimos resultados e aplicações. É o que falaremos neste artigo, que faz parte de uma série sobre o mesmo assunto. Para mais sobre a tarefa de descobrir equivalência entre produtos, veja o artigo Equivalência de produtos no ecommerce. Já para como descobrir similaridades entre títulos de produtos usando word2vec e similaridade de cossenos, veja o artigo Similaridade entre títulos de produtos com Word2Vec.

Sendo assim, imagine que alguém pense:

Como consigo encontrar um produto específico dentro de uma imagem?

Ou ainda:

Como faço para comparar imagens dos meus produtos com os enviados pelos parceiros e encontrar quais produtos eu e meus parceiros vendemos mutuamente?

Uma maneira de responder à estas questões veio através de um algoritmo conhecido como SIFT, ou Scale Invariant Feature Transform, criado por David G. Lowe e publicado num artigo seminal em 2004. Grosso modo, o SIFT descobre padrões (ou estruturas) no meio dos dados (pixels) não estruturados das imagens. Para entender melhor como o SIFT funciona, temos que falar de matemática (de maneira gentil), mesmo que introdutoriamente.

Como o SIFT funciona?

Uma simplificação que iremos adotar é que uma imagem digital nada mais é que uma matriz (ou um tensor de segunda ordem, para os íntimos). Todo o trabalho do SIFT está em descobrir os padrões nesse tensor.

A Lu, à esquerda, e um zoom no seu olho direito, com os valores numéricos referentes a cada canal RGB de cada pixel. No caso de uma imagem colorida, cada elemento do tensor bidimensional tem um tensor unidimensional com três valores (na imagem acima, valores representados por um inteiro de 8 bits)

O SIFT começa descobrindo os padrões, que a partir de agora chamaremos de descritores e pontos característicos, buscando as bordas de cada objeto. Bordas numa imagem são descobertas calculando-se a magnitude da derivada das frequências em x (na horizontal) e y (na vertical) de um tensor G. SIFT usa uma espécie de filtro passa-alta para ressaltar as bordas e “separar” os objetos na imagem.

Uma analogia seria um pequeno sensor que só consegue olhar para uma parte pequena da imagem por vez, algo como espaços de 5x5 pixels. Enquanto esse sensor (tecnicamente conhecido como kernel) “anda” pela imagem, ele “analisa” a diferença de valores do trecho da imagem sob ele (operação conhecida formalmente como convolução), e caso a diferença seja grande, ele “marca” como uma possível borda. Esse tipo de operação é dada por

Onde G é a magnitude da derivada em x e y dos tensores Gx e Gy.

Uma outra forma de entender reside na análise da imagem abaixo.

Um kernel 5x5 (destacado, em branco) demonstrando a descoberta de bordas. Neste exemplo, existe uma grande diferença de valores no pixels da borda do kernel, tornando essa área uma possível borda.

Afinal, qual o resultado de tudo isso? Um tensor (que pode ser visto como uma imagem) apenas com as frequências mais altas, ou com as bordas ressaltadas. Como visto na imagem abaixo.

Esta é a Lu com as bordas ressaltadas. Quanto mais clara a borda, mais “forte” ela é. Em outras palavras, a diferença nos gradientes foi maior.

E assim, temos bordas detectadas. Mas essa é apenas a primeira parte do algoritmo. A segunda parte explica o scale invariant (invariância na escala) das duas primeiras letras do SIFT: a detecção das bordas “fortes” pode variar de acordo com a escala. O SIFT testa e avalia essa possibilidade por meio de seus octaves (que são camadas variando o desvio-padrão de uma gaussiana).

Para entender melhor como a segunda parte funciona, vamos voltar à analogia do sensor, e imagine que ele ganhou uma nova capacidade: além de andar na imagem, agora ele consegue parar num determinado ponto que tenha uma borda “forte” e se afastar. Ou seja, ele consegue alterar sua altura, testando em três dimensões cada borda. Ele faz isso usando um outro tipo de filtro, conhecido como passa-baixa. Ele faz o inverso do filtro passa-alta, permitindo a “passagem” apenas de frequências mínimas. O resultado prático desse filtro, na imagem, é bem simples: ele “embaça” a imagem.

Exemplo do SIFT testando quais regiões de borda continuam relevantes após a mudança de escala simulada pela aplicação de um filtro gaussiano, que dependendo da variação do σ (ou desvio-padrão) aplicado, “embaça” de maneira mais intensa. Nesta imagem (da esquerda para direita, de cima para baixo), vemos os efeitos da variação do σ.

A operação aplicada pelo filtro gaussiano é dada pela equação

Agora, perceba o seguinte fenômeno: quanto mais a imagem “embaça”, algumas bordas ficam menos visíveis durante o aumento da suavização. Isso quer dizer que, na diferença de escala (ou de zoom), as bordas que sumiram são “fracas”, ou deixam de ser bordas. E assim, invariante na escala a extração (transformação) de características acontece! Lowe define a relação entre a detecção de bordas, a suavização da imagem e o teste de extremos (“bordas fortes” ou “bordas fracas”) pela equação

A diferença das gaussianas do gradiente (denotado por ∇, também conhecido como operador nabla ou del) das magnitudes geram descritores e suas orientações. O termo (k-1) é fator aplicado nas variâncias e gradientes, onde k é uma constante definida apriori.

O resultado é um tensor de segunda ordem com as dimensões n x 128, onde n refere-se à quantidade de descritores encontrados e o 128 está relacionado ao tensor de histogramas de orientação. Explicando rapidamente sobre o histograma de orientação, cada descritor tem uma direção associada, que nada mais é que a direção de seu gradiente. Como têmos tensores resultantes 4 x 4 de orientação, cada um contando com 8 orientações, portanto temos 4 x 4 x 8 = 128 bins neste histograma. Na próxima seção, a demonstração dos pontos característicos extraídos deve ajudar a entender melhor estes conceitos.

O SIFT em ação

O resultado que temos do SIFT é um “mapa” de características latentes da imagem. Isto significa que estes pontos tornam a imagem “única”, e objetos ou cenas que duas ou mais imagens compartilham podem ser descobertos e comparados. Na imagem abaixo, tem-se a visualização destes pontos.

Os 128 pontos característicos mais representativos. Isto é, mesmo que a escala mude ou a imagem seja rotacionada, a maior parte desses pontos continuará definida. Circunferências de maior diâmetro representam pontos maiores. A linha representando o raio demonstra a direção do gradiente.

Na comparação de duas imagens, é necessários extrair os pontos característicos e descritores das duas e depois usar uma função de distância (como a euclidiana, por exemplo) para calcular a proximidade dos bins dos histogramas de orientação. Normalmente isto é feito através de algoritmos de vizinhança mais próxima, como o k-NN (como este algoritmo funciona está além do escopo do artigo).

Pontos que têm distância muito alta têm baixa proximidade, logo devem ser descartados durante a busca por similaridade. Porém, pontos com pequenas distância de histograma são eleitos como correspondentes. Quanto maior a quantidade de pontos correspondentes, maior a probabilidade de as imagens compartilharem objetos, paisagens, rostos, etc. Um exemplo da busca por pontos correspondentes é mostrado na figura abaixo.

Duas imagens distintas sendo comparadas. São mostrados os pontos característicos (em verde) e as linhas (laranja) demonstram os pontos com menores distâncias entre si. Neste caso, o fator de distância utilizado foi de 0.8

Resultados

A comparação de imagens em busca de similaridades pode ser usada para diversos fins além dos citados. Um exemplo é buscar por produtos similares visualmente, mas que não sejam os mesmos. Isto é importante para categorização automática ou recomendação de produtos para se comprar junto, entre outros. E tudo isso usando apenas informação visual. Como exemplo, temos abaixo resultados onde, ao invés de buscar pelo máximo de pontos correspondentes, foi retornado imagens com um limite mínimo e máximo aceito de pontos correntes.

Buscando imagens visualmente similares, porém que respeitem um mínimo e um máximo de similaridade. A imagem maior, a esquerda, é a imagem usada na entrada da busca. As imagens menores, da esquerda para direita, tem graus decrescentes de similaridade.

Conclusões

Usar o SIFT na comparação de um par de produtos, para compor um score de semelhança entre eles, se mostrou uma abordagem bastante simples e rápida, pois não envolve treinamento de modelo nem aprendizado de hiperparâmetros. Além disso, ele pode ser extrapolado para outros usos, como o já citado (semelhança de produtos) ou busca por imagens. Isto é, para tarefas em que a classe dos objetos na imagem não é importante, mas sim a equivalência entre elas.