Dados dois arquivos de imagem diferentes (em qualquer formato que eu escolher), preciso escrever um programa para prever a chance de uma cópia ilegal de outra. O autor da cópia pode fazer coisas como girar, tornar negativo ou adicionar detalhes triviais (além de alterar a dimensão da imagem).
Você conhece algum algoritmo para fazer esse tipo de trabalho?
algorithm
image
image-processing
image-recognition
Salvador Dalí
fonte
fonte
Respostas:
Estas são simplesmente idéias que tive pensando sobre o problema, nunca tentei, mas gosto de pensar em problemas como este!
Antes de você começar
Considere normalizar as imagens; se uma tiver uma resolução mais alta que a outra, considere a opção de que uma delas seja uma versão compactada da outra; portanto, reduzir a resolução poderá fornecer resultados mais precisos.
Considere digitalizar várias áreas prospectivas da imagem que possam representar partes ampliadas da imagem e várias posições e rotações. Começa a ficar complicado se uma das imagens é uma versão distorcida de outra, esses são os tipos de limitações que você deve identificar e comprometer.
O Matlab é uma excelente ferramenta para testar e avaliar imagens.
Testando os algoritmos
Você deve testar (no mínimo) um grande conjunto de dados de teste analisados em humanos, onde as correspondências são conhecidas com antecedência. Se, por exemplo, nos seus dados de teste você tiver 1.000 imagens, das quais 5% correspondem, agora você tem uma referência razoavelmente confiável. Um algoritmo que encontra 10% de positivos não é tão bom quanto aquele que encontra 4% de positivos em nossos dados de teste. No entanto, um algoritmo pode encontrar todas as correspondências, mas também possui uma alta taxa de falsos positivos de 20%, portanto, existem várias maneiras de classificar seus algoritmos.
Os dados do teste devem tentar ser projetados para cobrir o maior número possível de dinâmicas que você esperaria encontrar no mundo real.
É importante notar que cada algoritmo para ser útil deve ter um desempenho melhor do que a estimativa aleatória, caso contrário, é inútil para nós!
Você pode aplicar seu software no mundo real de maneira controlada e começar a analisar os resultados que produz. Esse é o tipo de projeto de software que pode continuar infinitamente; sempre há ajustes e melhorias que você pode fazer; é importante ter isso em mente ao projetá-lo, pois é fácil cair na armadilha do projeto interminável.
Baldes de cor
Com duas fotos, digitalize cada pixel e conte as cores. Por exemplo, você pode ter os 'buckets':
(Obviamente, você teria uma resolução mais alta de contadores). Toda vez que você encontra um pixel 'vermelho', aumenta o contador vermelho. Cada balde pode ser representativo do espectro de cores, quanto maior a resolução, mais precisa, mas você deve experimentar uma taxa de diferença aceitável.
Depois de ter seus totais, compare-os com os totais para uma segunda imagem. Você pode achar que cada imagem tem uma pegada bastante única, suficiente para identificar correspondências.
Detecção de borda
Que tal usar a detecção de borda . (fonte: wikimedia.org )
Com duas imagens semelhantes, a detecção de borda deve fornecer uma pegada exclusiva utilizável e bastante confiável.
Tire as duas fotos e aplique a detecção de borda. Talvez meça a espessura média das bordas e depois calcule a probabilidade de a imagem poder ser dimensionada e redimensione, se necessário. Abaixo está um exemplo de um filtro Gabor aplicado (um tipo de detecção de borda) em várias rotações.
Compare as imagens pixel por pixel, conte as correspondências e as não correspondências. Se eles estiverem dentro de um certo limite de erro, você terá uma correspondência. Caso contrário, você pode tentar reduzir a resolução até um certo ponto e ver se a probabilidade de uma correspondência aumenta.
Regiões de Interesse
Algumas imagens podem ter segmentos / regiões de interesse distintos. Essas regiões provavelmente contrastam muito com o restante da imagem e são um bom item para procurar nas outras imagens para encontrar correspondências. Veja esta imagem, por exemplo:
(fonte: meetthegimp.org )
O trabalhador da construção civil em azul é uma região de interesse e pode ser usado como um objeto de pesquisa. Provavelmente, existem várias maneiras de extrair propriedades / dados dessa região de interesse e usá-los para pesquisar seu conjunto de dados.
Se você tiver mais de 2 regiões de interesse, poderá medir as distâncias entre elas. Veja este exemplo simplificado:
(fonte: per2000.eu )
Temos três regiões de interesse claras. A distância entre a região 1 e 2 pode ser de 200 pixels, entre 1 e 3 400 pixels e 2 e 3 200 pixels.
Pesquise outras imagens em regiões de interesse semelhantes, normalize os valores da distância e veja se você tem correspondências em potencial. Essa técnica pode funcionar bem para imagens rotacionadas e em escala. Quanto mais regiões de interesse você tiver, maior a probabilidade de uma correspondência à medida que cada medição de distância corresponder.
É importante pensar no contexto do seu conjunto de dados. Se, por exemplo, seu conjunto de dados for arte moderna, as regiões de interesse funcionarão muito bem, pois as regiões de interesse provavelmente foram projetadas para serem uma parte fundamental da imagem final. Se, no entanto, você estiver lidando com imagens de canteiros de obras, as regiões de interesse podem ser interpretadas pela copiadora ilegal como feias e podem ser cortadas / editadas livremente. Lembre-se de recursos comuns do seu conjunto de dados e tente explorar esse conhecimento.
Transformando
Transformar duas imagens é o processo de transformar uma imagem na outra através de um conjunto de etapas:
Observe que isso é diferente de desvanecer uma imagem em outra!
Existem muitos pacotes de software que podem transformar imagens. É tradicionalmente usado como efeito de transição, duas imagens não se transformam em algo a meio caminho geralmente, uma extrema se transforma em outra como resultado final.
Por que isso poderia ser útil? Dependendo do algoritmo de morphing usado, pode haver uma relação entre similaridade de imagens e alguns parâmetros do algoritmo de morphing.
Em um exemplo bastante simplificado, um algoritmo pode ser executado mais rapidamente quando houver menos alterações a serem feitas. Sabemos então que há uma probabilidade maior de que essas duas imagens compartilhem propriedades entre si.
Essa técnica pode funcionar bem para todos os tipos de imagens rotacionadas, distorcidas, distorcidas, com zoom. Novamente, essa é apenas uma idéia que tive, e não é baseada em nenhuma academia pesquisada até onde eu saiba (embora não pareça difícil), portanto pode ser muito trabalho para você com resultados limitados / sem resultados.
Fechando
A resposta de Ow nesta pergunta é excelente, lembro-me de ler sobre esse tipo de técnica de estudo de IA. É bastante eficaz na comparação de corpus lexicons.
Uma otimização interessante ao comparar corpus é que você pode remover palavras consideradas muito comuns, por exemplo 'The', 'A', 'And' etc. Essas palavras diluem nosso resultado. Queremos descobrir qual a diferença entre os dois corpus. para que eles possam ser removidos antes do processamento. Talvez haja sinais comuns semelhantes nas imagens que poderiam ser removidos antes da compactação? Pode valer a pena investigar.
A taxa de compactação é uma maneira muito rápida e razoavelmente eficaz de determinar como dois conjuntos de dados são semelhantes. Lendo sobre como a compactação funciona , você terá uma boa idéia de por que isso pode ser tão eficaz. Para um algoritmo de lançamento rápido, isso provavelmente seria um bom ponto de partida.
Transparência
Novamente, não tenho certeza de como os dados de transparência são armazenados para determinados tipos de imagem, gif png etc., mas isso pode ser extraído e serviria como um corte simplificado e eficaz para comparar com a transparência dos conjuntos de dados.
Inversão de sinais
Uma imagem é apenas um sinal. Se você tocar um ruído de um alto-falante e tocar outro ruído em outro alto-falante em perfeita sincronia no mesmo volume, eles se cancelam.
(fonte: themotorreport.com.au )
Inverta as imagens e adicione-as à sua outra imagem. Dimensione as posições it / loop repetidamente até encontrar uma imagem resultante em que um número suficiente de pixels seja branco (ou preto? Vou me referir a ela como uma tela neutra) para fornecer uma correspondência positiva ou parcial.
No entanto, considere duas imagens iguais, exceto uma que tem um efeito de brilho aplicado a ela:
(fonte: mcburrz.com )
Inverter um deles e adicioná-lo ao outro não resultará em uma tela neutra que é o nosso objetivo. No entanto, ao comparar os pixels das duas imagens originais, podemos ver claramente uma relação clara entre as duas.
Não estudei cores há alguns anos e não tenho certeza se o espectro de cores está em uma escala linear, mas se você determinou o fator médio de diferença de cores entre as duas imagens, poderá usar esse valor para normalizar os dados antes de processar com essa técnica.
Estruturas de dados em árvore
No começo, eles não parecem adequados para o problema, mas acho que eles poderiam funcionar.
Você pode pensar em extrair certas propriedades de uma imagem (por exemplo, compartimentos de cores) e gerar uma árvore de Huffman ou uma estrutura de dados semelhante. Você pode comparar duas árvores por similaridade. Isso não funcionaria bem para dados fotográficos, por exemplo, com um amplo espectro de cores, mas desenhos animados ou outras imagens com cores reduzidas podem funcionar.
Provavelmente isso não funcionaria, mas é uma ideia. A estrutura de dados trie é ótima para armazenar léxicos, por exemplo, um dicionário de dicção . É uma árvore de prefixo. Talvez seja possível construir uma imagem equivalente a um léxico (novamente, só consigo pensar em cores) para construir um trio. Se você reduziu, digamos, uma imagem de 300 x 300 em quadrados de 5x5, decomponha cada quadrado de 5x5 em uma sequência de cores para criar um teste a partir dos dados resultantes. Se um quadrado 2x2 contiver:
Temos um código trie bastante exclusivo que estende 24 níveis, aumentando / diminuindo os níveis (IE, reduzindo / aumentando o tamanho do nosso sub-quadrado) pode gerar resultados mais precisos.
A comparação de três árvores deve ser razoavelmente fácil e pode fornecer resultados efetivos.
Mais ideias
Tropecei em um artigo interessante sobre a classificação de imagens de satélite , que descreve:
Pode valer a pena investigar essas medidas com mais detalhes, embora algumas delas não sejam relevantes para o seu conjunto de dados.
Outras coisas a considerar
Provavelmente, existem muitos artigos sobre esse tipo de coisa; portanto, a leitura de alguns deles deve ajudar, embora possam ser muito técnicos. É uma área extremamente difícil em computação, com muitas horas infrutíferas de trabalho gastas por muitas pessoas tentando fazer coisas semelhantes. Mantê-lo simples e desenvolver essas idéias seria o melhor caminho a percorrer. Deve ser um desafio razoavelmente difícil criar um algoritmo com uma taxa de correspondência melhor que aleatória e começar a melhorar isso realmente começa a ficar bastante difícil de alcançar.
Provavelmente, cada método precisaria ser testado e aprimorado, se você tiver alguma informação sobre o tipo de imagem que verificará, isso seria útil. Por exemplo, anúncios, muitos deles continham texto; portanto, o reconhecimento de texto seria uma maneira fácil e provavelmente muito confiável de encontrar correspondências, especialmente quando combinadas com outras soluções. Como mencionado anteriormente, tente explorar propriedades comuns do seu conjunto de dados.
Combinar medidas e técnicas alternativas, cada uma com um voto ponderado (dependendo de sua eficácia) seria uma maneira de criar um sistema que gere resultados mais precisos.
Se o emprego de múltiplos algoritmos, como mencionado no início desta resposta, for possível encontrar todos os positivos, mas com uma taxa de falsos positivos de 20%, seria interessante estudar as propriedades / pontos fortes / fracos de outros algoritmos, pois outro algoritmo pode ser eficaz na eliminação de falsos positivos retornados de outro.
Cuidado para não cair na tentativa de concluir o projeto sem fim, boa sorte!
fonte
Leia o artigo: Porikli, Fatih, Oncel Tuzel e Peter Meer. "Rastreamento de covariância usando atualização de modelo com base em médias em coletores Riemannianos". (2006) IEEE Computer Vision e reconhecimento de padrões.
Consegui detectar com êxito regiões sobrepostas em imagens capturadas de webcams adjacentes usando a técnica apresentada neste artigo. Minha matriz de covariância era composta por saídas de detecção de aspecto / borda Sobel, astuto e SUSAN, bem como os pixels originais em escala de cinza.
fonte
Uma ideia:
O passo 2 não é trivial. Em particular, pode ser necessário usar um algoritmo inteligente para encontrar o ponto-chave mais semelhante na outra imagem. Os descritores de pontos geralmente têm dimensões muito altas (como uma centena de parâmetros) e há muitos pontos a serem examinados. O kd-trees pode ser útil aqui, as pesquisas de hash não funcionam bem.
Variantes:
fonte
Na verdade, é muito menos simples do que parece :-) A sugestão de Nick é boa.
Para começar, lembre-se de que qualquer método de comparação que valha a pena funcionará convertendo as imagens em um formato diferente - um formato que facilita a seleção de recursos semelhantes. Geralmente, esse material não facilita muito a leitura ...
Um dos exemplos mais simples em que posso pensar é simplesmente usar o espaço de cores de cada imagem. Se duas imagens têm distribuições de cores altamente semelhantes, você pode ter certeza razoável de que elas mostram a mesma coisa. Pelo menos, você pode ter certeza suficiente para sinalizá-lo ou fazer mais testes. A comparação de imagens no espaço de cores também resistirá a coisas como rotação, redimensionamento e alguns cortes. Evidentemente, não resistirá a modificações pesadas da imagem ou a recolorir intensamente (e até mesmo uma simples mudança de matiz será um pouco complicada).
http://en.wikipedia.org/wiki/RGB_color_space
http://upvector.com/index.php?section=tutorials&subsection=tutorials/colorspace
Outro exemplo envolve algo chamado Transformação de Hough. Essa transformação decompõe essencialmente uma imagem em um conjunto de linhas. Você pode pegar algumas das linhas 'mais fortes' em cada imagem e ver se elas estão alinhadas. Você pode fazer algum trabalho extra para tentar compensar também a rotação e o dimensionamento - e, neste caso, como comparar algumas linhas é MUITO menos computacional do que fazer o mesmo com imagens inteiras - não será tão ruim.
http://homepages.inf.ed.ac.uk/amos/hough.html
http://rkb.home.cern.ch/rkb/AN16pp/node122.html
http://en.wikipedia.org/wiki/ Hough_transform
fonte
Na forma descrita por você, o problema é difícil. Você considera copiar, colar parte da imagem em outra imagem maior como cópia? etc.
Se você der um passo atrás, isso será mais fácil de resolver se você der marca d'água nas imagens mestras. Você precisará usar um esquema de marca d'água para incorporar um código à imagem. Para dar um passo atrás, ao contrário de algumas das abordagens de baixo nível (detecção de bordas etc.) sugeridas por algumas pessoas, um método de marca d'água é superior porque:
É resistente a ataques de processamento de sinal ► Aprimoramento de sinal - nitidez, contraste, etc. ► Filtragem - mediana, passa-baixo, passa-alto, etc. ► Ruído aditivo - Gaussiano, uniforme, etc. ► Compressão com perda - JPEG, MPEG, etc.
É resistente a ataques geométricos ► Transformações afins ► Redução de dados - corte, recorte, etc. ► Distorções locais aleatórias ► Distorção
Faça uma pesquisa sobre algoritmos de marca d'água e você estará no caminho certo para resolver seu problema. (Nota: você pode comparar seu método usando o conjunto de dados STIRMARK . É um padrão aceito para esse tipo de aplicativo.
fonte
Esta é apenas uma sugestão, pode não funcionar e estou preparado para ser chamado a isso.
Isso irá gerar falsos positivos, mas esperamos que não falsos negativos.
Redimensione as duas imagens para que elas tenham o mesmo tamanho (presumo que as proporções de larguras e comprimentos sejam as mesmas em ambas as imagens).
Compacte um bitmap de ambas as imagens com um algoritmo de compactação sem perdas (por exemplo, gzip).
Encontre pares de arquivos com tamanhos de arquivo semelhantes. Por exemplo, você pode classificar cada par de arquivos que você possui, de acordo com o tamanho dos arquivos e recuperar o X superior.
Como eu disse, isso definitivamente gerará falsos positivos, mas espero que não sejam falsos negativos. Você pode implementar isso em cinco minutos, enquanto o Porikil et. al. provavelmente exigiria um trabalho extenso.
fonte
Acredito que se você estiver disposto a aplicar a abordagem a todas as orientações possíveis e a versões negativas, um bom começo para o reconhecimento de imagens (com boa confiabilidade) é usar os autofaces: http://en.wikipedia.org/wiki/Eigenface
Outra idéia seria transformar as duas imagens em vetores de seus componentes. Uma boa maneira de fazer isso é criar um vetor que opere nas dimensões x * y (x sendo a largura da imagem e y a altura), com o valor de cada dimensão aplicado ao valor do pixel (x, y). Em seguida, execute uma variante de K-vizinhos mais próximos com duas categorias: correspondência e não correspondência. Se estiver suficientemente próximo da imagem original, ele se encaixará na categoria de correspondência, caso contrário, não será.
K vizinhos mais próximos (KNN) pode ser encontrado aqui, também existem outras boas explicações na web: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm
Os benefícios do KNN é que, quanto mais variantes você compara à imagem original, mais preciso o algoritmo se torna. A desvantagem é que você precisa de um catálogo de imagens para treinar o sistema primeiro.
fonte
Se você estiver disposto a considerar uma abordagem completamente diferente para detectar cópias ilegais de suas imagens, considere a marca d'água . (de 1.4)
Embora também seja um campo complexo, existem técnicas que permitem que as informações da marca d'água persistam através de uma alteração grosseira da imagem: (de 1.9)
é claro, o FAQ chama a implementação dessa abordagem: "... muito desafiador", mas se você obtiver sucesso, terá uma grande confiança de que a imagem é uma cópia ou não, em vez de uma probabilidade percentual.
fonte
Se você estiver executando o Linux, sugiro duas ferramentas:
align_image_stack do pacote hugin-tools - é um programa de linha de comando que pode corrigir automaticamente rotação, redimensionamento e outras distorções (principalmente para composição de fotografia HDR, mas também para quadros de vídeo e outros documentos). Mais informações: http://hugin.sourceforge.net/docs/manual/Align_image_stack.html
comparar a partir do pacote imagemagick - um programa que pode encontrar e contar a quantidade de pixels diferentes em duas imagens. Aqui está um tutorial interessante: http://www.imagemagick.org/Usage/compare/ uising o -fuzz N%, você pode aumentar a tolerância a erros. Quanto maior o N, maior a tolerância a erros para contar dois pixels da mesma forma.
align_image_stack deve corrigir qualquer deslocamento, para que o comando compare tenha a chance de detectar os mesmos pixels.
fonte