comparação de imagem - algoritmo rápido

https://stackoverflow.com/questions/843972

20-08-2019
|

Pergunta

Eu estou olhando para criar uma tabela de base de imagens e então comparar quaisquer novas imagens contra que para determinar se a nova imagem é uma exata (ou próximo) duplicado da base.

Por exemplo: se você quiser reduzir o armazenamento da mesma imagem 100 vezes, você pode armazenar uma cópia do mesmo e fornecer links de referência para ele. Quando uma nova imagem é introduzido você deseja comparar com uma imagem existente para se certificar de que não é uma duplicata ... idéias?

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

Solução

A seguir estão três abordagens para resolver este problema (e há muitos outros).

A primeira é uma abordagem padrão em visão computacional, correspondência ponto-chave. Isso pode exigir algum conhecimento de implementar, e pode ser lento.
O segundo método usa apenas processamento de imagem elementar, e é potencialmente mais rápido do que a primeira abordagem, e é simples de implementar. No entanto, o que ele ganha em compreensibilidade, que falta em robustez -. Correspondência falha em escala, girada ou imagens descoloridos
O terceiro método é rápido e robusto, mas é potencialmente o mais difícil de implementar.

Keypoint Matching

Melhor do que pegar 100 pontos aleatórios é escolher 100 importantes pontos. Certas partes de uma imagem tem mais informação do que os outros (especialmente nas bordas e cantos), e estes são os que você deseja usar para a correspondência de imagem inteligente. Google " keypoint extração " e " keypoint matching" e você encontrará muito poucos trabalhos acadêmicos sobre o assunto. Estes dias, SIFT keypoints são, indiscutivelmente, o mais popular, uma vez que podem corresponder imagens sob diferentes escalas , rotações, e iluminação. Algumas implementações SIFT pode ser encontrada aqui .

Uma desvantagem para correspondência de ponto-chave é o tempo de funcionamento de uma implementação simples: O (n ^ 2m), onde n é o número de pontos chave em cada imagem, e m é o número de imagens no banco de dados. Alguns algoritmos inteligentes pode encontrar o par mais próximo mais rápido, como quadtrees ou binário particionamento espaço.

Solução Alternativa: método Histograma

Outra solução menos robusta, mas potencialmente mais rápido é a função Criar histogramas para cada imagem, e escolher a imagem com o histograma mais próximo histograma da imagem de entrada. I implementado este como uma graduação, e nós usado 3 histogramas de cor (vermelho, verde e azul), e dois histogramas textura, direção e escala. Eu vou dar os detalhes abaixo, mas gostaria de salientar que isso só funcionou bem para imagens combinando muito semelhante às imagens de banco de dados. Re-escalado, girada ou imagens descoloridos pode falhar com este método, mas pequenas mudanças como corte não vai quebrar o algoritmo

Computing os histogramas de cor é simples - basta escolher o intervalo para seus baldes histograma, e para cada faixa, contagem do número de pixels com uma cor nesse intervalo. Por exemplo, considere o histograma "verde", e suponha que nós escolhemos 4 baldes para a nossa histograma: 0-63, 64-127, 128-191 e 192-255. Então, para cada pixel, olhamos para o valor verde, e adicionar um registro para o balde apropriado. Quando terminar de contagem, dividimos o total de cada balde pelo número de pixels em toda a imagem para obter um histograma normalizado para o canal verde.

Para o histograma sentido textura, começámos por realizar a detecção de bordas na imagem. Cada ponto de extremidade tem um apontador normal de vector na direcção perpendicular à aresta. Nós quantizado ângulo do vetor normal em uma das 6 baldes entre 0 e PI (desde arestas têm simetria de 180 graus, nós convertemos ângulos entre -PI e 0 a estar entre 0 e PI). Após calculando o número de pontos do bordo em cada sentido, temos um histograma un-normalizado que representa textura direcção, que nós normalizado dividindo cada balde pelo número total de pontos do bordo na imagem.

Para calcular o histograma escala textura, para cada ponto de vantagem, medimos a distância até o ponto de borda próxima mais próximo com a mesma direção. Fou exemplo, se o ponto de borda A tem uma direcção de 45 graus, o algoritmo anda em que direcção até que encontre outro ponto de extremidade com uma orientação de 45 graus (ou dentro de um desvio razoável). Depois de calcular esta distância para cada ponto de extremidade, nós despejar esses valores em um histograma e normalizá-lo dividindo pelo número total de pontos de borda.

Agora você tem 5 histogramas para cada imagem. Para comparar duas imagens, você toma o valor absoluto da diferença entre cada balde histograma, e em seguida, soma desses valores. Por exemplo, para comparar imagens A e B, que calcularia

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

para cada balde no histograma verde, e repita para os outros histogramas, e, em seguida, soma-se todos os resultados. Quanto menor for o resultado, melhor o jogo. Repita o procedimento para todas as imagens no banco de dados, e a partida com as vitórias de resultados menores. Você provavelmente vai querer ter um limite, acima do qual o algoritmo conclui que nenhuma correspondência foi encontrada.

Third Choice - Keypoints + Árvores de Decisão

Uma terceira abordagem que é, provavelmente, muito mais rápido do que os outros dois está usando semântica texton florestas (PDF). Isso envolve a extração keypoints simples e usando um árvores coleção de decisão para classificar a imagem. Isso é mais rápido do que simples correspondência SIFT ponto chave, porque evita o processo de correspondência caro, e keypoints são muito mais simples do que SIFT, para que a extração ponto-chave é muito mais rápido. No entanto, ele preserva invariância do método SIFT à rotação, escala e iluminação, uma característica importante que o método histograma faltava.

Atualizar :

O meu erro - Semântica texton Florestas papel não é especificamente sobre a correspondência de imagem, mas sim rotulagem região. O documento original que faz correspondência é este: Keypoint Reconhecimento usando Randomized Árvores . Além disso, os papéis abaixo de continuar a desenvolver as ideias e representam o estado da arte (c 2,010.):

Reconhecimento rápido Keypoint usando aleatória Ferns - mais rápido e mais escalável do que Lepetit 06
~~BREVE: Binary Robust Elementary Independent Features~~ - menos robusta, mas muito rápido - Eu acho que o objetivo aqui é em tempo real correspondência em telefones inteligentes e outros dispositivos portáteis

Outras dicas

O melhor método que conheço é usar um Perceptual Hash. Parece haver uma boa implementação open source de um tal de hash disponível em:

http://phash.org/

A idéia principal é que cada imagem é reduzido a um pequeno código hash ou 'impressão digital', identificando características marcantes no arquivo de imagem original e hashing uma representação compacta desses recursos (em vez de hash dos dados de imagem diretamente). Isto significa que a taxa de falsos positivos é muito reduzido sobre uma abordagem simplista como a redução de imagens até uma imagem de tamanho minúsculo impressão digital e comparação de impressões digitais.

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

Este post foi o ponto da minha solução inicial, muitas boas idéias aqui para que eu que eu iria partilhar os meus resultados. A principal visão é que eu encontrei uma maneira de contornar a lentidão da correspondência de imagem baseada keypoint explorando a velocidade de phash.

Para a solução geral, é melhor empregar várias estratégias. Cada algoritmo é mais adequado para determinados tipos de transformações 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 ignorar os lentos se uma boa correspondência é encontrada no nível mais rápido.

file-hash com base (md5, sha1, etc) para cópias exatas
hash perceptual (phash) para imagens escalonados
baseada em recursos (SIFT) para imagens modificados

Eu estou tendo resultados muito bons com phash. A precisão é boa para imagens escalonados. Não é bom para imagens (perceptually) modificados (colhido, rodados, espelhados, etc). Para lidar com a velocidade hashing devemos empregar um cache de disco / banco de dados para manter os hashes para o palheiro.

A coisa realmente agradável sobre phash é que uma vez que você construir seu banco de dados de hash (que para mim é de cerca de 1000 imagens / seg), as buscas podem ser muito, muito rápido, especialmente quando você pode segurar todo o banco de dados de hash na memória . Isto é bastante prático, uma vez um hash é apenas 8 bytes.

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

Para modificada / cropped imagens parece uma característica transformar-invariante / detector de ponto-chave como SIFT é o caminho a percorrer. SIFT vai produzir bons keypoints que detectarão cultura / rotação / espelho etc. No entanto, o descritor de comparar é muito lento em comparação com distância de Hamming usado por phash. Esta é uma limitação importante. Há um monte de se compara a fazer, uma vez que existem descritor máxima IxJxK compara a pesquisa de uma imagem (I = num palheiro imagens, J = alvo keypoints imagem palheiro por, K = keypoints alvo imagem Agulha por).

Para contornar a questão da velocidade, eu tentei usar phash em torno de cada ponto-chave encontrada, usando a dimensão do traço / raio para determinar a sub-retângulo. O truque para fazer este trabalho bem, é crescer / diminuir o raio para gerar diferentes níveis sub-rect (na imagem da agulha). Normalmente, o primeiro nível (sem escala) irá corresponder no entanto, muitas vezes é preciso um mais alguns. Eu não estou 100% certo por que isso funciona, mas posso imaginar que permite funcionalidades que são muito pequenas para phash ao trabalho (imagens escalas phash até 32x32).

Outra questão é que SIFT não vai distribuir os pontos-chave de forma otimizada. Se houver uma seção da imagem com um monte de bordas as keypoints vai se aglomeram lá e você não vai obter qualquer em outra área. Eu estou usando o GridAdaptedFeatureDetector em OpenCV para melhorar a distribuição. Não tenho certeza o tamanho da grade é melhor, estou usando uma pequena grade (1x3 ou 3x1, dependendo da orientação da imagem).

Você provavelmente vai querer escalar todas as imagens palheiro (e agulha) para um tamanho menor antes de detecção de recurso (eu uso 210px junto dimensão máxima). Isto irá reduzir o ruído na imagem (sempre um problema para algoritmos de visão de computador), também se concentrará detector de características mais proeminentes.

Para imagens de pessoas, você pode tentar a detecção de rosto e usá-lo para determinar o tamanho da imagem para escala de e para o tamanho da grade (por exemplo maior cara escalado para ser 100px). O detector recurso é responsável por vários níveis de escala (usando pirâmides), mas há uma limitação para o número de níveis que vai usar (esta é sintonizável é claro).

O detector de ponto-chave é provavelmente a trabalhar melhor quando ele retorna menos de tele número de recursos que você queria. Por exemplo, se você perguntar para 400 e obter 300 costas, isso é bom. Se você receber 400 volta cada vez, provavelmente algumas boas características tinha de ser deixado de fora.

A imagem da agulha pode ter menos pontos-chave do que as imagens palheiro e ainda obter bons resultados. Adicionando mais não significa necessariamente que você obtenha ganhos enormes, por exemplo com J = 400 e K = 40 minha taxa de sucesso é de cerca de 92%. Com J = 400 e K = 400 a taxa de acerto só vai até 96%.

Podemos tirar proveito da velocidade extrema da função Hamming para resolver escala, rotação, espelhamento etc. Uma técnica de passagem múltipla pode ser usado. Em cada iteração, transformar a sub-retângulos, re-hash e executar a função de busca novamente.

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

Um ponto de partida para encontrar imagens em close poderia ser aqui . Esta é uma ferramenta usada por empresas CG para verificar se as imagens renovada ainda estão mostrando essencialmente a mesma cena.

Eu tenho uma idéia, que pode trabalhar e é mais provável que ser muito rápido. Você pode sub-amostra de uma imagem para dizer 80x60 resolução ou comparáveis, e convertê-lo em escala de cinza (depois de subamostragem, será mais rápido). Processar ambas as imagens que você deseja comparar. Em seguida, executado soma normalizada de diferenças de quadrados entre duas imagens (a imagem-query e cada a partir do ter), ou ainda melhor correlação normalizada Cruz, que dá resposta mais próximo de 1, se ambas as imagens são semelhantes. Em seguida, se as imagens são semelhantes você pode avançar para técnicas mais sofisticadas para verificar que são as mesmas imagens. Obviamente, este algoritmo é linear em termos de número de imagens em seu banco de dados por isso mesmo que vai ser muito rápido até 10000 imagens por segundo no hardware moderno. Se você precisar de invariância de rotação, em seguida, um gradiente dominante pode ser computada para esta imagem pequeno, e então todo o sistema de coordenadas pode ser girada para canônica orientação, isso, porém, será mais lento. E não, não há nenhuma invariância de escala aqui.

Se você quiser algo mais geral ou usando bancos de dados grandes (milhões de imagens), então você precisa olhar para a teoria de recuperação de imagem (cargas de papéis apareceu nos últimos 5 anos). Há alguns ponteiros em outras respostas. Mas pode ser um exagero, eo sugerem histograma abordagem vai fazer o trabalho. Embora eu pensaria combinação de muitos diferentes se aproxima rápido será ainda melhor.

Eu acredito que diminuir o tamanho do baixo para quase ícone do tamanho, digamos, 48x48, em seguida, converter para tons de cinza, em seguida, tomando a diferença entre pixels, ou Delta, deve funcionar bem. Porque nós estamos comparando a mudança na cor do pixel, em vez da cor do pixel real, não importa se a imagem é um pouco mais clara ou mais escura. Grandes mudanças importa desde pixels ficando muito claro / escuro serão perdidos. Você pode aplicar isso em uma linha, ou como muitos como você gostaria de aumentar a precisão. No máximo, você teria 47x47 = 2.209 subtrações para fazer a fim de formar uma chave comparáveis.

Escolher 100 pontos aleatórios poderia significar que imagens semelhantes (ou ocasionalmente até mesmo diferentes) seria marcado como o mesmo, que eu suponho que não é o que você quer. hashes MD5 não funcionaria se as imagens eram diferentes formatos (PNG, JPEG, etc), teve diferentes tamanhos, ou tinham metadados diferente. Reduzir todas as imagens para um tamanho menor é uma boa aposta, fazendo uma comparação pixel pixel-para- não deve demorar muito, enquanto você estiver usando uma linguagem biblioteca de imagens bom / rápido, e o tamanho é pequeno o suficiente.

Você poderia tentar torná-los pequenos, em seguida, se eles são o mesmo executar outra comparação em um tamanho maior - poderia ser uma boa combinação de velocidade e precisão ...

Se você tem um grande número de imagens, olhar em um Bloom filtro, que utiliza múltiplas hashes para um resultado probablistic mas eficiente. Se o número de imagens não é enorme, então um hash criptográfico como md5 deve ser suficiente.

A minha empresa tem cerca de 24million imagens vêm de fabricantes de cada mês. Eu estava procurando por uma solução rápida para garantir que as imagens que envia para o nosso catálogo são new imagens.

Eu quero dizer que eu procurei na internet longe para tentar encontrar uma solução ideal. Eu mesmo desenvolvi meu próprio algoritmo de detecção de bordas.
I têm avaliado velocidade e precisão de vários modelos. Minhas imagens, que têm fundos brancos, trabalham muito bem com phashing. Como redcalx disse, eu recomendo phash ou ahash. NÃO uso hash MD5 ou de umas outras hashes criptográficos. A menos que, você quer apenas partidas imagem exata. Qualquer redimensionamento ou manipulação que ocorre entre as imagens irá produzir um hash diferente.

Para phash / ahash, vejam isto: imagehash

Eu queria estender redcalx * '* s pós por postar 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  totalaccuracy
desk1  desk2       3
desk2  phone1     22
chair1 desk1      17
phone1 chair1     34

onde o item representa o sujeito real da imagem e o número representa a escala de orientação.

Espero que isso ajude!

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow