Análise de movimento de corpos deformáveis usando visão computacional

João Manuel Ribeiro da Silva Tavares Análise de Movimento de Corpos Deformáveis usando Visão Computacional Julho - 2000 Universidade do Porto Faculdade de Engenharia João Manuel Ribeiro da Silva Tavares Orientador Prof. Associado do Departamento de Engenharia Electrotécnica e de Computadores da Faculdade de Engenharia da Universidade do Porto Tese submetida ao Departamento de Engenharia Electrotécnica e de Computadores para satisfação parcial dos requisitos do Doutoramento em Engenharia Electrotécnica e de Computadores Licenciado em Engenharia Mecânica pela Faculdade de Engenharia da Universidade do Porto (1992) A. Jorge Padilha Análise de Movimento de Corpos Deformáveis usando Visão Computacional Mestre em Engenharia Electrotécnica e de Computadores pela Faculdade de Engenharia da Universidade do Porto (1995) Julho - 2000 Análise de Movimento de Corpos Deformáveis usando Visão Computacional J. Tavares Julho - 2000 Agradecimentos Ao Prof. A. Jorge Padilha por todo o apoio prestado ao longo da minha dissertação de Mestrado e, especialmente, ao longo desta tese; nomeadamente, pela sua orientação e total disponibilidade sempre demonstrada e pelo seu significativo incentivo e contínuo exemplo. Aos Prof. Ana Maria Mendonça, Aurélio Campilho, Jorge Alves e Miguel Pimenta Monteiro, por todo o apoio prestado. Ao Carlos Felgueiras, ao Jorge Barbosa e ao Miguel Velhote, por todo o apoio, companheirismo e pela partilha de algumas ideias e conselhos. À Tânia Pinto e ao Paulo Vieira pela colaboração na Plataforma de Desenvolvimento e Ensaio. Aos restantes investigadores e colaboradores do Instituto de Engenharia Biomédica pelo excelente ambiente de trabalho no qual estou inserido deste a minha dissertação de Mestrado. Aos Prof. Alex Pentland, Berthold K. P. Horn, Chahab Nastar, Larry Shapiro e Stan Sclaroff, pelo envio de alguns dos seus artigos e pela disponibilidade demonstrada. À Junta Nacional de Investigação Científica e Tecnológica pela Bolsa de Mestrado, atribuída ao abrigo do Programa Ciência com a ref. BM / 3258 / 92 - RM, e pela Bolsa de Doutoramento, atribuída ao abrigo do Programa Praxis XXI com a ref. BD / 3243 / 94. Ao Instituto de Engenharia Biomédica pelos recursos utilizados ao longo desta tese. À minha família, pais e irmã, e à Cláudia pelo carinho, compreensão, paciência, incentivo, .... A TODOS AQUELES QUE TORNARA M ESTA PUBLICAÇÃO POSSÍVEL ... Sumário O tema desta tese está inserido no domínio da visão por computador e na área da análise de movimento de corpos deformáveis. O seu interesse tem vindo a aumentar consideravelmente nos últimos tempos devido, sobretudo, ao fracasso das tentativas de utilizar as metodologias normalmente associadas aos corpos rígidos para a análise do movimento não rígido, e também ao elevado número de aplicações que existem para tal análise. O enorme potencial de aplicação existente na área da imagem médica, nomeadamente na segmentação, no emparelhamento e na análise e seguimento do movimento de estruturas, é responsável por grande parte do trabalho realizado neste âmbito. Outras aplicações que podem ser referidas são o seguimento de sistemas articulados, a análise do escoamento de fluidos, do movimento de nuvens para a previsão meteorológica, do comportamento de materiais sob a acção de forças, a análise e reconhecimento de faces, de veículos e de caracteres, etc. Ao contrário do que sucede com os objectos rígidos, a representação da forma de um objecto deformável está fortemente relacionada com a análise e seguimento do seu movimento e, para se desenvolverem técnicas para resolver tais problemas, é necessário utilizar determinadas restrições sobre o movimento/forma o que, consequentemente, individualiza as abordagens desenvolvidas e as torna específicas para determinadas classes de problemas. A abordagem utilizada para o desenvolvimento desta tese foi constituída pelas seguintes etapas: estudo bibliográfico de algumas das metodologias actualmente existentes e verificação das suas aplicações; desenvolvimento de uma nova aplicação, que além de constituir um sistema para integração dos algoritmos desenvolvidos e permitir o ensaio e a análise dos resultados obtidos, fosse também, por si só, um sistema para a análise e processamento de imagem de utilização flexível e, ao mesmo tempo, uma plataforma de desenvolvimento e ensaio para outros investigadores; estudo e implementação de metodologias que permitissem determinar a correspondência entre dois objectos 2D deformáveis; estudo e implementação de uma abordagem baseada em princípios físicos para determinar a mesma correspondência, estimar os deslocamentos em função das propriedades do material elástico simulado, e traduzir a transformação existente; evolução de modelos 2D do tipo contorno para modelos superficiais, construídos utilizando o nível de intensidade de cada pixel como a sua terceira coordenada, estendendo as abordagens utilizadas para este tipo de modelo; ensaio da metodologia física, dos modelos utilizados e do sistema desenvolvido numa aplicação exemplo. Esta tese é constituída por oito capítulos: no primeiro, é realizada uma introdução ao tema e à abordagem utilizada, são descritos, de forma resumida, cada um dos restantes capítulos e indicadas as contribuições inovadoras; no capítulo seguinte, são apresentados os fundamentos das metodologias existentes, classificado o movimento não rígido, descritos com maior detalhe os modelos deformáveis e referenciadas algumas das suas aplicações, nomeadamente na área da imagem médica; no terceiro capítulo são apresentadas duas metodologias para a determinação da correspondência utilizando análise modal da forma dos objectos a emparelhar; no capítulo seguinte, é descrita uma abordagem na qual é utilizada modelização física, por intermédio do método dos elementos finitos, e emparelhamento modal, para determinar a correspondência, estimar os deslocamentos e traduzir a deformação existente; os modelos físicos e suas construções são descritos no quinto capítulo; no sexto capítulo, é descrita a plataforma de desenvolvimento e ensaio criada; no penúltimo capítulo são apresentados ensaios de aplicação da abordagem física, dos modelos utilizados e da plataforma desenvolvida em imagens de pedobarografia dinâmica; finalmente, no último capítulo, são apresentadas algumas conclusões finais e perspectivas de trabalho futuro. Summary The theme of this thesis is in the computer vision domain and more specifically in the area of motion analysis of deformable bodies. The interest in this field has risen significantly in the last few years due to the failure of adapting existing rigid-body methods and to the very wide range of potential applications. A strong impulse originated in the area of medical imaging for segmenting, matching and tracking body structures, but other application domains have also contributed, namely the tracking of articulate systems, the analysis of fluids flow, the movement of clouds for weather forecasting, the structural analysis of materials, the recognition of faces, vehicles and characters, etc. Unlike rigid objects, the shape representation of deformable objects is strongly related with the analysis and tracking of its motion and thus, in order to develop suitable approaches and techniques for analysis, certain restrictions and constraints on the shape/motion must be specific to the type of task under consideration. The work plan for this thesis was made of the following tasks: bibliographical study of some of the current methodologies and analysis of their applications; development of a new software system that, apart from incorporating the specific results to be obtained in the deformation and motion analysis, would have a flexible and modular structure enabling to play the dual role of a development and test platform and of a general-purpose image processing and analysis package; design and implementation of methodologies for matching and interpolating 2D deformable objects and for measuring the amount of deformation, focusing on physically-based approaches; evolution from 2D contour models to 3D surface models; testing of the methods designed in a real world medical application example. The thesis is organized in eight chapters: the first one provides an introduction to the theme and a brief summary of the remaining chapters and identifies the main contributions of the work reported; existing methods are reviewed in the second chapter, the non rigid motion is classified and the deformable models are described with some detail as well as some of their applications, specially in the field of medical imaging; the third chapter presents two methodologies for shape matching using modal analysis; in the following chapter, the physically-based approach is described, using the finite elements method and modal analysis for matching, for estimating the displacement of unmatched nodes and for quantifying the deformation; the object models and the construction of the FEM models are described in the fifth chapter; the sixth chapter describes the development and test platform system; overall testing of the methodology is reported in the next chapter, using dynamic pedobarography data; finally, the last chapter draws the final conclusions and briefly presents plans for further work. Résumé Le thème de cette thèse est inséré dans le domaine de la vision par ordinateur et particulièrement dans l’analyse du mouvement de corps déformables. L’intérêt par ce thème s’est développé considérablement pendant les dernières années, ce qui se doit surtout à l’échec des tentatives de faire usage des méthodes connus pour corps rigides dans le domaine non-rigide, et aussi au grand nombre potentiel d’applications. La thématique de l’imagerie médicale est la responsable majeure de la recherche récente dans ce domaine, soit pour faire la segmentation, soit l’alignement et le suivi de structures. Néanmoins, il y a d’autres domaines où la littérature scientifique rapporte des applications importantes: la pousuite de systèmes articulés, l’analyse de l’écoulement de fluides, la prévision météorologique basée sur le mouvement des nuages, la reconnaissance de visages, de véhícules ou de caractères, etc. Au contraire de ce qu’il se passe pour les objets rigides, la représentation de la forme d’un objet déformable est fortement racontée avec l’analyse et suivi de son mouvement et, pour développer des techniques qui résoudrent ces problèmes il faut se borner à certaines restrictions sur le mouvement/forme ce qui, par conséquent, singularise les approches développées et les rend spécifiques de certaines classes de problèmes. L’approche utilisée pour le développement de cette thèse a été constituée par les étapes suivantes: étude bibliographique de quelques-unes des méthodologies existantes et vérification de leurs applications; développement d’une nouvelle application logicielle qui constitue un système pour l’intégration et l’essai des algorithmes développés et l’analyse des résultats obtenus et qui soit aussi, par soi-même, un système générique et d’usage flexible pour le traitement et l’analyse d’images; étude et mise en oeuvre de méthodologies pour déterminer la correspondance entre deux objets déformables (2D); étude et mise en ouevre d’une approche basée sur des principes physiques pour déterminer la même correspondance, estimer les déplacements en fonction des propriétés du matériau élastique simulé, et traduire la transformation existante; évolution de modèles 2D pour modèles 3D du type surface, construits en employomt le niveau d’intensité de chaque pixel comme sa troisième coordonnée, et en étendant les approches utilisées pour ces modèles; essai de la méthodologie physique, des modèles employés et du système dans une application réelle. Cette thèse est constituée par huit chapitres: au premier chapitre une introduction au thème et à l’approche utilisée est accomplie, chacun des chapitres suivants est décrit d’une façon résumée et les contributions innovatrices sont énumérées; au chapitre suivant, les principes des méthodologies en existance sont présentés, le mouvement non rigide est classé, les modèles déformables sont décrits en détail et quelques-unes de ses applications son indiquées, surtout dans le domaine de l’image médicale; au troisième chapitre deux méthodologies sont présentées pour la détermination de correspondances en employant l’analyse modale de la forme des objets à apparier; au chapitre suivant on décrit une approche dans laquelle la modélisation physique est employée selon la méthode des éléments finis, et l’appariement modal permet de déterminer la correspondance, estimer les déplacements et quantifier la différence entre les formes; les modèles physiques et ses constructions sont décrits au cinquième chapitre; au sixième chapitre, on décrit le système de développement et d’essai; à l’avant-dernier chapitre on présente quelques essaies de l’approche physique, des modèles développés et du système dans le domaine de la pédobaragraphie dynamique; finalement, au dernier chapitre sont présentées des conclusions finales et des perspectives de travail futur. Índice INTRODUÇÃO À TESE E À SUA ESTRUTURA 3 1.1 – Introdução Numerosos seres vivos têm no seu sistema de visão o elemento sensorial mais importante para a sua sobrevivência e para as suas condições de vida. A importância do sistema de visão prende-se com a riqueza de informação que este faculta, não só em termos quantitativos, mas também qualitativos. Tais informações permitem, por exemplo, a detecção e o seguimento de certos alvos (predadores, alimento, etc.), a determinação de obstáculos na sua trajectória, em suma, informações sobre o ambiente que rodeia cada ser. Neste contexto, não é surpreendente que a comunidade científica tenha, nos últimos tempos, realizado intensos esforços no sentido de prover sistemas automáticos, isto é sistemas computadorizados, que sejam capazes de executar funções do sistema de visão que são normalmente encontradas nos sistemas equivalentes dos seres vivos, e em especial no sistema visual humano. A tentativa de implementar certas funções do sistema de visão humana em sistemas automáticos pode ser realizada quer ao nível de software, quer ao nível de hardware. Surge, assim, uma área de desenvolvimento científico que é designada por processamento de imagem e visão por computador ou visão artificial. O processamento de imagem e a visão por computador são normalmente divididos em quatro áreas de actuação: a) melhoramento ou realce de imagens: consiste basicamente na tentativa de melhorar e realçar subjectivamente certas características de uma dada imagem (por exemplo, acentuar contraste, reduzir ruído, etc.); b) restauração de imagens: consiste basicamente na tentativa de restaurar imagens que tenham sido degradadas na sua qualidade por um qualquer processo, como por exemplo distorção geométrica, movimento, etc.; c) compressão de imagens: consiste basicamente na tentativa de representar uma imagem original de forma mais simples e portanto mais leve, sem contudo perder informação necessária; d) análise de imagens: consiste basicamente em descrever ou interpretar uma dada imagem ou sequência de imagens; isto é, na tentativa de medir, reconhecer, classificar uma imagem ou conjunto de imagens. As três primeiras áreas costumam ser agrupadas na designação de processamento de imagem; a última está mais ligada à visão por computador e aparece por vezes associada à inteligência artificial. Naturalmente que surgem inúmeras situações em visão por computador em que todas as áreas anteriores aparecem perfeitamente combinadas e integradas. Um exemplo desta combinação pode ser, por exemplo, um sistema que procure analisar o movimento de certos objectos a partir de uma sequência de imagens. Este sistema deverá incluir, quase obrigatoriamente, funções de melhoramento das imagens originais (compensação de ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 4 iluminação, remoção de ruído), de restauração das imagens degradadas geometricamente, de análise das imagens e, porventura, pode ser utilizada compressão (para efeitos de arquivo ou de transmissão). Na actualidade, surgem cada vez mais aplicações do processamento de imagem e da visão por computador. Como exemplos de tais aplicações podem ser referidos os seguintes: • inspecção industrial: na indústria, a qualidade do produto final tem cada vez mais um papel de importância primordial. Como, geralmente, as funções de inspecção visual humana são bastante rotineiras, cansativas, morosas, e consequentemente originam frequentemente falhas e erros, surge a necessidade de as automatizar por sistemas computadorizados (utilizando, por exemplo, robots e manipuladores em tais tarefas). É evidentemente necessário prover estes sistemas de “visão”; surge, assim, uma área importante da visão por computador em que o objectivo é o controlo dimensional de componentes, o controlo da sua qualidade superficial ou a verificação da integridade dos mesmos. • no guiamento de veículos autónomos: cada vez mais se pretende substituir operários a cumprir funções pesadas e perigosas para a sua integridade física. Surgem assim veículos, robots ou manipuladores que, possuindo sistemas de condução autónoma, se podem mover em ambientes hostis para o homem transportando diferentes tipo de materiais e produtos. Se estes sistemas autónomos dispuserem de informação visual sobre o ambiente que os rodeia, poderão ser mais “inteligentes” e guiar-se de forma mais correcta e segura, pois podem seguir a melhor trajectória possível e de forma mais rápida. • compressão de imagens: quando se pretende armazenar um elevado número de imagens, torna-se essencial diminuir o volume da respectiva informação. Tal redução pode também ser necessária na transmissão de imagens, em que a largura de banda é inevitavelmente reduzida. Técnicas de compressão de imagem desempenham um papel fulcral em inúmeros sistemas de arquivo e comunicação de imagens, em especial com o advento e proliferação de sistemas multimédia. • aplicações médicas: na medicina existem bastantes imagens de diagnóstico obtidas por diferentes processos e técnicas (como por exemplo por raios-X, ecografia, endoscopia, etc.). Tais imagens necessitam de ser processadas no sentido de remover ruído, melhorar algumas características e analisá-las. A análise não é geralmente pretendida com um sentido perfeitamente autónomo mas como um auxiliar importante ao diagnóstico efectuado pelos especialistas. Não é, assim, surpreendente encontrar um elevado número de aplicações de processamento de imagem e de visão por computador em medicina. • recuperação de imagens degradadas: certas imagens são obtidas com uma inevitável INTRODUÇÃO À TESE E À SUA ESTRUTURA 5 deterioração; tal pode ser devido às más condições de iluminação, influência de campos eléctricos e/ou magnéticos, às elevadas distâncias de transmissão, etc. Nestas situações, é necessário realizar uma melhoria da qualidade das imagens. Por curiosidade, refira-se que uma das primeiras aplicações do processamento de imagem se refere à recuperação das imagens enviadas para a Terra por um sonda espacial em 1960. A deterioração ficava-se a dever a elevadas restrições acerca do peso do sistema de visão [Lim, 1990], implicando assim que o sistema de imagem a bordo da sonda fosse de reduzida qualidade. • na meteorologia: pela análise do movimento das nuvens, sistemas de visão por computador podem auxiliar em estudos de previsão do estado do tempo. • em sistemas de tráfego automóvel: cada vez mais pretende-se dotar os sistemas de gestão de tráfego automóvel actualmente existentes com sistemas de visão por computador. Tal incorporação tem como objectivo tornar a gestão mais flexível, eficiente e rápida. • na agricultura: na análise do crescimento e grau de maturação das plantações, a visão por computador, baseada em imagens de detecção remota, surge cada vez mais como um sistema bastante útil para análise e controlo. Os exemplos anteriores, apesar de em número reduzido, evidenciam perfeitamente a utilidade do processamento de imagens e da visão por computador no dia a dia da humanidade. O tema desta tese insere-se no domínio da visão por computador, em particular na análise de movimento e deformação. A análise de movimento tem vindo a ser, nas duas últimas décadas, uma área importante de investigação no domínio da visão por computador. O problema da análise de movimento é tradicionalmente definido como a determinação do movimento de um objecto a partir de uma sequência de imagens, 2D ou 3D, capturadas em dois ou mais instantes de tempo. O problema designado por obtenção da estrutura a partir do movimento apresenta ainda um objectivo adicional: obtenção da estrutura geométrica e também dos parâmetros do movimento a partir de uma sequência de projecções [Tavares, 1995, 1995a]. Uma grande percentagem do trabalho envolvendo a análise de movimento foi realizada nesta área, devido à sua elevada importância no processamento de cenas, assumindo que os objectos em questão têm formas constantes ao longo de toda a sequência. Esta restrição de rigidez é inadequada em muitas situações de análise de movimento, pois muitos objectos reais, com exactidão todos, são deformáveis. Por exemplo: as árvores balançam, as folhas de papel dobram-se, as roupas enrugam-se, o corpo humano apresenta movimento contínuo não rígido, etc. Nos anos mais recentes, um crescente volume de investigação na análise de movimento ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 6 não rígido tornou-se aparente. Grande parte do impulso verificado nesta área deriva das aplicações potenciais na área da imagem médica e na compressão de imagem baseada em modelos. Várias aplicações existem na área biomédica, tais como o estudo do movimento do coração e do pulmão, estudo do fluxo sanguíneo e a análise do crescimento de tumores. Por exemplo, um dos objectivos na imagem cardíaca é a análise do movimento não rígido e estimar as características da deformação do coração. Nesta aplicação, dispositivos adequados de ressonância magnética ou tomografia computorizada adquirem dados 3D do coração em vários instantes durante o ciclo cardíaco. Uma análise da gama dos parâmetros do movimento pode auxiliar na triagem de pacientes e na decisão da extensão das lesões cardíacas existentes. Um outro exemplo é a compressão de imagem baseada em modelos, para teleconferência a elevadas velocidades de transmissão. Desde que os parâmetros do movimento, ou as correspondências pontuais do movimento facial, possam ser estimados, as imagens podem ser eficientemente codificadas e transmitidas, reduzindo significativamente a largura de banda necessária, em comparação com as abordagens estatísticas tradicionais. Existem muitas outras aplicações da análise de movimento não rígido. Algumas que podem ser citadas são: estudo do movimento dos lábios, para leitura labial; reconhecimento de faces para aplicações de segurança; deformações de material para inspecção visual de estruturas, tais como inspecções de barragens, de pontes e de crescimento de cristais; seguimento da formação de nuvens para previsão meteorológica. A visão artificial em aplicações robóticas também necessita de considerar a não rigidez das formas: partes articuladas e flexíveis são abundantes em ambientes industriais. Adicionalmente, aplicações de realidade virtual requerem métodos para a construção e simulação de modelos de objectos rígidos e não rígidos. 1.2 – Objectivos e abordagem seguida Enunciam-se de seguida os principiais objectivos traçados inicialmente para esta tese, a estratégia e abordagens consideradas e, de forma resumida, o trabalho realizado. Os principais objectivos formulados inicialmente foram os seguintes: a) estudo das várias metodologias existentes para a análise e seguimento de movimento de corpos deformáveis; em vez de se partir de um problema concreto, procurou-se criar um quadro geral para tratamento de múltiplos casos de análise de movimento e deformação; no mesmo sentido, em todo o desenvolvimento e implementação, procurou-se manter acessíveis os parâmetros de controlo e de análise de resultados, como se pode constatar em diversas das janelas de interface da aplicação apresentadas no sexto capítulo. b) criação de uma plataforma de desenvolvimento e ensaio para análise e processamento de imagem que, além de possibilitar uma utilização flexível, permitisse a integração de INTRODUÇÃO À TESE E À SUA ESTRUTURA 7 novos algoritmos de forma totalmente transparente. O uso da plataforma como sistema de desenvolvimento, por parte de diversos investigadores, facilita a sua continuada manutenção e actualização. Por outro lado, a estrutura modular da plataforma permite também configurar múltiplos sistemas de aplicação que disponibilizem apenas a funcionalidade adequada. De forma mais específica, são ainda objectivos desta tese: c) implementar e desenvolver metodologias para a determinação da correspondência entre dois objectos; d) estimar de forma consistente os deslocamentos pontuais para cada objecto; e) medir globalmente a deformação existente entre dois objectos previamente emparelhados; f) determinar a transformação rígida que melhor traduz a componente rígida da transformação global existente entre dois objectos previamente emparelhados; g) passar de modelos 2D para modelos superficiais utilizando as mesmas metodologias para determinar a correspondência, estimar os deslocamentos, determinar a deformação existente e a transformação rígida envolvida. No cumprimento de tais objectivos estiveram sempre presentes as seguintes considerações: a) as abordagens a utilizar não deveriam estar sujeitas nem limitadas a nenhuma aplicação específica; b) os dados a considerar para cada objecto deveriam ser apenas os seus pontos (ou parte deles) evitando-se, deste modo, estruturas mais complexas e de mais difícil construção; c) os algoritmos utilizados deveriam ser implementados numa plataforma comum e de uso geral; d) sempre que uma ferramenta, ou conjuntos de ferramentas, estivesse disponível no domínio público, deveria ser integrada no sistema desenvolvido e reutilizada. Utilizando estas considerações, o trabalho desenvolvido ao logo desta tese pode ser descrito de forma resumida do seguinte modo: A primeira etapa concentrou-se no estudo bibliográfico de várias metodologias e em aplicações actualmente existentes no domínio da análise e seguimento de corpos deformáveis. Na etapa seguinte, procedeu-se à criação de uma plataforma de desenvolvimento e ensaio que permitisse a incorporação das metodologias implementadas ao longo da tese e a análise dos resultados obtidos. Assim, construiu-se um sistema de análise e processamento de imagem para sistemas operativos Microsoft Windows, utilizando o ambiente de programação ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 8 integrado Microsoft Visual C++. Este sistema, além de possuir as funções básicas e comuns para uma aplicação de análise e processamento de imagem, permite que sejam integrados, de forma transparente e flexível, novos algoritmos. Desde a sua criação foram já incorporadas várias funções, contendo a sua versão actual um número de funções já bastante apreciável. Após a construção do sistema base de análise e processamento de imagem procedeu-se à integração no mesmo das ferramentas desenvolvidas durante o curso de mestrado do autor desta tese para a detecção e seguimento de linhas, aproximação poligonal de linhas, simplificação de segmentos de recta e seguimento de segmentos de recta ao longo de sequências de imagem utilizando filtragem de Kalman [Tavares, 1995, 1995a]. Essa abordagem, bastante comum e satisfatória para objectos rígidos, foi testada em sequências de imagens com objectos deformáveis. Os resultados obtidos permitiram-nos concluir que, se o movimento entre as imagens for muito reduzido e os contornos dos objectos puderem ser representados de forma razoável por segmentos de recta, a referida abordagem conduz a bons resultados. Contudo, como seria de esperar, quando os contornos não são representados de forma adequada por segmentos de recta e o ritmo de amostragem não é suficientemente rápido, a abordagem torna-se inadequada. Ainda poderia ser ultrapassada essa incapacidade, se os contornos fossem aproximados por curvas paramétricas, por exemplo por splines. Tal seria bastante similar a algumas metodologias já existentes, nomeadamente as snakes de Kalman (ver segundo capítulo), no entanto, existiria sempre a restrição de o movimento entre as imagens a considerar ter que ser necessariamente reduzido. Após este primeiro teste, procedeu-se à implementação de metodologias para a determinação dos contornos dos objectos presentes em cada imagem. Como os contornos determinados poderiam ter um número elevado de pixels, implementou-se um algoritmo para se proceder à sua amostragem, utilizando critérios de largura máxima do intervalo entre pixels e do valor da curvatura. Assim, tornou-se possível obter contornos com densidade adaptativa de maneira a concentrar mais pixels nas zonas onde existem variações de curvatura mais acentuadas. Estando os contornos dos objectos presentes em cada imagem determinados e amostrados, procedeu-se à implementação de duas metodologias para a determinação da correspondência entre dois objectos, baseadas na análise dos valores e vectores próprios de matrizes descritivas dos mesmos. Estas metodologias foram testadas para diferentes objectos rígidos e deformáveis, realizando-se uma análise detalhada dos resultados obtidos. Como os objectos reais deformáveis são simulados de forma mais adequada por modelos deformáveis elásticos, procedeu-se à modelização física dos objectos a considerar por intermédio do método dos elementos finitos. Essa modelização foi efectuada utilizando-se dois tipos de elementos finitos: um único elemento isoparamétrico, construído utilizando funções de interpolação de base Gaussiana, e elementos axiais standard devidamente agrupados. A determinação das correspondências é obtida pela análise das trajectórias de cada nodo no respectivo espaço modal. Além das correspondências, esta modelização permite obter uma estimativa, consistente com as propriedades do material simulado, por minimização da INTRODUÇÃO À TESE E À SUA ESTRUTURA 9 energia de deformação, para os deslocamentos dos nodos. Esta energia de deformação, distribuída ao longo dos modos de vibração dos modelos, permite traduzir quantificadamente a transformação existente entre os dois objectos, sendo possível distinguir perfeitamente as parcelas referentes à transformação rígida e às deformações locais. Esta metodologia foi aplicada a vários objectos rígidos e deformáveis, procedendo-se a uma análise detalhada dos resultados obtidos. Ao longo do trabalho desenvolvido, tornou-se ainda mais evidente a necessidade de implementar uma metodologia para a obtenção da transformação rígida que melhor traduzisse a parte rígida da transformação global existente entre dois objectos previamente emparelhados. Assim, tal implementação foi realizada utilizando-se um método baseado em quaternions unitários. Estando implementadas várias metodologias para determinar a correspondência entre objectos 2D que conduziam a resultados bastante satisfatórios, evoluiu-se para modelos superficiais. Estes novos modelos resultam da utilização do nível de intensidade como a terceira coordenada de cada pixel do objecto presente na imagem 2D. (Deve-se notar que, naturalmente, os métodos desenvolvidos são directamente aplicáveis a objectos representados no espaço tridimensional.) A amostragem de cada objecto no espaço 2D foi conseguida de duas maneiras distintas: uma utilizando uma malha rectangular regular e uma outra utilizando uma malha adaptativa construída por análise dos perfis radiais de intensidade centrados nos máximos. Para a construção destas superfícies tornou-se evidente que seriam úteis ferramentas para realizar a triangulação de pontos não estruturados, e para simplificar e suavizar a malha triangular resultante. Assim procedeu-se à integração na plataforma de desenvolvimento e ensaio da biblioteca de domínio público VTK - The Visualization Toolkit [Schroeder, 1996, 1998, 1999]. Após essa integração, as metodologias utilizadas com modelos 2D foram estendidas para este tipo de modelo e foram realizados vários testes e analisados os resultados obtidos. Com a modelização superficial tornou-se possível representar, utilizando um único modelo, objectos que no plano imagem podem ser constituídos por diversas entidades. Deste modo, diminui-se a dificuldade do problema original e, ao mesmo tempo, torna-se possível desprezar a eventual fusão e/ou divisão das entidades, que pode ocorrer ao longo do movimento no plano imagem. Obviamente que esta modelização se torna mais apropriada, e com maior significado intuitivo, se o nível de intensidade de cada pixel estiver relacionado com alguma característica do objecto a modelizar. Essa relação, entre o nível de intensidade e a terceira coordenada, é verificada em imagens de pedobarografia dinâmica nas quais o nível de intensidade está directamente relacionado com a pressão exercida, sobre o sistema sensor, pelo pé em estudo. Assim, e a título de exemplo, as várias metodologias e modelizações implementadas na tese foram aplicadas em imagens de pedobarografia dinâmica, tendo-se verificado que, apesar dos bons resultados obtidos na determinação das correspondências entre contornos 2D, a evolução para os modelos superficiais de intensidade, além de também originar resultados bastante ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 10 satisfatórios, evitou o aumento da complexidade provocada pela possibilidade de existirem mais do que apenas um contorno em cada imagem e de ocorrer a divisão e/ou fusão entre os mesmos. 1.3 – Estrutura organizativa da tese Pretendeu-se estruturar esta tese de forma a maximizar a autonomia e a independência entre os seus capítulos. Apresentam-se de seguida, de forma resumida, os restantes sete capítulos e o único anexo que constituem esta publicação: • CAPÍTULO II MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS Neste capítulo são apresentadas várias metodologias actualmente existentes no domínio desta tese e são indicados vários exemplos de aplicações. Após a introdução de alguns fundamentos, o movimento não rígido é classificado e, para cada classe resultante, são indicadas as restrições e as condições inerentes e verificados alguns trabalhos realizados no seu âmbito. Como uma grande parte do trabalho realizado envolve o desenvolvimento e a utilização de modelos deformáveis, o destaque deste capítulo concentra-se nesse tipo de modelos. Assim, estes modelos são descritos com alguma profundidade e são analisadas várias aplicações principalmente na área da imagem médica, nomeadamente na segmentação e na análise e seguimento de movimento não rígido. • CAPÍTULO III DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA Como já foi referido, ao longo do trabalho desenvolvido verificou-se ser de grande interesse a possibilidade de separar a transformação existente entre dois objectos em dois tipos: rígida e local ou de deformação. Assim, foi implementado um método, baseado em quaternions unitários, para se determinar a transformação rígida existente e que necessita de apenas um reduzido número de emparelhamentos entre os pontos que constituem cada objecto; o referido método é apresentado no início deste capítulo. É depois descrito um método para a determinação de correspondências entre pontos, 2D e 3D, de dois objectos baseado no princípio da distância mínima. Como o método referido anteriormente não produz bons resultados quando os objectos têm formas, ou posicionamento, ou orientação, ligeiramente diferentes, é descrito um novo método, baseado neste, que utiliza informação sobre as duas formas a emparelhar, obtida a partir dos valores e dos vectores próprios de uma matriz construída para cada objecto, e obtém resultados satisfatórios para as referidas situações. INTRODUÇÃO À TESE E À SUA ESTRUTURA 11 • CAPÍTULO IV DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL No capítulo anterior foram apresentados dois métodos para a determinação de correspondências entre objectos, 2D ou 3D, rígidos ou não, baseados na construção de matrizes de proximidade, construídas a partir das coordenadas dos seus pontos, e na análise dos valores e dos vectores próprios destas matrizes para o estabelecimento das correspondências. Neste capítulo é apresentada uma nova abordagem, com o mesmo objectivo, mas na qual é utilizada uma modelização física, pelo método dos elementos finitos, dos objectos a emparelhar considerando que estes são construídos por um determinado material virtual, e determinando as correspondências pela análise das trajectórias dos nodos de cada objecto no respectivo espaço modal. No início deste capítulo é realizada uma breve introdução ao método dos elementos finitos e, a seguir, é realizada uma apresentação introdutória à análise modal. • CAPÍTULO V MODELOS PONTUAIS E ELEMENTOS FINITOS UTILIZADOS É descrito neste capítulo o processo utilizado para construir os modelos dos objectos baseados na sua modelização física. Assim, em primeiro lugar, são apresentados os dois tipos de modelos finitos que foram utilizados: um no qual é utilizado um único elemento finito isoparamétrico, que utiliza funções de interpolação de base Gaussiana entre todos os nós que constituem cada objecto a modelizar, e um outro que utiliza na modelização de cada objecto elementos finitos axiais standard devidamente agrupados. São descritos os procedimentos utilizados na determinação dos nodos dos modelos do tipo contorno e do tipo superfície de intensidade. Também são apresentados neste capítulo alguns resultados experimentais obtidos na análise modal de vibração em modo livre, na determinação de correspondências, na estimação de deslocamentos, e na utilização da energia de deformação como indicação da deformação existente. • CAPÍTULO VI PLATAFORMA DE DESENVOLVIMENTO E ENSAIO Durante o trabalho relacionado com esta tese foi criada, expandida e utilizada, uma plataforma de desenvolvimento e ensaio para o processamento e análise de imagem. Esta plataforma, desenvolvida em linguagem C++ no sistema integrado de desenvolvimento Microsoft Visual C++ para sistemas operativos Microsoft Windows 95/98/NT/2000, obedece a uma filosofia que permite que a mesma seja, por si só, uma aplicação para o processamento e análise de imagem dos mais diversos tipos mas também, um sistema base no qual outros investigadores possam desenvolver e posteriormente integrar os seus algoritmos. Neste capítulo é apresentada a plataforma de desenvolvimento e ensaio, nomeadamente: a sua concepção, as bibliotecas de domínio público integradas, as entidades actualmente suportadas, a sua interface, o modo como se processa a integração de uma nova função e as ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 12 operações actualmente disponíveis, quer de âmbito geral, quer as mais específicas desta tese. • CAPÍTULO VII ENSAIOS EM IMAGENS DE PEDOBAROGRAFIA DINÂMICA Neste capítulo são apresentados ensaios de aplicação da metodologia desenvolvida em sequências de imagem de pedobarografia dinâmica. Não se pretende tratar o problema geral de aplicação em pedobarografia dinâmica mas, tão só, usar esse domínio como fonte de dados. São apresentados resultados obtidos na determinação de correspondências, na utilização da energia de deformação para medida das deformações existentes, e na estimação dos deslocamentos nodais por minimização da referida energia, entre objectos do tipo contorno 2D, superfície de intensidade (construídas utilizando-se amostragem regular ou amostragem adaptativa) e contornos de isonível. Antes da apresentação dos resultados obtidos é realizada uma introdução breve à pedobarografia dinâmica. • CAPÍTULO VIII CONCLUSÕES FINAIS E PERSPECTIVAS DE DESENVOLVIMENTO FUTURO Neste capítulo são apresentadas algumas conclusões finais sobre o trabalho desenvolvido, sobre a filosofia que o orientou e sobre os resultados experimentais obtidos. Também são indicadas algumas perspectivas de desenvolvimento futuro, as quais serão consideradas no prosseguimento do trabalho realizado. • ANEXO IMAGENS A CORES Este anexo é constituído pelas versões coloridas de algumas das imagens apresentadas, em níveis de cinzentos, ao longo dos capítulos que constituem esta tese. Com este anexo esperase, de algum modo, facilitar a interpretação de algumas imagens que pareceram mais relevantes. 1.4 – Contribuições principais da tese Como principais contribuições, algumas com carácter inovador, obtidas pelo trabalho realizado nesta tese, podem ser referenciadas as seguintes: • No domínio do tema da tese: O estudo, de certo modo aprofundado, das várias metodologias, e suas aplicações, existentes no domínio da análise e seguimento de corpos deformáveis, que se espera ser de utilidade em trabalhos futuros, dada a actual carência de boas revisões do estado da arte neste domínio. MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 21 estatísticas serão referidas na secção 2.2.4. Conquanto as primeiras representações de objectos baseadas em princípios físicos permitissem uma melhor modelização das deformações não rígidas, elas apresentam a desvantagem de serem baseadas na técnica matemática das diferenças finitas para a discretização e integração numérica das equações físicas inerentes. A utilização das diferenças finitas origina problemas severos com a amostragem, pois não permite a fixação das molas elásticas em pontos diferentes dos nodos de discretização. Este problema pode ser compensado pelo aumento do número de pontos de discretização, mas o tempo de cálculo é fortemente penalizado. 2.2.2 – Método dos elementos finitos Para resolver de forma adequada os problemas associados à amostragem e à escala, pode-se utilizar o método dos elementos finitos na modelização física. Esta abordagem foi considerada na modelização de objectos sólidos deformáveis superquádricos em [Pentland, 1990, 1991] e posteriormente em [Terzopoulos, 1991]. Em [Cohen, 1990] é apresentada uma formulação para as snakes utilizando o método dos elementos finitos, que resultou na modelização de um objecto em termos de balões 3D deformáveis que podem ser insuflados para se ajustarem a conjuntos de dados de imagens médicas e de outros tipos [Cohen, 1992]. No método dos elementos finitos as funções de interpolação usadas permitem a consideração da continuidade das propriedades do material, tal como a massa e a rigidez, de forma a serem integradas ao longo da região de interesse. Note-se que, apesar da similaridade das equações resultantes, tal abordagem é bastante diferente da baseada na técnica das diferenças finitas [Bathe, 1996; Pentland, 1991; Segerlind, 1984]. Particularmente significativo é que o método dos elementos finitos disponibiliza uma caracterização analítica da superfície entre nodos e pode garantir convergência para uma solução [Bathe, 1996], enquanto os métodos de diferenças finitas não o permitem. Contudo, indiferentemente da utilização do método dos elementos finitos ou das diferenças finitas, as representações baseadas em princípios físicos não podem ser utilizadas directamente na comparação de objectos. Virtualmente todos os métodos baseados em splines, em placas finas ou em polinómios apresentam esta inadequação para a obtenção de descrições canónicas [Sclaroff, 1995]; tal problema deve-se ao facto de os parâmetros para as superfícies poderem ser definidos de forma arbitrária, e assim não serem invariantes às alterações do ponto de vista, às oclusões, ou às deformações não rígidas. Para uma qualquer representação que utilize malhas, o único método geral para determinar se duas superfícies são equivalentes é gerar um número de pontos amostrados em posições correspondentes nas duas superfícies e observar as distâncias entre esses dois conjuntos de pontos. Além de se tratar de uma abordagem grosseira e custosa, pode acontecer que as superfícies apresentem parametrizações bastante diferentes o que implica o aumento da dificuldade na geração dos pontos de ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 22 amostragem em posições correspondentes. 2.2.3 – Decomposição modal Para resolver o problema de não unicidade da representação obtida pela utilização de modelos deformáveis segundo princípios físicos foi apresentada uma solução baseada na análise modal em [Pentland, 1991]. Na análise modal, as equações resultantes do método dos elementos finitos são simplificadas por expressão destas equações dinâmicas utilizando os vectores próprios do modelo. Estes vectores próprios são designados por modos de deformação do modelo e, em conjunto, formam uma base ortonormal ordenada pela frequência para representação da forma do mesmo. A análise modal foi aplicada em problemas de obtenção da forma e de reconhecimento [Pentland, 1989a, 1990, 1991], e também para o seguimento de movimento não rígido [Pentland, 1989, 1991a]. Basicamente, a representação modal apresenta a vantagem de desagrupar os graus de liberdade do sistema dinâmico não rígido. Desacoplando os graus de liberdade obtêm-se vantagens substanciais, a mais importante das quais é o problema original se tornar mais simples e resolúvel de forma eficiente. A transformação modal, por si só, não reduz o número de graus de liberdade, e assim a representação modal completa apresenta o mesmo problema de não unicidade de outras representações. A solução do problema passa pela eliminação de um número suficiente dos modos de frequências mais elevadas; a utilização de uma representação modal de base reduzida também origina uma representação única da forma, pois os modos formam um conjunto de base ortonormal ordenado pela frequência, semelhante à decomposição de Fourier. Tal como na decomposição de Fourier, desde que seja assumida uma subamostragem regular, a redução do número de pontos de amostragem não altera as componentes de frequências reduzidas. Do mesmo modo, a amostragem local e o ruído afectam principalmente os modos de frequências elevadas, e não os modos de frequências reduzidas. O resultado é um modelo deformável paramétrico cujos parâmetros apresentam um significado físico intuitivo. Os modos utilizados para descrever a deformação de um objecto são determinados pela resolução de um problema de valores próprios de uma matriz de elevadas dimensões; tal significa que a análise modal pode apresentar a desvantagem de a base modal ser de difícil cálculo em tempo real. Contudo, verificou-se que para uma classe particular de formas similares os modos podem ser pré-calculados e generalizados [Pentland, 1990, 1991a]; para alguns casos, com topologias esféricas e tubulares, é demonstrado que os modos de deformação podem ser determinados de forma analítica [Nastar, 1993a, 1994]. A utilização da representação modal proporciona uma solução computacionalmente conveniente para a obtenção de um modelo de elementos finitos paramétrico, ao mesmo tempo que também resolve os problemas associados à amostragem e à não unicidade; contudo, um outro problema continua sem resolução. Em cada um dos métodos baseados em MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 23 princípios físicos a ligação por uma mola virtual entre pontos dos dois objectos especifica implicitamente as correspondências entre alguns dos nodos dos objectos deformáveis. Geralmente a correspondência a utilizar para o estabelecimento destas ligações não é conhecida e deve ser determinada. Por vezes, para o método apresentar um bom desempenho, o utilizador necessita de especificar manualmente quais as ligações adequadas a serem consideradas. Este é o aspecto mais problemático da modelização segundo princípios físicos; tal não deve ser surpreendente pois este problema é similar ao de determinação de correspondência entre objectos existente em muitas aplicações da visão por computador. 2.2.4 – Representações próprias Existe uma classe de métodos próprios que derivam a sua parametrização directamente a partir da forma dos dados e, deste modo, evitam o problema da fixação das molas virtuais. Algumas destas técnicas também tentam determinar, de forma explícita e automática, as correspondências entre conjuntos de pontos característicos, enquanto outras evitam especificar a correspondência ao nível de características, mas procuram emparelhar imagens utilizando abordagens mais globais. Tal como na análise modal, cada um dos métodos próprios decompõe a deformação do objecto numa base ortogonal e ordenada. Geralmente estes métodos dividem-se em três categorias: formas próprias (eigenshapes), deformações próprias (eigenwarps), e imagens próprias (eigenpictures). Formas próprias A ideia base dos métodos baseados nas formas próprias é simples: a forma é descrita por uma matriz, simétrica e definida positivamente, medindo a ligação existente entre os dados pontuais. Esta descrição da forma pode ser decomposta de maneira única num conjunto de componentes lineares por análise dos vectores próprios da matriz de forma, e os vectores próprios resultantes podem ser utilizados para descrever as deformações mais significativas para tal classe de objectos. Estas deformações principais são similares aos eixos de simetria generalizados de um objecto, pois descrevem os eixos principais da sua deformação. Uma destas matrizes para a descrição da forma, a matriz de proximidade [Shapiro, 1991, 1992, 1992a], é fortemente relacionada com a teoria potencial clássica e descreve distâncias com ponderação Gaussiana entre dados pontuais. Os vectores próprios desta matriz podem ser utilizados para determinar a correspondência entre dois conjuntos de pontos. Deformações próprias Em [Cootes, 1992] é introduzido um método para capturar as propriedades invariantes de uma classe de formas baseado na ideia de determinar as variações principais de um modelo de contorno. O método tem por base a representação de objectos como um conjunto de pontos etiquetados e a análise estatística das suas variações num conjunto de treino. Uma matriz de covariância é construída para a descrição dos deslocamentos dos pontos do modelo relativamente ao centróide do protótipo. Seguidamente é realizada uma análise de ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 24 componentes principais desta matriz de covariância e, depois, um reduzido número das componentes mais significativas é utilizado para o controlo das deformações do modelo. Esta técnica tem a vantagem de poder ser treinada de maneira a capturar a informação ao longo dos eixos mais importantes de variação para o conjunto de treino e, deste modo, para a variação estimada nos novos modelos que sejam encontrados na mesma classe de objectos. A técnica é baseada directamente nos pontos característicos amostrados. Quando diferentes pontos característicos são determinados em vistas distintas, ou resultam de densidades de amostragem desiguais, as matrizes de forma para duas vistas serão diferentes, mesmo que a pose e a forma do objecto sejam idênticas. O método também não pode incorporar informação acerca da conectividade entre características; isto é, os dados são tratados como nuvens de pontos idênticos. Uma desvantagem ainda mais significativa que este método apresenta é a sua inadequação para deformações acentuadas, a menos que previamente sejam dadas as correspondências entre características [Sclaroff, 1995]. Numa tentativa de diminuir os problemas associados a esta metodologia surgiram várias propostas de melhoramentos. Assim, em [Hill, 1994] é apresentada uma solução para a determinação automática dos pontos a serem utilizados na geração dos modelos e para a determinação da correspondência pontual, sendo apresentados resultados em imagens do coração e da mão. Em [Cootes, 1995] estes modelos são complementados com modelos de forma baseados na análise dos elementos finitos. Basicamente, a solução apresentada baseiase na tradução das deformações admissíveis pela utilização dos modos de vibração do modelo finito, quando existem poucas formas de treino, e na consideração de mais modos estatísticos, quando um maior número de formas de treino está disponível. Imagens próprias Um outro grupo de métodos de descrição própria é designado por imagens próprias, pois estes métodos executam o cálculo das componentes principais directamente a partir das imagens originais. Utilizando esta abordagem foram construídos sistemas que executam com estabilidade o reconhecimento de faces, o reconhecimento de veículos, o seguimento de veículos em estradas, etc. Por exemplo, em [Turk, 1991] é utilizada esta técnica para a descrição de novas faces por determinação das variações principais num vasto conjunto de treino de imagens em níveis de cinzento. Para reconhecer uma nova face, é determinada uma solução que sintetiza a nova face a partir de uma combinação pesada das faces próprias. A nova face pode ser posteriormente reconhecida pela comparação da solução para a sua síntese com as soluções para as sínteses das faces conhecidas. No limite, a decomposição em faces próprias pode conter muitas faces na sua base mas, geralmente, truncando-se para apenas as primeiras 10-20 faces próprias pode-se contemplar até 99% da variância do conjunto de treino [Sclaroff, 1995]. Além do mais, a descrição de faces pode ser conseguida com um número reduzido de parâmetros. Esta transformação para o espaço próprio truncado descreve um subespaço designado por espaço facial. MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 25 Como originalmente proposta, esta técnica apresenta problemas relativos a alterações na escala, na orientação e na iluminação. Em [Moghaddam, 1994; Pentland, 1994] este método foi estendido de forma a incorporar espaços próprios modulares, que podem incluir informação sobre alterações do ponto de vista, e modelos próprios, para melhor modelizar características faciais como os olhos, o nariz e a boca. A utilização de subespaços para o reconhecimento de faces, reconhecimento de linguagem gestual e detecção de objectos é também realizada em [Moghaddam, 1997]. Em [Belhumeur, 1997] é apresentada uma abordagem baseada na análise de componentes principais para o reconhecimento de faces que é invariante à iluminação e às suas variações. A análise de componentes principais é também utilizada em [Craw, 1999] para a detecção e reconhecimento de faces, em [Ohba, 1997] para o reconhecimento de objectos múltiplos, e em [Swets, 1996] para o reconhecimento de faces e de outros objectos. Geralmente, apesar dos aperfeiçoamentos que tem vindo a sofrer, este método não consegue contemplar adequadamente os problemas associados ao escalamento, à rotação e às deformações [Sclaroff, 1995]. 2.3 – Análise de movimento não rígido O problema da análise de movimento não rígido é complexo: a não rigidez implica a variação da forma e, eventualmente, a variação da topologia da estrutura. Um objecto não rígido não pode ser representado por um conjunto fixo de parâmetros, a menos que certas restrições sejam utilizadas no comportamento do objecto. Assim, ao contrário do movimento rígido, não é possível utilizar um algoritmo geral para determinação dos parâmetros do movimento. Consequentemente, é necessário classificar o movimento não rígido de forma a guiar a escolha da abordagem a utilizar. Os objectos não rígidos podem ser separados em diferentes tipos tais como: articulados, elásticos e fluidos [Kambhamettu, 1998]. Diferentes métodos para a análise de movimento podem ser mais adequados para cada tipo. Limitando o âmbito de um problema de análise de movimento não rígido a um tipo particular, é possível definir considerações não rígidas específicas que podem ser incorporadas como restrições computacionais nos algoritmos a utilizar. Nos últimos anos têm vindo a realizar-se progressos significativos na análise de movimento não rígido. Nesta secção, são classificadas diferentes abordagens na análise de movimento não rígido e indicadas as considerações e condições que utilizam. É importante notar que as questões de análise de movimento e modelização da forma se tornam inseparáveis quando se considera o movimento do tipo não rígido. A perspectiva orientada à modelização sugere uma classificação possível da forma não rígida e do movimento. Modelos de forma não rígida podem ser divididos em dois grandes grupos: modelos locais e modelos globais. As abordagens de modelização local, concentram-se nas representações da forma local e incluem os métodos baseados em geometria diferencial e os métodos físicos baseados na técnica dos elementos finitos. Abordagens de modelização global ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 26 incluem vários modelos parametrizáveis (que são várias vezes adequados tanto para objectos rígidos como para não rígidos) tais como harmónicos esféricos, modelos polinomiais globais, hiperquádricos, etc. A classificação local/global não é a única possível e, de facto, vários autores desenvolveram recentemente modelos de forma com características globais e locais em simultâneo. 2.3.1 – Classificação do movimento não rígido Uma classificação possível do movimento de objectos 3D, especialmente as suas superfícies, pode contemplar as seguintes classes1 [Kambhamettu, 1998]: • Movimento rígido – a distância entre quaisquer dois pontos do objecto é preservada. O objecto não estica nem dobra; desde modo, a curvatura2 média e a curvatura Gaussiana na superfície mantêm-se invariantes. • Movimento articulado – conjunto de elementos cada um dos quais com movimento rígido. Envolve o movimento de partes rígidas conectadas por ligações não rígidas. Claramente neste caso as restrições de rigidez são mais relaxadas. • Movimento quase rígido – as deformações são limitadas a pequena amplitude. Quando visto em intervalos de tempo suficientemente reduzidos o movimento não rígido entre imagens é quase rígido. • Movimento isométrico – movimento não rígido que preserva o comprimento ao longo da superfície assim como os ângulos entre curvas sobre a mesma. • Movimento homotético – expansão ou contracção uniforme da superfície. • Movimento conforme – movimento não rígido que preserva os ângulos entre curvas da superfície mas não os comprimentos das curvas. • Movimento elástico – movimento não rígido cuja única restrição é algum grau de continuidade ou suavização. Este é o tipo de movimento de um objecto sólido mais difícil de analisar. • Movimento fluído – movimento não rígido geral, não necessariamente contínuo. Pode envolver variações de topologia e deformações turbulentas. 1 Também é comum verificar-se a classificação do movimento não rígido em apenas três classes: articulado, elástico e fluído. 2 As superfícies têm dois tipos principais de curvatura [Farin, 1996]: a média e a Gaussiana. Nos pontos de uma superfície existem dois valores extremos de curvatura: 1 k e 2 k, designados por curvaturas principais; o produto 12 kk é designado por curvatura Gaussiana e a soma () 12 12kk+ é designada por curvatura média. MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 27 2.3.2 – Classes restringidas de movimento não rígido 2.3.2.1 – Movimento articulado Um objecto articulado é um tipo de objecto não rígido bastante restringido, composto por partes rígidas com ligações entre si que permitem estilos definidos de movimento. Alguns exemplos simples de objectos articulados são: braços, pernas, tesouras, alicates, esqueletos de animais e manipuladores robóticos. A importância do movimento articulado no movimento de robôs é uma das razões para a sua grande importância na análise de movimento não rígido. Um objecto pode ser classificado como articulado pela observação do seu comportamento ao longo de determinado período de tempo e comparando a sequência de imagens com todas as formas válidas que podem ser geradas por um modelo articulado conhecido. Uma outra abordagem viável é considerar toda a sequência de imagens de um objecto e integrá-las em função dos graus de liberdade de articulação em cada ponto. Muita investigação tem vindo a ser realizada na modelização, no reconhecimento e na análise de movimento do tipo articulado. Em geral, quando comparado com os restantes tipos de movimento não rígido, tem vindo a verificar-se um maior desenvolvimento neste tipo de movimento [Kambhamettu, 1998]. Tal deve-se ao facto de existir a possibilidade de decompor o corpo articulado em partes rígidas e aplicar-se a análise de movimento rígido em cada uma dessas partes. Em [Pentland, 1990] é utilizada uma abordagem física para sistemas articulados, baseada no método dos elementos finitos e na dinâmica modal, para a segmentação da imagem 2D e posterior ajuste de modelos deformáveis a dados 3D associados com a imagem. Um modelo para a representação de movimento não rígido, baseado em elasticidade relativa, com o qual é possível obter-se o movimento e a estrutura de objectos deformáveis articulados, sem o prévio conhecimento dos seus parâmetros físicos, é apresentado em [Smith, 1995]. Trata-se de uma tentativa de utilizar as técnicas aplicadas em movimento de objectos rígidos incluindo a elasticidade relativa nas equações de movimento rígido. A análise de objectos articulados ou que se dobram é também considerada em [Sozou, 1995] através de uma generalização não linear dos modelos de distribuição de pontos utilizando regressão polinomial e permitindo, deste modo, que os pontos de controlo se desloquem segundo trajectórias polinomiais. Esta abordagem foi utilizada na análise de cromossomas em imagens, e complementada com a utilização de redes neuronais em [Sozou, 1995a]. Em [Kakadiaris, 1994, 1995, 1996] é estimado o movimento e a forma de objectos articulados utilizando uma abordagem física, por intermédio do método dos elementos finitos, e filtragem de Kalman [Maybeck, 1979] para estimar a posição do modelo na imagem seguinte. Em [Jones, 1999] é apresentada uma abordagem que utiliza características invariantes dos objectos articulados para o reconhecimento baseado em modelos construídos previamente. Esta abordagem é aplicada em imagens de radar. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 28 O problema de reconhecimento da forma de objectos articulados e deformáveis é também tratado em [Pelillo, 1999], através da utilização de grafos e de árvores de pesquisa para a determinação dos emparelhamentos. Em [Tsap, 1999] é tratado o problema da análise de movimento não rígido de objectos elásticos e articulados utilizando modelos de elementos finitos não lineares, construídos a partir de conhecimento prévio do objecto e dos seus dados 3D. A ideia base da metodologia utilizada é a determinação das forças que são responsáveis pelo movimento ou deformação da forma do objecto, sem a necessidade da determinação da correspondência pontual. 2.3.2.2 – Movimento quase rígido O movimento quase rígido restringe o grau de deformação. Um movimento geral não rígido é quase rígido quando analisado em intervalos de tempo suficientemente reduzidos entre imagens, isto é, quando a amostragem temporal for suficientemente elevada. O trabalho inicial na área do movimento não rígido foi formulado tendo por base o facto de um objecto real não poder alterar a sua forma instantaneamente devido à inércia. Quando uma translação, uma rotação, e uma deformação, são aplicadas a um objecto e uma sequência de imagens é adquirida, utilizando-se intervalos de tempo reduzidos, o movimento não rígido que ocorre entre imagens é diminuto. Em [Sethi, 1987] é abordado o problema da determinação da correspondência pontual em movimento não rígido. O método apresentado para estabelecer correspondências de objectos não rígidos em sequências de imagens utiliza uma restrição de suavidade do movimento. Utilizando coerência das trajectórias, é formulado um problema de optimização que assume que o objecto não pode alterar a sua forma instantaneamente. A abordagem utilizada implica que as trajectórias pontuais 2D, resultantes das projecções das trajectórias 3D, sejam suaves, resultando as trajectórias mais suaves entre todas as possíveis. Tal abordagem resolve automaticamente o problema da correspondência; contudo, esta técnica é computacionalmente intensiva, dependendo do número de imagens a considerar, e baseia-se na suavidade de movimento 2D. Uma abordagem similar para medir as trajectórias pontuais em objectos deformáveis em sequências de imagens é apresentada em [Duncan, 1991], em que a fronteira do objecto é modelizada como um contorno deformável e os seus segmentos locais são seguidos ao longo da sequência temporal. É assumido reduzido movimento para as características utilizadas, de maneira a determinar-se os pontos candidatos a cada emparelhamento. A estimativa do movimento é realizada por emparelhamento de segmentos locais entre pares de contornos, baseada na minimização da deformação entre segmentos utilizando como medida a energia de flexão. A abordagem apresentada foi aplicada no seguimento do movimento do ventrículo esquerdo do coração. Em [Zhang, 1992, 1994] é apresentada uma técnica iterativa, baseada no método dos mínimos quadrados, para determinar o emparelhamento entre os pontos de uma curva com os MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 29 pontos mais próximos de uma outra curva, admitindo que o movimento é reduzido. Também em [Kumar, 1995] é considerado o problema da determinação da correspondência entre pontos de objectos não rígidos ao longo de sequências de imagens. No método apresentado, é assumido que na imagem seguinte a localização de cada ponto é interior a um dado círculo centrado na posição que tinha na imagem anterior. Para determinar a correspondência é minimizada a soma dos quadrados das distâncias utilizando resultados das teorias dos grafos. Em [Tavares, 1995a, 1995b, 1995c] é descrita uma abordagem para o seguimento de linhas ao longo de sequências de imagens para a obtenção de estrutura a partir do movimento conhecido de uma câmara. Após a detecção e seguimento das linhas presentes em cada imagem, é realizada a sua aproximação poligonal, simplificação dos segmentos de recta determinados em cada imagem e é realizado o seguimento destes segmentos ao longo da sequência. No seguimento é utilizada filtragem de Kalman, para prever o estado das entidades em cada etapa do movimento, e a distância de Mahalanobis em conjunto com restrições geométricas para o estabelecimento das correspondências. 2.3.2.3 – Movimento isométrico, homotético e conforme O movimento isométrico é definido como o movimento que preserva o comprimento ao longo da superfície assim como os ângulos entre curvas sobre a mesma. Este tipo de movimento pode ser caracterizado como mantendo a curvatura Gaussiana, mas não a curvatura média. Um exemplo deste tipo de movimento é uma deformação por flexão, como por exemplo a flexão de um pedaço de papel, ou de uma placa metálica, a partir de uma configuração plana até uma forma cilíndrica. O movimento isométrico limita severamente a não rigidez, pois para muitos objectos curvos, tais como a esfera, a isometria não é possível. Actualmente existem muitas abordagens para estimar o movimento isométrico a partir de sequências de imagens 2D. É importante notar que geralmente este tipo de métodos assume que a correspondência pontual entre imagens está previamente determinada [Kambhamettu, 1998]. O movimento homotético envolve expansão ou contracção uniforme de uma superfície, isto é, o estiramento (a quantidade de expansão ou de contracção) é igual em todos os pontos da superfície. O movimento isométrico é um caso especial de movimento homotético com o parâmetro de estiramento unitário em todos os pontos da superfície. Exemplos do movimento homotético incluem a expansão ou a contracção de um balão e uma esfera. Em [Goldgof, 1988] é considerada a utilização das curvaturas média e Gaussiana para a classificação do movimento, e os movimentos articulados e homotéticos merecem destaque. Na abordagem utilizada, o estiramento da superfície durante o movimento é um parâmetro de movimento adicional. É realizada a extracção do estiramento da superfície sujeita a uma transformação homotética (constante em todos os pontos), e também são detectadas as partes da superfície onde o movimento homotético é violado. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 30 O movimento conforme é definido como um movimento que preserva os ângulos entre as curvas na superfície, mas não os comprimentos. O movimento homotético é uma classe restrita do movimento conforme. Em [Mishra, 1991] é apresentado um algoritmo para a determinação do estiramento local a partir da curvatura Gaussiana, baseado em aproximações polinomiais (lineares e quadráticas) da função de estiramento, sobre movimento conforme. A expressão utilizada para o estiramento linear em movimento conforme requer pelos menos a correspondência entre três pontos. Uma característica deste algoritmo é a não necessidade da preservação do sistema de coordenadas entre quaisquer dois conjuntos de dados. Este algoritmo é aplicado para estimar o estiramento da parede do ventrículo cardíaco esquerdo a partir dos dados obtidos por angiografia coronária. Em [Amini, 1991] é apresentada uma abordagem para o seguimento da correspondência de pontos do ventrículo esquerdo em movimento que, além do modelo de estiramento, utiliza um modelo adicional para a flexão. A física do modelo do ventrículo esquerdo é simulada por uma placa fina, e o movimento envolvido é seguido por minimização da flexão e da divergência do estiramento conforme. As direcções principais antes e depois do movimento são utilizadas para definir o sistema de coordenadas. 2.3.3 – Movimento não rígido geral Muitos autores têm vindo a trabalhar no problema da análise do movimento não rígido geral. Neste domínio, o movimento, além da invariância topológica, tem poucas restrições. A análise de movimento não rígido geral é possível em situações para as quais existem modelos específicos que utilizam conhecimento prévio sobre a aplicação em causa (métodos baseados em modelos). Contudo, abordagens mais globais podem utilizar restrições mais genéricas como, por exemplo, a suavidade do movimento. 2.3.3.1 – Movimento elástico O movimento elástico é um movimento não rígido no qual a única restrição é algum grau de continuidade ou suavidade. Exemplos são o movimento de materiais elásticos como a borracha, de materiais viscoelásticos tais como a argila e o barro, e de materiais plásticos. Este tipo de movimento de objectos sólidos é o mais difícil de analisar. Movimento elástico inclui movimento rígido mais deformações de estiramento, de flexão e de torção. Em [Terzopoulos, 1988] é introduzida uma abordagem genérica, baseada em princípios físicos para estimar o movimento elástico, utilizando modelos deformáveis. Estes modelos são definidos por primitivas dinâmicas construídas por material elástico simulado. O material, representado matematicamente por meio de splines generalizadas, permite utilizar restrições de suavidade intrínsecas e torna possível a determinação do movimento contínuo não rígido. Tal como os objectos reais, os modelos deformáveis movem-se em resposta a forças aplicadas MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 37 forma associados com as funções de base. A forma discreta da energia () ve da snake pode ser escrita como: () {} [] {} {} () 1 2 T E uuKu u=+R, (2.6) onde [ ] K é a matriz de rigidez e { } () uR é a versão discretizada do potencial externo. A solução para o mínimo de energia resulta fixando o gradiente da equação (2.6) igual a 0; tal é equivalente a resolver o sistema de equações algébricas: [ ] { } { } { } K uf=-— R = , (2.7) onde { } f é o vector de forças externas generalizadas. A versão discreta das equações dinâmicas Lagrangianas dadas pela equação (2.5) pode ser escrita por um conjunto de equações às diferenças ordinárias de segunda ordem em () { } ut : [ ] { } [ ] { } [ ] { } { } M uCuKu f++ =   , (2.8) onde [] M é a matriz de massa e [ ] C é a matriz de amortecimento. As derivadas em ordem ao tempo na equação (2.5) são aproximadas por diferenças finitas e métodos explícitos ou implícitos de integração temporal são utilizados para simular o sistema ordinário de equações diferenciais resultante, em termos dos parâmetros da forma { } u. 2.4.4 – Modelos deformáveis probabilísticos Uma abordagem alternativa para os modelos deformáveis deriva da resolução do processo de ajuste do modelo utilizando métodos probabilísticos. Tal permite a incorporação de características conhecidas a priori em termos de distribuições probabilísticas. Esta metodologia probabilística também possibilita uma medida da incerteza dos parâmetros estimados para a forma depois do ajuste do modelo aos dados da imagem. Seja u a representar os parâmetros da forma do modelo deformável com uma probabilidade a priori () p u nos seus parâmetros. Seja () p Iu o modelo de sensor de imagem – a probabilidade de produzir uma imagem I dado um modelo u. O teorema de Bayes: () () () () p Iu pu puI pI = (2.9) expressa a probabilidade a posteriori () p uI de um modelo dada a imagem, em termos do modelo da imagem e das probabilidades a priori do modelo e da imagem. É fácil converter a medida da energia interna da equação (2.2) do modelo deformável ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 38 numa distribuição a priori sobre as formas esperadas, com as formas de menor energia a serem as mais prováveis. Tal é atingido utilizando uma distribuição de Boltzmann (ou de Gibbs) com a forma: () () () 1exp S S p uu Z =-, (2.10) onde () Su é a versão discreta de () Sv na equação (2.2) e S Z é uma constante de normalização (designada por função de separação). Este modelo a priori é depois combinado com um modelo simples do sensor, baseado em medidas lineares com ruído Gaussiano: () () () 1exp P I p Iu u Z =-, (2.11) onde () Pu é uma versão discreta do potencial () P v na equação (2.3), que é uma função da imagem () , I xy. Os modelos podem ser ajustados por determinação de uma solução para u que maximiza localmente () p uI na equação (2.9); tal é designado por solução (MAP) máxima a posteriori. Com a construção anterior, é obtido um resultado idêntico ao obtido por minimização da equação (2.1). A abordagem probabilística pode ser expandida assumindo a priori um modelo variante no tempo (modelo de sistema) em conjunção com o modelo de sensor, resultando num filtro de Kalman. O modelo do sistema descreve a evolução esperada dos parâmetros u ao longo do tempo. Se as equações do movimento do modelo físico das snakes da equação (2.8) forem utilizadas como modelo do sistema, o resultado é um algoritmo de estimação sequencial conhecido por snakes de Kalman. Por exemplo, em [Baumberg, 1993, 1994, 1994a] são utilizadas snakes em conjunção com filtragem de Kalman para o seguimento de pessoas a caminhar (sistemas articulados) ao longo de cenas estáticas. Também em [Byrne, 1994] é realizado este tipo de seguimento, incorporando o nível de cinzento na modelização, e utilizando modelos de forma flexível em conjunção com filtragem de Kalman. Em [Bascle, 1994] é realizado o seguimento e a análise do movimento rígido e não rígido, utilizando também contornos activos e filtragem de Kalman. A obtenção de uma descrição das restrições na geometria diferencial de uma superfície, pela observação de uma curva da mesma numa sequência de imagens, é realizada em [Cipolla, 1992, 1992a], sendo o seguimento dos contornos efectuado por snakes de Kalman. MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 39 2.4.5 – Aplicações de modelos deformáveis Os modelos deformáveis têm vindo a ser bastante utilizados para a segmentação, classificação e seguimento de objectos não rígidos em geral. Por exemplo em [Jain, 1996] é considerado um modelo protótipo (template) e um conjunto de deformações prováveis do mesmo para o emparelhamento de objectos deformáveis; em [Bimbo, 1997] é determinado o objecto existente numa base de dados que mais se assemelha a um esboço definido pelo utilizador, através de uma utilização de um protótipo deformável para o esboço; em [Mardia, 1997] são utilizados protótipos deformáveis para o reconhecimento de múltiplos objectos. O problema da modelização, extracção, detecção e classificação de contornos deformáveis através de protótipos deformáveis é abordado em [Lai, 1994, 1994a]. Na metodologia adoptada são utilizadas snakes generalizadas (g-snakes), para representação de formas de maneira única e invariante a transformações afins, sendo a inicialização dos modelos obtida por utilização da transformada de Hough. Os modelos deformáveis são bastante utilizados para a segmentação e classificação de veículos ao longo de sequências de imagens; exemplos podem ser verificados em [Dubuisson, 1995, 1996]. Outra área na qual os modelos deformáveis são também empregues é a segmentação, classificação e reconhecimento de caracteres; exemplos podem ser analisados em [Jain, 1997; Kopec, 1997; Lai, 1994, 1994a; Wilfong, 1996]. A análise e reconhecimento de faces é outra área em que os modelos deformáveis são bastantes comuns; exemplos podem ser encontrados em [DeCarlo, 1996; Essa, 1992, 1994, 1994a, 1995, 1997; Lanitis, 1995; Moghaddam, 1996; Yuille, 1989, 1992]. Actualmente também se verifica grande utilização de modelos deformáveis em aplicações de simulação cirúrgica; um exemplo é descrito em [Bro-Nielsen, 1996]. O elevado número de aplicações dos modelos deformáveis na área da imagem médica é, sem dúvida, responsável por uma elevada percentagem do trabalho desenvolvido no âmbito dos corpos deformáveis. Nas subsecções seguintes são indicadas algumas aplicações dos modelos deformáveis nessa área e referenciados alguns trabalhos desenvolvidos. 2.4.5.1 – Análise de imagem médica com modelos deformáveis Apesar de originalmente desenvolvidos para aplicações em problemas de visão por computador ou em computação gráfica, o potencial dos modelos deformáveis na análise de imagem médica tem vindo a ser rapidamente utilizado. Assim, têm vindo a ser aplicados em imagens geradas por diversas modalidades de aquisição de imagem médica [Acharya, 1998] tais como raios X, tomografia computorizada, angiografia, ressonância magnética e ultrasons. Modelos deformáveis bidimensionais e tridimensionais têm vindo a ser utilizados para segmentar, visualizar, seguir e quantificar, uma variedade de estruturas anatómicas que vão ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 40 desde a escala macroscópica até à microscópica [Elliott, 1995]. Tais estruturas incluem o cérebro, o coração, a face, as artérias da retina e coronárias, o rim, o pulmão, o estômago, o fígado, o crânio, as vértebras e a coluna vertebral, e mesmo estruturas celulares como neurónios e cromossomas. Modelos deformáveis têm vindo a ser utilizados no seguimento de movimento não rígido do coração, do pulmão, da artéria coronária [Puentes, 1998], do estômago, etc. Também têm sido utilizados para localizar estruturas no cérebro, e no alinhamento de imagens da retina, da estrutura vertebral e de tecidos neurológicos. 2.4.5.1.1 – Segmentação de imagem com curvas deformáveis A segmentação de estruturas anatómicas é uma primeira etapa essencial em muitas tarefas de análise de imagem médica, tais como alinhamento, etiquetagem e seguimento de movimento. Estas tarefas requerem que as estruturas anatómicas presentes na imagem original sejam reduzidas para uma representação compacta e analítica da sua forma. Executar manualmente tal segmentação é um processo extremamente trabalhoso e moroso. Um primeiro exemplo é a segmentação do coração, especialmente o ventrículo esquerdo, em imagem cardíaca. A segmentação do ventrículo esquerdo é um pré-requisito para se obter informação diagnóstica [Monteiro, 1994] tal como a fracção de ejecção ou o volume ventricular, para a análise do movimento parietal, etc. Um esquema de segmentação baseado em modelos deformáveis, utilizado de forma concertada com técnicas de pré-processamento de imagem, pode ultrapassar muitas das limitações da edição manual e das técnicas tradicionais de processamento de imagem. Estes modelos geométricos, contínuos e interligados, consideram a fronteira de um objecto como um todo e podem utilizar conhecimento existente a priori sobre a forma do mesmo para restringir o problema da segmentação. A continuidade inerente e a suavidade destes modelos pode compensar o ruído, fendas e outras irregularidades presentes nas fronteiras dos objectos. Além do mais, a representação paramétrica dos modelos possibilita uma descrição compacta e analítica da forma do objecto. Estas propriedades originam uma técnica robusta para ligar características de imagem dispersas e misturadas com ruído num modelo coerente e consistente para o objecto [McInerney, 1996]. Entre as várias utilizações dos modelos deformáveis em análise de imagem médica destacam-se os modelos de contorno deformáveis, tais como as snakes, para segmentar estruturas em imagens 2D, como, por exemplo, em [Cohen, 1991; Gupta, 1994; Solaiyappan, 1996]. Tipicamente os utilizadores iniciam um modelo deformável próximo do objecto desejado e permitem que o mesmo se deforme até atingir o equilíbrio. Os utilizadores podem usar as capacidades interactivas destes modelos e afiná-los manualmente. Quando o utilizador estiver satisfeito com o resultado numa imagem inicial, o modelo de contorno ajustado pode ser utilizado como a aproximação inicial na imagem seguinte da sequência que esteja a ser considerada. A sequência de contornos 2D resultante pode ser posteriormente ligada, para formar um modelo superficial 3D contínuo como, por exemplo, é realizado em [Cohen, 1991]. Em [Xu, 1999] são utilizadas curvas elásticas Gaussianas para a segmentação de zonas de MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 41 cancro da pele. A segmentação de imagens médicas de ultrasons utilizando snakes é apresentada em [Maurincomme, 1993]. Em tal aplicação, as curvas são inicializadas numa determinada posição previamente determinada sendo, assim, o processo totalmente automático. Contornos activos são também utilizados na segmentação de tecidos cerebrais em imagens de ressonância magnética em [Kapur, 1996]. Em [Fishman, 1996] são utilizados contornos deformáveis paramétricos na segmentação de imagens 2D para o planeamento cirúrgico. A aplicação de snakes e outros modelos de contornos deformáveis similares para extrair regiões de interesse não é, contudo, isenta de limitações. Por exemplo, as snakes foram desenvolvidas como modelos interactivos e, em aplicações não interactivas, devem ser inicializadas próximas à estrutura desejada de forma a garantir-se um bom desempenho. As restrições da energia interna das snakes podem limitar a flexibilidade geométrica e impedir que uma snake represente formas longas e do tipo tubular ou formas com bifurcações ou protusões significativas. A topologia da estrutura desejada deve ser conhecida antecipadamente pois os modelos deformáveis de contorno clássicos são paramétricos e, sem mecanismos adicionais, são incapazes de transformações topológicas. Vários métodos têm vindo a ser propostos para melhorar e automatizar o processo de segmentação por contornos deformáveis. Em [Cohen, 1991] é utilizada uma força interna de inflação, expandindo o modelo da snake de maneira a ultrapassar falsas orlas, originadas pelo ruído, fazendo assim com que a snake seja menos sensível às condições iniciais e ao ruído. Em [Grzeszczuk, 1997] é minimizada a energia de modelos de contornos activos, utilizando um algoritmo que obtém soluções globais de minimização e permite a incorporação de restrições não diferenciáveis. Em [Herlin, 1992] é integrada, nos modelos de contorno deformáveis, informação baseada em regiões numa tentativa de diminuir a sensibilidade a falsas orlas e à localização inicial do modelo. Também em [Ronfard, 1994] é utilizada uma técnica semelhante para segmentar imagens médicas, e em [Chesnaud, 1999] é utilizada informação estatística de regiões para diminuir a sensibilidade das snakes ao ruído. Contornos activos poligonais foram sugeridos em [Delagnes, 1995] para o seguimento de objectos em sequências de imagens com fundos complexos. Segundo os autores, utilizando polígonos ajustáveis (conjunto de segmentos activos) é possível aproximar a forma de qualquer objecto, ultrapassando-se as limitações das snakes originais na representação de objectos com elevado número de vértices. Na abordagem utilizada, a energia é baseada em informação de textura e a posição inicial do contorno é predita utilizando informação do movimento obtida por estimativa. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 42 2.4.5.1.2 – Segmentação de imagem 3D com superfícies deformáveis Modelos de superfícies deformáveis em 3D foram primeiramente utilizados em visão por computador em [Terzopoulos, 1988], [McInerney, 1996]. Muitos autores têm desde então explorado a utilização de modelos de superfície deformáveis para segmentação de estruturas em imagens médicas 3D. Em [Cohen, 1992a, McInerney, 1995] são utilizados elementos finitos e técnicas baseadas em princípios físicos na implementação de cilindros e esferas elasticamente deformáveis. Os modelos são utilizados para segmentar a parede interna do ventrículo esquerdo do coração a partir de imagens 3D de ressonância magnética ou de tomografia computorizada. As superfícies deformáveis utilizadas, propostas em [Cohen, 1991a], são baseadas numa superfície do tipo spline modelizada por uma placa fina sob tensão, que controla e restringe o estiramento e a flexão da superfície. Os modelos são dinamicamente ajustados aos dados por integração das equações Lagrangianas do movimento ao longo do tempo, de forma a ajustar os graus de liberdade da deformação. O método dos elementos finitos é utilizado para representar os modelos como uma superfície contínua utilizando somatórios ponderados de funções de base polinomial. Em [Pentland, 1991a; Nastar, 1993] também são desenvolvidos modelos físicos, mas é utilizada uma base modal reduzida para os elementos finitos. Outros trabalhos que envolvem modelos de superfícies deformáveis 3D e aplicações de imagem médica são revistos em [Davatzikos, 1995]. 2.4.5.1.3 – Incorporação de conhecimento a priori Em imagem médica a forma geral, a localização e a orientação de objectos são conhecidas, e este conhecimento pode ser incorporado no modelo deformável sob a forma de condições iniciais, de restrições nos dados, de restrições dos parâmetros da forma, ou no processo de ajuste. A utilização implícita ou explícita de conhecimento anatómico no processo da determinação da forma é especialmente importante na interpretação automática e robusta em imagem médica. Para interpretação automática, é essencial obter um modelo que não apenas descreva o tamanho, a forma, a localização e a orientação do objecto-alvo, mas que também permita variações esperadas destas características. A interpretação automática em imagem médica pode aliviar os clínicos dos aspectos laboratorialmente intensivos, ao mesmo temo que aumenta a precisão, a consistência e a reprodutibilidade das interpretações. Um número considerável de autores têm vindo a incorporar o conhecimento da forma do objecto nos modelos deformáveis pela utilização de protótipos deformáveis (templates). A ideia de protótipos deformáveis precede o desenvolvimento das snakes, mas sofreu um novo desenvolvimento provocado por estas [Blake, 1998]. Um exemplo da utilização deste tipo de modelos é dado em [Yuille, 1989, 1992] onde protótipos deformáveis são construídos para detectar e descrever características das faces, MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 43 como os olhos. É utilizado um protótipo parametrizado para o olho, constituído por um círculo circunscrito por duas parábolas, e deformado por optimização de uma função de custo baseada em características morfológicas. Modelos deformáveis baseados em superquádricas são um outro exemplo de modelos frequentes na área da imagem médica. As superquádricas contêm um reduzido número de parâmetros globais intuitivos, que podem ser ajustados à forma média de uma estrutura anatómica alvo. Além do mais, os parâmetros globais podem frequentemente ser combinados com parâmetros locais como splines, resultando uma abordagem interessante para a representação da forma. Em [Vemuri, 1994] é construído um modelo deformável superquádrico numa base ortonormal de onduletas (wavelets) para utilização em imagem médica 3D e 4D. Esta base de multiresolução possibilita ao modelo a capacidade de se transformar de maneira contínua de deformações locais para globais, permitindo assim, utilizando relativamente poucos parâmetros, a criação e a representação de uma quantidade contínua de modelos de forma. Em [Bardinet, 1994, 1995, 1996] é ajustado um modelo superquádrico deformável para segmentar imagens cardíacas 3D e refinado o ajuste utilizando uma técnica de deformação volumétrica designada por deformações de forma livre. Estas deformações podem ser interpretadas como uma caixa, construída por borracha simulada, na qual o objecto a ser deformado, neste caso o superquádrico, está embebido; as deformações da caixa são transmitidas automaticamente aos objectos embebidos. Este aspecto volumétrico das deformações de forma livre, permite que dois modelos superquádricos superficiais sejam simultaneamente deformáveis de maneira a reconstruir as superfícies internas e externas do ventrículo esquerdo do coração e determinar o volume entre estas. Em [Kelemen, 1996; Székely, 1996] são desenvolvidos modelos paramétricos de Fourier, aos quais foi adicionada elasticidade de maneira a criar snakes de Fourier (2D) e modelos de superfícies deformáveis de Fourier (3D). Pela utilização da parametrização de Fourier seguida de uma análise estatística de um conjunto de treino, são definidos modelos de órgãos médios e as suas deformações próprias. Um ajuste elástico do modelo médio no subespaço dos modos próprios restringe as deformações possíveis e determina um emparelhamento óptimo entre o modelo superficial e os candidatos. Um exemplo de aplicação é apresentado na segmentação 3D de estruturas profundas do cérebro. Em [Taylor, 1995] é apresentada uma técnica estatística para a construção de protótipos deformáveis e são utilizados estes modelos para segmentar vários órgãos em imagens médicas 2D e 3D. A parametrização estatística fornece restrições globais para a forma e permite que o modelo se deforme apenas nas direcções implícitas no conjunto de treino. Para extrair o ventrículo esquerdo a partir de ecocardiogramas [Parker, 1994], os pontos são escolhidos ao redor da fronteira do ventrículo, perto da orla do ventrículo direito, e no topo da aurícula esquerda. Estes pontos podem ser ligados de forma a construir um contorno deformável. Pelo exame estatístico de conjuntos de treino cujos pontos foram manualmente especificados, e ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 44 utilizando uma análise de componentes principais, um protótipo é construído de maneira a descrever as posições médias e os principais modos de variação dos pontos do objecto. 2.4.5.1.4 – Emparelhamento O emparelhamento de regiões pode ser executado entre a representação de uma região e um modelo (segmentação) ou entre a representação de duas regiões distintas (alinhamento). O alinhamento de imagens médicas 2D e 3D é necessário para se estudar a evolução de uma patologia num indivíduo, ou para fundir a informação complementar obtida a partir de diferentes modalidades de aquisição de imagem. Exemplos da utilização de modelos deformáveis para executar o alinhamento de imagens médicas são descritos em [Bainville, 1995; Christensen, 1996; Davis, 1995; Declerck, 1995; Malandain, 1993, 1995; Rohr, 1996; Subsol, 1994; Syn, 1995, 1995a, 1995b, 1996; Thirion, 1993]. Geralmente estas técnicas partem da construção de descrições altamente estruturadas. Esta operação é frequentemente conseguida pela extracção de regiões de interesse com um algoritmo de detecção de orlas de intensidade, seguida da extracção de pontos específicos ou contornos característicos (ou curvas na superfície fronteira extraída dos dados 3D). Geralmente (em 3D) estas curvas descrevem estruturas diferenciais tais como cumes, ou singularidades topológicas. Posteriormente, um algoritmo de emparelhamento elástico pode ser aplicado entre pontos correspondentes de curvas ou contornos, sendo o contorno inicial deformado iterativamente até coincidir com o contorno desejado, através de forças derivadas dos emparelhamentos de padrões locais com o contorno desejado. Um exemplo de emparelhamento no qual a utilização de conhecimento explícito a priori foi envolvido nos modelos deformáveis é a extracção e etiquetagem de estruturas anatómicas no cérebro, especialmente a partir de imagens de ressonância magnética. O conhecimento anatómico é tornado explícito na forma de um atlas 3D para o cérebro. O atlas é modelizado como um objecto físico, com propriedades elásticas atribuídas. Depois de um alinhamento global inicial, o atlas deforma-se e emparelha-se nas correspondentes regiões da imagem volumétrica do cérebro, em resposta a forças derivadas das características da imagem. A suposição subjacente a esta abordagem é que, para um dado nível de representação, cérebros normais têm a mesma estrutura topológica e diferem apenas em detalhes da forma. A técnica de deformação elástica de um atlas tem sido uma área de investigação muito activa e tem vindo a ser explorada, por exemplo, em [Bajcsy, 1989; Christensen, 1996; Declerck, 1995; Subsol, 1994]. Existem várias dificuldades na abordagem baseada em atlas deformáveis. A técnica é sensível à posição inicial do atlas – se o alinhamento rígido inicial for afastado em demasia, então o emparelhamento elástico pode conduzir a resultados insatisfatórios. A presença de características fortes na vizinhança também pode causar problemas de emparelhamento – o atlas pode deformar-se para uma fronteira incorrecta. Por outro lado, sem a interacção do utilizador, o atlas pode não convergir para fronteiras de estrutura complexa. Uma solução para MÉTODOS DE SEGUIMENTO E ANÁLISE DE MOVIMENTO DE OBJECTOS DEFORMÁVEIS 45 estes problemas passa por técnicas de pré-processamento de imagem, como por exemplo detecção de orlas de intensidade e operações morfológicas de simplificação, em conjunção com o atlas deformável [McInerney, 1996]. 2.4.5.1.5 – Análise e seguimento de movimento A utilização principal de modelos deformáveis para o seguimento (tracking) em imagens médicas está relacionada com a medição do comportamento dinâmico do coração humano, especialmente do ventrículo esquerdo. A caracterização regional do movimento da parede do coração é necessária para isolar a severidade e a extensão de doenças como a isquemia. A ressonância magnética, e outras tecnologias de aquisição de imagem médica, permitem actualmente obter imagens 3D do coração, ao longo do tempo, com resolução espacial excelente e resolução temporal razoável. Os modelos deformáveis são bastante adequados para este tipo de tarefa de análise de imagem. Na abordagem mais simples, um modelo de contorno 2D deformável é utilizado para segmentar a fronteira do ventrículo esquerdo em cada fatia (slice) de uma imagem inicial 3D. Estes contornos são depois utilizados como a aproximação inicial das fronteiras do ventrículo esquerdo nas correspondentes fatias da imagem 3D no instante seguinte, e são depois deformados de maneira a extrair o novo conjunto de fronteiras do ventrículo esquerdo; esta abordagem é utilizada, por exemplo, em [Geiger, 1995; Gupta, 1993; Herlin, 1992]. A propagação temporal dos contornos deformáveis diminui drasticamente o tempo necessário para segmentar manualmente o ventrículo esquerdo a partir de uma sequência de imagens 3D, obtida ao longo de um ciclo cardíaco. Em [McInerney, 1995] é aplicada a abordagem de propagação temporal em 3D, utilizando modelos de balão deformáveis dinamicamente. Em [Amini, 1991] é utilizado um método baseado na energia de flexão e na curvatura da superfície para seguir e analisar o movimento do ventrículo esquerdo. Em cada instante são criados dois subconjuntos esparsos de pontos específicos, por selecção de pontos geometricamente significantes, um para a superfície endocárdica e o outro para a superfície epicárdica do ventrículo esquerdo. Fragmentos superficiais em torno destes pontos são então modelizadas por placas finas e flexíveis. Assumindo que num intervalo de tempo reduzido cada fragmento superficial se deforma apenas ligeiramente e localmente, é construída para cada ponto amostrado na primeira superfície uma área de pesquisa na superfície do ventrículo esquerdo da imagem 3D referente ao próximo instante. O melhor ponto para emparelhamento (correspondendo, por exemplo, ao mínimo da energia de flexão) no interior da janela de pesquisa na segunda superfície é considerado como correspondente ao ponto na primeira superfície. Este processo de emparelhamento produz um conjunto inicial de vectores associados ao movimento para pares de superfícies derivadas a partir de imagens de sequências 3D. É então realizado um procedimento de suavização para gerar um campo vectorial denso de movimento sobre a superfície do ventrículo esquerdo. Em [Cohen, 1992] também é aplicada uma técnica baseada na energia de flexão em 2D, e é realizada uma tentativa de melhorar o método anterior por adição à função de energia de flexão de um termo ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 46 que tende a preservar o emparelhamento dos pontos de elevada curvatura. Em [Goldgof, 1988; Kambhamettu, 1994; Mishra, 1991] também são apresentadas abordagens para a determinação da correspondência entre superfícies baseadas na variação da curvatura Gaussiana e assumindo um modelo de movimento do tipo conforme. Em [Chen, 1994] é empregue uma abordagem alternativa que utiliza um modelo hierárquico de movimento do ventrículo esquerdo, construído por combinação de uma superquádrica deformável globalmente com uma superfície deformável localmente utilizando primitivas de modelização de forma harmónica. Utilizando este modelo, é estimado o movimento do ventrículo esquerdo a partir dos dados de angiografia, e é produzida uma decomposição hierárquica que caracteriza o movimento do ventrículo esquerdo, com resolução variante entre grosseira e fina. Em [Benayoun, 1995; Nastar, 1994, 1996; Pentland, 1991] também é obtida uma caracterização do movimento do ventrículo esquerdo com resolução variante entre grosseira e fina. São utilizados modelos deformáveis para seguir e recuperar o movimento do ventrículo esquerdo, e análise modal para parametrizar os modelos. Esta parametrização é obtida a partir dos modos de vibração em regime livre e representações com diferentes detalhes são obtidas por variação do número de modos utilizado. O coração é um órgão relativamente suave e consequentemente existem reduzidos pontos característicos fidedignos. O coração também sofre movimento não rígido complexo que inclui uma componente do movimento de torção (tangencial), assim como uma componente normal. Geralmente, os métodos de estimação do movimento não são capazes de capturar este movimento tangencial sem informações adicionais [McInerney, 1996]. Vários autores têm aplicado modelos deformáveis em sequências de imagens de ressonância magnética de dados etiquetados por modulação espacial da magnetização (SPAMM – Spatial Modulation of Magnetizaton); exemplos são descritos em [Donnell, 1995; Kumar, 1994; Park, 1996; Young, 1992]. Por exemplo em [Kumar, 1994] é descrita uma abordagem para o seguimento automático de pontos etiquetados em imagens cardíacas de ressonância magnética e consequente estimação dos parâmetros de deformação. Esta etiquetagem é conseguida pela produção de zonas localizadas de magnetizações distintas na parede do coração. A distinção da magnetização é uma propriedade do tecido e é constante ao longo do seu movimento. Um outro problema existente, na maior parte dos métodos mais comuns, é a modelização separada das superfícies endocárdica e epicárdica. Na realidade, o coração é uma estrutura de paredes com determinada espessura. Em [Park, 1996] é desenvolvido um modelo que considera a natureza volumétrica da parede do coração e que incorpora a parametrização descritiva directamente na sua formulação. Em [Donnell, 1995] é utilizado um modelo híbrido e volumétrico, híbrido porque é um compromisso entre uma componente global (paramétrica) e uma componente local (explícita), para analisar e comparar o ventrículo esquerdo. Em [Young, 1992] também são construídos modelos 3D de elementos finitos a partir das representações das fronteiras das superfícies endocárdica e epicárdica. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 54 [] () () () () xx yy zz yz zy zx xz xy yx yz zy xx yy zz xy yx zx xz zx xz xy yx xx yy zz yz zy xy yx zx xz yz zy xx yy zz SSS SS SS SS SS SSS SS SS NSS SS SSS SS SS SS SS SSS È˘ ++ - - - Í˙ Í˙ --- + + Í˙ =Í˙ -+-+-+ Í˙ Í˙ -+ +--+ Í˙ Î˚ , com xx S, xy S, …, z z S determinados calculando-se os nove produtos possíveis 1tt x x+ ¢¢ , 1tt x y + ¢¢ , …, 1tt z z+ ¢¢ das coordenadas respectivas para cada par de pontos emparelhados: ,,1 1 n xx it it i Sxx + = =¢¢ Â, ,,1 1 n xy it it i Sxy + = =¢¢ Â, ... O quaternion unitário q  que maximiza o produto [ ] T qNq  é [Horn, 1987] um vector unitário com a mesma direcção do vector próprio [Bathe, 1996; Chapra, 1988; Press 1992] da matriz [ ] N associado ao valor próprio positivo mais elevado da mesma matriz. O escalamento existente pode ser determinado pelo quociente da raiz quadrada dos desvios médios quadráticos dos dois conjuntos de coordenadas relativamente aos seus centróides: 12 22 ,1 , 11 nn it it ii sX X + == ʈ =¢¢ Á˜ ˯ ÂÂ. Analisando esta equação verifica-se que para a determinação do escalamento não é necessária a prévia determinação da rotação. A melhor solução para a translação { } T é obtida pela diferença entre as coordenadas do centróide do objecto 1t+ e as coordenadas do centróide do objecto t previamente rodado e escalado: { } [ ] 1tt TG sRG + =- . Deve-se notar que este é um método directo, e assim não existe a necessidade de correcção iterativa. 3.2.2.1 – Consideração da confiança associada às coordenadas dos pontos Quando os erros esperados para as coordenadas dos pontos não são todos iguais deve-se considerar os respectivos pesos de forma a considerar tais medidas de incerteza. Assim, os centróides tornam-se centróides ponderados: , 11 nn tiiti ii GwX w == = , DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 55 1,1 11 nn tiiti ii GwX w ++ == = , onde i w é a medida de confiança associada às coordenadas do ponto i. A determinação do melhor escalamento é alterada pela utilização das medidas de confiança: 12 22 ,1 , 11 nn iit iit ii swX wX + == ʈ =¢¢ Á˜ ˯ ÂÂ. (3.1) A única mudança no método para a determinação da rotação envolvida está no facto de os produtos nos somatórios serem agora ponderados, isto é: ,,1 1 n xx i i t i t i Swxx + = =¢¢ Â, ,,1 1 n xy i i t i t i Swxy + = =¢¢ Â, ... 3.2.3 – Resultados experimentais Com o intuito de verificar a qualidade da solução determinada pelo método proposto para a transformação rígida existente entre objectos 2D e entre objectos 3D são neste ponto apresentados alguns dos resultados experimentais obtidos. 3.2.3.1 – Para objectos 2D Na primeira experiência realizada, Tabela 3.1, aplicou-se a um objecto uma rotação de -20º em torno da origem, um escalamento relativamente ao mesmo ponto de 0.75 e uma translação de -10 pixels segundo o eixo x e de 100 pixels segundo o eixo y. Analisando os resultados obtidos2 é possível concluir que a solução determinada é de boa qualidade. Numa segunda experiência, Tabela 3.2, aplicou-se a um objecto constituído por 84 pixels uma rotação de 45º em torno da origem, um escalamento relativamente ao mesmo ponto de 0.7 e uma translação de 150 pixels segundo o eixo x e de -100 pixels segundo o eixo y. Analisando os resultados obtidos utilizando-se 82 correspondências e a incerteza associada3 é novamente possível concluir que a solução determinada é de boa qualidade. 2 Deve-se ter em atenção que a utilização de coordenadas imagem do tipo inteiro implica um aumento na imprecisão da transformação determinada pois as coordenadas pós-transformação são arredondadas para valores inteiros. 3 O método utilizado para o emparelhamento é o baseado na análise modal da forma apresentado na secção 3.4. A medida de incerteza é: ( ) 11 i z + onde i z é a medida de emparelhamento: entre 0, bom emparelhamento, e 2, mau emparelhamento. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 56 Tabela 3.1 – Dados utilizados e resultados obtidos na primeira experiência para a determinação da transformação rígida. Objecto Original Objecto Transformado tx ty q s w -10 100 -20º 0.75 Não Objectos Sobrepostos Transformação Obtida -9.6 100.28 -19.97º 0.75 Tabela 3.2 – Dados utilizados e resultados obtidos na segunda experiência para a determinação da transformação rígida. Objecto Original Objecto Transformado tx ty q s w 150 -100 45º 0.7 Sim Objectos Sobrepostos Transformação Obtida 150.09 -99.91 45.01º 0.69 x y DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 57 3.2.3.2 – Para objectos 3D Na terceira experiência, Tabela 3.3, aplicou-se a um objecto constituído por 244 pontos uma rotação de 45º em torno do eixo z que passa pela origem, um escalamento relativamente ao mesmo ponto de 1.25 e uma translação de 10 segundo o eixo x , -25 segundo o eixo y e de -5 segundo o eixo z . Analisando os resultados obtidos nesta terceira experiência, utilizando-se 244 correspondências e a incerteza associada, é mais uma vez possível concluir que a solução determinada é de boa qualidade. Tabela 3.3 – Dados utilizados e resultados obtidos na terceira experiência para a determinação da transformação rígida. Objecto Original Objecto Transformado tx ty tz z q s w 10 -25 -5 45º 1.25 Sim Objectos Sobrepostos Transformação Obtida tx ty tz z q s w 10.00 -24.99 -4.99 45.00º 1.25 Sim 3.2.4 – Comentários aos resultados Pelos resultados experimentais obtidos4, quer para objectos 2D quer para 3D, pode-se concluir que o método adoptado determina boas soluções para a transformação geométrica rígida existente entre dois objectos. 4 Outros resultados podem ser analisados em [Tavares, 2000, 2000a]. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 58 Ao longo de todo o trabalho, verificou-se a utilidade deste método na determinação da transformação rígida existente entre dois objectos, quer estes sejam rígidos ou não. Para a solução determinada ser satisfatória não é necessário utilizar um número muito elevado de correspondências, pelo que se podem seleccionar apenas as correspondências obtidas com maior grau de confiança. Quando os escalamentos ao longo de cada eixo coordenado não são iguais, o escalamento obtido pela utilização da equação (3.1) pode não ser adequado. Verificou-se que, nestes casos, é geralmente preferível determinar-se escalamentos independentes para cada eixo utilizandose equações semelhantes à equação (3.1), uma para cada eixo, em que apenas intervêm as coordenadas ao longo desse eixo. 3.3 – Determinação de correspondências utilizando o princípio do mapeamento segundo a distância mínima Nesta secção é apresentado um método implementado para a determinação de correspondências entre pontos de objectos, baseado no mapeamento segundo a distância mínima de Scott e Longuet-Higgins [Shapiro 1991, 1992, 1992a]. Neste método é incorporada uma medida de afinidade entre pontos, baseada na distância entre elementos, e um esquema de concorrência permitindo que os pontos se candidatem a um dado emparelhamento. Este critério é formulado segundo um princípio de proximidade, favorecendo emparelhamentos através de distâncias o mais reduzidas possível, e um de exclusão, favorecendo o emparelhamento de um para um. O mapeamento resultante efectivamente minimizará a soma total do quadrado das distâncias percorridas pelos pontos tendo como restrição o emparelhamento de um para um. Uma boa característica deste método é a possibilidade de implementá-lo, de forma elegante, através de uma solução bem condicionada para a determinação dos vectores próprios, não exigindo iterações. 3.3.1 – Princípio do método Como entrada, este método recebe um conjunto de m pontos, de coordenadas t X, de um objecto t e um conjunto de n pontos, de coordenadas 1t X + , de um objecto 1t+. As fases intervenientes no método estão representadas de forma gráfica na Figura 3.1. A primeira etapa (análise espacial cruzada) consiste na enumeração de todos os pares de emparelhamento possíveis e em guardar as suas afinidades numa matriz de proximidade [] G, em geral não simétrica. Cada elemento ij G representa a atracção entre o ponto i do objecto t DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 59 e o ponto j do objecto 1t+ através de uma distância de métrica Gaussiana ponderada5: () () 22 2 ij d ij Ge s- =, 1...im=, 1...jn=, onde () 22 ,,1 ij i t j t dXX + =- é o quadrado da distância Euclidiana entre os dois pontos. Deste modo ij G varia de 0 (zero), para pontos bastante separados ( ij d=•), a 1 (um) para pontos coincidentes ( 0 ij d=). O parâmetro s controla a largura da curva Gaussiana e, desta forma, o grau de interacção entre os dois conjuntos de pontos. De forma simplista, este parâmetro pode ser encarado como a colocação de um círculo centrado num ponto do objecto t, permitindo que este interactue apenas com os pontos do objecto 1t+ interiores a este círculo. Assim, um valor reduzido para s favorece as interacções locais, enquanto um valor mais elevado permite interacções mais globais. Objecto t Correspondência entre pontos Decomposição em valores/vectores singulares Decomposição em valores/vectores singulares Objecto t+1 Análise espacial cruzada Pontos Matriz de proximidade Vectores singulares "esquerdos e direitos" Matriz de associação ,it X ,1jt X + [] G [] U [] T [] P Figura 3.1 – Etapas do método de mapeamento segundo a distância mínima. A segunda etapa do método consiste na realização da decomposição em valores singulares, geralmente designada por SVD [Bathe, 1996; Chapra, 1988; Press, 1992], da matriz [] G, exprimindo [] G como: [ ] [ ] [ ] [ ] GTDU=, onde [ ] T é uma matriz ortogonal de dimensões () mm¥, [] U é uma matriz ortogonal de dimensões () nn¥ e [] D é uma matriz de dimensões () mn¥ com elementos não diagonais nulos. Como a matriz [] G não é geralmente quadrada, os seus vectores singulares não podem ser obtidos directamente; em verdade não existem. Assim, a solução adoptada [Shapiro, 1991] 5 A utilização desta distância métrica prende-se com: • na maior parte dos casos a matriz [] G resultante é definida positivamente; • cada elemento i, j, da matriz [] G decresce com o aumento da distância, variando de um, para pontos coincidentes, (0 ij d=) a zero, para os bastante distantes ( ij d=•). ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 60 passa pela utilização de duas matrizes adicionais [] r G e [ ] l G ambas quadradas e simétricas: [ ] [ ] [ ] T r GGG=, [ ] [ ] [ ] T l GGG=, e os seus valores e vectores singulares são determinados: [] [][][][][][] [][][] [] [][][] TTT T T T r t GTDUUDTTDDTTDT È˘ === Î˚ , [] [][][][][][][] [][][][][][] TTT T T T l u G UDTTDUUDDUUDU È˘ === Î˚ . As matrizes [ ] T e [] U são ortogonais. As colunas da matriz [ ] T são referidas como os vectores próprios direitos da matriz [] G, enquanto as linhas da matriz [] U são referidas como os vectores próprios esquerdos6 da matriz [] G: [ ] { } { } { } 12 m TTT T È˘ =Î˚ , [] { } {} {} 1 2 T T T n U U U U È˘ Í˙ Í˙ =Í˙ Í˙ Í˙ Î˚ . Os primeiros k valores próprios da matriz [] t D (com { } min ,kmn=) são idênticos aos da matriz [ ] u D , e as suas raízes quadradas são elementos da matriz [] D dos valores próprios da matriz [] G. (Porque a matriz [] D não é quadrada, apenas é constituída por k elementos não nulos ao longo da sua diagonal.) Como as matrizes [] t D e [ ] u D contêm os quadrados dos valores singulares, pode-se arbitrar se a matriz [] D conterá as raízes quadradas positivas ou negativas. Optando-se pelas raízes positivas, a matriz [] D conterá os k valores singulares positivos ao longo da diagonal e em ordem decrescente () 12 ... k ll l≥≥≥ . Em conjunto com os vectores singulares, os k valores singulares são suficientes para reconstruir completamente a matriz [] G: [] {}{ } 1 kT ii i i GTUl = =Â. Quando a matriz [] G é simétrica, [ ] [ ] [ ] [ ] [ ] 2TT GG G G G==, verifica-se [ ] [ ] TU= e 6 Tal designação apenas deriva das suas posições relativas na respectiva equação. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 61 [ ] [ ] [ ] 2 tu D DD==. Então os valores singulares da matriz [] D correspondem aos valores singulares da matriz [] G, e as matrizes [ ] T e [] U contêm os seus vectores singulares. Por analogia com sistema físicos de partículas vibratórias e com vibrações mecânicas [Bathe, 1996; Kelly, 1993; Meirovitch, 1986], os vectores próprios associados aos maiores valores próprios podem ser denominados por vectores próprios de baixa frequência, enquanto os associados aos menores valores próprios por vectores próprios de alta frequência. A última etapa consiste no cálculo da correlação, no sentido do produto escalar, entre as linhas da matriz [ ] T e as colunas da matriz [] U, resultando a matriz de associação [ ] P : [] [][][] {}{ } 1 kT ii i PTEU TU = == Â, onde a matriz [ ] E é obtida por substituição dos elementos da diagonal da matriz [] D por 1 (um) de forma a desprezar os vectores singulares em excesso da matriz de maiores dimensões. Deste modo o elemento ij P indica a força de atracção entre os pontos i do objecto t e j do objecto 1t+, onde 1 (um) indica um emparelhamento perfeito e 0 (zero) um falso emparelhamento. A correspondência entre dois pontos só deve ser classificada como forte caso ij P seja máximo na sua linha e na sua coluna, o que significa que ambos os pontos reclamam um pelo outro para um bom emparelhamento. Quando ij P é apenas máximo na sua coluna mas não na sua linha, ou vice-versa, uma correspondência fraca está implícita, com vários pontos competindo para o mesmo emparelhamento. Este método maximiza o traço da matriz [][] T P G È˘ Î˚ ; por outras palavras, a matriz [ ] P é uma máscara que actua sobre a matriz [] G e selecciona os elementos de valor mais elevado. Como ij G é elevado quando ij d é reduzido, é garantido um mínimo para o quadrado total da distância de mapeamento. Isto pode ser entendido intuitivamente quando se imaginam pedaços de fio a ligar os pontos emparelhados com o objectivo de minimizar a quantidade total de fio utilizado; contudo, ao mesmo tempo, [ ] P é ortogonal, e assim só pode existir um elemento máximo por linha ou coluna. Desta forma, nenhum ponto do objecto t pode ser fortemente emparelhado com mais do que um ponto do objecto 1t+, garantindo-se o princípio da exclusão. Deve-se notar que, para o emparelhamento, não é a forma absoluta7 dos vectores próprios que é importante mas sim a similaridade relativa entre estes. 7 Isto é, a análise do sinal e do valor das componentes dos vectores próprios. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 62 3.3.2 – Resultados experimentais 3.3.2.1 – Para objectos 2D Considere-se para a primeira experiência, Tabela 3.4, o objecto 1, constituído por 62 pixels do contorno de um objecto, e o 2, resultante da aplicação ao primeiro de uma rotação de 10º em torno do centróide. Optando-se por um valor de s igual à média da distância entre cada pixel e o seu vizinho seguinte determinaram-se 58 correspondências classificáveis como aceitáveis pois foi possível verificar que na sua grande maioria estavam correctas e apenas algumas estavam erradas. Utilizando um valor de s quatro vezes superior ao anterior, obtiveram-se 45 correspondências sendo, desta feita, o número de correspondências erradas mais elevado; tal permite concluir que valores para s demasiado elevados fazem com que as correspondências obtidas sejam globalmente de inferior qualidade. Tabela 3.4 – Dados utilizados e resultados obtidos na primeira experiência para a determinação das correspondências utilizando o princípio do mapeamento segundo a distância mínima. (Nº de Corresp. é o número de correspondências, s/Transformação e c/Transformação indica se foi ou não aplicada a transformação determinada pelo método da secção anterior.) Objecto 1 (62 pixels) Objecto 2 (q=10º) Objectos Sobrepostos (pixels ligados) Correspondências Obtidas s: 5.8, Nº de Corresp.: 58 s: 23.3, Nº de Corresp.: 45 s/Transformação c/Transformação s/Transformação Considere-se agora para a segunda experiência, Tabela 3.5, o objecto 3, constituído por 66 pixels, e o 4, constituído por 61 pixels. Optando-se por um valor de s igual à distância entre os centróides dos objectos, o valor que durante as experiências desenvolvidas durante este trabalho geralmente originava os melhores resultados (e que é também sugerido por Shapiro), determinaram-se 48 correspondências aceitáveis. Utilizando-se apenas 75% dos vectores DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 63 singulares, considerados a partir do primeiro vector, obtiveram-se 47 correspondências que, pela análise das trajectórias estimadas para os pixels, se revelam de qualidade superior. Tal aumento de qualidade é provocado pela não consideração dos vectores associados às frequências mais elevadas geralmente associadas ao ruído. Tabela 3.5 – Dados utilizados e resultados obtidos na segunda experiência para a determinação das correspondências utilizando o princípio do mapeamento segundo a distância mínima. (% dos Vect. é a percentagem dos vectores singulares considerada) Objecto 3 (66 pixels) Objecto 4 (61 pixels) Objectos Sobrepostos (pixels ligados) Correspondências Obtidas % dos Vect.: 100, Nº de Corresp.: 48 % dos Vect.: 75%, Nº de Corresp.: 47 Para a terceira experiência, Tabela 3.6, considere-se o objecto 5, constituído por 57 pixels, e o objecto 6, resultante da aplicação ao primeiro de uma translação de 15 pixels ao longo do eixo x e um escalamento de 1.25 em relação ao centróide. Optando por um valor de s igual à distância entre os centróides dos objectos determinaram-se 41 correspondências que, ao analisar a imagem referente aos resultados, podem ser classificadas como de fraca qualidade pois muitas estão erradas. Outros valores para o parâmetro s foram também considerados; todavia, não foi possível obter resultados que se pudessem classificar como aceitáveis. Tal permite concluir que o método utilizado não é adequado para objectos que apresentem formas bastante diferentes, mesmo quando a transformação envolvida é apenas do tipo rígido. Considere-se para a quarta e última experiência, Tabela 3.7, o objecto 7, constituído por 84 pixels, e o 8, constituído por 81 pixels. Optando por um valor de s igual à distância média entre cada pixel e o seu vizinho seguinte determinaram-se 78 correspondências que visualmente podem ser classificadas como aceitáveis. Esta experiência permite confirmar que quando os objectos envolvidos são semelhantes o método baseado no princípio do mapeamento segundo a distância mínima consegue obter resultados satisfatórios. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 70 [ ] [ ] [ ] [ ] T H VDV=. A matriz diagonal [] D contém os valores próprios, todos positivos pois a matriz [ ] H é definida positivamente, ao longo da sua diagonal e de forma decrescente: [ ] [ ] 12 , ,..., m Ddiagll l= com 12 ... m ll l>>>. A matriz modal [ ] V é ortogonal e tem os vectores próprios como os seus vectores coluna: [ ] { } { } 1m VE E È˘ =Î˚ . Cada linha da matriz [ ] V pode ser referida por um vector linha { } i F designado por vector característica: [] { } {} 1 m F V F È˘ Í˙ =Í˙ Í˙ Î˚ , contendo as m coordenadas modais de cada ponto i, correspondendo à sua projecção nos m eixos modais do objecto. Este processo de computação é executado para os dois objectos t e 1t+. Isto é, para o objecto t, constituído por m pontos, obtemos: [ ] [ ] [ ] [ ] T tttt H VDV=, enquanto para o objecto 1t+, constituído por n pontos, obtemos: [ ] [ ] [ ] [ ] 1111 T tttt HVDV ++++ =. Os vectores característica associados a cada ponto dos dois objectos t e 1t+ são designados por { } ,it F e { } ,1jt F+. A etapa final do método consiste na determinação da correlação entre os dois conjuntos de vectores característica, resultando a matriz de associação [ ] Z . Como no método apresentado na secção anterior, ij Z traduz a confiança no emparelhamento entre os pontos i do objecto t e j do objecto 1t+. Na construção desta matriz de associação [ ] Z deverão ser notadas as seguintes três observações: a) Devido aos objectos terem possivelmente diferentes números de pontos, os números de modos a considerar serão diferentes. A solução passa pela truncagem dos mnmodos menos significativos do objecto com mais pontos, onde os menos significativos são indicados pelos valores próprios mais reduzidos. Desta forma as matrizes modais DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 71 terão k colunas, ou modos, onde { } min ,kmn=; em realizações práticas poderão ser utilizados menos de k modos, conseguindo-se deste modo uma maior imunidade ao ruído. Efectivamente, com este procedimento são desprezadas as componentes dos vectores característica ao longo dos eixos menos importantes. b) O sinal de cada vector próprio não é único, pois invertendo a sua direcção não se viola a ortonormalidade da base; assim, é necessário que ambos os conjuntos de eixos tenham direcções consistentes pois deseja-se comparar directamente os vectores característica. Desta forma, deve-se utilizar um procedimento de correcção do sinal. Resumidamente (ver adiante secção 3.4.2), uma solução passa por considerar { } t V como a base de referência e proceder à orientação de cada eixo de { } 1t V+, um de cada vez, escolhendo para cada um a direcção que maximiza o alinhamento dos dois conjuntos de vectores característica. c) A matriz de associação [ ] Z difere da matriz [ ] P que lhe corresponde no método apresentado na secção anterior no facto de que um emparelhamento perfeito é, neste caso, indicando por 0 (zero), enquanto um valor igual a 2 (dois) indica um emparelhamento completamente falhado (deslocamentos no espaço modal segundo direcções opostas). Deste modo, os melhores emparelhamentos são indicados pelos elementos da matriz [ ] Z que são mínimos na sua linha e na sua coluna. Os valores ij Z são obtidos considerando a distância Euclidiana entre os vectores característica: {} {} 2 ,,1 ij it jt ZF F + =- , em vez dos seus produtos escalares. A vantagem deste procedimento é a robustez à truncagem dos modos não necessários, o melhoramento da sensibilidade, devido a um aumento da gama de valores e, como pode ser analisado no ponto seguinte, uma interface conveniente para o algoritmo de correcção do sinal. Na Figura 3.2 são descritas as várias etapas que constituem o algoritmo deste método baseado na descrição modal da forma de cada objecto a emparelhar. 3.4.2 – Algoritmo de correcção de sinal dos modos e de emparelhamento Neste ponto é apresentado o algoritmo para a correcção do sinal dos vectores próprios e para o emparelhamento entre os pontos que constituem dois objectos. O algoritmo12 tenta, numa primeira fase, solucionar o problema da indefinição da direcção dos vectores próprios e, numa segunda fase, estabelecer o emparelhamento entre os vários pontos. 12 Inicialmente apresentado, e proposto, por Shapiro, em [Shapiro, 1991, 1992, 1992a]. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 72 Objecto t Análise espacial Correcção de sinal e correspondência entre pontos Decomposição em valores/vectores próprios Decomposição em valores/vectores próprios Objecto t+1 Análise espacial Decomposição em valores/vectores próprios Decomposição em valores/vectores próprios Pontos Matrizes de proximidade Modos Matriz de associação ,it X ,1jt X+ [ ] t H [ ] 1t H + [ ] t V [ ] 1t V + [ ] Z Figura 3.2 – Etapas do método baseado na descrição modal da forma. Basicamente, para a solução do problema da indefinição do sinal, o algoritmo começa por admitir que os sinais dos modos do primeiro objecto estão correctos e define o sinal de cada modo do segundo objecto, um a um, de forma a maximizar o número de emparelhamentos obtidos. Para tal, é assumido que os objectos a emparelhar são de formas razoavelmente similares e explora-se o facto de os pontos deverem ser correlacionados. A fase correspondente do algoritmo, considerando-se que existem k modos para cada objecto, ordenados por ordem decrescente dos seus valores próprios, e que os objectos t e 1t+ são constituídos por m e n pontos, pode ser descrita da seguinte forma: • Para cada modo q, começando em 1q= e crescendo até qk=, fazer: a) Com o sinal do vector { } ,1qt E + positivo, isto é, não trocado, calcular uma matriz [ ] () mxn ZP constituída pelas distâncias Euclidianas entre os vectores característica { } ,it F , com 1im££ , e { } ,1jt F + , com 1jn££, onde os vectores característica são truncados a q componentes13: {} {} () 2 ,,1 ij it jt q ZP F F + =-  {} {} () {} {} () 2 2 ,,1 ,,,,1 1 it jt iqt jqt q FF F F ++ - =- + -    (3.4) Somar o menor elemento em cada coluna e guardar o resultado numa variável p C. b) Repetir a) com o sinal de { } ,1qt E + negativo, utilizando uma matriz [ ] () mxn ZN e uma variável n C. 13 Um vector { } i F  truncado a apenas q componentes é {} {} {} {} {} ,1 ,2 , ... 0 ... 0 ii iq i FFF F=  onde {} i F é o vector original. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 73 c) Se p n CC<, então melhores emparelhamentos são obtidos com { } ,1qt E+ positivo, isto é, com sinal não trocado; contudo se np CC>, o sinal de { } ,1qt E+ deve ser trocado. Se p n CC@ então existe uma simetria de reflexão na forma e o sinal pode ser escolhido de forma arbitrária. d) A matriz de associação [ ] Z é actualizada, fazendo-se igual a [ ] Z N ou a [] Z P em função do sinal determinado em c). Na Figura 3.3 está representada, de forma gráfica, a fase do algoritmo para a determinação dos sinais dos vectores próprios do objecto 1t+. yes no Start End [ ] [ ] Z ZP= q = 1, q <= k, q++ i = 1, i <= m, i++ j = 1, j <= n, j++ [ ] [ ] {} {} ,1 ,1qt qt ZZN EE ++ = =- pn CC< {} {} () {} {} ( ) {} {} () {} {} () () () () 2 2 ,,1 ,,,,1 1 2 2 ,,1 ,, ,,1 1 1, 1 1, 1 min min ij it jt iqt jqt q ij it jt iqt jqt q n pimj j n nimj j ZP F F F F ZN F F F F CZP CZN ++ - ++ - ££ = ££ = =- + - =- + -- = =         Figura 3.3 – Representação da fase do algoritmo correspondente à determinação dos sinais dos vectores próprios do objecto 1t+. Para se determinar os emparelhamentos, a fase correspondente do algoritmo pode ser descrita da seguinte forma: • Para cada linha i, com 1im££ , da matriz [ ] Z , isto é para cada ponto i do objecto t: a) Procurar o menor elemento dessa linha; b) Verificar se o menor elemento encontrado em a) apresenta um grau de confiança aceitável através da verificação que o valor de associação não é superior a um limiar arbitrado e se também é o menor valor para a sua coluna: isto é, a associação apresenta um grau de confiança aceitável e o ponto j , com 1jn££, ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 74 do objecto 1t+ também reclama pelo ponto i como o melhor para emparelhar; c) Se a verificação realizada em b) for verdadeira, então o ponto i do objecto t é emparelhado com o ponto j do objecto 1t+. Se tal verificação for falsa, então não é encontrado um bom emparelhamento para o ponto em questão. Na Figura 3.4 está representada, de forma gráfica, a fase do algoritmo para a determinação dos emparelhamentos entre os pontos que constituem os objectos t e 1t+. yes yes no no Start End Xi,t emparelhado com Xk,t+1 Xi,t não emparelhado i = 1, i <= m, i++ limiarM£ ( ) 1, min imk MZ ££ = () , ,1 com 1emin ik ijn MZ knM Z ££ = ££ = Figura 3.4 – Representação da fase do algoritmo para o emparelhamento dos pontos que constituem os objectos t e 1t+. 3.4.3 – Resultados experimentais Neste ponto são analisados alguns resultados experimentais obtidos por uma nossa implementação deste método para objectos, 2D e 3D, rígidos ou não. Em primeiro lugar, serão apresentados alguns resultados na análise modal de objectos 2D e 3D. Posteriormente serão verificados alguns resultados obtidos14 na determinação das correspondências entre objectos 2D e entre objectos 3D. 3.4.3.1 – Na análise modal Como foi referido serão apresentados neste ponto alguns resultados obtidos na análise modal de objectos em “vibração de modo livre” (por analogia com sistemas mecânicos). Em primeiro lugar serão analisados resultados considerando-se objectos 2D e por último objectos 3D. 14 Outros resultados experimentais podem ser analisados em [Tavares, 1997]. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 75 3.4.3.1.1 – Para objectos 2D Para a primeira análise modal a apresentar, Tabela 3.11, considere-se um objecto constituído por 62 pixels e utilize-se um valor para o parâmetro s igual à média da distância entre todos os seus pixels, o valor que durante as experiências realizadas ao longo deste trabalho geralmente originava os melhores resultados de emparelhamento. Para verificar a influência dos modos de vibração nos deslocamentos impostos aos pixels que constituem o objecto original são apresentados os objectos resultantes15 da utilização dos primeiros dez, trinta e de todos os modos de vibração. Analisando-se os objectos apresentados pode-se concluir que a influência dos modos de frequência mais elevadas traduz-se numa inclusão de deformações mais localizadas e semelhante à inclusão de ruído no objecto original (confrontar, por exemplo, os objectos resultantes considerando os dez primeiros modos e todos os modos). Para verificar-se a influência do parâmetro s são também apresentados na mesma tabela os objectos resultantes considerando um valor para s bastante menor do que o anterior, igual à média da distância entre cada ponto e o seu vizinho seguinte, e também a utilização dos primeiros dez, trinta e de todos os modos de vibração. Analisando-se os objectos apresentados, para os dois valores de s, pode-se concluir que a diminuição do valor utilizado implicou um efeito semelhante à diminuição da rigidez do objecto original (confrontar, por exemplo, os objectos resultantes considerando todos os modos de vibração). Considere-se numa nova experiência, Tabela 3.12, um objecto constituído por 120 pixels, resultante de uma amostragem semelhante à utilizada para o objecto considerado na análise anterior mas na qual são mantidos os pontos de elevada curvatura16, e utilize-se um valor para o parâmetro s igual ao menor valor utilizado na experiência anterior. Na referida tabela é possível analisar-se os objectos resultantes utilizando-se a soma dos dez primeiros, de todos os modos e dos modos compreendidos entre o modo noventa e o último. Analisando-se o objecto resultante da consideração da soma dos modos compreendidos entre o modo noventa e o último é possível verificar que as deformações existentes estão essencialmente localizadas nas zonas de maior concentração de nodos. Analisando-se os resultados apresentados para esta experiência e para a anterior pode-se concluir que a consideração dos pontos de elevada curvatura aumentou a concentração de pontos nos vértices do objecto e fez com que o mesmo ficasse “amarrado” nestes pontos. 15 Os objectos apresentados resultam da soma às coordenadas originais de cada pixel dos respectivos deslocamentos impostos pelos modos de vibração considerados. Os conjuntos de modos utilizados foram definidos de forma arbitrária apenas com o intuito de ilustrar de forma adequada os objectivos da experiência em causa. 16 Após o cálculo da curvatura em cada ponto do objecto original os pixels que apresentavam um valor elevado foram conservados durante a amostragem. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 76 Tabela 3.11 – Objecto original e objectos resultantes da análise modal do mesmo utilizando-se dois valores diferentes para o parâmetro s. Objecto Original (62 pixels) Objecto Original com Pixels Ligados Objectos Resultantes, s: 45.4 nº de modos: 10 30 62 (todos) Objectos Resultantes, s: 5.1 nº de modos: 10 30 62 (todos) Na Figura 3.5 são sobrepostos os objectos resultantes da consideração da soma de todos os modos de vibração nas três análises modais apresentadas. 3.4.3.1.2 – Para objectos 3D Consideremos um objecto 3D, constituído por 314 pontos, e um valor para o parâmetro s igual à distância média entre todos os seus pontos, Tabela 3.13. Considerando-se a soma dos primeiros seis, doze, vinte e cinco, cem, duzentos e de todos os modos de vibração, obtiveram-se os objectos representados na referida tabela. Na mesma tabela estão também representados os objectos resultantes da consideração da soma dos modos de vibração compreendidos entre o modo vinte e cinco e o cem e entre o modo duzentos e o último. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 77 Tabela 3.12 – Objecto original, resultante de utilização de uma amostragem que conservou os pixels de elevada curvatura, e objectos resultantes da análise modal do mesmo. Objecto Original (120 pixels) Objectos Resultantes, s: 5.1 nº de modos: 10 120 (todos) 30, a partir do modo 90 Figura 3.5 – Objectos resultantes em cada análise efectuada considerando-se todos os modos. Considerando o mesmo objecto original mas desta vez um valor para o parâmetro s bastante superior obtiveram-se, como seria de esperar, objectos que traduzem um aumento da rigidez do objecto original. Na Tabela 3.13 estão representados os objectos resultantes da consideração dos doze primeiros modos e da consideração dos vinte e cinco primeiros modos; analisando-se estes objectos, e também as Figura 3.6 e Figura 3.7, pode ser comprovado o aumento de rigidez verificado. Como se pode comprovar a partir deste exemplo, quanto mais elevado o valor para o parâmetro s mais rígido se torna o objecto e cada vez mais se começa a notar o efeito e a inclusão de perturbações semelhantes a ruído localizado, normalmente provocado pelos modos de frequências mais elevadas, nos primeiros modos (confrontar, por exemplo, os objectos resultantes considerando-se a soma dos primeiros vinte e cinco modos). ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 78 Tabela 3.13 – Objecto original e objectos resultantes da análise modal do mesmo utilizando-se dois valores diferentes para o parâmetro s. Objecto Original (314 pontos) Objectos Resultantes, s: 3.8 nº de modos: 6 12 25 100 200 314 (todos) 75, a partir do modo 25 64, a partir do modo 250 DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 79 Tabela 3.13 – Objecto original e objectos resultantes da análise modal do mesmo utilizando-se dois valores diferentes para o parâmetro s. (Continuação) Objectos Resultantes, s: 100 nº de modos: 12 25 Figura 3.6 – Objectos obtidos utilizando-se os doze primeiros modos e com 3.8s= e 100s=. [Reprodução a cores em anexo.] Figura 3.7 – Objectos obtidos utilizando-se os vinte e cinco primeiros modos e com 3.8s= e 100s=. [Reprodução a cores em anexo.] 3.4.3.2 – Na determinação de correspondências Neste ponto são apresentados alguns resultados experimentais obtidos na utilização deste método para a determinação de correspondências entres objectos rígidos e não rígidos. Em primeiro lugar serão apresentados resultados obtidos considerando-se objectos 2D e, seguidamente, serão apresentados resultados para objectos 3D. 3.4.3.2.1 – Para objectos 2D Para se verificar os resultados obtidos por este método considere-se, o objecto 1, constituído por 62 pixels, e o 2, resultante da aplicação ao primeiro de uma transformação rígida constituída por uma rotação de -15º em torno do centróide e um escalamento de 1.25 em relação ao mesmo ponto e uma translação de 50 pixels em relação ao eixo x e de -65 pixels em relação ao eixo y, Tabela 3.14. Optando-se por valores para os parâmetros s iguais à média da distância entre todos os pontos de cada um dos objectos obtiveram-se 62 emparelhamentos correctos (100%). Aplicando-se ao objecto 1 a rotação e a translação determinadas, pelo método apresentado na primeira secção deste capítulo, obtivemos a figura ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 86  Sob o ponto de vista de implementação o método é bem condicionado, linear em termos do número de pontos e potencialmente paralizável18. 3.4.4.1 – Valor considerado para o parâmetro s  A função do parâmetro s é a de controlar a largura da função Gaussiana, centrada em cada ponto, determinando a influência dos pontos vizinhos. Se s for reduzido, menor do que a distância entre pontos vizinhos, os elementos da matriz de proximidade não diagonais são aproximadamente iguais a zero e a matriz [ ] H é praticamente diagonal. Assim que s seja mais elevado, os elementos não diagonais aumentam até que no limite, para o qual sÆ•, todos os elementos da matriz [ ] H são iguais a um.  Quando s é reduzido, os m valores próprios são aproximadamente iguais: 12 ... 1 m ll lªªª ª. Quando s aumenta, os valores próprios tornam-se mais distintos obtendo-se 12 ... m ll l>>>.  Quando s é bastante elevado, o primeiro valor próprio 1 l tende para m e, necessariamente, os restantes tendem para zero. Os modos associados a valores próprios tão reduzidos provocam severos problemas computacionais tornando-se, assim, necessário reduzir o valor de s quando tal situação ocorre. 3.4.4.2 – Da análise modal de um objecto Dos resultados experimentais obtidos na análise modal de objectos podemos concluir o seguinte:  Quanto mais elevado é o valor do parâmetro s menor é influência dos detalhes do objecto original e maior é a zona do objecto final perturbada pelos mesmos.  O aumento do valor do parâmetro s suaviza o objecto final.  Os modos de baixa frequência estão associados a deformações globais e os de alta frequência a deformações locais.  A consideração dos modos de alta frequência tem um efeito semelhante ao de inclusão de ruído no objecto final. 3.4.4.3 – Da determinação de correspondências Os resultados experimentais obtidos na determinação das correspondências entre objectos 2D ou 3D, permitem concluir: 18 Em [Barbosa, 2000, 2000a] é descrita uma versão paralizada deste método. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO ANÁLISE MODAL DA FORMA 87  Quando a deformação existente entre os dois objectos é essencialmente rígida poucos modos de vibração são suficientes para se obterem emparelhamentos aceitáveis;  Geralmente são obtidos melhores resultados de emparelhamento utilizando-se valores para os parâmetros s próximos da média da distância entre todos os pontos que constituem cada objecto;  A utilização de valores demasiado reduzidos (ou demasiado elevados) para os valores dos parâmetros s torna impossível obter-se emparelhamentos aceitáveis;  A não inclusão dos modos de alta frequência em geral favorece a obtenção de melhores emparelhamentos;  Nos vários testes efectuados ao longo deste trabalho o valor do limiar para um emparelhamento ser considerado como possível não teve influência relevante nos resultados obtidos; tal sugere que a exigência de mínimo na linha e na coluna parece ser suficiente para classificá-lo como bom ou não;  Também nos vários testes efectuados se verificou que a não consideração na base modal dos modos de vibração que tenham frequências praticamente iguais geralmente favorece os resultados de emparelhamento obtidos;  Para obter-se bons resultados de emparelhamento a relação entre os valores de t s e 1t s+ deve reflectir a escala existente entre cada objecto de modo que os dois conjuntos de valores próprios tenham a mesma ordem de grandeza;  Por vezes, a inclusão dos pontos de elevada curvatura facilita a resolução dos casos para os quais é difícil obter-se emparelhamentos satisfatórios;  Os emparelhamentos obtidos são de melhor qualidade se a deformação existente entre os dois objectos não for apenas restrita a uma zona reduzida dos mesmos;  O processo de determinação das correspondências pode ser bastante acelerado se não forem determinados todos os valores/vectores próprios para cada objecto, mas apenas um número suficiente19 de forma a ser possível obter-se correspondências satisfatórias. A consideração de apenas 25% dos modos revelou-se, ao longo das experiências, um número geralmente adequado. 3.4.4.4 – Adaptação do método para objectos do tipo contorno Na construção da matriz de proximidade [ ] H para cada objecto é considerada, na equação (3.2), a distância Euclidiana entre cada ponto e todos os restantes. Contudo, quando o objecto em questão é um contorno, e assim não apresenta pontos no seu interior, tal consideração faz 19 Por exemplo, em [Bathe, 1996] são descritos vários métodos iterativos para a determinação de um subconjunto dos valores/vectores próprios de uma matriz simétrica. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 88 com que a influência de pontos já afastados de zonas particulares dos contornos possam ainda exercer elevada influência sobre estas. Numa tentativa de se adaptar este método a objectos deste tipo entendeu-se que seria preferível passar a utilizar na equação (3.2) as distâncias entre os pontos determinadas ao longo do contorno, em vez das distâncias Euclidianas. 3.5 – Sumário Neste capítulo é inicialmente apresentado um método para a determinação da transformação geométrica rígida existente entre dois objectos, 2D ou 3D, cujos pontos tenham sido previamente emparelhados. Este método, baseado em minimização por mínimos quadrados do erro da transformação determinada, utiliza quaternions unitários para representar a rotação envolvida e é de fácil implementação sem qualquer processo iterativo. Os resultados obtidos pela implementação desenvolvida demonstram que é possível obter-se boas estimativas para a transformação geométrica existente sem a necessidade de considerar um elevado número de correspondências. Ao longo do trabalho, verificou-se também que a possibilidade de determinar a transformação rígida é de facto de muito interesse mesmo quando os objectos a emparelhar são deformáveis, pois assim é possível distinguir-se as transformações globais do tipo rígido das essencialmente localizadas. Seguidamente foi descrito um método para determinar as correspondências entre dois objectos, 2D ou 3D, rígidos ou não, segundo um mapeamento baseado no princípio da distância mínima. Apesar de o método ser bastante atraente do ponto de vista de implementação, pela sua simplicidade, os resultados obtidos para objectos reais só são satisfatórios quando existir uma elevada semelhança no posicionamento, na orientação e nas formas dos objectos em questão. Esta inadaptação, verificada pelas experiências realizadas, deve-se ao facto de não ser considerada a estrutura de cada objecto na modelização utilizada. A referida inadequação para objectos relativamente diferentes na forma, posicionamento ou orientação, originou o desenvolvimento de um novo método, apresentado na quarta secção deste capítulo. Este método utiliza informação da estrutura de cada objecto na modelização, através da análise dos vectores próprios de forma dos dois objectos a emparelhar. Os resultados experimentais obtidos comprovam a sua melhor adaptação para objectos reais e confirmam tratar-se de um método bastante interessante para a determinação das correspondências entre objectos 2D ou 3D, rígidos ou não. 89 Capítulo IV DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL Na sequência dos dois métodos antes apresentados para a determinação de correspondência entre objectos, apresenta-se neste capítulo uma nova abordagem ao mesmo problema, incorporando princípios físicos. Em vez de se basear a determinação das correspondências nodais na construção de matrizes de proximidade geométrica, usa-se uma modelização física dos objectos por meio do método dos elementos finitos, na qual o objecto se considera constituído por um certo material virtual e se utiliza a análise modal para determinação dos emparelhamentos nodais. Após uma introdução ao método dos elementos finitos, é formulada a análise modal e analisado o método proposto. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 91 4.1 – Introdução O problema do seguimento de objectos ao longo de uma sequência de imagens é um dos temas centrais da visão por computador. O reconhecimento do objecto nas imagens e o seu emparelhamento na sequência exige a definição de modelos de descrição dos objectos baseados em descritores como contornos, superfícies ou volumes. As primeiras dificuldades associadas a essa descrição são: os descritores do objecto são sensíveis ao ruído, o objecto pode não ser rígido, a aparência de um objecto deforma-se se a geometria utilizada na captação das imagens for alterada. Estes problemas motivaram a utilização de modelos deformáveis para interpolar, suavizar e segmentar dados. Modelos deformáveis, por si só, não incluem um método para cálculo dos descritores canónicos para reconhecimento ou para obter a correspondência entre conjuntos de dados. Para resolver este problema Sclaroff e Pentland, [Pentland, 1990, 1991], desenvolveram um método para representar objectos por deformações canónicas a partir de um objecto protótipo. Descrevendo a forma do objecto em termos dos valores próprios da matriz de rigidez do objecto protótipo, é possível obter para a mesma uma descrição robusta e ordenada pela frequência. Além do mais, estes vectores ou modos próprios são um método intuitivo para descrição da forma pois correspondem aos eixos de simetria generalizados do objecto. Representando os objectos em termos das deformações modais, este método é robusto para a modelização 3D, reconhecimento de objectos, e seguimento 3D utilizando pontos, contornos, distâncias e fluxo óptico. Contudo, este método ainda não resolve o problema da determinação da correspondência entre conjuntos de dados ou entre dados e modelos. Tal é devido à imposição de cada objecto ser necessariamente descrito por deformações a partir de um único objecto protótipo, o que impõe a priori uma parametrização implícita dos dados para assim determinar (implicitamente) a correspondência entre os dados e o protótipo. Para solucionar este problema, Sclaroff [Sclaroff, 1995, 1995a] propôs um método com o qual é possível obter os invariantes modais de forma directamente a partir dos dados, permitindo calcular descritores canónicos robustos para o reconhecimento e resolver problemas de correspondência. Sclaroff modeliza cada objecto por intermédio de um elemento finito isoparamétrico [Bathe, 1996; Segerlind, 1984] e determina para este as matrizes de massa, de rigidez e dos modos próprios de vibração. Obtendo estas matrizes para cada um dos dois modelos, obtêm-se os emparelhamentos através da similaridade dos deslocamentos de cada dado pontual no respectivo espaço modal; desta forma, dados que apresentam deslocamentos semelhantes nos dois espaços modais são declarados como correspondentes. Para determinar os deslocamentos dos dados não emparelhados por análise modal, Sclaroff utiliza um processo de minimização da energia de deformação, segundo princípios físicos. Com este procedimento, são estimados os deslocamentos para os dados não emparelhados de forma a serem congruentes com o próprio objecto em análise e com as propriedades do material virtual utilizado na sua modelização. O valor determinado para a ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 92 energia de deformação pode ser posteriormente utilizado como medida global de similaridade entre os dois objectos em análise. Com a descrição modal utilizada, as deformações são descritas de forma perfeitamente ordenada, do nível global para o local, através das frequências de vibração em modo livre [Meirovitch, 1986]. O método que a seguir se apresenta para a determinação de correspondências entre objectos 2D ou 3D, rígidos ou não, foi adaptado do método proposto por Sclaroff, e generalizado a qualquer tipo de modelização física dos objectos pelo método dos elementos finitos. Com o novo método proposto é possível obter os emparelhamentos dos dados pontuais que constituem dois objectos, estimar os deslocamentos dos dados que tenham falhado o emparelhamento por análise modal, e obter uma medida da deformação, independentemente do tipo de elementos finitos utilizados na modelização. 4.2 – Princípio do método Considere-se o problema de, a partir de dois conjuntos de dados pontuais, se pretender determinar se eles correspondem ou não a dois objectos similares. A abordagem mais comum para resolver este tipo de problema é a de tentar determinar características locais distintivas que possam ser emparelhadas com alguma confiança; essa abordagem falha quando existe insuficiente informação local e quando as condições de obtenção dos dados ou a sua deformação alteraram significativamente a aparência das características locais utilizadas. Uma outra abordagem consiste em determinar um referencial de corpo centrado para cada objecto e depois tentar emparelhar os dados pontuais. Desde que os dados estejam descritos por coordenadas intrínsecas, ou por coordenadas de corpo centrado, em vez de coordenadas cartesianas, é mais fácil obter a correspondência entre os dados dos dois objectos. Muitos métodos para determinar o referencial de corpo centrado têm sido sugeridos, incluindo métodos de momentos de inércia, de determinação das simetrias e descritores polares de Fourier. Geralmente estes métodos apresentam as seguintes dificuldades: erros de amostragem, erros de parametrização e de não unicidade. A grande contribuição do método proposto (na sequência do trabalho de Sclaroff) é a de determinar um sistema de referência local que evita, em grande parte, estas três dificuldades. Os erros de amostragem são bem compreendidos: os dados observados e as suas localizações podem ser drasticamente alteradas de imagem para imagem. A solução mais comum para este tipo de problema é a de apenas utilizar estatísticas globais, como momentos de inércia; contudo, na melhor das hipóteses, tais métodos oferecem soluções fracas ou parciais. Os erros de parametrização são mais subtis. O problema ocorre quando, por exemplo, se ajusta um conjunto de dados pontuais utilizando-se uma esfera deformável 3D, o que impõe um sistema coordenado radial nos dados em vez de permitir que os mesmos determinem por si só um adequado sistema de coordenadas. Consequentemente, a descrição resultante é DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 93 afectada fortemente, por exemplo, pelas distorções compressivas e de corte típicas da perspectiva. O elevado número de artigos sobre simetrias distorcidas é indicativo da seriedade deste tipo de problema. A não unicidade é um problema óbvio para o reconhecimento e emparelhamento, mas que é muitas vezes ignorado quando se procura um qualquer tipo de descrição estável. Virtualmente, todos os métodos baseados em splines, em placas finas e em polinómios, não são capazes de gerar descrições canónicas; geralmente este problema é devido ao facto de os parâmetros para as entidades consideradas serem definidos de forma arbitrária, e assim não serem invariantes à mudança de vista, a oclusões e a deformações não rígidas. O método proposto para a determinação de correspondências entre dois objectos procura solucionar as três dificuldades referidas nas seguintes etapas: 1. É calculada uma descrição da forma de cada objecto, robusta em relação à amostragem, pela utilização de interpolação de Galerkin, matematicamente associada ao método dos elementos finitos. 2. É utilizada uma modelização de cada objecto por intermédio de elementos finitos, o que permite obter a parametrização da forma directamente a partir dos dados. 3. São utilizados os modos próprios de vibração de cada objecto modelizado para se obter um sistema de coordenadas canónico ortogonal e ordenado pela frequência. Cada um destes sistemas pode ser encarado como os eixos de simetria generalizados para a forma do respectivo objecto. Com a descrição da localização dos dados pontuais neste sistema de corpo centrado é fácil emparelhar dados correspondentes e medir a similaridade entre objectos diferentes, o que permite o reconhecimento de objectos e determinar se diferentes objectos são relacionados por simples transformações físicas. Um diagrama do método proposto está representado na Figura 4.1. MU KU R  mr lqlq  determinar as matrizes de massa e de rigidez para o modelo finito Saída: Entrada: Determinação dos modos próprios Construção do modelo físico utilizar os modos 1 lq i emparelhados como sistema de coordenadas MU KU R  mr lqlq  determinar as matrizes de massa e de rigidez para o modelo finito KM iii IZ I lq lq 2 resolver o problema de valores/vectores próprios generalizado KM iii IZ I lq lq 2 resolver o problema de valores/vectores próprios generalizado emparelhar os modos 1 lq i não rígidos de baixa ordem de ambos os modelos dados pontuais considerados como nodos de um modelo de elementos finitos correspondência entre dados Figura 4.1 – Diagrama do método proposto neste capítulo. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 94 Para cada imagem, consideram-se as localizações dos dados pontuais > @ 1m XX X do objecto em questão e utilizam-se estes como nodos na construção do seu modelo de elementos finitos, constituídos por um determinado material virtual (por exemplo, borracha). De seguida, são determinados os modos próprios de vibração ^ ` i 1 dos modelos de elementos finitos. Estes modos proporcionam uma descrição ortogonal, ordenada pela frequência, de cada objecto e das suas deformações naturais. Tais vectores são, por vezes, designados por vectores de forma para cada modo [Kelly, 1993; Meirovitch, 1986] pois descrevem como cada modo deforma o objecto por alteração das localizações originais dos dados, por meio de: ^ ` deformado i XXa1 , em que a é um escalar. Os primeiros modos (3 em 2D e 6 em 3D) são os modos de corpo rígido enquanto os restantes respeitam a movimento não rígido [Bathe, 1996; Meirovitch, 1986]. Os modos não rígidos são ordenados por ordem crescente da frequência de vibração; no geral, os modos (não rígidos) de baixa frequência descrevem deformações globais, enquanto que os modos de elevada frequência descrevem essencialmente as deformações localizadas. Este ordenamento do global para o local é bastante útil na comparação e emparelhamento de objectos. Os modos próprios também formam um sistema de coordenadas ortogonal e centrado no objecto para descrição da localização dos dados pontuais. Isto é, a localização de cada dado pontual pode ser descrita de forma única em termos do seu movimento segundo cada modo próprio. A transformação entre as localizações no sistema cartesiano e no sistema modal é conseguida pela utilização dos vectores próprios do modelo finito como uma base coordenada. Na técnica adoptada, dois grupos de dados são comparados neste espaço próprio. A ideia base é que os modos de baixa ordem para dois objectos similares deverão ser bastante próximos mesmo na presença de deformações afins [Folley 1991; Hall, 1993], deformações não rígidas, perturbações locais da forma ou de ruído. Utilizando esta propriedade, a correspondência entre dois objectos é determinada por emparelhamento modal, sendo a correspondência entre dois objectos determinada por comparação das suas trajectórias em cada espaço modal. Dados cujo emparelhamento apresenta um elevado grau de confiança são obtidos por este processo; os deslocamentos dos restantes dados serão estimados pela utilização do modelo físico como uma restrição de suavização. Finalmente, determinada a correspondência entre os dados pontuais que constituem dois objectos, pode-se medir as suas diferenças de forma. Como o processo modal decompõe as deformações num conjunto ortogonal, pode-se medir selectivamente as diferenças de corpo rígido, ou deformações do tipo projectivo de baixa ordem, ou deformações que são principalmente locais. Consequentemente, pode-se reconhecer objectos duma maneira flexível e geral. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 95 Alternativamente, dadas as correspondências, pode-se alinhar ou distorcer um objecto num outro. Tal alinhamento é útil na fusão de dados obtidos por sensores diferentes, ou na comparação de dados obtidos em instantes de tempo distintos ou sob condições diferentes. Também é útil em computação gráfica, domínio em que a referida distorção é designada por morphing [Folley 1991]. Em resumo, pode-se afirmar que esta técnica modal oferece duas vantagens sobre outras técnicas existentes: • Pode ser utilizada automaticamente para identificar e etiquetar dados correspondentes em dois objectos; de tal forma, pode ser possível, sem intervenção de um utilizador, alinhar, comparar e realizar morphing entre os dois. • A representação modal obtida permite a separação de diferentes tipos de deformação. Além destas vantagens, deve-se ter em conta que a representação modal é suportada pelas teorias defendidas por biólogos envolvidos no estudo da morfologia dos esqueletos e das formas dos animais, segundo as quais espécies diferentes estão relacionadas entre si por deformações. Estudos recentes também utilizam as deformações modais para a descrição do crescimento de órgãos de animais e no alinhamento entre órgãos do mesmo tipo [Martin, 1998; Syn, 1995, 1995a] e demonstram que os parâmetros de deformação correspondem qualitativamente aos que são utilizados pelos humanos em animação e na pesquisa em bases de dados. Quando o volume de dados é muito elevado, a obtenção dos modos próprios pode ser um processo bastante custoso em termos computacionais; contudo, para se obter um procedimento mais rápido existem algumas soluções possíveis: para uma classe particular de formas similares, os modos podem ser predeterminados e generalizados [Pentland, 1990, 1991a]; em alguns casos, para topologias do tipo tubo e esfera, Nastar [Nastar, 1994] demonstrou que os modos de deformação podem ser determinados analiticamente; é também possível utilizar-se o método proposto utilizando interpolação do espaço modal (ver adiante secção 4.5.1); podem utilizar-se implementações paralelizadas para a determinação dos modos próprios de vibração [Barbosa, 2000, 2000a]. 4.3 – Introdução ao método dos elementos finitos O aumento da complexidade das estruturas e da capacidade dos computadores favoreceu o aparecimento de novos métodos computacionais de análise, nomeadamente o método dos elementos finitos. Após uma utilização inicial em problemas de elasticidade [Bathe, 1996; Segerlind, 1984], a mesma técnica foi-se rapidamente estendendo a outros domínios como o da transferência de calor e da mecânica dos fluidos, do electromagnetismo, das vibrações mecânicas e acústicas [Kelly, 1993; Meirovitch, 1986], da computação gráfica [Essa, 1992; ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 96 Pentland, 1989; Pentland, 1989a], da realidade virtual, nomeadamente em simulações cirúrgicas [Bro-Nielsen, 1996; Keeve, 1996], da visão por computador1, etc. O objectivo do método é a obtenção de uma formulação que possa explorar a análise, de forma automática, de sistemas complexos e/ou irregulares, por intermédio de programas computacionais. Para atingir tal objectivo, o método considera o sistema global como equivalente a um agrupamento de elementos finitos no qual cada um deles é uma estrutura contínua mais simples. Impondo que em certos pontos comuns a vários elementos, designados por nodos ou nós, os deslocamentos sejam compatíveis e as forças internas estejam em equilíbrio, o sistema global resultante do agrupamento reage como uma única entidade. Apesar do método dos elementos finitos considerar os elementos individuais como contínuos, ele é, na sua essência, um procedimento de discretização pois exprime os deslocamentos, as deformações e as tensões em qualquer ponto de um elemento contínuo em termos de um número finito de deslocamentos nos seus pontos nodais, usando funções de interpolação2 apropriadas. A vantagem do método é que a equação de movimento para o sistema global pode ser obtida pelo agrupamento das equações determinadas individualmente para cada elemento finito utilizado na modelização. O movimento em qualquer ponto do interior de cada um destes elementos é obtido por intermédio de interpolação, sendo as funções de interpolação, geralmente, polinómios de grau reduzido e iguais para elementos do mesmo tipo. Uma outra vantagem do método dos elementos finitos é a facilidade com que a sua generalização pode ser conseguida para a resolução de problemas bidimensionais e tridimensionais constituídos por vários materiais e com fronteiras irregulares. Os passos essenciais de uma solução numérica pelo método dos elementos finitos são os seguintes: 1. Subdivisão do sistema global contínuo em elementos finitos; 1 Desde a primeira utilização do método dos elementos finitos por Pentland em 1989, [Pentland, 1989], no domínio da visão por computador, que a mesma tem vindo a generalizar-se às suas diferentes áreas, nomeadamente: • análise de movimento 2D e 3D, rígido e não rígido [Benayoun, 1994, 1994a; Cootes, 1995; Nastar, 1994, 1994a; Pentland, 1991; Sclaroff, 1994a]; • obtenção de estruturas 2D e 3D [Cohen, 1991; Kakadiaris, 1996; Pentland, 1991a]; • análise de faces [Essa, 1995]; • análise de objectos deformáveis 2D e 3D [McInermey, 1996; Park, 1996; Pentland, 1990; Pentland, 1991]; • representação de imagens 2D e 3D [Moulin, 1992]; • alinhamento de imagens e modelos 2D e 3D [Syn, 1995a, 1995b, 1996]; • descrição de objectos 2D e 3D [Sclaroff, 1994, 1995, 1995a; Syn, 1995, 1996]. 2 Também designadas por funções de forma, devem ser contínuas e em cada nodo do respectivo elemento o seu somatório deve ser igual a 1 [Bathe, 1996]. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 103 primeira aplicação obtém-se ^ ` ^ ` 1 Ue7, na segunda aplicação ^ ` ^ ` 2 Ue, e assim por adiante até que, após a última aplicação, resulta: > @ ^ ` ^ ` K UR. (4.6) O vector de carga ^ ` R é: ^ ` ^ ` ^ ` ^ ` ^ ` BSIC R RRRR. (4.7) A matriz > @ K é a matriz de rigidez para o sistema global: >@  () () () () () e e Te eee eV K K BDBdV ËÛ ÍÝ ËÛ ËÛ ËÛ ÍÝ ÍÝ ÍÝ ÇÔ  . (4.8) O vector de carga ^ ` R inclui o efeito das forças de corpo ^ ` B R : ^`  ^ ` ^` () () () () e e B TBe ee B eV R R NfdV ËÛ ÍÝ ÇÔ  , (4.9) o efeito das forças de superfície ^ ` S R : ^ `  ^ ` ^` () () 1 () () () ,, ee q e S TSe Se e S eSS R R NfdS ËÛ ÍÝ ÇÔ   , (4.10) o efeito da tensão inicial no vector ^ ` I R : ^`  ^ ` ^` () () () () e e I TIe ee I eV R R BdV8 ËÛ ÍÝ ÇÔ      , (4.11) e as cargas concentradas ^ ` c R . Note-se que o somatório dos integrais de volume na equação (4.8) exprime a adição directa das matrizes de rigidez dos elementos utilizados  e K ËÛ ÍÝ de forma a obter-se a matriz de rigidez do sistema global > @ K . Do mesmo modo, o agrupamento do vector de forças de corpo ^ ` B R é determinado pela adição directa dos vectores das forças de corpo dos elementos utilizados   ^ ` e B R; os vectores ^ ` S R e ^ ` I R são obtidos de forma similar. Como já foi referido, o processo de agrupamento das matrizes e dos vectores dos elementos por esta 7 O vector ^ ` i e tem todas as suas componentes nulas exceptuando a componente i que é unitária. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 104 adição directa é designado por método directo de rigidez. Este processo de agrupamento baseia-se em dois factores principais: as dimensões de todas as matrizes e de todos os vectores são as mesmas, e os graus de liberdade de cada elemento são iguais aos graus de liberdade do conjunto agrupado. Evidentemente que na prática, apenas as linhas e as colunas diferentes de zero para as matrizes e vectores de cada elemento são calculadas (correspondendo aos efectivos graus de liberdade nodais de cada elemento), e o agrupamento é executado utilizando para cada elemento um vector de conectividade no qual são guardados os índices, em relação ao conjunto agrupado, dos graus de liberdade associados ao elemento. Na prática, também as matrizes e os vectores de cada elemento finito podem, por questões de simplificação do seu cálculo, ser primeiramente calculadas relativamente aos seus graus de liberdade locais, não alinhados com os graus de liberdade do conjunto agrupado; neste caso, antes de se proceder ao agrupamento deve-se realizar uma transformação dos graus de liberdade locais para os graus de liberdade globais (ver adiante secção 4.3.1.1). Isto equivale a transformar o sistema de coordenadas local no sistema de coordenadas global. A equação (4.6) é a equação de equilíbrio estático para o sistema global. Na consideração deste equilíbrio, as forças aplicadas podem variar com o tempo e neste caso, os deslocamentos também variam com o tempo e a equação (4.6) é a equação de equilíbrio para um qualquer instante de tempo específico. Contudo, se as cargas forem aplicadas de forma rápida, as forças de inércia não podem ser desprezadas; isto é, é necessário resolver um verdadeiro sistema dinâmico. Utilizando-se o princípio de d’Alembert8 pode-se simplesmente incluir as forças de inércia como parte das forças de corpo. Assumindo que as acelerações são aproximadas da mesma maneira que os deslocamentos na equação (4.7), a contribuição das forças totais de corpo no vector das cargas ^ ` R é (com o sistema de coordenadas  ,,XYZ estacionário): ^`    ^ `   ^ `  e T eBeee e B eV R Nf NUdV7 ËÛ ËÛ ËÛ  ÍÝ ÍÝ ÍÝ ÇÔ , (4.12) onde o vector  ^ ` Be f já não inclui as forças de inércia, ^ ` U  é o vector das acelerações nodais (isto é, a segunda derivada de ^ ` U em relação ao tempo), e   e 7 é a densidade de massa do elemento e. Neste caso as equações de equilíbrio resultantes são: > @ ^ ` > @ ^ ` ^ ` M UKU R  , (4.13) onde ^ ` R e ^ ` U são dependentes do tempo. A matriz >@ M é a matriz de massa para o sistema global: 8 Principio de d’Alembert [Beer, 1981]: as forças externas que actuam sobre um corpo rígido são equivalentes às forças efectivas dos vários pontos materiais que formam o corpo. Este princípio permite utilizar o princípio dos deslocamentos virtuais, definido para problemas de equilíbrio estático, em problemas de equilíbrio dinâmico através da consideração da força de inércia como parte das forças de corpo. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 105 >@ () () () () () () e e T ee e e eV M M NNdV7 ËÛ ÍÝ ËÛËÛ ÍÝÍÝ ÇÔ  . (4.14) Na medição das respostas dinâmicas reais do sistema global é observado que alguma energia é dissipada durante a vibração; na análise de vibrações tal dissipação é geralmente considerada pela introdução de forças de amortecimento dependentes da velocidade. Introduzindo estas forças na equação (4.12) como contribuições adicionais às forças de corpo, obtém-se: ^`    ^ `   ^ `   ^ `  e T eBeee ee e B eV R Nf NU NUdVUN ËÛ ËÛ ËÛ ËÛ  ÍÝ ÍÝ ÍÝ ÍÝ ÇÔ  . Neste caso o vector  ^ ` Be f já não inclui as forças de inércia nem as do amortecimento dependente da velocidade, ^ ` U  é o vector das velocidades nodais (isto é a primeira derivada de ^ ` U em relação ao tempo), e   e N é o parâmetro de amortecimento para o elemento e. Neste caso, as equações de equilíbrio resultantes são: > @ ^ ` > @ ^ ` > @ ^ ` ^ ` M UCUKU R    , (4.15) onde > @ C é a matriz de amortecimento do sistema global: >@ () () () () () () e e T ee e e eV C CNNdVN ËÛ ÍÝ ËÛËÛ ÍÝÍÝ ÇÔ  . Na prática é difícil, se não impossível, determinar para sistemas gerais de elementos finitos os parâmetros de amortecimento para os elementos que os constituem, particularmente porque as propriedades de amortecimento são dependentes da frequência. Por esta razão, a matriz > @ C não é geralmente obtida por agrupamento das matrizes de amortecimentos dos elementos mas sim construída a partir das matrizes de massa e de rigidez do sistema global conjuntamente com resultados experimentais do valor de amortecimento. Por exemplo, no caso de amortecimento proporcional, a matriz de amortecimento do sistema é uma combinação linear de potências das matrizes de massa >@ M e de rigidez > @ K [Bathe, 1996], isto é: > @ > @ > @ rs CK M,- , onde , e - são valores reais e r e s são valores inteiros. No caso de amortecimento proporcional com r e s iguais a um, então o amortecimento é proporcional e viscoso ficando a equação matricial de movimento para o sistema global com a forma: ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 106 > @ ^ ` > @ > @ ^ ` > @ ^ ` ^ ` M UMKUKUR,-        . Em resumo, uma análise completa de um sistema pelo método dos elementos finitos consiste no cálculo da matriz de rigidez > @ K (e numa análise dinâmica, das matrizes de massa >@ M e de amortecimento > @ C) e do vector das cargas {} R , na determinação dos deslocamentos ^ ` U a partir da equação (4.6) (ou numa análise dinâmica dos deslocamentos ^ ` U, das velocidades ^ ` U  e das acelerações ^ ` U  a partir da equação (4.13) ou da (4.15)), e de seguida no cálculo das deformações e das tensões nos elementos, utilizando respectivamente as equações (4.2) e (4.3). 4.3.1.1 – Graus de liberdade locais e globais Para a derivação das matrizes dos elementos é geralmente mais fácil e conveniente estabelecer em primeiro lugar as matrizes desejadas relativamente aos seus graus de liberdade locais. A construção das matrizes do elemento finito correspondentes aos graus de liberdade globais pode ser depois obtida directamente pela identificação dos graus de liberdade globais que correspondem aos seus graus de liberdade locais. Uma vez que as matrizes dos elementos (por exemplo,  e N ËÛ ÍÝ ,  e B ËÛ ÍÝ ou  e K ËÛ ÍÝ ) foram definidas para os graus de liberdade globais, o processo de agrupamento fica facilitado, visto que nessas matrizes são nulos todos os elementos que não se situem nas linhas e colunas relativas aos graus de liberdade do elemento. Assim, considerando incluídos no vector ^ ` ˆ u (cujas entradas são os deslocamentos em ^ ` U que pertencem ao elemento) apenas os graus de liberdade locais dos nodos do elemento pode-se escrever: ^ ` > @ ^ ` ˆ uNu , (4.16) onde as entradas no vector ^ ` u são os deslocamentos do elemento relativamente ao sistema de coordenadas local. Por outro lado, também se tem: ^ ` > @ ^ ` ˆ B u0. (4.17) Nas equações (4.16) e (4.17), as matrizes de interpolação são definidas relativamente aos graus de liberdade locais do elemento a que se referem. Reescrevendo para o elemento as relações antes usadas para as matrizes de massa e de rigidez e para o vector de carga, obtémse: > @ > @ > @ > @ T V K BDBdVÔ, (4.18) DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 107 > @ > @ > @ T V M NNdV7Ô, (4.19) ^ ` > @ ^ ` TB B V R NfdVÔ, (4.20) ^` ^ ` T SB S S R NfdS ËÛ ÍÝ Ô, (4.21) ^ ` > @ ^ ` TI I V R BdV8Ô, (4.22) onde todas as variáveis são definidas como nas equações (4.8) até (4.14), mas correspondendo aos graus de liberdade locais do elemento finito considerado. Desde que as matrizes dadas nas equações (4.18) até (4.22) estejam calculadas para todos os elementos, elas podem ser agrupadas directamente, pelo processo já descrito, determinando-se assim as matrizes para o sistema global. Neste processo de agrupamento é assumido que as direcções dos deslocamentos nodais do elemento ^ ` ˆ u na equação (4.16) são as mesmas que as direcções dos deslocamentos nodais globais ^ ` U. Contudo, por vezes é conveniente começar a derivação das matrizes e dos vectores relativamente aos graus de liberdade locais do elemento ^ ` u  que não são alinhados com os graus de liberdade globais do sistema agrupado ^ ` ˆ u. Neste caso tem-se: ^ ` ^ ` uNu ËÛ ÍÝ  , (4.23) e ^ ` > @ ^ ` ˆ uTu , (4.24) onde a matriz > @ T transforma os graus de liberdade ^ ` ˆ u nos graus de liberdade ^ ` u  ; a equação (4.24) corresponde a uma transformação de tensor de primeira ordem; as entradas na coluna j da matriz > @ T são os co-senos directores de um vector unitário correspondendo ao grau de liberdade j do vector ^ ` ˆ u quando medido segundo as direcções dos graus de liberdade ^ ` u . Substituindo a equação (4.24) na (4.23), obtém-se: ^ ` ^ ` N NT ËÛ ÍÝ . (4.25) Assim, identificando por K ËÛ ÍÝ , M ËÛ ÍÝ , ^ ` B R  , ^ ` S R  e ^ ` I R  as matrizes e vectores do método dos elementos finitos relativamente aos graus de liberdade ^ ` u  , obtém-se, a partir da equação (4.25) e das equações (4.18) até (4.22): > @ > @ > @ T K TKT ËÛ ÍÝ , > @ > @ > @ T M TMT ËÛ ÍÝ  , ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 108 ^ ` > @ ^ ` T BB R TR , ^ ` > @ ^ ` T SS R TR  , ^ ` > @ ^ ` T II R TR  . Deve-se notar que estas transformações também são utilizadas quando são impostos deslocamentos na fronteira que não correspondem aos graus de liberdade globais do sistema agrupado. 4.3.1.2 – Determinação das deformações e das tensões Conhecido o campo dos deslocamentos num elemento, o cálculo das componentes do tensor das deformações segue-se por diferenciação [Bathe, 1996; Branco, 1985]: xx u x 0 b b, yy v y 0 b b, zz w z 0 b b, xy uv yx J    , yz vw z y J    , zx wu x z J    , ou utilizando a notação matricial: ^` 00 00 00 0 00 0 0 0 xx yy zz xy yz xz xx ux yy vy u wz zv uy vx w yx vz wy uz wx zy zx H H H HJ J J                                                                    >@ ^` >@ ^` 0 00 ˆˆ 0 0 0 z N uBu yx zy zx                           , onde u é o deslocamento e xx 0 a deformação segundo o eixo x , v é o deslocamento e y y H a deformação segundo o eixo y, w é o deslocamento e z z 0 a deformação segundo o eixo z , xy J (igual a y x J) a deformação de corte no plano  , x y, y z J (igual a z y J) a deformação de corte no plano  ,yz e z x J (igual a xz J) a deformação de corte no plano  , x z. Por questões de tratamento matricial do método dos elementos finitos, as componentes das deformações são geralmente agrupadas num vector designado por vector das deformações ^ ` 0: ^` ^ ` T xx yy zz xy yz zx H HHHJJJ. Conhecidos em cada ponto do elemento os deslocamentos e as deformações, pode ser realizado o cálculo das tensões instaladas. Admitindo que, para o nível das forças aplicadas ao elemento, o material se encontra no domínio linear-elástico, isto é, no domínio de aplicabilidade da lei de Hooke, as componentes do tensor das tensões ^ ` 8 podem ser DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 109 calculadas a partir de: ^ ` > @ ^ ` D80, onde ^` ^ ` T xx yy zz xy yz zx 8888999 é o vector das tensões de componentes xx 8 para a tensão segundo o eixo x , y y 8 para a tensão segundo o eixo y, z z 8 para a tensão segundo o eixo z , xy 9 (igual a y x 9) para a tensão de corte no plano  , x y, y z 9 (igual a z y 9) para a tensão de corte no plano  ,yz e z x 9 (igual a xz 9) para a tensão de corte no plano  , x z. A matriz de elasticidade >@ D para estados tridimensionais de tensão tem a seguinte forma [Branco, 1985]: >@    11 11 11 1 1 1 1000 1000 1000 1 000 00 112 0000 0 00000 E D ,, ,, ,, : - :: - -             , (4.26) onde : é o coeficiente de Poisson9, E o módulo de elasticidade, 11 : , :   e  1 12 21 : -:    . Utilizando-se a lei de Hooke generalizada pode-se escrever: ^ ` > @ ^ ` 08, onde >@  é a matriz que relaciona as tensões com as deformações para o material considerado e é dada por [Branco, 1985]: >@    1 000 1 000 1000 1 00021 0 0 000 0 21 0 000 0 0 21 E :: :: :: : : :  ËÛ ÌÜ  ÌÜ ÌÜ  ÌÜ  ÌÜ ÌÜ  ÌÜ  ÌÜ ÍÝ . (4.27) 9 Quando uma barra é traccionada, o alongamento axial é acompanhado por uma contracção lateral, isto é, a largura da barra torna-se menor e o seu comprimento aumenta. A relação entre as deformações transversal e longitudinal, dentro da região elástica, é constante e conhecida [Timoshenko, 1994] por coeficiente de Poisson. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 110 4.3.1.2.1 – Estado plano de tensão Quando o sistema elástico é muito fino e não existem forças aplicadas segundo a direcção paralela à espessura, pode-se considerar que as tensões resultantes são constantes ao longo da espessura e está-se perante o que é usualmente designado por estado plano de tensão. O deslocamento de um ponto P , de coordenadas  ,, x yz, será descrito pelas duas componentes, u e v, do seu vector de deslocamento ^ ` u. Em geral os deslocamentos serão diferentes de um ponto para outro mas independentes da cota z . As componentes u e v serão portanto funções de x e y. Usando uma notação matricial pode-se escrever: ^ ` ^ ` T uuv. Conhecido o campo dos deslocamentos, o cálculo das componentes do tensor das tensões será efectuado de acordo com a Mecânica dos Meios Contínuos. Dado o carácter bidimensional do problema o vector das tensões resultante é ^` ^ ` T xx yy xy 8889, não havendo tensões envolvendo o eixo z (na realidade são bastante reduzidas e por isso desprezadas). O vector das deformações resultante é ^` ^ ` T xx yy zz xy HHHHJ; isto é, apesar de estado plano, existe deformação segundo o eixo z : () z zxxyy E : 088 , desprezando-se as restantes deformações de corte relacionadas com o eixo z por serem bastante reduzidas. Para este estado a matriz de elasticidade >@ D é definida como [Branco, 1985]: >@ 2 10 10 11 00 2 E D : : : : ËÛ ÌÜ ÌÜ ÌÜ ÌÜ  ÌÜ ÍÝ . 4.3.1.2.2 – Estado plano de deformação Quando o sistema não expande segundo a direcção perpendicular ao plano das forças aplicadas, isto é, quando a espessura é elevada, pode-se considerar o sistema como em estado plano de deformação. Se as forças aplicadas actuam no plano  , x y então w, o deslocamento segundo a direcção z , é zero e os deslocamentos u e v são apenas funções de x e y. Este conjunto de deslocamentos faz com que as deformações relacionadas com o eixo z sejam nulas, resultando o vector de deformações ^` ^ ` T xx yy xy HHHJ e o vector das tensões DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 111 ^` ^ ` T xx yy zz xy 88889 com a tensão segundo o eixo z determinada a partir da lei de Hooke como:  112 zz xx yy E: 888 ::      , e as restantes tensões relacionadas com o mesmo eixo reduzidas e por isso desprezadas. Para este estado a matriz de elasticidade >@ D é definida como [Branco, 1985]: >@ 22 22 0 0 11 00 2 E D ,- -, :        , onde 2 1 12 : ,:    e 212 : -:   . 4.3.2 – Material adoptado Na Tabela 4.1 [Crandall, 1978] estão indicados os valores do módulo de Young E , do coeficiente de Poisson : e da densidade 7 para alguns materiais isotrópicos. Tabela 4.1 – Algumas propriedades para materiais isotrópicos à temperatura ambiente. (1 GN/m2 = 145 × 103 psi, 1 psi = 6.895 kN/m2) Material E (GN/m2) : 7 (103 kg/m3) Alumínio 68-78.6 0.32-0.34 2.66-2.88 Bronze 100-110 0.33-0.36 8.36-8.50 Cobre 117-118 0.33-0.36 8.94-8.97 Ferro fundido 89-145 0.21-0.30 6.95-7.34 Aço 193-220 0.26-0.29 7.72-7.86 Titânio 106-114 0.34 4.51 Vidro 50-79 0.21-0.27 2.38-3.88 Polietileno 0.14-0.38 0.45 0.91 Borracha 0.00076-0.0041 0.50 1.0-1.24 Obviamente que as propriedades do material adoptado condicionam o comportamento do modelo construído; assim é possível, variando as suas propriedades, alterar o seu comportamento esperado e adaptá-lo a um problema concreto. Como será possível analisar no próximo capítulo, verifica-se que as propriedades do material influenciam o comportamento do modelo na análise em modo livre de vibração, e no valor da energia de deformação necessária para alinhar dois modelos; no entanto, no que respeita ao emparelhamento entre dois modelos, a única propriedade que exerce influência relevante é o coeficiente de Poisson, que controla a resistência do modelo ao corte. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 112 4.4 – Formulação da análise modal O sistema de equações do equilíbrio dinâmico do modelo de elementos finitos agrupado: > @ ^ ` > @ ^ ` > @ ^ ` ^ ` M UCUKU R    , pode ser desacoplado impondo as suas equações numa base definida pelos vectores próprios de > @ > @ 1 M K  ortonormais à matriz de massa >@ M . Estes vectores próprios e os respectivos valores próprios são a solução ^ `  2 ,i i IZ do problema de valores próprios generalizado [Bathe, 1996; Chapra, 1988; Press, 1992]: > @ ^ ` > @ ^ ` 2 i ii KMIZ I. (4.28) O vector ^ ` i 1 é designado por vector de forma para o modo i e i Z é a correspondente frequência de vibração [Bathe, 1996; Kelly, 1993; Meirovitch, 1986]. Os vectores de forma podem ser interpretados como uma descrição dos eixos generalizados de simetria do objecto. A equação (4.28) pode ser escrita como: > @ > @ > @ > @ > @ KM) ) :, (4.29) onde, para um objecto 2D constituído por m nodos: >@ ^` ^` ^ ` ^` ^` ^` 1 12 1 T T m T m T m u u v v 11 ËÛ ÌÜ ÌÜ ÌÜ ÌÜ ËÛ ) ÍÝ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÍÝ    e >@ 2 1 2 2m Z Z ËÛ ÌÜ : ÌÜ ÌÜ ÍÝ ; e para um objecto 3D constituído por m nodos: >@ ^` ^` ^ ` ^` ^` ^` ^` ^` 1 1 13 1 T T m T m T m T T m u u v v w w 11 ËÛ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ËÛ ) ÌÜ ÍÝ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÍÝ     e >@ 2 1 2 3m Z Z ËÛ ÌÜ : ÌÜ ÌÜ ÍÝ . DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 119 das amplitudes modais a determinar. Nesta formulação é assumido que as amplitudes dos modos desprezados são nulas. Os termos na equação anterior podem ser reagrupados obtendose: >@ >@ >@ ^` ^` >@ >@ >@ ^ ` ^` 11 0 00 não conhecido conhecido conhecida não conhecida não conhecido U IU IU                       . As amplitudes dos modos pretendidas podem ser obtidas directamente por inversão da matriz do lado direito desta equação. Note-se que, com este procedimento obteve-se novamente uma solução para determinar as amplitudes não conhecidas, mas foi assumido que os deslocamentos modais são nulos para os modos ip. Esta simplificação pode não ser a mais adequada pois, por exemplo, zonas relativamente extensas cujos pontos não foram emparelhados por análise modal não se deformam com esta solução, o que pode ser inconsistente com a deformação existente. Adicionando uma restrição de minimização da energia de deformação podem-se evitar os inconvenientes das duas soluções anteriores [Sclaroff, 1995, 1995a]. A energia de deformação pode ser obtida directamente a partir dos deslocamentos modais: ^` >@ ^` 1 2 T S E UU :  . (4.35) Analisando esta equação é possível concluir que, apesar de normalmente os modos mais elevados corresponderem a deslocamentos de baixa amplitude (semelhantes a ruído), as suas contribuições no valor total da energia de deformação podem ser importantes pois é tomado o quadrado das correspondentes frequências (elevadas). Esta observação sugere que, no cálculo da energia de deformação para efeitos de comparação de objectos, pode ser vantajoso não considerar, ou considerar de forma menos acentuada, a participação dos modos mais elevados. Formulando uma solução por mínimos quadráticos restringida, na qual se minimiza o erro de alinhamento que inclua o termo da energia de deformação, obtém-se: ^` >@ ^ ` ^` >@ ^ ` ^ ` >@ ^ ` energia de erro de ajuste deformação quadrático TT E rroUUUUUUO            , (4.36) onde O é o parâmetro de Lamé [Bathe, 1996] para o material adoptado:   112 EX OXX   . Diferenciando a equação (4.36) em relação ao vector dos deslocamentos modais ^ ` U  resulta a equação de minimização da energia de deformação: ^ ` >@>@ >@ >@ ^` 1 TT UUO        . ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 120 Desta forma, podem-se explorar as características do modelo físico utilizado de forma a incluir certas restrições geométricas numa solução pelo método dos mínimos quadrados. A medida da energia de deformação permite a incorporação de algum conhecimento prévio acerca do esticamento admissível para o objecto, da sua resistência à compressão, etc. Utilizando este conhecimento adicional, podem-se prever razoavelmente os deslocamentos que os nodos não emparelhados deverão assumir. Como o algoritmo para a determinação dos emparelhamentos calcula o grau de certeza para os emparelhamentos obtidos, pode-se também utilizar esta informação directamente na fase de alinhamento, o que é obtido por inclusão de uma matriz diagonal > @ W: ^ ` >@>@>@ >@ >@>@ ^` 1 22TT UW WUO        . Os elementos da matriz > @ W variam inversamente com a medida de afinidade para o emparelhamento do respectivo nodo11. O vector dos deslocamentos nodais ^ ` U é determinado através dos emparelhamentos obtidos (equação (4.33)), considerando-se nulas, para os nodos não emparelhados, as respectivas entradas na matriz > @ W. Este procedimento de minimização da energia de deformação é semelhante ao utilizado no domínio dos contornos activos: o modelo físico é utilizado como restrição de suavização [Blake, 1998; Cohen, 1991; Kass, 1988]. 4.6.2 – Solução dinâmica: Morphing No ponto anterior foram descritos métodos para determinar os deslocamentos modais que deformam directamente e alinham dois conjuntos de dados. Embora não tenha sido implementado durante este trabalho, também é possível resolver o problema de alinhamento de dois modelos por simulação física, integrando no tempo as equações do modelo de elementos finitos até se atingir um equilíbrio. Neste caso, determinam-se as deformações em cada instante de tempo através da equação dinâmica de equilíbrio dada pela equação (4.32). De seguida, calculam-se as deformações intermédias de uma maneira consistente com as propriedades do material utilizado na formulação do modelo. As deformações intermédias também podem ser utilizadas para morphing segundo princípios físicos. Quando se resolve a equação dinâmica utilizam-se dados de um modelo 2 para exercer forças que os transformem nos dados do outro modelo 1. As cargas dinâmicas  ^ ` R t nos nodos dos modelos de elementos finitos são assim proporcionais às distâncias entre nodos 11 Por exemplo,   ii ij WZ\\ sendo ij Z a afinidade do emparelhamento entre os pontos i e j respectivamente dos objectos t e 1t. Nas implementações realizadas durante este trabalho utilizou-se \ igual a 1. DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 121 emparelhados:  ^ `  ^ `    ^ `   ^ ` 1, 2,ii ii i Rt t Rt k X Ut X     , (4.37) onde k é uma constante global de rigidez e  ^ ` i Ut é o deslocamento nodal para o nodo i no instante de tempo anterior. Estas forças simulam forças elásticas a actuar sobre os nodos dos dois modelos e vão diminuindo até que estes estejam perfeitamente ajustados. O equilíbrio dinâmico modal pode ser descrito por um sistema de 2m (2D) ou 3m (3D) equações independentes com a seguinte forma:  ^ `  ^ `  ^ `  ^ ` 2 ii ii ii Ut C Ut Ut RtZ       , onde  ^ ` i R t  contém as componentes para o nodo i do vector de carga transformado:  ^ ` > @  ^ ` T R tRt . Estas equações independentes de equilíbrio podem ser resolvidas por um procedimento de integração numérica iterativa, por exemplo, pelo método de Newmark [Bathe, 1996]. O sistema é integrado no tempo até a diferença na carga ser inferior a um dado limiar /:  ^ `  ^ ` 22 Rt t Rt /   . A carga  ^ ` i R t a actuar no nodo i é actualizada em cada instante de tempo considerado através da equação (4.37). 4.6.3 – Consideração de rotações elevadas Se a rotação necessária para alinhar os dois conjuntos de dados for potencialmente muito elevada então, antes de se determinarem as deformações modais, é conveniente realizar um alinhamento inicial. A orientação, o posicionamento e o escalamento podem ser determinados utilizando-se o algoritmo baseado em quaternions unitários apresentado na secção 3.2 do capítulo anterior. Utilizando-se apenas as correspondências determinadas para alguns nodos emparelhados com elevada certeza, a transformação de corpo rígido pode ser determinada directamente. Os parâmetros adicionais resultantes para este alinhamento prévio são: • vector de posição: ^ ` 0 p ; • quaternion unitário definindo a orientação: q ; • factor de escala: s ; ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 122 • centróides dos dois conjuntos: ^ ` t c e ^ ` 1t c  . Como a estimação dos parâmetros da transformação rígida existente é realizada utilizando-se apenas as correspondências com certeza elevada, obtêm-se geralmente boas soluções. Os objectos podem então ser alinhados através da determinação das deformações modais ^ ` U , como foi previamente descrito. Como anteriormente, são calculadas as cargas virtuais que deformam os dados de um modelo nos dados do outro modelo com que foram devidamente emparelhados. Como foi introduzida mais uma rotação, uma translação e um escalamento, a equação (4.33) deve ser modificada de forma a traduzir a distância entre os dados no sistema de coordenadas correcto: ^` >@ ^` ^` ^` ^ ` ^` ^ ` 2, 0 1, 1T iitti URXpccX s     , onde > @ R é a matriz de rotação obtida a partir do quaternion unitário q . 4.6.4 – Comparação de objectos Conhecidas as amplitudes dos modos, pode-se calcular a energia de deformação utilizando a equação (4.35). Esta energia pode ser utilizada como medida de similaridade. Em certos casos também pode ser desejável comparar a energia de deformação num dado subconjunto de modos, considerados como importantes na medição da similaridade, ou então a energia associada a cada modo. A energia de deformação associada ao modo i com deslocamento modal i U  e frequência i Z é simplesmente: 22 1 2 i Sii EUZ . Por vezes pode ser útil avaliar a similaridade de objectos, sem determinar previamente a correspondência entre os seus dados, o que pode ser conseguido através da comparação das respectivas amplitudes modais. Determinam-se em primeiro lugar as descrições modais de cada objecto e, depois, utiliza-se uma qualquer métrica de distância para medir a distância entre os descritores modais, o que sugere um espaço coordenado alternativo para descrição da dissemelhança entre objectos: o espaço de similaridade modal. Neste espaço a similaridade de objectos é proporcional à distância Euclidiana entre os seus descritores modais. A energia necessita de ser modificada, se se pretender usá-la como medida de distância, uma vez que não satisfaz uma das condições para uma métrica: • Existência de mínimo:  ,,0AB AA//_; DETERMINAÇÃO DE CORRESPONDÊNCIAS UTILIZANDO MODELIZAÇÃO FÍSICA E ANÁLISE MODAL 123 • Simetria:  ,,AB BA//; • Desigualdade triangular:  ,,,AB BC AC// /. Embora a existência de mínimo e a desigualdade triangular sejam satisfeitas, a energia de deformação não satisfaz a simetria. A energia de deformação não é simétrica para objectos com tamanhos diferentes; por exemplo, se a escala de dois objectos A e B diferir, então a energia necessária para alinhar A com B pode ser diferente da necessária para alinhar B com A. A diferença na deformação será inversamente proporcional ao produto das escalas nos diferentes eixos. Deste modo, quando se comparam objectos com diferentes escalas devese dividir a energia de deformação pela área/volume do objecto em questão. Quando um mapa de suporte for conhecido, esta área/volume pode ser determinada directamente. No caso de suporte infinito, a área/volume dos dados pode ser aproximada pelo cálculo do menor círculo/esfera que os engloba. Existe uma propriedade adicional que prova a utilidade da definição de uma métrica, a adição segmentada:  ,,,AB BC AC// /, se B estiver na fronteira entre A e C. Para satisfazer a adição segmentada pode-se considerar a raiz quadrada da energia de deformação: 22 1 2ii i U a GZÇ, onde a é a área/volume do objecto. Tal resulta numa distância métrica ponderada semelhante à distância de Mahalanobis [Tavares, 1995a]: as amplitudes modais são desagregadas, cada qual tendo uma “variância” inversamente proporcional ao valor próprio do modo. Como resultado, esta formulação pode ser utilizada como parte de um esquema de regularização evolutiva no qual a matriz de covariância inicial >@ : é actualizada iterativamente de forma a incorporar as covariâncias dos parâmetros modais observados, por exemplo utilizando filtragem de Kalman [Maybeck, 1979; Tavares, 1995a] ou análise das componentes principais [Cootes, 1992, 1994a, 1995; Martin, 1998; Nastar, 1996]. Utilizando-se a análise das componentes principais pode-se descrever uma classe dos modos próprios de um objecto a partir de um conjunto de treino. Utilizando um modelo modal como uma estimativa inicial, pode-se de seguida aprender iterativamente os “verdadeiros” modos por via de uma análise recursiva das componentes principais. Como resultado, obterse-á um esquema regularizado de aprendizagem, no qual a matriz inicial de covariância é actualizada iterativamente de forma a incorporar as covariâncias para os parâmetros modais observados. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 124 4.7 – Sumário Neste capítulo foi apresentado um método para determinação de correspondências entres dois objectos 2D ou 3D, rígidos ou não, baseado em modelização física e na análise modal de vibração em modo livre dos objectos modelizados. Na modelização é utilizado o método dos elementos finitos, considerando-se que os objectos a emparelhar são construídos por um determinado material virtual responsável pelo seu comportamento elástico. Após a modelização de cada um dos dois objectos a emparelhar, os seus modos de vibração em modo livre são determinados. Com os dois conjuntos de vectores de forma, que constituem os respectivos espaços modais, são analisados os deslocamentos nestes espaços de cada dado pontual que constitui os objectos. Pontos que apresentem deslocamentos similares são classificados como pontos correspondentes. Para se estimar os deslocamentos dos pontos não emparelhados, utiliza-se a minimização da energia de deformação necessária para alinhar o primeiro objecto com o segundo. Esta energia de deformação constitui uma medida da deformação necessária para se alinhar dois objectos e permite a sua compararão. A vantagem deste método, relativamente aos métodos apresentados no capítulo anterior, está relacionada com a consideração de um material virtual na construção dos objectos a emparelhar, conseguindo-se deste modo uma modelização física para os mesmos e fazendo com que as correspondências sejam determinadas, não por um processo “estatístico” sem grande ligação ao comportamento físico esperado para os objectos mas, pelo contrário, de acordo com as características elásticas do material adoptado. 125 Neste capítulo são apresentados os modelos de objectos a serem utilizados no método de determinação de correspondências, baseado em modelização física e análise modal, tratado no capítulo anterior. São apresentados os dois tipos de modelização física adoptados: o baseado num único elemento finito isoparamétrico, e o que agrupa elementos finitos axiais. São também descritos os métodos usados para selecção dos nodos que constituem o modelo de representação de cada objecto. O capítulo apresenta ainda alguns resultados experimentais ilustrativos, para análise de vibração em modo livre, para determinação de correspondências e estimação de deslocamentos nodais e para cálculo da energia de deformação como medida de semelhança. Capítulo V MODELOS PONTUAIS E ELEMENTOS FINITOS UTILIZADOS MODELOS PONTUAIS E ELEMENTOS FINITOS UTILIZADOS 127 5.1 – Introdução Tendo sido tratada a metodologia proposta para a determinação de correspondências entre objectos 2D e 3D, abordam-se neste capítulo os tipos de elementos finitos considerados na construção dos modelos físicos e os processos usados na determinação do conjunto de pontos que constituem a rede de nós a partir das imagens. A secção seguinte apresenta a construção das matrizes de massa e de rigidez, para modelos 2D e 3D, relativas a dois tipos de elementos finitos: o modelo finito isoparamétrico1 de Sclaroff e o agrupamento de modelos finitos axiais lineares. A terceira secção trata da extracção, a partir das imagens, do conjunto de pontos definidores de objectos 2D e 3D, em especial contornos 2D e superfícies 3D; no caso das superfícies 3D também se considera a sua modelização por meio de um conjunto de contornos 2D isonível. Na quarta secção apresentam-se e discutem-se alguns resultados experimentais, nos quais os modelos precedentes são usados para se efectuar a análise modal em regime livre de vibração, para determinar a correspondência entre objectos e estimar os deslocamentos nodais, e para determinar a energia de deformação. A última secção apresenta um sumário do capítulo em que se destacam algumas das principais conclusões. 5.2 – Elementos finitos utilizados Os elementos finitos usados e a definição das respectivas matrizes de massa >@ M e de rigidez > @ K são apresentados, de forma separada para os objectos 2D e 3D, nas subsecções 5.2.1 e 5.2.2. 5.2.1 – Para objectos 2D Apresentam-se de seguida os dois tipos de elementos finitos que foram utilizados na modelização de objectos bidimensionais. Em primeiro lugar é apresentado o elemento isoparamétrico de Sclaroff e, seguidamente, o elemento finito axial linear. Com um único elemento finito de Sclaroff é possível modelizar-se um objecto definido pelos seus pontos sem a necessidade de existência de ordem entre eles; no caso de um conjunto de elementos finitos do tipo axial, devidamente agrupados, torna-se necessária a existência de ordem entre os nodos que definem o objecto. 1 Fundamentalmente [Bathe, 1996] os elementos isoparamétricos caracterizam-se por utilizarem a mesma função de aproximação, ou de forma, para descrever a geometria do elemento e o campo dos deslocamentos. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 128 5.2.1.1 – Elemento isoparamétrico de Sclaroff Na técnica de modelização de Sclaroff utilizam-se os próprios dados pontuais do objecto em questão para a construção das matrizes de rigidez e de massa, considerando esses pontos como os nodos do elemento finito a ser considerado. Em primeiro lugar desenvolve-se uma formulação para o elemento finito utilizando funções Gaussianas como interpoladores de Galerkin2 e, seguidamente, utilizam-se estes interpoladores para se obter as matrizes generalizadas de massa e de rigidez. Intuitivamente, as funções de interpolação suavizam os dados pontuais, e as áreas delimitadas por estes são preenchidas com um material virtual que tem propriedades físicas de massa e de rigidez. Esta suavização e preenchimento da nuvem de pontos fazem com que exista uma boa imunidade ao ruído e à falta de alguns pontos, assim como torna desnecessária a informação acerca da conectividade entre pontos. As funções de interpolação também permitem atribuir maior peso a pontos importantes e diminuir o peso associado a pontos com menor importância. Este aumento ou diminuição do peso é conseguido por variação das propriedades do material virtual entre os dados pontuais. 5.2.1.1.1 – Interpoladores Gaussianos Dado um conjunto de m pontos amostrados de um objecto ( i X) é necessário construir as matrizes de massa e de rigidez apropriadas. O primeiro passo é optar por um conjunto de funções de interpolação a partir das quais seja possível derivar (ver capítulo anterior) as matrizes das funções de forma3 > @ N e de deformação > @ B . Em soluções típicas do método dos elementos finitos aplicados em engenharia são utilizadas funções de interpolação polinomiais de Lagrange ou de Hermite [Bathe, 1996; Segerlind, 1984]; as matrizes de massa >@ M e de rigidez > @ K são determinadas para cada tipo de elemento finito utilizado na modelização e são agrupadas de forma a obter-se as correspondentes matrizes para o sistema global (ver capítulo anterior). O problema presente é diferente, pois o pretendido é examinar os modos próprios de uma nuvem de dados pontuais. Este problema é idêntico ao verificado na interpolação de redes: tem-se um certo número de medidas dispersas e pretende-se encontrar um conjunto de 2 A determinação dos coeficientes, habitualmente designados por parâmetros nodais, das funções de interpolação utilizadas na formulação de um elemento finito, pode fazer-se de diversas formas correspondendo cada uma à imposição de um conjunto de condições fronteira a serem verificadas. Um destes métodos é o método de Galerkin [Bathe, 1996; Segerlind, 1984], que é a base do método dos elementos finitos em problemas nos quais estão envolvidos termos da primeira derivada. Este método impõe erro médio pesado nulo em todo o domínio e usa no método dos Resíduos Pesados as próprias funções de interpolação como funções de ponderação. 3 Isto é, optar por um conjunto de funções de interpolação contínuas i h de tal forma que: 1. os seus valores são unitários para o nodo i a que estão associadas e nulos nos restantes; 2. 1 1.0 m i i h   Ç em qualquer ponto do objecto. MODELOS PONTUAIS E ELEMENTOS FINITOS UTILIZADOS 129 funções de base que permitam a inserção e movimentação de dados pontuais. Funções de base Gaussianas são candidatas ideais para este tipo de problema de interpolação, tendo a forma:    22 2 i XX i gX e 8 , (5.1) onde i X é o centro de dimensão n da função Gaussiana e 8 é o desvio padrão, que controla a interacção entre os dados. Nesta modelização desenvolvem-se as funções de interpolação i h como a soma de m funções de base, uma por cada dado pontual i X:   1 m iikk k hX ag X  Ç, (5.2) onde ik a são os coeficientes que satisfazem os requisitos para as funções de forma. A matriz dos coeficientes de interpolação > @ A pode ser determinada por inversão da matriz >@ G definida como: >@     11 1 1 m mmm gX gX G gX gX ËÛ ÌÜ ÌÜ ÌÜ ÍÝ    . (5.3) Utilizando os interpoladores Gaussianos como funções de forma para a aproximação de Galerkin, é possível formular facilmente elementos finitos de qualquer dimensão, os quais podem ser obtidos por agrupamento de Gaussianos de menor dimensão. Um aspecto bastante útil dos interpoladores Gaussianos é que eles são factorizáveis: interpoladores multidimensionais podem ser formados a partir de Gaussianos de menor dimensão. Este facto não só reduz o custo computacional, como pode ser também útil para implementações de hardware VLSI ou de redes neuronais. Deve-se notar que o somatório dos interpoladores Gaussianos não é conforme [Bathe, 1996], pois não satisfaz a condição de, em qualquer ponto de elemento, o somatório das funções de forma ser igual a 1 (um). Como consequência, a interpolação entre nodos da deformação e da tensão não é conservativa em termos de energia. Normalmente este facto não apresenta inconvenientes em aplicações da visão por computador; de facto, a grande maioria das formulações de elementos finitos utilizadas em visão são também não conformes [Sclaroff, 1995, 1995a]; contudo, se for pretendido um elemento conforme, ele pode ser obtido através da inclusão de um factor de normalização em i h:    1 11 m ik k k imm jk k jk ag X hX ag X    Ç ÇÇ . (5.4) ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 136 >@ 4565.669 -3487.052 1408.415 844.367 0.000 0.000 0.000 0.000 -3487.052 4197.662 -1752.839 -1036.613 0.000 0.000 0.000 0.000 1408.415 -1752.839 2435.106 555.524 0.000 0.000 0.000 0.000 844.367 -1036.613 555.524 1829.475 0.000 0.0 M 00 0.000 0.000 0.000 0.000 0.000 0.000 4565.669 -3487.052 1408.415 844.367 0.000 0.000 0.000 0.000 -3487.052 4197.662 -1752.839 -1036.613 0.000 0.000 0.000 0.000 1408.415 -1752.839 2435.106 555.524 0.000 0.000 0.000 0.000 844.367 -1036.613 555.524 1829.475 Ë Û Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Í Ý , >@ 0.092 -0.105 0.025 -0.002 -0.015 0.014 0.001 -0.008 -0.105 0.154 -0.055 0.002 0.014 -0.012 -0.004 0.008 0.025 -0.055 0.041 0.000 0.001 -0.004 0.004 -0.002 -0.002 0.002 0.000 0.016 -0.008 0.008 -0.002 0.000 -0.015 0.014 0.001 -0.008 0. K 062 -0.060 0.023 -0.024 0.014 -0.012 -0.004 0.008 -0.060 0.075 -0.031 0.030 0.001 -0.004 0.004 0.002 0.023 -0.031 0.028 -0.017 -0.008 0.008 -0.002 0.000 -0.024 0.030 -0.017 0.017 ËÛ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÍÝ . Comparando as matrizes obtidas, utilizando-se a formulação original e a modificada, verificase, de forma mais acentuada, que com a formulação sugerida para contornos se diminui a influência do nodo 4 sobre o nodo 2. Torna-se assim evidente que com a modificação sugerida se consegue ponderar de forma mais adequada a este tipo de objectos a influência exercida por cada nodo sobre os restantes. Esta ponderação assume maior importância nos casos em que se pretende diminuir a influência exercida sobre os pontos que constituem zonas particulares de um contorno pelos pontos cuja distância Euclidiana é reduzida, apesar de estarem muito afastadas ao longo do contorno. 5.2.1.2 – Elementos axiais lineares Durante este trabalho desenvolveu-se uma metodologia original para modelizar objectos segundo princípios físicos, que consiste na utilização de um conjunto de elementos finitos do tipo axial, devidamente agrupados. De seguida descreve-se a formulação para este tipo de elementos finitos standard. Utilizando-se a abordagem variacional [Meirovitch, 1986], as matrizes de rigidez e de massa e o vector de forças nodais equivalentes podem ser obtidos através das expressões em coordenadas nodais, para a energia potencial, para a energia cinética e para o trabalho virtual, respectivamente. O deslocamento axial  ,uxt do sistema de segunda ordem da Figura 5.3 pode ser escrito com a forma:        ^ `  ^ ` 11 2 2 ,T uxt N xu t N xu t Nx ut  , (5.13) MODELOS PONTUAIS E ELEMENTOS FINITOS UTILIZADOS 137 onde  ^ ` N x é o vector de dimensão 2 das funções de forma, com o índice a indicar qual o nodo com que cada função de forma está associada, e  ^ ` ut é o correspondente vector de deslocamentos nodais. Deve-se notar que esta equação apenas é válida no interior do elemento em questão e não é aplicável fora deste. x l x u(x,t) f1(t) f2(t) u1(t)u2(t) m(x), massa em x E , módulo de Young A (x), área em x Figura 5.3 – Elemento axial. A energia cinética  Tt para um elemento finito e do tipo axial é simplesmente:      ^`  ^`  ^`  ^` 2 00 , 11 22 ll TT uxt Tt mx dx mx ut Nx Nx ut dx t ËÛ  ÌÜ  ÍÝ ÔÔ   ^`   ^` 1 2 Te ut M ut ËÛ ÍÝ  , onde:    ^`  ^` 0 lT e M mx Nx Nx dx ËÛ ÍÝ Ô, é a matriz simétrica de massa para o elemento e (de dimensão  22`) e  mx a massa em x . Da mesma forma, a energia potencial  Vt é:      ^`  ^`  ^`  ^` 2 00 , 11 22 ll TT uxt Vt EAx dx EAxut Nx Nx utdx x ËÛ   ÌÜ  ÍÝ ÔÔ  ^`   ^` 1 2 Te ut K ut ËÛ ÍÝ , onde:    ^`  ^` 0 lT e K EA x N x N x dx ËÛ  ÍÝ Ô, ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 138 é a matriz simétrica de rigidez para o elemento e (de dimensão  22`),  Ax a área da secção em x e  ^`  ^` d N xNx dx  T. Para derivar o vector das forças nodais, utiliza-se a expressão para o trabalho virtual [Bathe, 1996]. Assumindo que o elemento é sujeito à força axial distribuída não conservativa5  , f xt e considerando a equação (5.13) pode-se obter:       ^`  ^`  ^`  ^` 00 ,, , ll TT Wt fxtuxtdx fxt Nx ut dx ft ut  ÔÔ , onde  Wt representa o trabalho virtual,  ,uxt o deslocamento virtual em x ,  ^ ` ut o vector de deslocamentos nodais virtuais e:  ^`   ^` 0 , l f tfxtNxdxÔ, (5.14) é o vector das forças nodais não conservativas. Utilizando para o elemento finito do tipo axial de massa m as funções de forma polinomiais de grau 1:  11 x Nx l  e  2 x Nx l , representadas na Figura 5.4, obtém-se a matriz de massa:  2 2 00 11 11 21 12 6 1 T ll e xxx xx lll ml ll Mm dxm dx xx xx x ll ll l ËÛ ÈØÈØ ÎÞÎÞ  ÌÜ  ÉÙÉÙ ÑÑÑÑ ÊÚÊÚ ËÛ ÑÑÑÑ ÌÜ ËÛ ÏßÏß ÌÜ ÍÝ ÌÜ ÍÝ ÈØ ÈØ ÑÑÑÑ ÌÜ  ÉÙ ÉÙ ÑÑÑÑ ÐàÐà ÊÚ ÊÚ ÌÜ ÍÝ ÔÔ ; isto é, para um elemento finito axial de secção constante, de área A, e de material com densidade 7: 2 () 21 12 6 eAl M7ËÛ ËÛ ÌÜ ÍÝ ÍÝ . 5 Esta consideração sobre a força não é limitativa, pois deve-se notar que forças concentradas podem ser transformadas em forças distribuídas por intermédio da função espacial delta de Dirac; por exemplo, a força   P t concentrada no ponto 3xl pode ser expressa na forma distribuída como   ,3fxt Pt xl/ onde  3xl/ é a função espacial delta de Dirac. MODELOS PONTUAIS E ELEMENTOS FINITOS UTILIZADOS 139  1 Nx 11 x x l l  2 Nx Figura 5.4 – Funções de forma polinomiais de grau um para um elemento finito do tipo axial de comprimento l. Para se determinar a matriz de rigidez do elemento é necessário calcular  ^ ` N xT:  ^`  ^` 11 1 1 x dd l Nx Nx x dx dx l l ÎÞ  ÑÑ  ÎÞ ÑÑ ÏßÏß Ðà ÑÑ ÑÑ Ðà . Deste modo, obtém-se a matriz de rigidez para o elemento de rigidez axial E A constante:  2 0 11 11 11 11 T l eEA EA Kdx ll   ÎÞÎÞ Ë Û ËÛ ÏßÏß ÌÜ ÍÝ  ÍÝ ÐàÐà Ô. Finalmente, para se determinar o vector das forças nodais para uma força distribuída do tipo, por exemplo,  , f xt a bx utiliza-se a equação (5.14) e obtém-se:  ^`  22 2 200 11 126 11 23 ll ab xab x x al bl ll l ft a bx dx dx xab al bl xx lll                                        ÔÔ . 5.2.1.2.1 – Determinação das matrizes no sistema global De acordo com o método dos elementos finitos, o sistema global é composto por elementos discretos que deverão ser agrupados. As componentes dos deslocamentos nos nodos em cada elemento são especificadas segundo as direcções que melhor se adaptam ao mesmo. No caso de um elemento axial com os seus nodos designados por i e j (Figura 5.5) é conveniente especificar as componentes para os deslocamentos em cada um dos nodos de maneira que uma componente ocorra segundo a direcção axial x  e a outra lhe seja ortogonal. As componentes dos deslocamentos nos nodos i e j ao longo destes eixos são designadas na Figura 5.5, respectivamente, por 1 u , 2 u  e 3 u  , 4 u  . ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 140 2 u  i j α 4 u  3 u  1 u  x  y  x y 1 u 2 u 3 u 4 u Figura 5.5 – Sistemas de referência para um elemento axial. Como geralmente os elementos individuais são parte de um sistema mais complexo, e provavelmente têm orientações diferentes, torna-se óbvio que exprimir os deslocamentos num sistema de coordenadas particular a cada elemento – sendo um tal sistema designado por sistema de coordenadas locais – pode criar dificuldades no emparelhamento dos deslocamentos em cada nodo. Por esta razão, torna-se vantajoso trabalhar com as componentes dos deslocamentos num único sistema de coordenadas, enquanto se mantém a vantagem de identificar as componentes dos deslocamentos em cada elemento segundo as direcções que lhe são mais convenientes. Assim, pretende-se escolher um único sistema de referência global  , x y e denotar as componentes dos deslocamentos ao longo destas direcções em i por 1 u e 2 u e em j por 3 u e 4 u. Então, uma simples transformação de coordenadas [Foley, 1991; Hall, 1993] permite exprimir as componentes dos deslocamentos de um elemento particular ao longo do sistema de referência global  , x y a partir das componentes ao longo do seu sistema de coordenadas local  , x y   e vice-versa. Para se obter tal transformação de coordenadas, utiliza-se a matriz > @ tg dos co-senos directores: >@ xx xy y xyy tg tg tg tg tg ËÛ ÌÜ ÍÝ   , onde xx tg representa o co-seno do ângulo entre os eixos x  e x , etc. Esta matriz permite escrever a transformação de coordenadas do sistema global para o local: >@ x x tg yy ÎÞ ÎÞ Ïß Ïß Ðà Ðà  , e a transformação do sistema local para o global: >@ T x x tg yy ÎÞ ÎÞ Ïß Ïß Ðà Ðà  . MODELOS PONTUAIS E ELEMENTOS FINITOS UTILIZADOS 141 A mesma transformação de coordenadas pode ser aplicada às componentes dos deslocamentos, obtendo-se: >@ 11 22 uu tg uu ÎÞ ÎÞ Ïß Ïß Ðà Ðà  , >@ 33 44 uu tg uu ÎÞ ÎÞ Ïß Ïß Ðà Ðà   e >@ 11 22 T uu tg uu ÎÞ ÎÞ Ïß Ïß Ðà Ðà   , >@ 33 44 T uu tg uu ÎÞ ÎÞ Ïß Ïß Ðà Ðà  . Estas equações podem ser combinadas de forma a que a transformação seja aplicada ao elemento como um todo, obtendo-se: ^ ` > @ ^ ` uTgu , (5.15) e ^ ` > @ ^ ` T uTgu , onde ^ ` u  e ^ ` u são os vectores coluna dos deslocamentos nodais com componentes 1 u  , 2 u  , 3 u , 4 u  e 1 u, 2 u, 3 u, 4 u, respectivamente, e a matriz de transformação > @ Tg é definida como: >@ > @ > @ >@ > @ 0 0 tg Tg tg ËÛ ÌÜ ÍÝ . Obviamente, existem diferentes matrizes de transformação > @ Tg para diferentes elementos, a menos que alguns sejam do mesmo tipo e tenham a mesma orientação. Deve ser notado que a matriz > @ Tg é ortonormal e, assim, > @ > @ 1T Tg Tg  , pois > @ tg representa uma transformação entre dois sistemas de eixos ortogonais. No caso da Figura 5.5, sistema plano com z z, a matriz dos co-senos directores é: >@ cos sin sin cos tg ,, ,,  ËÛ ÌÜ ÍÝ . Para transformar as matrizes de rigidez e de massa e o vector de forças nodais do sistema de referência local para o global, e vice-versa, utiliza-se novamente a matriz de transformação geométrica > @ Tg . Para se obter tal transformação, deve-se notar que a energia cinética T e a energia potencial V podem ser reescritas na forma de um produto matricial triplo: ^`  ^` 1 2 Te TuMu ËÛ ÍÝ  e ^`  ^` 1 2 Te VuKu ËÛ ÍÝ, enquanto o trabalho virtual tem a expressão ^ ` ^ ` T Wu f. Mas, se as componentes dos deslocamentos locais e globais estão relacionadas pela equação (5.15), então as componentes locais e globais das velocidades estão relacionadas por ^ ` > @ ^ ` uTgu   e os correspondentes deslocamentos virtuais por: ^ ` > @ ^ ` uTgu . (5.16) ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 142 Assim, utilizando estas relações, pode-se obter: ^` >@  >@ ^` ^`  ^` 11 22 TTTee TuTgMTgu uMu ËÛ ËÛ ÍÝ ÍÝ   , onde  > @  > @ T ee M Tg M Tg ËÛ ËÛ ÍÝ ÍÝ  é a matriz de massa para o elemento referida ao sistema de coordenadas global  , x y. Da mesma forma, pode-se escrever a energia potencial como: ^` >@  >@ ^` ^`  ^` 11 22 TTTee VuTgKTgu uKu ËÛ ËÛ ÍÝ ÍÝ  , onde  > @  > @ T ee K Tg K Tg ËÛ ËÛ ÍÝ ÍÝ  é a matriz de rigidez para o elemento expressa no sistema de coordenadas global  , x y. Note-se que as matrizes  e M ËÛ ÍÝ e  e K ËÛ ÍÝ são simétricas pois  e M ËÛ ÍÝ  e  e K ËÛ ÍÝ  também o são. Finalmente, inserindo a relação da equação (5.16) na expressão do trabalho virtual obtém-se: ^ ` > @ ^ ` ^ ` ^ ` TT T WuTgf u f  , onde ^ ` > @ ^ ` T f Tg f  é o vector das forças nodais no sistema de coordenadas global  , x y. As matrizes de massa e de rigidez e o vector das forças nodais, expressos no sistema de referência global, podem ser utilizadas na escrita das equações do movimento do elemento individual relativamente ao mesmo sistema. Contudo, se o objectivo final for a escrita das equações do movimento do sistema global, é então necessário proceder (ver capítulo anterior) ao agrupamento das matrizes de massa e de rigidez e do vector de forças nodais de cada elemento que constitui tal sistema. 5.2.1.2.2 – Agrupamento A essência do método dos elementos finitos é considerar o sistema global como a soma de elementos individuais. Para esta soma, ou agrupamento, dos elementos individuais representar adequadamente o sistema global deve existir compatibilidade geométrica nos nodos dos elementos; por exemplo, os deslocamentos nos nodos partilhados por vários elementos devem ser iguais para cada um destes. Do mesmo modo, as correspondentes forças nodais devem ser estaticamente equivalentes às forças aplicadas. Deve-se notar que os deslocamentos podem incluir rotações e as forças podem incluir binários. Assumindo que o sistema global consiste em L elementos e que estes são identificados pelo índice e, com 1, 2, ,eL, então, considerando um elemento e, o vector nodal de deslocamentos é designado por  ^ ` e u, o das forças por  ^ ` e f , a matriz de massa por  e M ËÛ ÍÝ e a de rigidez por  e K ËÛ ÍÝ (onde todas as quantidades se referem a este elemento e estão MODELOS PONTUAIS E ELEMENTOS FINITOS UTILIZADOS 143 expressas no sistema de coordenadas global). De seguida, assumindo que o sistema tem um total de N graus de liberdade ( N deslocamentos j u, com 1, 2, ,jN), designa-se o vector dos N deslocamentos nodais no sistema global por ^ ` U. Para ser executado o processo de agrupamento, define-se para o elemento e um vector de deslocamentos nodais expandido  ^ ` exp e U obtido a partir da adição ao vector  ^ ` e u de componentes com valor nulo de forma que a dimensão do vector  ^ ` exp e U seja igual a N. Da mesma maneira se definem o vector das forças nodais expandido  ^ ` exp e F, assim como as matrizes (de dimensão  N N`) de massa  exp e M ËÛ ÍÝ e de rigidez  exp e K ËÛ ÍÝ expandidas. As equações de movimento para o sistema global podem ser obtidas por um processo de agrupamento que consiga exprimir a energia cinética, a energia potencial e o trabalho virtual em termos da contribuição dos elementos individuais utilizados na modelização. Assim, a energia cinética  Tt pode ser escrita com a forma:   ^ `   ^ ` ^`  ^` ^` >@ ^` exp exp exp 11 11 1 22 2 LL TTT eee e ee Tt u M u U M U U M U  ËÛ ËÛ ÍÝ ÍÝ ÇÇ   , onde >@  exp 1 Le e MM  ËÛ ÍÝ Ç, é a matriz simétrica de massa para o sistema global, obtida simplesmente pela adição das matrizes de massa expandidas dos elementos que constituem tal sistema. Da mesma forma, a energia potencial  Vt é escrita como:   ^ `   ^ `  ^ `   ^ `  >@  exp expexp 11 11 1 22 2 LL TT T eee e e e ee Vt u K u U K U U K U  ËÛ ËÛ ÍÝ ÍÝ ÇÇ , onde >@  exp 1 Le e KK  ËÛ ÍÝ Ç é a matriz simétrica de rigidez para o sistema global. Também o trabalho virtual pode ser escrito com a forma:  ^ `  ^ `  ^ `  ^ ` ^` ^` exp exp 11 LL TT T ee e e ee Wfu FU FU    ÇÇ , onde ^`  ^ ` exp 1 Le e FF  Ç é o vector das forças nodais não conservativas para o sistema global. Utilizando as matrizes de massa e de rigidez, o vector das forças nodais não conservativas, e o vector dos deslocamentos nodais do sistema global é possível, desprezando o efeito de amortecimento que eventualmente possa existir, escrever as equações de movimento de ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 144 Lagrange [Bathe, 1996] para o sistema com a seguinte forma matricial: > @ ^ ` > @ ^ ` ^ ` M UKU F  . Considerando o efeito de amortecimento, as equações de movimento de Lagrange são: > @ ^ ` > @ ^ ` > @ ^ ` ^ ` M UCUKU F    , onde > @ C é a matriz de amortecimento e ^ ` U  o vector das velocidades nodais. Esta matriz pode também ser obtida a partir do agrupamento das matrizes de amortecimento dos elementos utilizados na modelização. Contudo, como foi referido no capítulo anterior, geralmente esta matriz é obtida utilizando-se as matrizes de massa e de rigidez do sistema global conjuntamente com resultados experimentais do valor de amortecimento. 5.2.1.2.3 – Exemplos Para se verificar o cálculo e o significado das matrizes de um sistema modelizado por um conjunto de elementos finitos axiais lineares, considere-se novamente os três pontos representados na Figura 5.1 ligados por intermédio de elementos axiais como na Figura 5.6. Figura 5.6 – Três pontos ligados por intermédio de elementos finitos axiais. Considerando-se, por exemplo, que os elementos são de área unitária e construídos por borracha obtiveram-se as seguintes matrizes6: >@ 2033.920000 908.693333 108.266667 0.000000 0.000000 0.000000 908.693333 3400.320000 791.466667 0.000000 0.000000 0.000000 108.266667 791.466667 1799.466667 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 2033.9200 M 00 908.693333 108.266667 0.000000 0.000000 0.000000 908.693333 3400.320000 791.466667 0.000000 0.000000 0.000000 108.266667 791.466667 1799.466667 Ë Û Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Í Ý , 6 Os valores dos elementos destas matrizes foram arredondados para a sexta casa decimal. MODELOS PONTUAIS E ELEMENTOS FINITOS UTILIZADOS 145 >@ 0.000052 -0.000007 -0.000045 0.000036 0.000014 -0.000050 -0.000007 0.000028 -0.000020 0.000014 -0.000033 0.000019 -0.000045 -0.000020 0.000065 -0.000050 0.000019 0.000032 0.000036 0.000014 -0.000050 0.000084 -0.000028 -0. K 000056 0.000014 -0.000033 0.000019 -0.000028 0.000045 -0.000017 -0.000050 0.000019 0.000032 -0.000056 -0.000017 0.000073 ËÛ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÍÝ . Analisando a matriz de rigidez obtida, verifica-se que o sistema resultante apresenta baixa rigidez. Optando-se agora pelo aço como o material a utilizar na construção dos elementos axiais, obtiveram-se as seguintes matrizes de massa e de rigidez: >@ 14146.640000 6320.286667 753.033333 0.000000 0.000000 0.000000 6320.286667 23650.440000 12515.933333 0.000000 0.000000 0.000000 753.033333 5504.933333 1799.466667 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 14 M 146.640000 6320.286667 753.033333 0.000000 0.000000 0.000000 6320.286667 23650.440000 5504.933333 0.000000 0.000000 0.000000 753.033333 5504.933333 12515.933333 Ë Û Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Í Ý , >@ 4.407162 -0.622579 -3.784583 3.051410 1.206246 -4.257656 -0.622579 2.345850 -1.723272 1.206246 -2.785912 1.579666 -3.784583 -1.723272 5.507855 -4.257656 1.579666 2.677990 3.051410 1.206246 -4.257656 7.126964 -2.337102 -4. K 789863 1.206246 -2.785912 1.579666 -2.337102 3.785128 -1.448027 -4.257656 1.579666 2.677990 -4.789863 -1.448027 6.237890 ËÛ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÌÜ ÍÝ . Comparando estas matrizes com as obtidas na experiência anterior verifica-se, como seria de esperar, que os seus elementos aumentaram em valor, traduzindo o aumento da densidade e da rigidez correspondente à passagem de borracha para aço como o material virtual adoptado para os elementos. Considerando-se novamente borracha para o material virtual mas desta vez um valor para a área dos elementos 10 vezes superior, obtiveram-se as seguintes matrizes: >@ 20339.200000 9086.933333 1082.666667 0.000000 0.000000 0.000000 9086.933333 34003.200000 7914.666667 0.000000 0.000000 0.000000 1082.666667 7914.666667 17994.666667 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 M 20339.200000 9086.933333 1082.666667 0.000000 0.000000 0.000000 9086.933333 34003.200000 7914.666667 0.000000 0.000000 0.000000 1082.666667 7914.666667 17994.666667 Ë Û Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Ì Ü Í Ý , ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 252 Tabela 7.12 – Superfícies, resultantes de amostragem adaptativa, a emparelhar ao longo da sequência. (Continuação.) 7 8 9 10 Tabela 7.13 – Algumas propriedades das superfícies, construídas utilizando amostragem adaptativa, a considerar ao longo da sequência. ID Nº Nodos Volume Área C. F. 1 93 80215.0 8106.1 0.9493 2 103 100892.8 8701.4 0.9112 3 117 113451.0 8353.9 0.8586 4 112 57104.9 8210.6 1.0700 5 119 108901.9 7021.5 0.7979 6 120 85956.3 7509.7 0.8929 7 124 73657.1 7603.4 0.9459 8 125 69080.5 8144.2 1.0001 9 123 125919.5 8199.3 0.8215 10 122 93369.7 8788.9 0.9397 Utilizando-se elementos isoparamétricos 3D de Sclaroff construídos por material do tipo borracha, valores para o parâmetro s iguais a 25% da distância média entre todos os modos de cada superfície, e considerando 10% dos modos de vibração, obtiveram-se os emparelhamentos representados nas imagens das Tabela 7.14 e Tabela 7.15. O número e a percentagem de emparelhamentos e o valor da energia de deformação ao longo da sequência estão indicados na Tabela 7.16. A percentagem de emparelhamentos e a energia de deformação ao longo da sequência estão representados de forma gráfica nas Figura 7.16 e Figura 7.17. O número de emparelhamentos obtidos, variando ao longo da sequência entre 27% e 57%, e atendendo que os mesmos não foram obtidos tendo em conta qualquer tipo de optimização, pode ser classificado como satisfatório. A título de exemplo, optando-se no emparelhamento 8 por apenas utilizar os 25 primeiros modos de vibração é possível obter 42 correspondências aceitáveis (Figura 7.18a) a que corresponde uma percentagem de 34.1% superior à obtida ENSAIOS EM IMAGENS DE PEDOBAROGRAFIA DINÂMICA 253 com as condições globais (na Figura 7.18b é possível verificar que a energia necessária para alinhar as duas superfícies concentra-se em grande parte nos primeiros grupos de modos). Tabela 7.14 – Emparelhamentos obtidos entre as superfícies, resultantes de amostragem adaptativa, ao longo da sequência. [Reprodução a cores em anexo.] 1 2 3 4 5 6 7 8 9 Para se analisar a importância dos vários modos de vibração na energia de deformação ao longo da sequência apresenta-se, de forma gráfica, na Figura 7.19 a contribuição dos mesmos modos, agrupados em doze classes, no valor global da referida energia. A título de exemplo, é possível verificar-se na Figura 7.20 a influência da aplicação prévia da transformação rígida na distribuição da energia de deformação ao longo dos modos no quarto emparelhamento: verifica-se uma redução da contribuição dos primeiros grupos de modos. Também com esta experiência se pode concluir que, quando a deformação entre duas superfícies é essencialmente global, a energia se concentra nos primeiros grupos de modos; ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 254 assim que as deformações se tornam mais locais, a energia passa a concentrar-se nos grupos intermédios até ficar, nos casos de deformações semelhantes a ruído localizado, praticamente concentrada nos grupos de modos mais altos. Tabela 7.15 – Outra vista dos emparelhamentos obtidos entre as superfícies, resultantes de amostragem adaptativa, ao longo da sequência. [Reprodução a cores em anexo.] 1 2 3 4 5 6 7 8 9 Em termos de conclusão, pode-se afirmar que se obteve emparelhamentos satisfatórios ao longo da sequência e que geralmente a energia de deformação traduz de forma aceitável a deformação existente. Nesta experiência verificou-se que a energia de deformação e a ENSAIOS EM IMAGENS DE PEDOBAROGRAFIA DINÂMICA 255 variação do factor da forma apresentam comportamentos semelhantes ao longo da sequência o que também indicia que os valores desta energia traduzem satisfatoriamente as deformações existentes. Tabela 7.16 – Número e % de emparelhamentos e valor da energia de deformação ao longo da sequência de superfícies adaptativas. ID Nº Emp. % Emp. Energia 1 33 35.5% 521.6 2 58 56.3% 559.7 3 35 31.3% 1467.1 4 39 34.8% 1874.4 5 33 27.7% 701.3 6 63 52.5% 389.9 7 51 41.1% 421.1 8 33 26.8% 646.3 9 41 33.6% 497.4 % Emparelhamentos 0% 10% 20% 30% 40% 50% 60% 123456789 ID Figura 7.16 – Percentagem de emparelhamentos obtidos ao longo da sequência de superfícies baseadas em amostragem adaptativa. Energia 0 500 1000 1500 2000 123456789 ID Figura 7.17 – Energia de deformação ao longo da sequência de superfícies baseadas em amostragem adaptativa. Distribuição da Energia Emp. 8 I II III IV V X IX VI VII VIII XIXII a) b) Figura 7.18 – Emparelhamento 8 entre superfícies baseadas em amostragem adaptativa: a) Duas vistas das correspondências obtidas utilizando-se os primeiros 25 modos de vibração; b) Distribuição da energia de deformação ao longo dos modos de vibração. [Reprodução a cores em anexo.] A título de exemplo, estão representadas na Figura 7.21 as superfícies 5 e 6 após aplicação à primeira dos deslocamentos estimados por minimização da energia de deformação. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 256 Distribuição da Energia 0 200 400 600 800 1000 1200 1400 1600 1800 123456789 ID III III IV VVI VII VIII IX XXI XII Figura 7.19 – Comparticipação dos modos de vibração na energia de deformação ao longo da sequência de superfícies baseadas em amostragem adaptativa. [Reprodução a cores em anexo.] Distribuição da Energia Emp. 4 I II III IV IX V XXI XII VIII VII VI a) Distribuição da Energia Emp. 4 I II III IV V VI X IX VII VIII XI XII b) Figura 7.20 – Distribuição da energia de deformação por 12 classes de modos, sem (a) e com (b) a prévia aplicação da transformação rígida obtida, para o emparelhamento 4 entre superfícies baseadas em amostragem adaptativa. [Reprodução a cores em anexo.] Figura 7.21 – Emparelhamento 5 após aplicação dos deslocamentos nodais estimados à superfície 5. [Reprodução a cores em anexo.] ENSAIOS EM IMAGENS DE PEDOBAROGRAFIA DINÂMICA 257 7.2.3 – Modelização por contornos isobáricos Neste ponto serão apresentados alguns resultados obtidos considerando-se isocontornos de intensidade. Em primeiro lugar, serão apresentados resultados entre contornos determinados numa mesma imagem da sequência; seguidamente, serão apresentados resultados entre contornos correspondentes ao nível de brilho médio ao longo da sequência. Também com este tipo de modelização se deve notar que, de forma semelhante ao que acontece com a modelização de objectos em imagens de pedobarografia dinâmica por superfícies de intensidade, as áreas de pressão dos dedos do pé podem originar variações severas na topologia dos modelos construídos. Estas variações poderão ser ainda mais importantes nos isocontornos determinados ao longo da sequência. Para se diminuir este efeito, deve-se optar por amostragens suficientemente finas na construção dos modelos. 7.2.3.1 – Contornos de uma mesma imagem Considerando-se a quarta imagem da sequência apresentada na Tabela 7.1, procedeu-se à remoção dos pixels de reduzido brilho, construiu-se uma superfície de intensidade utilizando amostragem regular de dimensões 10 10 5¥¥, realizou-se a triangulação 2D de Delaunay e determinaram-se os onze contornos de isonível a considerar nesta experiência, Figura 7.22. a) b) Figura 7.22 – Determinação dos isocontornos a considerar: a) Superfície de intensidade construída a partir da imagem 4 da sequência; b) Onze contornos isobáricos extraídos a partir da superfície. [Reprodução a cores em anexo.] Na Tabela 7.17 indicam-se algumas propriedades dos isocontornos a considerar para o emparelhamento: o número de pixels, a cota correspondente ao nível de intensidade e a área. Utilizando-se elementos isoparamétricos 3D de Sclaroff construídos por material do tipo borracha, valores para o parâmetro s iguais a 25% da distância média entre todos os pixels de cada contorno, e considerando 10% dos modos de vibração, obtiveram-se os emparelhamentos representados na Figura 7.23. O número e a percentagem de emparelhamentos e o valor da energia de deformação ao ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 258 longo da sequência de isocontornos estão indicados na Tabela 7.17. A percentagem de emparelhamentos e a energia de deformação são analisados, de forma gráfica, nas Figura 7.24 e Figura 7.25. Tabela 7.17 – Algumas propriedades dos isocontornos a considerar. ID Nº de Pixels Cota Área 1 76 9 9206.9 2 76 18 8737.0 3 74 27 8308.0 4 76 40.5 7695.8 5 70 54 7106.0 6 54 71 4539.6 7 46 92 3396.6 8 38 86.9 3195.0 9 34 91.7 2976.5 10 34 96.6 2765.5 11 34 101 2562.1 Figura 7.23 – Duas vistas dos emparelhamentos determinados entre contornos de isonível de uma mesma imagem. [Reprodução a cores em anexo.] Tabela 7.18 – Número e % de emparelhamentos e valor da energia de deformação ao longo dos isocontornos de uma mesma imagem. ID Emp. Emp. (%) Energia 1 52 68.4% 2235.8 2 57 77.0% 2251.9 3 52 70.3% 4703.4 4 40 57.1% 4025.8 5 32 59.3% 6328.9 6 24 52.2% 1878.9 7 22 57.9% 419.3 8 17 50.0% 329.6 9 32 94.1% 317.8 10 17 50.0% 212.9 ENSAIOS EM IMAGENS DE PEDOBAROGRAFIA DINÂMICA 259 % Emparelhamentos 0% 20% 40% 60% 80% 12345678910 ID Figura 7.24 – Percentagem de emparelhamentos obtidos ao longo dos isocontornos de uma mesma imagem. Energia 0 1000 2000 3000 4000 5000 6000 12345678910 ID Figura 7.25 – Energia de deformação obtida ao longo dos isocontornos de uma mesma imagem. O número de emparelhamentos obtidos entre os contornos de isonível de uma mesma imagem original, variando entre 52% e 94%, e atendendo que os mesmos não foram obtidos tendo em conta qualquer tipo de optimização, pode ser classificado como bastante satisfatório. Para, mais uma vez, se proceder à análise da importância dos modos de vibração na energia de deformação apresenta-se, de forma gráfica, na Figura 7.26, para cada emparelhamento a contribuição no valor global da referida energia dos modos agrupados em doze classes. Ao analisar-se a referida figura, verifica-se que, principalmente até ao sexto emparelhamento, as classes primeiras e intermédias assumem uma participação relevante no valor global da energia. Isto evidencia a existência de uma transformação global considerável entre os objectos e que, para se determinar as correspondências de forma aceitável, se deve apenas considerar, a partir do primeiro modo, um reduzido conjunto de modos de vibração. Também com esta experiência é possível concluir que, quando a deformação entre dois contornos é essencialmente global, a energia se concentra nos primeiros grupos de modos e, assim que as deformações se tornam mais locais, a energia passa a concentrar-se nos grupos intermédios até ficar praticamente concentrada nos grupos de modos mais altos, nos casos de deformações do tipo ruído localizado. Na Figura 7.27 estão representados os contornos de isonível considerados nesta experiência após aplicação dos deslocamentos nodais estimados por minimização da energia de deformação. Analisando-se as referidas figuras é possível verificar que os deslocamentos estimados, de modo geral, são bastante razoáveis. Em termos de conclusão pode-se afirmar que se obteve emparelhamentos satisfatórios ao longo dos contornos de isonível de uma mesma imagem original, que a energia de deformação traduz de forma aceitável a deformação existente entre os objectos e que os deslocamentos nodais estimados, por minimização dessa energia, podem ser classificados como bastante satisfatórios. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 260 Distribuição da Energia 0 1000 2000 3000 4000 5000 6000 12345678910 ID XII XI X IX VIII VII VI V IV III II I Figura 7.26 – Comparticipação dos modos de vibração na energia de deformação ao longo do emparelhamento dos isocontornos de uma mesma imagem. [Reprodução a cores em anexo.] Figura 7.27 – Duas vistas dos deslocamentos estimados para os contornos de isonível de uma mesma imagem. [Reprodução a cores em anexo.] 7.2.3.2 – Contornos de diferentes imagens Considerando as imagens representadas na Tabela 7.1 da sequência exemplo, para se determinar os contornos de nível de brilho médio ao longo da sequência a utilizar nesta experiência, e visíveis na Figura 7.28, procedeu-se ao seguinte conjunto de operações: 1. remoção dos pixels de reduzido nível de brilho presentes em cada imagem original; 2. aplicação de um filtro Gaussiano, de dimensões 99¥, de forma a suavizar cada imagem filtrada; ENSAIOS EM IMAGENS DE PEDOBAROGRAFIA DINÂMICA 261 3. para cada imagem suavizada construiu-se a respectiva superfície de intensidade, utilizando-se uma amostragem regular de dimensões 10 10 5¥¥, e uma triangulação 2D de Delaunay; 4. em cada superfície de intensidade construída determinou-se o contorno de nível médio de brilho. Na Tabela 7.19 são indicadas algumas propriedades dos isocontornos determinados ao longo da sequência: o número de pixels, a cota e a área. Figura 7.28 – Duas vistas dos dez isocontornos a considerar ao longo da sequência exemplo. [Reprodução a cores em anexo.] Tabela 7.19 – Algumas propriedades dos isocontornos a considerar ao longo da sequência. ID Nº de Pixels Cota Área 1 58 35 6626.7 2 53 35 6920.5 3 62 37.5 6183.2 4 61 35 6920.1 5 37 35 3214.3 6 46 37.5 4226.2 7 42 35 3880.8 8 52 37.5 4079.1 9 47 40 4197.8 10 46 40 4477.9 Utilizando-se elementos isoparamétricos 3D de Sclaroff construídos por material do tipo borracha, valores para o parâmetro s iguais a 25% da distância média entre todos os pixels de cada contorno, e considerando 10% dos modos de vibração, obtiveram-se os emparelhamentos representados nas imagens da Tabela 7.20. O número e a percentagem de emparelhamentos e o valor da energia de deformação ao longo dos contornos de isonível da sequência estão indicados na Tabela 7.21. A percentagem de emparelhamentos obtida ao longo da sequência, variando entre 19% e 68%, e atendendo que os mesmos não foram obtidos tendo em conta qualquer tipo de optimização e à considerável diferença existente entre as imagens da sequência, pode ser classificada como satisfatória. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 270 possível aos seus utilizadores disporem num só sistema de um elevado número de entidades e de ferramentas; a segunda característica que a plataforma apresenta é a facilidade com que as funções incorporadas podem ser parametrizadas e controladas e com que os resultados obtidos podem ser analisados e visualizados, conseguindo-se assim realizar ensaios exaustivos dos métodos envolvidos. A filosofia utilizada na estrutura e implementação da plataforma permite que esta seja facilmente configurada e adaptada a níveis diferentes de utilizadores e de aplicação, e que a sua manutenção não seja demasiado complexa. Actualmente, a aplicação já incorporou contribuições de vários outros investigadores do grupo e serviu de plataforma de desenvolvimento e ensaio a vários alunos de licenciatura e mestrado da Faculdade de Engenharia da Universidade do Porto. Comprovou-se que a integração de novas funções é fácil e expedita, o que torna mais rápida a adaptação de novos investigadores. O sistema desenvolvido também tem sido utilizado como aplicação de demonstração em cursos de processamento e análise de imagem, revelando-se uma aplicação com valor na aprendizagem. Actualmente a plataforma já integra um número elevado de funções para um sistema de processamento e análise de imagem, estando ainda em aberto a construção de um sistema de ajuda que auxilie os seus utilizadores na incorporação dos seus algoritmos e na utilização das funções disponíveis. A determinação da transformação geométrica rígida existente entre dois objectos, 2D ou 3D, cujos pontos tenham sido previamente emparelhados é conseguida pela utilização de uma metodologia, baseada em minimização por mínimos quadrados do erro da transformação determinada, que utiliza quaternions unitários para representar a rotação envolvida. Os resultados obtidos permitem concluir que é possível obter-se boas estimativas para a transformação geométrica existente sem a necessidade de considerar um elevado número de correspondências, e assim distinguir-se as transformações globais do tipo rígido das deformações essencialmente localizadas. A primeira metodologia implementada para determinar a correspondência entre dois objectos utiliza a análise dos valores e vectores próprios de uma matriz, construída considerando a distância entre os dados pontuais de cada objecto, e estabelecendo as correspondências segundo o princípio da distância mínima. Apesar de a metodologia ser bastante atraente do ponto de vista de implementação, pela sua simplicidade, os resultados obtidos para objectos reais só são satisfatórios quando existir uma grande semelhança no posicionamento, na orientação e nas formas dos objectos em questão. A inadequação da metodologia referida para objectos relativamente diferentes na forma, posicionamento ou orientação, deve-se ao facto de não ser considerada a estrutura de cada objecto na modelização utilizada. Tal facto originou o desenvolvimento de um novo método que utiliza informação estrutural e estabelece as correspondências através da análise dos CONCLUSÕES FINAIS E PERSPECTIVAS DE DESENVOLVIMENTO FUTURO 271 vectores próprios de forma dos dois objectos a emparelhar. Os resultados experimentais obtidos comprovam a melhor adaptação deste novo método para objectos reais e confirmam tratar-se de um método bastante interessante para a determinação das correspondências entre objectos 2D ou 3D, rígidos ou não. Apesar dos bons resultados obtidos pelo novo método, por vezes verificava-se que os mesmos não eram consistentes com o comportamento físico esperado, se os objectos correspondessem a entidades físicas reais, o que se deve à natureza puramente geométrica do método. A simulação do comportamento dos objectos reais segundo princípios físicos foi conseguida através de uma modelização física por intermédio do método dos elementos finitos. Após a construção dos modelos para os objectos a emparelhar, as correspondências são determinadas por análise das trajectórias de cada nodo no respectivo espaço modal. Para se estimar os deslocamentos dos nodos não emparelhados, utiliza-se a minimização da energia de deformação necessária para alinhar o primeiro objecto com o segundo. Esta energia constitui uma medida da deformação necessária para se alinhar dois objectos e permite a sua compararão. A vantagem deste método está relacionada com a consideração de um material virtual na construção dos objectos a emparelhar, conseguindo-se deste modo uma modelização física para os mesmos e fazendo com que as correspondências sejam determinadas, não por um processo “estatístico” sem grande ligação ao comportamento físico esperado para os objectos mas, pelo contrário, de acordo com as características elásticas do material adoptado. Nas modelizações físicas consideradas para cada objecto foram utilizados um único elemento finito isoparamétrico de Sclaroff, no qual são empregues funções de interpolação de base Gaussiana, e conjuntos de elementos finitos axiais standard devidamente agrupados. Enquanto que nas modelizações por intermédio do elemento finito de Sclaroff os nodos são totalmente envolvidos por uma película elástica, obtendo-se modelos com o seu interior totalmente preenchido pelo material virtual, nas modelizações por intermédio de elementos finitos axiais agrupados os modelos resultantes apenas são constituídos por lados (os elementos elásticos dimensionais), obtendo-se assim modelos “ocos” mais simples. Neste segundo caso, os modelos obtidos são geralmente mais flexíveis e menos densos. A modelização física por intermédio de elementos finitos axiais standard agrupados é capaz de produzir bons resultados quando os objectos a emparelhar são rígidos ou quando a deformação existente é reduzida; no entanto, nas situações em que tal não se verifica e desde que os emparelhamentos sejam determinados por um outro processo, continuam a ser úteis na estimação dos deslocamentos e na quantificação da deformação existente; a modelização por intermédio do elemento finito isoparamétrico é mais adaptável, de utilização mais genérica e geralmente produz bons resultados. Há indícios claros de que a inadequação da modelização por intermédio de elementos finitos axiais lineares, no caso das deformações não rígidas serem elevadas, se deve à ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 272 facilidade com que os mesmos entram em instabilidade; tal efeito pode ser atenuado ou evitado aumentando a rigidez do sistema global, através da utilização de ligações suplementares entre os nodos. Ao longo dos ensaios efectuados verificou-se que as propriedades densidade e módulo de elasticidade do material virtual praticamente não influenciavam as correspondências obtidas; no entanto, o coeficiente de Poisson já as influenciava por alterar a resistência dos modelos ao corte. O valor da energia de deformação e os deslocamentos nodais, estimados por minimização desta energia, são influenciados pelos valores adoptados para todas estas propriedades do material virtual, sendo o módulo de elasticidade a propriedade que apresenta uma influência preponderante. As várias experiências desenvolvidas permitem concluir que a abordagem baseada em modelização física produz bons resultados de emparelhamento, que os deslocamentos estimados por minimização da energia de deformação geralmente são de boa qualidade e congruentes com as propriedades adoptadas para o material virtual, e que a energia de deformação quantifica de forma aceitável a transformação existente entre os dois objectos a emparelhar. A contribuição dos modos de vibração no valor global dessa energia é função da deformação existente: se a deformação for essencialmente global, os primeiros modos assumem um maior relevo; se as deformações forem mais locais, os modos intermédios e mais elevados assumem então um maior protagonismo no valor global da energia. A modelização das entidades presentes em cada imagem através de uma superfície de intensidade permite ultrapassar situações bastante comuns em visão por computador, nas quais as imagens 2D de objectos reais são constituídas por várias entidades que, ao longo do seu movimento, se vão agrupando e/ou dividindo, sem que isso corresponda a uma variação real da sua topologia. Assim, desde que o nível de brilho esteja relacionado com alguma característica do objecto a modelizar, a modelização por superfície de intensidade torna possível considerar um único modelo do tipo “casca” em cada imagem e resolver em simultâneo os dois problemas referidos. As superfícies de intensidade foram construídas a partir das imagens originais de duas maneiras distintas: uma na qual é utilizada uma amostragem rectangular e regular, e uma outra em que é utilizada uma amostragem adaptativa, baseada na análise dos perfis radiais de intensidade centrados nos máximos locais presentes na imagem. Enquanto a amostragem rectangular e regular pode originar superfícies em que existam zonas com excessivo e/ou com reduzido número de nodos, a amostragem adaptativa origina superfícies com uma distribuição dos nodos que é função das características das zonas presentes na imagem original, obtendose assim modelos mais adequados aos objectos existentes. Para se construir os modelos de superfície de intensidade, algumas ferramentas comuns no âmbito da computação gráfica tornaram-se necessárias: triangulação de pontos não estruturados, suavização e simplificação de malhas, etc. Tal foi conseguido pela integração na plataforma de desenvolvimento e ensaio da biblioteca de domínio público VTK – The CONCLUSÕES FINAIS E PERSPECTIVAS DE DESENVOLVIMENTO FUTURO 273 Visualization Toolkit [Schroeder, 1996, 1998, 1999]. Esta integração permitiu que várias das entidades e algumas das ferramentas comuns na área da computação gráfica ficassem disponíveis, de forma transparente e em perfeita simbiose, num sistema típico de processamento e análise de imagem. A título de exemplo, a metodologia física e os modelos implementados foram aplicados em imagens de pedobarografia dinâmica. Os primeiros objectos considerados foram do tipo contorno e, apesar dos bons resultados obtidos, comprovou-se o interesse dos modelos de superfície pois existiam imagens constituídas por mais do que um contorno e que ao longo da sequência se dividiam e/ou se agrupavam. Como nesta aplicação existe uma forte relação entre a intensidade de cada pixel e o valor de pressão exercida sobre o sistema sensor, foram utilizados modelos de superfície de intensidade e obtiveram-se bons resultados para o emparelhamento, para a estimação dos deslocamentos nodais por minimização da energia de deformação, e para a quantificação da deformação existente entre os objectos através dessa energia. Acresce ainda que a modelização por contornos não permite obter informação sobre as zonas de hiperpressão e sobre os gradientes espaciais e temporais de pressão. Como em pedobarografia dinâmica, assim como em outras aplicações existentes em visão por computador, tem especial interesse analisar a deformação existente entre contornos de isonível, foram também integradas na plataforma de desenvolvimento e ensaio funções que possibilitam a determinação de tais entidades; as metodologias implementadas para determinar a correspondência, estimar os deslocamentos nodais e determinar a energia de deformação foram alargadas a este tipo de objectos. Para não serem necessários tempos computacionais muito elevados, a amostragem espacial utilizada nos ensaios realizados em imagens de pedobarografia dinâmica foi algo grosseira. A amostragem a utilizar poderá ser mais fina, facilitando a obtenção de resultados mais satisfatórios, principalmente nos casos dos isocontornos; no entanto, os tempos de computação exigidos serão bastante elevados, o que sugere uma implementação paralela da metodologia adoptada. Será possível obter-se resultados de qualidade consideravelmente superior em sequências de imagens de pedobarografia dinâmica obtidas quando se utilizar uma amostragem temporal mais fina. Aquando da aplicação da abordagem utilizada para modelizar objectos 2D, procedeu-se à experiência de também incluir na sua modelização pontos do seu interior; contudo, não se verificaram grandes diferenças nos resultados obtidos relativamente aos determinados utilizando-se unicamente os pontos que constituem os seus contornos. Tal verificação confirma que a modelização de objectos 2D pelos seus contornos é uma boa solução. A aplicação da abordagem física e dos modelos desenvolvidos em imagens de pedobarografia dinâmica permitiu obter bons resultados e verificar a utilidade e adequação dos modelos de superfície de intensidade para problemas reais. Pensa-se que idênticos ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 274 benefícios poderão também ser verificados em muitos outros problemas similares. 8.2 – Perspectivas de desenvolvimento futuro Apesar do trabalho desenvolvido já possibilitar a obtenção de resultados experimentais bastante satisfatórios e promissores, ele pode ser enriquecido, complementado e melhorado, nomeadamente nas seguintes etapas: • Na modelização: a) Nas modelizações baseadas em distâncias Gaussianas ponderadas, verificou-se que a utilização de curvas Gaussianas de largura constante pode não ser adequada nos casos em que a densidade não é uniforme ou quando os dados a modelizar pertencem a entidades distintas. Nestes casos, será interessante utilizar-se curvas cuja largura é determinada localmente, de forma a obter-se uma melhor modelização. b) Visto que actualmente já estão disponíveis na plataforma de desenvolvimento e ensaio ferramentas que permitem a construção de elementos finitos standard mais complexos, deve-se realizar um estudo da sua utilização na modelização física. c) Como por vezes a deformação existente entre dois objectos é acentuada, os resultados obtidos pelo método dos elementos finitos clássicos, utilizando a teoria da elasticidade linear, não são satisfatórios. Nestes casos poderão ser utilizados elementos finitos não lineares. d) As propriedades elásticas do material deverão ser determinadas de forma a que o modelo se deforme segundo o esperado. Assim, caso seja possível, as propriedades do material deverão ser incluídas na modelização e estimadas a partir do comportamento verificado para o modelo ao longo do seu movimento. • Na determinação da correspondência: a) Na fase de determinação das correspondências deverá ser considerada informação sobre a vizinhança; por exemplo, os nodos vizinhos deverão permanecer vizinhos na imagem seguinte, a correspondência determinada não deverá implicar uma dobragem do modelo sobre si mesmo, a ordem dos nodos não deverá ser alterada em demasia ao longo da sequência, etc. b) Na pesquisa das correspondências na matriz de correlação, determinada utilizando a distância euclidiana entre os modos de vibração que constituem cada modelo a emparelhar, deverá ser maximizada a correspondência obtida em termos globais e não locais. Isto é, deverá ser encontrada a solução cujas CONCLUSÕES FINAIS E PERSPECTIVAS DE DESENVOLVIMENTO FUTURO 275 correspondências conduzem à melhor solução para todos os nodos, e não à melhor correspondência para cada um. c) Existem muitas situações em que a correspondência do tipo “um para um” não deverá ser imposta. Assim, na fase da determinação da correspondência, deverão ser permitidos emparelhamentos entre vários nodos e um único nodo e vice-versa. d) Ao longo dos testes efectuados verificou-se que, consoante o conjunto dos modos de vibração considerado, se obtinham emparelhamentos variáveis. A situação de melhor compromisso passou por considerar apenas uma percentagem dos primeiros modos; tal poderá ser complementado através de uma combinação ponderada de vários conjuntos de modos de vibração. Os pesos a considerar deverão reflectir a importância dos vários conjuntos em cada situação. e) Em sequências de imagem, antes de se proceder à modelização de cada objecto a emparelhar, poderá realizar-se um alinhamento rígido. Os parâmetros a utilizar em tal alinhamento poderão ser estimados, de forma recursiva ao longo da sequência, por filtragem de Kalman. • Na aplicação em pedobarografia dinâmica: Na aplicação da abordagem física e dos modelos utilizados em pedobarografia dinâmica, verificou-se que as imagens a considerar estavam bastante separadas no tempo, o que implicava objectos bastante distintos. Se as imagens a considerar forem adquiridas utilizando uma amostragem temporal mais rápida, os resultados obtidos serão de qualidade bastante superior. Evidentemente que a exploração dos resultados, de forma a produzir informação clinicamente relevante, não sendo do âmbito deste trabalho, constitui outro vector de desenvolvimento. • Nos resultados obtidos: a) Utilizando modelização física por intermédio do método dos elementos finitos torna-se extremamente fácil o cálculo das tensões instaladas e das deformações existentes ao longo do modelo. Tal informação pode ser bastante útil em várias aplicações; por exemplo, na avaliação dos esforços a que o modelo está sujeito. b) Além da energia global de deformação pode ser interessante, em várias aplicações, determinar a energia de deformação local e a sua variação. Assim poderia ser calculada a energia de deformação necessária para cada conjunto restrito de nodos emparelharem, por exemplo utilizando-se elementos finitos axiais, e visualizar essa energia ao longo do modelo. ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 276 c) Nas aplicações em que existam conjuntos de dados disponíveis para treino, a análise das componentes principais das deformações poderá ser bastante útil para validar os resultados obtidos, para limitar as deformações admissíveis, para comparar, classificar e reconhecer objectos, etc. d) A abordagem física e os modelos utilizados deverão ser aplicados e analisados em outros tipos de imagem; por exemplo em imagens de faces, do pulmão, do coração, etc. Actualmente está em fase inicial a aplicação da metodologia desenvolvida em imagens renais de medicina nuclear. • Na plataforma de desenvolvimento e ensaio: a) Qualquer aplicação informática necessita de um razoável período de validação; a plataforma criada encontra-se nessa fase. Um grande número de utilizadores tem contribuído para este processo. b) O sistema de ajuda para as funções disponíveis na plataforma ainda não está concluído. Tal sistema é indispensável a qualquer plataforma que pretenda ser de utilização genérica e disponível a diferentes tipos de utilizadores, como é o caso. c) Parte das funções actualmente disponíveis na plataforma apresenta elevados custos de processamento. Seria desejável e de grande utilidade a paralelização de algumas destas funções. Bastante trabalho já foi realizado nessa área, nomeadamente na paralelização, utilizando o Windows PVM - Parallel Virtual Machine, do método utilizado para determinação da correspondência entre dois objectos através da análise modal da forma [Barbosa, 2000, 2000a], dos algoritmos de contornos activos [Barbosa, 1996] e de detecção de orlas de intensidade com o algoritmo de Shen & Castan e de construção do histograma [Barbosa, 1998]. 277 Bibliografia BIBLIOGRAFIA 279 [ [[ [Acharya, 1998] ]] ] – Raj Acharya, Richard Wasserman, Jeffrey Stevens, Carlos Hinojosa BIOMEDICAL IMAGING MODALITIES: AN OVERVIEW DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 [ [[ [Amini, 1991] ]] ] – Amir A. Amini, James S. Duncan POINTWISE TRACKING OF LEFT-VENTRICULAR MOTION IN 3D DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 (1991) [ [[ [Åström, 1999] ]] ] – Kalle Åström, Fredrik Kahl MOTION ESTIMATION IN IMAGE SEQUENCES USING THE DEFORMATION OF APPARENT CONTOURS IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 21, Nº 2 – FEBRUARY 1999 [ [[ [Bainville, 1995] ]] ] – E. Bainville, G. Champleboux, P. Cinquin, V. Dessenne, A. Hamadeh, J. Troccaz, S. Lavallée, O. Péria, P. Sautot, R. Seliski ANATOMICAL SURFACES BASED 3D/3D AND 3D/2D REGISTRATION FOR COMPUTER ASSISTED MEDICAL INTERVENTIONS MEDICAL IMAGING - ANALYSIS OF MULTIMODALITY 2D/3D IMAGES, IOS PRESS – 1995 [ [[ [Bajcsy, 1989] ]] ] – Ruzena Bajcsy, Stane Kovačič MULTIRESOLUTION ELASTIC MATCHING DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 (1989) [ [[ [Barbosa, 1996] ]] ] – Jorge G. Barbosa, João Manuel Tavares, A. Jorge Padilha PARALELLISATION OF ACTIVE CONTOURS RECPAD’96 – 8TH PORTUGUESE CONFERENCE ON PATTERN RECOGNITION GUIMARÃES, PORTUGAL – 21/22 DE MARÇO DE 1996 [ [[ [Barbosa, 1998] ]] ] – Jorge Barbosa, Armando Padilha ALGORITHM-DEPENDANT METHOD TO DETERMINE THE OPTIMAL NUMBER OF COMPUTERS IN PARALLEL VIRTUAL MACHINES VECTOR AND PARALLEL PROCESSING – VECPAR’98, THIRD INTERNATIONAL CONFERENCE PORTO, PORTUGAL – JUNE 1998 [ [[ [Barbosa, 2000] ]] ] – Jorge G. Barbosa, João Manuel Tavares, A. Jorge Padilha PARALLEL IMAGE PROCESSING SYSTEM ON A CLUSTER OF PERSONAL COMPUTERS VECPAR 2000 – 4TH INTERNATIONAL MEETING ON VECTOR AND PARALLEL PROCESSING FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO, PORTO, PORTUGAL – 21/23 DE JUNHO DE 2000 [ [[ [Barbosa, 2000a] ]] ] – Jorge G. Barbosa, João Manuel Tavares, A. Jorge Padilha LINEAR ALGEBRA ALGORITHMS IN A HETEROGENEOUS CLUSTER OF PERSONAL COMPUTERS HCW 2000 – 9TH HETEROGENEOUS COMPUTING WORKSHOP, CANCUN, MEXICO – 2000 [ [[ [Bardinet, 1994] ]] ] – Eric Bardinet, Laurent D. Cohen, Nicholas Ayache FITTING 3-D DATA USING SUPERQUADRICS AND FREE-FORM DEFORMATIONS IEEE 1051-4651/94, PP. 79/83 – 1994 ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 280 [ [[ [Bardinet, 1995] ]] ] – Eric Bardinet, Laurent D. Cohen, Nicholas Ayache TRACKING MEDICAL 3D DATA WITH A PARAMETRIC DEFORMABLE MODEL IEEE INTERNATIONAL SYMPOSIUM ON COMPUTER VISION, FLORIDA, PP. 299/304 – 1995 [ [[ [Bardinet, 1996] ]] ] – Eric Bardinet, Laurent D. Cohen, Nicholas Ayache TRACKING AND MOTION ANALYSIS OF THE LEFT VENTRICLE WITH DEFORMABLE SUPERQUADRICS MEDICAL IMAGE ANALYSIS, VOLUME 1, NUMBER 2, PP. 129/149, OXFORD UNIVERSITY PRESS – 1996 [ [[ [Bascle, 1992] ]] ] – B. Bascle, R. Deriche FEATURES EXTRACTION USING PARAMETRIC SNAKES IEEE 11TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION, NETHERLANDS – 1992 [ [[ [Bascle, 1994] ]] ] – Benedicte Bascle, Patrick Bouthemy, Rachild Deriche, Francois Meyer SUIVI DE PRIMITIVES COMPLEXES SUR UNE SEQUENCES D’IMAGES INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATION, RAPPORT DE RECHERCHE Nº 2468 – DECEMBRE 1994 [ [[ [Bathe, 1996] ]] ] – Klaus-Jürgen Bathe FINITE ELEMENT PROCEDURES PRENTICE HALL – 1996 [ [[ [Baumberg, 1993] ]] ] – A. M. Baumberg, D. C. Hogg LEARNING FLEXIBLE MODELS FROM IMAGE SEQUENCES UNIVERSITY OF LEEDS, SCHOOLS OF COMPUTER STUDIES, REPORT Nº 93.36 – OCTOBER 1993 [ [[ [Baumberg, 1994] ]] ] – A. M. Baumberg, D. C. Hogg AN EFFICIENT METHOD FOR CONTOUR TRACKING USING ACTIVE SHAPE MODELS UNIVERSITY OF LEEDS, SCHOOLS OF COMPUTER STUDIES, REPORT Nº 94.11 – APRIL 1994 [ [[ [Baumberg, 1994a] ]] ] – Adam Baumberg, David Hogg AN ADAPTIVE EIGENSHAPE MODEL BRITISH MACHINE VISION CONFERENCE – 1994 [ [[ [Beer, 1981] ]] ] – Ferdinand P. Beer, E. Russell Johnston, Jr. MECÂNICA VETORIAL PARA ENGENHEIROS, VOLUME II, DINÂMICA MCGRAW-HILL – 1981 [ [[ [Belhumeur, 1997] ]] ] – Peter N. Belhumeur, João P. Hespanha, David J. Kriegman EIGENFACES VS FISHERFACES: RECOGNITION USING CLASS SPECIFIC LINEAR PROJECTION IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, Nº 7 – JULY 1997 [ [[ [Benayoun, 1994] ]] ] – Serge Benayoun, Nicholas Ayache, Isaac Cohen ADAPTIVE MESHES AND NONRIGID MOTION COMPUTATION IEEE - 1051-4651/94 – MAI 1994 BIBLIOGRAFIA 287 [ [[ [Henricsson, 1994] ]] ] – Olof Henricsson, Walter Neuenschwander CONTROLLING GROWING SNAKES BY USING KEY–POINTS IEEE 1051–4651/94 – 1994 [ [[ [Herlin, 1992] ]] ] – Isabelle L. Herlin, Nicholas Ayache FEATURES EXTRACTION AND ANALYSIS METHODS FOR SEQUENCES OF ULTRASOUND IMAGES DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 (1992) [ [[ [Hill, 1994] ]] ] – A. Hill, C. J. Taylor AUTOMATIC LANDMARK GENERATION FOR POINT DISTRIBUTION MODELS DEPARTMENT OF MEDICAL BIOPHYSICS, UNIVERSITY OF MANCHESTER – 1994 [ [[ [Horn, 1987] ]] ] – Berthold K. P. Horn CLOSED-FORM SOLUTION OF ABSOLUTE ORIENTATION USING UNIT QUATERNIONS JOURNAL OF THE OPTICAL SOCIETY OF AMERICA A, VOL. 4, 629/642 – APRIL 1987 [ [[ [Jain, 1996] ]] ] – Anil K. Jain, Yu Zhong, Sridhar Lakshmanan OBJECT MATCHING USING DEFORMABLE TEMPLATES IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 18, Nº 3 – MARCH 1996 [ [[ [Jain, 1997] ]] ] – Anil K. Jain, Douglas Zongker REPRESENTING AND RECOGNITION OF HANDWRITTEN DIGITS USING DEFORMABLE TEMPLATES IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, Nº 12 – DECEMBER 1997 [ [[ [Jones, 1999] ]] ] – Grinnell Jones, Bir Bhanu RECOGNITION OF ARTICULATED AND OCCLUDED OBJECTS IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 21, Nº 7 – JULY 1999 [ [[ [Kakadiaris, 1994] ]] ] – Ioannis A. Kakadiaris, Dimitri Metaxas, Ruzena Bajcsy ACTIVE PART-DECOMPOSITION, SHAPE AND MOTION ESTIMATION OF ARTICULATED OBJECTS: A PHYSICS-BASED APPROACH IEEE COMPUTER VISION AND PATTERN RECOGNITION CONFERENCE, PP. 980/984, SEATTLE, WASHINGTON – JUNE 1994 [ [[ [Kakadiaris, 1995] ]] ] – Ioannis A. Kakadiaris, Dimitri Metaxas 3D HUMAN BODY MODEL ACQUISITION FROM MULTIPLE VIEWS FIFTH INTERNATIONAL CONFERENCE ON COMPUTER VISION, PP. 618/623, BOSTON, MA – 20/23 JUNE 1995 [ [[ [Kakadiaris, 1996] ]] ] – Ioannis A. Kakadiaris, Dimitri Metaxas, Ruzena Bajcsy INFERRING 2D OBJECT STRUCTURE FROM THE DEFORMATION OF APPARENT CONTOURS TO APPEAR IN THE SPECIAL ISSUE OF COMPUTER VISION AND IMAGE UNDERSTANDING ON PHYSICS-BASE MODELING AND REASONING IN COMPUTER VISION – 1996 ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 288 [ [[ [Kambhamettu, 1994] ]] ] – Chandra Kambhamettu, Dmitry B. Goldgof CURVATURE-BASED APPROACH TO POINT CORRESPONDENCE RECOVERY IN CONFORMAL NONRIGID MOTION DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 (1994) [ [[ [Kambhamettu, 1998] ]] ] – Chandra Kambhamettu, Dmitry B. Goldgof, Demetri Terzopoulos, Thomas S. Huang NONRIGID MOTION ANALYSIS DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 [ [[ [Kapur, 1996] ]] ] – Tina Kapur, W. Eric L. Grimson, William M. Wells III, Ron Kikinis SEGMENTATION OF BRAIN TISSUE FROM MAGNETIC RESONANCE IMAGES MEDICAL IMAGE ANALYSIS, VOLUME 1, Nº 2, PP. 109/127, OXFORD UNIVERSITY PRESS – 1996 [ [[ [Kass, 1988] ]] ] – Michael Kass, Andrew Witkin, Demetri Terzopoulos SNAKES: ACTIVE CONTOUR MODELS INTERNATIONAL JOURNAL OF COMPUTER VISION, PP. 321/331 – 1988 DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 (1988) [ [[ [Keeve, 1996] ]] ] – Erwin Keeve, Sabine Girod, Bernd Girod CRANIOFACIAL SURGERY SIMULATION VBC'96 – VISUALIZATION IN BIOMEDICAL COMPUTING, 4TH INTERNATIONAL CONFERENCE, HAMBURG, GERMANY, SPRINGER – SEPTEMBER 1996 [ [[ [Kelemen, 1996] ]] ] – A. Kelemen, G. Székely, H-W. Reist, G. Gerig AUTOMATIC SEGMENTATION OF CELL NUCLEI FROM CONFOCAL LASER SCANNING MICROSCOPY IMAGES VBC'96 – VISUALIZATION IN BIOMEDICAL COMPUTING, 4TH INTERNATIONAL CONFERENCE, HAMBURG, GERMANY, SPRINGER – SEPTEMBER 1996 [ [[ [Kelly, 1993] ]] ] – S. Graham Kelly FUNDAMENTALS OF MECHANICAL VIBRATIONS MCGRAW-HILL – 1993 [ [[ [Kita, 1996] ]] ] – Yasuyo Kita ELASTIC-MODEL DRIVEN ANALYSIS OF SEVERAL VIEWS OF A DEFORMABLE CYLINDRICAL OBJECT IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 18, Nº 12 – DECEMBER 1996 [ [[ [Kittler, 1986] ]] ] – Josef Kittler, John Illingworth MINIMUM ERROR THRESHOLDING PATTERN RECOGNITION, VOL 19, PP. 41/47 – 1986 [ [[ [Kopec, 1997] ]] ] – Gary E. Kopec, Mauricio Lomelin SUPERVISED TEMPLATE ESTIMATION FOR DOCUMENT IMAGE DECODING IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, Nº 12 – DECEMBER 1997 BIBLIOGRAFIA 289 [ [[ [Kumar, 1994] ]] ] – Senthil Kumar, Dmitry Goldgof AUTOMATIC TRACKING OF SPAMM GRID AND THE ESTIMATION OF DEFORMATION PARAMETERS FROM CARDIAC MR IMAGES DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 (1994) [ [[ [Kumar, 1995] ]] ] – Senthil Kumar, Maha Sallam, Dmitry Goldgof, Kevin Bowyer POINT CORRESPONDENCE IN UNSTRUCTURED NONRIGID MOTION IEEE INTERNATIONAL SYMPOSIUM ON COMPUTER VISION, FLORIDA, PP. 289/298 – 1995 [ [[ [Lai, 1994] ]] ] – Kok F. Lai, Roland T. Chin ON CLASSIFYING DEFORMABLE CONTOURS USING THE GENERALIZED ACTIVE CONTOUR MODEL MASSACHUSETTS INSTITUTE OF TECHNOLOGY, MEDIA LABORATORY, 1994 [ [[ [Lai, 1994a] ]] ] – Kok F. Lai PHD THESIS: DEFORMABLE CONTOURS: MODELING, EXTRACTION, DETECTION AND CLASSIFICATION UNIVERSITY OF WISCONSIN-MADISON – 1994 [ [[ [Lane, 1996] ]] ] – Thomas G. Lane JPEG LIBRARY – 1996 [ [[ [Lanitis, 1995] ]] ] – A. Lanitis, T. F. Cootes, C. J. Taylor A UNIFIED APPROACH TO CODING AND INTERPRETING FACE IMAGES DEPARTMENT OF MEDICAL BIOPHYSICS, UNIVERSITY OF MANCHESTER – 1995 [ [[ [Lim, 1990] ]] ] – Jae S. Lim TWO–DIMENSIONAL SIGNAL AND IMAGE PROCESSING PTR PRENTICE HALL – 1990 [ [[ [Lima, 1995] ]] ] – Rui Lima DISSERTAÇÃO DE MESTRADO: PROCESSAMENTO DE IMAGEM NA ANALISE DE DOCUMENTOS DE ENGENHARIA FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO – 1995 [ [[ [L∅ ∅∅ ∅nnestad, 1992] ]] ] – Tor L ∅ nnestad, Otto Milvang XITE: X–BASED IMAGE PROCESSING TOOLS AND ENVIRONMENT USER'S MANUAL – OCTOBER 21, 1992 [ [[ [Malandain, 1993] ]] ] – Grégoire Malandain, Jean-Marie Rocchisani MATCHING OF 3D MEDICAL IMAGES WITH A POTENTIAL BASED METHOD INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATION, RAPPORT DE RECHERCHE Nº 1890 – MARS 1993 [ [[ [Malandain, 1995] ]] ] – Grégoire Malandain, Sara Fernández-Vidal, Jean-Marie Rocchisani PHYSICALLY BASED RIGID REGISTRATION OF 3-D FREE-FORM OBJECTS: APPLICATION TO MEDICAL IMAGING INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATION, RAPPORT DE RECHERCHE Nº 2453 – JANVIER 1995 ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 290 [ [[ [Mardia, 1997] ]] ] – Kanti V. Mardia, Wei Qian, Druti Shah, Kevin M. A. de Souza DEFORMABLE TEMPLATE RECOGNITION OF MULTIPLE OCCLUDED OBJECTS IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, Nº 9 – SEPTEMBER 1997 [ [[ [Martin, 1998] ]] ] – J. Martin, Alex Pentland, Stan Sclaroff, R. Kikinis CHARACTERIZATION OF NEUROPATHOLOGICAL SHAPE DEFORMATIONS IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 20, Nº 3 – FEBRUARY 1998 [ [[ [Maurincomme, 1993] ]] ] – Eric Maurincomme, Denis Friboulet, Gérard Finet, Isabelle Magnin, Johan H. C. Reiber ADDER: A SNAKE-BASED SEGMENTATION APPROACH FOR INTRAVASCULAR ULTRASOUND IMAGES DICTA-93 – 1993 [ [[ [Maybeck, 1979] ]] ] – Peter S. Maybeck STOCHASTIC MODELS, ESTIMATION, AND CONTROL, VOLUME I MATHEMATICS IN SCIENCE AND ENGINEERING, VOL. 141, ACADEMIC PRESS – 1979 [ [[ [McInerney, 1995] ]] ] – Tim McInerney, Demetri Terzopoulos A DYNAMIC FINITE ELEMENT SURFACE MODEL FOR SEGMENTATION AND TRACKING IN MULTIDIMENSIONAL MEDICAL IMAGES WITH APPLICATION TO CARDIAC 4D IMAGE ANALYSIS DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 (1995) [ [[ [McInerney, 1996] ]] ] – Tim McInerney, Demetri Terzopoulos DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS: A SURVEY MEDICAL IMAGE ANALYSIS, VOL. 1, Nº 2, PP. 91/108, OXFORD UNIVERSITY PRESS – 1996 DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 (1996) [ [[ [Meirovitch, 1986] ]] ] – Leonard Meirovitch ELEMENTS OF VIBRATION ANALYSIS MCGRAW-HILL – 1986 [ [[ [Metaxas, 1991] ]] ] – Dimitri Metaxas, Demetri Terzopoulos CONSTRAINED DEFORMABLE SUPERQUADRICS AND NONRIGID MOTION TRACKING IEEE CVPR’91 – COMPUTER VISION AND PATTERN RECOGNITION, HAWAII – 1991 [ [[ [Metaxas, 1996] ]] ] – Dimitri Metaxas, Ioannis A. Kakadiaris ELASTICALLY ADAPTIVE DEFORMABLE MODELS FOURTH EUROPEAN CONFERENCE ON COMPUTER VISION, PP. II: 550/559, CAMBRIDGE, UK – APRIL 1996 [ [[ [Mishra, 1991] ]] ] – Sanjoy K. Mishra, Dimitry B. Goldgof, Thomas S. Huang MOTION ANALYSIS AND EPICARDIAL DEFORMATION ESTIMATION FROM ANGIOGRAPHY DATA IEEE CVPR’91 – COMPUTER VISION AND PATTERN RECOGNITION, HAWAII – 1991 BIBLIOGRAFIA 291 [ [[ [Moghaddam, 1994] ]] ] – Baback Moghaddan, Alex Pentland FACE RECOGNITION USING VIEW-BASED AND MODULAR EIGENSPACES AUTOMATIC SYSTEMS FOR THE IDENTIFICATION AND INSPECTION OF HUMANS, SPIE VOL. 2277 – JULY 1994 [ [[ [Moghaddam, 1996] ]] ] – Baback Moghaddam, Chahab Nastar, Alex P. Pentland BAYESIAN FACE RECOGNITION USING DEFORMABLE INTENSITY SURFACES MASSACHUSETTS INSTITUTE OF TECHNOLOGY, MEDIA LABORATORY, TECHNICAL REPORT Nº 371 – 1996 [ [[ [Moghaddam, 1997] ]] ] – Baback Moghaddam, Alex Pentland PROBABILISTIC VISUAL LEARNING FOR OBJECT REPRESENTATION IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, Nº 7 – JULY 1997 [ [[ [Monteiro, 1994] ]] ] – António Miguel Pontes Pimenta Monteiro DISSERTAÇÃO DE DOUTORAMENTO: PROCESSAMENTO E ANÁLISE AUTOMÁTICA DE ECOCARDIOGRAMAS FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO – 1994 [ [[ [Moulin, 1992] ]] ] – Pierre Moulin AN ADAPTIVE FINITE-ELEMENT METHOD FOR IMAGE REPRESENTATION IEEE 11TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION, NETHERLANDS – 1992 [ [[ [Nastar, 1993] ]] ] – Chahab Nastar, Nicholas Ayache FAST SEGMENTATION, TRACKING, AND ANALYSIS OF DEFORMABLE OBJECTS FOURTH INTERNATIONAL CONFERENCE ON COMPUTER VISION, BERLIN, GERMANY – 11/14 MAY 1993 [ [[ [Nastar, 1993a] ]] ] – Chahab Nastar ANALYTICAL COMPUTATION OF THE FREE VIBRATION MODES: APPLICATION TO NON RIGID MOTION ANALYSIS AND ANIMATION IN 3D IMAGES INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATION, ROCQUENCOURT, RAPPORT DE RECHERCHE Nº 1935 – JUIN 1993 [ [[ [Nastar, 1994] ]] ] – Chahab Nastar THESE POUR LE GRADE DE DOCTEUR: MODELES PHYSIQUES DEFORMABLES ET MODES VIBRATOIRES POUR L’ANALYSE DU MOUVEMENT NON-RIGIDE DANS LES IMAGES MULTIDIMENSIONNELLES L’ÉCOLE NATIONALE DES PONTS ET CHAUSSEES – 1994 [ [[ [Nastar, 1994a] ]] ] – Chahab Nastar, Nicholas Ayache FAST SEGMENTATION, TRACKING, AND ANALYSIS OF DEFORMABLE OBJECTS INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATION, ROCQUENCOURT, RAPPORT DE RECHERCHE Nº 1783 – 1994 ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 292 [ [[ [Nastar, 1996] ]] ] – Chahab Nastar, Nicholas Ayache FREQUENCY-BASED NONRIGID MOTION ANALYSIS: APPLICATION TO FOUR DIMENSIONAL MEDICAL IMAGES IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 18, Nº 11, NOVEMBER 1996 DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE – 1998 (1996) [ [[ [Neuenschwander, 1994] ]] ] – W. Neuenschwander, P. Fua, G. Székely, O. Kübler MAKING SNAKES CONVERGE FROM MINIMAL INITIALIZATION IEEE 1051-4651/94 – 1994 [ [[ [Ohba, 1997] ]] ] – Kohtaro Ohba, Katsushi Ikeuchi DETECTABILITY, UNIQUENESS, AND RELIABILITY OF EIGEN WINDOWS FOR STABLE VERIFICATION OF PARTIALLY OCCLUDED OBJECTS IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, Nº 9 – SEPTEMBER 1997 [ [[ [Olstad, 1996] ]] ] – Bjørn Olstad, Anders H. Torp ENCODING OF A PRIORI INFORMATION IN ACTIVE CONTOUR MODELS IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 18, Nº 9 – SEPTEMBER 1996 [ [[ [Otsu, 1978] ]] ] – Otsu, N. A THRESHOLD SELECTION METHOD FROM GRAY–LEVEL HISTOGRAMS IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. SMC-8, PP. 62/66 – 1978 [ [[ [Padilha, 1995] ]] ] – A. Jorge Padilha, Luís A. Serra, Susana A. Pires, A. Filipe N. Silva RELATÓRIO INTERNO: CARACTERIZAÇÃO ESPACIO-TEMPORAL DE PRESSÕES PLANTARES EM PEDOBAROGRAFIA DINÂMICA INSTITUTO DE ENGENHARIA BIOMÉDICA, FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO – 1995 [ [[ [Park, 1996] ]] ] – Jinah Park, Dimitri Metaxas, Leon Axel ANALYSIS OF LEFT VENTRICULAR WALL MOTION BASED ON VOLUMETRIC DEFORMABLE MODELS AND MRI-SPAMM MEDICAL IMAGE ANALYSIS, VOL. 1, Nº 1, PP. 53/71, OXFORD UNIVERSITY PRESS – 1996 [ [[ [Parker, 1994] ]] ] – A. D. Parker, A. Hill, T. F. Cootes, X. Y. Jin, D. G. Gibson APPLICATION OF POINT DISTRIBUTION MODELS TO THE AUTOMATED ANALYSIS OF ECHOCARDIOGRAMS DEPARTMENT OF MEDICAL BIOPHYSICS, UNIVERSITY OF MANCHESTER – 1994 [ [[ [Pavlovic, 1997] ]] ] – Vladimir I. Pavlovic, Rajeev Sharma, Thomas S. Huang VISUAL INTERPRETATION OF HAND GESTURES FOR HUMAN-COMPUTER INTERACTION: A REVIEW IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, Nº 7 – JULY 1997 BIBLIOGRAFIA 293 [ [[ [Pentland, 1989] ]] ] – Alex Pentland, Jonh Williams GOOD VIBRATIONS: MODAL DYNAMICS FOR GRAPHICS AND ANIMATION MASSACHUSETTS INSTITUTE OF TECHNOLOGY, MEDIA LABORATORY, TECHNICAL REPORT Nº 115 – 1989 [ [[ [Pentland, 1989a] ]] ] – Alex Pentland, Jonh Williams PERCEPTION OF NON-RIGID MOTION: INFERENCE OF SHAPE, MATERIAL AND FORCE MASSACHUSETTS INSTITUTE OF TECHNOLOGY, MEDIA LABORATORY, TECHNICAL REPORT Nº 113 – 1989 ELEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, DETROIT, MICHIGAN USA – 20/25 AUGUST 1989 [ [[ [Pentland, 1990] ]] ] – Alex P. Pentland AUTOMATIC EXTRACTION OF DEFORMABLE PART MODELS INTERNATIONAL JOURNAL OF COMPUTER VISION, 4, PP. 107/126 – MARCH 1990 [ [[ [Pentland, 1991] ]] ] – Alex Pentland, Stan Sclaroff CLOSED-FORM SOLUTIONS FOR PHYSICALLY BASED SHAPE MODELING AND RECOGNITION IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 13, Nº 7, PP. 715/729 – JULY 1991 [ [[ [Pentland, 1991a] ]] ] – Alex Pentland, Bradley Horowitz RECOVERY OF NONRIGID MOTION AND STRUCTURE IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 13, Nº 7 – JULY 1991 DEFORMABLE MODELS IN MEDICAL IMAGE ANALYSIS, IEEE, 1998 (1991) [ [[ [Pentland, 1994] ]] ] – Alex Pentland, Baback Moghaddan, Thad Starner VIEW-BASED AND MODULAR EIGENSPACES FOR FACE RECOGNITION IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION – 1994 [ [[ [Pelillo, 1999] ]] ] – Marcello Pelillo, Kaleem Siddiqi, Steven W. Zucker MATCHING HIERARCHICAL STRUCTURES USING ASSOCIATION GRAPHS IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 21, Nº 11 – NOVEMBER 1999 [ [[ [Pinto, 1999] ]] ] – Tânia Pinto RELATÓRIO DA BOLSA DE INVESTIGAÇÃO 1998/1999 INSTITUTO DE ENGENHARIA BIOMÉDICA – 1999 [ [[ [Press, 1992] ]] ] – William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery NUMERICAL RECIPES IN C - THE ART OF SCIENTIFIC COMPUTING CAMBRIDGE UNIVERSITY PRESS – 1992 [ [[ [Puentes, 1998] ]] ] – John Puentes, Mireille Garreau, Hervé Lebreton, Cristian Roux UNDERSTANDING CORONARY ARTERY MOVEMENT: A KNOWLEDGE-BASED APPROACH ARTIFICIAL INTELLIGENCE IN MEDICINE 13, PP. 207/237 – 1998 ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 294 [ [[ [Reis, 1995] ]] ] – Luís Paulo Gonçalves dos Reis DISSERTAÇÃO DE MESTRADO: SISTEMA INTEGRADO DE DETECÇÃO E SEGUIMENTO DE CONTORNOS FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO – SETEMBRO DE 1995 [ [[ [Richter, 1995] ]] ] – Jeffrey Richter ADVANCED WINDOWS MICROSOFT PRESS – 1995 [ [[ [Rimmer, 1991] ]] ] – Steve Rimmer SUPERCHARGED BITMAPPED GRAPHICS WINDCREST/MCGRAW-HILL – 1991 [ [[ [Rohr, 1996] ]] ] – K. Rohr, H. S. Stiehl, R. Sprengel, W. Beil, T. M. Buzug, J. Weese, M. H. Kuhn POINT-BASED ELASTIC REGISTRATION OF MEDICAL IMAGE DATA USING APPROXIMATING THIN-PLATE SPLINES VBC'96 – VISUALIZATION IN BIOMEDICAL COMPUTING, 4TH INTERNATIONAL CONFERENCE, HAMBURG, GERMANY, SPRINGER – SEPTEMBER 1996 [ [[ [Ronfard, 1994] ]] ] – Rémi Ronfard REGION-BASED STRATEGIES FOR ACTIVE CONTOUR MODELS INTERNATIONAL JOURNAL OF COMPUTER VISION, 13:2, PP. 229/251 – 1994 [ [[ [Schalkoff, 1989] ]] ] – Robert J. Schalkoff DIGITAL IMAGE PROCESSING AND COMPUTER VISION JOHN WILLEY & SONS, INC. – 1989 [ [[ [Schroeder, 1996] ]] ] – Will Schroeder, Ken Martin, Bill Lorensen THE DESIGN AND IMPLEMENTATION OF AN OBJECT-ORIENTED TOOLKIT FOR 3D GRAPHICS AND VISUALIZATION VISUALIZATION ’96 – 1996 [ [[ [Schroeder, 1998] ]] ] – Will Schroeder, Ken Martin, Bill Lorensen THE VISUALIZATION TOOLKIT, 2ND EDITION PRENTICE HALL – 1998 [ [[ [Schroeder, 1999] ]] ] – Will Schroeder, Ken Martin THE VTK USER’S GUIDE KITWARE INC. – JUNE 1999 [ [[ [Sclaroff, 1994] ]] ] – Stan Sclaroff, Alex Pentland OBJECT RECOGNITION AND CATEGORIZATION USING MODAL MATCHING MASSACHUSETTS INSTITUTE OF TECHNOLOGY, MEDIA LABORATORY, TECHNICAL REPORT Nº 267 – 1994 [ [[ [Sclaroff, 1994a] ]] ] – Stan Sclaroff, Alex Pentland PHYSICALLY-BASED COMBINATIONS OF VIEWS: REPRESENTING RIGID AND NON RIGID MOTION MASSACHUSETTS INSTITUTE OF TECHNOLOGY, MEDIA LABORATORY, TECHNICAL REPORT Nº 273 – NOVEMBER 1994 BIBLIOGRAFIA 295 [ [[ [Sclaroff, 1995] ]] ] – Stanley Edward Sclaroff PHD THESIS: MODAL MATCHING: A METHOD FOR DESCRIBING, COMPARING, AND MANIPULATING DIGITAL SIGNALS MASSACHUSETTS INSTITUTE OF TECHNOLOGY – 1995 [ [[ [Sclaroff, 1995a] ]] ] – Stan Sclaroff, Alex Pentland MODAL MATCHING FOR CORRESPONDENCE AND RECOGNITION MASSACHUSETTS INSTITUTE OF TECHNOLOGY, MEDIA LABORATORY, TECHNICAL REPORT Nº 95-008 – 1995 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 17, Nº 6 – JUNE 1995 [ [[ [Segerlind, 1984] ]] ] – Larry J. Segerlind APPLIED FINITE ELEMENT ANALYSIS JOHN WILLEY & SONS, INC. – 1984 [ [[ [Sethi, 1987] ]] ] – Ishwar K. Sethi, Ramesh Jain FINDING TRAJECTORIES OF FEATURE POINTS IN A MONOCULAR IMAGE SEQUENCE IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 9, Nº 1 – JANUARY 1987 [ [[ [Shapiro, 1991] ]] ] – Larry Shapiro REPORT: TOWARDS A VISION-BASED MOTION FRAMEWORK ROBOTICS RESEARCH GROUP, DEPARTMENT OF ENGINEERING SCIENCE, OXFORD UNIVERSITY, TECHNICAL REPORT – 1991 [ [[ [Shapiro, 1992] ]] ] – Larry Shapiro, J. Michael Brady A MODAL APPROACH TO FEATURE-BASED CORRESPONDENCE ROBOTICS RESEARCH GROUP, DEPARTMENT OF ENGINEERING SCIENCE, OXFORD UNIVERSITY – 1992 [ [[ [Shapiro, 1992a] ]] ] – Larry Shapiro, J. Michael Brady FEATURE-BASED CORRESPONDENCE: AN EIGENVECTOR APPROACH BUTTERWORTH-HEINEMANN LTD, VOL. 10, Nº 5 – JUNE 1992 [ [[ [Shenoy, 1995] ]] ] – Shiva Shenoy WIN4DV V1.0: VIEWER FOR 3D POLYGONAL MESHES AND DATA DEPARTMENT OF AEEM, IOWA STATE UNIVERSITY, IA 50010, USA – 1995 [ [[ [Smart, 1997] ]] ] – Julian Smart and others CIMAGE CLASS VERSION 1.2 HTTP://WEB.UKONLINE.CO.UK/MEMBERS/JULIAN.SMART – 1997 [ [[ [Smith, 1995] ]] ] – Philip W. Smith, N. Nandhakumar, A. K. Ramadorai REPRESENTATION OF DEFORMABLE OBJECT STRUCTURE AND MOTION FOR AUTONOMOUS MANIPULATION USING RELATIVE ELASTICITY IEEE 0-8186-7190-4/95, PP. 200/205 – APRIL 1995 ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 296 [ [[ [Solaiyappan, 1996] ]] ] – Meiyappan Solaiyappan, Tim Postin INTERACTIVE VISUALIZATION FOR RAPID NONINVASIVE CARDIAC ASSESSMENT IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, VOL. 29, Nº 1 – JANUARY 1996 [ [[ [Sozou, 1995] ]] ] – P. D. Sozou, T. F. Cootes, C. J. Taylor, E. C. Di-Mauro A NON-LINEAR GENERALIZATION OF PDMS USING POLYNOMIAL REGRESSION DEPARTMENT OF MEDICAL BIOPHYSICS, UNIVERSITY OF MANCHESTER – 1995 [ [[ [Sozou, 1995a] ]] ] – P. D. Sozou, T. F. Cootes, C. J. Taylor, E. C. Di-Mauro NON-LINEAR POINT DISTRIBUTION MODELLING USING A MULTI-LAYER PERCEPTRON DEPARTMENT OF MEDICAL BIOPHYSICS, UNIVERSITY OF MANCHESTER – 1995 [ [[ [Staib, 1991] ]] ] – Lawrence H. Staib, James S. Duncan PARAMETRICALLY DEFORMABLE CONTOURS MODELS CVPR’91 – COMPUTER VISION AND PATTERN RECOGNITION, HAWAII – 1991 [ [[ [Stroustrup, 1995] ]] ] – Bjarne Stroustrup THE C++ PROGRAMMING LANGUAGE ADDISON-WESLEY PUBLISHING COMPANY – 1995 [ [[ [Subsol, 1994] ]] ] – G. Subsol, J. Ph. Thirion, N. Ayache NON RIGID REGISTRATION FOR BUILDING 3D ANATOMICAL ATLASES IEEE 1051-4651/94, PP. 576/578 – 1994 [ [[ [Swets, 1996] ]] ] – Daniel L. Swets, John Weng USING DISCRIMINANT EIGENFEATURES FOR IMAGE RETRIEVAL IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 18, Nº 8 – AUGUST 1996 [ [[ [Syn, 1995] ]] ] – N. H-M. Syn, R. W. Prager FEM EIGENMODES AS SHAPE FEATURES CAMBRIDGE UNIVERSITY ENGINEERING DEPARTMENT, TECHNICAL REPORT Nº 211 – 1995 [ [[ [Syn, 1995a] ]] ] – N. H-M. Syn, R. W. Prager BAYESIAN REGISTRATION OF MODELS USING FEM EIGENMODES CAMBRIDGE UNIVERSITY ENGINEERING DEPARTMENT, TECHNICAL REPORT Nº 213 – 1995 [ [[ [Syn, 1995b] ]] ] – N. H-M. Syn, R. W. Prager A BIOLOGICAL GROWTH METRIC FOR 3D SHAPE REGISTRATION CAMBRIDGE UNIVERSITY ENGINEERING DEPARTMENT, TECHNICAL REPORT Nº 225 – 1995 [ [[ [Syn, 1996] ]] ] – Michael Hsien-Min Syn PHD THESIS: MODEL-BASED THREE-DIMENSIONAL FREEHAND ULTRASOUND IMAGING UNIVERSITY OF CAMBRIDGE – 1996 [ [[ [Székely, 1996] ]] ] – Gábor Székely, András Kelemen, Christian Brechbühler, Guido Gerig SEGMENTATION OF 2-D AND 3-D OBJECTS FROM MRI VOLUME DATA USING CONSTRAINED ELASTIC DEFORMATIONS OF FLEXIBLE FOURIER CONTOUR AND SURFACE MODELS MEDICAL IMAGE ANALYSIS, VOL. 1, Nº 1, PP. 19/34, OXFORD UNIVERSITY PRESS – 1996 ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 4 Tabela 3.10 – Dados utilizados e resultados obtidos na sétima experiência para a determinação das correspondências utilizando o princípio do mapeamento segundo a distância mínima. (Continuação) Correspondências Obtidas (duas vistas), % dos Vect.: 100%, Nº de Corresp.: 73 Correspondências Obtidas (duas vistas), % dos Vect.: 75%, Nº de Corresp.: 64 Figura 3.6 – Objectos obtidos utilizando-se os doze primeiros modos e com 3.8s= e 100s=. (sec. 3.4.3.1.2, pág. 79) Figura 3.7 – Objectos obtidos utilizando-se os vinte e cinco primeiros modos e com 3.8s= e 100s=. (sec. 3.4.3.1.2, pág. 79) ANEXO: IMAGENS A CORES 5 Tabela 3.20 – Dados utilizados e resultados obtidos na oitava experiência para a determinação das correspondências utilizando a análise modal da forma. (sec. 3.4.3.2.2, pág. 84) Objecto 13 (120 pontos) Objecto 14 (107 pontos) Correspondências Obtidas (duas vistas), Nº de Corresp.: 38 A2 – Capítulo V a) b) c) Figura 5.10 – Superfície resultante utilizando-se amostragem adaptativa: a) Objecto da Figura 5.9a) após amostragem adaptativa; b) Superfície resultante por triangulação (232 nodos); c) Superfície resultante após simplificação e suavização (115 nodos). (sec. 5.3.2.2, pág. 155) ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 6 a) b) Figura 5.12 – Representação de uma superfície de intensidade utilizando um conjunto de contornos de isonível: a) Superfície de intensidade; b) Oito contornos de isonível. (sec. 5.3.3, pág. 156) Tabela 5.8 – Dados utilizados e resultados obtidos na sexta experiência para a determinação das correspondências utilizando o elemento finito de Sclaroff. (sec. 5.4.1.2.2, pág. 165) Imagens Originais Objecto 10 (336 nodos) Objecto 11 (316 nodos) Correspondências Obtidas (duas vistas), Nº de Corresp.: 49 ANEXO: IMAGENS A CORES 7 Tabela 5.9 – Dados utilizados e resultados obtidos na sétima experiência para a determinação das correspondências utilizando o elemento finito de Sclaroff. (sec. 5.4.1.2.2, pág. 166) Objecto 12 (143 nodos) Objecto 13 (111 nodos) Correspondências Obtidas (duas vistas), Nº de Corresp.: 42 Tabela 5.10 – Dados utilizados e resultados obtidos na oitava experiência para a determinação das correspondências utilizando o elemento finito de Sclaroff. (sec. 5.4.1.2.2, pág. 166) Imagens Originais Objecto 14 (176 nodos) Objecto 15 (190 nodos) ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 8 Tabela 5.10 – Dados utilizados e resultados obtidos na oitava experiência para a determinação das correspondências utilizando o elemento finito de Sclaroff. (Continuação.) Correspondências Obtidas (duas vistas), Nº de Corresp.: 90, Energia: 2501.9 Tabela 5.11 – Dados utilizados e resultados obtidos na nona experiência para a determinação das correspondências utilizando o elemento finito de Sclaroff. (sec. 5.4.1.2.2, pág. 167) Imagem Original Objecto 16 (192 nodos) Correspondências Obtidas com o Objecto 15 (duas vistas), Nº de Corresp.: 68, Energia: 1413.3 ANEXO: IMAGENS A CORES 9 Tabela 5.22 – Dados utilizados e resultados obtidos na nona experiência para a determinação das correspondências utilizando elementos axiais lineares agrupados. (sec. 5.4.2.2.2, pág. 182) Objecto 16 e 17 (25 nodos) Correspondências Obtidas (duas vistas), Nº de Corresp.: 25 Tabela 5.24 – Dados utilizados e resultados obtidos na décima segunda experiência para a determinação das correspondências utilizando elementos axiais lineares agrupados. (sec. 5.4.2.2.2, pág. 183) Imagens Originais Objecto 21 (30 nodos) Objecto 22 (30 nodos) Correspondências Obtidas (duas vistas), Nº de Corresp.: 25 ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 10 A3 – Capítulo VI Menus Barra de ferramentas Menu Emergente Documento Imagem Documento VTK Barra de Estado Figura 6.3 – A interface da plataforma de desenvolvimento e ensaio. (O documento activo é do tipo imagem; assim as funções disponíveis são as existentes para este tipo de documento.) (sec. 6.4, pág. 196) Figura 6.5 – Interface da plataforma de desenvolvimento e ensaio quando está activo um documento VTK. (sec. 6.4, pág. 198) ANEXO: IMAGENS A CORES 11 a) b) Figura 6.17 – Segmentação de um objecto utilizando o modelo de snake de Kass: a) Definição da snake inicial, utilizando o rato, e aplicação do método; b) Snake final obtida. (sec. 6.6.3.1, pág. 209) a) b) c) Figura 6.20 – Fusão de dois segmentos: a) Segmentos originais; b) Confirmação da fusão; c) Segmento resultante. (sec. 6.6.3.2, pág. 211) ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 12 a) b) c) Figura 6.21 – Simplificação de dois segmentos: a) Segmentos originais; b) Confirmação da simplificação; c) Segmento resultante. (sec. 6.6.3.2, pág. 211) a) b) Figura 6.27 – Binarização das células de um objecto: a) Objecto original; b) Objecto resultante da binarização das células com valores entre –90.0 e –80.0. (sec. 6.6.4, pág. 215) a) b) c) Figura 6.30 – Determinação dos contornos de um objecto: a) Objecto original; b) Contorno exterior; c) Alguns contornos de isonível. (sec. 6.6.4, pág. 216) ANEXO: IMAGENS A CORES 13 a) b) c) Figura 6.44 – Visualização 3D de uma superfície: a) Imagem original (negada); b) Amostragem resultante; c) Superfície visualizada na aplicação Win4Dv. (sec. 6.6.5.1.2, pág. 225) A4 – Capítulo VII Figura 7.3 – Contornos a considerar ao longo da sequência. (sec. 7.2.1, pág. 240) ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 20 Distribuição da Energia 0 200 400 600 800 1000 1200 1400 1600 1800 123456789 ID III III IV V VI VII VIII IX X XI XII Figura 7.19 – Comparticipação dos modos de vibração na energia de deformação ao longo da sequência de superfícies baseadas em amostragem adaptativa. (sec. 7.2.2.2, pág. 256) Distribuição da Energia Emp. 4 I II III IV IX V XXI XII VIII VII VI a) Distribuição da Energia Emp. 4 I II III IV V VI X IX VII VIII XI XII b) Figura 7.20 – Distribuição da energia de deformação por 12 classes de modos, sem (a) e com (b) a prévia aplicação da transformação rígida obtida, para o emparelhamento 4 entre superfícies baseadas em amostragem adaptativa. (sec. 7.2.2.2, pág. 256) Figura 7.21 – Emparelhamento 5 após aplicação dos deslocamentos nodais estimados à superfície 5. (sec. 7.2.2.2, pág. 256) ANEXO: IMAGENS A CORES 21 a) b) Figura 7.22 – Determinação dos isocontornos a considerar: a) Superfície de intensidade construída a partir da imagem 4 da sequência; b) Onze contornos isobáricos extraídos a partir da superfície. (sec. 7.2.3.1, pág. 257) Figura 7.23 – Duas vistas dos emparelhamentos determinados entre contornos de isonível de uma mesma imagem. (sec. 7.2.3.1, pág. 258) Distribuição da Energia 0 1000 2000 3000 4000 5000 6000 12345678910 ID XII XI X IX VIII VII VI V IV III II I Figura 7.26 – Comparticipação dos modos de vibração na energia de deformação ao longo do emparelhamento dos isocontornos de uma mesma imagem. (sec. 7.2.3.1, pág. 260) ANÁLISE DE MOVIMENTO DE CORPOS DEFORMÁVEIS USANDO VISÃO COMPUTACIONAL 22 Figura 7.27 – Duas vistas dos deslocamentos estimados para os contornos de isonível de uma mesma imagem. (sec. 7.2.3.1, pág. 260) Figura 7.28 – Duas vistas dos dez isocontornos a considerar ao longo da sequência exemplo. (sec. 7.2.3.2, pág. 261) Distribuição da Energia 0 200 400 600 800 1000 1200 1400 1600 123456789 ID XII XI X IX VIII VII VI V IV III II I Figura 7.31 – Comparticipação dos modos de vibração na energia de deformação ao longo da sequência de isocontornos de nível de brilho médio. (sec. 7.2.3.2, pág. 263) 23 A1 – Capítulo III _________________________________________________________________ 3 A2 – Capítulo V __________________________________________________________________ 5 A3 – Capítulo VI ________________________________________________________________ 10 A4 – Capítulo VII _______________________________________________________________ 13