Comparação de imagens - algoritmo rápido

Estou procurando criar uma tabela de imagens de base e, em seguida, comparar novas imagens com relação a isso para determinar se a nova imagem é uma duplicata exata (ou fechada) da base.

Por exemplo: se você quiser reduzir o armazenamento da mesma imagem centenas de vezes, poderá armazenar uma cópia e fornecer links de referência. Quando uma nova imagem é inserida, você deseja comparar com uma imagem existente para garantir que não seja uma duplicata ... idéias?

Uma ideia minha era reduzir para uma miniatura pequena e, em seguida, escolher aleatoriamente 100 locais de pixel e comparar.

Abaixo estão três abordagens para resolver esse problema (e existem muitas outras).

• A primeira é uma abordagem padrão em visão computacional, correspondência de pontos-chave. Isso pode exigir algum conhecimento prévio para implementar e pode ser lento.

• O segundo método usa apenas o processamento de imagem elementar e é potencialmente mais rápido que a primeira abordagem e é simples de implementar. No entanto, quanto ganha em compreensão, falta robustez - a correspondência falha em imagens redimensionadas, giradas ou descoloridas.

• O terceiro método é rápido e robusto, mas é potencialmente o mais difícil de implementar.

Correspondência de Keypoint

Melhor do que escolher 100 pontos aleatórios, é escolher 100 pontos importantes . Certas partes de uma imagem têm mais informações do que outras (principalmente bordas e cantos), e estas são as que você deseja usar para a correspondência inteligente de imagens. Google " extração de ponto-chave " e " correspondência de ponto-chave " e você encontrará vários trabalhos acadêmicos sobre o assunto. Atualmente, os pontos-chave do SIFT são indiscutivelmente os mais populares, pois podem combinar imagens em diferentes escalas, rotações e iluminação. Algumas implementações do SIFT podem ser encontradas aqui .

Uma desvantagem da correspondência de pontos-chave é o tempo de execução de uma implementação ingênua: O (n ^ 2m), em que n é o número de pontos-chave em cada imagem e m é o número de imagens no banco de dados. Alguns algoritmos inteligentes podem encontrar a correspondência mais próxima mais rapidamente, como quadtrees ou particionamento de espaço binário.

Solução alternativa: método de histograma

Outra solução menos robusta, mas potencialmente mais rápida, é criar histogramas de recursos para cada imagem e escolher a imagem com o histograma mais próximo do histograma da imagem de entrada. Eu implementei isso na graduação e usamos três histogramas de cores (vermelho, verde e azul) e dois histogramas de textura, direção e escala. Vou dar os detalhes abaixo, mas devo observar que isso só funcionou bem para combinar imagens MUITO semelhantes às imagens do banco de dados. Imagens redimensionadas, rotacionadas ou descoloridas podem falhar com esse método, mas pequenas alterações como o corte não quebram o algoritmo

O cálculo dos histogramas de cores é simples - basta escolher o intervalo para seus intervalos de histograma e, para cada intervalo, contabilizar o número de pixels com uma cor nesse intervalo. Por exemplo, considere o histograma "verde" e suponha que escolhamos 4 intervalos para o histograma: 0-63, 64-127, 128-191 e 192-255. Em seguida, para cada pixel, examinamos o valor verde e adicionamos uma contagem ao intervalo apropriado. Quando terminamos a contagem, dividimos cada total de baldes pelo número de pixels em toda a imagem para obter um histograma normalizado para o canal verde.

Para o histograma da direção da textura, começamos realizando a detecção de bordas na imagem. Cada ponto da aresta possui um vetor normal apontando na direção perpendicular à aresta. Quantificamos o ângulo do vetor normal em um dos 6 intervalos entre 0 e PI (como as arestas têm simetria de 180 graus, convertemos ângulos entre -PI e 0 para estar entre 0 e PI). Depois de calcular o número de pontos da borda em cada direção, temos um histograma não normalizado representando a direção da textura, que normalizamos dividindo cada intervalo pelo número total de pontos da borda na imagem.

Para calcular o histograma da escala de textura, para cada ponto de borda, medimos a distância até o próximo ponto de borda mais próximo com a mesma direção. Por exemplo, se o ponto de extremidade A tem uma direção de 45 graus, o algoritmo caminha nessa direção até encontrar outro ponto de extremidade com uma direção de 45 graus (ou dentro de um desvio razoável). Depois de calcular essa distância para cada ponto de extremidade, despejamos esses valores em um histograma e o normalizamos dividindo pelo número total de pontos de extremidade.

Agora você tem 5 histogramas para cada imagem. Para comparar duas imagens, você pega o valor absoluto da diferença entre cada intervalo de histograma e depois soma esses valores. Por exemplo, para comparar as imagens A e B, calcularíamos

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 

para cada balde no histograma verde, repita para os outros histogramas e depois resuma todos os resultados. Quanto menor o resultado, melhor a correspondência. Repita o procedimento para todas as imagens no banco de dados e a partida com o menor resultado vence. Você provavelmente desejaria ter um limite acima do qual o algoritmo conclua que nenhuma correspondência foi encontrada.

Terceira escolha - pontos-chave + árvores de decisão

Uma terceira abordagem, provavelmente muito mais rápida que as outras duas, está usando florestas de textos semânticas (PDF). Isso envolve extrair pontos-chave simples e usar árvores de decisão de coleção para classificar a imagem. Isso é mais rápido que a simples correspondência de pontos-chave do SIFT, porque evita o processo caro de correspondência, e os pontos-chave são muito mais simples que o SIFT, portanto, a extração do ponto-chave é muito mais rápida. No entanto, preserva a invariância do método SIFT em rotação, escala e iluminação, um recurso importante que o método de histograma não possuía.

Atualização :

Meu erro - o jornal Florestas Semânticas de Textos não se refere especificamente à correspondência de imagens, mas à rotulagem regional. O artigo original que corresponde é este: Reconhecimento de ponto-chave usando árvores aleatórias . Além disso, os trabalhos abaixo continuam a desenvolver as idéias e representam o estado da arte (c. 2010):

• Reconhecimento rápido de pontos-chave usando samambaias aleatórias - mais rápido e escalonável que o Lepetit 06
• RESUMO: Recursos elementares independentes robustos binários - menos robustos, mas muito rápidos - acho que o objetivo aqui é a correspondência em tempo real em smartphones e outros dispositivos portáteis

O melhor método que conheço é usar um Hash Perceptual. Parece haver uma boa implementação de código aberto desse hash disponível em:

http://phash.org/

A idéia principal é que cada imagem seja reduzida a um pequeno código de hash ou 'impressão digital', identificando recursos destacados no arquivo de imagem original e misturando uma representação compacta desses recursos (em vez de mesclar os dados da imagem diretamente). Isso significa que a taxa de falsos positivos é muito reduzida em relação a uma abordagem simplista, como reduzir imagens para uma imagem minúscula do tamanho de uma impressão digital e comparar impressões digitais.

phash oferece vários tipos de hash e pode ser usado para imagens, áudio ou vídeo.

Este post foi o ponto de partida da minha solução, com muitas boas idéias aqui, então eu gostaria de compartilhar meus resultados. O principal insight é que eu encontrei uma maneira de contornar a lentidão da correspondência de imagens com base em pontos-chave, explorando a velocidade do phash.

Para a solução geral, é melhor empregar várias estratégias. Cada algoritmo é mais adequado para certos tipos de transformação de imagem e você pode tirar vantagem disso.

No topo, os algoritmos mais rápidos; na parte inferior, o mais lento (embora mais preciso). Você pode pular os mais lentos se uma boa correspondência for encontrada no nível mais rápido.

• baseado em hash de arquivo (md5, sha1, etc) para duplicatas exatas
• hash perceptivo (phash) para imagens redimensionadas
• baseado em recursos (SIFT) para imagens modificadas

Estou tendo resultados muito bons com o phash. A precisão é boa para imagens redimensionadas. Não é bom para imagens (perceptivamente) modificadas (cortadas, giradas, espelhadas, etc). Para lidar com a velocidade do hash, devemos empregar um cache / banco de dados em disco para manter os hashes do palheiro.

O mais interessante sobre o phash é que, depois de criar seu banco de dados de hash (que para mim é de cerca de 1000 imagens / s), as pesquisas podem ser muito, muito rápidas, principalmente quando você pode armazenar todo o banco de dados de hash na memória. Isso é bastante prático, pois um hash é de apenas 8 bytes.

Por exemplo, se você tiver 1 milhão de imagens, será necessário um array de 1 milhão de valores de hash de 64 bits (8 MB). Em algumas CPUs, isso se encaixa no cache L2 / L3! Em uso prático, vi um Corei7 comparar a mais de 1 Giga-hamm / s; é apenas uma questão de largura de banda de memória para a CPU. Um banco de dados de 1 bilhão de imagens é prático em uma CPU de 64 bits (é necessário 8 GB de RAM) e as pesquisas não excederão 1 segundo!

Para imagens modificadas / cortadas, parece que um recurso / detector de ponto-chave invariável à transformação, como o SIFT, é o caminho a percorrer. O SIFT produzirá bons pontos-chave que detectarão cortar / girar / espelhar etc. No entanto, a comparação do descritor é muito lenta em comparação com a distância de hamming usada pelo phash. Essa é uma grande limitação. Há muitas comparações a serem feitas, pois o descritor IxJxK máximo se compara à pesquisa de uma imagem (I = número de imagens do palheiro, J = pontos-chave de destino por imagem do palheiro, K = pontos-chave de destino por imagem da agulha).

Para contornar o problema de velocidade, tentei usar phash em torno de cada ponto-chave encontrado, usando o tamanho / raio do recurso para determinar o sub-retângulo. O truque para fazer isso funcionar bem é aumentar / diminuir o raio para gerar diferentes níveis sub-retos (na imagem da agulha). Normalmente, o primeiro nível (sem escala) corresponderá, no entanto, muitas vezes são necessários mais alguns. Não sei ao certo por que isso funciona, mas posso imaginar que ele permita recursos muito pequenos para o phash funcionar (o phash reduz as imagens para 32x32).

Outra questão é que o SIFT não distribuirá os pontos-chave de maneira ideal. Se houver uma seção da imagem com muitas arestas, os pontos-chave se agruparão ali e você não encontrará nenhum em outra área. Estou usando o GridAdaptedFeatureDetector no OpenCV para melhorar a distribuição. Não tenho certeza de qual tamanho de grade é melhor, estou usando uma grade pequena (1x3 ou 3x1, dependendo da orientação da imagem).

Você provavelmente deseja dimensionar todas as imagens do palheiro (e agulha) para um tamanho menor antes da detecção de recurso (eu uso 210px na dimensão máxima). Isso reduzirá o ruído na imagem (sempre um problema para os algoritmos de visão computacional), além de focar o detector em recursos mais importantes.

Para imagens de pessoas, você pode tentar a detecção de rosto e usá-lo para determinar o tamanho da imagem a ser dimensionado e o tamanho da grade (por exemplo, o maior rosto dimensionado para 100px). O detector de recursos é responsável por vários níveis de escala (usando pirâmides), mas há uma limitação de quantos níveis ele usará (é possível ajustar isso, é claro).

O detector de ponto-chave provavelmente está funcionando melhor quando retorna menos do que o número de recursos que você queria. Por exemplo, se você pedir 400 e receber 300 de volta, isso é bom. Se você receber 400 de volta todas as vezes, provavelmente alguns recursos bons precisariam ser deixados de fora.

A imagem da agulha pode ter menos pontos-chave que as imagens do palheiro e ainda assim obter bons resultados. Adicionar mais não significa necessariamente grandes ganhos, por exemplo, com J = 400 e K = 40, minha taxa de acerto é de cerca de 92%. Com J = 400 e K = 400, a taxa de acerto apenas sobe para 96%.

Podemos tirar proveito da velocidade extrema da função hamming para resolver escala, rotação, espelhamento, etc. Uma técnica de múltiplas passagens pode ser usada. Em cada iteração, transforme os sub-retângulos, re-hash e execute a função de pesquisa novamente.

Como cartman apontou, você pode usar qualquer tipo de valor de hash para encontrar duplicatas exatas.

Um ponto de partida para encontrar imagens próximas pode estar aqui . Esta é uma ferramenta usada pelas empresas de computação gráfica para verificar se as imagens renovadas ainda estão mostrando essencialmente a mesma cena.

Eu tenho uma ideia, que pode funcionar e é muito provável que seja muito rápida. Você pode fazer uma amostra secundária de uma imagem com resolução de 80x60 ou comparável e convertê-la em escala de cinza (após a subamostragem, será mais rápida). Processe as duas imagens que você deseja comparar. Em seguida, execute a soma normalizada das diferenças ao quadrado entre duas imagens (a imagem de consulta e cada uma do banco de dados), ou ainda melhor Correlação cruzada normalizada, que fornece uma resposta mais próxima de 1, se as duas imagens forem semelhantes. Se as imagens forem semelhantes, você poderá prosseguir para técnicas mais sofisticadas para verificar se são as mesmas imagens. Obviamente, esse algoritmo é linear em termos de número de imagens em seu banco de dados, mesmo que seja muito rápido até 10000 imagens por segundo no hardware moderno. Se você precisar de invariância à rotação, um gradiente dominante pode ser calculado para esta pequena imagem, e então todo o sistema de coordenadas pode ser rotacionado para a orientação canônica; porém, isso será mais lento. E não, não há invariância para escalar aqui.

Se você quiser algo mais geral ou usar grandes bancos de dados (milhões de imagens), precisará investigar a teoria de recuperação de imagens (muitos documentos apareceram nos últimos 5 anos). Existem alguns indicadores em outras respostas. Mas pode ser um exagero, e a abordagem do histograma sugerido fará o trabalho. Embora eu ache que a combinação de muitas abordagens rápidas diferentes será ainda melhor.

Minha empresa tem cerca de 24 milhões de imagens provenientes de fabricantes todos os meses. Eu estava procurando uma solução rápida para garantir que as imagens que carregamos em nosso catálogo sejam novas .

Quero dizer que pesquisei na Internet em toda parte para tentar encontrar uma solução ideal. Eu até desenvolvi meu próprio algoritmo de detecção de borda.
Avaliei a velocidade e a precisão de vários modelos. Minhas imagens, com fundo branco, funcionam extremamente bem com o phashing. Como redcalx disse, eu recomendo phash ou ahash. NÃO use hash MD5 ou outros hashes criptográficos. A menos que você deseje apenas correspondências EXACT da imagem. Qualquer redimensionamento ou manipulação que ocorra entre as imagens produzirá um hash diferente.

Para phash / ahash, verifique isto: imagehash

Eu queria estender a postagem de * redcalx publicando meu código e minha precisão.

O que eu faço:

from PIL import Image
from PIL import ImageFilter
import imagehash

img1=Image.open(r"C:\yourlocation")
img2=Image.open(r"C:\yourlocation")
if img1.width<img2.width:
    img2=img2.resize((img1.width,img1.height))
else:
    img1=img1.resize((img2.width,img2.height))
img1=img1.filter(ImageFilter.BoxBlur(radius=3))
img2=img2.filter(ImageFilter.BoxBlur(radius=3))
phashvalue=imagehash.phash(img1)-imagehash.phash(img2)
ahashvalue=imagehash.average_hash(img1)-imagehash.average_hash(img2)
totalaccuracy=phashvalue+ahashvalue

Aqui estão alguns dos meus resultados:

item1  item2  totalsimilarity
desk1  desk1       3
desk1  phone1     22
chair1 desk1      17
phone1 chair1     34

Espero que isto ajude!

Acredito que reduzir o tamanho da imagem para quase o tamanho de um ícone, digamos 48x48, depois converter para escala de cinza e, em seguida, calcular a diferença entre pixels, ou Delta, deve funcionar bem. Como estamos comparando a alteração na cor do pixel, e não na cor real do pixel, não importa se a imagem é um pouco mais clara ou mais escura. Grandes alterações serão importantes, pois os pixels que ficarem muito claros / escuros serão perdidos. Você pode aplicar isso em uma linha ou quantas quiser para aumentar a precisão. No máximo, você teria 47x47 = 2.209 subtrações a serem feitas para formar uma chave comparável.

Escolher 100 pontos aleatórios pode significar que imagens semelhantes (ou ocasionalmente até diferentes) serão marcadas da mesma forma, o que suponho que não seja o que você deseja. Os hashes MD5 não funcionariam se as imagens tivessem formatos diferentes (png, jpeg etc.), tivessem tamanhos diferentes ou tivessem metadados diferentes. Reduzir todas as imagens para um tamanho menor é uma boa aposta, fazer uma comparação pixel por pixel não deve demorar muito, desde que você esteja usando uma boa biblioteca de imagens / linguagem rápida, e o tamanho seja pequeno o suficiente.

Você pode tentar diminuí-los e, se forem iguais, faça outra comparação em um tamanho maior - pode ser uma boa combinação de velocidade e precisão ...

Se você tiver um grande número de imagens, procure um filtro Bloom , que usa vários hashes para um resultado probablístico, mas eficiente. Se o número de imagens não for grande, um hash criptográfico como md5 deve ser suficiente.