14

Estou precisando criar um gerenciador para um banco de imagens bem extenso, onde neste gerenciador além da busca por título e descrição, deverá haver um recurso que busque por imagens visualmente semelhantes.

Para este caso estive pensando em "dividir" uma imagem em blocos e salvar as informações predominância de cor de cada bloco, porém acredito que desta forma só seria possível encontrar imagens de cores semelhantes.

Como funciona o recurso do Google de encontrar imagens semelhantes?

1 Resposta 1

19

Eu não sei te dizer como funciona exatamente o algoritmo específico do Google, mas posso oferecer uma ajuda em como é o princípio básico da busca de imagens por conteúdo.

Essa área é comumente chamada de CBIR (Content-Based Image Retrieval, ou Recuperação de Imagens Baseada em Conteúdo em português), pois envolve a busca de imagens a partir de seu conteúdo. É uma área de grande interesse mas de difícil solução porque as imagens são de difícil interpretação por computadores (é por isso que se usa amplamente CAPTCHAS para impedir acesso automatizado às páginas na Internet).

Há algumas abordagens tradicionais pra resolver esse problema.

1. Busca Baseada em Anotação

A ideia de anotar as imagens com rótulos descritivos do seu conteúdo é a mais simples. Você apenas cria um banco de dados contendo as imagens e os textos (rótulos) que a descrevem. Imagine, por exemplo, a imagem de um filhote de cachorro. O banco de dados pode conter pra elas as palavras "filhote", "cachorro", "labrador" (se for o caso), e por ai vai. A busca então seria realizada com base nas anotações, sendo as imagens devolvidas aquelas cujas anotações mais bem correspondem ao termo de pesquisa. Eu suponho que esse seja o algoritmo principal utilizado pelo Google, quando você pesquisa por imagens usando expressões de texto.

A grande dificuldade desse método é que é trabalhoso e entediante fazer anotações manuais das imagens. Por isso, existem soluções parcialmente automatizadas. O Google, muito provavelmene, utiliza reforço humano a partir das pesquisas efetuadas. Você digita um texto qualquer ("cachorrinho", no exemplo anterior - uma palavra que ainda não consta como anotação) e ele exibe imagens mais e menos "relevantes" com base nos links existentes entre elas. Se você clica em uma imagem menos relevante (que ainda não tem esse rótulo), isso pode ser considerado um indício de que você, como humano, validou que esse rótulo também é aplicável. Se mais pessoas fazem o mesmo, então o Google pode automaticamente adicionar tal rótulo à imagem, e aumentar a relevância dele conforme essas buscas específicas ocorrem.

Outra ideia é usar fontes de rotulações mantidas por humanos, como o Flickr e/ou o Pinterest. Apesar de ser uma tarefa entendiante, quem gosta de fotografia sente prazer em fazê-lo nesse contexto. Além disso, há um trabalho comunitário na rotulação, que facilita a existência de novos rótulos.

Há ainda a ideia de usar jogos para automatizar a rotulação. A ideia é bem simples, mas muito inteligente: com um jogo de adivinhação, duas pessoas (que não necessariamente se conhecem) jogam pela Internet. O jogo simplesmente apresenta uma foto (de um filhotinho de labrador, por exemplo) para um dos jogadores, e o outro jogador (que não vê a foto) precisa adivinhar com base em perguntas que só podem ser respondidas com sim ou não pelo companheiro de jogo. As perguntas (por exemplo, "É um animal?) que vão sendo respondidas como sim, se tornam rótulos automaticamente, e a relevância decorre do número de ocorrências entre diferentes partidas. Eu infelizmente perdi a referência desse jogo, mas há inúmeros outros como o ESP-Game (que é bem similar) e o Name-It-Game (que faz a anotação por regiões).

2. Busca Baseada em Similaridade

Um dos problemas da abordagem anterior é que mesmo que as imagens sejam muito bem rotuladas ainda podem existir dificuldades semânticas importantes. Um exemplo clássico é a busca pelo termo "porco". Esse termo pode retornar imagens que sejam rotuladas corretamente, mas que são muito distintas e não necessariamente representam o que o usuário desejava no momento da busca. Eis um exemplo clássico (aqui no Brasil, ao menos):

A ideia dessa segunda abordagem é melhorar a busca evitando o uso de texto, mas fazendo a busca de imagens que sejam similares a uma imagem de referência fornecida pelo usuário (recurso que o Google Images também tem disponível).

A grande dificuldade dessa abordagem é justamente definir similaridade. Há três formas tradicionais (e eu suponho que o Google use uma mistura das duas primeiras): similaridade por cor, similaridade por textura e localização de pontos de referência.

Na similaridade por cor o algoritmo pode realizar uma medição numérica das cores na imagem de referência, e então buscar em um banco de dados em que tal medição já esteja pré-calculada (afinal, fazer esse cálculo a cada pesquisa é computacionalmente inviável). Existem inúmeros algoritmos, mas o mais simples é o seguinte (a fonte original dessa sugestão é esta resposta no SOEN):

  1. Escale as imagens para um tamanho pequeno (64x64, por exemplo, para que os detalhes sejam menos importantes na comparação).
  2. Escale as cores para o mesmo intervalo (para que ambas as imagens tenha a cor mais escura como preto e a mais clara como branco).
  3. Rotacione e inverta as imagens para que os cantos mais claro e mais escuro fiquem em locais padronizados (mais claro no canto superior esquerdo e mais escuro no canto inferior direito, por exemplo, para que ambas estejam na mesma orientação).
  4. Então, tire a diferença entre cada pixel e calcule a diferença média. Quando mais próxima de zero, mais similares serão as imagens.

É comum também combinar a comparação de cores com os locais e/ou o formato em que elas ocorrem. Como a diferença média do algoritmo anterior fornece um único valor para toda a imagem, a comparação vai resultar em algo como você mesmo disse na pergunta: comparar pela predominância geral de cor. Nesse caso, uma alternativa é - ao invés de ter um único valor de diferença média - ter uma quadtree com valores médios para diferentes regiões (e sub regiões) da imagem. Assim, a comparação pela similaridade ainda será por predominância de cores, mas em regiões específicas de forma a gerar resultados potencialmente mais acurados.

Em um passado não muito distante havia um produto comercial da IBM chamado QBIC, que chegou a ser usado em museus para facilitar a busca de quadros: bastava você desenhar mais ou menos o quadro que desejava (céu azul claro, mar azul escuro, areia amarela, por exemplo) e ele achava imagens similares. Infelizmente não achei museus que ainda usem essa tecnologia, mas há esse exemplo de buscador chamado Retrievr que faz exatamente o mesmo, buscando imagens similares ao que você desenha no Flickr. :)

Há também outro algoritmo bastante utilizado para definir similaridade: a comparação do histograma de cores normalizado. Um histograma nada mais é do que uma distribuição de frequências, isto é, do número de ocorrências de algo (cada valor de pixel, por exemplo) em um contexto (na imagem, por exemplo). O histograma de cores não separa as ocorrências por valor de pixel, mas sim por cada cor em uma sequência de cores (que você mesmo define, não precisa ser só RGB). Imagens semelhantes tem essa distribuição muito parecida, e a vantagem é que quando o histograma é normalizado (isto é, transformado em percentual de cada cor, pra não importar o número total de pixels) isso torna a comparação independente de rotação e escala nas imagens. Veja esta outra resposta do SOEN para mais detalhes sobre a implementação (nela há uma referência a slides com ajuda para obter histogramas em OpenCV, por exemplo).

Assim, você pode implementar esse algoritmo da seguinte forma:

  1. Calcule o histograma de cores para ambas as imagens (em cada imagem, conte os pixels e acumule essa contagem em "categorias" de cores que você definir - no exemplo da Wikipedia os pixels são contados para cada combinação RGB, mas com os valores dos pixels escalonados para [0 a 3] pra facilitar - isto é, diminuir o tamanho da tabela). Naturalmente, no caso das imagens no banco de dados esses valores podem (devem!) estar pré-calculados.
  2. Normalize os valores em cada categoria, dividindo o valor pelo número total de pixels. Isso resultará no valor em formato percentual, mais fácil de ser comparado.
  3. Compare os histogramas das duas imagens medindo, por exemplo, a taxa média de erro. Para cada categoria, tire a diferença entre os valores nas duas imagens. Depois, tire a diferença média entre todas as categorias. Quanto mais semelhante a imagem, mais próximo de zero será essa diferença.

inserir a descrição da imagem aqui

Na similaridade por textura procura-se definir o padrão (matemático) da textura da imagem. Você pode imaginar algo como a sequência de "claro-escuro-claro-escuro-..." que ocorre em uma imagem de um piso ladrilhado, por exemplo. Algo muito utilizado nesse caso são os Filtros de Gabor. Esses filtros são muito sensíveis às variações de bordas na imagem (bordas são detalhes importantes) em diferentes orientações (vertical, horizontal, diagonal, etc). Esses filtros são considerados como muito próximos à forma como o olho humano responde aos mesmos estímulos visuais, mas independentemente disso o fato é que eles são muito úteis para descrever a textura de uma imagem.

No blog de Patrick Fuller há um fantástico tutorial (em inglês) de 6 partes que vai te explicar muito facilmente (e com exemplos em C++) o princípio do processamento de imagens até chegar ao Filtro de Gabor. Vale a leitura!

Assim, é possível extrair esse padrão de uma imagem para então utilizá-lo em buscas. É também muito comum utilizar algoritmos de para aprender o padrão de um conjunto de imagens de exemplo e utilizá-los na classificação de novas imagens (como sendo de algo "já conhecido"). Este exemplo em Python demonstra exatamente isso, usando a biblioteca Scikit-Learn. Ele aprende o padrão de imagens de tijolos, grama e parede, e usa-o na função match para comparar as características de textura (features) de duas imagens (usando os mínimos quadrados para definir o "erro" - que quanto mais próximo de zero, mais similares as imagens são).

inserir a descrição da imagem aqui

Por fim, há também a possibilidade de se comparar as imagens diretamente em termos do detalhe de seu conteúdo, de forma a tentar encontrar imagens que sejam semelhantes em termos dessas ocorrências. A ideia é primeiramente encontrar nas imagens as características de borda (features) mais relevantes, e então verificar se as mesmas características ocorrem nas duas imagens (na de referência e na sendo comparada na busca).

Essa abordagem é mais usada para sobrepor imagens parciais (para juntá-las automaticamente e criar um panorama 360º, por exemplo), mas poderiam ser utilizadas também na comparação de conteúdo em uma busca. Existem exemplos prontos em OpenCV, tanto para identificar as características mais relevantes, como para fazer a sua localização entre as imagens (matching):

inserir a descrição da imagem aqui

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .