Le projet proposé ici consiste à développer en ADA des paquetages génériques sur les arbres
n-aires et quaternaires. Ces paquetages seront réutilisés pour implanter un autre
paquetage permettant de faire de la compression et décompression d'images.
Les opérations que l'on doit faire sur un arbre n-aire se classent en 3 catégories:
création, consultation et modification. Voici la liste des procédures à implanter.
An_Changer_Valeur: qui change la valeur rangée à la racine d'un arbre.
An_Inserer_Fils: qui insère un arbre sans frère en position de premier
fils d'un arbre a. L'ancien fils de a devient le premier frère de l'arbre inséré.
An_Inserer_Frere: qui insère un arbre sans frère en position de premier
frère d'un arbre a.
An_Supprimer_Fils: qui supprime le nième fils d'un arbre a.
An_Supprimer_Frere: qui supprime le nième frère d'un arbre a.
An_Changer: qui applique une fonction à chaque élément de l'arbre.
Un noeud est représenté par un enregistrement contenant la valeur de la racine,
un pointeur sur le premier fils, un pointeur sur le frère et un pointeur sur le père
de l'arbre. Le type arb_nr est mis en private pour cacher à l'utilisateur du
paquetage la structure de données choisie pour représenter l'arbre n-aire.
Nous avons choisi de
passer en paramètres génériques le type de la valeur de la racine, la procédure
qui permet d'afficher un élément et la fonction qui sera appliquée à chaque élément :
Pour l'affichage de l'arbre, nous utilisons une procédure auxiliaire récursive
qui permettra de parcourir l'arbre.
La procédure auxiliaire est la suivante.
Nous parcourons tout d'abord dans le sens des premiers fils avec un décalage dans
l'affichage puis dans le sens
des frères en gardant le même décalage pour tous les frères.
Nous utilisons ici aussi une procédure auxiliaire qui permettra de parcourir l'arbre
dans les deux sens de récursivité, fils et frères.
La procédure auxiliaire est la suivante. Nous nous servons d'un booléen passé en
données/résultats pour terminer les appels récursifs dans le cas où la valeur est
trouvée. Si elle n'est pas trouvée, arb_cour sera un pointeur null.
Les arbres quaternaires étant une sous-catégorie des arbres n-aires, nous
définissons un type arbre quaternaire sous-type des arbres n-aires. Les
paramètres génériques sont les mêmes que ceux du paquetage arbre n-aire.
Nous utilisons la directive ADA "renames" dans la partie spécification qui
nous permet de réutiliser les procédures et fonctions implantés dans le paquetage arbre n-aire.
exemple:
Nous faisons de même pour les exceptions:
Nous définissons une exception filsq_vide pour la procédure Aq_Construire.
Le but est de compresser et décompresser une image en utilisant un
arbre quaternaire. Les images que nous utilisons sont carrées et leur
dimension est une puissance de 2. Une couleur est définie à partir des
3 couleurs de base rouge, vert, bleu et est codée sur un entier.
Le principe d'encodage récursif d'une image de dimension n est le
suivant: si l'image est homogène, on crée une feuille
dont la valeur est la couleur de l'image. Si l'image n'est pas homogène,
on la découpe en 4 sous-images de dimension n/2, et on crée un arbre
quaternaire dont les quatre fils sont les encodages des quatre sous-images.
En parcourant en profondeur l'arbre quaternaire, nous obtenons une suite
de valeurs représentant l'image compressée.
Il est demandé de réaliser un paquetage permettant de:
créer ue image à partir d'une dimension et d'une matrice.
Nous choisissons de représenter une couleur par une valeur codée sur 32 bits
(pixel). L'image est une matrice de pixels. Nous utilisons des
tableaux non contraints.
Nous détaillons ici la fonction est_homogene en distinguant 3 cas : la
tolérance est minimale (0), maximale(100) ou entre les deux. Si elle est
maximale, alors nous retournons le booléen égal à true et une feuille est crée
avec la couleur moyenne de la zone concernée (cf procédure im_to_arb). Si elle est minimale, on s'assure que tous
les pixels ont la même valeur. Enfin, pour le cas intermédiaire, nous regardons
si l'inégalité abs(couleur_primaire-moyenne) <= tolerance est vérifiée pour
chaque pixel et couleur primaire.
Il s'agit tout d'abord de construire l'arbre à partir de la séquence
encodée (procédure charger_im_encod et imc_to_arb) puis de reconstruire l'image à
partir de cet arbre (procédure arb_to_im).
Nous devons reconstituer l'image à partir de l'arbre. l'arbre est arb_im et
l'image résultante est im. Nous nous servons des indices i_d,i_f,j_d,j_f
pour obtenir le décalage entre les appels récursifs.
Les programmes de test main_arb_nr.adb et main_arb_quater.adb utilisent
respectivement les paquetages arb_nr.db et arb_quater.adb. Il est possible
de construire un arbre pour vérifier le bon fonctionnement des différentes
procédures et fonctions.
Le programme de test main_pimage.adb permet de créer une image
pour valider la compression et décompression. L'affichage des couleurs de
cette image est représentée sur la figure suivante:
Figure 1 : Contenu de l'image test 8x8
Sa taille est égale à 260 octets (64*4+4) car nous stockons aussi la
dimension. On vérifie maintenant la compression. Nous prenons en compte une tolérance pour
déterminer si une image est homogène. L'arbre construit avec une tolérance minimale (0)
est représenté sur la figure suivante:
Figure 2 : Affichage de l'arbre obtenu pour la compression avec une tolérance minimale
La taille de l'image compressée est égale à 104 octets (25*4+4) dont 4 octets pour
la dimension, ce qui est bien le résultat attendu.
Pour une tolérance maximale (100), nous obtenons une feuille avec la couleur moyenne de
l'image (161) car celle-ci est considérée comme homogène d'après le critère dans la
fonction est_homogene.
Avec une tolérance égale à 80, nous obtenon l'arbre suivant :
Figure 3 : Affichage de l'arbre obtenu pour la compression avec une tolérance de 80
Nous remarquons qu'il y aura une perte d'information par rapport à l'image test dans la décompression
car la partie Nord Ouest de l'image est considérée comme homogène avec cette tolérance. Ceci
est illustré sur la figure suivante :
Figure 4 : Contenu de l'image test 8x8 décompréssée avec une tolérance initiale de 80
Nous enregistrons pour chaque cas l'image compréssée puis vérifions la décompression.
Ce projet nous a permis de créer un paquetage permettant de faire de la
compression et décompression d'images. Les opérations implantées pour les
arbres quaternaires ont été réutilisées et validées dans l'algorithme
d'encodage.
![\begin{lstlisting}[language=ada]
type noeud;
type arb_nr is access noeud;
type n...
...emier_fils: arb_nr;
frere: arb_nr;
pere: arb_nr;
end record;
\end{lstlisting}](n7_report/img1.png)
![\begin{lstlisting}[language=ada]
generic
type T is private;
with procedure ecrire ( a: in T );
with function fonction_main ( a: in T) return T;
\end{lstlisting}](n7_report/img2.png)
![\begin{lstlisting}[language=ada]
function An_Creer_Vide return arb_nr isbeginreturn null;end An_Creer_Vide;
\end{lstlisting}](n7_report/img3.png)
![\begin{lstlisting}[language=ada]
function An_Creer_Feuille ( valeur : in T ) ret...
...;
a.frere:=null;
a.pere:=null;
return a;end An_Creer_Feuille;
\end{lstlisting}](n7_report/img4.png)
![\begin{lstlisting}[language=ada]
function An_Vide ( a: in arb_nr ) return boolean isbeginreturn (a=null);end An_Vide;
\end{lstlisting}](n7_report/img5.png)
![\begin{lstlisting}[language=ada]function An_Valeur ( a: in arb_nr ) return T i...
...ion
when constraint_error => raise arbre_vide;end An_Valeur;\end{lstlisting}](n7_report/img6.png)
![\begin{lstlisting}[language=ada]
function An_Pere ( a: in arb_nr ) return arb_nr...
...nte_vide;
else
return a.pere;
end if;
end if;end An_pere;\end{lstlisting}](n7_report/img7.png)
![\begin{lstlisting}[language=ada]
function An_Fils ( a: in arb_nr; n: in integer ...
...tion
when constraint_error => raise parente_vide;
end An_Fils;
\end{lstlisting}](n7_report/img8.png)
![\begin{lstlisting}[language=ada]
function An_Frere ( a: in arb_nr; n: in integer...
...ion
when constraint_error => raise parente_vide;
end An_Frere;
\end{lstlisting}](n7_report/img9.png)
![\begin{lstlisting}[language=ada]procedure An_Afficher( a: in arb_nr ) isbegi...
...t('' '');
An_Afficher_Aux(a,'' '');
end if;end An_Afficher;\end{lstlisting}](n7_report/img10.png)
![\begin{lstlisting}[language=ada]procedure An_Afficher_Aux( a: in arb_nr ; str_...
...(a.frere,str_decal);
end if;end if;end An_Afficher_Aux;\end{lstlisting}](n7_report/img11.png)
![\begin{lstlisting}[language=ada]function An_Rechercher ( a: in arb_nr; e: in T...
...arret);
return arb_cour;
end if;
end if;end An_Rechercher;\end{lstlisting}](n7_report/img12.png)
![\begin{lstlisting}[language=ada]procedure An_Rechercher_Aux ( arb :in arb_nr ;...
...else null;
end if;
end if;
end if;end An_Rechercher_Aux;\end{lstlisting}](n7_report/img13.png)
![\begin{lstlisting}[language=ada]function An_Nombre_Fils( a: in arb_nr ) return...
...turn n;
else
return 0;
end if;
end if;end An_Nombre_Fils;
\end{lstlisting}](n7_report/img14.png)
![\begin{lstlisting}[language=ada]
function An_Est_Feuille( a: in arb_nr )return b...
...when constraint_error => raise arbre_vide;end An_Est_Feuille;
\end{lstlisting}](n7_report/img15.png)
![\begin{lstlisting}[language=ada]function An_Est_Racine( a: in arb_nr )return b...
... when constraint_error => raise arbre_vide;end An_Est_Racine;
\end{lstlisting}](n7_report/img16.png)
![\begin{lstlisting}[language=ada]
procedure An_Changer_Valeur ( a:in out arb_nr; ...
... constraint_error => raise arbre_vide;end An_Changer_Valeur;\end{lstlisting}](n7_report/img17.png)
![\begin{lstlisting}[language=ada]procedure An_Inserer_Fils ( arb: in out arb_nr...
...er_fils:=arb_i;
end if;
end if;
end if;end An_Inserer_Fils;
\end{lstlisting}](n7_report/img18.png)
![\begin{lstlisting}[language=ada]
procedure An_Inserer_Frere( arb: in out arb_nr ...
...re;
arb.frere:=arb_i;
end if;
end if;end An_Inserer_Frere;\end{lstlisting}](n7_report/img19.png)
![\begin{lstlisting}[language=ada]
procedure An_Supprimer_Fils ( a: in out arb_nr ...
....frere:=a_s;
end if;
end if;
end if;end An_Supprimer_Fils;\end{lstlisting}](n7_report/img20.png)
![\begin{lstlisting}[language=ada]
procedure An_Supprimer_Frere ( a :in out arb_nr...
...rien
when constraint_error => null;end An_Supprimer_Frere;\end{lstlisting}](n7_report/img21.png)
![\begin{lstlisting}[language=ada]
procedure An_Changer( a: in out arb_nr ) isbe...
....premier_fils);
An_Changer(a.frere);
end if;end An_Changer;
\end{lstlisting}](n7_report/img22.png)
![\begin{lstlisting}[language=ada]
function Aq_Creer_Vide return arb_quat renames An_Creer_Vide;
\end{lstlisting}](n7_report/img23.png){kind=small}
![\begin{lstlisting}[language=ada]
-- arbre vide
arbreq_vide: exception renames ar...
... pas de parenté
parenteq_vide: exception renames parente_vide;
\end{lstlisting}](n7_report/img24.png)
![\begin{lstlisting}[language=ada]----------------------------------------------...
...);
An_Inserer_Fils(arb_res,a_no);end if;end Aq_Construire;
\end{lstlisting}](n7_report/img25.png)
![\begin{lstlisting}[language=ada]
function Aq_Nord_Ouest( a: in arb_quat ) return arb_quat isbeginreturn An_fils(a,1);end Aq_Nord_Ouest;\end{lstlisting}](n7_report/img26.png)
![\begin{lstlisting}[language=ada]
-- sous type arb_im
subtype arb_im is arb_quat...
...e image is array (integer range <>,integer range <>) of pixel;\end{lstlisting}](n7_report/img27.png)
![\begin{lstlisting}[language=ada]----------------------------------------------...
...(-1,a_no,a_ne,a_so,a_se,a);end if;
end if;end im_to_arb;\end{lstlisting}](n7_report/img28.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...=i+1;
end loop;
return result;
end case;end est_homogene;\end{lstlisting}](n7_report/img29.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...ite(f,n);
arb_to_imc(a,f);
close(f);end enregistrer_imagec;\end{lstlisting}](n7_report/img30.png)
![\begin{lstlisting}[language=ada]----------------------------------------------...
...1),f);
arb_to_imc(Aq_Frere(a,1),f);
end if;end arb_to_imc;\end{lstlisting}](n7_report/img31.png)
![\begin{lstlisting}[language=ada]procedure charger_im_encod( a: out arb_im ; n:...
...m);
n:=dim;
a:=imc_to_arb(f);
close(f);end charger_im_encod;\end{lstlisting}](n7_report/img32.png)
![\begin{lstlisting}[language=ada]function imc_to_arb( f: in pack_pixel.file_typ...
...(-1,a_no,a_ne,a_so,a_se,a);
end if;
return a;end imc_to_arb;
\end{lstlisting}](n7_report/img33.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...f,j_f-(j_f-j_d+1)/2+1,j_f);end if;end if;end arb_to_im;\end{lstlisting}](n7_report/img34.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...se
im(i,j):=1;
end if;
end loop;
end loop;end thresh_im;\end{lstlisting}](n7_report/img35.png)
