Classificação de Imagens

Introdução | Preparação dos Dados | Classificador Quadrático | Resultados | Download do Programa | Referências Bibliográficas

1. Introdução

            Técnicas de classificação de objetos consistem, basicamente, em separá-los colocando-os em grupos previamente definidos. Os critérios de classificação dos objetos baseiam-se nos atributos dos mesmos. Por isso, em classificadores automáticos, estes atributos precisam ser representados numericamente. No processamento de imagem, atributos relacionados a intensidade dos pixels são naturalmente escolhidos para representarem objetos ou regiões das imagens num classificador.

            O tipo de classificação pode ser dividida em duas categorias: supervisionada, que precisa de dados de treinamento para o classificador; e não-supervisionada que funciona sem a etapa de treinamento, utilizando outros critérios de semelhança dos objetos, como por exemplo, a distância entre os mesmos. Este projeto implementa um classificador quadrático com várias populações descrito na Ref.[1]. A preparação dos dados das imagens para o classificador pode ser vistas na Figura 1.1.
 

Fig 1.1

            A idéia básica do sistema é segmentar uma imagem qualquer, identificar cada uma das classes da imagem, obter as características (média e variância, por exemplo) dos segmentos, treinar o classificador com um conjunto separado para treinamento e depois utilizar o conjunto de teste para avaliar o se desempenho através da taxa de erro e da matriz de confusão.  As etapas de segmentação e rotulagem estão descritas em [2]. Os passos principais do algoritmo de classificação são:
 

1º) Para cada segmento devidamente rotulado, calcular a média, a variância e identificar a qual classe o segmento pertence;

2º) Armazenar os resultados em duas matrizes M1 e M2, onde M1 é o conjunto de treinamento e M2 é o conjunto de teste;

3º) Treinar o classificador; e

4º) Utilizar o conjunto de teste para avaliar o desempenho do classificador.

            O cálculo da média e da variância e a etapa de distribuição dos elementos nas classes (passos 1 e 2) são escritos na Seção 2, já o classificador (passos 3 e 4) é descrito na Seção 3 deste relatório.
 
 

2. Preparação dos Dados

            Para a preparação dos dados, bem como o classificador, foi criado um programa principal que é responsável pela organização de todos os algoritmos. A seguir mostramos o código da função principal, que faz o papel do programa principal.
 

FUNCTION Principal, ima, n_classes, limites, n_segmentos

;segmentar a imagem
ima_seg = cMoveis(ima,n_segmentos)

;rotular a imagem
ima_rotulada = rerotular(ima_seg)
window,0, xsize=128, ysize=128
tvscl, congrid(ima_rotulada,128,128), 0

;Funcao que retorna uma matriz contendo a MEDIA, VARIANCIA e CLASSE
;à qual cada segmento pertence
Resposta = Prepara_Dados(ima, ima_rotulada, n_classes, limites)

;Ordena a matriz de resposta pelo NUMERO DA CLASSE
Resposta = Resposta[*,SORT(Resposta[2,*])]

s = SIZE(Resposta)

;Preparar o vetor que contem o numero de segmentos por classe.
SegmentosPorClasse = ContarSegementoClasse(Resposta, n_classes)

caract = FLTARR(2,s[2])
classeV = INTARR(FIX(TOTAL(segmentosPorClasse)/2))
classeV[0:CEIL(FLOAT(segmentosPorClasse[0])/2)-1] = 0
contc = CEIL(FLOAT(segmentosPorClasse[0])/2)
FOR i=1, n_classes-1 DO BEGIN
 classeV[contc:contc+ceil(float(segmentosPorClasse[i])/2)-2]=i
 contc = contc + ceil(float(segmentosPorClasse[i])/2)
ENDFOR

caract[0,*] = Resposta[0,*]
caract[1,*] = Resposta[1,*]

; Separa dados de teste e treinamento
vet_teste = FLTARR(2,TOTAL(SegmentosPorClasse)/2)
vet_trein = FLTARR(2,TOTAL(SegmentosPorClasse)/2)
contador = 0
cont_trein = 0
cont_test = 0
FOR i = 0, n_classes-1 DO BEGIN
 FOR j=0, (SegmentosPorClasse[i]/2)-1 DO BEGIN
  ;treinamento
  vet_trein[*,j+cont_trein] = caract[*,j + contador]
 ENDFOR
 cont_trein = cont_trein + SegmentosPorClasse[i]/2
 FOR j=0, (SegmentosPorClasse[i]/2)-1 DO BEGIN
   ;teste
   vet_teste[*,j+cont_test] = caract[*,j+cont_test+cont_trein]
 ENDFOR
 cont_test = cont_test + SegmentosPorClasse[i]/2
 contador = contador + SegmentosPorClasse[i]
ENDFOR

classeQ = classQuad(vet_trein,vet_teste,SegmentosPorClasse/2)
matC = matConf(classeV, classeQ, SegmentosPorClasse/2)
RETURN, matC
END

               Para a realização do primeiro passo do algoritmo (cálculo da média, variância e identificação da classe), utilizamos uma imagem Is (por exemplo, figura 2.1) de segmentos já rotulados, correspondeste à imagem original Io, e que fora obtida pelos algoritmos desenvolvidos em [2].
 

1 2 2 3 3
1 2 2 4 3
1
4
4
4
3
4 4 4 4 3
5 6 6 3 3
Fig 2.1: Segmentos rotulados.

            Aplicamos então a função Prepara_Dados(ima, ima_rot, num_classes, coordenadas), que recebe como parâmetros a imagem original Io, a imagem rotulada Is, o número de classes visualmente identificáveis na imagem Io e os limites desta classe. Considere uma imagem original Io como a da figura 2.2.
 

Fig 2.2: Imagem original.

            Podemos definir visualmente quatro classes nesta imagem (nuvem - C2, pirâmide C3, céu C1 e terreno C4). Definidas as classes, precisamos definir a área ocupada por cada uma delas através de seus limites. Uma observação a ser feita é que os limites (vetor contendo o pixel inicial e a largura da região) definirão áreas quadradas, as quais tentarão aproximar a área desejada da classe na imagem real, como mostrado na figura 2.2. O quadrado pontilhado define a classe nuvem, o quadrado tracejado-grande define a classe pirâmide, o quadrado traço-cheio define a classe céu e o quadrado tracejado-pequeno define a classe chão.

            A seguir mostramos o código da função Prepara_Dados:
 

FUNCTION Prepara_Dados, ima, ima_rot, num_classes, coordenadas

num_segmentos = MAX(ima_rot)+1
Descri=fltarr(3,num_segmentos)

;o tamanho de ima e ima_rot são os mesmos.
s = SIZE(ima)

contador = 0
;Para cada segmento
FOR i=0, MAX(ima_rot) DO BEGIN
 segmento = WHERE(ima_rot EQ i)
 sair = 0
 j=0
 ;descri[2,contador]=-1
 ;Para cada classe
 WHILE (j LE (num_classes-1)) AND (sair EQ 0) DO BEGIN
    classe = Formar_Vetor (coordenadas[j,0],coordenadas[j,1],s[1])

IF (Interseccao(classe,segmento)GE(0.7*N_ELEMENTS(segmento))) THEN BEGIN
  sair = 1
  ;calcula media e variancia do segmento
  if (n_elements(segmento) gt 1) then begin
      mome = MOMENT(ima(segmento))
   Descri[0,contador] = mome(0)
   Descri[1,contador] = mome(1)
  endif else begin
   Descri[0,contador] = ima(segmento)
   Descri[1,contador] = 0
  endelse

  ;Inserir a classe na matriz de dados
  Descri[2,contador]=j+1
  contador = contador + 1
         ENDIF
  j=j+1
 ENDWHILE
ENDFOR
Dados = Descri[*,0:contador-1]
RETURN, Dados
END

             Este função vai, para cada segmento, verificar a que classe este segmento pertence. Saber a que classe um segmento pertence é saber em qual das classes definidas pelo usuário pelo menos 70% dos pixels deste segmento está contido. Para tal foi necessária a definição de duas novas funções, chamadas Formar_Vetor e Interseccao.

            A função Formar_Vetor é responsável pelo preenchimento de um vetor com os índices de todos os pixels de uma janela quadrada qualquer. Utiliza como parâmetros a posição inicial da janela, a largura da janela e a largura da imagem sobre qual a janela foi definida.
 

FUNCTION Formar_Vetor, Posi_Ini, Lar_Jan, Lar_Ima
 vetor = lonarr(Lar_Jan*Lar_Jan)
 contador=-1
 FOR i=0, Lar_Jan - 1 DO BEGIN
  FOR j=0, Lar_Jan -1 DO BEGIN
     contador = contador +1
     vetor[contador]=Posi_Ini + (i*Lar_Ima) + j
  ENDFOR
 ENDFOR
RETURN, vetor
END

            A função Interseccao conta  quantos pontos de um determinado segmento estão presentes na área de uma determinada classe.  O programa Prepara_Dados utiliza este valor para saber o percentual de pontos do segmento que está contido na classe. Os parâmetros utilizados são os números da classe e do segmento que estão sendo analisados.
 

FUNCTION Interseccao, Classe, Segmento
 num_elementos = 0
 FOR i=0, N_ELEMENTS(Segmento)-1 DO BEGIN
  a = WHERE(Classe EQ Segmento(i), controle)
  IF (controle NE 0) THEN num_elementos = num_elementos + 1
 ENDFOR
RETURN, num_elementos
END

             A contagem do número de pixels é feita de classe a classe, até que se encontre uma com um número procurado de pixels ou que não exista mais classes a serem examinadas. Para cada segmento verificado e que tenha sido rotulado como pertencente a uma classe, calcula-se a média e a variância do valor dos pixels deste segmento na imagem original Io. Os valores são armazenados em uma matriz chamada Descri e que tem a seguinte forma:

Descri
Média Variância Número da Classe

            O segundo passo do programa principal é obter as matrizes M1 e M2 para separar o conjunto de treinamento e o conjunto de teste. A primeira função criada foi a função
 

FUNCTION ContarSegementoClasse, MatrizDados, Num_Classes
 Resultado = intarr(Num_Classes)
 FOR i=1, Num_Classes DO BEGIN
   a = WHERE(MatrizDados[2,*] EQ i, controle)
IF (controle NE 0) THEN Resultado[i-1]=N_ELEMENTS(a) $ 
ELSE Resultado[i-1]=0
 ENDFOR
 Resultado=TRANSPOSE(Resultado)
RETURN, Resultado
END

que conta o número de segmentos que foram rotulados para cada uma das classes. A partir deste ponto, as matrizes de treinamento e teste são geradas, vet_trein e vet_teste respectivamente, e depois passadas para o classificador.
 
 

3. Classificador Quadrático

            O classificador implementado neste projeto se baseia na minimização do custo esperado no erro de classificação (ECM Espected Cost Misclassification ), que é definido para g classes como
 

onde pi é a probabilidade a priori da classe i, c(k|i) é o custo de classificar um objeto na classe k quando ele é, na verdade, da classe i, e P(k|i) é a probabilidade de classificar um objeto na classe i quando, na verdade, ele é da classe k. Explicitamente, P(k|i) é dado em função da densidade de probabilidade multivariada, fi(x), dos dados da população i, como
onde x é associado as observações da variável aleatória X de dimensão p  e  Rk é a região que representa a população k num espaço p-dimensional. Considere a densidade de
 

probabilidade  fi(x) é a distribuição normal,
 

onde mi é o vetor de médias e Si é a matriz de covariância. Se considerarmos c(k|i)=1,
k¹ i e c(i|i)=0, obtemos o discriminante quadrático para a i-ésima população
 

o maior discriminante dQi(x) minimiza o ECM. Portanto, podemos definir a regra o classificador como:
 

            Temos também a função classQuad que é a implementação do classificador quadrático. Esta função recebe um vetor com dados de treinamento, um vetor com os dados a serem classificados (já abordados no tópico anterior), e um vetor com as classes que os elementos do vetor de treinamento pertencem.
 

FUNCTION classQuad, vet_trein, vet_x, vet_nsclasse
p = .5
dimc = n_elements(vet_nsclasse)
dimt = size(vet_trein)
dimx = size(vet_x)
dQ = fltarr(dimc)
classe = intarr(dimx[2])
x = fltarr(dimx[1])
for c=0, dimx[2]-1 do begin
 cont = 0
 for i=0, dimc-1 do begin
  Xi = fltarr( dimt[1], vet_nsclasse[i] )
  for j=0, vet_nsclasse[i]-1 do $
   for k=0, dimt[1]-1 do $
    Xi[k,j] = vet_trein[k, j + cont]
  cont = cont + vet_nsclasse[i]
  xmed = vetorMedia(Xi)
  cov = matrizCov(Xi)
  for k=0, dimx[1]-1 do $
   x[k]=vet_x[k,c]
  dQ[i] = discriminante(x, cov, xmed, p)
 endfor
 classe[c] = where(dQ eq max(dQ))
   endfor
   RETURN, transpose(classe)
END

 

4. Resultados

            Para a simulação dos resultados, utilizaremos a imagem da figura 2.2 e o phanton abaixo:
 

Fig 4.1

            Na primeira simulação utilizamos a imagem da figura 2.2. Os limites das 4 classes identificadas nesta imagem são:
 

CLASSE
COORDENADA INICIAL
LARGURA DA JANELA
C1 (céu)
1195
79
C2 (nuvem) 
15122
39
C3 (pirâmide)
15974
93
C4 (terreno) 
34760
54

            Chamamos a função principal para os limites definidos acima e com o número de 5 segmentos. A partir da mesma, os seguintes dados foram obtidos:
 

Fig 4.2: Imagem Segmentada

CLASSE
SEGMENTOS
C1
930
C2
198
C3
1410
C4
11
Fig 4.3: Número de Segmentos Identificados por Classe

Fig 4.4: Matriz de Confusão

            Para o segunto experimento, utilzamos o phanton da figura 4.1 com os limites abaixo e obtivemos os seguintes resultados:
 
Fig 4.5: Imagem Segmentada

CLASSE
COORDENADA INICIAL
LARGURA DA JANELA
C1
0
21
C2
21
22
C3
41
21
Fig 4.6: Limites das três regiões criadas no phanton

Fig 4.7: Matriz de Confusão



5. Referências Bibliográficas

[1] Johnson, R. A.; Wichern, D. W.; Applied Mulvariate Statistical Analysis, Prentice-Hall, 4th edition, 1998.
[2] Dória, R.C.; Guedes, P.A.; Maximiano, J.C.N.; Tomaz, G.; Segmentação de Imagens Utilizando a Técnica dos Centros Móveis, Projeto da Disciplina Tópicos Avançados em Processamento de Imagens, Dep. de Informática - UFPE,1999.
 


Tópicos Avançados de Processamento de Imagens
Professor:
Francisco Tenório (fatc@di.ufpe.br)
Alunos:
Glauber Tomaz (gjfts@di.ufpe.br)
Júlio César N. Maximiano (jcnm@di.ufpe.br)
Paulo A. Guedes (pag@di.ufpe.br)
Rodrigo C. Dória (rcd@di.ufpe.br)

Página atualizada em 24/12/1999 por Júlio César.