Impressão digital da imagem para comparar a semelhança de muitas imagens

Preciso criar impressões digitais de muitas imagens (cerca de 100.000 existentes, 1.000 novas por dia, RGB, JPEG, tamanho máximo de 800x800) para comparar cada imagem com todas as outras imagens muito rapidamente. Não posso usar métodos binários de comparação porque também imagens quase semelhantes devem ser reconhecidas.

Melhor seria uma biblioteca existente, mas também algumas dicas para algoritmos existentes me ajudariam muito.

Algoritmos de hash normal ou de cálculo CRC não funcionam bem com dados de imagem. A natureza dimensional da informação deve ser levada em consideração.

Se você precisar de impressões digitais extremamente robustas, de modo que transformações afins (escala, rotação, translação, inversão) sejam contabilizadas, você pode usar uma transformação de Radon na fonte da imagem para produzir um mapeamento normativo dos dados da imagem - armazene-o com cada imagem e em seguida, compare apenas as impressões digitais. Este é um algoritmo complexo e não para os fracos de coração.

algumas soluções simples são possíveis:

1. Crie um histograma de luminosidade para a imagem como uma impressão digital
2. Crie versões reduzidas de cada imagem como uma impressão digital
3. Combine a técnica (1) e (2) em uma abordagem híbrida para melhorar a qualidade de comparação

Um histograma de luminosidade (especialmente aquele que é separado em componentes RGB) é uma impressão digital razoável para uma imagem - e pode ser implementado com bastante eficiência. Subtrair um histograma de outro produzirá um novo historgrama que você pode processar para decidir o quão semelhantes são duas imagens. Os histogramas, porque os únicos que avaliam a distribuição e ocorrência de informações de luminosidade / cor lidam muito bem com as transformações afins. Se você quantizar as informações de luminosidade de cada componente de cor até um valor de 8 bits, 768 bytes de armazenamento são suficientes para a impressão digital de uma imagem de quase qualquer tamanho razoável. Os histogramas de luminosidade produzem falsos negativos quando as informações de cor em uma imagem são manipuladas. Se você aplicar transformações como contraste / brilho, posterizar, mudança de cor, mudanças nas informações de luminosidade.

Usar imagens em escala é outra maneira de reduzir a densidade de informações da imagem a um nível mais fácil de comparar. Reduções abaixo de 10% do tamanho da imagem original geralmente perdem muitas informações para serem úteis - portanto, uma imagem de 800x800 pixels pode ser reduzida para 80x80 e ainda fornecer informações suficientes para realizar uma impressão digital decente. Ao contrário dos dados do histograma, você deve executar o dimensionamento anisotrópico dos dados da imagem quando as resoluções da fonte têm proporções variáveis. Em outras palavras, reduzir uma imagem de 300x800 em uma miniatura de 80x80 causa deformação da imagem, de forma que quando comparada com uma imagem de 300x500 (que é muito semelhante) irá causar falsos negativos. Impressões digitais em miniatura também costumam produzir falsos negativos quando transformações afins estão envolvidas. Se você virar ou girar uma imagem,

Combinar as duas técnicas é uma maneira razoável de proteger suas apostas e reduzir a ocorrência de falsos positivos e falsos negativos.

Há uma abordagem muito menos ad-hoc do que as variantes de imagem reduzidas que foram propostas aqui, que retém seu sabor geral, mas que fornece uma base matemática muito mais rigorosa para o que está acontecendo.

Faça uma wavelet de Haar da imagem. Basicamente, a wavelet Haar é a sucessão de diferenças das imagens de resolução mais baixa para cada imagem de resolução mais alta, mas ponderada por quão profundo você está na 'árvore' de mipmaps. O cálculo é direto. Então, uma vez que você tenha a wavelet Haar devidamente ponderada, jogue fora todos os coeficientes, exceto os k maiores (em termos de valor absoluto), normalize o vetor e salve-o.

Se você pegar o produto escalar de dois desses vetores normalizados, obterá uma medida de similaridade com 1 sendo quase idêntico. Postei mais informações aqui .

Você definitivamente deveria dar uma olhada em phash .

Para comparação de imagens, existe este projeto php : https://github.com/kennethrapp/phasher

E meu pequeno clone de javascript : https://redaktor.me/phasher/demo_js/index.html

Infelizmente, isso é baseado em "contagem de bits", mas reconhecerá imagens giradas. Outra abordagem em javascript era construir um histograma de luminosidade a partir da imagem com a ajuda do canvas. Você pode visualizar um histograma de polígono na tela e comparar esse polígono em seu banco de dados (por exemplo, mySQL espacial ...)

Há muito tempo, trabalhei em um sistema que tinha algumas características semelhantes, e esta é uma aproximação do algoritmo que seguimos:

1. Divida a imagem em zonas. Em nosso caso, estávamos lidando com vídeo de resolução 4: 3, então usamos 12 zonas. Isso tira a resolução das imagens de origem da imagem.
2. Para cada zona, calcule uma cor geral - a média de todos os pixels na zona
3. Para a imagem inteira, calcule uma cor geral - a média de todas as zonas

Portanto, para cada imagem, você está armazenando n + 1valores inteiros, onde né o número de zonas que você está rastreando.

Para fazer comparações, você também precisa examinar cada canal de cor individualmente.

1. Para a imagem geral, compare os canais de cores para as cores gerais para ver se eles estão dentro de um certo limite - digamos, 10%
2. Se as imagens estiverem dentro do limite, em seguida compare cada zona. Se todas as zonas também estiverem dentro do limite, as imagens são uma correspondência forte o suficiente para que você possa pelo menos sinalizá-las para comparação posterior.

Isso permite que você descarte rapidamente as imagens que não correspondem; você também pode usar mais zonas e / ou aplicar o algoritmo recursivamente para obter maior confiança de correspondência.

Semelhante à resposta de Ic - você pode tentar comparar as imagens em várias resoluções. Portanto, cada imagem é salva como 1x1, 2x2, 4x4 .. 800x800. Se a resolução mais baixa não corresponder (sujeito a um limite), você pode rejeitá-la imediatamente. Se corresponder, você pode compará-los na resolução mais alta seguinte e assim por diante.

Além disso, se as imagens compartilharem qualquer estrutura semelhante, como imagens médicas, você poderá extrair essa estrutura em uma descrição que seja mais fácil / rápida de comparar.

Então você deseja fazer "correspondência de impressão digital" que é bem diferente de "correspondência de imagem". A análise das impressões digitais foi profundamente estudada durante os últimos 20 anos, e vários algoritmos interessantes foram desenvolvidos para garantir a taxa de detecção correta (com relação às medidas FAR e FRR - Taxa de aceitação falsa e Taxa de rejeição falsa ).

Eu sugiro que você dê uma olhada melhor na classe de técnicas de detecção LFA (Local Feature Analysis) , principalmente construída em minúcias de inspeção. Minúcias são características específicas de qualquer impressão digital e foram classificadas em várias classes. Mapear uma imagem raster para um mapa de minúcias é o que, na verdade, a maioria das autoridades públicas faz para registrar criminosos ou terroristas.

Veja aqui mais referências

Para comparação de imagens do iPhone e desenvolvimento de similaridade de imagens, confira: http://sites.google.com/site/imagecomparison/

Para vê-lo em ação, verifique eyeBuy Visual Search na iTunes AppStore.

A partir de 2015 (de volta ao futuro ... nesta questão de 2009, que agora está bem classificada no Google), a semelhança de imagem pode ser calculada usando técnicas de aprendizado profundo. A família de algoritmos conhecida como Auto Encoders pode criar uma representação vetorial que pode ser pesquisada por similaridade. Há uma demonstração aqui .

Uma maneira de fazer isso é redimensionar a imagem e diminuir a resolução significativamente (para 200x200 talvez?), Armazenando uma versão menor (média de pixels) para fazer a comparação. Em seguida, defina um limite de tolerância e compare cada pixel. Se o RGB de todos os pixels estiver dentro da tolerância, você tem uma correspondência.

Sua execução inicial é O (n ^ 2), mas se você catalogar todas as correspondências, cada nova imagem é apenas um algoritmo O (n) para comparar (você só precisa compará-lo com cada imagem inserida anteriormente). No entanto, ele acabará quebrando conforme a lista de imagens a serem comparadas se torna maior, mas acho que você está seguro por um tempo.

Após 400 dias de execução, você terá 500.000 imagens, o que significa (descontando o tempo para redimensionar a imagem) 200(H)*200(W)*500,000(images)*3(RGB)= 60.000.000.000 de comparações. Se cada imagem for uma correspondência exata, você ficará para trás, mas provavelmente não será o caso, certo? Lembre-se de que você pode descontar uma imagem como uma correspondência assim que uma única comparação ficar fora de seu limite.

Você quer literalmente comparar todas as imagens com as outras? Qual é o aplicativo? Talvez você só precise de algum tipo de indexação e recuperação de imagens com base em determinados descritores? Então, por exemplo, você pode olhar para o padrão MPEG-7 para Interface de descrição de conteúdo multimídia. Em seguida, você pode comparar os diferentes descritores de imagem, o que não será tão preciso, mas muito mais rápido.

Parece que algoritmos especializados de hash de imagem são uma área de pesquisa ativa, mas talvez um cálculo normal de hash dos bytes da imagem resolva o problema.

Você está procurando imagens de bytes idênticos em vez de imagens derivadas da mesma fonte, mas que podem ter um formato ou resolução diferente (o que me parece um problema bastante difícil).