Correspondência de modelos

Você está aqui:Iniciar “Guia de visão mecânica” “Correspondência de modelos

Introdução

Correspondência de modelos é uma técnica de visão mecânica de alto nível que identifica as peças de uma imagem que correspondem a um modelo predefinido. Os algoritmos avançados de correspondência de modelos permitem encontrar ocorrências do modelo independentemente da sua orientação e brilho local.

Template Matching As técnicas de correspondência de modelos são flexíveis e relativamente simples de usar, o que as torna um dos métodos mais populares de localização de objectos. A sua aplicabilidade é limitada principalmente pelo poder computacional disponível, uma vez que a identificação de modelos grandes e complexos pode ser demorada.

Conceito

Template Matching techniques are expected to address the following need: provided a reference image of an object (the template image) and an image to be inspected (the input image) we want to identify all input image locations at which the object from the template image is present. Dependendo do problema específico em questão, podemos (ou não) querer identificar as ocorrências rotacionadas ou escalonadas.

Começaremos com uma demonstração de um método ingênuo de Correspondência de Templates, que é insuficiente para aplicações da vida real, mas ilustra o conceito central a partir do qual os algoritmos reais de Correspondência de Templates se originam. Depois disso vamos explicar como este método é aprimorado e estendido nas rotinas avançadas de Correspondência baseada em Grayscale-based Matching e Edge-based Matching.

Naive Template Matching

Imagine que vamos inspecionar uma imagem de um plug e nosso objetivo é encontrar seus pinos. É-nos fornecida uma imagem modelo representando o objecto de referência que procuramos e a imagem de entrada a ser inspeccionada.

Imagem do template	Imagem de entrada

Realizaremos a pesquisa real de uma forma bastante simples – posicionaremos o template sobre a imagem em todos os locais possíveis, e cada vez vamos calcular alguma medida numérica de semelhança entre o modelo e o segmento de imagem com o qual ele se sobrepõe atualmente. Finalmente vamos identificar as posições que produzem as melhores medidas de similaridade como as prováveis ocorrências do template.

Image Correlation

Um dos sub-problemas que ocorrem na especificação acima é o cálculo da medida de similaridade da imagem do template alinhado e do segmento sobreposto da imagem de entrada, que é equivalente ao cálculo de uma medida de similaridade de duas imagens de dimensões iguais. Esta é uma tarefa clássica, e uma medida numérica de similaridade de imagem é normalmente chamada de correlação de imagem.

Correlação cruzada

O método fundamental para calcular a correlação da imagem é o chamado cross-correlação, que é essencialmente uma simples soma de multiplicações em pares de valores de píxeis correspondentes das imagens.

Embora possamos notar que o valor de correlação parece de facto reflectir a semelhança das imagens a serem comparadas, o método de correlação cruzada está longe de ser robusto. O seu principal inconveniente é que é tendencioso por mudanças no brilho global das imagens – o brilho de uma imagem pode subir em flecha com outra imagem, mesmo que a segunda imagem não seja nada semelhante.

Correlação Cruzada Normalizada

Correlação cruzada normalizada é uma versão melhorada do método clássico de correlação cruzada que introduz duas melhorias em relação ao original:

• Os resultados são invariantes para as mudanças globais de brilho, i.e. O brilho consistente ou escurecimento de qualquer uma das imagens não tem efeito no resultado (isto é conseguido subtraindo o brilho médio da imagem de cada valor de pixel).
• O valor final da correlação é escalado para o intervalo, de modo que o NCC de duas imagens idênticas é igual a 1,0, enquanto que o NCC de uma imagem e sua negação é igual a -1,0,

Imagem de Correlação do Template

Deixe-nos voltar ao problema em questão. Tendo introduzido a Correlação Cruzada Normalizada – medida robusta de similaridade de imagem – agora somos capazes de determinar o quão bem o modelo se encaixa em cada uma das posições possíveis. Podemos representar os resultados numa forma de imagem, onde o brilho de cada pixel representa o valor NCC do template posicionado sobre este pixel (cor preta representando a correlação mínima de -1.0, cor branca representando a correlação máxima de 1.0).

Imagem do template	Imagem do template	Imagem do template	Imagem da correlação do template

Identificação de correspondências

Tudo o que precisa ser feito neste ponto é decidir quais os pontos da imagem de correlação do modelo que são bons o suficiente para serem considerados correspondências reais. Normalmente identificamos como correspondências as posições que (simultaneamente) representam a correlação do template:

• mais forte que algum valor limite predefinido (ou seja, mais forte que 0.5)
• máximo local (mais forte que a correlação do template nos pixels vizinhos)

Áreas de correlação do template acima de 0.75	Pontos de correlação de modelo localmente máxima	Pontos de correlação de modelo localmente máxima acima de 0,75

Resumo

É bastante fácil expressar o método descrito no Adaptive Vision Studio – precisaremos apenas de dois filtros incorporados. Vamos calcular a imagem de correlação do template usando o filtro ImageCorrelationImage, e então identificar as combinações usando ImageLocalMaxima – só precisamos definir o parâmetro inMinValue que irá cortar os máximos locais fracos dos resultados, como discutido na seção anterior.

Embora a técnica introduzida tenha sido suficiente para resolver o problema a ser considerado, podemos notar os seus importantes inconvenientes:

• As ocorrências de templates têm de preservar a orientação da imagem do template de referência.
• O método é ineficiente, uma vez que calcular a imagem de correlação de templates para imagens médias a grandes consome tempo.

Nas próximas secções discutiremos como estas questões estão a ser abordadas nas técnicas avançadas de correspondência de templates: Grayscale-based Matching e Edge-based Matching.

Grayscale-based Matching, Edge-based Matching

Grayscale-based Matching é um algoritmo avançado de Matching de templates que estende a ideia original de detecção de template baseado em correlação, aumentando a sua eficiência e permitindo a pesquisa de ocorrências de template independentemente da sua orientação. O Matching baseado em Edge melhora ainda mais este método ao limitar o cálculo às áreas de borda do objeto.

Nesta seção vamos descrever os detalhes intrínsecos de ambos os algoritmos. Na próxima seção (conjunto de ferramentas Filter) explicaremos como usar estas técnicas no Adaptive Vision Studio.

Image Pyramid

Image Pyramid é uma série de imagens, sendo cada imagem um resultado de downsampling (escala para baixo, pelo fator de dois, neste caso) do elemento anterior.

Nível 0 (imagem de entrada)	Nível 1	Nível 2

Processamento de pirâmides

Pirâmides de imagem podem ser aplicadas para aumentar a eficiência da correlação…baseado na detecção de modelos. A observação importante é que o modelo retratado na imagem de referência geralmente ainda é discernível após uma significativa diminuição da imagem (embora, naturalmente, detalhes finos sejam perdidos no processo). Portanto, podemos identificar os candidatos correspondentes na imagem da amostra reduzida (e, portanto, muito mais rápido de processar) no nível mais alto da nossa pirâmide, e depois repetir a pesquisa nos níveis inferiores da pirâmide, cada vez considerando apenas as posições do template que pontuaram no nível anterior.

Em cada nível da pirâmide precisaremos de uma imagem da amostra reduzida do template de referência, ou seja, tanto a pirâmide da imagem de entrada como a pirâmide da imagem do template devem ser calculadas.

Nível 0 (imagem de referência do modelo)	Nível 1	Nível 2

Grayscale-Matching based

Embora em algumas das aplicações a orientação dos objectos seja uniforme e fixa (como vimos no exemplo do plug), é frequentemente o caso de os objectos a detectar aparecerem rodados. Nos algoritmos de correspondência de modelos a busca clássica em pirâmide é adaptada para permitir a correspondência multi-ângulo, ou seja, a identificação de instâncias rotacionadas do modelo.

Isto é conseguido calculando não apenas uma pirâmide de imagem do modelo, mas um conjunto de pirâmides – uma para cada possível rotação do modelo. Durante a pesquisa da pirâmide na imagem de entrada o algoritmo identifica os pares (posição do template, orientação do template) em vez das únicas posições do template. De forma semelhante ao esquema original, em cada nível da pesquisa o algoritmo verifica apenas os pares (posição, orientação) que tiveram uma boa pontuação no nível anterior (ou seja, pareciam corresponder ao modelo na imagem de menor resolução).

Imagem do Template	Imagem de entrada	Resultados de multi-correspondência angular

A técnica de correspondência em pirâmide juntamente com a pesquisa multi-ângulo constituem o método de correspondência de modelos (Template Matching) baseado em Grayscale-.

Edge-based Matching

Edge-based Matching melhora o anteriormente discutido Grayscale-based Matching usando uma observação crucial – que a forma de qualquer objecto é definida principalmente pela forma das suas arestas. Portanto, em vez de combinar todo o template, poderíamos extrair suas bordas e combinar apenas os pixels próximos, evitando assim alguns cálculos desnecessários. Em aplicações comuns, a velocidade alcançada é geralmente significativa.

Acoplar bordas de objetos em vez de um objeto como um todo requer uma ligeira modificação do método de correspondência da pirâmide original: imagine que estamos combinando um objeto de cor uniforme posicionado sobre um fundo uniforme. Todos os pixels da borda do objeto teriam a mesma intensidade e o algoritmo original combinaria com o objeto em qualquer lugar onde houvesse blob suficientemente grande da cor apropriada, e isto claramente não é o que queremos alcançar. Para resolver este problema, no Matching baseado em Edge é a direção do gradiente (representado como uma cor no espaço HSV para fins ilustrativos) dos pixels de borda, e não a sua intensidade, que é correspondida.

Filter Toolset

Adaptive Vision Studio fornece um conjunto de filtros implementando o Matching baseado em Grayscale- e o Matching baseado em Edge. Para a lista dos filtros ver Template Matching filters.

Como a imagem do modelo tem de ser pré-processada antes da correspondência em pirâmide (precisamos de calcular as pirâmides da imagem do modelo para todas as rotações possíveis), os algoritmos são divididos em duas partes:

• Model Creation – nesta etapa as pirâmides da imagem do modelo são calculadas e os resultados são armazenados num modelo – objecto atómico representando todos os dados necessários para executar a correspondência em pirâmide.
• Matching – neste passo o modelo do modelo é usado para combinar o modelo na imagem de entrada.

Tal organização do processamento torna possível calcular o modelo uma vez e reutilizá-lo várias vezes.

Filtros disponíveis

Para ambos os métodos de Correspondência de Modelos são fornecidos dois filtros, um para cada etapa do algoritmo.

	Matching baseado em Grayscale-	Matching baseado em Edge
Criação de modelos:
Matching:

Por favor note que o uso dos filtros CreateGrayModel e CreateEdgeModel só será necessário em aplicações mais avançadas. Caso contrário é suficiente usar um único filtro do passo Correspondência e criar o modelo definindo o parâmetro inGrayModel ou inEdgeModel do filtro. Para mais informações consulte Criando Modelos para Correspondência de Modelos.

O principal desafio da aplicação da técnica de Correspondência de Modelos reside no ajuste cuidadoso dos parâmetros do filtro, em vez de projetar a estrutura do programa.

Advanced Application Schema

Existem vários tipos de aplicativos avançados, para os quais a interface gráfica interativa para a correspondência de modelos não é suficiente e o usuário precisa utilizar o filtro CreateGrayModel ou CreateEdgeModel diretamente. Por exemplo:

1. Quando a criação do modelo requer pré-processamento não trivial de imagens.
2. Quando precisamos de um array inteiro de modelos criados automaticamente a partir de um conjunto de imagens.
3. Quando o usuário final deve ser capaz de definir seus próprios templates na aplicação em tempo de execução (por exemplo, fazendo uma seleção em uma imagem de entrada).

Esquema 1: Criação de modelos em um programa separado

Para os casos 1 e 2 é aconselhável implementar a criação de modelos em um macrofiltro de tarefas separado,salvar o modelo em um arquivo AVDATA e então vincular esse arquivo à entrada do filtro correspondente no programa principal:

Criação de modelos:	Programa principal:

Quando este programa estiver pronto, você pode executar a tarefa “CreateModel” como um programa a qualquer momento que você quiser torecrear o modelo. O link para o arquivo de dados na entrada do filtro correspondente não precisa de nenhuma modificação então, porque este é apenas um link e o que está sendo alterado é apenas o arquivo no disco.

Schema 2: Dynamic Model Creation

Para o caso 3, quando o modelo tem que ser criado dinamicamente, tanto o filtro criador do modelo quanto o filtro correspondente têm que estar na mesma tarefa. O primeiro, entretanto, deve ser executado condicionalmente, quando um respectivo evento HMI é levantado (por exemplo, o usuário clica em um ImpulseButton ou faz alguma ação do mouse em uma VideoBox). Para representar o modelo, deve ser usado um registro do tipo EdgeModel? que irá armazenar o último modelo (outra opção é usar o filtro LastNotNil).Aqui está um exemplo de realização com o modelo sendo criado a partir de uma caixa pré-definida em uma imagem de entrada quando um botão é clicado no HMI:

Criação do Modelo

Altura da Pirâmide

O parâmetro inPyramidHeight determina o número de níveis da correspondência da pirâmide e deve ser definido para o maior número para o qual o modelo ainda é reconhecível no nível mais alto da pirâmide. Este valor deve ser selecionado através de experimentos interativos usando a saída de diagnóstico diagPatternPyramid (Grayscale-based Matching) ou diagEdgePyramid (Edge-based Matching).

No exemplo a seguir o valor inPyramidHeight de 4 seria muito alto (para ambos os métodos), já que a estrutura do modelo é totalmente perdida neste nível da pirâmide. Também o valor de 3 parece um pouco excessivo (especialmente no caso do Edge-based Matching), enquanto o valor de 2 seria definitivamente uma escolha segura.

	Nível 0	Nível 1	Nível 2	Nível 3	Nível 4
Casamento baseado em Grayscale- (diagPatternPyramid):					>
Edge-based Matching (diagEdgePyramid):	>

Angle Range

Os parâmetros inMinAngle, inMaxAngle determinam o intervalo de orientações do modelo que será considerado no processo de correspondência. Por exemplo (valores entre parênteses representam os pares de valores inMinAngle, inMaxAngle):

• (0.0, 360.0): todas as rotações são consideradas (valor padrão)
• (-15.0, 15.0): as ocorrências do template podem se desviar da orientação do template de referência no máximo em 15.0 graus (em cada direção)
• (0.0, 0.0): espera-se que as ocorrências do template preservem a orientação do template de referência

A ampla gama de possíveis orientações introduz uma quantidade significativa de overhead (tanto no uso da memória como no tempo de computação), por isso é aconselhável limitar a gama sempre que possível.

Configurações de detecção de bordas (somente Matching baseado em bordas)

O inEdgeMagnitudeThreshold, parâmetros do filtro CreateEdgeHysteresis do CreateEdgeModel determinam as configurações do limiar de histerese usado para detectar bordas na imagem do modelo. Quanto menor o valor do inEdgeMagnitudeThreshold, mais bordas serão detectadas na imagem do modelo. Estes parâmetros devem ser definidos para que todas as bordas significativas do modelo sejam detectadas e a quantidade de bordas redundantes (ruído) no resultado seja a mais limitada possível. Similarmente à altura da pirâmide, os limites de detecção de bordas devem ser selecionados através de experimentos interativos usando o diagEdgePyramid de saída de diagnóstico – desta vez precisamos olhar apenas para a imagem no nível mais baixo.

(15.0, 30.0) – quantidade excessiva de ruído	(40.0, 60.0) – OK	(60.0, 70.0) – bordas significativas perdidas

O filtro CreateEdgeModel não permitirá criar um modelo no qual não foram detectadas bordas no topo da pirâmide (o que significa que não só algumas bordas significativas foram perdidas, mas todas elas), produzindo um erro nesse caso. Sempre que isso acontecer, a altura da pirâmide, ou os limites das arestas, ou ambos, devem ser reduzidos.

Matching

O parâmetro inMinScore determina quão permissivo o algoritmo será na verificação dos candidatos de partida – quanto maior o valor, menos resultados serão retornados. Este parâmetro deve ser definido através de experimentos interativos para um valor suficientemente baixo para assegurar que todas as correspondências corretas serão retornadas, mas não muito mais baixas, pois um valor muito baixo torna o algoritmo mais lento e pode causar falsas correspondências nos resultados.

Tips and Best Practices

How to Select a Method?

Para a grande maioria das aplicações o método de Correspondência Baseada em Bordas será tanto mais robusto quanto mais eficiente do que a Correspondência Baseada em Grayscale-. Este último só deve ser considerado se o modelo a ser considerado tiver áreas de transição de cores suaves que não são definidas por bordas discerníveis, mas ainda assim devem ser combinadas.

Prévio: Ajuste da Forma

Próximo: Sistemas de coordenadas locais