Upload
trandien
View
218
Download
0
Embed Size (px)
Citation preview
Reconstrução de imagens de tomografia por impedância
elétrica usando elementos finitos, fuzzy c-médias e
programação evolucionária
Leonardo R. Ribeiro¹, Mêuser J. S. Valença¹ e Wellington P. dos Santos²
¹ Escola Politécnica de Pernambuco – Universidade de Pernambuco
Rua Benfica, Madalena, 50720-001, Recife, PE.
E-mail: [email protected], [email protected]
² Departamento de Engenharia Biomédica – Universidade Federal de Pernambuco
Av. Prof. Moraes Rego, 1235 – Cidade Universitária, 50670-901, Recife, PE.
E-mail: [email protected]
Abstract. This article presents a quantitative comparison among four group-
ing algorithms – K-SOM, K-means, K-means optimized with evolutionary pro-
gramming and Fuzzy C-means – all applied to reconstructed electrical imped-
ance tomographic images generated from EIDORS (Electrical Impedance and
Diffuse Optical Tomography Reconstruction Software). EIDORS is an extensi-
ble software base for EIT (Electrical Impedance Tomography) researchers. It
solves the main equation of EIT, the Laplace’s equation, resulting in recon-
structed smooth images with no definition of boundaries. Grouping algorithms
are used to quantize the resulting reconstructed images from EIDORS in order
to get better defined EIT images boundaries. To compare the grouping algo-
rithms we used the Omran combined index that unites three of the main criteria
used to validate the best grouping process.
Keywords: Grouping Algorithms, K-SOM, K-means, Fuzzy C-means, Electri-
cal Impedance Tomography, Omran Index.
1 Introdução
A Tomografia por Impedância Elétrica (TIE) é uma técnica não-invasiva de imagem
para diagnóstico que consiste na obtenção da imagem no interior da seção de um cor-
po a partir do mapeamento computacional das condutividades e permissividades em
seu interior. Ela é baseada na injeção de corrente elétrica alternada de baixa frequên-
cia [1] e da medição dos potenciais de fronteira resultantes. O cálculo dos potenciais
nos eletrodos a partir da injeção de corrente é caracterizado como o problema direto
da TIE [2]. Já a estimativa da distribuição de condutividades no interior do corpo a
partir dos potenciais medidos caracteriza o problema inverso da TIE [3].
746 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
O simulador EIDORS (Electrical Impedance and Diffuse Optical Tomography
Reconstruction Software) [4], plataforma com código aberto construída em Matlab e
Octave, simula os problemas direto e inverso e os resolve, apresentando, por fim, uma
imagem que representa a distribuição de condutividades do interior de uma região.
As imagens de TIE reconstruídas pelo EIDORS, entretanto, ainda apresentam
característica nebulosa, sem definição das bordas. Em resumo, as imagens de TIE
reconstruídas pelo EIDORS exibem baixa resolução se comparadas a outras técnicas
de tomografia utilizadas. A TIE, contudo, possui vantagens que tornam viável sua
aplicação clínica e pesquisas na área, como, por exemplo, baixo custo e ausência de
radiação ionizante.
No intuito de melhorar a definição das bordas e realçar a região de interesse das
imagens reconstruídas pelo EIDORS, algoritmos de aprendizagem não-
supervisionada baseados em métodos de agrupamento são utilizados. Dentre eles,
citam-se os mapas auto-organizáveis de Kohonen (K-SOM) [5], Mapas de K-médias e
Mapas de K-médias otimizado por programação evolucionária [6].
Neste trabalho é apresentada uma análise comparativa entre os algoritmos de
agrupamento K-SOM, Mapas de K-Médias e Mapas de K-médias otimizado por pro-
gramação evolucionária, com o algoritmo de agrupamento Mapas Fuzzy C-médias,
todos aplicados na classificação e quantização de imagens de TIE reconstruídas pelo
simulador EIDORS. As imagens classificadas e quantizadas foram geradas na ferra-
menta AnImed [7] [6]. A análise comparativa foi realizada de forma quantitativa,
tomando-se como base o índice combinado de Omran [7] [8], uma medida de valida-
ção de agrupamento que une os três critérios de validação de agrupamento: a minimi-
zação do erro de distorção de quantização, a separação dos grupos resultantes e a
coesão de pontos em torno do centróide do grupo.
O objetivo do uso dos Mapas Fuzzy C-Médias é classificar os pixels das ima-
gens reconstruídas pelo EIDORS considerando que eles podem pertencer a dois ou
mais grupos dependendo do seu grau de pertinência. Diferentemente do K-SOM,
Mapas de K-médias e Mapas de K-Médias otimizado onde o pixel é classificado em
apenas um grupo.
Este artigo está organizado da seguinte forma: (2) Materiais e Métodos. Essa se-
ção apresenta conceitos e os materiais e métodos utilizados para a obtenção dos resul-
tados; (3) Resultados. Essa sessão apresenta os resultados obtidos; (4) Conclusão.
Apresenta a análise dos resultados e conclui o trabalho; (5) Referências.
2 Materiais e Métodos
2.1 Tomografia por Impedância Elétrica
Tomografia por Impedância Elétrica é uma técnica não invasiva de imagem para di-
agnóstico onde uma corrente elétrica alternada, de baixa freqüência, é aplicada, de
acordo com um padrão de excitação elétrica, através dos eletrodos dispostos em torno
da superfície da seção do corpo. O potencial resultante é então medido nos eletrodos.
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 747
A partir dessas medições, um algoritmo de reconstrução é aplicado de forma a estimar
a distribuição de condutividades da seção do corpo em estudo. A representação com-
putacional dessa distribuição estimada é a imagem reconstruída da TIE.
A formulação matemática da TIE corresponde à uma equação diferencial parcial
(EDP) que rege o potencial e às condições de contorno. As condições de contorno
dependem da forma do processo de estímulo e resposta [9]. Nesse trabalho, utilizam-
se como estímulo a injeção de correntes alternadas e como resposta a medição do
potencial nos eletrodos. A derivação da EDP a seguir se faz a partir das equações de
Maxwell, que governam as interações da eletricidade e magnetismo em um problema
físico.
( ) ( )
A equação (1) é uma equação diferencial parcial (EDP) elíptica de segunda or-
dem conhecida como equação de difusão com coeficientes variáveis que rege a distri-
buição do potencial no meio condutivo Ω sendo σ a condutividade elétrica em seu
interior. Ela é também conhecida como Equação de Laplace que rege o potencial no
interior da seção nos casos que a freqüência da corrente de excitação é inferior a
30MHz [10].
O problema direto da TIE consiste na determinação da distribuição de poten-
ciais, , dado o padrão de corrente injetada e a distribuição de condutividades, σ. Já o
problema inverso da TIE consiste na obtenção da distribuição de condutividades, σ,
dado os potenciais medidos na fronteira e o padrão de corrente injetada.
Atualmente, os métodos mais utilizados para solução do problema direto são o
MDF (Método das Diferenças Finitas) e o MEF (Método dos Elementos Finitos) [10]
[11]. O primeiro discretiza a região de interesse e aproxima a equação de Laplace em
cada ponto da grade. Já o MEF divide a região de interesse em uma grade de figuras
geométricas conhecidas como elementos finitos e aproxima a Equação de Laplace em
cada elemento de forma que a solução de todos os elementos reunidos é a solução da
malha completa. Merece destaque também MEC (Método dos Elementos de Contor-
no) como alternativa ao MEF [12].
No que se refere a solução do problema inverso da TIE, os métodos utilizados
para a sua solução podem ser classificados em não-iterativos (lineares) e iterativos
(não lineares). Nos métodos lineares assume-se que a distribuição do potencial elétri-
co é uma função linear da distribuição de impedâncias. Destacam-se algoritmos como
backprojection [13], aproximação de Calderón [15] e os métodos de momentos [14].
Os algoritmos iterativos, ou não-lineares, consideram a não-linearidade do problema
levando a resultados mais precisos, contudo com um custo computacional mais eleva-
do. A estratégia adotada é a solução da Equação de Laplace no domínio em estudo
para obtenção dos potenciais e fronteira a partir de uma distribuição inicial de impe-
dâncias (conhecimento a priori). Os potenciais de fronteira calculados são então com-
parados com os potenciais de fronteira medidos. A diferença é utilizada para ajustar a
distribuição de impedâncias de forma que, a cada iteração, os potenciais calculados se
748 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
aproximem dos potenciais medidos. Destacam-se, entre os métodos iterativos, alguns
baseados no método de Newton-Raphson como o método de Gauss-Newton, o Modi-
fied Newton-Raphson (MNR) [17] e o Newton’s One Step Error Reconstructor
(NOSER) [16]. Citam-se também o método de Otimização Topológica
[18] e métodos baseados no filtro de Kalman [19].
2.2 Elementos Finitos e EIDORS
O EIDORS, Electrical Impedance and Diffuse Optical Tomography Reconstruction
Software, é uma ferramenta para reconstrução de imagens de Tomografia por Impe-
dância Elétrica e Tomografia de Óptica Difusa (ainda não implementada pelo projeto
EIDORS), cujo objetivo é oferecer um software de reconstrução de imagem que seja
distribuído e também modificável livremente. O EIDORS permite que sejam constru-
ídas referências com a finalidade de se realizarem comparações com novos sistemas e
métodos, bem como permitir que novas ideias sejam construídas e devidamente testa-
das. O fato de ser um código livremente modificável, o EIDORS possibilita que ou-
tros pesquisadores possam criticar e expandir os algoritmos originais, bem como suas
implementações. A versão original do EIDORS (versão1) está baseada no software da
tese de Vaukhonen [20]. A versão1 do EIDORS consiste em um pacote do MATLAB
para a geração de malhas bidimensionais, solução do problema direto e exibição das
imagens [21].
O simulador EIDORS é utilizado para resolver dois diferentes problemas ine-
rentes à técnica de TIE. O primeiro deles é o problema direto, que está associado à
solução da equação elíptica de difusão, equação (1). Ao se resolver o problema direto
lança-se mão do Método dos Elementos Finitos (MEF) que busca linearizar as equa-
ções atribuindo-se valores a coeficientes desconhecidos e, depois, resolve-se um sis-
tema de equações lineares a fim de se atualizarem os coeficientes [21]. O EIDORS faz
uso de um pacote do MATLAB para gerar malhas bidimensionais, resolver o proble-
ma direto, através do Método dos Elementos Finitos, e exibir as imagens. O segundo
problema de TIE tratado pelo EIDORS reside no cálculo do problema inverso, consi-
derado um problema mal posto, dado que os potenciais no interior da estrutura de
interesse dependem fortemente das impedâncias, além de erros de quantização, intro-
duzidos pelo Método dos Elementos Finitos, bem como aqueles associados às medi-
ções [22]. O problema inverso é resolvido de modo iterativo, por meio da minimiza-
ção de uma função objetivo encontrando por fim uma melhor solução para a distribui-
ção de resistividades do domínio em questão [23]. O EIDORS usa um solucionador
não linear regularizado a fim de encontrar a única e estável solução para o problema
inverso [22]. Como exemplo utiliza-se, para a reconstrução das imagens, o método
iterativo de Gauss-Newton.
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 749
2.3 Mapas Auto-Organizáveis de Kohonen
As redes de Kohonen tem inspiração neurofísiológica sendo baseadas em observações
do funcionamento cerebral, onde o aprendizado não supervisionado é predominante.
Os mapas auto-organizáveis de Kohonen são analogias a forma lógica de organização
das informações no cérebro [24] e sua principal utilização é agrupar as entradas que
são semelhantes entre si formando classes ou agrupamentos denominados clusters
[25]. Os mapas auto-organizáveis de Kohonen, em geral, podem ser unidimensionais
ou bidimensionais e tem por base um aprendizado competitivo de forma que se faz
necessário uma função objetivo para definir um neurônio vencedor.
Uma das métricas mais utilizadas é a distância euclidiana entre as entradas e o
conjunto de pesos dos neurônios definida por:
√∑( )
( )
onde são os exemplos de entrada da rede e são os pesos do neurônios que co-
nectam a entrada à saída . Definido o neurônio vencedor, seus pesos são ajustados de acordo com a forma
de processo competitivo. Existem duas formas de processos competitivos: “o vence-
dor leva tudo” (winner take all) ou o “vencedor leva parte” (winner take quota). No
processo competitivo o “vencedor leva tudo”, apenas os pesos do neurônio vencedor
são ajustados. O novo peso é dado pela expressão:
( ) ( )
onde α é a taxa de aprendizado da rede e
é o novo peso do neurônio vencedor.
No processo competitivo “o vencedor leva parte”, os pesos dos neurônios vizi-
nhos ao neurônio vencedor também são ajustados. A vizinhança do neurônio vence-
dor é estabelecida pela função de vizinhança das quais destaca-se a função gaussiana,
obtida por:
( ) *
( )+ ( )
onde
( ) representa o valor da vizinhaça topológica entre o neurônio vizinho e
o neurônio vencedor, representa o número de iterações, σ a largura da região de
750 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
vizinhança e representa a distância entre o neurônio vencedor e o neurônio vizinho
excitado cujos pesos serão atualizados.
De forma a se obter uma organização do mapa topológico da rede e uma espe-
cialização maior dos neurônios, ou seja, uma convergência do algoritmo, é necessário
que a região de vizinhança decaia com o número de iterações. Dessa forma, a largura
da função de vizinhança, σ, deve decrescer com o número de iterações a partir da
seguinte expressão:
( ) ( ) [
] ( )
onde ( ) é o valor inicial da largura da função e é uma constante de tempo que faz
com que a largura da função decaia com o aumento do número de iterações.
No intuito de evitar que a rede “perca” o conhecimento adquirido e que se con-
sigam ajustes cada vez mais finos, é necessário que a taxa de aprendizagem também
decaia com o número de iterações. Para tal, utiliza-se a seguinte expressão:
( ) ( ) [
] ( )
onde é a constante de tempo que faz com que a taxa de aprendizagem decaia com o
aumento do número de iterações.
Com base no exposto, tem-se que o ajuste dos pesos de todos os neurônios den-
tro da região de vizinhança é dada por:
( ) ( )
2.4 Mapas de K-médias
O algoritmo de Mapas de K-médias é classificado como um método de agrupamento
particionado onde o número de clusters ou grupos, , é considerado fixo [47].
A ideia do algoritmo é fornecer uma classificação de informações de acordo com
os próprios dados. Essa classificação é baseada em análises e comparações entre os
valores numéricos dos dados. Dessa maneira, o algoritmo fornece automaticamente
uma classificação sem necessidade de uma supervisão humana sendo considerado
como um algoritmo de mineração de dados não supervisionado.
Considere um conjunto de dados representados por pontos no . O objetivo é
agrupar esses dados em grupos ou clusters. Primeiramente define-se em quantos
grupos o conjunto de dados serão agrupados. A partir daí, selecionam-se pontos
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 751
aleatórios ou do conjunto de dados. A esses pontos atribui-se o nome de centróides.
Calcula-se a distância euclidiana dos centróides para cada ponto do conjunto de da-
dos. Os dados são agrupados de acordo com sua distância em relação aos centróides.
As distâncias entre um ponto e os centróides são comparadas. O ponto será agrupa-
do pelo centróide ao qual sua distância é menor. Faz-se esse cálculo comparativo para
todos os pontos do conjunto de dados. Após o primeiro agrupamento, tem-se gru-
pos. Para cada grupo calcula-se um novo centróide através da média de todos os pon-
tos do agrupamento. As distâncias são novamente calculadas. O algoritmo se repete
até que se atinja o critério de parada definido como o número de iterações ou a con-
vergência, ou seja, quando não há variação no cálculo dos centróides.
2.5 Mapas de K-médias otimizado por programação evolucionária
O algoritmo de Mapas de K-médias otimizado por programação evolucionária [6] é
uma hibridização de duas técnicas de Computação Inteligente: O algoritmo de otimi-
zação de programação evolucionária e o algoritmo de agrupamento de Mapas de K-
médias.
A programação evolucionária é utilizada para, a partir da geração aleatória dos
vetores candidatos a centróides, otimizar a geração dos centróides do algoritmo K-
médias a partir de uma função objetivo a ser minimizada, da seleção e da mutação A
função objetivo utilizada nesse trabalho foi o índice combinado de Omram [27], que
será explanado na seção 2.5. Existem quatro tipos principais de algoritmos de pro-
gramação evolucionária cuja diferença encontra-se na distribuição de probabilidade
de mutação. São eles: o algoritmo CEP (Classical Evolutionary Programming), o
algoritmo FEP (Fast Evolutionary Programming), o algoritmo LEP (Lévy-Type Evo-
lutionary Programming) e o algoritmo SPMEP (Single-Point Mutation Evolutionary
Programming). Nesse trabalho, o algoritmo de programação evolucionária utilizado
para compor a técnica híbrida foi o CEP.
Após a geração dos centróides por programação evolucionária, o algoritmo de
agrupamento K-médias é aplicado. Os pontos são agrupados aos centróides aos quais
eles possuem menor distância euclidiana.
2.6 Mapas Fuzzy C-médias
A Lógica Nebulosa trata valores intermediários entre 0 e 1 ao invés de puramente
verdadeiros ou falsos. O algoritmo de Mapas Fuzzy C-médias [31] [30] é baseado em
Lógica Nebulosa e Mapas de K-médias. É um método de agrupamento onde os dados
podem pertencer a dois ou mais agrupamentos dependendo do seu grau de pertinência
em cada agrupamento. O Mapa Fuzzy C-Médias é uma rede neuro-fuzzy não supervi-
sionada bastante utilizada em aplicações de classificação de imagens de Ressonância
752 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
Magnética Nuclear e na detecção de regiões ativadas em Ressonância Magnética Nu-
clear funcional [7].
O algoritmo usa como entrada um conjunto de dados * + , o número de
classes, , a tabela de pertinência inicial, μ, cujos elementos, ( ), representam a
função de pertinência de à classe , e um expoente de nebulosidade [28]. O ex-
poente de nebulosidade é um inteiro maior que 1.
O agrupamento dos dados em tornos dos grupos consiste em minimizar a função
objetivo definida por [28] [29]:
∑∑ ( )
‖ ‖ ( )
onde é o vetor de pesos do i-ésimo neurônio.
Os neurônios possuem a expressão de saída :
( ) (∑ (‖ ‖
‖ ‖)
( )
)
( )
Os pesos são ajustados a partir da definição do neurônio vencedor. Consideran-
do como vencedor o k-ésimo neurônio, tem-se:
( ) ⋁ ( )
( )
Assim:
( )( ) ( )
( )
onde α é a taxa de aprendizado da rede e pode ser reduzida a cada iteração de for-
ma semelhante aos mapas auto-organizáveis de Kohonen. O operador V é o operador
“ou” da Lógica Fuzzy [32].
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 753
2.7 AnImed
A ferramenta computacional AnImed [7] foi desenvolvida para implementar os méto-
dos de classificação e reconstrução de volumes. Esse programa foi criado utilizando a
linguagem de programação orientada a objeto Object Pascal no ambiente de desen-
volvimento Delphi 5. Sua primeira versão data de 2002 tendo na sua mais nova ver-
são, a 8.0 de 2012, a inclusão do algoritmo de agrupamento K-médias otimizado por
programação evolucionária [6] e K-médias otimizada por PSO (Particle Swarm Opti-
mization). A nova versão foi desenvolvida no ambiente Lazarus.
2.8 Índice combinado de Omram
Os índices de validade de agrupamento correspondem a funções matemáticas e esta-
tísticas para avaliar quantitativamente um algoritmo de agrupamento. Pode-se definir
três critérios para avaliar o melhor processo de agrupamento: a minimização do erro
de distorção de quantização, a clara separação entre os grupos resultantes, ou seja,
quanto maior for a menor distância entre centroides, e a coesão de pontos em torno
do centróide do grupo, ou seja, quanto menor for a maior distância dos pontos ao
centróide do grupo [33].
No caso de imagens, o objetivo dos algoritmos de agrupamento é agrupar os
pixels da imagem em classes de forma a classificar ou segmentar a imagem. Um
agrupamento ótimo corresponde à maximização da separação e da coesão bem como
a minimização do erro de quantização. O índice combinado de Omran avalia o pro-
cesso de agrupamento de imagens levando em consideração os três critérios anterior-
mente citados. Considere a aplicação desse índice para imagens. A medida do erro de
distorção de quantização já adaptado para o contexto de segmentação de imagens, ,
pode ser calculada a partir da função:
∑ ∑‖ ( ) ‖
( )
( )
onde ‖ ( ) ‖ é a distância do pixel ( ) da imagem, ou seja, do valor do pixel
da imagem em cada banda, e o centróide do -ésimo grupo em cada banda . Essa
distância pode ser a distância euclidiana. O número de grupos é representado por
com centróides * + enquanto é o número de elemento de
agrupados no -ésimo grupo.
A coesão mede o quanto os dados, ou pixels, estão mais próximos ao centróide.
Dessa forma, o objetivo é minimizar a máxima distância dos pixels ao centróide. A
máxima distância é dada por:
754 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
( ) ( )
∑‖ ( ) ‖
( )
( )
A separação é um critério que maximiza a menor distância entre os centróides.
A distância mínima entre centróides é dada por;
{‖ ‖} ( )
A combinação das equações 13, 14 e 16 define o índice combinado de Omram,
:
( ) ( ) ( ( )) ( ) (17)
onde é um vetor candidato a solução, é o conjunto de centróides associados ao
respectivo candidato e é maior valor de distância entre os centróides que equiva-
le ao maior valor assumido por um pixel da imagem. No segundo termo da equação
tem-se que máximixar é equivalente a minimizar a diferença entre maior distân-
cia entre centroides e a distância mínima entre dois centróides. Os coeficientes ,
e são pesos que ponderam cada medida quantitativa da qualidade do agrupamento.
2.9 Implementação
Nesse trabalho foram utilizadas 03 imagens teste com três bandas elaboradas no
simulador EIDORS. As imagens a serem reconstruídas foram criadas em uma malha
de elementos finitos simulando 32 eletrodos na borda. A partir da resolução do pro-
blema direto da TIE e da aplicação da resolução do problema inverso, foram obtidas
imagens com três bandas reconstruídas pelo EIDORS. As imagens receberam a se-
guintes denominações: “tumor”, losango e losango com “tumor” [6].
A ferramenta computacional AnImed, foi utilizada para os testes de geração de
agrupamentos e classificações. Para cada imagem do conjunto de imagens teste foram
geradas novas imagens classificadas pixel a pixel pelos algoritmos dos Mapas Auto-
Organizáveis de Kohonen, Mapas de K-médias, Mapas de K-médias otimizado por
CEP e Mapas Fuzzy C-médias. A imagens foram classificadas em 4 classes em todos
os algoritmos. Esse número de classes foi escolhido para apresentação dos resultados
visto que foi verificado que, com menos classes, regiões visivelmente diferentes nas
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 755
imagens reconstruídas eram agrupadas em uma mesma classe. Observou-se também
que com mais classes, as imagens classificadas se assemelharam as imagens recons-
truídas, ou seja, quanto maior o número de classes, mais a imagem classificada se
aproximou da imagem original a ser classificada.
Após a geração das imagens classificadas, elas foram quantizadas para melhor
visualização e padronização. Os agrupamentos das imagens resultantes foram avalia-
dos e comparados utilizando o índice combinado de Omran. No caso do algoritmo de
Mapas K-médias otimizado por CEP, o índice combinado de Omran também foi utili-
zado como função objetivo a ser minimizada pelo algoritmo de Programação Evolu-
cionária. Os pesos e utilizados para o cálculo do índice combinado de Om-
ran foram iguais a 1/3 de forma a não privilegiar nenhum aspecto da medida quantita-
tiva da qualidade do agrupamento.
A tabela 1 explicita os parâmetros utilizados de cada algoritmo e a tabela 2 apre-
senta os valores dos parâmetros utilizados em cada algoritmo para a geração dos re-
sultados:
Tabela 1. Parâmetros utilizados para cada algoritmo de agrupamento
Parâmetros K-SOM K-médias K-médias (CEP) Fuzzy C-médias
Classes Número de
clusters
Número de
clusters
Número de
clusters Número de clusters
q - - - Expoente de nebu-
losidade
α Taxa de
aprendizado
Taxa de apren-
dizado -
Taxa de aprendiza-
do
Iterações /
Repetições
Quantidade de
iterações do
algoritmo
Quantidade de
iterações do
algoritmo
Quantidade de
repetições do
algoritmo
Quantidade de
iterações do algo-
ritmo
Limite - - Erro limite -
Pais - - Vetores
solução iniciais -
Gerações - -
Vetores solução
gerados a partir
dos vetores
iniciais
-
756 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
Tabela 2. Valores dos parâmetros utilizados para cada algoritmo de agrupamento
Algoritmo Classes q α Iterações /
Repetições Limite Pais Gerações
K-SOM 4 - 0,1 50 - - -
K-SOM 4 - 0,1 100 - - -
K-médias 4 - 0,1 50 - - -
K-médias 4 - 0,1 100 - - -
K-médias
(CEP) 4 - - 10 0,01 5 50
K-médias
(CEP) 4 - - 10 0,01 5 100
K-médias
(CEP) 4 - - 10 0,01 10 50
K-médias
(CEP) 4 - - 10 0,01 10 100
Fuzzy C-
Médias 4 2 0,1 50 - - -
Fuzzy C-
Médias 4 2 0,1 100 - - -
Fuzzy C-
Médias 4 4 0,1 50 - - -
Fuzzy C-
Médias 4 4 0,1 100 - - -
3 Resultados
Adiante são apresentados os resultados obtidos para a classificação e o agrupamento
das imagens teste utilizando como métrica comparativa o índice combinado de Om-
ran.
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 757
3.1 Imagem teste: “Tumor”
Fig. 1. Resultados - Imagens “Tumor”. (a) "Tumor” – modelo direto; (b) “Tumor” – imagem
reconstruída pelo EIDORS; (c) “Tumor” – imagem classificada por KSOM e quantizada.
; (d) “Tumor” – imagem classificada por Fuzzy C-médias e quanti-
zada. ; (e) “Tumor” – imagem classificada por K-médias otimizado
por CEP e quantizada. ; (f) “Tumor” – imagem classificada por K-
médias e quantizada. ;
Tabela 3. Resultados da imagem teste “tumor”
Algoritmo Classes q α Iter.
/Rep. Limite Pais Gerações
Índice de Om-
ran
K-SOM 4 - 0,1 50 - - - 24,6406019198829
K-SOM 4 - 0,1 100 - - - 24,6406019198829
K-médias 4 - 0,1 50 - - - 28,0169079885215
K-médias 4 - 0,1 100 - - - 28,0169079885215
K-médias
(CEP) 4 - - 10 0,01 5 50 28,0168944697403
K-médias
(CEP) 4 - - 10 0,01 5 100 28,0168944697403
758 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
K-médias
(CEP) 4 - - 10 0,01 10 50 28,0168944697403
K-médias
(CEP) 4 - - 10 0,01 10 100 28,0168944697403
Fuzzy C-
Médias 4 2 0,1 50 - - - 31,6808386672501
Fuzzy C-
Médias 4 2 0,1 100 - - - 31,6808386672501
Fuzzy C-
Médias 4 4 0,1 50 - - - 35,7466152543624
Fuzzy C-
Médias 4 4 0,1 100 - - - 35,7466152543624
A partir dos resultados, observa-se que, de acordo com o índice combinado de
Omram, , o melhor algoritmo de agrupamento para a imagem teste “Tumor” é o
KSOM. Algoritmos de agrupamento e classificação que apresentaram mesmo ou
índices próximos com diferenças a partir da quarta casa decimal, apresentam imagens
quantizadas semelhantes como no caso das imagem (e) e (f) da Figura 1. O algoritmo
de agrupamento Fuzzy C-médias apresentou o maior . A imagem (d) da Figura 1
apresenta a imagem quantizada resultante desse teste.
3.2 Imagem teste: Losango
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 759
Fig. 2. Resultados - Imagens Losango. (a) Losango – modelo direto; (b) Losango – imagem
reconstruída pelo EIDORS; (c) Losango – imagem classificada por KSOM e quantizada.
; (d) Losango – imagem classificada por Fuzzy C-médias e quantiza-
da. (e) Losango – imagem classificada por K-médias otimizado por
CEP e quantizada. ; (f) Losango – imagem classificada por K-médias
e quantizada. .
Tabela 4. Resultados imagem teste Losango
Algoritmo Classes q α Iter. /
Rep. Limite Pais Gerações Índice de Omran
K-SOM 4 - 0,1 50 - - - 26,1712951257200
K-SOM 4 - 0,1 100 - - - 26,1712951257200
K-médias 4 - 0,1 50 - - - 26,1712951257200
K-médias 4 - 0,1 100 - - - 26,1712951257200
K-médias
(CEP) 4 - - 10 0,01 5 50 26,1713623736444
K-médias
(CEP) 4 - - 10 0,01 5 100 26,1713623736444
K-médias
(CEP) 4 - - 10 0,01 10 50 26,1713623736444
K-médias
(CEP) 4 - - 10 0,01 10 100 26,1713623736444
Fuzzy C-
Médias 4 2 0,1 50 - - - 27,9757991157171
Fuzzy C-
Médias 4 2 0,1 100 - - - 27,9757991157171
Fuzzy C-
Médias 4 4 0,1 50 - - - 36,0640997996174
Fuzzy C-
Médias 4 4 0,1 100 - - - 36,0640998023245
A partir dos resultados, observa-se que, de acordo com o índice combinado de
Omram, , os algoritmos K-médias e K-SOM apresentaram convergência para o
mesmo índice. Algoritmos de agrupamento que apresentaram mesmo ou índices
próximos apresentaram imagens quantizadas semelhantes como no caso das imagens
(c), (e) e (f) da Figura 2. O algoritmo de agrupamento Fuzzy C-médias apresentou o
maior . A imagem (d) da Figura 2 apresenta a imagem quantizada resultante desse
teste.
760 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
3.3 Imagem teste: “Tumor” com Losango
Fig. 3. Resultados – Imagens “Tumor”com Losango. (a) “Tumor” com Losango – modelo
direto; (b) “Tumor” com Losango - imagem reconstruída pelo EIDORS; (c) “Tumor”
com Losango – imagem classificada por K-SOM e quantizada. ; (d)
“Tumor” com Losango – imagem classificada por Fuzzy C-médias e quantizada. ; (e) “Tumor” com Losango – imagem classificada por K-médias otimiza-
do por CEP e quantizada. ; (f) “Tumor” com Losango – imagem
classificada por K-médias e quantizada .
Tabela 5. Resultados imagem teste “Tumor” com Losango
Algoritmo Classes q α Iter./
Rep. Limite Pais Gerações Índice de Omran
K-SOM 4 - 0,1 50 - - - 23,6750634969013
K-SOM 4 - 0,1 100 - - - 23,6750634969013
K-médias 4 - 0,1 50 - - - 27,4711654148943
K-médias 4 - 0,1 100 - - - 27,4711654148943
K-médias
(CEP) 4 - - 10 0,01 5 50 27,4713182004213
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 761
K-médias
(CEP) 4 - - 10 0,01 5 100 27,4713182004213
K-médias
(CEP) 4 - - 10 0,01 10 50 27,4713182004213
K-médias
(CEP) 4 - - 10 0,01 10 100 27,4713182004213
Fuzzy C-
Médias 4 2 0,1 50 - - - 31,6826160316555
Fuzzy C-
Médias 4 2 0,1 100 - - - 31,6826160316555
Fuzzy C-
Médias 4 4 0,1 50 - - - 35,7916972209175
Fuzzy C-
Médias 4 4 0,1 100 - - - 35,7916972209175
A partir dos resultados, observa-se que, de acordo com o índice combinado de
Omram, , o melhor algoritmo de agrupamento para a imagem teste “Tumor” + Lo-
sango é o KSOM. Algoritmos de agrupamento e classificação que apresentaram
mesmo ou índices próximos com diferenças a partir da quarta casa decimal apre-
sentam imagens quantizadas semelhantes como no caso das imagens (e) e (f) da Figu-
ra 3. O algoritmo de agrupamento Fuzzy C-médias apresentou o maior índice combi-
nado de Omran. A imagem (d) da Figura 3. apresenta a imagem quantizada resultante
desse teste.
4 Conclusão
As imagens de Tomografia por Impedância Elétrica reconstruídas pelo simulador
EIDORS ainda possuem característica nebulosa sem definição das bordas e da região
de interesse. Algoritmos de classificação e agrupamento são utilizados em imagens de
TIE reconstruídas pelo simulador EIDORS para realçar e melhor definir as bordas da
região de interesse [5] [6].
O objetivo do presente trabalho foi analisar comparativamente de forma quanti-
tativa a aplicação de diferentes técnicas de classificação e agrupamento em imagens
de TIE reconstruídas pelo simulador EIDORS. Para tal, os algoritmos de Mapas Auto-
Organizáveis de Kohonen, Mapas de K-médias, Mapas de K-médias otimizado por
CEP e Mapas Fuzzy C-médias foram aplicados em 03 imagens com três bandas gera-
das pelo processo direto, através do Método dos Elementos Finitos, e posteriormente
pelo processo inverso (imagem reconstruída), pelo método de Gauss-Newton, no
EIDORS. A partir do resultado obtido, calculou-se o índice combinado de Omran,
uma métrica de validação quantitativa de agrupamentos que une os três principais
critérios de avaliação de agrupamentos: a separação dos grupos, a coesão dos pontos
em um grupo e o erro de distorção de quantização.
762 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
Para cada uma das 03 imagens foram realizados e expostos nesse trabalho os 12
testes mais relevantes: 02 testes com K-SOM, 02 testes com K-médias, 04 testes para
K-médias otimizado por CEP e 04 testes com Fuzzy C-médias. Foram apresentados
48 testes no total. Para cada teste, foi calculado o índice de Omran. Quanto menor o
índice de Omran, maior a coesão e a separação e menor o erro de quantização.
De acordo com os resultados obtidos, conclui-se que a melhor técnica para quan-
tização de imagens de TIE é o K-SOM. Em todos os testes realizados, as imagens
quantizadas por K-SOM apresentaram menor índice de avaliação de agrupamento.
Não foram observadas diferenças significativas no índice de avaliação de agrupamen-
tos entre as técnicas K-médias e K-médias otimizado por CEP em relação às imagens
de TIE reconstruídas pelo EIDORS. Os agrupamentos realizados com o algoritmo de
Mapas Fuzzy C-médias apresentaram o maior índice de Omram em todos os testes.
Em experimentos realizados na pesquisa, porém não explicitados nesse trabalho,
variou-se a quantidade de repetições, de pais e de gerações do algoritmo Mapas de K-
médias otimizado por CEP, contudo não houve variação do índice de Omran. No caso
do algoritmo de Mapas Fuzzy C-médias, variou-se o expoente de nebulosidade, a taxa
de aprendizado e o número de iterações, entretanto, não houve variação positiva nos
resultados, ou seja, minimização do índice de Omran. É possível que a característica
do algoritmo Mapas Fuzzy C-médias, de poder classificar os pixels em dois ou mais
agrupamentos dependendo do grau de pertinência do pixel, aliado as imagens recons-
truídas de baixa resolução tenha sido responsável pelo alto índice de Omram obtido
em relação às demais técnicas. Outra hipótese que se pode concluir é que a conver-
gência desse algoritmo ocorre nas primeiras repetições, assim como os algoritmos K-
SOM e Mapas de K-médias.
Não obstante, é importante destacar que as imagens utilizadas para a realização
dos testes foram simples. Isso em virtude da não existência de um benchmarking de
imagens de TIE geradas pelo simulador EIDORS pelo método direto e inverso. Todas
as imagens expostas nesse trabalho foram geradas no intuito de realizar os experimen-
tos desenvolvidos e explicitadas nesse trabalho.
Apesar das técnicas de classificação e agrupamento utilizadas nesse trabalho te-
nham delimitado as bordas e realçado a região de interesse, nenhuma delas destacou a
estrutura modelada na grade do MEF no modelo direto. Verifica-se que a característi-
ca nebulosa da imagem reconstruída pelo EIDORS utilizando o MEF como método
de resolução do problema direto e o método de Gauss-Newton para resolução do pro-
blema inverso não possibilita a definição da estrutura. Isso pode ser verificado na
imagem teste “Tumor” com losango, Figura 3, onde o losango “desaparece” na ima-
gem reconstruída e na imagem quantizada aparece como uma extensão da região cen-
tral.
Referências
1. Lawrence, C.W: Electronics for real time and three-dimensional electrical impedance to-
mography. Tese (doutorado). University of Denver, Denver (1996).
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 763
2. Censor, Y: Finite series-expansion reconstruction methods. Proceedings of the IEEE, vol.
71, no. 3, pp. 409-419 (1983).
3. Lewitt, R.M: Reconstruction algorithms: transform methods. Proceedings of the IEEE,
vol.71, no. 3, pp. 390-408 (1983).
4. Adler, A. e Lionheart, W.R.B: Uses and abuses of EIDORS: an extensive software base
for EIT. Physiol. Meas. 27, S25-S42. (2006).
5. Eulálio, A., Ribeiro, L.R.F., Valença, M.J.S. e Santos, W.P. Uso de Mapas Auto Organi-
záveis de Kohonen para quantização de imagens de Tomografia por Impedância Elétrica
reconstruídas pelo software EIDORS. In: X Congresso Brasileiro de Inteligência Compu-
tacional, Anais do X CBIC, Fortaleza (2011).
6. Ribeiro, L.R.F. Reconstrução de imagens de tomografia por impedância elétrica usando
elementos finitos e requantização por mapas de Kohonen e otimização por programação
evolucionária. Dissertação (Mestrado). Departamento de Engenharia da Computação. Es-
cola Politécnica de Pernambuco, Universidade de Pernambuco (2012).
7. Santos, W.P. Método Dialético de Busca e Otimização para Análise de Imagens de Resso-
nância Magnética. Tese de Doutorado. Universidade Federal de Campina Grande. Centro
de Engenharia Elétrica e Informática. Departamento de Engenharia Elétrica. (2009).
8. Omran, M., Engelbrecht, A.P. e Salman, A. Particle swarm optimization method for image
clustering. International Journal of Pattern Recognition and Artifficial Intelligence.
vol.19, pp. 297-321 (2005).
9. Carosio, G.C: Tomografia de escoamentos multifásicos por sensoriamento elétrico-
desenvolvimento de algoritmos genéticos paralelos para solução do problema inverso. Tese
(Doutorado). Escola de Engenharia de São Carlos da Universidade de São Paulo (2008).
10. Hua, J.W.P., Webster, J. e Tompkins,W.: Finite element modeling of electrode-skin con-
tact impedance in electrical impedance tomography. IEEE Transactions on Biomedical
Engineering. vol.40, n. 4, pp 335-343 (1993).
11. Cook, R.D. et al : Concepts and Applications of Finite Elements Analysis. 4.ed. New York:
John Wiley & Sons, Inc. (2002).
12. Menin, O.H: Método dos Elementos de Contorno para Tomografia de Impedância Elétrica.
Dissertação (Mestrado), Programa de Física Aplicada a Medicina e Biologia, Faculdade
de Filosofia, Ciências e Letras de Ribeirão Preto, Universidade de São Paulo (2009).
13. Barber, D., Brown, B.: Applied Potential Tomography. Journal of Physics. E: Scientific
Instruments. vol.17, pp. 723-733 (1984).
764 Leonardo R. Ribeiro, Mêuser J. S. Valença e Wellington P. dos Santos
14. Connoly, T. e Wall, D: On an inverse problem with bounding measurements for a steady
state diffusion equation. Inverse Problems. vol. 4, pp. 995-1012 (1998).
15. Calderon, A: On an inverse boundary value problem. In. Proc. Seminar on Numerical
Analysis and its Applications to Continuum Physics. Soc. Brasileira de Matemática, [S.1].
pp. 65-73 (1980).
16. Cheney, M., Issacson, D., Newell, J., Goble, J. e Simske, S.: Noser: An algorithm for solv-
ing the inverse conductivity problem. Int. J. Imaging Systems and Technology. vol. 2, pp.
66-75(1990).
17. Yorkey, T., Webster, J. e Tompkins, W.: Comparing reconstruction algorithms for electri-
cal impedance tomography. IEEE Trans. on Biomed. Eng., vol. 34, n. 11, pp. 843-852.
(1980).
18. Lima, C.: Estudo da obtenção de imagens de tomografia de impedância elétrica do pulmão
pelo método de otimização topológica. Tese (Doutorado). Departamento de Engenharia
Mecatrônica. Escola Politécnica da Universidade de São Paulo (2006).
19. Trigo F.C., Lima, R.G. e Amato, M.B.P. Electrical impedance tomography using the ex-
tended Kalman filter. IEEE Trans. Biomed. Eng. vol.51, n. 1, pp. 72-81 (2004).
20. Vaukhonen, M.: Electrical impedance tomography and prior information. Ph.D. thesis.
Kuopio University, Kuopio (1997).
21. Lionheart, W.R.B. et al.: Electrical Impedance and Diffuse Optical Tomography Recon-
struction Software. Artigo, 1st World Congress on Industrial Process Tomography, Bux-
ton, Greater Manchester, (1999).
22. Stacey, R.W.: Electrical Impedance Tomography. Stanford Geothermal Program, Stanford
University (2006).
23. Garnadi, A.D. e Kumiadi, D.: Two Dimensional Numerical Reconstruction of Electrical
Impedance Tomography using Tikhonov Regularization Algorithms with a-posteriori pa-
rameter choice rule, IPB (Bogor Agricultural University) (2005).
24. Taner, M.T.: Kohonen Self Organizing Networks with “Conscience”. Rock Solid Images,
(1997).
25. Haykin, S.: Neural Networks: A Comprehensive Foundation. Macmilliam College Publish-
ing Company, New York (1994).
26. Carvalho, L.O.R.: Data Clustering. Estudo em agrupamento de dados usando K-médias,
Unicamp, (2011).
Reconstrução de imagens de tomografia por impedância elétrica usando elementos
finitos, fuzzy c-médias e programação evolucionária 765
27. Omran, M., Engelbrecht, A.P. e Salman, A.: Particle swarm optimization method for im-
age clustering. International Journal of Pattern Recognition and Artifficial Intelligence.
vol.19, pp. 297-321 (2005).
28. Hung, W.L., Yang, M.S. and Chen, D.H.: Parameter selection for suppressed fuzzy c-
means with application to MRI segmentation. Pattern Recognition Letters. vol.27, pp.424-
438 (2006).
29. Dimitradou, E., Barth, M., Windischberger, K., Hornik, K. and Moser, E.: A quantitative
comparison of functional MRI cluster analysis. Artificial Intelligence in Medicine, vol. 29,
pp. 203 – 223 (2003).
30. Bezdek, J.C.: Pattern Recognition with Fuzzy Objective Function Algoritms. Plenum
Press, New York (1981).
31. Dunn, J.C.: A Fuzzy Relative to ISODATA Process an Its Use in Detecting Compact
Well-Separated Clusters. Journal of Cybernetics, vol.3, pp. 32-57 (1973).
32. Takagi, T. and Sugeno, M.: Fuzzy identification of systems and its applications to model-
ing and control. IEEE transactions on systems, man and cybernetics, vol.15, n.1, pp 116-
132 (1985).
33. Das, S., Abraham, A. e Konar, A. Automatic clustering using an improved differential
evolution algorithm. IEEE Transactions on Systems, Man, and Cybernetics – Part A: Sys-
tems and Humans. vol.38, pp. 218-237 (2008).