Les différents codages de formes

Les différents codages de formes

Le code de Freeman [Fre74] a comme but premier la compression des données. En effet, il permet de passer d’une image binaire, dont on mémorise la valeur du niveau de gris (0 ou 1) de chaque pixel, à une chaîne de codants d’une part et aux coordonnées d’un point du contour de l’objet d’autre part. Il est également possible d’utiliser le code de Freeman différentiel compressé grâce au code de Huffman [Liu] pour augmenter encore le taux de compression. Dans ce chapitre, nous présenterons d’abord les codes de contour les plus connus, puis d’autres codes visant à compresser les images binaires et enfin le code de Freeman en détail. e1, qui correspond à un virage à gauche pour sortir de l’objet étudié et le 0 associé à un virage à droite pour entrer dans l’objet étudié. L’algorithme 1 présente la méthode d’obtention du code d’un contour selon le code de Papert. Dans cet algorithme, à la ligne 1, la localisation du premier point de la frontière interne peut se faire, grâce à la détection du premier point allumé par exemple au sens du balayage éléctronique (Voir figure 1.21 page 17). Du fait du choix de tourner à gauche lorsqu’on se trouve dnas l’objet et à droite lorsqu’on se trouve à l’extérieur, le parcours de la frontière se fait dans le sens horaire.

Le code introduit par E. Bribiesca ([Bri99]et[Bri00]) permet de coder une surface discrète en trois dimensions afin d’en obtenir les caractéristiques. Cette surface ayant été extraite auparavant, on la considère comme une courbe faisant le tour de l’objet de départ (Voir l’illustration figure 1.4 page 5 issue de la publication de [Bri00]). On parle alors de courbe ou de surface par abus de langage. Cette courbe est composée de segments non épais de taille égale à un côté de pixel. Les frontières d’un objet quelconque en trois dimensions peuvent être représentées par ce genre de chaîne. L’alphabet de cette représentation est composé uniquement de cinq symboles correspondant aux cinq variations possibles de directions orthogonales dans l’espace. Chacun de ces symboles est représenté par un nombre et illustré sur la figure 1.3 page suivante. La chaîne représentative d’une courbe est obtenue en calculant les changements relatifs de direction autour de la courbe. On obtient donc une chaîne composée d’un nombre fini d’éléments que l’on pourra coder en base 5. La longueur L de la courbe sera donc L =(n+2)p avec n le nombre de codes dans la chaîne et p la longueur d’un segment (ici égal à un côté de pixel). Une surface en trois dimensions représentée par un ensemble de voxels peut ainsi être codée par la courbe entourant cette surface. Un exemple issu de la publication de [Bri00]est donné figure 1.4 page ci-contre où l’on voit à gauche l’objet en volume à coder et à droite la succession des arêtes par lesquelles la courbe décrit la surface de cet objet.

L’étude de E. Bribiesca [Bri00] a été poursuivie en 2005 par H. Sanchez-Cruz [San05] en n’utilisant plus que trois des cinq symboles initiaux afin de rester dans le plan. Une représentation graphique de l’alphabet de ce code correspondant à ces trois changements de direction est donnée figure 1.5. Voici ce à quoi ils correspondent : En 1999, E. Bribiesca [Bri99] a présenté un autre moyen de coder les contours de formes : le Vertex Chain Code ou VCC. Le principe est de compter le nombre de sommets à l’intérieur de l’objet, et touchant le sommet considéré. Pour améliorer la compression, chacun de ces nombres est décrémenté d’une unité. Dans le cas des pixels d’une image en trame carrée, il existe trois possibilités décrites respectivement par les symboles 0, 1 et 2. L’alphabet de ces symboles, correspondant res- pectivement à un, deux et trois sommets à l’intérieur de l’objet, est représenté figure 1.7.signifie que la longueur de ce segment représente p% du périmètre de l’objet (supposé fermé) et la dernière (d − θ) signifie que l’angle formé par ce segment et l’axe des x est de θ degrés En plus des connaissances a priori qu’elle requiert, cette méthode est en quelque sorte une vectorisation et ne code plus tous les pixels de la frontière de l’objet. Pour ces raisons, l’obtention du code n’est pas aussi simple et rapide que dans les cas vus précédemment et nous avons décidé de ne pas approfondir l’étude de ce code.