TRIANGULAÇÃO DE DELAUNAY COM RESTRIÇÃO EM IMAGENS BIDIMENSIONAIS
Leide Daiane Caires 1, Edson A. Capello Sousa 2
1
2
Depto Eng. Mecânica – Universidade Estadual Paulista, Bauru, Brasil, [email protected]
Depto de Eng. Mecânica – Universidade Estadual Paulista, Bauru, Brasil, [email protected]
Resumo: A partir da dificuldade de criar modelos com
geometria complexa para análise por Elementos Finitos foi
desenvolvido um programa computacional, que trabalha
com imagens médicas bidimensionais (regiões ósseas). O
programa desenvolvido trata estas imagens, reconstrói os
modelos e gera a malha de superfície para ser inserida no
modelo de Elementos Finitos, utilizando o método da
Triangulação de Delaunay com restrição.
Palavras-chave: biomecânica, elementos finitos, imagem
médica, triangulação de Delaunay, geração de malhas
1. INTRODUÇÃO
A utilização de métodos numéricos e o desenvolvimento
de algoritmos para resolução de problemas complexos de
engenharia entre outras áreas, têm crescido muito nos
últimos anos. Tal crescimento se dá pelo fato de que quando
se utiliza experimentação numérica (métodos numéricos),
este praticamente não apresenta restrições, podendo resolver
problemas
complicados e
geometrias
arbitrárias,
apresentando resultados de maneira rápida e econômica em
relação a outros métodos.
O estudo realizado trabalha com a geração de malhas
não estruturadas, onde estas malhas são geradas a partir da
modelagem de objetos extraídos por dispositivos não
invasivos, como Tomografia Computadorizada e
Ressonância Magnética.
Como a obtenção destes modelos não é uma tarefa fácil
de realizar devido à complexidade de sua geometria, a
solução seria reconstruí-los com auxílio de um programa
computacional.
Um dos métodos mais utilizados para a reconstrução
desses modelos é o método de Delaunay. Este trabalho foi
baseado na Triangulação de Delaunay com restrição ou
Constrained Delaunay Triangulation (CDT), que trata de
modelos com geometrias complexas. Pode-se utilizar de
outros recursos para tratamento e melhoria dessas imagens
para que ao final do trabalho a malha gerada atendesse os
objetivos pretendidos. Neste caso, utilizou-se componentes
conexas para extração dos diversos contornos que podem
existir em uma imagem, e a organização dos pontos que
formam o contorno utilizou-se o algoritmo de MooreNeighborhood.
A base para o desenvolvimento deste programa foi o
software MATLAB (MATrix LABoratory) – um software
interativo direcionado para cálculo numérico e de alto
desempenho, que integra cálculo com matrizes, análise
numérica, processamento de sinais e construção de gráficos
em ambiente de fácil implementação.
Com sua própria linguagem, oferece uma ampla
biblioteca de funções predefinidas para que a programação
técnica se torne mais fácil. Ele permite a resolução de
muitos problemas numéricos em apenas uma fração do
tempo que se gastaria para escrever um programa
semelhante em linguagem Fortran, Basic ou C. Além disso,
as soluções dos problemas são expressas quase exatamente
como elas são escritas matematicamente, ao contrário da
programação tradicional. Maiores detalhes podem ser
encontrados em Chapman (2003) e MATLAB (set. 2009).
Neste artigo apresentaremos a organização deste
programa, as ferramentas e os passos utilizados para a
reconstrução do modelo.
2. OBJETIVO
O programa desenvolvido teve como principal objetivo
implementar a CDT, em imagens bidimensionais com
geometrias complexas (buracos e/ou concavidades), para
reconstrução de superfície e geração de malha. Foram
utilizadas imagens bidimensionais no formato DICOM
(Digital Imaging Communications in Medicine), mas ele
também é capaz de trabalhar com imagens nos formatos
BMP e JPEG. Estas imagens são aplicadas na área da
biomecânica, relacionados à fase que precede a análise por
elementos finitos, ou seja, obtenção do modelo geométrico
(região óssea) para posterior análise em softwares
especializados.
3. MÉTODOS
A imagem de entrada em formato DICOM, (Fig. 1),
onde suas dimensões foram dadas em pontos (pixels)
horizontais e verticais. Em ambiente MATLAB, através
imagem de entrada foi obtida a matriz de cores, neste caso
foi gerada em tons de cinza (Grayscale). No caso das
imagens em tons de cinza, como é o caso da imagem de
entrada, ela se diferencia da imagem binária por não limitar
seus pixels em (0 e 1), os mesmos fazem parte de um
conjunto finito de números inteiros não negativos, Heijmans
(1993), ou seja, a imagem em tons de cinza, Eq. (1)
definida, por t é um levantamento topográfico de um
subconjunto Dt de Zn, onde o domínio de definição de t é o
conjunto limitado de inteiros não negativos (série finita No).
t:Dt  Zn {0,1,...tmax}
(1)
1
Proceedings of the 9th Brazilian Conference on Dynamics Control and their Applications
Serra Negra, SP - ISSN 2178-3667
830
Triangulaçao de Delaunay com Restrição em Imagens Bidimensionais
Leide Daiane Caires, Edson A. Capello Sousa
onde, tmax é o valor máximo do tipo de dados usado para
armazenar a imagem, ou seja, para todo pixel f do domínio
de definição de imagem p(f) pertence a {0, 1,..., tmax}.
Figura 1 – Tomografia computadorizada, seção transversal da
mandíbula, imagem de entrada.
A matriz de entrada (tons de cinza), então é transformada
em uma matriz binária, esta matriz é gerada a partir da
imagem de entrada.
Na matriz binária, que se refere a imagem binarizada, o
valor de um pixel é 1 ou 0, isto depende se o pixel pertence
ao primeiro plano (objeto), ou plano de fundo que não faz
parte do objeto. No caso da imagem utilizada para
realização desta pesquisa, (Fig. 2), os pixels de primeiro
plano são impressos em branco, que são referentes à parte
interna do osso da mandíbula, e os pixels de fundo são
pretos, são a área externa do osso.
Quando se trabalha com análise de imagem, a maioria
dos algoritmos realizam desta forma, onde conseguem
retirar informações relacionadas a geometria dos objetos,
Heijmans (1999).
Por definição, Eq. (2), uma imagem binária p é um
plano de um subconjunto Dp de Zn, chamado domínio de
definição de p no par {0,1}:
p: Dp  Zn {0,1}
Figura 2 – Identificação do contorno, presença de alguns pontos
dispersos na região interna do osso.
Observou-se que os procedimentos de filtragem da
imagem binária (Fig. 2), deveria tornar a identificação da
região interna do osso mais evidente e precisa, pois ainda
era verificado que haviam vários pontos, dispersos na
imagem, e estes não faziam parte do osso.
O programa desenvolvido procurou manter o máximo
de organização dos pontos que formam o contorno da
imagem. Para isto é realizado um novo filtro de
padronização da imagem a fim de eliminar estes pontos que
afetam a definição do contorno do osso. Este novo filtro faz
uma limpeza para organização destes pontos se mostrou
bem satisfatório. Na Fig. 2, as setas mostram que os pontos
que estão mais próximos e delineados tornam-se mais
alinhados (Fig. 3), ou seja, o contorno ficou mais definido e
os pontos dispersos ou duplicados foram eliminados. É
possível verificar nesta imagem uma parte do osso da coluna
cervical, mas esta não fará parte do trabalho.
(2)
isto quer dizer que para todos os pixels f do domínio de
definição da imagem, p(f) iguais a 0 ou 1. Uma imagem com
n-dimensão (n-D) apresenta uma imagem cujo domínio de
definição é um subconjunto n-D do intervalo discreto Zn ,
Danielsson (1980).
2
Proceedings of the 9th Brazilian Conference on Dynamics Control and their Applications
Serra Negra, SP - ISSN 2178-3667
831
componente conexa tenham sido explorados. Esta busca é
implementada de forma recursiva, e leva em consideração
apenas os pixels que ainda não foram rotulados, ou seja,
exclui os que tenham valor ‘0’ (preto) ou que tenham o valor
de outro rótulo. Esse método é muito semelhante ao
Algoritmo de Preenchimento de Região. Não foi encontrada
dificuldade na implementação do algoritmo. Isto significa
que o programa implementado encontra as componentes
conexas e as rotula corretamente.
(a) imagem original
(b) contorno 1, região interna
(c) contorno 2, região externa
(d) contorno 3, região interna
Figura 3 – Nova identificação do contorno após a limpeza.
3.1. COMPONENTES CONEXAS
Figura 4 – Imagens dos diversos contornos da região óssea da
mandíbula.
As componentes conexas foram utilizadas para extrair
os diversos contornos que existem na imagem, (Fig. 4). Na
Figura 4 (a), temos a imagem original, e em seguida alguns
dos contornos desta imagem de forma isolada, este método é
importante quando tratamos de imagens como buracos
(holes), pois eles podem ser tratados de forma isolada, sem a
necessidade do carregamento da imagem inteira,
proporcionando rapidez e economia de tempo.
A partir da imagem binária, é necessário encontrar e
rotular todas as componentes conexas da imagem, tal que
para todo pixel pertencente à componente existe um
caminho conexo para cada um dos pixels também
pertencentes à componente.
Caminhos conexos é seqüência de pixels indo de P até
Q: tal que Pi é adjacente de Pi-1.
Seja uma imagem binária S e um subconjunto s cujos
pixels assumem todos os mesmo valor 1. Dados dois pixels
P e Q em s, eles serão conectados se, e somente se, existe
um caminho conexo incluso em s ligando P a Q, definindose assim como componentes conexas.
O método consiste em para cada pixel P pertencente à
figura, tomamos um modelo que representa toda a sua
vizinhança (vizinhança -4, -8 ou -m). A cada iteração,
procuramos então a vizinhança dos pixels vizinhos a P, e
fazemos isso sucessivamente até que todos os pixels da
3.2. ALGORITMO MOORE NEIGHBORHOOD
O algoritmo de Neighborhood foi utilizado neste
trabalho para ordenar os pontos do contorno da imagem, ou
seja, a seqüência da fronteira ou contorno de rastreamento,
(Fig. 5), para extrair o limite da imagem.
O Moore Neighborhood é conhecido na literatura por
conter 8-vizinhos ou moradores indiretos. Um pixel P
contém ao seu redor 8 pixels que partilham um vértice ou
aresta com ele. Estes pixels são denominados pixels P1, P2,
P3, P4, P5, P6, P7 e P8.
A partir da imagem binária gerada (imagem original),
onde os pixels em preto são o fundo e os brancos a imagem,
é localizado o pixel branco inicial (P), onde este pode ser
localizado de várias maneiras. Neste trabalho ele foi
localizado no canto superior esquerdo mais extremo da
matriz (imagem). A varredura de cada coluna de pixels do
fundo vai para baixo, a partir da coluna mais à esquerda e
segue para a direita até encontrarmos um pixel branco. Nós
declaramos este pixel como o pixel inicial (P).
Encontrado o pixel (P), vamos rastrear todo o contorno
no sentido horário. O traçado deste contorno é feito através
da verificação dos 8 vizinhos, para verificar se algum deles é
3
Proceedings of the 9th Brazilian Conference on Dynamics Control and their Applications
Serra Negra, SP - ISSN 2178-3667
832
Triangulaçao de Delaunay com Restrição em Imagens Bidimensionais
Leide Daiane Caires, Edson A. Capello Sousa
branco. Encontrado o próximo pixel branco, P1, este passa a
ser o pixel inicial para o laço da verificação dos 8 vizinhos,
e este laço continua do passo onde parou, mas com um novo
pixel inicial de vértices diferentes. Quando o mesmo pixel
inicial P, for visitado pela segunda vez o algoritmo termina,
pois já terminou o contorno. Os pixels brancos que foram
encontrados formaram o contorno da imagem.
Uma triangulação n-dimensional de um conjunto de
pontos P= {p1 , p2 , p3 ,..., pn} é uma coleção de ndimensional simplexos cuja definição de pontos encontra-se
em P. Os simplexos não intersectam um ao outro e
compartilham elementos de fronteira como arestas ou faces.
A triangulação de Delaunay é um caso particular. Ela tem a
propriedade de que a circunferência circunscrita de qualquer
n-dimensional simplexo não contém outros pontos de P
exceto os n+1 pontos definidos do simplexo
O critério utilizado na triangulação de Delaunay é a
maximização dos ângulos mínimos de cada triângulo. Isto
quer dizer, que a malha final deve conter triângulos o mais
próximo possível de equiláteros, evitando-se a criação de
triângulos afinados, ou seja, triângulos com ângulos internos
muito agudos.
A triangulação com restrição é definida, segundo
Figueiredo e Carvalho (1991), como: dado um conjunto C
de pontos do plano e um conjunto G de segmentos com
extremos em C (tais que dois elementos quaisquer de G não
se interceptam a não ser em seus extremos), obter uma
triangulação do fecho convexo de C, cujo conjunto de
vértices seja C inclua todos os segmentos em G.
A Figura (7), extraída do trabalho Sousa (2004), que
utilizou uma imagem em formato BMP, mostra a aplicação
da Triangulação de Delaunay sobre os pontos que definem o
contorno, neste caso, não foi possível detectar a existência
da região côncava e dos buracos da mandíbula. Este
problema mostra que a utilização somente da Triangulação
de Delaunay, não é suficiente para trabalhos que envolvam
imagem com presença de concavidades e buracos.
Fig. 5 – Demonstração da aplicação do Algoritmo de Moore
Neighborhood, utilizado para organização dos pontos que formam o
contorno.
3.3. PONTOS DE CONTORNO
Para obter o contorno final da imagem e seja gerada a
malha, deve-se converter a imagem em dados geométricos
no plano e defini-los em coordenadas x e y, (Fig. 5). Este
conjunto é utilizado para a aplicação do método de
Delaunay. Para que o método de Delaunay gere um
contorno mais preciso, o conjunto de pontos gerados deve
ser de forma sequencial, por isso foi utilizado o Algoritmo
de Neighborhood, para que os pontos fossem ordenados para
melhor desempenho do método. Neste trabalho os pontos
foram ordenados em sentido horário, (Fig. 6). Podemos
observar que a imagem foi reproduzida claramente pela
nuvem de pontos gerada.
Fig. 7 – Malha gerada a partir da Triangulação de Delaunay sem
restrição.
Devido a tais dificuldades foi empregado no programa
desenvolvido o método de Delaunay com restrição. Na Fig.
8, podemos visualizar a imagem extraída do trabalho de
Sousa (2004), com a aplicação do método desenvolvido por
este trabalho. As figuras 9 e 10, se referem a aplicação do
método sugerido nas imagens aqui apresentadas.
(a)
(b)
Figura 6 – Imagem convertida em dados geométricos, onde a
imagem (a) foi gerada a partir de 151 pontos e a imagem (b) a partir de
1811 pontos.
3.4. TRIANGULAÇÃO DE DELAUNAY
4
Proceedings of the 9th Brazilian Conference on Dynamics Control and their Applications
Serra Negra, SP - ISSN 2178-3667
833
Fig. 8 – Malha gerada pelo programa desenvolvido, com aplicação
da Triangulação de Delaunay com restrição.
Fig 10 – Imagem gerada a partir de uma nuvem de 151 pontos.
A Fig. 10 ilustra que mesmo com uma quantidade bem
menor de pontos, o algoritmo se mostrou satisfatório e não
houve grande deformidade em relação ao contorno.
É importante que o programa consiga trabalhar com uma
quantidade menor de pontos, pois o processamento da
imagem ser torna mais rápido, mas isso não pode interferir
na qualidade do contorno final.
4. DISCUSSÃO DOS RESULTADOS
Este trabalho teve como principal objetivo resolver o
problema de modelos com geometrias complexas
(concavidades e/ou buracos), em imagens bidimensionais
para problemas voltados para área da bioengenharia. Podese confirmar no trabalho realizado por Sousa (2004), que
somente a triangulação de Delaunay não é suficiente para
resolver este tipo de problema (Fig. 7).
No trabalho desenvolvido por Sousa (2004), a solução
deste problema só era possível subdividindo as regiões com
concavidade para obtenção dos contornos de cada região
fechada.
O programa desenvolvido com base na aplicação do
método de Delaunay com restrição, mostrou-se eficiente e
favorável para a resolução deste tipo de problema. Os
demais métodos utilizados também se mostraram
satisfatórios,
como
a aplicação do Algoritmo de
Neighbordhood, que proporcionou a organização dos pontos
com eficiência, contribuindo para a aplicação da
Triangulação de Delaunay com restrição, pois este tipo de
triangulação necessita desta ordenação para sua eficiência.
O programa também consegue isolar algumas regiões de
interesse sem a necessidade de outros softwares.
Como ilustrado na Fig. 8, Fig. 9 e Fig. 10 , fica evidente
as vantagens de se utilizar um software de reconstrução,
essas vantagens se referem à riqueza dos detalhes presentes
na forma geométrica reconstruída, onde deve ser levado em
Fig. 9 – Malha gerada a partir de uma nuvem de 1811 pontos (Fig.
6).
5
Proceedings of the 9th Brazilian Conference on Dynamics Control and their Applications
Serra Negra, SP - ISSN 2178-3667
834
Triangulaçao de Delaunay com Restrição em Imagens Bidimensionais
Leide Daiane Caires, Edson A. Capello Sousa
consideração também a facilidade, rapidez e precisão que se
obtêm os modelos a partir de técnicas de reconstrução por
uso do programa computacional.
Os recursos utilizados neste trabalho são de extrema
utilidade para a fase que precede a análise por elementos
finitos, uma vez que garante maior fidelidade ao modelo
geométrico construído.
O modelo reconstruído será importado pelo software de
análise por elementos finitos, Ansys Multiphysics, onde
nesta fase de pré-processamento serão definidas
as
condições de contorno, criação de ósseo-implantes,
propriedades do material, aplicação de carga e outros mais,
pertinentes a esta etapa, mas que no momento fogem ao
objetivo deste estudo.
AGRADECIMENTOS
A Edmar S. de Mattos e ao Profº Dr. Edson A. Capello
Sousa pelo entusiasmo e incentivo para a elaboração deste
trabalho.
REFERÊNCIAS
[1] S. J. Chapman, “Programação em MATLAB para
Engenheiros”, Ed. Thomson, São Paulo, 2003.
[2] MATLAB. MathWorks Inc. Disponível em:
<http://www.mathworks.com>. Acesso em: set. 2009.
[3] H. Heijmans, “A Note on the Umbra Transformin in
Gray-scale Morphology”, Pattern Recognition Letters,
Vol. 14, pp. 877-881, 1993.
[4] H. Heijmans, “Connected Morphological Operators
for Binary Images”, Computer Vision and Image
Understanding, Vol. 73, pp. 99-120, 1999.
[5] P. E. Danielsson, “Euclidean Distance Mapping”,
Computter Graphics and Image Processing, Vol. 14, pp.
227-248, 1980.
[6] L. H. Figueiredo, and P. C. P. Carvalho, “Introdução à
Geommetria Computacional”, In: XVII Colóquio
Brasileiro de Matemática, IMPA, 1991.
[7] E. A. C. Sousa, “Identificação de Imagens Aplicada a
Modelagem de Estruturas Ósseas em Bio-Engenharia”,
Relatório de Pesquisa, Janeiro 2004.
[8] Ansys, “APDL Programmer´s Guide. Ansys
Release 10.0”. Southpointe, Pennsylvania, 2006.
6
Proceedings of the 9th Brazilian Conference on Dynamics Control and their Applications
Serra Negra, SP - ISSN 2178-3667
835