Análise de Movimento Não Rígido em Visão por Computador

Análise de Movimento Não Rígido em Visão por Computador João Manuel R. S. Tavares1, J. Barbosa2, A. Jorge Padilha3 1Universidade do Porto, Faculdade de Engenharia, Departamento de Engenharia Mecânica e Gestão Industrial, Instituto de Engenharia Biomédica, Laboratório Sinal e Imagem, Rua Dr. Roberto Frias, s/n 4200-465 PORTO – PORTUGAL [email protected], http://www.fe.up.pt/~tavares 2, 3Universidade do Porto, Faculdade de Engenharia, Departamento de Engenharia Electrotécnica e de Computadores, Instituto de Engenharia Biomédica, Laboratório Sinal e Imagem [email protected], http://www.fe.up.pt/~jbarbosa [email protected], http://www.fe.up.pt/~padilha Resumo - Neste artigo são apresentadas várias metodologias actualmente existentes, no domínio da Visão por Computador, para a análise de movimento não rígido e são indicados diversos exemplos de aplicações. Assim 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 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 modelização sugere uma classificação possível da forma não rígida e do movimento. Assim são também apresentados modelos de forma para objectos deformáveis e indicados vários exemplos de aplicações. Com este estudo, de certo modo aprofundado, das várias metodologias, e suas aplicações, existentes no domínio da análise de movimento não rígido, espera-se contribuir para o seu desenvolvimento, dada a actual carência de boas revisões do estado da arte neste domínio. Palavras-chave: Análise de Movimento Não Rígido, Objectos Deformáveis, Visão por Computador. Abstract - In this article several methodologies actually existent, in the Computer Vision domain, for nonrigid movement analysis are presented and several examples of applications are indicated. Thus the nonrigid movement is classified and, for each resulting class, the restrictions and the inherent conditions are presented and some works accomplished in its ambit are verified. As the questions of movement and shape analysis becomes non-separable when it’s considered the movement of the non-rigid type, the shape models also suggests a possible classification of the non-rigid shape and of the movement. Thus shape models for deformable objects will be presented and some examples of applications indicated. With this study, in certain way deep, of several methodologies, and its applications, existent in the domain of the non-rigid movement analysis, the authors hope to contribute for its development, given the actual lack of good state of the art revisions in this domain. Key-words: Computer Vision, Deformable Objects, Non-rigid Movement Analysis. 1 - Introdução 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 [1]. 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. É 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 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 e modelos volumétricos. Nos pontos seguintes deste artigo o movimento não rígido será classificado, serão apresentadas as classes restringidas de movimento não rígido, com indicação das considerações e condições inerentes, e serão descritos modelos de forma para objectos não rígidos. 2 - 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 classes – 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. – [1]: • Movimento rígido – a distância entre quaisquer dois pontos do objecto é preservada. O objecto não estica nem dobra; desde modo, a curvatura 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. 3 - Classes restringidas de movimento não rígido 3.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 [1]. 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 [2] é 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 [3]. 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 [4] 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 [5]. Em [6-8] é 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 para estimar a posição do modelo na imagem seguinte. Em [9] é 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. O problema de reconhecimento da forma de objectos articulados e deformáveis é também tratado em [10], através da utilização de grafos e de árvores de pesquisa para a determinação dos emparelhamentos. Em [11] é 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. Modelos deformáveis são utilizados em [12] para a estimação, baseada num modelo, do movimento 3D do corpo humano a partir de várias câmaras. O método proposto é baseado na análise espaço-temporal das silhuetas, e apresenta a vantagem da não necessidade de marcas especiais no corpo ou outros dispositivos, e uma considerável estabilidade na presença de oclusões significativas. O problema de localização de pessoas em imagens é também tratado em [13]. A solução adoptada baseia-se na utilização de quatro detectores distintos, construídos a partir de exemplos, treinados para separadamente encontrar as quatro componentes do corpo humano: a cabeça, as pernas, o braço esquerdo e o braço direito. A solução é proposta para situações nas quais os objectos em causa são compostos por componentes distintos, cujas combinações obedecem a configurações bem definidas. O reconhecimento do movimento humano através da utilização de protótipos temporal é sugerido em [14]. O protótipo temporal proposto é um vector imagem estático, cujo o valor em cada ponto é uma função das propriedades do movimento na correspondente localização espacial na sequência de imagens. Em [15] é apresentada uma abordagem para o seguimento (acompanhamento) dos contornos aparentes de estruturas articuladas ao longo do seu movimento. Na reconstrução das trajectórias é utilizada filtragem de Kalman, o que torna o processo mais robusto às oclusões. A abordagem é aplicada no seguimento de pessoas a caminhar e em linguagem gestual. O problema de seguimento de estruturas articuladas complexas em tempo real é abordado em [16]. O método proposto é baseado num modelo de CAD interno do objecto a seguir, e também incorpora a calibração em tempo real dos parâmetros internos da câmara usada. 3.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 taxa de 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 [17] é 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 [18], 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 determinarse 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 [19, 20] é 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 pontos mais próximos de uma outra curva, admitindo que o movimento é reduzido. Também em [21] é 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 [22-24] é 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. A classificação automática de silhuetas através do emparelhamento de curvas é realizada em [25]. A transformação que mapea uma curva na outra é determinada utilizando programação dinâmica. Apesar de ser referido que a metodologia é desenhada para deformações substanciais, grandes escalamentos e transformações rígidas arbitrárias, a mesma é baseada numa simples heurística que assume que os pontos emparelhados deverão localizar-se sobre parcelas semelhantes de curva. 3.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 [1]. 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 [26] é 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. 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 [27] é 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 [28] é 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. 3.4 - 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. Em [29] é proposto um algoritmo para o seguimento de movimento não rígido a partir de um modelo representando o conhecimento geral do objecto, um conjunto esparso de correspondências, e informação incompleta ou inexistente sobre a geometria ou propriedades do material. O método é baseado na análise iterativa das diferenças entre o comportamento verificado e o previsto ao longo da sequência de movimento. Os parâmetros desconhecidos são determinados através da procura do modelo, de elementos finitos não lineares, que melhor aproxima o movimento não rígido do objecto. Durante essa procura não são apenas estimadas as melhores propriedades do material, mas também correspondências densas a partir das correspondências esparsas iniciais. Um método para estimar a forma de um modelo deformável, usando mínimos quadrados residuais de um modelo baseado no cálculo de fluxo óptico é proposto em [30]. Este método é baseado na metodologia de estimação usando fluxo óptico e características de imagem, onde o fluxo óptico apenas afecta os parâmetros do movimento do modelo. Utilizando os resultados do cálculo, o método ajusta todos os parâmetros de maneira que os resíduos resultantes do fluxo óptico são minimizados. A metodologia proposta é aplicada no seguimento de faces. Em [31] é apresentada um técnica de visão por computador para controlo não rígido que pode ser utilizada em animação e aplicações de vídeo jogos. O utilizador deforma e move um objecto em frente a uma câmara e, deste modo, especifica o movimento desejado. É utilizada uma técnica de seguimento não rígido para determinar a posição, a rotação e as deformações não rígidas impostas ao objecto. As transformações determinadas podem posteriormente ser aplicadas a uma malha mapeada com textura, permitindo assim o seu controlo por parte do utilizador. O seguimento do movimento não rígido é conseguido deformando a malha mapeada com textura de forma a alinha-la, por minimização de energia, em cada imagem da sequência [31, 32]. No processo de alinhamento é utilizado o elemento finito isoparamétrico proposto em [33] e análise modal. 3.5 - 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 [34] é 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 de acordo com os princípios da mecânica Lagrangiana. Nesta abordagem dinâmica, campos de forças externas são utilizados para aproximar o modelo deformável aos objectos da imagem. Estes campos são derivados a partir de funções de potencial e calculados a partir das imagens a considerar. Assim que o modelo deformável atinge o equilíbrio no campo de forças externas, ele reconstrói a forma do objecto em questão. Quando presentes em imagens de sequências de objectos em movimento não rígido, os modelos deformáveis são aptos a estimar e a seguir o movimento existente. Esta abordagem física é também aplicável ao movimento não rígido plano, por exemplo através de contornos activos (snakes). Estimadores recursivos do movimento não rígido têm vindo a ser desenvolvidos, utilizando as equações do movimento dos modelos deformáveis como modelos de sistema numa abordagem de estimação não linear por filtragem de Kalman. 3.6 - Movimento fluído O movimento fluído é o tipo mais geral de movimento não rígido e inclui o movimento de objectos gasosos e líquidos. Estes movimentos, que não necessitam de ser contínuos, podem exibir estruturas topológicas altamente variáveis assim como comportamento não suave como, por exemplo, turbulência. Um novo modelo, baseado em princípios físicos, é proposto em [35] para animações de objectos deformáveis. Os objectos são representados por membranas elásticas fechadas preenchidas por um fluido viscoso compressível. A superfície elástica é modelizada por um sistema de massas e de molas, o fluido é discretizado com uma grelha regular e são utilizadas equações diferenciais para determinar o escoamento entre os seus nodos adjacentes. O modelo proposto, é capaz de simular correctamente a colisão com outros objectos, quer sejam do tipo rígido ou não, sem variação de volume. Um método para a simulação em tempo real de tecidos deformáveis, nomeadamente para a simulação cirúrgica, é proposto em [36]. O método implementa uma solução estática para as deformações globais elásticas do objecto, considerado preenchido com um fluido incompressível, baseada no princípio de Pascal e na conservação do volume. A física dos objectos é modelizada utilizando as variáveis: pressão, densidade, volume e tensão. Os volumes são discretizados utilizando elementos longos. O conjunto de equações estáticas, mais o princípio de Pascal e a conservação do volume, são utilizadas para determinar a deformação do objecto e as forças. São assim obtidas deformações globais e locais consistentes. O problema da estimação e da análise do movimento de fluidos em sequências de imagem, nomeadamente em imagens de satélite para fins meteorológicos, é abordado em [37]. A solução proposta é baseada num estimador de movimento dedicado, construído de forma a minimizar uma função de custo. Esta função incorpora um termo derivado da versão integrada da equação de continuidade da mecânica dos fluidos compatível com grandes deslocamentos. Quando comparado com outras classes de movimento não rígido, relativamente pouco trabalho foi ainda realizado na análise deste tipo de movimento. 4 - Modelos de forma para objectos não rígidos A modelização de formas para a análise de movimento não rígido tem vindo a atrair cada vez mais atenção. Modelos de forma poderosos são necessários para representar eficientemente objectos deformáveis e seguir os seus movimentos não rígidos. Primitivas parametrizáveis globais, tais como superquádricas e hiperquádricas, têm surgido como úteis na representação de formas. Estas primitivas permitem que sólidos e superfícies sejam construídos e facilmente modificados, utilizando-se apenas poucos parâmetros. Modelos parametrizáveis globais são úteis para o reconhecimento de objectos, utilizando-se bibliotecas de modelos. Uma outra classe útil de modelos de forma é a dos modelos de splines e de malha com forma livre, cuja definição envolve vários parâmetros locais. Estes modelos são úteis para o controlo local da forma e para representar detalhes locais. Recentemente, modelos híbridos têm vindo a ser propostos por combinação das características das representações parametrizáveis locais e globais. Existem muitos objectos reais que, para se obter uma simulação mais fidedigna, devem ser modelizados segundo primitivas volumétricas. Versões dinâmicas e baseadas em princípios físicos de alguns modelos destas classes têm vindo a ser propostas e são referenciadas nos pontos seguintes. 4.1 - Modelos locais Trabalho significativo na área da visão por computador tem vindo a ser realizado no desenvolvimento de algoritmos de reconstrução da forma baseados em modelos locais utilizando splines generalizadas. Em [38] é apresentado um método que utilizada malhas adaptativas para amostragem não uniforme e reconstrução de dados de intensidade e de profundidade. Malhas adaptativas são modelos dinâmicos discretos agrupados por interligação de massas nodais por molas não lineares ajustáveis. Os nodos não são fixos e podem-se mover sobre a superfície. As molas podem ajustar automaticamente a sua rigidez utilizando a informação local sobre a profundidade, o gradiente e/ou a curvatura, de maneira a concentrar os nodos sujeitos a variações rápidas da forma. Assim, a posição dos nodos e a rigidez das molas que os ligam alteram-se automaticamente em função das propriedades da superfície (ou da imagem). Malhas adaptativas elásticas, dependentes da presença de orlas de intensidade e/ou de pontos de elevada curvatura, são também utilizadas em [39, 40] na determinação do movimento 2D e 3D não rígido segundo princípios físicos, utilizando o método dos elementos finitos e minimização de energia. A metodologia apresentada é aplicada na reconstrução de imagens, nomeadamente, na área da imagem médica. Também em [41] são utilizadas malhas elásticas adaptativas para compressão, restauração e representação de imagens. Em [42] são também utilizadas malhas adaptativas em imagens de ultrasons para o seguimento de movimento não rígido, segundo princípios físicos pela utilização do método dos elementos finitos. A aproximação de pontos 3D não ordenados por B-Splines é tratado em [43]. Na solução apresentada os dados são ordenados e os parâmetros das B-Splines são determinados, de forma congruente com o sentido físico inerente aos dados. Tal é conseguido pela parâmetrização da superfície através dos seus geodésicos e linhas de curvatura. 4.2 - Modelos globais Os harmónicos esféricos são comuns no desenvolvimento de modelos globais. O modelo harmónico esférico é uma representação paramétrica da superfície fechada que pode ser descrita por uma função radial. O modelo, de conceito similar ao descriptor de Fourier, decompõe a função radial em várias funções de base ortogonal. A desvantagem associada a tais modelos é que a função de base é global, tal como as funções seno e co-seno no descriptor de Fourier. Em [44] é apresentada uma abordagem para a obtenção de movimento não rígido baseada num elemento finito elástico isoparamétrico do tipo hexaédrico com 20 nodos. O elemento aplica uma deformação global parametrizada a um modelo geométrico fechado do tipo esfera, cubo ou superquádrico. O algoritmo adoptado utiliza análise modal aproximada de maneira a desacoplar os graus de liberdade do elemento em modos rígidos e não rígidos. Na abordagem apresentada é modelizada e simulada a física do movimento elástico para estimar a forma do objecto e a sua velocidade. A estimação da forma é integrada ao longo do tempo, pela utilização de filtragem de Kalman, resultando uma estimação estável da forma 3D e também da velocidade 3D. 4.3 - Modelos híbridos Em [45] é apresentada uma abordagem física para ajustar formas 3D complexas, utilizando uma nova classe de modelos dinâmicos que podem deformar-se localmente e globalmente ao mesmo tempo. É utilizada a formulação de superquádricas deformáveis, que incorpora os parâmetros globais da forma de um superelipsóide convencional com os graus de liberdade locais de uma spline. O seguimento de objectos 3D utilizando modelos deformáveis híbridos segundo princípios físicos é realizado em [46]. Os modelos utilizados resultam da combinação de modelos superquádricos parametrizáveis, para as deformações globais, e de splines generalizadas, para as deformações locais. Em [47, 48] são utilizados cilindros generalizados deformáveis periodicamente para a transformação do problema de seguimento 2D num problema de ajuste de modelo 3D. Estes cilindros têm componentes rígidos (globais) e deformáveis (locais) e são utilizados no seguimento do ventrículo cardíaco esquerdo em fatias (slices) da parede deste. Um modelo hiperquádrico híbrido é utilizado em [49] para o ajuste de dados 2D e 3D de imagens médicas, que descreve propriedades locais e globais através de uma equação implícita e única para a representação da forma, sendo o ajuste obtido por minimização de energia. Em [50] são utilizados modelos deformáveis elasticamente adaptativos para estimar a forma de objectos utilizando modelos deformáveis 2D e 3D, cujos parâmetros de elasticidade variam em função do erro de ajuste. São utilizados dois filtros independentes de Kalman: um para a transformação rígida e um outro para as deformações locais. Uma utilização de superfícies subdivididas para modelizar formas é realizada em [51]. A ideia principal da metodologia proposta, é integrar as vantagens da subdivisão superficial com as técnicas de modelização segundo princípios físicos. Com esta integração, a manipulação por parte do utilizador do modelo superficial, baseado em princípios físicos pela utilização do método dos elementos finitos, é facilitada e mais intuitiva. A metodologia é aplicada na reconstrução de objectos estáticos e em movimento não rígido. O seguimento da estrutura e do movimento de objectos não rígidos baseado numa metodologia híbrida é proposto em [52], e é utilizada em imagens 2D de nuvens obtidas por satélite sem a prévia determinação das correspondências. O método utilizado é hierárquico: integra análise local, para detalhes finos, e análise global. Basicamente, o método consiste em segmentar as imagens em várias regiões de reduzidas dimensões e analisar localmente cada uma das regiões resultantes. Seguidamente é utilizado um algoritmo recursivo para integrar a análise local com as apropriadas restrições do modelo fluído global. O alinhamento e o emparelhamento de objectos deformáveis, o alinhamento de imagens médicas 3D e a reconstrução de dentes a partir de imagens 2D, são tratados em [53]. O esquema de representação proposto captura a informação da curvatura da superfície em certos pontos e produz imagens de “assinatura” nesses pontos. Estas imagens são comparadas utilizando templates. Para ser possível o emparelhamento parcial um outro critério, o coeficiente de sobreposição, é utilizado. Este esquema de representação pode ser utilizado como uma representação global da superfície assim como local, e possibilita a execução de alinhamento quase em tempo real. É verificado que a representação proposta recupera a transformação devida ao escalonamento, assim como possibilita o emparelhamento de objectos em cenas 3D com oclusão e subdivisão. Em [54] é sugerido uma nova modelização geométrica de formas que permite a representação das características globais e locais de um objecto. A modelização proposta permite a representação de formas globais com detalhe local, o que torna possível a modelização de formas assim como variações topológicas através de um controlo segundo princípios físicos. Com a modelização sugerida a manipulação dos modelos obtidos é conseguida através da aplicação de forças. Em [55, 56] são desenvolvidos modelos alternativos que combinam elementos descritores primitivos, como por exemplo cilindros flexíveis, numa estrutura global. Assim, os novos modelos paramétricos resultam da interpolação linear de duas formas paramétricas, segundo os seus eixos médios, utilizando uma função de fusão governada por princípios físicos. O seguimento de formas utilizando múltiplos modelos, seleccionados de forma dinâmica, é proposto em [57]. Assim os parâmetros variantes no tempo, tais como parâmetros de movimento e de forma, são estimados utilizando sistemas dinâmicos, por exemplo modelos estocásticos, seleccionados de acordo com um mecanismo probabilístico. São apresentados resultados de seguimento e estimação em linguagem gestual. O problema da representação de classes de objectos não rígidos em termos de objectos protótipos é tratado em [58]. A abordagem apresentada desenvolve um modelo flexível para uma classe de objecto a partir de um conjunto de protótipos. Este modelo é posteriormente utilizado para estimar os parâmetros de representação de baixo nível de novos objectos como combinações dos parâmetros do protótipo. As variações da forma do objecto são modelizadas como deformações não rígidas. Variações da aparência são modelizadas como variações de intensidade. Na fase de alinhamento de protótipos é utilizada a abordagem proposta em [32]. São apresentados resultados experimentais em imagens de faces e do coração. 4.4 - Modelos volumétricos Vários autores têm explorando a utilização de modelos deformáveis volumétricos ou sólidos para a face e a cabeça humana em aplicações de computação gráfica, como por exemplo [59-62], e em aplicações médicas, particularmente em cirurgia reconstrutiva, como por exemplo [63-65], e para seguir e analisar o movimento do ventrículo esquerdo de forma mais precisa como, por exemplo, em [66]. Outra aplicação dos modelos deformáveis volumétricos é na simulação cirúrgica; por exemplo, em [67] são utilizados elementos finitos volumétricos sólidos 3D para simular em tempo real o comportamento elástico em situações de cirurgia. Em [68] é tratado o seguimento de objectos 3D em sequências 2D de imagens estéreo, segundo princípios físicos que assumem que os objectos são construídos a partir de classes de primitivas volumétricas. Na primeira imagem é realizado o ajuste de um modelo deformável, utilizando um elipsóide superquádrico deformável como referência, e é utilizada filtragem de Kalman para estimar o movimento e a forma do objecto, existindo a possibilidade de seguir vários objectos de forma independente. Esta abordagem é utilizada em [69] na determinação da posição e estimação da forma de um objecto a partir de várias vistas do mesmo. Um método volumétrico para a obtenção faseada da transformação 3D de uma forma numa outra é proposta em [70]. A interpolação das duas formas é expresso por um processo no qual uma forma se deforma de maneira a maximizar a sua similaridade com a outra. Assim o processo optimiza de forma incremental uma função objectivo, que traduz a semelhança entre a forma alvo e a forma em deformação. A superfície deformável é representada como um conjunto de iso-níveis de uma função escalar de três dimensões densamente amostrada. 5 - Sumário e conclusões O movimento não rígido é ubíquo pois não existe nenhum objecto no mundo real que seja perfeitamente rígido. A razão da recente onda de interesse no movimento não rígido baseia-se em dois factores principais: primeiro, investigação recente conduziu a novas abordagens promissoras para a análise de movimento não rígido; segundo, um elevado número de aplicações potenciais tornou-se evidente, incluindo reconhecimento da face/cabeça humana para teleconferência, reconhecimento gestual para realidade virtual, construção de modelos de objectos não rígidos, estudos de deformação de materiais e de solos sujeitos a pressão, seguimento da formação de nuvens para previsão meteorológica, observação de crescimento de cristais, e análise do fluxo de fluídos. Também inúmeras aplicações existem na área biomédica, tal como a análise do movimento do ventrículo esquerdo, estudo do movimento pulmonar, e crescimento de tumores, entre outras. A análise de movimento não rígido é uma área de investigação a florescer e o trabalho já realizado começou apenas a desbravar soluções para alguns dos muitos problemas de resolução complexa existentes. Muitos assuntos teóricos estão ainda em aberto nas áreas de seguimento do movimento de dados 3D, ou a partir das suas projecções 2D, da análise de objectos sujeitos a elevadas deformações, e da análise de movimento fluído e viscoelástico não restringido. Para objectos não rígidos, as questões de representação do movimento e da representação da forma estão muito mais relacionadas do que para objectos rígidos. Apenas alguns autores consideraram os problemas de representação de objectos não rígidos mais complexos do que objectos articulados [1]. A maior parte deste trabalho descreve objectos não rígidos constituídos por um único elemento. É evidente que para muitos objectos não rígidos são mais adequadas representações de elementos múltiplos. Por vezes, cada elemento é por si só um objecto não rígido existindo ainda a possibilidade destes objectos se dividirem e/ou se fundirem ao longo do movimento. Questões de representação tornam-se de importância crítica assim que se avança de problemas de seguimento e análise de movimento para problemas de reconhecimento de objectos não rígidos. Como ficou claro ao longo deste artigo, a análise de movimento e/ou da forma de objectos deformáveis é um problema deveras complexo existindo ainda muito trabalho a ser realizado. Referências 1. Chandra Kambhamettu, D.B.G., Demetri Terzopoulos, Thomas S. Huang, Nonrigid Motion Analysis, in Deformable Models in Medical Image Analysis. 1998. 2. Pentland, A.P., Automatic Extraction of Deformable Part Models. International Journal of Computer Vision, 1990(4): p. 107/126. 3. Philip W. Smith, N. Nandhakumar, and A.K. Ramadorai, Representation of Deformable Object Structure and Motion for Autonomous Manipulation using Relative Elasticity, in IEEE 0-8186-7190-4/95. 1995, IEEE. p. 200/205. 4. P. D. Sozou, et al., A Non-linear Generalization of PDMs using Polynomial Regression. 1995, Department of Medical Biophysics, University of Manchester. 5. P. D. Sozou, et al., Non-linear Point Distribution Modelling using a Multi-layer perceptron. 1995, Department of Medical Biophysics, University of Manchester. 6. Ioannis A. Kakadiaris, Dimitri Metaxas, and R. Bajcsy. Active Part-Decomposition, Shape and Motion Estimation of Articulated Objects: A Physics-Based Approach. in IEEE Computer Vision and Pattern Recognition Conference. 1994. Seattle, Washington. 7. Ioannis A. Kakadiaris, Dimitri Metaxas, and R. Bajcsy. 3D Human Body Model Acquisition from Multiple Views. in Fifth international Conference on Computer Vision. 1995. Boston, MA. 8. Ioannis A. Kakadiaris, Dimitri Metaxas, and R. Bajcsy, Inferring 2D object structure from the deformation of apparent contours, in Special Issue of Computer Vision and Image Understanding on Physics-base Modeling and Reasoning in Computer Vision. 1996. 9. Grinnell Jones and B. Bhanu, Recognition of Articulated and Occluded Objects, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 1999. 10. Marcello Pelillo, Kaleem Siddiqi, and S.W. Zucker, Matching Hierarchical Structures Using Association Graphs, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 1999. 11. Leonid V. Tsap, Dmitry B. Goldgof, and S. Sarkar, Model-based force-driven nonrigid motion recovery from sequences of range image without point correspondences. Image and Vision Computing, 1999(17): p. 997/1007. 12. Ioannis A. Kakadiaris and D. Metaxas, ModelBased Estimation of 3D Human Motion, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 2000. p. 1453/1459. 13. Anuj Mohan, Constantine Papageorgiou, and T. Poggio, Example-Based Object Detection in Imagens by Components, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 2001. p. 349/361. 14. Aaron F. Bobick and J.W. Davis, The Recognition of Human Movement Using Temporal Templates, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 2001. p. 257/267. 15. Yann Ricquebourg and P. Bouthemy, RealTime Tracking of Moving Persons by Exploiting Spatio-Temporal Image Slices, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 2000. p. 797/808. 16. Tom Drummond and R. Cipolla, Real-Time Visual Tracking of Complex Structures, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 2002. p. 932/946. 17. Ishwar K. Sethi and R. Jain, Finding Trajectories of Feature Points in a Monocular Image Sequence, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 1987. 18. J. S. Duncan, et al. Measurement of Non-rigid Motion Using Contour Shape Descriptors. in CVPR'91 - Computer Vision and Pattern Recognition. 1991. Hawaii. 19. Zhang, Z., Iterative Point Matching for Registration of Free-Form Curves. 1992, Institut National de Recherche en Informatique et en Automation. 20. Zhang, Z., Iterative Point Matching for Registration of Free-Form Curves and Surfaces. International Journal of Computer Vision, 1994. 13(2): p. 119/152. 21. Senthil Kumar, et al. Point Correspondence in Unstructured Nonrigid Motion. in IEEE International Symposium on Computer Vision. 1995. Florida. 22. João Manuel R. S. Tavares and A.J. Padilha. Matching lines in image sequences with geometric constraints. in RecPad'95 - 7th Portuguese Conference on Pattern Recognition. 1995. Aveiro, Portugal. 23. João Manuel R. S. Tavares and A.J. Padilha. A new approach for merging edge line segments. in RecPad'95 - 7th Portuguese Conference on Pattern Recognition. 1995. Aveiro, Portugal. 24. Tavares, J.M.R.S., Obtenção de Estrutura Tridimensional a Partir de Movimento de Câmara, in Faculdade de Engenharia. 1995, Universidade do Porto. 25. Yoram Gdalyahu and D. Weinshall, Flexible Syntactic Matching of Curves and Its Application to Automatic Hierarchical Classification of Silhouttes, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 1999. p. 1313/1328. 26. Dmitry B. Goldgof, Hua Lee, and T.S. Huang, Motion Analysis of Nonrigid Surfaces, in IEEE Transactions on Pattern Analysis and Machine Intelligence. 1988. p. 375/380. 27. Sanjoy K. Mishra, Dimitry B. Goldgof, and T.S. Huang. Motion Analysis and Epicardial Deformation Estimation from Angiography