Análise Estrutural de Sinais e Imagens
Structural Analysis of Signals and Images

MIDE/SIM
SCM

ATUALIZAÇÕES E CORREÇÕES
UPDATES AND CORRECTIONS

Geraldo L B Ramalho

gramalho@ifce.edu.br

rev. 00 - Setembro, 2017

lapisco.ifce.edu.br
tinyurl.com/SIM-SCM
bit.ly/SIM-SCM


Índice

Apresentação        3

Conceitos e definições para interpretação da
MIDE/SIM e da SCM
        4

Matriz de Interdependência Espacial - MIDE        8

Structural Co-occurrence Matrix - SCM        9

Gray Level Co-occurrence Matrix - GLCM        13

Outras representações da GLCM, MIDE/SIM e SCM        15

Aplicações da SCM        17

Características conhecidas da SCM        19

Agradecimentos        20

Referências Bibliográficas        21

ERRATA        22



Apresentação

Este documento apresenta os métodos MIDE/SIM (Ramalho et al., 2014) e SCM (Ramalho et al., 2016) usando uma notação matemática revisada e padronizada para ambos. Além de facilitar a interpretação de ambos os métodos, essa padronização visa facilitar a identificação das semelhanças e das diferenças entre eles e a GLCM (Haralick, Shanmugam e Dinstein, 1973). Adicionalmente, este documento apresenta explicações adicionais,  exemplos e sugestões de aplicação dos métodos MIDE/SIM e SCM.

No final do documento são apresentadas erratas cobrindo a 1a. Edição do Livro Análise Estrutural de Imagens Aplicada à Visão Computacional (ISBN 978-85-64778-63-4) e eventuais falhas encontradas em outras publicações do tema.

O documento está em constante atualização e é de total responsabilidade do autor.


Conceitos e definições para interpretação da
MIDE/SIM e da SCM

Imagem (sinal bidimensional): refere-se a uma imagem digital em cores, em geral capturada de uma cena usando um sensor matricial de m linhas e n colunas com profundidade de b bits para cada elemento da matriz em um arranjo tridimensional , sendo que cada elemento da matriz é um vetor que contém os valores R (vermelho), G (verde) e B (azul) que combinados formam diferentes intensidades, matizes e saturação de cores.

Imagem em níveis de cinza: refere-se a uma imagem digital representada por uma matriz , sendo que cada elemento corresponde ao valor de intensidade i.

Pixel: menor elemento de uma imagem, definido por uma posição p em um espaço bidimensional representado por uma matriz de tamanho . Cada pixel possui um valor  (R,G,B) em que representa uma cor no padrão RGB (no caso de imagens em cores) ou um valor de intensidade I (no caso de imagens em níveis de cinza). O valor da cor c ou da intensidade i do pixel p, na coordenada , de uma imagem f é representado por  ou .

Estrutura: região da imagem, formada por aglomerados de pixels cujos níveis de cinza possuem alguma relação entre si e que definem um objeto ou parte de um objeto.

Exemplo:

                

Estruturas bem definidas que lembram asas, cauda e fuselagem de um avião

Estruturas desorganizadas dificultam a interpretação da cena

Saliência: parte de uma estrutura, de um objeto ou de uma cena que se destaca por apresentar alguma característica diferente da sua vizinhança.

Exemplo:

                        

Objetos destacados com círculo são salientes em relação aos objetos vizinhos

Transformação estrutural: uma modificação dos valores dos pixels que formam uma estrutura de tal maneira que uma nova estrutura emerge da nova relação entre os valores desses pixels. O ruído, a atenuação e o aguçamento são tipos de transformação estrutural.

Exemplo:

                

Estruturas bem definidas que lembram asas, cauda e fuselagem de um avião

Asas e causa estão menos evidentes em uma imagem suavizada por um filtro passa-baixa

Escala estrutural: as relações entre os valores dos pixels de uma estrutura definem diferentes escalas dessas estruturas e a percepção do objeto na cena. Essas relações dependem diretamente da quantidade de níveis de quantização que permite agrupar estruturas menores em outras maiores formando partes de objetos ou objetos inteiros. Além da quantização, outra forma de redefinir relações de escala de estrutura incluem representação em superpixels, segmentação e transformações estruturais.

Exemplo:

                

Estruturas de menor escala permitem perceber detalhes como asas e cauda do avião

Um aglomerado de estruturas pequenas permite perceber o contorno do avião como uma estrutura única

Notação matemática

Definição de imagem:

Seja [1] uma imagem definida como um matriz de intensidades de pixel . O pixel  é uma posição na imagem f , dado que , .

Definição de propriedade entre pixels:

Considere dois pixels  e ,  é uma propriedade que assume valor verdade se for satisfeita uma condição que define uma relação arbitrária entre os pixels p e q. Como resultado da escolha de P, a contagem das coocorrências pode ser restringida a um dos quadrantes da matriz.

Exemplo 1:

Considere  uma propriedade entre p e q que assume valor verdade se , sendo  um conjunto de deslocamentos das coordenadas , de tal forma que  é uma propriedade verdade para todos os deslocamentos d. Essa propriedade permite limitar a análise a uma região na vizinhança do pixel p.

Exemplo 2:

Considere  uma propriedade entre p e q que assume valor verdade em todos os pixels nos quais , sendo l um limiar arbitrário. Essa propriedade restringe a análise às regiões menos semelhantes entre f e g, ou regiões de f e de g que são menos suscetíveis a mudanças estruturais. 

Definição de contagem:

Considere o cálculo do número de transições dos pixels de valor i  para os pixels de valor j,   de uma imagem digital definida por uma função   em níveis de cinza, de forma que  e , em que p e q  definem a posição de um pixel e seu vizinho, respectivamente, na imagem f. A frequência de cada ocorrência do par , dada uma propriedade  que determina se p e q atendem a um critério arbitrário de vizinhança, para dado i e j, é definida por

 

Exemplo:

Considere  uma propriedade booleana, verdadeira se , em que   define um conjunto de deslocamentos, ou seja,  e . Portanto,


Matriz de Interdependência Espacial - MIDE


Spatial Interdependence Matrix - SIM
Ramalho, GLB; Rebouças Filho, PP; de Medeiros, FNS; Cortez, PC.
Lung disease detection using feature extraction and extreme learning machine. RBEB, v.30, n.3, pp. 1-8, 2014.

A MIDE/SIM que registra o número de transições do pixel de valor i de uma imagem quantizada  para o pixel de valor j de uma imagem quantizada , sendo  e , em que  e , p e q , determinam as posições dos pixels nas imagem f e g, respectivamente, dada uma relação espacial  entre os pixels de p e q. Portanto, para dado i e j, os elementos da matriz são definidos por  

Exemplos: Considere f e g duas imagens de mesmas dimensões quantizadas nos níveis de cinza .  define um deslocamento  em uma direção  de tal forma que  é verdade se . Se . A coluna 6 das imagens não é considerada.

1

2

3

4

5

6

1

0

0

2

0

0

3

2

0

0

1

0

2

3

3

0

0

2

0

0

3

4

3

0

0

0

0

0

Imagem

1

2

3

4

5

6

1

0

0

2

0

0

3

2

0

0

3

0

3

3

3

0

0

2

0

0

3

4

0

0

0

0

0

0

Imagem g

MIDE 

0

1

2

3

0

16

0

0

0

1

0

0

0

1

2

0

0

2

1

3

1

0

0

3

MIDE , d = 1

0

1

2

3

0

9

0

2

4

1

1

0

0

0

2

2

0

0

1

3

1

0

0

0

Structural Co-occurrence Matrix - SCM


Ramalho, GLB; Ferreira, DS; Rebouças Filho, PP; de Medeiros, FNS.
Rotation-invariant feature extraction using a structural co-occurrence matrix. Measurement, v.94, pp. 406-415, 2016.

Na SCM, dada uma propriedade  entre elementos dos sinais de entrada  e  e considerando uma função de particionamento  que define a escala das estruturas dos sinais de entrada, a matriz registra o número de transições do elemento de valor  do sinal quantizado  para o elemento de valor   do sinal g transformado pela função  e quantizado, ou seja . Sendo  e , em que  é a posição do elemento no sinal ,  é posição do elemento no sinal . Para dado  e , os elementos da matriz são definidos por

Q é uma função de particionamento do sinal que tem o objetivo de agrupar os elementos dos sinais formando estruturas em escalas conforme o número de níveis determinados pela quantização ou por meio de um método de agrupamento obtido por Total Variation, Superpixel, kNN, k-means, propriedades estatísticas como média e mediana, dentre outros.

SCM em análise de imagens:

No caso em que os sinais de entrada são imagens em níveis de cinza, ou seja,  e ,  é uma propriedade de similaridade que tem o objetivo de agrupar estruturas baseadas em uma vizinhança espacial ou por similaridade entre os níveis de cinza dos pixels  e . Por definição, podem ser empregados métodos como SOM, kNN, k-means, classificadores e redes neurais.

O deslocamento  possibilita definir relações espaciais entre os pixels em uma ou mais direções e em diferentes escalas. Essa propriedade modifica a configuração da matriz e permite, por exemplo, tornar a SCM invariante à translação.

Exemplo 1: Considere  e  duas imagens de mesmas dimensões quantizadas nos níveis de cinza . Considere que: i) a função k é um filtro passa-baixa, por exemplo  se  e , caso contrário; ii) o particionamento  é uma função de quantização que mapeia os valores dos pixels de  como, por exemplo:  e , em que  retorna a parte inteira de um número.  é uma propriedade verdadeira  para todo .  é uma propriedade verdadeira (true) para todo  e , e neste caso a matriz resultante será uma triangular superior.  é uma propriedade verdadeira  para todo   e , e neste caso as regiões mais homogêneas determinadas por um limiar de similaridade l entre os valores dos pixels não são avaliadas.

1

2

3

4

5

6

1

0

50

200

50

50

300

2

0

50

100

50

200

300

3

50

50

200

50

50

300

4

300

50

50

50

50

50

Imagem

1

2

3

4

5

6

1

0

50

200

50

50

300

2

0

50

300

50

300

300

3

0

50

200

50

50

300

4

0

50

50

50

50

50

Imagem g

1

2

3

4

5

6

1

0

50

200

50

50

200

2

0

50

200

50

200

200

3

0

50

200

50

50

200

4

0

50

50

50

50

0

Imagem

1

2

3

4

5

6

1

0

0

2

0

0

3

2

0

0

1

0

2

3

3

0

0

2

0

0

3

4

3

0

0

0

0

0

Imagem  

1

2

3

4

5

6

1

0

0

3

0

0

3

2

0

0

3

0

3

3

3

0

0

3

0

0

3

4

0

0

0

0

0

0

Imagem  

SCM

0

1

2

3

0

16

0

0

0

1

0

0

0

1

2

0

0

0

3

3

1

0

0

3

SCM         

0

1

2

3

0

16

0

0

0

1

0

0

0

0

2

0

0

0

3

3

1

0

0

3

MIDE  

 

0

1

2

3

0

16

0

0

0

1

0

0

0

1

2

0

0

2

1

3

1

0

0

3

SCM  

0

1

2

3

0

16

0

0

0

1

0

0

0

1

2

0

0

2

1

3

1

0

0

3

SCM

0

1

2

3

0

0

0

0

0

1

0

0

1

0

2

0

0

0

0

3

1

0

3

0

SCM

0

1

2

3

0

0

0

0

0

1

0

0

0

0

2

0

0

0

0

3

1

0

0

0

Exemplo 2: Atenuação de estruturas de diferentes escalas. Considere g uma cópia atenuada do sinal f. A figura da direita destaca 3 regiões (retângulos em linha contínua) em que a diferença estrutural é significativa, sendo que uma delas possui escala maior (com 3 elementos) do que as outras duas (com 1 elemento cada).

 SCM k = filtro passa-baixa

0

1

2

3

0

1

1

0

0

1

0

4

0

0

2

0

0

4

0

3

0

0

1

0

 SCM k = filtro passa-alta

        

0

1

2

3

0

2

0

0

0

1

3

0

0

0

2

0

3

3

1

3

2

0

0

0


Gray Level Co-occurrence Matrix - GLCM


Haralick, RM; Shanmugam, K; Dinstein, I. Textural features for image classification.
IEEE Transactions on Systems, Man and Cybernetics. v.3, n.6, pp. 610-21, 1973.

A GLCM calcula o número de transições do pixel de valor i para o pixel de valor j de uma imagem quantizada f, sendo  e , em que  é a posição do pixel na imagem f  e  define um deslocamento na direção  de forma que . Os elementos da matriz, para dado i e j, são definidos por .

Observe que, para:

Exemplo: Considere f uma imagem quantizada nos níveis de cinza .

Example: Consider f  a quantized image of gray levels .

1

2

3

4

5

6

1

0

0

2

0

0

3

2

0

0

1

0

2

3

3

0

0

2

0

0

3

4

3

0

0

0

0

0

Imagem f 

GLCM  (asymmetric; ignores column 6)

0

1

2

3

0

9

1

3

2

1

1

0

0

0

2

2

0

0

1

3

0

0

0

1

Nota 1: a GLCM pode ser vista como um caso particular da MIDE se  e  sendo  um deslocamento em uma direção específica ,

GLCM  (asymmetric)

0

1

2

3

0

9

1

3

2

1

1

0

0

0

2

2

0

0

1

3

0

0

0

0

MIDE  

0

1

2

3

0

9

1

3

2

1

1

0

0

0

2

2

0

0

1

3

0

0

0

0

Nota 2: a GLCM pode ser vista como um caso particular da SCM se g = f, k é uma função identidade ou seja, ,  é uma quantização para L níveis de cinza e  é uma propriedade verdadeira para todo . Dado ,  e, simplificando , tem-se que .

GLCM  (ignores column 6)

 

0

1

2

3

0

9

1

3

2

1

1

0

0

0

2

2

0

0

1

3

0

0

0

0

SCM

 

0

1

2

3

0

9

1

3

2

1

1

0

0

0

2

2

0

0

1

3

0

0

0

0


Outras representações da GLCM, MIDE/SIM e SCM

GLCM:

MIDE/SIM:

SCM:


Aplicações da SCM

Análise referenciada de imagens ou sinais: entrada = 2 imagens (2D) ou 2 sinais (1D)

Caso os sinais de entrada sejam binários, uma transformação para níveis de cinza torna a SCM mais precisa. Recomenda-se o uso da TEM (Transformação Estrutural Multiescala, explicada no livro) ou da transformada da distância como função Q.

Exemplo 1:

Considere a análise de dois sinais, conforme a figura abaixo, em que um deles não possui informação conhecida ou a informação contém apenas ruído em um determinado período de amostragem. Neste caso, é interessante limitar a análise apenas às áreas (região central em linha contínua) em que a diferença estrutural entre os dois sinais é representativa (região cinza da figura em linha tracejada). Assim, define-se uma propriedade .

Extração de características: entrada = 1 imagem (2D) ou 1 sinal (1D)

A função de transformação  deve ser escolhida de forma a produzir modificações nas estruturas que se deseja detectar. Se não houver conhecimento prévio sobre as estruturas da imagem, deve-se realizar testes de agrupamento dos atributos a partir de  com filtros passa-baixa e passa-alta. Os filtros passa-baixa atenuam estruturas salientes de alta frequência como bordas, contornos, e cantos. Os filtros passa-alta realçam essas mesmas estruturas. A SCM consegue capturar mudanças globais significativas nas estruturas. Entretanto, se a influência dessas estruturas for pequena, é possível que os atributos obtidos com a SCM não sejam suficientemente distinguíveis entre grupos distintos de imagens. Isto pode ser resolvido com a escolha adequada da função de particionamento , diminuindo a escala das estruturas, ou da propriedade , definindo um critério de similaridade/dissimilaridade.


Características conhecidas da SCM

Invariância à rotação:

Quando utilizada como extrator de características,  e, portanto, qualquer rotação aplicada a  não produz influência no resultado da SCM.

Nota: Nesse tipo de aplicação, uma translação aplicada a  também não muda o resultado da SCM. Entretanto, a invariância se refere à análise de estruturas que podem aparecer em diferentes orientações em uma mesma cena ou em cenas diferentes. Obviamente o resultado da SCM será diferente para uma estruturas semelhantes se aparecem em regiões diferentes da imagem.

Contraste:

A SCM produz resultados diferentes quando avalia imagens de uma mesma cena mas com contrastes distintos. Mesmo que os sinais de entrada sejam normalizados de forma que os valores de ambos estejam dentro de um mesmo intervalo, a matriz tenderá a possuir pesos diferentes nos quatro quadrantes, dependendo do contraste e do nível DC dos sinais.

Nota: Escolhidos adequadamente, a propriedade , a função de particionamento   e a função de transformação , podem contribuir para diminuir a sensibilidade da SCM ao contraste dos sinais de entrada.


Agradecimentos

Ao Prof. Dr. Amauri Holanda de Souza Júnior e ao Prof. Dr. Euripedes Carvalho da Silva, ambos do IFCE, pelos esclarecimentos quanto à notação matemática e pelas sugestões de melhoria.


Referências Bibliográficas

Haralick, R.M.; Shanmugam, K.; Dinstein, I. Textural features for image classification. IEEE Transactions on Systems, Man and Cybernetics. v.3, n.6, pp. 610-21, 1973.

Ramalho, G.L.B.; de Medeiros, F.N.S. Análise estrutural de imagens aplicada à visão computacional. Imprima: Recife, 2017. 222 p.

Ramalho, G.L.B.; Rebouças Filho, P.P.; de Medeiros, F.N.S.; Cortez, P.C. Lung disease detection using feature extraction and extreme learning machine. Revista Brasileira de Engenharia Biomédica - RBEB, v.30, n.3, pp. 1-8, 2014.

Ramalho, G.L.B.; Ferreira, D.S.; Rebouças Filho, P.P.; de Medeiros, F.N.S. Rotation-invariant feature extraction using a structural co-occurrence matrix. Measurement, v.94, pp. 406-415, 2016.


ERRATA

capa livro MIDE 2 peq.png

Livro Análise estrutural de imagens aplicada à visão computacional, 1a. ed.

ISBN 978-85-64778-63-4

Lombada

ERRO: primeiro nome do segundo autor aparece em local errado.

CORREÇÃO: nome dos autores: Geraldo Luis Bezerra Ramalho e Fátima Nelsizeuma Sombra de Medeiros.

Equação 4.1, pág. 45

ERRO:

CORREÇÃO:

COMPLEMENTO: Sejam I:  e J:  imagens definidas como matrizes de intensidades de pixel I=  e J= . Considere  e  as posições dos pixels das imagens I e J, respectivamente, dado que , . Considere  uma propriedade entre p e q que assume valor verdade se , sendo  um conjunto de deslocamentos das coordenadas de . Se , então p = q, ou seja, q e p correspondem a uma mesma posição no domínio espacial das imagens I e J . A relação espacial pode então ser definida na equação .

Figura 6.1, pág. 87

ERRO: A ilustração não aparece na figura.

CORREÇÃO: A figura correta completa é mostrada abaixo.

Figura 6.1: Conceito de dimensão fractal de um sinal unidimensional.



[1] conjunto dos números naturais