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.
Un arbre n-aire est un arbre dont les noeuds peuvent avoir un nombre quelconque de
fils.
Un arbre n-aire est représenté par:
- Une valeur à la racine de l'arbre
- Un arbre père
- Un arbre fils
- Un arbre frère
Cette structure devra être implantée à l'aide de pointeurs.
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_Creer_Vide: crée un arbre n-aire vide.
- An_Creer_Feuille: crée un arbre n-aire avec une valeur, mais sans fils, ni
frere, ni pere.
- An_Vide: qui détecte si un arbre est vide ou non.
- An_Valeur: qui retourne la valeur rangée à la racine d'un arbre.
- An_Pere: qui retourne l'arbre père d'un arbre.
- An_Fils: qui retourne l'arbre nième fils d'un arbre.
- An_Frere: qui retourne l'arbre nième frère d'un arbre.
- An_Afficher: qui affiche le contenu complet de l'arbre.
- A_Rechercher: qui recherche une valeur dans un arbre et retourne
l'arbre dont la valeur est racine si elle est trouvée, un arbre vide sinon.
- An_Nombres_Fils: qui retourne le nombre de fils au premier niveau
d'un arbre.
- An_Est_Feuille: qui indique si un arbre est une feuille (pas de fils).
- An_Est_Racine: qui indique si un arbre est sans père.
- 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.
![\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}](img1.png)
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
![\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}](img2.png)
Nous allons décrire les procédures et les fonctions que nous avons conçus.
![\begin{lstlisting}[language=ada]
function An_Creer_Vide return arb_nr isbeginreturn null;end An_Creer_Vide;
\end{lstlisting}](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}](img4.png)
![\begin{lstlisting}[language=ada]
function An_Vide ( a: in arb_nr ) return boolean isbeginreturn (a=null);end An_Vide;
\end{lstlisting}](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}](img6.png)
Nous levons l'exception arbre_vide s'i y a une constraint_error. Nous la laissons
se propager jusqu'au programme de test où elle sera traitée.
![\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}](img7.png)
Si l'arbre n'a pas de père, on lève l'exception parente_vide.
![\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}](img8.png)
On lève l'exception parente_vide s'il y a une constraint error.
![\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}](img9.png)
Pour l'affichage de l'arbre, nous utilisons une procédure auxiliaire récursive
qui permettra de parcourir l'arbre.
![\begin{lstlisting}[language=ada]procedure An_Afficher( a: in arb_nr ) isbegi...
...vide;
else
An_Afficher_Aux(a,'''');
end if;end An_Afficher;\end{lstlisting}](img10.png)
La procédure auxiliaire est la suivante.
![\begin{lstlisting}[language=ada]procedure An_Afficher_Aux( a: in arb_nr ; str_...
...fficher_Aux(a.frere,str_decal);
end if;end An_Afficher_Aux;\end{lstlisting}](img11.png)
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.
![\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}](img12.png)
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.
![\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}](img13.png)
Nous comptons le nombre de fils de l'arbre rentré en paramètre.
![\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}](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}](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}](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}](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}](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}](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}](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}](img21.png)
la fonction fonction_main est passée en paramètre générique lors
de l'instanciation du paquetage arbre_nr.
![\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}](img22.png)
Un arbre quaternaire est un arbre ayant 0 ou 4 fils. Les quatre fils sont
appelés fils nord-ouest, nord-est, sud-ouest, sud-est.
Les opérations suivantes sont les mêmes que celles demandées pour le
paquetage arbre n-aire:
Aq_Creer_Vide, Aq_Creer_Feuille, Aq_Vide, Aq_Valeur, Aq_Pere,
Aq_Afficher, Aq_Rechercher, Aq_Est_Feuille, Aq_Est_Racine,
Aq_Changer_Valeur, Aq_Changer.
Les nouvelles fonctions à implanter sont:
- Aq_Construire: crée un arbre quaternaire à partir d'une valeur et de
4 arbres fils.
- Aq_Nord_Ouest: qui retourne le fils nord-ouest d'un arbre quaternaire.
- Aq_Nord_Est: qui retourne le fils nord-est d'un arbre quaternaire.
- Aq_Sud_Ouest: qui retourne le fils sud-ouest d'un arbre quaternaire.
- Aq_Sud_Est: qui retourne le fils sud-est d'un arbre quaternaire.
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:
![\begin{lstlisting}[language=ada]
function Aq_Creer_Vide return arb_quat renames An_Creer_Vide;
\end{lstlisting}](img23.png)
Nous faisons de même pour les exceptions:
![\begin{lstlisting}[language=ada]
-- arbre vide
arbreq_vide: exception renames ar...
... pas de parent�
parenteq_vide: exception renames parente_vide;
\end{lstlisting}](img24.png)
Nous définissons une exception filsq_vide pour la procédure Aq_Construire.
![\begin{lstlisting}[language=ada]----------------------------------------------...
...);
An_Inserer_Fils(arb_res,a_no);end if;end Aq_Construire;
\end{lstlisting}](img25.png)
Nous nous servons de la fonction An_Fils qui retourne l'arbre nième fils
d'un arbre.
![\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}](img26.png)
Nous faisons de même pour Aq_Nord_Est (return An_fils(a,2)), Aq_Sud_Ouest
(return An_fils(a,3)) et Aq_Sud_Est(return An_fils(a,4)).
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.
- charger une image à partir d'un fichier.
- enregistrer une image dans un fichier.
- afficher une image.
- charger une image encodée depuis un fichier.
- enregistrer une image encodée dans un fichier.
- appliquer une opération sur une image
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.
![\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}](img27.png)
Cette procédure permet de construire un arbre à partir d'une image. Nous
suivons l'algorithme d'encodage.
![\begin{lstlisting}[language=ada]----------------------------------------------...
...(-1,a_no,a_ne,a_so,a_se,a);end if;
end if;end im_to_arb;\end{lstlisting}](img28.png)
Il nous reste à parcourir l'arbre et enregistrer la séquence dans un
fichier, ce qui est fait dans la procédure enregistrer_imagec et arb_to_imc.
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.
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...=i+1;
end loop;
return result;
end case;end est_homogene;\end{lstlisting}](img29.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...ite(f,n);
arb_to_imc(a,f);
close(f);end enregistrer_imagec;\end{lstlisting}](img30.png)
Nous appelons la procédure récursive arb_to_imc qui va parcourir l'arbre.
![\begin{lstlisting}[language=ada]----------------------------------------------...
...1),f);
arb_to_imc(Aq_Frere(a,1),f);
end if;end arb_to_imc;\end{lstlisting}](img31.png)
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).
![\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}](img32.png)
Nous utilisons la procédure auxiliaire imc_to_arb.
cette procédure permet de construire l'arbre à partir de la
séquence de l'image compressée.
![\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}](img33.png)
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.
![\begin{lstlisting}[language=ada]procedure arb_to_im ( a: in arb_im ; im: out i...
...im,i_f/2+1,i_f,j_f/2+1,j_f);
end if;
end if;end arb_to_im;\end{lstlisting}](img34.png)
Nous devons faire une opération sur l'image. Nous avons choisi de
faire un seuillage binaire.
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...se
im(i,j):=1;
end if;
end loop;
end loop;end tresh_im;\end{lstlisting}](img35.png)
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 7.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 7.2:
Affichage de l'arbre obtenu pour la compression avec une tolérance minimale
|
|
La taille de l'image compressée est égale à 40 octets (9*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 (197) 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 7.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 7.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.
This document was generated using the
LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
|
![\includegraphics[width=5cm height=5cm]{arb.eps}](img37.png)
![\includegraphics[width=3.2cm height=3.2cm]{arb2.eps}](img38.png)
