Qual algoritmo o Google usa para o site "Search By Image"?

45

Qual é o seu melhor palpite sobre como a Pesquisa de imagens do Google funciona? Posso fazer upload de uma foto e procurar imagens semelhantes. Qual algoritmo ele usa para identificar imagens semelhantes?

Cory
fonte
Eles podem armazenar o histograma da imagem. Isso funciona para diferentes escalas da mesma imagem e pequenas diferenças devido a artefatos de compactação ou qualquer outra coisa.
Hélice
1
Os histogramas não capturam informações espaciais; você obteria correspondências falsas.
Emre
Redes neurais: research.googleblog.com/2015/06/…
endolith 04/04

Respostas:

29

Não sei qual algoritmo o Google usa. Mas, como você queria uma melhor estimativa, deixe-me dar algumas idéias sobre como um sistema semelhante pode ser construído .

Todo o campo que trata da pesquisa-imagem-base-por-imagem é chamado de Recuperação de Imagem Baseada em Conteúdo (CBIR) . A idéia é, de alguma forma, construir uma representação de imagem (não necessariamente compreensível por humanos) que contenha as informações sobre o conteúdo da imagem .

Existem duas abordagens básicas:

  • recuperação usando recursos de baixo nível (local): cor, textura, forma em partes específicas das imagens (uma imagem é uma coleção de descritores de recursos locais )
  • abordagens semânticas em que uma imagem é, de alguma forma, representada como uma coleção de objetos e suas relações

A abordagem local de baixo nível é muito bem pesquisada. A melhor abordagem atual extrai recursos locais (há uma opção de algoritmo de extração de recursos envolvida aqui) e usa seus descritores locais (novamente, escolha de descritores) para comparar as imagens.

Em trabalhos mais recentes, os descritores locais são agrupados primeiro e depois os clusters são tratados como palavras visuais - a técnica é muito semelhante à pesquisa de documentos do Google, mas usando palavras visuais em vez de palavras-letra.

Você pode pensar nas palavras visuais como equivalentes às raízes das palavras na linguagem: por exemplo, as palavras: trabalho, trabalho, trabalho pertencem à mesma raiz da palavra.

Uma das desvantagens desses tipos de métodos é que eles geralmente apresentam baixo desempenho em imagens de baixa textura.

Eu já dei e vi muitas respostas detalhando essas abordagens; portanto, fornecerei links para essas respostas:

  • CBIR: 1 , 2
  • extração / descrição de recursos: 1 , 2 , 3 , 4

As abordagens semânticas são tipicamente baseadas em representações hierárquicas de toda a imagem. Essas abordagens ainda não foram aperfeiçoadas, especialmente para os tipos de imagem gerais. Existe algum sucesso na aplicação desse tipo de técnica a domínios de imagem específicos.

Como atualmente estou no meio da pesquisa dessas abordagens, não posso tirar conclusões. Agora, dito isso, expliquei uma idéia geral por trás dessas técnicas nesta resposta .

Mais uma vez, em breve: a idéia geral é representar uma imagem com uma estrutura em forma de árvore, onde as folhas contêm os detalhes da imagem e os objetos podem ser encontrados nos nós mais próximos da raiz dessas árvores. Então, de alguma forma, você compara as subárvores para identificar os objetos contidos nas diferentes imagens.

Aqui estão algumas referências para diferentes representações em árvore. Eu não li todos eles, e alguns deles usam esse tipo de representação para segmentação em vez do CBIR, mas ainda assim, aqui estão eles:

Penélope
fonte
22

Além da resposta de Penélope, existem duas abordagens, o hash perceptivo e o modelo de saco de palavras cuja funcionalidade básica é facilmente implementada e é agradável brincar com ou aprender com ela antes de se aventurar em um território mais avançado.

Hash perceptivo

Os algoritmos de hash perceptivo têm como objetivo construir um hash, que diferentemente de um hash criptográfico, fornecerá valores de hash semelhantes ou quase similares para imagens idênticas que foram ligeiramente distorcidas, por exemplo, por escala ou compactação JPEG. Eles servem a um propósito útil na detecção perto de duplicatas em uma coleção de imagens.

Em sua forma mais básica, você pode implementar isso da seguinte maneira:

  1. Converter imagem em escala de cinza

  2. Faça com que sua imagem seja zero

  3. Esmague sua imagem no tamanho de miniatura, digamos [32x32]
  4. Execute a transformação discreta de cosseno bidimensional
  5. Mantenha a parte superior esquerda [8 x 8], os componentes de baixa frequência mais significativos
  6. Binarize o bloco, com base no sinal dos componentes

O resultado é um hash resiliente de 64 bits, porque é baseado nos componentes de baixa frequência da imagem. Uma variante desse tema seria dividir cada imagem em 64 sub-blocos e comparar a média da imagem global com a média do sub-bloco local e escrever 1 ou 0 de acordo.

O hash perceptivo é implementado, por exemplo, por phash

Modelo de saco de palavras

O modelo de saco de palavras visa identificar semanticamente uma imagem, por exemplo, todas as imagens com cães. Isso é feito usando certos patches de imagem no mesmo espírito que se classificaria um documento de texto com base na ocorrência de certas palavras. Pode-se categorizar as palavras, dizer "cachorro" e "cães" e armazená-las como identificador em um arquivo invertido, onde a categoria "cachorro" agora aponta para todos os documentos que contêm "cachorro" ou "cães".

Em sua forma mais simples, é possível fazer isso com imagens da seguinte maneira:

  1. Implante os chamados recursos SIFT, por exemplo, usando a excelente biblioteca vlfeat , que detectará os pontos de recurso SIFT e um descritor SIFT por ponto. Esse descritor é basicamente um modelo inteligente do patch de imagem em torno desse ponto de recurso. Esses descritores são suas palavras cruas.
  2. Reúna descritores SIFT para todas as imagens relevantes

Agora você tem uma enorme coleção de descritores SIFT. O problema é que, mesmo a partir de imagens quase idênticas, haverá alguma incompatibilidade entre os descritores. Você deseja agrupar os idênticos mais ou menos como tratar algumas palavras, como "cachorro" e "cães" como idênticos e precisa compensar os erros. É aqui que entra o cluster para jogar.

  1. Pegue todos os descritores SIFT e agrupe-os, por exemplo, com um algoritmo como k-means. Isso encontrará um número pré-determinado de clusters com centróides nos dados do seu descritor. Esses centróides são suas novas palavras visuais.
  2. Agora, por imagem e seus descritores encontrados originais, é possível ver os clusters aos quais esses descritores foram atribuídos. A partir disso, você sabe quais centróides ou palavras visuais 'pertencem' à sua imagem. Esses centróides ou palavras visuais se tornam o novo descritor semântico da sua imagem, que pode ser armazenado em um arquivo invertido.

Uma consulta de imagem, por exemplo, encontre-me imagens semelhantes à imagem de consulta, será resolvida da seguinte maneira:

  1. Encontre os pontos SIFT e seus descritores na imagem da consulta
  2. Atribua os descritores da consulta aos centróides encontrados anteriormente na fase de inscrição. Agora você tem um conjunto de centróides ou palavras visuais que pertencem à sua imagem de consulta
  3. Associe as palavras visuais da consulta às palavras visuais no seu arquivo invertido e retorne as imagens correspondentes
Maurits
fonte
1
Sua abordagem por palavras-chave é basicamente o que meus links para a "abordagem local" levam a :) Embora não seja realmente de natureza semântica: você nunca representaria um único cão com um recurso, nem seria tão fácil de identificar especiarias diferentes para cães como cães. Mas o hash perceptivo é bom, não sabia disso. Explicações são legais. O que me fez pensar ... você teria alguma sugestão de como aplicar essa técnica em uma área não retangular? Ou talvez forneça algumas referências a artigos, eu poderia ler um pouco e, se a pergunta fizer sentido, abri-la como uma pergunta separada.
Penelope
1
@penelope Na verdade, li um artigo, anos atrás, em que os autores dividem uma imagem em triângulos arbitrários. E há a transformação de traço que também foi usada como base para um hash perceptivo. Eu voltarei para você.
Maurits
Tudo o que quero lhe perguntar sobre isso está muito além do escopo desta pergunta, então abri uma nova. Mais informações / referências sobre a técnica básica ainda seriam ótimas também, nesta resposta ou nessa. Olhando para a frente :)
penelope
2

A outra abordagem interessante que parece ser negligenciada nas respostas acima são as Redes Neurais Convolucionais Profundas. Parece que o Google está usando agora para seu mecanismo de busca de imagens e seu serviço de tradução . As CNNs são extremamente poderosas em tarefas cognitivas, como a descoberta de similaridades. Parece que a CNN realiza um procedimento semelhante ao do Saco dos Mundos, que é incorporado às suas camadas de rede. A desvantagem dessas técnicas é a incapacidade de desaprender e a necessidade de grandes conjuntos de dados para treinamento e, claro, os custos computacionais pesados ​​no estágio de treinamento.

Artigo sugerido sobre esse assunto:

e implementação de recuperação de imagem de aprendizado profundo de código aberto (o artigo posterior): https://github.com/paucarre/tiefvision

MimSaad
fonte