Simulação da deformação de objectos em imagens segundo princípios físicos

2º ENCONTRO NACIONAL DE BIOMECÂNICA H. Rodrigues et al. (Eds.) Évora, Portugal, 8 e 9 de Fevereiro, 2007 SIMULAÇÃO DA DEFORMAÇÃO DE OBJECTOS EM IMAGENS SEGUNDO PRINCÍPIOS FÍSICOS Patrícia C. T. Gonçalves, Raquel R. Pinho e João Manuel R. S. Tavares Laboratório de Óptica e Mecânica Experimental, Instituto de Engenharia Mecânica e Gestão Industrial Faculdade de Engenharia da Universidade do Porto e-mail: [email protected], [email protected], [email protected] Palavras-Chave: Análise de imagem, Objectos deformáveis, Simulação, Princípios físicos. Resumo. Este artigo apresenta uma abordagem física para simular a deformação de objectos representados em imagens. Nessa abordagem, para modelar fisicamente os objectos, é utilizado o método dos elementos finitos. De seguida, é aplicada análise modal para determinar as correspondências entre os nodos dos objectos. Finalmente, o campo dos deslocamentos é simulado através da equação de equilíbrio dinâmico. Para resolver esta equação, foram considerados quatro métodos de integração numérica: o método da diferença central, o método de Newmark e o método da sobreposição de modos em conjunto com os dois anteriores. 1 INTRODUÇÃO Todos os objectos reais são deformáveis, por isso a grande maioria não pode ser adequadamente modelada se a considerarmos como um corpo rígido. A simulação de objectos deformáveis pode ser conseguida através de modelos deformáveis, o que pode não ser trivial pois diferentes áreas de aplicação têm diferentes requisitos; por exemplo, algumas requerem precisão, como a análise de imagens médicas, outras requerem interacção em tempo real, como as aplicações de ambientes virtuais. Embora tenham sido propostos vários métodos para simular rapidamente e com precisão objectos deformáveis, há ainda muito trabalho a fazer nesta área. O nosso objectivo principal é simular as formas intermédias que um dado objecto representado em imagens poderá assumir, dados os seus estados inicial e final. Para isso, usamos a metodologia proposta por Terzopoulos et al. [1] para fazer simulações realísticas da deformação de objectos considerando um modelo elástico construído por um determinado material virtual e a resolução temporal da equação de equilíbrio dinâmico. Assim, consideramos: o elemento finito isoparamétrico de Sclaroff [2] para modelar fisicamente as Patrícia C. T. Gonçalves, Raquel R. Pinho e João Manuel R. S. Tavares formas inicial e final do objecto; a descrição modal da forma de Shapiro e Brady [3] para emparelhar os nodos (dados pontuais) dos dois estados do objecto; e a decomposição da deformação em modos rígidos e não rígidos de Pentland e Horowitz [4]. 2 MODELAÇÃO FÍSICA Para construir o modelo físico das formas inicial e final utilizamos o elemento finito isoparamétrico de Sclaroff [2] que usa um conjunto de funções radiais base que permitem uma fácil inserção dos dados pontuais; desta forma, são usadas funções de interpolação de base gaussiana e os nodos do modelo não necessitam ser previamente ordenados. É a partir desses elementos finitos, e tendo em conta o tipo de material virtual considerado para o objecto em questão, que as matrizes de massa, , e rigidez, M K , são construídas para cada uma das formas do objecto a simular [2;5;6]. Neste trabalho, usamos a matriz de amortecimento de Rayleigh, K MC β α + = , onde α e β são constantes definidas em função do amortecimento crítico admitido [7]. 3 CORRESPONDÊNCIA ENTRE OS NODOS DOS OBJECTOS Para determinar as correspondências entre os nodos das formas inicial e final do objecto, cada problema generalizado de valores e vectores próprios é resolvido: ΩMΦ K Φ = , (1) onde é a matriz modal dos vectores de forma , que descrevem o deslocamento modal (u,v) de cada nodo devido ao modo de vibração i, e Ω é a matriz diagonal cujas entradas são o quadrado dos valores próprios ordenados por ordem crescente. Φi φ Após a construção da matriz modal para cada forma do objecto, os nodos das duas formas podem ser emparelhados comparando o deslocamento de cada um no respectivo espaço modal [3]. Assim, para determinar as correspondências entre os nodos da forma inicial, I, do objecto, com os da forma final, F, do mesmo objecto, é construída uma matriz de afinidade, Z, cujos elementos são definidos como 22 j,Fi,Ij,Fi,Iij vvuuZ −+−= , (2) onde a afinidade entre os nodos i e j será 0 (zero) se a correspondência for perfeita, e será tanto maior quanto pior for a correspondência. Neste artigo, consideramos o método de busca global na matriz Z para determinar as correspondências. Este método, proposto em [8;9], consiste em descrever o emparelhamento como um problema de atribuição e resolvê-lo usando um algoritmo apropriado de optimização. 4 EQUAÇÃO DE EQUILÍBRIO DINÂMICO Para estimar a deformação do objecto, e assim obter as suas formas de transição atendendo Patrícia C. T. Gonçalves, Raquel R. Pinho e João Manuel R. S. Tavares a propriedades físicas, resolvemos a equação de equilíbrio dinâmico, , (3) ttt ++ =MU CU KU R && & t para cada passo de tempo t, onde , e são respectivamente os vectores deslocamento, velocidade e aceleração, e U U &U && R é o vector das cargas implícitas. Para resolver a equação (3) podem ser usados diversos métodos de integração. Neste artigo comparamos os resultados obtidos por quatro métodos: diferença central, Newmark e sobreposição de modos juntamente com cada um dos anteriores. O método da diferença central é um esquema explícito e directo de integração, com precisão de segunda ordem se as matrizes de massa e de amortecimento forem diagonais [7]. No entanto, usando o elemento finito isoparamétrico de Sclaroff essas matrizes não são geralmente diagonais e, por isso, usamos um algoritmo modificado que faz com que a equação de equilíbrio dinâmico sofra um atraso na velocidade de meio passo de tempo [10;11]. Esta alteração tem a desvantagem de tornar a precisão do método apenas de primeira ordem. Uma outra desvantagem do método da diferença central é ser condicionalmente estável; assim, o passo de integração deve ser suficientemente pequeno para que o método não divirja [7]. O método de Newmark é um esquema implícito de integração directa, originalmente proposto em [12], que foi modificado e melhorado por muitos investigadores e aplicado à análise dinâmica de muitos problemas práticos da engenharia. Neste trabalho usamos o método sem amortecimento numérico, o que significa que os resultados têm precisão de segunda ordem e o método é incondicionalmente estável [10;11]. O método da sobreposição de modos propõe a transformação dos deslocamentos modais, , nos deslocamentos nodais, , usando a matriz dos vectores próprios Φ: . Consequentemente, a equação (3) pode ser reescrita como V U ΦVU = , (4) tttt RΦΩVVCΦΦVTT =++ &&& onde e são, respectivamente, as derivadas de primeira e segunda ordem do vector dos deslocamentos modais. V &V && Este método de integração obtém novas matrizes de massa, rigidez e amortecimento com menor largura de banda, permitindo a resolução da equação de equilíbrio com apenas uma parte dos modos de vibração dos modelos [7], reduzindo assim o custo computacional envolvido. Como um método indirecto de integração temos que aplicar um método directo para prosseguir com a resolução da equação de equilíbrio dinâmico. Neste trabalho, consideramos os dois métodos descritos anteriormente [10;11]. 5 RESULTADOS EXPERIMENTAIS Nesta secção, apresentamos alguns dos resultados experimentais obtidos usando um computador pessoal com um processador Intel Pentium D a 3GHz e 2GB de RAM. Consideremos os dois contornos apresentados na Figura 1, com 35 nodos cada, obtidos de imagens reais de um coração em diástole e em sístole. Utilizando a metodologia descrita com Patrícia C. T. Gonçalves, Raquel R. Pinho e João Manuel R. S. Tavares as propriedades mecânicas do tecido do miocárdio, todos os nodos da forma inicial são bem emparelhados com nodos da forma final. Para simular a deformação do objecto em análise, escolhemos parar o processo iterativo quando a norma euclidiana do vector dos deslocamentos fosse menor que 10-3 pixels. Usando amortecimento crítico entre 1% e 2% – quanto maior o amortecimento crítico, menor tem que ser o intervalo de tempo – o intervalo de tempo, ∆t, tem que ser menor que 0,75s para que o método da diferença central seja estável; assim, escolhemos ∆t=0,7s. A constante global de rigidez, k, foi definida como sendo igual a 100N/m. Os resultados obtidos usando cada um dos métodos de integração descritos neste artigo são numericamente equivalentes e visualmente iguais. Foram necessários 64s (65s no caso do método da sobreposição de modos com o método de Newmark) para atingir o deslocamento desejado e a distância1 entre a última forma estimada e a forma final é apenas 2,35% da distância entre as formas inicial e final do objecto. Na Figura 1 estão visíveis cinco formas intermédias simuladas usando o método da diferença central. Figura 1 - Correspondências entre os nodos de dois contornos obtidos de imagens reais de um coração (à esquerda) e cinco formas intermédias simuladas pelo método da diferença central (à direita). Ao comparar os resultados obtidos pelo método da sobreposição de modos usando diferentes números de modos de vibração, notamos que à medida que esse número diminui, a aproximação à forma final do objecto piora, Figura 2. Neste exemplo, também verificamos que usando 75% dos modos de vibração, se obtém uma forma estimada final satisfatória, mas o tempo poupado no processo computacional, apenas 1s, não compensa a perda de precisão verificada. No entanto, outros casos há que ao considerar-se uma percentagem considerável dos modos de vibração utilizados no processo de integração se conseguem bons resultados com uma diminuição significativa do custo computacional. Tal como referido anteriormente, o método da diferença central precisa de um passo de tempo reduzido para ser estável, mas o de Newmark é incondicionalmente estável e, por isso, podemos utilizar um passo de maior valor. Então, alterando ∆t para 10s e k para 1000N/m, deixa de ser possível utilizar o método da diferença central, mas consegue-se obter um deslocamento inferior a 10-3 pixels em apenas 11s, atingindo uma distância de 0,28% da 1 Consideramos distância como a norma euclidiana do vector das distâncias entre cada nodo de uma forma e o seu correspondente na forma final. Patrícia C. T. Gonçalves, Raquel R. Pinho e João Manuel R. S. Tavares distância entre as formas inicial e final do objecto. O método da sobreposição de modos com o de Newmark obtém os mesmos resultados, mas com um tempo de computação igual a 12s. Figura 2 - A preto está a forma final do objecto e a cinza a última forma simulada pelo método da sobreposição de modos com o método de Newmark utilizando, da esquerda para a direita, 50%, 75% e 100% dos modos de vibração na resolução da equação de equilíbrio dinâmico. 6 CONCLUSÕES E TRABALHO FUTURO Os resultados experimentais obtidos na determinação das correspondências e na simulação da deformação entre as duas formas dadas de um objecto são coerentes com o comportamento físico esperado, validando assim a metodologia considerada. O método da sobreposição de modos pode acelerar o processo computacional de resolução da equação de equilíbrio dinâmico se for reduzido o número de modos de vibração utilizado. No entanto, o uso de poucos modos de vibração pode comprometer significativamente a precisão dos resultados obtidos. Considerando o número total dos modos de vibração, os quatro métodos apresentados neste artigo obtêm resultados muito similares. No entanto, a estabilidade do método da diferença central é condicionada pelo passo de integração escolhido, o mesmo se passando com a estabilidade do método da sobreposição de modos quando aliado ao da diferença central. Por outro lado, o método de Newmark usado como um esquema de segunda ordem é incondicionalmente estável, permitindo a sua utilização com um passo de integração maior, fazendo com que seja mais rápida a convergência para a forma final do objecto. Aliando o método de Newmark e o método da sobreposição de modos obtém-se uma convergência ligeiramente mais lenta. Embora os resultados experimentais obtidos sejam satisfatórios, há ainda algum trabalho a realizar no futuro, como a consideração de restrições no processo de simulação para impedir que um nodo de uma forma estimada ultrapasse o seu nodo correspondente na forma final dada, a utilização de elementos finitos adequados a grandes deformações, etc. AGRADECIMENTOS Este trabalho foi parcialmente desenvolvido no âmbito do Projecto de Investigação Patrícia C. T. Gonçalves, Raquel R. Pinho e João Manuel R. S. Tavares “Segmentação, Seguimento e Análise de Movimento de Objectos Deformáveis (2D/3D) usando Princípios Físicos” financiado pela FCT - Fundação para a Ciência e a Tecnologia, com a referência POSC/EEA-SRI/55386/2004. O segundo autor agradece a bolsa SFRH/BD/12834/2003 da FCT. REFERÊNCIAS [1] D. Terzopoulos, J. Platt, A. Barr and K. Fleischer, Elastically deformable models, Proc. of the 14th Annual Conference on Computer Graphics and Interactive Techniques, Anaheim, USA, pp. 205-214, 1987. [2] S. Sclaroff, Modal Matching: a Method for Describing, Comparing, and Manipulating Digital Signals, PhD Thesis, Massachusetts Institute of Technology, Cambridge, USA, 1995. [3] L. S. Shapiro and J. M. Brady, Feature-based correspondence: an eigenvector approach, Image Vision Comput. 10 (5), pp. 283-288, 1992. [4] A. Pentland and B. Horowitz, Recovery of Nonrigid Motion and Structure, IEEE Trans. Pattern Anal. Mach. Intell. 13 (7), pp. 730-742, 1991. [5] J. M. Tavares, Análise de Movimento de Corpos Deformáveis usando Visão Computacional, PhD Thesis, Faculdade de Engenharia da Universidade do Porto, Porto, Portugal, 2000. [6] S. Sclaroff and A. Pentland, Modal Matching for Correspondence and Recognition, IEEE Trans. Pattern Anal. Mach. Intell. 17 (6), pp. 545-561, 1995. [7] K.-J. Bathe, Finite Element Procedures, Prentice-Hall, New Jersey, USA, 1996. [8] L. Bastos and J. M. Tavares, Matching of objects nodal points improvement using optimization, Inverse Probl. Sci. Eng. 14 (5), pp. 529-541, 2006. [9] M. L. Bastos, Optimização da Determinação das Correspondências Entre Objectos Deformáveis no Espaço Modal, MSc Thesis, Faculdade de Engenharia da Universidade do Porto, Porto, Portugal, 2003. [10] P. Gonçalves, R. R. Pinho and J. M. Tavares, Physical Simulation Using FEM, Modal Analysis and the Dynamic Equilibrium Equation, CompIMAGE - Computational Modelling of Objects Represented in Images: Fundamentals, Methods and Applications, Coimbra, Portugal, 2006. [11] R. R. Pinho, Determinação do Campo de Deslocamentos a partir de Imagens de Objectos Deformáveis, MSc Thesis, Faculdade de Engenharia da Universidade do Porto, Porto, Portugal, 2002. [12] N. Newmark, A Method of Computation for Structural Dynamics, ASCE J. Eng. Mech. Div. 85 (3), pp. 67-94, 1959.