Une méthode classique utilisée pour représenter des images
carrées
consiste à définir une image comme étant soit une image de
couleur
uniforme, soit la réunion de quatre sous-images carrées de
même
tailles. Ainsi, toute une catégorie d'images peut être
représentée sous
la forme d'arbres quaternaires dont les feuilles sont des
couleurs. Dans toute la suite, sauf précision contraire, on se
limitera à deux couleurs, le noir et le blanc, et on pourra ainsi
identifier une image avec une partie du carré élémentaire
(l'image
toute blanche est l'ensemble vide, etc.). De plus, on numérotera les
fils d'un nud
dans le sens des aiguilles d'une montre, en partant du
quart nord-ouest. Par exemple :
Cette méthode de représentation permet de minimiser l'information nécessaire pour coder des zones homogènes ; de ce point de vue, c'est une forme de compactage.
Néanmoins, l'ensemble des images qui peuvent être
représentées par
cette méthode est assez limité, en effet, on voit facilement que
les
seules images qui peuvent être représentées par des arbres
quaternaires finis sont des réunions finies de carrés dont les
sommets ont
des coordonnées de la forme .
Dans ce projet on se propose d'étendre cette représentation en y
introduisant la récursivité. Un nud pourra donc posséder pour fils
des images situées au dessus de lui dans l'arbre. Par exemple
considérons l'image :
Elle représente un triangle inférieur droit.
Cette représentation est beaucoup plus riche que la précédente qu'elle contient trivialement (il suffit de considérer la sous-famille des images récursives qui n'utilisent pas la recursivité !)