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 .