Gerando Padrões: Análise de Sinais e Imagens

Visão Geral de Análise de Sinais Digitais, Filosofia Geral de Análise de Sinais Digitais e integração desta com Reconhecimento de Padrões

Na área da Visão Computacional e do Reconhecimento de Padrões em Imagens e Sinais Digitais, a verdade crua e dolorosa é que não existe um algoritmo de “Visão Computacional” genérico. A interpretação de padrões em imagens é um processo complexo e constituído de muitos passos. A interpretação de Imagens é realizada através de:

  • Um conjunto de algoritmos (filtros) para imagens, cuja natureza varia dependendo do que se quer identificar e do tipo de imagem trabalhado.
  • Esses algoritmos são encadeados em uma “pipeline de processamento”.
  • Serão sempre extremamente específicos para cada tarefa a ser realizada.
  • Variação grande. Conjunto de algoritmos a ser utilizado varia:
    • De acordo com a tarefa.
    • De acordo com as características da imagem.

Classificação dos Métodos: Domínios de Valor, Espaço e Freqüência

David Marr em seu clássico livro Vision: A Computational Investigation into the Human Representation and Processing of Visual Information, de 1982, lançou as bases para a classificação e sistematização dos métodos de reconhecimento de padrões e análise de imagens, postulando um processo em 4 passos de grau crescente de abstração na análise de uma imagem. Cada passo desse processo seria realizado por um ou mais algoritmos específicos. O ocnjunto de 4 etapas formaria então uma pipeline sequencial, que levaria da imagem sem significado a uma representação simbóilica do que interessa de seu conteúdo. Essas etapas são: (1) Filtragem e Preprocessamento, (2) Condicionamento, (3) Rotulação e (4) Modelagem e Interpretação.

  1. Filtering and Processing: Não são esperadas modificações profundas nas imagens, elas são apenas atenuadas ou melhoradas.
  2. Conditioning:  Espera-se que uma nova imagem seja gerada e possivelmente ainda a formata.
  3. Labeling:  Início da etapa de interpretação.
  4. Modeling Interpretation:  Classificação e Interpretação dos Dados: Tradução de descrições de estruturas da imagem realizadas anteriormente em linguagens ou esquemas de representação que possuam semântica no contexto de aplicação. Relacionada principalmente com esquemas que levam em consideração aspectos espaciais.

Além disso, podemos “enxergar” uma imagem de três pontos de vista ou “domínios” diferentes: (i) Valor, (ii) Espaço de Imagem e (iii) Freqüencia.  Se tomarmos estes 3 possíveis domínios dentro dos quais podemos interpretar os dados de uma imagem; podemos então cruzar estes dois esquemas de classificação e criar a tabela abaixo, que classifica e contextualiza as diversas famílias de algoritmos de processamento de imagens.

A última linha da tabela mostra se se espera uma transformação de uma imagem em outra imagem (I -> I), de uma imagem em uma modelo descritivo ou conjunto de parâmetros descritores (I -> M) ou então se se espera que haja a transformação de um modelo de descrição paramétrica de baixo nível para um modelo mais abstrat (M -> M).

Classificação de Métodos

Classificação de Métodos

Métodos no Domínio do Valor: Aritmética de Imagens, Thresholding, Histogramas

V1. Operações Matemáticas de imagem com operando escalarV1.1. Soma: Soma-se um escalar a cada pixel da imagem, aumentando sua intensidade.

V1.2. Multiplicação: Multiplica-se um escalar por cada pixel da imagem. Resultado é expresso em valor inteiro.

Resultados de ambos os métodos são truncados para o valor máximo de representação de pixel no tipo de imagem (no nosso caso 255).

V1.3. Subtração: Subtrai-se um escalar de cada pixel da imagem, reduzindo-se sua intensidade.

V1.4. Divisão inteira: Divide-se o valor de cada pixel da imagem por um escalar. Expressa-se o resultado como inteiro.

Resultados são expressos truncados ao valor mínimo de representação no tipo de imagem (em nosso caso 0).

Implementação: Operações Matemáticas de imagem com operando escalar

  • Um único programa implementa todo o conjunto V1.
  • Um parâmetro do tipo Símbolo define qual operação será realizada.

Exemplo:

mathescalar -i imagem.pgm -o iresult.pgm -valor 20 -op soma
V2. Operações Lógicas com operando escalar

V2.1. OR: Realiza-se OU lógico entre cada pixel da imagem e operando binário escalar.

V2.2. AND: Realiza-se E lógico entre cada pixel da imagem e operando binário escalar.

V2.3. XOR: Realiza-se OU exclusivo lógico entre cada pixel da imagem e operando binário escalar.

V2.4. NOT: Realiza-se negação lógica de cada pixel da imagem.

Resultados são expressos sempre de forma binária (em nosso caso 0 ou 255)

Implementação:

  • Um único programa implementa todo o conjunto V2.
  • Um parâmetro do tipo Símbolo define qual operação será realizada.

Exemplo:

boolescalar -i imagem.pgm -o iresult.pgm -valor 1 -op and
V3. Operações Matemáticas de imagem com imagem

V3.1. Soma: Soma-se cada pixel de uma imagem ao correspondente da outra.

V3.2. Multiplicação: Multiplica-se cada pixel de uma imagem com o correspondente da outra. Resultado é expresso em valor inteiro.

Resultados de ambos os métodos são truncados para o valor máximo de representação de pixel no tipo de imagem (no nosso caso 255)
Método só pode ser executado se ambas imagens possuem dimensões iguais (x@y)

Dois exemplos de aplicação de um operador aritmético entre duas imagens: a máscara binária obtida por limiarizaçãomorfologia matemática a partir da imagem original é multiplicada com esta para a extração do segmento desejado. Observe que no segundo exemplo a máscara continha o artefato em forma de U que foi trazido para a imagem resultante.

original máscara resultado da multiplicação

V3.3. Subtração: Subtrae-se-se cada pixel de uma imagem do correspondente da outra.

V3.4. Diferença absoluta: Subtrae-se-se cada pixel de uma imagem do correspondente da outra. Resultado é expresso em valor positivo.

V3.5. Divisão: Divide-se cada pixel de uma imagem pelo correspondente da outra. Resultado é expresso em valor inteiro.

Valem as considerações sobre limites mínimos.

  • A ordem dos parâmetros de entrada faz diferença.
  • Ordem é a mesma da expressão na forma infixada.

Implementação:

  • Um único programa implementa todo o conjunto V3.
  • Um parâmetro do tipo Símbolo define qual operação será realizada.

Exemplo:

math -i1 imagem.pgm -i2 imagem2.pgm -o iresult.pgm -op dif

V4. Operações Lógicas de imagem com imagem

V4.1. OR: Realiza-se OU lógico entre cada pixel corespondente das imagens.

V4.2. AND: Realiza-se E lógico entre cada pixel corespondente das imagens.

V4.3. XOR: Realiza-se OU exclusivo lógico entre cada pixel corespondente das imagens.

Resultados são expressos sempre de forma binária (em nosso caso 0 ou 255)

  • A ordem dos parâmetros de entrada faz diferença.
  • Ordem é a mesma da expressão na forma infixada.

Implementação:

  • Um único programa implementa todo o conjunto V4.
  • Um parâmetro do tipo Símbolo define qual operação será realizada.

Exemplo:

bool -i1 imagem.pgm -i2 imagem2.pgm -o iresult.pgm -op xor

V5. Operações de Limiarização

Limiarização simples

V5.1. Limiar acima: Compara-se cada pixel de uma imagem com um valor limiar. Pixels cujo valor for >= ao limiar recebem a cor #1, o resto a cor #2.

V5.2. Limiar abaixo: Compara-se cada pixel de uma imagem com um valor limiar. Pixels cujo valor for <= ao limiar recebem a cor #1, o resto a cor #2.

Para indicar que as cores são branco e preto, podemos expressar #1 = 255 e #2 = 0. Pode-se perfeitamente definir outros valores.

Imagem de tomografia computadorizada de crânio e três diferentes limiarizações. A imagem é de 8 bits e portanto seu valor máximo de pixel é 255. Observe com uma diferença de apenas 5% no limiar, entre 130 e 140 faz uma enorme diferença com relação à quantidade de material indesejável que resulta. O limiarização com valor de 150 será utilizada como máscara em outros exemplos em morfologia matemática.

image original limiar de 130
limiar de 140 limiar de 150

Limiarização de faixa

V5.3. Limiar dentro: Compara-se cada pixel de uma imagem com dois valores limiar. Pixels cujo valor for >= ao limiar inferior e <= ao superior recebem a cor #1, o resto a cor #2.

V5.4. Limiar fora: Compara-se cada pixel de uma imagem dois valores limiar. Pixels cujo valor for <= ao limiar inferior e >= ao superior recebem a cor #1, o resto a cor #2.

Limiarização com, faixa. Observe que neste caso se obteve um resultado bastante interessante, considerando-se a simplicdade do método, mas não foi posível extrair somente a área de interesse (parênquima cerebral) sem problemas e será necessário um pós processamento com morfologia matemática.

Limiarização com Tolerância

V5.5. Limiar acima com histerese: Compara-se cada pixel de uma imagem com dois valores limiares. Pixels cujo valor for >= ao limiar superior recebem a cor #1, pixels que forem <= ao inferior a cor #2. Pixels entre os limiares são comparados aos seus vizinhos imediatos (vizinhança de 4 ou vizinhança de 8), se algum vizinho estiver acima do limiar, este pixel receberá a cor #1, senão a #2.V5.6. Limiar abaixo com histerese: Compara-se cada pixel de uma imagem com dois valores limiar. Pixels cujo valor for <= ao limiar inferior recebem a cor #1, pixels que forem >= ao superior a cor #2. Pixels entre os limiares são comparados aos seus vizinhos imediatos (vizinhança de 4 ou vizinhança de 8), se algum vizinho estiver abaixo do limiar, este pixel receberá a cor #1, senão a #2.

Cálculo de Vizinhança para Operações de Limiarização com Tolerância

Vizinhança de 4 Vizinhança de 8

Implementação:

  • Três programas implementam todo o conjunto V5.
    • Limiar Simples
    • Limiar com Faixa
    • Limiar com Tolerância
  • Um parâmetro do tipo Símbolo define qual operação será realizada.

Exemplos:limiarsimples -i imagem.pgm -o iresult.pgm -op acima -lim 100 -c1 255 -c2 0

limiarfaixa -i ima.pgm -o res.pgm -op fora -inf 128 -sup 200 -c1 255 -c2 0

limiartoler -i ima.pgm -o res.pgm -op acima -inf 128 -sup 130 -c1 255 -c2 0

V6. Operações Estatísticas

V6.1. Histograma

Para cada possível valor de pixel na escala de valores utilizada (0 a 255 no nosso caso) conta-se o número de pixels apresentando esse valor. Gera-se um vetor contendo esses valores (256 posições no nosso caso) e também uma imagem representando essa contagem como um gráfico de barras.

Implementação do Histograma V6.1:

  • Programa toma uma imagem de entrada e gera dois arquivos de saída: a imagem do histograma e o vetor de valores (em ASCII)

Exemplo:

histo -i imagem.pgm -o iresult.pgm -h histo.txt

histo.txt:

255
21 34 56 678 9000 7890 67 5677 456 ....
V6.2. Histograma por Faixas

Calcula-se o histograma dividindo-se a faixa de valores em pedaços dados por seus limites.

Implementação:

  • Programa toma uma imagem e um arquivo texto com a definição das faixas de entrada e gera dois arquivos de saída: a imagem do histograma e o vetor de valores (em ASCII)

Exemplo:

histofaixa -i imagem.pgm -f faixas.txt -o result.pgm -h histo.txt

faixas.txt:

4
0 34
35 90
91 200
200 255

V6.3. Pontos Nodais de Histograma

Calcula-se o histograma e procura-se por n fundos-de-vale no mesmo. Gera-se um vetor contendo esses valores.

Implementação do Cálculo de Pontos Nodais em Histograma

Veja o histograma abaixo. Aparentemente possui dois pontos nodais:

Achando Pontos Nodais em Histograma

  • Primeiramente achamos os picos: pontos de valor elevado onde a derivada muda de positivo para negativo. Para evitar que pequenas flutuações incluam erros, sempre tomar um conjunto de valores para o cálculo.

  • Depois achamos os vales : pontos pontos entre os picos de menor valor. Se houver uma faixa grande de valor baixo, pegar o meio desta.

Classificando Pontos Nodais em Histograma

  • Em terceiro lugar classificamos os vales: vales muito próximos aos picos não nos interessam, pois representam apenas variações de cor de um mesmo grupo.

Verificando Pontos Nodais em Histograma

  • Por último calculamos a área (numero de pontos) de cada segmento: segmentos com muito poucos pontos também não nos interessam e são fundidos com o vizinho que possuir tamanho suficiente.

  • Exemplo: A área amarela é considerada pequena por que possui poucos pontos e ao mesmo tempo representa um vale relativamente baixo. O ponto nodal em verde claro é eliminado. A área é fundida com a área em laranja, já que esse lado é o da menor amplitude.

Requisitos

  • Tolerância no cálculo das derivadas: Usamos uma seqüência de vários valores e uma reta interpolando estes para calcular a derivada tangente. Deve-se implementar o numero de valores como parâmetro.
  • Tolerância na identificação do centro de um vale: Ignora-se pequenas variações ao se seguir o fundo de um vale para determinar sua extensão. Implementado como parâmetro.
  • Tamanho (área) mínimo de um segmento entre pontos nodais: implementar como parâmetro.
  • Seleção de segmentos a fundir: devem ter área abaixo do mínimo e amplitude abaixo de um parâmetro. Melhor forma de expressar isto é multiplicar estes dois valores.
  • Número máximo de pontos nodais: parametro definido pelo usuário.

Implementação

Saídas:

  • Imagem do histograma mostrando os pontos nodais (mostrar histograma em cinza e pontos nodais como retas verticais em branco).
  • Arquivo texto dando lista de valores de pontos nodais.

Linha de comando para forçar encontrar dois pontos nodais:

histonodal -i imagem.pgm -o iresult.pgm -h histo.txt -ntan 10  -tolval 20 -amplitude 50 -area 100 -nodos 2

V7. Operações Combinadas

V7.1. Limiarização com Histograma: Utiliza o resultado de um Cálculo de Pontos Nodais em Histograma para definição dinâmica do limiar. O método de cálculo de pontos nodais é parametrizado para produzir apenas um único ponto nodal. limiarhisto -i imagem.pgm -o iresult.pgm \. .~\z

-op acima -histo histo.txt -c1 255 -c2 0

Métodos no Domínio do Espaço 1: Convolução Simples e Morfologia Matemática

Introdução

Consideramos o valor de cada pixel e também a relação deste com os valores de um conjunto de pixels na sua vizinhança.

  • Partes I e II – Operações utilizando Convolução
  • Parte III – Operações sobre Regiões

Dividido em três grupos de trabalhos:

E1. Operações Genéricas de Convolução
E2. Morfologia Matemática
E3. Operações de Detecção de Bordas

E1. Operações Genéricas de Convolução

O que é convolução ? Matematicamente, a convolução é uma operação entre duas matrizes, geralmente bidimensionais, uma das quais é a imagem e a outra é um matriz chamada de matriz de convolução ou elemento estruturante.

A matriz de convolução representa uma função matemática qualquer e é aplicada sobre cada pixel g(x,y) da imagem e sua vizinhança imediata, resultando em uma nova imagem gc(x,y), que reflete a relação da imagem original com a função matemática dada pela matriz.

Como realizamos a convolução ? Podemos considerar a convolução como a aplicação de uma máscara de resposta à imagem de acordo com critérios bem definidos. Na convolução temos dois componentes:

  • Uma ou mais matrizes de convolução ci(x,y)
  • A operação de convolução

A forma mais simples é quando temos apenas uma matriz de convolução e a operação de convolução é a soma dos resultados da multiplicação de cada elemento da matriz com a região da imagem sob a mesma e a subseqüente substituição do valor do pixel sobre o qual a matriz foi aplicada por este resultado.

Exemplo:

  • mi: é valor para um pixel
  • pi: é o valor do nível de cinza para um pixel
  • Rp5: é a máscara de resposta para o pixel central (p5).
    • Observe que o resultado é sempre escrito na nova imagem resultante
    • Observe que se o pixel sob a matriz se encontrar nas bordas da imagem, consideramos apenas os elementos sob a matriz.


imagem original                             —>                        imagem resultante

E1.1 Detecção de pontos salientes

A aplicação de convolução mais simples é a detecção de pontos salientes na imagem. Um ponto saliente é um ponto cujo valor se destaca de seus vizinhos, não necessariamente um valor alto do ponto de vista absoluto.

E1.2 Convolução Genérica

A aplicação de convolução simples pode ser extendida para outros tipos de matriz de filtragem que podem suavizar ou modificar a imagem. É importante possuir-se um programa que leia uma matriz qualquer e aplique o método utilizando:

  • Qualquer matriz quadrada de convolução ci(x,y) de dimensões ímpares
  • A operação de convolução é sempre a soma das multiplicações das posições correspondentes sob a matriz.
  • O pixel de aplicação R é sempre o valor sob o elemento central da matriz

E 1.3 Laplaciano

O operador de Laplace é utilizado para a detecção de cruzamentos por zero da Segunda Derivada em uma imagem e não possui direção específica, ao contrário do que veremos nos detectores de bordas de Sobel, Roberts, Robinson e outros, adiante.

Há duas variantes, uma utilizada para consideração de vizinhanças-de-4, h4, e outra para levar em consideração vizinhanças-de-8, h8.

Requisitos para E1.1, E1.2 e E1.3

  • Duas entradas: imagem e matriz de convolução
  • Ler as duas entradas tanto em P2 como em P5
  • Uma saída: Imagem resultante.

E2 – Morfologia Matemática

Morfologia Matemática

  • O estudo morfológico concentra-se na estrutura geométrica das imagens.
  • Aplica-se morfologia em , realce, filtragem, segmentação, esqueletonização e outras operações afins.
  • Definição de uma imagem e feita através de um vetor bidimensional com coordenadas (x, y) para sua representação gráfica .

Conceito de Morfologia Matemática

  • Conceito básico: consiste em extrair informações de uma imagem de geometria desconhecida pela transformação com uma outra imagem completamente definida (convolução), chamada elemento estruturante.
  • Ao contrário da convolução genérica, na Morfologia Matemática a FORMA do elemento estruturante terá impacto sobre o resultado.

E2.1 Dilatação Binária

A Dilatação  expande uma imagem utilizando um Kernel.

Requisitos:

    • Usaremos sempre um Kernel quadrado, com Hot Spot no centro da matriz.
    • Se quisermos representar um elemento estruturante com forma de linha, faremos uma matriz quadrada, com 1s na linha central e 0s no resto:

Algoritmo informal da dilatação binária:

  1. Passe o elemento estruturante por todos os pixels da imagem original:
  2. Se o valor do pixel da imagem sob o elemento central for diferente de zero, copie todos os valores não-zero do elemento estruturante para a imagem resultado.

E2.2. Erosão Binária

A Erosão pode ser definida de forma bem informal como a operação morfológica que encolhe uma imagem de acordo com critérios dados por um elemento estruturante.

Algoritmo informal da erosão binária:

  • Passe o elemento estruturante por todos os pixels da imagem original:
  • Se nenhum valor dos pixels da imagem sob os valores não-nulos do elemento estruturante for zero, ponha um valor 1 (ou 255) na posição R da imagem resultado.

Existem diversos Operadores e Filtros Morfológicos usando Dilatação/Erosão. Veremos alguns deles adiante.

E2.3 BoundEXT

  • Achar todos os pixels que limitam o objeto pelo lado de fora (contorno externo).
  • Realiza-se uma dilatação da imagem e desta subtrae-se a imagem original.

E2.4 BoundINT

  • Achar o contorno de interno objetos.
  • Erode-se a imagem e subtrai-se  a imagem erodida da original.

E2.5 Gradiente Morfológico

  • Outra forma de encontrar a borda.
  • Composta de três outras operações básicas: Dilatação, erosão e a subtração.
  • A imagem é dilatada e erodida pelo mesmo kernel e o resultado erodido é subtraído do resultado dilatado. Resulta em uma borda maior e mais confiável.

E2.6 Abertura (Opening)

  • Opening – suaviza o contorno de uma imagem.
  • Quebra estreitos e elimina proeminências delgadas.
  • É usada também para remover ruídos da imagem e abrir pequenos vazios ou espaços entre objetos próximos numa imagem .
  • Dada por uma erosão seguida de uma dilatação com o mesmo elemento estruturante.

E2.7 Fechamento

  • Closing – Funde pequenos quebras e alargas golfos estreitos. Elimina pequenos orifícios. Irá preencher ou fechar os vazios. Estas operações remover pixels brancos com ruídos.
Exemplo de abertura seguida de fechamento utilizado para gerar a máscara binária utilizada no exemplo de extração de estrutura por multiplicação acima.
1.imagem original 3.abertura da imagem limiarizada com
kernel branco de 3×3
2.limiarização por faixa 4.fechamento com o mesmo kernel de 3×3
  • A morfologia matemática, como mostra o exemplo acima é muito ítil para a geração de máscaras binárias, utilizadas então em outros tipos de operação, como operações lógicas e operações matemáticas entre imagens. Nem sempre a geração de uma máscara é simples como no exemplo acima. O exemplo abaixo mostra uma máscara gerada através da utilização de um kernel circular de diâmetro 11 pixels.
Outro exemplo. Neste caso não foi realizada uma abertura para filtragem de ruído. Realizou-se o fechamento imediatamente.
imagem original imagem limiarizada por 150 fechamento com disco de diâmetro 11

Morfologia Matemática – Parte II – Tons de Cinza e Cores

A idéia básica de Morfologia binária extende-se para tom de cinza, mas operações lógicas simulam a conversão aritmética: Uniões se tornam máximos e interseções se tornam mínimos.

E 2.8 Erosão em Tons de Cinza

Algoritmo em Linguagem Informal:
1. Posiciona-se a origem do elemento estruturante sobre o primeiro pixel da imagem que sofre erosão.
2. Calcula-se a diferença de cada par correspondente de valores de pixels do elemento estrutural e da imagem.
3. Acha-se o valor mínimo de todas essas diferenças, e armazena-se o pixel correspondente na imagem de saída para este valor.
4. Repete-se este processo para cada pixel da imagem que sofre erosão.

Erosão de tons de cinza de uma imagem de ultra-som com um kernel branco de 3×3
Erosão de uma imagem de tomografia computadorizada utilizando um kernel circular de diâmetro 7

E 2.8 – Dilatação em Tons de Cinza

Algoritmo em Linguagem Informal:
1. Posiciona-se a origem do elemento estrutural sobre o primeiro pixel da imagem a ser dilatada.
2. Calcula-se a soma de cada par correspondente de valores de pixels do elemento estrutural e da imagem.
3. Acha-se o valor máximo de todas essas somas, e armazena-se o pixel correspondente na imagem de saída para este valor.
4.  Repete-se este processo para cada pixel da imagem a ser dilatada.

Dilatação de tons de cinza  de uma imagem de ultra-som  com um kernel branco de 3×3
Dilatação de uma imagem de tomografia computadorizada utilizando um kernel circular de diâmetro 7

E 2.10 Fechamento em Tons de Cinza

O fechamento em tons de cinza funciona como o fechamento binário combinando as duas operações de dilatação e erosão em seqüência. A diferença é que a propriedade da idempotência não se aplica: vários fechamentos seguidos produzem uum resultado mais acentuado do que um único fechamento. Isto significa que ium operador do tipo n-fechamento faz sentido. Veremos alguns exemplos adiante.

E 2.11 Abertura em Tons de Cinza

A abertura em tons de cinza funciona como a abertura binária combinando as duas operações de erosão e dilatação em seqüência. A diferença é que a propriedade da idempotência não se aplica: várias aberturas seguidas produzem um resultado mais acentuado do que uma única abertura. Isto significa que ium operador do tipo n-abertura faz sentido. Veremos alguns exemplos adiante.

Exemplos de Morfologia Matemática de Tons de Cinza

Vários exemplos de aplicação de abertura e fechamento, sempre sobre as imagens originais de ultra-sm e tomografia computadorizada mostradas anteriormente

aberturas fechamentos
abertura simples com kernel 3×3 fechamento simples com kernel 3×3
2 aberturas com disco de diâmetro 7 2 fechamentos com disco de diâmetro 7
5-abertura com disco 7 5-fechamento com disco 7
15-abertura com kernel 3×3 15-fechamento com kernel 3×3
15-abertura com disco 7 da tomografia 15-fechamento com disco 7 da tomografia

Para você repetir os exemplos acima: Aqui está um workspace para Khoros versão 2.x, contendo em um arquivo as imagens-ponto de partida dessses exemplos e também o workspace para qualquer versão de Khoros 2.0 a 2.2. As imagens fornecidas estão em formato .JPG, lembre-se de convertê-las para PGM ou algo similar antes de usar. Para isso você pode usar o XV, gimp ou outro software livre.

Download workspace and images.

 


Métodos no Domíno do Espaço 2: Detecção de Bordas

6.6.1. Introdução

Dividido em três grupos de trabalhos que serão implementados  pelas equipes.

Borda é o contorno entre um objeto e o fundo indicando o limite entre objetos sobrepostos Um CONTORNO é uma linha fechada formada pelas bordas de um objeto. Mas como conceituamos e detectamos uma borda computacionalmente?

Variações de intensidade complexas que ocorrem em uma região são geralmente chamadas de textura. Bordas são definidas como picos da magnitude do gradiente, ou seja, são variações abruptas que ocorrem ao longo de curvas baseadas nos valores do gradiente da imagem. As bordas são regiões da imagem onde ocorre uma mudança de intensidade em um certo intervalo do espaço, em uma certa direção. Isto corresponde a regiões de alta derivada espacial, que contém alta frequência espacial. 

  • Borda unidimensional : pode ser definida como uma mudança de uma intensidade baixa para alta. A intensidade do sinal pode ser interferida por ruídos.

borda unidimensionalGráfico da intensidade de uma imagem
 

  • Borda bidimensional: as descontinuidades ocorrem ao longo de certas linhas ou orientações A orientação é uma característica importante em bordas 2-D 

Gráfico da intensidade representando uma borda bidimensional.
Ruídos

A aquisição da imagem está sujeita a algum tipo de ruído, a situação ideal (sem ruído), na prática não existe. Ruídos não podem ser previstos pois são de natureza randômica e não podem nem mesmo ser medidos precisamente. Porém, algumas vezes ele pode ser caracterizado pelo efeito na imagem, e é geralmente expresso como uma distribuição de probabilidade com uma média específica e um desvio padrão. Existem dois tipos de ruídos específicos: 

    • Ruído independente do sinal: é um conjunto randômico de níveis de cinza, estatisticamente independente dos dados da imagem. Este tipo de ruído acontece quando a imagem é transmitida eletronicamente de um lugar para outro. 
      • A – imagem perfeita 
      • N – é o ruído 
      • B – imagem final 
      • B= A+N 
  • Ruído dependente de sinal: o nível do valor de ruído a cada ponto na imagem é uma função do tom de cinza. 

Operadores para detecção de bordas – Operadores de derivadas

Uma vez que uma borda é definida por uma mudança no tom de cinza, quando ocorre uma denscontinuidade na intensidade, ou quando o grandiente da imagem tem uma variação abrupta, um operador que é sensível a estas mudanças operará como um detector de bordas.

Um operador de derivada faz exatamente esta função. Uma interpretação de uma derivada seria a taxa de mudança de uma função, e a taxa de mudança dos níveis de cinza em uma imagem é maior perto das bordas e menor em áreas constantes. Se pegarmos os valores da intensidade da imagem e acharmos os pontos onde a derivada é um ponto de máximo, nós teremos marcado suas bordas. Dado que as imagens são em duas dimensões, é importante considerar mudanças nos níveis de cinza em muitas direções. Por esta razão, derivadas parciais das imagens são usadas, com as respectivas direções X e Y. Uma estimativa da direção atual da borda pode ser obtida usando as derivadas x e y como os componentes da direção ao longo dos eixos, e computar o vetor soma. O operador envolvido é o gradiente, e se a imagem é vista como uma função de duas variáveis A(x,y) então o gradiente é definido como: 

Para operadores d edetecção de bordas usaremos operadores de convolução que utilizam mascaras de convolução (kernels) projetadas de tal forma e darem a máxima resposta quando se encontram sobre uma variação abrupta de intensidade de sinal (tom de cinza). Existem vários tipos de máscaras e elas recebem geralmente o nome de seus inventores. Além desses operadores simples, há ainda operadores de detecção de bordas que utilizam este conceito como ponto de partida mas o extendem de alguma forma, seja com convoluções sucessivas ou com heurísticas adicionais. Veremos dosi desses no final deste capítulo.

Retornar ao início.

6.6.2. Grupo E3 – Detecção de Bordas com Convolução Simples

E3.1 Roberts

É o mais antigo e simples algoritmos de detecção de bordas. Publicado em L. Roberts Machine Perception of 3-D Solids, Optical and Electro-optical Information Processing, MIT Press 1965. Utiliza uma matriz 2×2 para encontrar as mudanças nas direções x e y. 

Máscara ou Kernel de Convolução de Roberts: 

Para determinar onde o pixel avaliado é ou não um pixel de borda, o gradiente é calculado da seguinte forma: 

Fórmula para cálculo do gradiente: 

Se a magnitude calculada é maior do que o menor valor de entrada (definido de acordo com a natureza e qualidade da imagem que esta sendo processada), o pixel é considerado ser parte de um borda. A direção do gradiente da borda, perpendicular a direção da borda, é encontrada com a seguinte fórmula:

Fórmula para cálculo da magnitude: 

O pequeno tamanho da máscara para o operador de Roberts torna o mesmo fácil de se implementar e rápido para calcular a máscara de resposta. As
respostas são muito sensíveis ao ruído na imagem.


Resultado da aplicação da implementação do Khoros do operador de Roberts
sobre a imagem de tomografia mostrada anteriormente.
Algumas informações adicionais com sugestões de utilização do OPerador de Roberts para análise de imagens podem ser encontradas aqui

Retornar ao início.

E3.2 Sobel

Utiliza duas máscaras para encontrar os gradientes vertical e horizontal das bordas.
Máscaras de Sobel: 
Considerações sobre o operador de Sobel

  • A fórmula para encontrar o gradiente e o ângulo são as similares ao operador de Roberts. 
  • A computação de |G| se torna mais complexa. Na prática |G| é aproximada da seguinte forma: |G|= |Gx| + |Gy|. 
    • O ângulo do gradiente corresponde direção de máxima variação da intensidade 
  • Devido as máscaras serem 3X3 ao invés de 2X2, Sobel é muito menos sensível ao ruído do que Roberts. 
  • Os resultados são mais precisos e o módulo do gradiente é proporcional a derivada local da intensidade. 

Extensões ao método de Sobel

    1. Alguns autores incluem uma terceira matriz para encontra gradientes diagonais, mostrada abaixo. Netse caso temos três e não duas matrizes para o cálculo dos gradientes. 

  1. Alguns autores trabalham com mais três matrizes, que são as negações das três vistas até o momento. Isto permite que se identifique não só a direção mas também o sentido do crescimento do gradiente. Pode ser útil.


Resultado da aplicação da implementação do Khoros do operador de Sobel 
sobre a imagem de tomografia mostrada anteriormente.
Retornar ao início.

E3.3 Robinson

É similar em operação ao de Sobel, porém usa um conjunto de oito máscaras, onde quatro delas são as seguintes: 

As outras quatro são simplesmente negações destas quatro.

A magnitude do gradiente é o valor máximo obtido ao aplicar todas as oito máscaras ao pixel vizinho, e o ângulo do gradiente pode ser aproximado como o ângulo na linha de zeros na máscara dando a resposta máxima. Abaixo as quatro matrizes acima com seus respectivos ângulos de preferência:

As matrizes negadas possuem mesma direção, mas sentido oposto como ângulo preferencial. 
Este algoritmo aumenta a precisão de |G|, mas requer mais computação do que as versões tradicionais de Roberts e Sobel, devido à quantidade de máscaras.

Retornar ao início.

E3.4 Prewitt

O operador de Prewitt é muito similar à versão de 6 matrizes do Operador de Sobel. O que varia é apenas o conjunto de valores das matrizes de convolução, que são definidas como segue:

As outras matrizes são a negação destas e detectam gradientes de mesma direção e sentido oposto.  Na verdade, se se deseja calcular com precisão direção e sentido de gradientes diagonais, tem de se rotacionar a matriz h2 em passos de 90 graus por três vezes, o que resulta em 8 e não 6 matrizes.


Resultado da aplicação da implementação do Khoros do operador de Prewitt 
sobre a imagem de tomografia mostrada anteriormente.
Retornar ao início.

E3.5 Isotrópico

Um operador isotrópico em análise de imagens é um operador que responde de forma igual a variações de intensidade em toda e qualquer direção em uma imagem, sem qualquer preferência por uma direção ou conjunto de direções específico. Um exemplo típico é o detector de cruzamento por zero que responde de forma igual a bordas (na verdade a gradientes) em quaisquer direções. A utilização de suavização gaussiana também atua dessa forma. Na pratica costuma-se utilizar cruzamentos por zero associados a uma suavização gaussiana prévia da imagem. O operador para encontrar cruzamento spor zer pode ser o Laplaciano descrito anteriormente

No exemplo abaixo não sabemos qual matriz de convolução foi utilizada pois a documenttação do Khoros não menciona e não tentamos fazer negenharia reversa no código-fonte para descobrir. Fica apenas como exemplo. Este operador não vamos implementar. 


Resultado da aplicação da implementação do Khoros do operador  isotrópico 
sobre a imagem de tomografia mostrada anteriormente.
Retornar ao início.

6.6.3. Grupo E3’ – Operadores Avançados de Detecção de Bordas

E 3.4 Canny

Retornar ao início.

6.6.4. Grupo E3’’ – Detecção de Estruturas Salientes

E 3.5 Sha’aShua

Links de Detecção de Bordas Mundo Afora

Retornar ao início.


Métodos no Domínio do Espaço 3: Segmentação

A simplificação da imagem é uma questão central na visão computacional, o que pode ser feito reduzindo-se as informações da imagem para regiões mais ou menos homogêneas. O resultado é uma “caricatura” da realidade onde somente a parte importante está presente, sendo que os detalhes desnecessários e ruídos são extraídos.Aplicações:

  • Controle de qualidade
  • Inspeção automatizada de peças em fábricas
  • Visão robótica

Existem métodos simples para segmentar a imagem, como:

Mas esses métodos deixam restos de informações desnecessárias ou perdem informações. Para superar essas limitações de métodos no domínio do valor, foram desenvolvidos métodos que operam no domínio do espaço e utilizam informações sobre:

    • vizinhança de pixel
    • variação de valor de pixel em uma vizinhança
    • estatísticas sobre agrupamentos de pixel

…para gerar uma imagem resultante dividida em regiões.

Veremos os principais abaixo.Retornar ao início.

E4. Crescimento de Regiões

Informações adicionais sobre Crescimento de Regiões você pode obter na página da Disciplina de Visão Computacional do PPGCC da UFSC.

E4.1 Crescimento de Regiões com Medidas Simples

Crescimento de regiões simples se divide em dois grupos:

  1. Conecção simples 
  2. Conecção híbrida

Conexão SimplesPixels similares são unificados em regiões. Os seguintes princípios de similaridade são observados:

  • Normalização.
    • Valor absoluto da diferença com os seus vizinhos.
    • Diferença quadrática da média  dos píxels da imagem.
  •  Medida estatística
    • Região vai crescendo e se permite que cresça até o desvio padrão ou a variância dos valores em seu interior ultrapassar um limiar.

Conexão Híbrida 

Utiliza-se como auxiliar uma imagem de bordas (gradientes):

  • Cada píxel possui uma propriedade vetorial que depende de sua vizinhança K x K (máscara), indicando a direção da borda. 
  • Os píxels marcados como bordas são conectados por um arco/polígono. 
  • Uma região não pode ser considerada um segmento enquanto sua fronteira estiver aberta. 
  • A qualidade da técnica depende dos algoritmos de detecção de bordas utilizados.
  • Dentro de uma região definida por uma borda usa-se um dos métodos anteriores. A região pode ser subdividida.

Para facilitar a montagem dos polígonos pode-se utilizar uma dilatação ou um fechamento após uma limiarização…

E4.2 Split & Merge
E4’ O Funcional de Mumford & Shah

E 4.3 Mumford & Shah

Informações adicionais sobre Crescimento de Regiões com o Funcional de Mumford e Shah você pode obter na página específica deste assunto da Disciplina de Visão Computacional do PPGCC da UFSC. 
E3’’ O Método do Divisor de Águas

E 4.4 Watershed

O método do Divisor de Águas é baseado em uma idéia advinda da Geografia. Pode ser melhor visualizada com base nas figuras e no GIF animado produzidos por Serge Beucher do Centro de Morfologia Matemática da Escola de Engenharia de Minas de Paris.

O raciocínio parte do princípio de que uma imagem de gradientes pode ser considerada uma topografia, quanto maior o gradiente, mais alta a montanha por ele representada.

. . . 
Se aplicarmos conceitos de geografia àquela imagem topográfica acima que é como imaginamos a nossa imagem de gradientes, podemos então imaginar um método de segmentação que se baseia neste conceito geográfico e simula o que acontece em um conjunto de bacias hidrográficas sempre que chove muito: enchente. Basta então que façamos chover nesta topografia de forma a inundar as regiões profundas (de gradiente nulo ou muito baixo). Regiões que formam bacias de contenção isoladas por gradientes fechados formarão regiões ou segmentos separados. Procede-se da seguinte forma:

  1. Define-se uma altura mínima do nível de água. Este valor é um parâmetro e determinará a sensibilidade do algoritmo. Todos os gradientes com valor abaixo deste mínimo serão cobertos pela água na inicialização do algoritmo e ignorados.
  2. Inicializa-se as regiões com os pixels que contém valores de gradiente abaixo deste limiar (pode-se limiarizar a imagem e passar para 0 tudo abaixo da altura mínima de água). Conecta-se os pixels através do algoritmo de componentes conexas, onde tudo o que está abaixo do limiar inicial de altura de água é rotulado e agrupado em segmentos conexos e o que estiver acima é inicialmente ignorado (é o contrário do algoritmo de componentes conexas normal). A grande maioria dos segmentos gerados não vai se tocar, porque existem muitos gradientes que a esta altura do campeonato ainda estão “fora da água”. 
  3. Os outros gradientes estarão fora da água. Como possuem alturas diferentes, independentemente de sua altura, possuirão acima de seus pontos mais altos uma barragem virtual de largura 0 e altura infinita que impede que águas de diferentes bacias de contenção se misturem. Os pontos mais altos serão determinados naturalmente com o aumento do nível de inundação que se seguirá.
  4. Faz-se chover incrementando iterativamente o nível de água:
    • A cada iteração, rotula-se todos os pixel ainda não rotulados que foram cobertos pela água, conectando-os à região mais próxima, dando a eles o rótulo dessa região. 
    • Quando se atinge a barragem virtual e há ambigüidade na rotulação, deve-se atribuir o rótulo da região de gradiente descendente. Se o pixel se encontrar em um platô, sorteie.
    • O processo termina quando não há mais pixels sem rótulo e as águas cobriram tudo.

  ao inundar-se: 
Veja a animação de Serge Beucher para entender melhor:

Comentários sobre o Método do Divisor de ÁguasEste método, por se basear quase exclusivamente em informações de valor de pixel na imagem de gradientes para produzir o resultado final (informação espacial tem um papel no método, mas o peso maior na rotulação é do valor) possui uma sensibilidade extremamente grande a variações mínimas localizadas de gradientes. Isto significa que este algoritmo reage de forma extremada a pequenas variações e a sujeira na imagem. O algoritmo, na sua forma bruta, como descrito acima, também possui critério de qualidade zero no que diz respeito ao tamanho e à forma dos segmentos gerados, significando que uma pequeníssima mas muito intensa variação localizada de gradiente vai gerar um segmento renitente e um grande, harmonioso e belo segmento pode ser eliminado simplesmente pelo fato de possuir grandes e belos e suaves gradientes nas suas bordas. Em suma: é um método que cria segmentos feios, cheios de irregularidades nas bordas e deixa uma montoeira de segmentinhos irritantes que você tem de limpar de alguma forma.

Há formas de contornar isso através da inclusão de extensões ao método. Como o método possui uma complexidade computacional linear, ridículamente baixa para um método de processamento de imagens  (fácil de ver:  realiza um número fixo de iterações, definido a priori pelo número de tons de cinza de gradiente que a água vai subir e para cada iteração só há uma passada pela imagem), extendê-lo pelas formas mais variadas e criativas  tem sido um esporte praticado por muitos doutorandos em Computação, Matemática, Engenharia Biomédica e Engenharia Elétrica mundo afora. As duas principais formas de extensão podem ser resumidas como segue:

  • Utilização de filtragens a priori. Para eliminar  variações localizadas de gradientes, pequenos picos sem importância e gradientes sem significado, além de reforçar variações de gradiente de caráter mais global, pode-se usar uma filtragem suavizante, como uma convolução de Gauss. Mais interessante ainda é utilizar um filtro de gradientes que inclui um processo desse tipo, como o Detector de Bordas de Canny, ao invés de usar algoritmos simplórios como o de Sobel ou Robinson.
  • Utilização de heurísticas a posteriori. Pode-se utilizar uma série de heurísticas a posterior ou durante a junção de segmentos para eliminar segmentos muito pequenos ou sem importância, como tamanho mínimo de segmento, comprimento mínimo de borda, inclinação mínima de gradiente e até coisas mais sofisitcadas como simular tensão de superfície para fazer a águas passar por cima de uma gradiente acima do nível da água e outras coisas. Aqui não há limites à sua criatividade.

Concluindo, pode-se dizer que, as vantagens do Watershed são a sua extrema rapidez (é um dos poucos algoritmso de segmentação por crescimento de regiões que é adequado para aplicações de tempo real), facilidade com que pode ser paralelizado e extendido para 3D e facilidade com que pode ser incrementado com técnicas adicionais de pré- e pós-processamneto. A desvantagem está nos segmentos irregulares e feios gerados e na falta de um critério de qualidade global para os segmentos. Na prática a sugestão é que, sempre que possível, se utilize um método como o Funcional de Mumford e Shah e se reserve a utilização do Watershed para casos 3D (em 3D o Mumford e Shah é impraticável pelas capacidades computacionais de hoje) e casos onde performance é mais importante que qualidade e confiabilidade. Informações adicionais sobre Crescimento de Regiões com o Método do Divisor de Águas você pode obter na página específica deste assunto da Disciplina de Visão Computacional do PPGCC da UFSC. 

Links de Segmentação por Crescimento de Regiões Mundo Afora

Métodos de Extração de Parâmetros e Rotulação de Objetos

Até o momento discutimos métodos que transformam uma imagem em outra imagem, da filtragem, passando pelas diversas formas de morfologia até a segmentação. Para poder realizar uma análise de imagens automatizada ou semiautomatizada e que culmine em uma classificação do conteúdo da imagem e eventualmente em uma decisão automatizada acerca de como reagir a este conteúdo, é necessário que se descreva os objetos que a imagem contém. O primeiro passo foi dado na segmentação, onde se definou os limites dos diversos objetos, agora usaremos um conjunto de algoritmos para rotular e descrever este conteúdo. Na pipeline de processamento originalmente idealizada por David Marr, estes algoritmos estão no terceiro grupo de ações a serem realizadas sobre uma imagem, chamados de forma genérica de Rotulação ou Labeling, como mostramos em nossa tabela classificatória ao início deste módulo . Os métodos deste grupo podem ser  divididos em em dois conjuntos:

L1. Métodos de Rotulação, que tomam partes de uma imagem e associam rótulos a estas partes, rotulando-as pixel-a-pixel. São úteis para desmembrar imagens em pedaços, permitindo identificar as diferentes partes de uma imagem. Normalmente usa-se os rótulos gerados aqui para guiar algum processo de análise d eimagens posterior.L2. Métodos de Extração de Parâmetros, que calculam um parâmetro para uma imagem ou parte dela, expressando-o como um vetor ou escalar que representa um aspecto ou característica daquela parte. Normalmente usa-se os rótulos gerados aqui para expressar alguma característica da iamgem ou segmento de imagem para fins de classificação por algum método de Reconhecimento de Padrões como Redes Neurais ou IBL.

Evidentemente essa classificação é empírica e outras podem ser encontradas. O fundamento matemático dos métodos em cada um desses conjuntos variaanormemente de método para método. O objetivo é subdividir esse extenso grupo de uma forma didática.L1. Métodos de Rotulação

Aqui veremos apenas um método, o Cálculo de Componentes Conexas, que é o mais importante de todos e que é utilizado também como parte de outros algoritmos, como por exemplo a Segmentação pelo Método do Divisor de Águas

L 1.1. Cálculo de Componentes Conexas

O método de cálculo de componentes conexas é utilizado para extrair os diferentes objetos de uma imagem de acordo com alguma característica desses objetos, normalmente a sua cor. Utiliza-se para determiar que partes da imagem pertencem a qual objeto e para resolver ambigüidades quando diferentes objetos possuem atributos similares ou idênticos. 

Exemplo: Considere a seguinte imagem e responda à pergunta “Quantos objetos há nesta imagem ?”

A resposta evidentemente é 4! Isto significa que a informação de cor não é suficiente para distinguir os objetos. Na imagem há três objetos distintos possuindo exatamente a mesma cor (azul…). É necessário utilizar informação de continuidade espacial para determinar quais partes da imagem pertencem a qual objeto e qual é exatamente a extensão de cada objeto azul. Para determinar a  continuidade espacial, é necessário determinar as Componentes Conexas da imagem.

Para tanto, algumas definições:

  • Componente Conexa é um conjunto finito de pixels conectados que compartilham uma determinada propriedade V.
  • Dois pixels p e q são conectados ou conexos quando existe um caminho de p até q onde todos os pixels do camiho apresentam a propriedade V.

Para exemplificar e explicar o algoritmo do método, vamos imaginar uma imagem que possui fundo branco e três objetos distintos e bastante intrincados de três cores diferentes. Assumimos que a nossa propriedade de interessé é a cor do pixel e que podemos acessar o valor dessa cor como rótulo  intrínsico de cada pixel.Vamos inicialmente introduzir um pouco de notação: Representaremos a imagem por um vetor bidimensional A[M,N] onde M e N são as dimensões da imagem. Usaremos um segundo vetor Q de mesmo tamanho para armazenar os rótulos das componentes conexas. Vamos ainda chamar de L o índice de rotulação, que indica qual o rótulo presentemente utilizado. O valor de fundo da imagem é definido a priori e sempre que um pixel da faixa de valores de fundo é encontrado recebe o rótulo 0

Os objetivos do processo de rotulação conexa são:

  • Fazer com que todos os pixels em uma componente conexa possuam o mesmo rótulo e
  • fazer com que todas componentes diferentes possuam rótulos distintos.

No correr do processo o algoritmo vai fazer com que pixels em uam mesma componente tenham rótulos diferentes (mas nunca pixels em componentes diferentes tenham o mesmo rótulo). Isto é resolvido ao final. Existem variantes do algoritmo para vizinhanças-de-4 e de -8. Vamos descrever aqui a variante para vizinhanças de 4. A extensão deste algoritmo para vizinhanças de 8 é simples e ficará evidente no correr da explanação. O algoritmo tem três fases:

Fase 1: Primeira Linha

P1. Percorra a primeira linha da imagem. Rotule A[0,0]. Se A[0,0] possuir cor diferente do fundo, incremente o índice L e faça Q[0,0] = L

P2. Percorra o restante da linha. Se A[x,0]>cor_de_fundo e A[x,0]=A[x-1,0] então faça Q[x,0]=Q[x-1,0]. Se A[x,0]>cor_de_fundo e A[x,0] for diferente de A[x-1,0] então incremente o índice de rótulos L e faça  Q[x,0]=L. O resultado é mostrado abaixo:

Fase 2: Demais LinhasP3. Percorra as linhas restantes, uma a uma. Para o primeiro pixel de cada linha ignore o vizinho da esquerda do pixel sendo observado, considerando apenas seu vizinho de cima. Faça:

  • SE A[0,y]>cor_de_fundo e A[0,y]=A[0,y-1] ENTÃO faça Q[0,y]=Q[0,y-1]
  • SE A[0,y]>cor_de_fundo e A[0,y] diferente de A[0,y-1] ENTÃO incremente L e faça Q[0,y]=L

P4. Para o resto da linha, de y=1 até M-1 faça como segue, olhando agora ao mesmo tempo para o vizinho de cima e para o vizinho da esquerda. Por questões de simplicidade, vamos nos referir ao pixel corrente como p, ao pixel da esquerda como s e ao pixel acima como t

  • SE A[p] = A[s] mas A[p] for diferente de A[t] ENTÃO faça  Q[p] = Q[s]
  • SE  A[p] for diferente de A[s] mas A[p] = A[t] ENTÃO faça  Q[p] = Q[t]
  • SE  A[p] for diferente de A[s] e A[p] for diferente de A[t] ENTÃO incremente L e faça Q[p]=L
  • SE A[p] = A[t] e A[p] = A[s] (trio igual) e Q[t] = Q[s] (rótulos iguals e consistentes) ENTÃO faça Q[p] = Q[t]. Isto resolve todos os casos, à exceção de: A[p] =A[t] e A[p] = A[s] (trio igual) e Q[t] diferente de Q[s] (rótulos diferentes e inconsistentes).  Temos duas componnetes que deveriam ter o mesmo rótulo mas não sabíamos até agora. Neste caso nós rotulamos p com o menor dos dois rótulos, L1, e incluímos o maior dos dois, L2,  na Lista de Equivalência EQ, fazendo EQ[L2] = L1. Vamos arrumar estas inconsistências mais tarde. 

O resultado até o momento deveria se parecer com a figura abaixo. Elementos sublinhados representam momentos onde se descobriu equivalências de rótulos. Neste caso EQ[2] = 1, EQ[4] = 3, EQ[6] = 1 e EQ[7] = 5. 

Fase 3: Correção de RótulosP5. Percorra a Lista de Equivalência de trás para frente, percorrendo toda a imagem para cada entrada e substituindo o rótulo de todos os pixel de um determinado índice pelo rótulo associado, por exemplo, substituindo primeiro 7 por 5, depois 6 por 1, depois 4 por 3 e finalmente 2 por 1.

Retornar ao início.

L2. Métodos de Extração de Parâmetros

Os principais métodos que calculam um parâmetro para uma imagem ou parte dela, expressando-o como um vetor ou escalar estão listados abaixo. Para montar este material baseamos-nos no material disponibilizado por Dr. Harvey Rhody do Carlson Center for Imaging Science para a disciplina SIMG-782 Introduction to Digital Image Processing. 

Momentos
The moment of order (p+q) of a discrete function f(x,y) is defined at the right. The summation is over a domain that includes all nonzero values of the function.We will assume that f(x,y) is a non-negative function with finite values on a bounded image plane. This is appropriate for most image applicationsO Programa Meshgrid fornecido com os algoritmos de cálculo is used to generate the X and Y arrays for the moment calculation.
Massa e Área
The total mass of the function is given by the moment m00. When the function has been normalized so that it has unit mass it is sometimes called a probability function.Observe o seguinte: f(x,y) é o “peso” de cada elemento discreto na imagem (pixel). Você pode fazer isso de duas formas diferentes:

  • você considera que a intensidade luminosa (tom de cinza ou luminância em imagesn RGB) é um “peso” do pixel e utiliza este valor (normalizado ou não – para aplicar nas equações adiante tem de normalizar)  ou
  • você considera que todo pixel não nulo tem peso unitário e nesso caso a massa será equivalente à área e igual simplesmente à soma do número de pixel.
Centróide
The centroid of f(x,y) is the point at which it will balance. The coordinates of the centroid are found as shown at the right. Note that the function is normalized by dividing by the mass.
Momentos Centrais
The central moment is obtained by shifting the origin to the centroid of the function.
Momentos Centrais Normalizados
The normalized central moment of order (p+q) is obtained by dividing the central moment of the same order by a normalization factor. The factor is a function of p and q.
Momentos InvariantesA set of seven invariant moments can be defined by combining the normalized central moments. 

The table at the right is from the text, Gonzalez and Woods, page 516, which is based on the paper by Hu (1962).

Como eu calculo os etapq‘s ?

Fácil: estão representando os momentos centrais normalizados, que são calculados a partir dos momentos centrais, os quais são por sua vez calculados a partir dos   momentos de diversas ordens utilizados para compor os momentos invariantes.  Basta olhar a fórmula para cálculo do momento acima.

Exemplo dos 2 Primeiros  Momentos Invariantes phi1 e phi2 aplicados a um Retângulo. 

Escala: 1
Escala: 3
Escala: 5
Observe os valores de phi1 e phi2 para o mesmo objeto em diversas escalas de magnificação: eles se mantém muiot similares, apresentando invariância de escala. Isto é importante para se poder definir os atributos de um tipo de objeto. 

Escala Ângulo phi 1 phi 2
1 0 0.182 0.006
1 10 0.188 0.007
1 45 0.220 0.008
1 90 0.182 0.006
3 0 0.184 0.006
3 10 0.189 0.006
3 45 0.222 0.009
3 90 0.184 0.006
5 0 0.184 0.006
5 10 0.189 0.006
5 45 0.220 0.009
5 90 0.184 0.006
Exemplo dos 4 Primeiros  Momentos Invariantes phi1 a phi4 aplicados a uma Figura Geométrica mais complexa. 

Observe os valores de phi1 a phi4 para o mesmo objeto em diversas escalas de magnificação: eles se mantém menos  similares do que no exemplo anterior, por exemplo em 90 graus de inclinação, apresentando uma invariância de escala menor. Neste caso é necessária a comparação de mais momentos para que se possa caracterizar a inclinação do objeto com invariância de tamanho, caracterizando uma segunda operação de reconhecimento d epadrões dentro da operação de reconhecimento de objetos em imagens.

Escala Ângulo phi 1 phi 2 phi 3 phi 4
1 0 0.275 0.028 0.008 0.001
1 10 0.288 0.029 0.009 0.001
1 45 0.330 0.039 0.013 0.002
1 90 0.275 0.028 0.008 0.001
3 0 0.268 0.026 0.007 0.001
3 10 0.276 0.027 0.007 0.001
3 45 0.323 0.038 0.011 0.001
3 90 0.268 0.026 0.007 0.001
5 0 0.266 0.025 0.006 0.001
5 10 0.273 0.027 0.007 0.001
5 45 0.319 0.036 0.011 0.001
5 90 0.266 0.025 0.0063 0.001

Além destes, existe ainda a Excentricidade, cuja forma de cálculo pode ser encontrada na página da Cardiff School of Computer Science.

Algoritmos de Extração de Parâmetros

Observe que as rotinas abaixo calculam um vetor ou um escalar para apenas um segmento de imagem ou para uma imagem contendo apenas um segmento como pixel não-nulo. Significa que você vai ter de fazer o seguinte para usálas:

a) segmente a imagem original e use uma rotina de componentes conexas para separar os segmentos
b) aplique o algoritmo escolhido a cada um dos segmentos.

O material está compilado na Página de Rotinas de Cálculo de Momentos e outros Parâmetros desta Disciplina ou então você pode acessar os capítulos um a um:

  1. MESHGRID,N,M,X,Y
  2. Moments2D,A,p,q
  3. CentralMoments2D,A,p,q
  4. NormalMoments2D,A,p,q 
  5. InvariantMoments2D,A

Uma outra visão desse mesmo tema é dada por Dave Marshall do Geometric Computing and Computer Vision Group da Cardiff School of Computer Science. Abaixo dois links contendo o mesmo material:

Links de Rotulação de Imagens Mundo Afora

a) Componentes Conexas

6.9. Enunciado do Trabalho FinalO trabalho final consistirá na aplicação de tudo o que você desenvolveu até o momento, tanto RP I como RP II. O material e uma descrição do cenário de aplicação se encontram na página da disicplina entitulada Material para o Trabalho Final  Aqui você vai desenvolver um sistema de vigilância automatizado que adquire constantemente imagens de uma câmera e as compara com imagens do local vazio (a aquisição “constante” de imagesn vai ser simulada – usaremos apenas os exemplos providos no material do link anterior). Detectando diferenças entre a referência (local vazio) e a imagem atual, determina quais regiões (objetos) provocaram estas diferenças e calcula um conjunto de parâmetros. Daí utiliza estes parâmetros para calcular se este objeto pertence a uma de três classes: ruído provocado pela movimentação da câmera ou sombras de nuvens (ruíido), um ser humano (intruso) ou um dos animais (cachorros) que patrulham o terreno. Caso seja detectada a presença de um intruso um alarme deverá soar.

Para realizar os testes de procesamento de imagem para implementar esse cenário, utilize a interface de programação visual Cyclops Image Filter fornecida acima e as implementações dos algoritmos de processamento de imagem que você e as outras equipes fizeram durante a disciplina. Faça testes com diferentes algoritmos de filtragem, morfologia e segmentação até obter uma pipeline de processamento satisfatória, que separe os objetos “novos” na imagem e depois calcule os parâmetros descritores destes objetos, escolhendo algoritmos de descrição de objetos dentre os acima que achar adequados. Para a classificação, implemente  e utilize um classificador de padrões de sua escolha, como IBL, Rede Neural ou outro. 

Sobre o Autor

Thiago Rateke has a Master's degree of Computer Science from Federal University of Santa Catarina (UFSC) (2015). Bachelor's of Computer Science from University of Vale do Itajai (UNIVALI) (2011). With experience in LAPIX - Image Processing and Computer Graphics Lab - laboratory associated with INCoD at Federal University of Santa Catarina; UFSC. Where he conducted research and development in digital image processing. Currently enrolled in the Graduate program at the level of PhD at UFSC with focuses on Autonomous Navigation.