Near-Duplicate Imagem Detecção [fechado]

Question

O que é uma maneira rápida de resolver um determinado conjunto de imagens por sua semelhança com o outro.

No momento eu tenho um sistema que faz histograma análise entre duas imagens, mas esta é uma operação muito cara e parece muito exagero.

O ideal é que eu estou procurando um algoritmo que daria a cada imagem uma pontuação (por exemplo, uma pontuação inteiro, como o RGB Médio) e eu só posso classificar por essa pontuação. Pontuações idênticos ou pontuações ao lado do outro são possíveis duplicatas.

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994 

RGB médio por imagem é uma porcaria, há algo semelhante?

Answer 1

Tem havido uma série de pesquisas sobre as medidas de busca imagem e semelhança. Não é um problema fácil. Em geral, um único int não será suficiente para determinar se as imagens são muito semelhantes. Você terá uma alta taxa de falso-positivo.

No entanto, uma vez que tem havido muita pesquisa feito, você pode dar uma olhada em alguns deles. Por exemplo, este papel (PDF ) dá uma imagem algoritmo de impressão digital compacta que é adequado para encontrar imagens duplicadas de forma rápida e sem armazenar muitos dados. Parece que esta é a direito abordagem se você quiser algo robusto.

Se você está procurando algo mais simples, mas definitivamente mais ad-hoc, esta questão SO tem algumas ideias decentes.

Answer 2

Eu recomendaria considerando se afastando de apenas usando um histograma RGB.

Uma melhor digestão da sua imagem pode ser obtida se você tomar um Haar 2d wavelet da imagem (seu muito mais fácil do que parece, é apenas um monte de compensação e algumas raízes quadradas utilizadas para pesar os seus coeficientes) e apenas reter k as maiores coeficientes ponderados no wavelet como um vector esparso, normalizar, e excepto que, para reduzir o seu tamanho. Você deve redimensionar R G e B usando pesos de percepção de antemão, pelo menos, ou eu recomendo mudar para YIQ (ou YCoCg, ao ruído evitar quantização) para que você possa provar informação de crominância com importância reduzida.

Você pode agora usar o produto escalar de dois desses vetores normalizados esparsas como uma medida de similaridade. Os pares de imagens com os maiores produtos de ponto vai ser muito semelhante em estrutura. Isto tem a vantagem de ser um pouco resistente ao redimensionamento, mudança de cor e marca d'água, e ser realmente fácil de implementar e compacto.

Você pode trocar o armazenamento e precisão, aumentando ou diminuindo k.

Classificando por uma única pontuação numérica vai ser intratável para este tipo de problema de classificação. Se você pensar sobre isso exigiria imagens para só será capaz de 'mudança' ao longo de um eixo, mas eles não. É por isso que você precisa de um vector de características. No caso wavelet Haar sua aproximadamente onde as descontinuidades nítidas na imagem ocorrer. Você pode calcular a distância entre imagens aos pares, mas desde que tudo que você tem é uma uma métrica de distância linear ordenação não tem maneira de expressar um 'triângulo' de 3 imagens que são todos igualmente distante. (Ou seja, pensar em uma imagem que é toda verde, uma imagem que é todo vermelho e uma imagem que é tudo azul.)

Isso significa que qualquer solução real para o problema vai precisar O (n ^ 2) operações no número de imagens que você tem. Considerando que, se tivesse sido possível para linearizar a medida, o que poderia exigir apenas O (n log n), ou O (n) se a medida era adequado para, digamos, uma espécie radix. Dito isto, você não precisa gastar O (n ^ 2) uma vez que na prática você não precisa vasculhar todo o conjunto, você só precisa encontrar as coisas isso é mais perto do que algum limiar. Assim, através da aplicação de uma das várias técnicas para particionar o espaço vetorial esparsa você pode obter muito mais rápido asymptotics para a 'encontrar-me k das imagens que são mais semelhantes do que um dado limiar' problema de comparar ingenuamente cada imagem contra cada imagem, dando-lhe o que você provavelmente necessidade ... se não exatamente o que você pediu.

Em qualquer caso, eu usei isso há alguns anos com bons resultados pessoalmente ao tentar minimizar o número de diferentes texturas eu estava armazenamento, mas também tem havido muito barulho investigação neste espaço mostrando sua eficácia (e em neste caso, comparando-a com uma forma mais sofisticada de classificação histograma):

http://www.cs.princeton.edu/cass/papers/ spam_ceas07.pdf

Se você precisar de uma melhor precisão na detecção, os algoritmos minHash e TF-IDF pode ser usado com a Transformada de Haar (ou o histograma) para lidar com as edições mais robusta:

http://cmp.felk.cvut.cz/~chum/ papers / chum_bmvc08.pdf

Finalmente, Stanford tem uma pesquisa de imagens com base em uma variante mais exótico deste tipo de abordagem, baseada em fazer mais de extração de características das ondas para encontrar seções girados ou dimensionados de imagens, etc, mas que provavelmente vai muito além do montante de trabalho que você gostaria de fazer.

http://wang14.ist.psu.edu/cgi- bin / Zwang / regionsearch_show.cgi

Answer 3

Eu implementou um algoritmo muito confiável para este chamado rápido Multiresolution Imagem Consultando . Meu código (antiga, não mantido) para isso é aqui .

O rápido Multiresolution Imagem Consultando faz é dividir a imagem em 3 partes com base no colorspace YIQ (melhor para diferenças correspondência de RGB). Em seguida, a imagem é essencialmente comprimido usando um algoritmo de wavelet até que apenas a maioria dos recursos de destaque de cada espaço de cores estão disponíveis. Estes pontos são armazenados em uma estrutura de dados. imagens de consulta passar pelo mesmo processo, e as características proeminentes da imagem consulta são comparados com aqueles no banco de dados armazenado. Quanto mais jogos, o mais provável as imagens são semelhantes.

O algoritmo é usado frequentemente para "consulta por sketch" funcionalidade. Meu software só é permitido entrar imagens de consulta via URL, então não havia nenhuma interface de usuário. No entanto, descobri que funcionou excepcionalmente bem para combinar miniaturas à grande versão dessa imagem.

Muito mais impressionante do que o meu software é Retrievr que permite que você experimente o algoritmo FMIQ utilizando imagens do Flickr como a fonte. Muito legal! Experimentá-lo via esboço ou usando uma imagem de origem, e você pode ver o quão bem ele funciona.

Answer 4

A imagem tem muitas características, a menos que você restringir-se a um, como a luminosidade média, você está lidando com um problema de espaço n-dimensional.

Se eu perguntei-lhe atribuir um único inteiro para as cidades do mundo, para que eu pudesse dizer quais são próximos, os resultados não seria grande. Você pode, por exemplo, escolher o fuso horário como seu inteiro único e obter bons resultados com algumas cidades. No entanto, uma cidade perto do pólo norte e outra cidade perto do pólo sul também podem estar no mesmo fuso horário, mesmo que eles estão em extremos opostos do planeta. Se eu deixar você usar dois números inteiros, você pode obter resultados muito bons com a latitude e longitude. O problema é o mesmo para semelhança de imagem.

Tudo o que disse, há algoritmos que tentam agrupar imagens semelhantes juntos, o que é efetivamente o que você está pedindo. Isto é o que acontece quando você faz detecção de rosto com o Picasa. Mesmo antes de você identificar quaisquer rostos, que agrupa os similares em conjunto de modo que é fácil passar por um conjunto de rostos semelhantes e dar a maioria deles do mesmo nome.

Há também uma técnica chamada Princípio Análise de Componentes, que permite reduzir os dados n-dimensionais para baixo para qualquer número menor de dimensões. Assim, uma imagem com n características poderia ser reduzido a um recurso. No entanto, isso ainda não é a melhor abordagem para a comparação de imagens.

Answer 5

Há uma biblioteca C ( "libphash" - http://phash.org/ ) que irá calcular um " de hash perceptual" de uma imagem e permitem detectar imagens semelhantes comparando hashes (assim você não tem que comparar cada imagem diretamente contra qualquer outra imagem), mas infelizmente não parece ser muito preciso quando eu tentei.

Answer 6

Você tem que decidir o que é "similar". Contraste? Hue?

É uma imagem "similar" à mesma imagem de cabeça para baixo?

Eu aposto que você pode encontrar um monte de "chamadas de perto" por quebrar as imagens até em 4x4 peças e obter uma cor média para cada célula da grade. Você teria dezesseis contagens por imagem. Para semelhança juiz, você teria apenas que fazer a soma dos quadrados das diferenças entre imagens.

Eu não acho que um único de hash faz sentido, a menos que seja contra um único conceito como matiz, ou o brilho ou contraste.

Esta é a sua ideia:

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

Primeiro de tudo, eu vou assumir esses números decimais são que são R * (2 ^ 16) + G * (2 ^ 8) + B, ou algo parecido. Obviamente isso não é bom porque o vermelho é ponderado desordenadamente.

Movendo-se para HSV espaço seria melhor. Você poderia os pedaços de HSV fora para o hash, ou você pode apenas se contentar H ou S ou V individualmente, ou você poderia ter três hashes por imagem.

---

Só mais uma coisa. Se você fizer peso R, G e B. Peso verde mais alto, em seguida, vermelho, depois azul para combinar com sensibilidade visual humana.

Answer 7

Na era dos serviços da web que você poderia tentar http://tineye.com

Answer 8

A questão boa maneira de identificar imagens similares? parece fornecer uma solução para sua pergunta.

Answer 9

Eu assumi que outros duplicados executa software de pesquisa de imagem de uma FFT nas imagens, e armazena os valores dos diferentes freqüências como um vetores:

Image1 = (u1, u2, u3, ..., un)
Image2 = (v1, v2, v3, ..., vn)

e, em seguida, você pode comparar duas imagens para equalness , calculando a distância entre os vetores de pesos de duas imagens:

distance = Sqrt(
     (u1-v1)^2 +
     (u2-v2)^2 +
     (u2-v3)^2 +
     ...
     (un-vn)^2);

Answer 10

Uma solução é realizar uma comparação RMS / RSS em cada par de quadros necessários para realizar uma espécie de bolha. Em segundo lugar, você pode realizar uma FFT em cada imagem e fazer alguma média eixo para recuperar um único inteiro para cada imagem que você usaria como um índice para ordenar por. Você pode considerar fazer o que a comparação em uma versão redimensionada (25%, 10%) do original dependendo de como pequena diferença a você optar por ignorar e quanto aceleração que você necessita. Deixe-me saber se essas soluções são interessantes, e podemos discutir ou eu posso fornecer o código de exemplo.

Answer 11

A maioria das abordagens modernas para detectar Perto imagem duplicada uso de detecção de pontos interessantes detecção e descritores que descrevem a área em torno de tais pontos. Muitas vezes SIFT é usado. Então você pode quatize descritores e usar agrupamentos como vocabulário palavra visual.

Então, se vemos na proporção de palavras visuais comuns de duas imagens para todas as palavras visuais destas imagens que você estimar a similaridade entre as imagens. Há uma série de artigos interessantes. Um deles é Perto Detecção Duplicate Image: minHash e tf-idf Ponderação

Answer 12

Por exemplo, utilizando extensão IMMI e IMMI você pode examinar muitas maneiras diferentes como medida de similaridade entre as imagens: http: / /spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension-for-rapidminer-5

Ao definir um limite e selecionando algum método você pode medir similaridade.