1
Laboratoire de Recherche et Développement
d'EPITA
14-16, rue Voltaire, 94276 Le Kremlin-Bicêtre
cedex, France
thierry.geraud@epita.fr
2
Service Hospitalier Frédéric
Joliot, CEA
4, place du Général Leclerc, 91401 Orsay cedex, France
mangin@shfj.cea.fr
Dans cet article, nous nous intéressons aux techniques de programmation d'algorithmes de traitement d'images sous le jour de la réutilisabilité de ces algorithmes vis-à-vis du type des données et de celui des structures de données qui peuvent supporter ces algorithmes. Nous allons illustrer nos propos sur deux exemples très simples de traitement : l'ajout d'une constante à la valeur des éléments d'un agrégat (par exemple les points d'une image) et un filtre moyenneur sur un agrégat. Nous verrons finalement qu'une écriture totalement générale de ces algorithmes est possible en C++ grâce à la généricité et au polymorphisme générique ; nous verrons également que cette écriture n'entraîne pas de surcoût significatif en temps d'exécution et qu'elle est proche de la description en langage naturel de ces algorithmes.
Le code que nous citons dans cet article (disponible à partir de l'adresse http://www.epita.fr/~lrde) est volontairement simplifié afin d'augmenter la compréhensibilité des techniques de programmation que nous présentons.
L'avantage de cette écriture est de fournir une unique définition par type de structure de données, et ce quel que soit le type des données [2] ; en conséquence, un algorithme de traitement sur une structure de données se traduit par une unique fonction. Pour que l'addition soit supportée pour les images 2D dont le type des données est codé en char, une routine spécifique à ce type doit être écrite dans la fonction ad hoc, comme le montre la table 2.Table 1
Définition impérative d'une structure.
typedef struct { int nRows; int nColumns; type_t type; void* data; } Image2D;
T traitements, S types de structures et D types de données peuvent donner lieu à l'écriture de T× S× D routines différentes. Afin de réduire cette combinatoire, de nombreuses bibliothèques limitent le nombre de types de données et de structures de données manipulables par l'utilisateur, et restreignent l'applicabilité de la plupart des traitements à un petit nombre de types de structures et de données. Ainsi, pour les types de structures de données, la plupart des bibliothèques gèrent les images 2D, quelquefois les images 3D, et rarement les graphes d'adjacence de régions. On trouve pour les types de données, du plus classique au moins fréquent, les entiers non signés et signés sur 8 et 16 bits, les flottants, les booléens, les couleurs en rouge vert bleu avec des composantes entières non signées sur 8 et 16 bits.Table 2
Addition en langage impératif.
void add( Image2D* image, void* val ) { int iRow, iColumn; switch ( image->type ) { case CHAR: char** dataChar = toChar2D( image ); char valChar = toChar( val ); for ( iRow = 0; iRow < image->nRows; ++iRow ) for ( iColumn = 0; iColumn < image->nColumns; ++iColumn ) dataChar[iRow][iColumn] += valChar; break; //... } }
L'écriture traditionnelle en programmation procédurale entraîne donc une réutilisabilité presque nulle : introduire dans une telle bibliothèque un nouveau type de données ou de structure de données, ou un nouveau traitement impose un effort de réécriture qui se traduit la plupart du temps par des ``copier-coller-modifier'' manuels.
Les traitements sont paramétrés de la même façon, Cf. table 4. A partir de ce code, dit générique, le compilateur construit automatiquement les déclinaisons nécessaires. La déclaration Image2D<char> image et l'appel add( image, 3 ) va ainsi forcer la compilation de la classe Image2D<char> et de la fonction add( Image2D<char>&, char ) ; la routine de la section 2, dédiée à un type de données particulier, est donc produite automatiquement.Table 3
Définition générique d'une structure.
template<class Data> class Image2D { int nRows; int nColumns; Data** data; // ... };
La programmation générique présente deux avantages : le typage est fort (tout void* disparaît) et l'écriture de traitements devient indépendante du type des données. Pour le programmeur, la combinatoire est ainsi réduite à T× S routines ; en revanche, toute fonction est encore dépendante du type de structures de données (ici, image 2D).Table 4
Addition en programmation générique.
template<class Data> void add( Image2D<Data>& image, Data val ) { int iRow, iColumn; for ( iRow = 0; iRow < image.nRows; ++iRow ) for ( iColumn = 0; iColumn < image.nColumns; ++iColumn ) image.data[iRow][iColumn] += val; }
Les considérations que nous allons porter dans la suite de cet article sont à notre connaissance originales, l'ensemble des outils de traitement d'images que nous avons trouvés sur Internet n'utilisant pas les techniques que nous allons présenter.
Dans [3], une modélisation des itérations sur des agrégats est donnée ; nous l'adaptons ici à notre problématique. Deux classes abstraites sont définies : Aggregate<Data> et Iterator<Data>, qui représentent respectivement un agrégat d'éléments de type Data et un itérateur sur cet agrégat. La première classe déclare une méthode abstraite createIterator() pour l'instantiation d'un itérateur et la seconde un jeu de méthodes pour la manipulation d'un itérateur : void first() pour initialiser sa position sur un premier élément de l'agrégat, bool isDone() pour savoir s'il a terminé de parcourir l'agrégat, Data& value() pour récupérer la valeur de l'agrégat correspondant à sa position courante, void next() pour le déplacer à l'élément suivant de l'agrégat. De ces deux classes abstraites dérivent respectivement les classes concrètes et spécialisées : Image2D<Data> et Image2DIterator<Data>. Un itérateur sur les points d'une image 2D possède trois attributs : les indices de ligne et de colonne du point courant et la référence à l'image 2D sur les points de laquelle il itère.
Avec cette modélisation, l'écriture de l'addition ne fait intervenir que les classes abstraites comme le montre la table 5. Un procédé de liaison dynamique se charge à l'exécution d'appeler les méthodes spécifiques aux types effectifs, dits types dynamiques. Ainsi, avec la déclaration Image2D<char> image et l'appel add(image,3), la méthode createIterator() exécutée est celle de la classe Image2D<char>, le type dynamique de iter est Image2DIterator<Data> et les méthodes d'itération exécutées sont effectivement celles d'un itérateur sur une image 2D.
Considérons maintenant l'exemple d'un filtre moyenneur. Nous pouvons définir deux nouveaux types d'itérateurs : un itérateur suiveur et un itérateur de voisinage. Avec une macro for_each simplifiant l'écriture de la boucle for de la table 5, une écriture par polymorphisme classique est donnée en table 6. Ici, inputElt itère sur les éléments de l'agrégat en entrée, neighborElt itère sur le voisinage de l'élément courant de l'agrégat en entrée et outputElt itère sur l'agrégat en sortie de façon équivalente à l'agrégat en entrée.Table 5
Addition par polymorphisme classique.
template<class Data> void add( Aggregate<Data>& aggregate, Data val ) { Iterator<Data>& iter = aggregate.createIterator(); for ( iter.first(); ! iter.isDone(); iter.next() ) iter.value() += val; }
Cette technique, qui recourt à l'héritage et à la redéfinition de méthodes, est le polymorphisme que nous qualifierons de classique. Dans nos exemples, il permet de déduire du type de l'agrégat, argument des fonctions de traitement, les itérateurs adéquats. Ainsi, nous nous affranchissons à la fois du type de données et du type de structures de données. La combinatoire est donc minimale (T), un traitement étant programmé une fois pour toutes. De plus, ce code est relativement proche d'une description algorithmique en langage naturel.Table 6
Moyenneur par polymorphisme classique.
template<class Data> void mean( Aggregate<Data>& inputAggregate, Aggregate<Data>& outputAggregate ) { Iterator<Data> & inputElt = inputAggregate.createIterator(), & neighborElt = inputElt.createNeighborIterator(), & outputElt = outputAggregate.createFollowerIterator( inputElt ); for_each( inputElt ) { Data sum = 0; for_each( neighborElt ) sum += neighborElt.value(); outputElt.value() = sum / neighborElt.getCard(); } }
Afin d'estimer le coût de ces indirections, nous avons réalisé
des tests de performance. Le premier test correspond à l'addition
d'une constante sur une image 2D comportant 8 millions de points ; le second
test correspond à un filtrage par la moyenne sur un 6-voisinage
d'une image 3D de 8 millions de points. Les résultats (obtenus avec
un PC à 333 MHz sous Linux et avec le compilateur libre egcs
(disponible pour de nombreuses plateformes à l'adresse http://egcs.cygnus.com/))
sont donnés par le tableau 7. L'utilisation
du polymorphisme classique est rédhibitoire, la répétition
des appels aux méthodes first(), isDone(), value()
et next() étant très coûteuse.
Le polymorphisme classique est une solution intéressante pour s'affranchir du type de la structure de données lors de l'écriture de traitements ; cependant, dans le cadre du traitement d'images où le nombre de points peut être élevé, cette approche ``classique'' du paradigme objet est inadaptée.Table 7
Performance comparée des différentes techniques de programmation.
approche
impérativepolymorphisme
classiquepolymorphisme
génériqueaddition 0.5 s 1.5 s 0.8 s moyenneur 3.5 s 11.4 s 3.9 s
Table 8
Déclaration de types déduits.
template<class Data> class Image2D { public: typedef Data DataType; typedef Image2DIterator<Data> Iterator; typedef Image2DFollowerIterator<Data> FollowerIterator; typedef Image2DNeighborIterator<Data> NeighborIterator; // ... };
La définition des classes abstraites Aggregate<Data> et Iterator<Data> n'est plus nécessaire et tout héritage devient obsolète. Chaque méthode correspond ici à un type d'objet concret et connu lors de la compilation ; le surcoût lié au polymorphisme classique est donc éliminé.Table 9
Moyenneur par polymorphisme générique.
template<class Aggregate> void mean( Aggregate& inputAggregate, Aggregate& outputAggregate ) { typename Aggregate::Iterator inputElt( inputAggregate ); typename Aggregate::NeighborIterator neighborElt( inputElt ); typename Aggregate::FollowerIterator outputElt( outputAggregate, inputElt ); for_each( inputElt ) { typename Aggregate::DataType::CumulType sum = 0; for_each( neighborElt ) sum += neighborElt.value(); outputElt.value() = sum / neighborElt.getCard(); } }
De plus, le langage C++ offre un mécanisme qui permet au compilateur de remplacer les appels de méthodes par le corps de ces méthodes lorsqu'elles ne sont pas polymorphes. Si la fonction mean() de la table 9 est utilisée pour le type d'agrégat Image2D<IntegerS8>, la compilation correspondante sera rigoureusement équivalente à celle du code de la table 10.
Au final, les temps d'exécution des algorithmes de traitement ne présentent que de très légers surcoûts par rapport à ceux d'écritures traditionnelles, comme en témoigne le tableau 7. Le polymorphisme générique est donc une solution adaptée à la problématique de l'écriture d'algorithmes généraux, appliquables à des types de données et de structures de données variés.Table 10
Code déduit de la table 9 par le compilateur.
void mean( Image2D<IntegerS8>& inputAggregate, Image2D<IntegerS8>& outputAggregate ) { int iRow, iColumn; // inputElt attributes int iNeighbor; // neighborElt attribute iRow = iColumn = 0; // inputElt.first() while ( iRow != inputAggregate.nRows ) // ! inputElt.isDone() { IntegerS16 sum = 0; iNeighbor = 0; // neighborElt.first() while ( iNeighbor != 4 ) // ! neighborElt.isDone() { sum += inputAggregate.data[iRow + delta[iNeighbor].iRow] [iColumn + delta[iNeighbor].iColumn]; // neighborElt.value() ++iNeighbor; // neighborElt.next() } outputElt.data[iRow][iColumn] // outputElt.value() = sum / 4; // neighborElt.getCard() if ( ++iColumn == inputAggregate.nColumns ) iColumn = 0; ++iRow; // inputElt.next() } }
A propos des types de données, un même type prédéfini du langage peut servir à implanter des types de données de sémantiques différentes (par exemple, un entier non signé codé sur 8 bits peut aussi représenter une valeur floue discrétisée) ; pour effectuer leur distinction, qui conduit à des variantes d'implémentations, il est nécessaire de définir les types de données sous forme de classes. Ainsi la classe IntegerS8 remplace avantageusement le type char dans la table 9 ; en particulier, le type de la variable sum servant au cumul de valeurs s'en déduit.
Nous développons actuellement une plateforme de traitements d'images qui utilise de façon hybride, en fonction des performances attendues, polymorphismes classique et générique. Sans modifier l'écriture simple des traitements, nous avons également obtenu deux formes supplémentaires de généricité n'entraînant pas de surcoût significatif à l'exécution : l'application de tout traitement peut être restreinte aux éléments d'un agrégat qui vérifient un prédicat donné et peut concerner uniquement un champ des données (par exemple la composante rouge de RVB).
This document was translated from LATEX by HEVEA.