The aim of this project is to develop generic packages on n-ary and quaternary trees.
These packages will be reused to implement another
package allowing to achieve image compression and decompression.
Operations that one has to operate on n-ary tree are grouped into 3 categories : creation,
consultation and modification. Here are the list of procedures to code.
A node is represented by a record type containing the value of the root,
a pointer on the first child, a pointer on the brother and another one on the father tree.
The tree_nr type is set to private for hiding from user
package the data structure chosen to represent the n-ary tree.
We chose to pass as generic parameters the type of value of the root, the procedure
which displays element and the function that will be applied to each element.
We use also here an auxiliary procedure that make browse the tree along two ways of recursivity, the children
one and the brothers one.
The auxiliary procedure is as follow : we use a boolean, passed as data/results parameters, to finish the
recursive calls if value is found. If it is found, tree_curr is set to a null pointer.
Quaternary tree being a subcategory of n-ary tree, we declare a type "quaternary tree", which is a
subtype of n-ary tree. The generic parameters are the same as parameters of n-ary tree package.
We use "renames" ADA directive in specification part. This will allow to reuse all procedures and functions
implemented into n-ary tree package. Example :
We do the same thing for exceptions :
We define a childq_empty exception for Qt_Build procedure.
The aim est to carry out compression and decompression on an image using
a quaternary tree. The images that we use are squares and their dimension
is a power of 2. A color is defined from the 3 primary colors (red, green, blue)
and is integer coded.
The recursive compression algorithm of a image with dimension n is as follows :
if image is homogeneous, then we create a leaf whose root value is the color of
image. If image is not homogeneous, we split it into 4 sub-images of dimension n/2, and
we create a quaternary tree whose the four children are the 4 encoded sub-images.
Browsing all the quaternary tree, we get a set of values representing the compressed image.
It is specified that pimage package allows to :
create a test image from a dimension and a matrix.
We explain here how is_homogeneous function deals with 3 possibles cases :
tolerance is minimal (0), maximal (100), or between these two values. If it
is maximal, then we return a boolean set to true and a leaf is created with
the average value of the image (see procedure im_to_tree). If it is
minimal, we check that all pixels have the same value. Finally, for the middle case,
we test the inequality abs(primary_color-average) <= tolerance on each pixel.
Firstly, we must build a tree from encoded sequence (procedure load_im_encod and
imc_to__tree) and then rebuild image from this tree (procedure tree_to_im).
Test program main_tree_nary.adb and main_tree_quater.adb use respectively
tree_nary.adb and tree_quater.adb package. It is possible to make a tree for
checking the good operating of all main above procedures and functions.
Tets program main_pimage.adb allows to create an image and validate compression and
decompression. An example of image is displayed as :
Figure 1 : Content of test image 8x8
Its size equals to 260 bytes (64*4+4) because we save also the dimension.
We take into account a tolerance to see if image is homogeneous. The tree built with
a minimal tolerance (0) is represented on the following figure :
Figure 2 : Content of tree for compression with minimal tolerance
Image compressed size equals to 104 bytes (25*4+4) with 4 bytes for dimension, which was
expected. With a maximal tolerance (100), we get a leaf with the average color of image (161)
because this one is considered as homogeneous from criterion into is_homogeneous function.
with a tolerance equal to 80, we get this tree :
Figure 3 : Content of tree for compression with a tolerance equal to 80
We can notice that there will be a loss of information regards to test image with compression.
Indeed, the north-west part of image is seen as homogeneous with this tolerance. This is illustrated
on this figure :
Figure 4 : Content of decompressed image 8x8 with a tolerance equal to 80
For each case, we save compressed image and check decompression.
This project has enabled us to create a package to make
compression and decompression of images. The operations implemented for
quaternary trees were reused and validated for encoding algorithm.
![\begin{lstlisting}[language=ada]
type node;
type tree_nr is access node;
type no...
...ild: tree_nr;
brother: tree_nr;
father: tree_nr;
end record;
\end{lstlisting}](img_en2.png)
![\begin{lstlisting}[language=ada]
generic
type T is private;
with procedure write ( a: in T );
with function main_function ( a: in T) return T;
\end{lstlisting}](img_en3.png)
![\begin{lstlisting}[language=ada]
function Nt_Create_Empty return tree_nr isbeginreturn null;end Nt_Create_Empty;
\end{lstlisting}](img_en4.png)
![\begin{lstlisting}[language=ada]
function Nt_Create_Leaf ( value : in T ) return...
...a.brother:=null;
a.father:=null;
return a;end Nt_Create_Leaf;
\end{lstlisting}](img_en5.png)
![\begin{lstlisting}[language=ada]
function Nt_Empty ( a: in tree_nr ) return boolean isbeginreturn (a=null);end Nt_Empty;
\end{lstlisting}](img_en6.png)
![\begin{lstlisting}[language=ada]
function Nt_Value ( a: in tree_nr ) return T is...
...ption
when constraint_error => raise tree_empty;end Nt_Value;
\end{lstlisting}](img_en7.png)
![\begin{lstlisting}[language=ada]
function Nt_Father ( a: in tree_nr ) return tre...
...empty;
else
return a.father;
end if;
end if;end Nt_Father;
\end{lstlisting}](img_en8.png)
![\begin{lstlisting}[language=ada]
function Nt_Child ( a: in tree_nr; n: in intege...
...n
when constraint_error => raise relation_empty;
end Nt_Child;
\end{lstlisting}](img_en9.png)
![\begin{lstlisting}[language=ada]
function Nt_Brother ( a: in tree_nr; n: in inte...
... when constraint_error => raise relation_empty;
end Nt_Brother;
\end{lstlisting}](img_en10.png)
![\begin{lstlisting}[language=ada]
procedure Nt_Display( a: in tree_nr ) isbegin...
... put('' '');
Nt_Display_Aux(a,'' '');
end if;end Nt_Display;
\end{lstlisting}](img_en11.png)
![\begin{lstlisting}[language=ada]
procedure Nt_Display_Aux( a: in tree_nr ; str_s...
...(a.brother,str_shift);
end if;end if;end Nt_Display_Aux;
\end{lstlisting}](img_en12.png)
![\begin{lstlisting}[language=ada]
function Nt_Search ( a: in tree_nr; e: in T ) r...
...curr,stop);
return tree_curr;
end if;
end if;end Nt_Search;
\end{lstlisting}](img_en13.png)
![\begin{lstlisting}[language=ada]
procedure Nt_Search_Aux ( tree :in tree_nr ; e:...
...p);
else null;
end if;
end if;
end if;end Nt_Search_Aux;
\end{lstlisting}](img_en14.png)
![\begin{lstlisting}[language=ada]
function Nt_Number_Children( a: in tree_nr ) re...
... n;
else
return 1;
end if;
end if;end Nt_Number_Children;
\end{lstlisting}](img_en15.png)
![\begin{lstlisting}[language=ada]
function Nt_Is_Leaf( a: in tree_nr )return bool...
...on
when constraint_error => raise tree_empty;end Nt_Is_Leaf;
\end{lstlisting}](img_en16.png)
![\begin{lstlisting}[language=ada]
function Nt_Is_Root( a: in tree_nr )return bool...
...on
when constraint_error => raise tree_empty;end Nt_Is_Root;
\end{lstlisting}](img_en17.png)
![\begin{lstlisting}[language=ada]
procedure Nt_Change_Value( a:in out tree_nr; e:...
...hen constraint_error => raise tree_empty;end Nt_Change_Value;
\end{lstlisting}](img_en18.png)
![\begin{lstlisting}[language=ada]
procedure Nt_Insert_Child ( tree: in out tree_n...
..._child:=tree_i;
end if;
end if;
end if;end Nt_Insert_Child;
\end{lstlisting}](img_en19.png)
![\begin{lstlisting}[language=ada]
procedure Nt_Insert_Brother( tree: in out tree_...
... tree.brother:=tree_i;
end if;
end if;end Nt_Insert_Brother;
\end{lstlisting}](img_en20.png)
![\begin{lstlisting}[language=ada]
procedure Nt_Delete_Child ( a: in out tree_nr ;...
...rother:=a_next;
end if;
end if;
end if;end Nt_Delete_Child;
\end{lstlisting}](img_en21.png)
![\begin{lstlisting}[language=ada]
procedure Nt_Delete_Brother ( a :in out tree_nr...
... noting
when constraint_error => null;end Nt_Delete_Brother;
\end{lstlisting}](img_en22.png)
![\begin{lstlisting}[language=ada]
procedure Nt_Change( a: in out tree_nr ) isbe...
...a.first_child);
Nt_Change(a.brother);
end if;end Nt_Change;
\end{lstlisting}](img_en23.png)
![\begin{lstlisting}[language=ada]
function Qt_Create_Empty return quat_tree renames Nt_Create_Empty;
\end{lstlisting}](img_en24.png){kind=small}
![\begin{lstlisting}[language=ada]
-- empty tree
treeq_empty: exception renames tr...
... no relation
relationq_empty: exception renames relation_empty;
\end{lstlisting}](img_en25.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...t_ne);
Nt_Insert_Child(tree_res,t_nw);end if;end Qt_Build;
\end{lstlisting}](img_en26.png)
![\begin{lstlisting}[language=ada]
function Qt_North_West( a: in tree_quat ) return tree_quat isbeginreturn Nt_Child(a,1);end Qt_North_West;
\end{lstlisting}](img_en27.png)
![\begin{lstlisting}[language=ada]
-- subtype tree_im
subtype tree_im is tree_qua...
...pe image is array (integer range <>,integer range <>) of pixel;
\end{lstlisting}](img_en28.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...(-1,a_nw,a_ne,a_sw,a_se,a);end if;
end if;end im_to_tree;
\end{lstlisting}](img_en29.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...i+1;
end loop;
return result;
end case;end is_homogeneous;
\end{lstlisting}](img_en30.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...me);
write(f,n);
tree_to_imc(a,f);
close(f);end save_imagec;
\end{lstlisting}](img_en31.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...f);
tree_to_imc(Qt_Brother(a,1),f);
end if;end tree_to_imc;
\end{lstlisting}](img_en32.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...,dim);
n:=dim;
a:=imc_to_tree(f);
close(f);end load_im_encod;
\end{lstlisting}](img_en33.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...-1,a_nw,a_ne,a_sw,a_se,a);
end if;
return a;end imc_to_tree;
\end{lstlisting}](img_en34.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
..._f,j_f-(j_f-j_b+1)/2+1,j_f);
end if;
end if;end tree_to_im;
\end{lstlisting}](img_en35.png)
![\begin{lstlisting}[language=ada]
-----------------------------------------------...
...1;
end if;
end loop;
end loop;end thresh_im;end pimage;
\end{lstlisting}](img_en36.png)
