La compression/décompression

La compression fractale par la méthode de Delaunay possède deux particularités. D'une part la segmentation des figures destinations est générée par un triangulation de Delaunay, et d'autre part, un processus de Division et Fusion (Split and Merge) a été ajouté. La compression par subdivision de triangle elle ne possèdait que le processus de division, la fusion n'était pas concevable avec un pavage régulier de triangle. Mais avec une triangulation de Delaunay dynamique, la fusion est possible.

En somme, seule la partition Destination est modifiée. Le processus de compression - décompression reste identique à celui évoqué dans la première partie du document, en considérant des figures triangulaires.

Mais revenons à la partition des figures destinations. Voici les étapes de la création de ce pavage :

$\begin{algorithm} % latex2html id marker 566 [H] \begin{algorithmic}[1] \par \F... ...end{algorithmic} \caption{Calcul de la partition Destination} \end{algorithm}$

$\begin{algorithm} % latex2html id marker 576 [H] \begin{algorithmic}[1] \par \F... ...rithmic} \caption{Division = Insertion d'un germe de Voronoï} \end{algorithm}$

$\begin{algorithm} % latex2html id marker 586 [H] \begin{algorithmic}[1] \par \F... ...rithmic} \caption{Fusion = Suppression d'un germe de Voronoï} \end{algorithm}$

Comme pour la compression par subdivision de triangles, nous devons aussi stocker les informations sur le partitionnement de Destination. Mais au lieu de stocker des booléens représentant la division d'un triangle, la compression de Delaunay impose de préciser les différentes coordonnées des germes du diagramme de Voronoï. Ainsi, la triangulation de Delaunay pourra être recréée à partir de ces germes.

Remarque : Le nombre de Division doit être surveillé, car il s'agit d'un algorithme presque récursif, et le nombre de germes de Voronoï augmente très rapidement ! Apres 2000 points, l'algorithme de Triangulation de Delaunay que nous avons utilisés devient assez long.

Pour illustrer cette divergence, voici un exemple du partitionnement effectué sur lena.jpg, avec 50 germes initialement déposés, 2 divisions et une fusion.

Debut

Split1

Split2

Merge Nombre de points

Nombre de sites de Voronoï, 2 éclatements + 1 fusion

Avec une troisième division, nous arrivons à 5000 sites, ce qui est assez conséquent. Cependant, il est à noter que plus le nombre de germes augmente et plus le niveau de détail de l'image reconstruite augmente, car ces points permettent de localiser les détails de l'image, comme le montre la figure ci-desous.

**Figure 4.5:** Pavages Source et Destination, Méthode de Delaunay
$\begin{figure} \begin{center} \epsfig{file=lena_sub_src.eps,scale=0.7} %\\ ... ...sfig{file=lena_del_dest_2_2.eps,scale=0.7} %\\ \end{center} \end{figure}$

Ce que nous pouvons dire sur la figure de droite est que les zones homogènes sont composées de triangles assez grands (notamment au dessus du chapeau de lena, et à droite de l'image). Les détails sont quant à eux localisés par de plus petits triangles (les cheveux de lena). C'est justement cette propriété que nous cherchions, l'algorithme de Divide and Merge sur une triangulation de Delaunay est donc validé.

Cependant, nous observons aussi que le pavage des triangles de Delaunay ne recouvre pas l'image entièrement ! Nous observerons les conséquences de ce non recouvrement dans la partie Test et résultats.