Detecção de imagem quase duplicada [fechada]

Qual é uma maneira rápida de classificar um determinado conjunto de imagens por semelhança entre si.

No momento, tenho um sistema que faz análise de histograma entre duas imagens, mas essa operação é muito cara e parece exagerada.

O ideal é que estou procurando um algoritmo que dê a cada imagem uma pontuação (por exemplo, uma pontuação inteira, como a média RGB) e posso apenas classificar por essa pontuação. Pontuações idênticas ou pontuações próximas umas das outras são possíveis duplicatas.

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

Média RGB por imagem é uma merda, há algo semelhante?

Tem havido muitas pesquisas sobre busca de imagens e medidas de similaridade. Não é um problema fácil. Em geral, um único intnão será suficiente para determinar se as imagens são muito semelhantes. Você terá uma alta taxa de falsos positivos.

No entanto, como muitas pesquisas foram feitas, você pode dar uma olhada em algumas delas. Por exemplo, este documento (PDF) fornece um algoritmo de impressão digital de imagem compacto que é adequado para localizar imagens duplicadas rapidamente e sem armazenar muitos dados. Parece que essa é a abordagem certa se você deseja algo robusto.

Se você está procurando por algo mais simples, mas definitivamente mais ad-hoc, esta pergunta do SO tem algumas idéias decentes.

Eu recomendaria deixar de usar apenas um histograma RGB.

Um resumo melhor de sua imagem pode ser obtido se você pegar uma wavelet Haar 2d da imagem (é muito mais fácil do que parece, é apenas uma grande quantidade de médias e algumas raízes quadradas usadas para ponderar seus coeficientes) e apenas reter o k maior coeficientes ponderados na wavelet como um vetor esparso, normalize-o e salve-o para reduzir seu tamanho. Você deve redimensionar RG e B usando pesos perceptuais de antemão, pelo menos, ou eu recomendo mudar para YIQ (ou YCoCg, para evitar ruído de quantização) para que você possa amostrar informações de crominância com importância reduzida.

Agora você pode usar o produto escalar de dois desses vetores normalizados esparsos como uma medida de similaridade. Os pares de imagens com os maiores produtos escalares serão muito semelhantes em estrutura. Isso tem a vantagem de ser ligeiramente resistente a redimensionamento, mudança de matiz e marca d'água, além de ser realmente fácil de implementar e compactar.

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

Classificar por uma única pontuação numérica será intratável para esse tipo de problema de classificação. Se você pensar sobre isso, seria necessário que as imagens só pudessem 'mudar' ao longo de um eixo, mas elas não mudam. É por isso que você precisa de um vetor de recursos. No caso da wavelet Haar é aproximadamente onde ocorrem as descontinuidades mais nítidas na imagem. Você pode calcular a distância entre as imagens aos pares, mas como tudo o que você tem é uma métrica de distância, uma ordenação linear não tem como expressar um 'triângulo' de 3 imagens que estão todas igualmente distantes. (ou seja, pense em uma imagem totalmente verde, uma imagem totalmente vermelha e uma imagem totalmente azul.)

Isso significa que qualquer solução real para o seu problema precisará de O (n ^ 2) operações no número de imagens que você tem. Ao passo que, se tivesse sido possível linearizar a medida, você poderia exigir apenas O (n log n) ou O (n) se a medida fosse adequada para, digamos, uma classificação de raiz. Dito isso, você não precisa gastar O (n ^ 2), pois na prática você não precisa vasculhar todo o conjunto, você só precisa encontrar o que está mais próximo do que algum limite. Assim, aplicando uma das várias técnicas para particionar seu espaço vetorial esparso, você pode obter assintóticos muito mais rápidos para o problema de 'encontrar o me k das imagens que são mais semelhantes do que um determinado limite' do que comparar ingenuamente todas as imagens com todas as imagens, dando-lhe o que você provavelmente precisa ... se não exatamente o que você pediu.

Em qualquer caso, usei isso há alguns anos com bons resultados pessoalmente ao tentar minimizar o número de texturas diferentes que estava armazenando, mas também houve muito ruído de pesquisa neste espaço, mostrando sua eficácia (e, neste caso, comparando para uma forma mais sofisticada de classificação de histograma):

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

Se você precisar de melhor precisão na detecção, os algoritmos minHash e tf-idf podem ser usados ​​com a wavelet Haar (ou o histograma) para lidar com as edições de forma mais robusta:

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

Finalmente, Stanford tem uma pesquisa de imagens baseada em uma variante mais exótica desse tipo de abordagem, baseada em fazer mais extração de recursos das ondas para encontrar seções giradas ou dimensionadas de imagens, etc., mas isso provavelmente vai muito além da quantidade de trabalho que você gostaria de fazer.

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

Implementei um algoritmo muito confiável para isso, chamado Fast Multiresolution Image Querying . Meu código (antigo, sem manutenção) para isso está aqui .

O que o Fast Multiresolution Image Querying faz é dividir a imagem em 3 partes com base no espaço de cores YIQ (melhor para combinar diferenças do que RGB). Em seguida, a imagem é essencialmente compactada usando um algoritmo de wavelet até que apenas os recursos mais proeminentes de cada espaço de cor estejam disponíveis. Esses pontos são armazenados em uma estrutura de dados. As imagens de consulta passam pelo mesmo processo e os recursos proeminentes na imagem de consulta são comparados àqueles no banco de dados armazenado. Quanto mais correspondências, mais provável é que as imagens sejam semelhantes.

O algoritmo é freqüentemente usado para a funcionalidade "consulta por esboço". Meu software só permitia inserir imagens de consulta via URL, portanto, não havia interface de usuário. No entanto, descobri que funcionou excepcionalmente bem para combinar miniaturas com a versão grande dessa imagem.

Muito mais impressionante do que o meu software é o retrievr, que permite testar o algoritmo FMIQ usando imagens do Flickr como fonte. Muito legal! Experimente através de um esboço ou usando uma imagem original e você verá como funciona bem.

Uma imagem tem muitos recursos, portanto, a menos que você se restrinja a um, como o brilho médio, está lidando com um espaço problemático n-dimensional.

Se eu pedisse para você atribuir um único inteiro às cidades do mundo, para que eu pudesse dizer quais são as próximas, os resultados não seriam bons. Você pode, por exemplo, escolher o fuso horário como seu único inteiro e obter bons resultados com certas cidades. No entanto, uma cidade próxima ao pólo norte e outra cidade próxima ao pólo sul também podem estar no mesmo fuso horário, embora estejam em extremos opostos do planeta. Se eu permitir que você use dois inteiros, poderá obter resultados muito bons com latitude e longitude. O problema é o mesmo para a semelhança de imagens.

Dito isso, existem algoritmos que tentam agrupar imagens semelhantes, o que é efetivamente o que você está pedindo. Isso é o que acontece quando você faz a detecção de rosto com o Picasa. Mesmo antes de identificar qualquer rosto, ele agrupa outros semelhantes, de modo que seja fácil passar por um conjunto de faces semelhantes e dar a maioria deles o mesmo nome.

Há também uma técnica chamada Análise de componente principal, que permite reduzir os dados n-dimensionais a qualquer número menor de dimensões. Portanto, uma imagem com n recursos pode ser reduzida a um recurso. No entanto, essa ainda não é a melhor abordagem para comparar imagens.

Há uma biblioteca C ("libphash" - http://phash.org/ ) que calculará um "hash perceptivo" de uma imagem e permitirá que você detecte imagens semelhantes comparando hashes (para que você não precise comparar cada imagem diretamente contra todas as outras imagens), mas infelizmente não parecia muito preciso quando tentei.

Você tem que decidir o que é "semelhante". Contraste? Matiz?

A imagem é "semelhante" à mesma imagem de cabeça para baixo?

Aposto que você pode encontrar muitos "fechos" dividindo as imagens em pedaços de 4x4 e obtendo uma cor média para cada célula da grade. Você teria dezesseis pontuações por imagem. Para julgar a semelhança, você faria apenas uma soma dos quadrados das diferenças entre as imagens.

Não acho que um único hash faça sentido, a menos que seja contra um único conceito como matiz, brilho ou contraste.

Aqui está a sua ideia:

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

Em primeiro lugar, assumirei que esses são números decimais R * (2 ^ 16) + G * (2 ^ 8) + B, ou algo parecido. Obviamente, isso não é bom porque o vermelho tem um peso desordenado.

Mudar para um espaço HSV seria melhor. Você pode espalhar os bits de HSV no hash, ou pode apenas resolver H, S ou V individualmente, ou pode ter três hashes por imagem.

Mais uma coisa. Se você pesar R, G e B. Pesar mais o verde, depois o vermelho e depois o azul para corresponder à sensibilidade visual humana.

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

A questão Boa maneira de identificar imagens semelhantes? parece fornecer uma solução para sua dúvida.

Presumi que outro software de pesquisa de imagem duplicada realiza um FFT nas imagens e armazena os valores das diferentes frequências como vetores:

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

e então você pode comparar duas imagens para igualdade , calculando a distância entre os vetores de peso de duas imagens:

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

Uma solução é realizar uma comparação RMS / RSS em cada par de imagens necessárias para realizar uma classificação por bolha. Em segundo lugar, você poderia executar um FFT em cada imagem e fazer algumas médias de eixo para recuperar um único inteiro para cada imagem que você usaria como um índice para classificar. Você pode considerar fazer qualquer comparação em uma versão redimensionada (25%, 10%) do original, dependendo da pequena diferença que você escolheu ignorar e de quanto aumento de velocidade você precisa. Deixe-me saber se essas soluções são interessantes, e podemos discutir ou fornecer um código de amostra.

A maioria das abordagens modernas para detectar a detecção de imagem quase duplicada usa a detecção de pontos interessantes e descritores que descrevem a área ao redor desses pontos. Freqüentemente, SIFT é usado. Então você pode quantificar descritores e usar clusters como vocabulário visual de palavras.

Portanto, se observarmos a proporção de palavras visuais comuns de duas imagens para todas as palavras visuais dessas imagens, você estima a semelhança entre as imagens. Existem muitos artigos interessantes. Um deles é a detecção de imagem quase duplicada: minHash e tf-idf Weighting

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

Ao definir algum limite e selecionar algum método, você pode medir a similaridade.