TRIANGULAÇÃO DE DELAUNAY COM RESTRIÇÃO … · formam o contorno utilizou-se o algoritmo de Moore- ... imagem de entrada foi obtida a matriz de cores, neste caso foi gerada em

1

TRIANGULAÇÃO DE DELAUNAY COM RESTRIÇÃO EM IMAGENS BIDIMENSIONAIS

Leide Daiane Caires 1, Edson A. Capello Sousa 2

1 Depto Eng. Mecânica – Universidade Estadual Paulista, Bauru, Brasil, [email protected]

2 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 Moore-Neighborhood.

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)

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

2

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} (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).

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.


3

Figura 3 – Nova identificação do contorno após a limpeza.

3.1. COMPONENTES CONEXAS

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, definindo-se 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

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 4 – Imagens dos diversos contornos da região óssea da

mandíbula. 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 é



4

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.

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.

(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

Uma triangulação n-dimensional de um conjunto de pontos P= {p1 , p2 , p3 ,..., pn} é uma coleção de n-dimensional 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. 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.


5

Fig. 8 – Malha gerada pelo programa desenvolvido, com aplicação

da Triangulação de Delaunay com restrição.

Fig. 9 – Malha gerada a partir de uma nuvem de 1811 pontos (Fig.

6).

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. Pode-se 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



6

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.


Documents

TRIANGULAÇÃO DE DELAUNAY COM RESTRIÇÃO … · formam o contorno utilizou-se o algoritmo de Moore- ... imagem de entrada foi obtida a matriz de cores, neste caso foi gerada em