Arbre quadruple: Exploration des structures de données hiérarchiques pour l'analyse d'images

Par Fouad Sabry

Qu'est-ce que Quadtree

Un quadtree est une structure de données arborescente dans laquelle chaque nœud interne a exactement quatre enfants. Les quadtrees sont l'analogue bidimensionnel des octrees et sont le plus souvent utilisés pour partitionner un espace bidimensionnel en le subdivisant de manière récursive en quatre quadrants ou régions. Les données associées à une cellule feuille varient selon l'application, mais la cellule feuille représente une « unité d'information spatiale intéressante ».

Comment vous en bénéficierez

(I) Informations et validations sur les sujets suivants :

Chapitre 1 : Quadtree

Chapitre 2 : Octree

Chapitre 3 : R-tree

Chapitre 4 : Arbre binaire

Chapitre 5 : B-tree

Chapitre 6 : Arborescence AVL

Chapitre 7 : Arbre rouge-noir

Chapitre 8 : Arbre de recherche binaire

Chapitre 9 : Tas binaire

Chapitre 10 : Arborescence des segments

(II) Répondre aux principales questions du public sur Quadtree.

(III) Exemples concrets d'utilisation de quadtree dans de nombreux domaines.

À qui s'adresse ce livre

Professionnels, étudiants de premier cycle et des cycles supérieurs, passionnés, amateurs et tous ceux qui souhaitent aller au-delà des connaissances ou des informations de base pour tout type de Quadtree.

 

• Langue: Français
• Éditeur: Un Milliard De Personnes Informées [French]
• Date de sortie: 14 mai 2024

Aperçu du livre

Quadtree

Exploration des structures de données hiérarchiques pour l'analyse d'images

Fouad Sabry est l'ancien responsable régional du développement commercial pour les applications chez Hewlett Packard pour l'Europe du Sud, le Moyen-Orient et l'Afrique. Fouad est titulaire d'un baccalauréat ès sciences des systèmes informatiques et du contrôle automatique, d'une double maîtrise, d'une maîtrise en administration des affaires et d'une maîtrise en gestion des technologies de l'information de l'Université de Melbourne en Australie. Fouad a plus de 25 ans d'expérience dans les technologies de l'information et de la communication, travaillant dans des entreprises locales, régionales et internationales, telles que Vodafone et des machines commerciales internationales. Actuellement, Fouad est un entrepreneur, auteur, futuriste, axé sur les technologies émergentes et les solutions industrielles, et fondateur de l'initiative One billion knowledge.

Un milliard de connaissances

Quadtree

Exploration des structures de données hiérarchiques pour l'analyse d'images

Fouad Sabry

Copyright

Quadtree © 2024 par Fouad Sabry. Tous droits réservés.

Aucune partie de ce livre ne peut être reproduite sous quelque forme que ce soit ou par quelque moyen électronique ou mécanique que ce soit, y compris les systèmes de stockage et de récupération d'informations, sans l'autorisation écrite de l'auteur. La seule exception est celle d'un critique, qui peut citer de courts extraits dans une critique.

Couverture conçue par Fouad Sabry.

Bien que toutes les précautions aient été prises dans la préparation de ce livre, les auteurs et les éditeurs n'assument aucune responsabilité pour les erreurs ou omissions, ou pour les dommages résultant de l'utilisation des informations contenues dans ce livre.

Table des matières

Chapitre 1 : Quadtree

Chapitre 2 : Octree

Chapitre 3 : Arbre R

Chapitre 4 : Arbre binaire

Chapitre 5 : Arbre B

Chapitre 6 : Arbre AVL

Chapitre 7 : Arbre rouge noir

Chapitre 8 : Arbre de recherche binaire

Chapitre 9 : Tas binaire

Chapitre 10 : Arborescence des segments

Appendice

À propos de l'auteur

Chapitre 1 : Quadtree

La structure de données d'un quadtree est un arbre dans lequel chaque nœud interne a exactement quatre descendants. Les quadriquades sont l'équivalent bidimensionnel des octrees et sont généralement utilisés pour diviser un espace bidimensionnel en quatre quadrants ou sections. L'information associée à une cellule feuille varie selon l'application, mais une cellule feuille est une « unité d'information spatiale intéressante ».

Les zones cloisonnées peuvent avoir des formes arbitraires, carrées ou rectangulaires. 1974 a vu la désignation de cette structure de données comme un quadtree par Raphael Finkel et J.L. Bentley. Q-tree est un autre terme pour un schéma de partitionnement similaire. Tous les types de quadtrees ont certaines caractéristiques :

Ils décomposent l'espace en cellules flexibles.

Chaque compartiment (ou réceptacle) a une capacité maximale. Lorsque la capacité maximale du godet est atteinte, il se sépare.

Le répertoire de l'arborescence est conforme à la décomposition spatiale du quadriceps.

Une pyramide arborescente (pyramide en T) est un arbre « complet » ; chaque nœud de la pyramide T contient quatre nœuds enfants, à l'exception des nœuds feuilles ; Toutes les feuilles sont au même niveau, ce qui correspond aux pixels individuels d'une image. De la même manière qu'un arbre binaire complet peut être stocké de manière compacte dans un tableau, les données de pyramide d'arbres peuvent être stockées de manière compacte dans un tableau en tant que structure de données implicite.

Les quadtrees peuvent être classés en fonction des types de données qu'ils représentent, tels que les surfaces, les points, les lignes et les courbes. Les quadtrees peuvent également être classés selon que la forme de l'arbre est indépendante de l'ordre de traitement. Les formes suivantes sont fréquentes de quadtrees :

Le quadriceps de région illustre une partition bidimensionnelle de l'espace en décomposant la région en quatre quadrants égaux, sous-quadrants, etc., chaque nœud terminal contenant des données relatives à une sous-région particulière. Chaque nœud de l'arbre a précisément quatre enfants ou aucun (un nœud feuille). Cette méthode de décomposition (c'est-à-dire la subdivision des sous-quadrants tant qu'il y a des données pertinentes dans le sous-quadrant pour lequel un plus grand raffinement est recherché) rend la hauteur des quadtrees sensible et dépendante de la distribution spatiale des zones intéressantes dans l'espace à décomposer. Le quadtree de région est une variante de la structure de données trie.

Un quadtree de région avec une profondeur de n peut être utilisé pour représenter une image composée de 2n × 2n pixels, où chaque pixel est soit 0, soit 1.

Le nœud racine représente la totalité de la région de l'image.

Si les pixels d'une région ne sont pas entièrement 0 ou 1, la région est considérée comme invalide, elle est segmentée.

Il s'agit d'une application, chaque nœud terminal représente un bloc de pixels composé entièrement de 0 ou de 1.

Notez les économies d'espace possibles lorsque ces arbres sont utilisés pour le stockage d'images ; Une caractéristique commune des représentations visuelles est la présence de nombreuses grandes zones avec la même valeur de couleur.

Au lieu de stocker un grand tableau 2D de chaque pixel d'une image, un réseau plus petit est utilisé, un quadtree peut capturer les mêmes informations à peut-être beaucoup plus de niveaux de division que les cellules de la taille d'une résolution de pixel.

La résolution et la taille de l'arbre sont limitées par les dimensions en pixels et en images.

Un quadriarbre de région peut également être utilisé pour représenter un champ de données avec une résolution variable. Par exemple, un quadtree peut être utilisé pour enregistrer les températures dans une région, chaque nœud feuille stockant la température moyenne de la sous-région qu'il représente.

Le quadtree ponctuel

Voici comment les quadrilatères ponctuels sont construits. Étant donné le prochain point à insérer, la cellule correspondante est localisée et le point est ajouté à l'arborescence. Le nouveau point est inséré de manière à ce que la cellule qui le contient soit divisée en quadrants par les lignes verticales et horizontales qui le traversent. Les cellules sont donc rectangulaires, mais pas toujours carrées. Chaque nœud de ces arbres contient l'un des points d'entrée.

En raison du fait que la partition du plan est déterminée par l'ordre d'insertion des points, la hauteur de l'arbre est sensible et dépend de l'ordre d'insertion. L'insertion dans un « mauvais » ordre peut entraîner un arbre dont la hauteur est proportionnelle au nombre de points d'entrée (auquel cas il devient une liste chaînée). Le prétraitement peut être utilisé pour générer un arbre avec une hauteur équilibrée si l'ensemble de points est statique.

Un nœud d'un quadrilatère ponctuel est similaire à un nœud d'un arbre binaire, la principale distinction étant qu'il a quatre pointeurs (un pour chaque quadrant) au lieu de deux (« gauche » et « droite ») comme dans un arbre binaire conventionnel. De plus, une clé est généralement divisée en deux composants qui font référence aux coordonnées x et y. Par conséquent, un nœud contient les données suivantes :

quatre pointeurs : quad['NW'], quad['NE'], quad['SW'] et quad['SE']

point; qui contient à son tour :

identificateur; généralement indiqué sous forme de coordonnées x, y

une valeur, telle qu'un nom

Les quadtrees de région ponctuelle (PR) ressemblent assez étroitement aux quadtrees de région. La différence réside dans le type de données liées aux cellules enregistrées. Dans un quadriarbre de région, une valeur qui s'applique à toute la surface d'une cellule feuille est conservée. Toutefois, les cellules d'un quadrilatère PR contiennent une liste de points qui résident dans une cellule feuille. Comme indiqué précédemment, la hauteur des arbres utilisant cette approche de décomposition dépend de la distribution spatiale des points. Semblable au quadrilatère ponctuel, le quadrilatère PR peut avoir une hauteur linéaire lorsqu'un « mauvais » ensemble est fourni.

Les quadriquarbres Edge (similaires aux quadriceps PM) sont utilisés pour maintenir les lignes par opposition aux points. Les cellules sont subdivisées à une résolution extrêmement fine afin d'approximer les courbes, précisément jusqu'à ce qu'il n'y ait qu'un seul segment de ligne par cellule. Les quadriarçons d'arêtes continueront à se diviser jusqu'à ce qu'ils atteignent leur niveau maximal de décomposition près des coins/sommets. Cela peut conduire à des arbres gravement déséquilibrés qui annulent l'objectif de l'indexation.

Le quadriarbre de carte polygonale (ou quadriceps PM) est une variante du quadrilatère utilisé pour contenir des groupes de polygones potentiellement dégénérés (ce qui signifie qu'ils ont des sommets ou des arêtes isolés). Une distinction significative entre les quadriquarbres PM et les quadriarçons d'arête est que la cellule examinée n'est pas partitionnée si les segments de la cellule se croisent au niveau d'un sommet.

Il existe trois principaux types de quadriquaristes PM, qui diffèrent en fonction des données stockées dans chaque nœud noir. Les quadriquararbres PM3 peuvent contenir un nombre arbitraire d'arêtes non sécantes et un seul point au maximum. Les quadriarbres PM2 sont identiques aux quadrichromades PM3, à l'exception du fait que toutes les arêtes doivent se terminer à la même position. Les quadriarbres PM1 sont similaires aux quadrichromades PM2, mais les nœuds noirs peuvent inclure un point et ses arêtes ou seulement un ensemble d'arêtes qui partagent un point, mais un point et un ensemble d'arêtes qui ne contiennent pas le point ne sont pas autorisés.

Cette section fournit un résumé d'un chapitre du livre de Sariel Har. Celui de Peled.

Si nous devions stocker chaque nœud correspondant à une cellule subdivisée, le besoin de stockage serait prohibitif, nous pourrions finir par stocker un nombre substantiel de nœuds vides.

Nous pouvons réduire la taille de ces arbres clairsemés en ne conservant que les sous-arbres dont les feuilles contiennent des données intéressantes (i.e.

« sous-succursales importantes »).

Nous pouvons en fait réduire la taille beaucoup plus.

Lorsque nous ne conservons que les sous-arbres essentiels, la procédure d'élagage peut laisser de longs itinéraires dans l'arbre avec des nœuds intermédiaires de degré deux (un lien vers un parent et un enfant).

Il s'avère que nous n'avons qu'à stocker le nœud u au début de ce chemin (et à lui associer des métadonnées pour représenter les nœuds supprimés) et attacher le sous-arbre enraciné à son extrémité à u .

Lorsqu'on leur donne des points d'entrée « médiocres », il est néanmoins possible que ces arbres comprimés aient une hauteur linéaire.

Bien qu'une quantité substantielle de l'arbre soit élaguée pendant cette compression, la recherche en temps logarithmique est toujours possible, l'insertion et la suppression par l'utilisation de courbes d'ordre Z.

La courbe d'ordre Z mappe chaque cellule du quadrilatère complet (et donc même le quadrilatère compressé) dans le O(1) temps à une ligne unidimensionnelle (et la mappe également dans O(1) le temps), établissant un ordre complet sur les éléments.

Par conséquent, nous pouvons stocker le quadtree dans une structure de données ordonnée (dans laquelle nous stockons les nœuds de l'arbre).

Nous devons formuler une hypothèse raisonnable avant de continuer : nous supposons qu'étant donné deux nombres réels {\displaystyle \alpha ,\beta \in [0,1)} exprimés en binaire, nous pouvons calculer dans O(1) le temps l'indice du premier bit dans lequel ils diffèrent.

Nous supposons également que nous pouvons calculer dans O(1) le temps l'ancêtre commun le plus bas de deux points/cellules dans le quadtree et établir leur ordre Z relatif, et nous pouvons calculer la fonction de plancher dans le O(1) temps.

Avec ces prémisses, l'emplacement d'un point donné q (i.e.

déterminer la cellule qui contiendrait q ), les opérations d'insertion et de suppression peuvent toutes être effectuées à O(\log {n}) temps (c.-à-d.

temps nécessaire pour effectuer une recherche dans la structure de données de l'ensemble ordonné sous-jacent).

Pour effectuer une localisation de point pour q (c.-à-d.

Trouvez la cellule correspondante dans l'arborescence compressée) :

Recherchez la cellule existante dans l'arborescence compressée qui précède q dans l' ordre Z.

Appelez cette cellule v .

Si {\displaystyle q\in v} , retournez v .

Sinon, trouvez ce qui aurait été l'ancêtre commun le plus bas du point et de q la cellule v dans un quadtree non compressé.

Appelez cette cellule ancêtre u .

Recherchez la cellule existante dans l'arborescence compressée qui précède u dans l' ordre Z et renvoyez-la.

Sans entrer dans les détails, pour faire des insertions et des suppressions, nous effectuons d'abord un placement de point pour l'élément à insérer ou à supprimer, puis à l'insérer ou à supprimer. Il faut prendre soin de remodeler l'arbre au besoin en ajoutant ou en supprimant des nœuds.

Représentation d'images

Bitmap and its compressed quadtree representation

Traitement d'images

Génération de maillage

Indexation spatiale, recherches basées sur des points et des plages

Efficacité de la détection de collision bidimensionnelle

Afficher les données sur l'abattage des frustum pour le terrain

Stockage de données éparses, telles que les informations de