O algoritmo pode ser usado para identificar se as imagens são a “mesma” ou similar, independentemente do tamanho?

Question

TinEye , a "imagem invertida motor de busca", permite que você faça o upload / link para uma imagem e é capaz para pesquisar os bilhões de imagens que tenha rastreado e ele irá retornar links para imagens que constatou que são a mesma imagem.

No entanto, não é uma soma de verificação ingênuo ou qualquer coisa relacionada a isso. Muitas vezes, é capaz de encontrar as duas imagens de uma resolução maior e menor resolução e maior e menor tamanho que a imagem original que você fornecer. Este é um bom uso para o serviço porque muitas vezes eu encontrar uma imagem e quer a versão mais alta resolução de possível.

Não só isso, mas eu tive que encontrar imagens do mesmo conjunto de imagens, onde as pessoas na imagem estão em uma posição diferente, mas o fundo em grande parte permanece o mesmo.

Que tipo de algoritmo poderia TinEye estar usando que lhe permitiria comparar uma imagem com outras pessoas de vários tamanhos e de compressão rácios e ainda assim descobrir com precisão que eles são a "mesma" imagem ou set?

Answer 1

Esses algoritmos são geralmente baseados em impressão digital. Fingerprint é uma estrutura de dados razoavelmente pequeno, algo como um código hash longo. No entanto, os objetivos da função de impressão digital são opostas aos objetivos da função hash. Uma função de hash boa deve gerar muito diferentes códigos para muito semelhante (mas não igual) objetos. A função de impressão digital deve, em contrário, geram a mesma impressão digital por imagens semelhantes.

Só para dar um exemplo, esta é uma função de impressão digital (não particularmente bom): redimensionar a imagem ao quadrado 32x32, normalizar e e quantificar as cores, reduzindo o número de cores para algo como 256. Então, você tem 1024 impressão digital -byte para a imagem. Basta manter uma tabela de impressão digital => [lista de URLs de imagem]. Quando você precisa olhar para as imagens semelhantes a uma determinada imagem, basta calcular seu valor de impressão digital e encontrar a lista de imagem correspondente. Fácil.

O que não é fácil - para ser útil na prática, a função de impressão digital precisa ser robusto contra culturas, transforma afins, alterações de contraste, etc. Construção de boas funções de impressão digital é um tema de pesquisa em separado. Muitas vezes eles são mão-afinado e usa um monte de heurística (ou seja, usar o conhecimento sobre os conteúdos típicos de fotografias, sobre o formato de imagem / dados adicionais em EXIF, etc.)

Outra variação é a utilização de mais de uma função de impressão digital, tentar aplicar cada um deles e combinar os resultados. Na verdade, é semelhante a encontrar textos semelhantes. Assim em vez de "saco de palavras" a busca da imagem similaridade usa um "saco de impressões digitais" e achados quantos elementos de um saco são os mesmos elementos de outro saco. Como fazer esta pesquisa eficiente é outro assunto.

Agora, em relação aos artigos / papers. Eu não poderia encontrar um bom artigo que daria uma visão geral dos diferentes métodos. A maioria dos artigos públicos Sei discutir melhorias específicas para métodos específicos. Eu poderia recomendar para verificar estes:

"Fingerprinting conteúdo Utilizando Wavelets" . Este artigo é sobre fingerprinting áudio usando wavelets, mas o mesmo método pode ser adaptado para fingerprinting imagem.

PERMUTATION agrupamento: INTELIGENTE função Hash DESIGN PARA AUDIO & recuperação de imagens . Informações sobre Hashes Localidade-sensível.

Agrupamento Características de Grande Escala Parcial-Duplicate Web Image Search . Um artigo muito bom, fala sobre SIFT e características agregação de eficiência. Ele também tem uma bibliografia agradável no final

Answer 2

É provavelmente baseado em melhorias de algoritmos de extração de características, aproveitando-se de características que são invariantes escala.

Veja

• recurso de extração

• SIFT , outro site

ou, se você estiver realmente interessado, você pode desembolsar cerca de 70 dólares (ou pelo menos olhar para a pré-visualização do Google) para

• recurso de extração e Processamento de Imagem

Answer 3

O criador do site FotoForensics postou este post sobre este tema, que foi muito útil para mim, e mostrou algoritmos que podem ser bons o suficiente para você e que exigem muito menos trabalho do que wavelets e extração de características.

http: // www .hackerfactor.com / blog / index.php? /archives/529-Kind-of-Like-That.html

aHash (também chamado Hash médio ou Hash Média). Esta abordagem esmaga a imagem em uma imagem de 8x8 em tons de cinza e define os 64 bits o hash com base em se o valor do pixel é maior do que o cor média para a imagem.

pHash (também chamado de "Hash Perceptive"). Este algoritmo é semelhante ao aHash mas usar um cosseno transformada discreta (DCT) e compara com base em freqüências em vez de valores de cor.

dHash Como aHash e pHash, dHash é bastante simples de implementar e é muito mais preciso do que tem o direito de ser. como um aplicação, dHash é quase idêntico ao aHash mas ele executa muito melhor. Enquanto aHash concentra-se em valores médios e avalia pHash padrões de freqüência, dHash faixas gradientes.

Answer 4

A Transformada de Hough é um algoritmo de extração de características muito antigo, que você mente achar interessante. Duvido que seja o que tinyeye usos, mas é uma boa, simples começando lugar para aprender sobre a extração de características.

Há também slides para um puro talk a partir de algumas Universidade de Toronto pessoas sobre o seu trabalho em astrometry.net . Eles desenvolveram um algoritmo para combinar telescópica imagens do céu noturno para locais em catálogos de estrelas, a fim de identificar as características da imagem. É um problema mais específico do que o que tinyeye tenta resolver, mas eu esperaria que muitas das idéias básicas que eles falam sobre são aplicáveis ??para o problema mais geral.

Answer 5

http://tineye.com/faq#how

Com base nisso, a resposta de Igor Krivokon parece ser sobre a marca.

Answer 6

Eles podem muito bem estar fazendo um Fourier Transform para caracterizar a complexidade da imagem, bem como um histograma para caracterizar a distribuição cromática, emparelhado com um algoritmo região categorização para garantir que as imagens semelhante complexos e coloridos não se erroneamente emparelhado . Não sei se isso é o que eles estão usando, mas parece que faria o truque.

Answer 7

Confira este post (não é meu) para uma descrição muito compreensível de um algoritmo muito compreensível que parece para obter bons resultados para como é simples. Ele basicamente partições respectivas fotos em uma grade muito grossa, classifica a rede pela vermelhas: azul e verde: azul proporções, e verifica se os tipos eram os mesmos. Isto, naturalmente, funciona apenas para imagens a cores.

Os prós mais provável obter melhores resultados usando vastamente algoritmos mais avançados. Como mencionado nos comentários sobre o blog, uma abordagem líder parece ser wavelets.

Answer 8

O que sobre o redimensionamento das fotos para um tamanho padrão pequeno e verificação de SSIM ou valores PSNR somente luma? isso é o que eu faria.