Algorithme cellulaire, itératif et asynchrone d'estimation de mouvement

Algorithme cellulaire, itératif et asynchrone d'estimation de mouvement

A Cellular Iterative and Asynchronous Motion Algorithm

Patricia Planet

LIME, UJF/ISTG/31, Bt D de Physique 122, rue de la Piscine – Domaine Universitaire, BP 53 F-38041 Grenoble cedex 9

Page: 
25-29
|
Received: 
N/A
| |
Accepted: 
N/A
| | Citation

OPEN ACCESS

Abstract: 

The growth of visual communication involves needs for image compression that are more and more important. It seems that futur coders will be based on the structural and semantic relevance of the image contents into play, instead of classical information - theoretic waveform coding.

In this work we apply theoretic concept of Markov modelisation and mean field annealing to the motion analysis problem. Our aim is to obtain a motion estimation algorithm highly parallelisable and dedicated, first, to error prediction minimization and second, to motion analysis problem. We obtain a cellular and iterative algorithm. Such an algorithm can be implemented on array processors with locally mesh connections.

The second part of this work is based on asynchronous iteration . This iteration mode is very suitable for architectural problem. We will see that the convergence of the algorithm in this iteration mode is verified. This part is an illustration of benefits of algorithms and architectures interactions.

Résumé

La communication visuelle est en pleine expansion, l'avènement du multimédia et ses besoins en images dynamisent fortement la recherche dans les domaines du codage et de la compression d'images. Il semble que les codeurs futurs seront basés sur des techniques de codage par modèles . Il s'agit à ce niveau essentiellement d'analyse et de synthèse d'images. Cependant toute analyse d'images dépend de primitives utilisant les caractéristiques obtenues par des traitements d'images dits de « bas - niveau» (ou niveau pixel), en particulier l'estimation de mouvement est une primitive de traitement bas-niveau extrèmement importante dans le domaine du codage d'images.

Une première partie de cet article est consacrée à l'étude d'un algorithme cellulaire et itératif d'estimation de mouvement , algorithme développé à partir d'une modélisation markovienne du champs de vecteurs mouvement et d'une méthode de relaxation déterministe. Nous montrons qu'il est possible d'obtenir un champ de vecteurs mouvement apportant un très bon compromis entre la minimisation de l'erreur de prédiction et la cohérence du champ de vecteurs (critères à prendre en compte pour respectivement la réduction de l'information temporelle dans les codeurs classiques, ou l'analyse de scène dans les nouveaux codeurs).

La seconde partie décrit l'étude de cet algorithme d'estimation de mouvement dans un mode de fonctionnement peu ordinaire qui est I'asynchronisme. Ce mode peut être particulièrement intéressant si on vise une implémentation massivement parallèle d'un tel algorithme. L'asynchronisme possède des atouts architecturaux irréfutables et, nous le verrons, des atouts fonctionnels intéressants, montrant ainsi que l'étroite adéquation algorithmes-architectures est très importante et souvent bénéfique.

Keywords: 

Image processing, Motion estimation, Cellular and interative algorithm, Asynchronism, Parallelism

Mots clés

Traitement d'image, Estimation de mouvement, Algorithme cellulaire itératif, Asynchronisme, Parallélisme

1. Introduction
2. Algorithme