1.4 Stockée les données du SIG.
Après avoir présenté une modélisation conceptuelle de l’information dans les SIG, maintenant nous nous intéressons à l’organisation de bas niveau de cette information. Cela concerne les structures de données informatiques utilisées pour coder l’information présente dans les SIG. Choisir la manière pour stockée des données est très importante en termes de performances d’accès aux données et de taille de stockage des bases.
+ Information graphique et information sémantique
On distingue habituellement deux types d’informations pour les données des SIG: L’aspect sémantique donne une description dans différents champs ou attributes. L’aspect graphique qui est le contour de l’objet localisé géographiquement.
1 information élémentaire correspond à un objet ou à 1 champ (d’une table) décrivant cet objet.
+ Organisation des systèmes de fichiers et méthodes d’accès
L’organisation élémentaire d’une base de données, est une collection de fichiers composés d’enregistrement, stockés sur un disque informatique. Des techniques plus sophistiquées de structurations des bases de données, sur les disques, ont été imaginées afin d’accélérer les algorithmes (programmes) de recherche.
- Organisation simple des fichiers et recherches linéaires
C’est la méthode d’organisation la plus élémentaire, il n’y a pas de structuration particulière des informations sur le disque, imposée par le SIG. C’est le système d’exploitation de la machine qui alloue les positions sur le disque pour les fichiers. Le type de recherche qui est utilisé avec ce type de structure est qualifiée de linéaire. En effet les données ne sont pas triées en fonction de l’information, pour rechercher une information il faut donc balayer tous les enregistrements jusqu’à trouver l’information recherchée.
Pour n enregistrements on va en moyenne faire n/2 recherche avant de trouver. (on parle de complexité de l’algorithme) Cette méthode est particulièrement lente pour de grosses bases de données. Elle a l’avantage, comme elle n’est pas structurée de permettre des modifications faciles des enregistrement (suppression, insertion …)
- Organisation séquentiel des fichiers et recherches binaires
Contrairement au cas précédent, les données sont ici organisées dans le fichier, en fonction de la valeur de un ou de plusieurs champs. Une recherche de type binaire peut être appliquée sur ces fichiers. Pour cette recherche on se place au milieu du fichier, on lit dans l’enregistrement le champ qui a servi à organiser le fichier. Si la valeur recherchée est inférieur au champ lu, on recherche alors dans la première moité du fichier, de la même manière, sinon on recherche dans la seconde moitié du fichier.
Pour n enregistrement la compléxité est cette fois de l’ordre de log2(n). Par exemple pour 1000 enregistrements, un traitement linéaire necessite en moyenne 500 accès contre seulement log2(1000) = 10 accès pour une recherche binaire.
Par contre les modifications de la base (insertion, deletions …) sont très couteuse en temps, car la modification de la place d’un enregistrement se répercute sur la place des autres.
- Tables de hachages
Une table de hachage utilise une fonction de hachage. Sur un ou plusieurs champs, la fonction de hachage transformat la valeur en une adresse physique sur le disque. L’adresse peut donc être entièrement calculée et ne nécessite alors seulement un accès disque pour retrouver l’enregistrement. Soit un bloque de 1000 emplacements sur le disque, numéroté de 0 à 999. Soir des enregistrements avec un champ numérique variant de 0 à 1999
Une fonction de hachage très simple: diviser par deux, peut être utilisée.valeur du champ = 400 FonctionHachage(400) = 200 adresse sur le disque
C’est une technique très optimale, mais qui pose des problèmes pour la gestion de bloques disques (recouvrement, taille élémentaire des bloques …), elle ne peut s’appliquer que sur des champs numériques ou pouvant se transformer en valeur numérique.
- Tables d’index notion d’identifiant
Cette technique utilise des tables d’index à la manière de l’index d’un livre.
Le fichier de données lui même n’est pas organisé, mais un second fichier index est créé, qui lui est ordonné et qui contient un des champs des enregistrement, que l’on nome l’indexe, ainsi que l’adresse ou pointeur de l’enregistrement correspondent dans le premier fichier.
Une recherche binaire peut alors être entreprise, sur le fichier indexe.
Pour de très grosses bases de données le fichier index peut lui aussi devenir très gros et ralentir la recherche. On peut alors créer une table d’index du fichier index. On parle alors d’index multi-niveaux. Le B-tree (balanced tree) est un exemple d’indexe multi-niveaux.
Dans la plupart des SIG un champ particulier, que l’on nome identifiant, sert à construire une table d’index, pour manipuler rapidemment les enregistrements de la base.
- Indexations spatiales notion de localisant
Les méthodes de codage et d’accès précédentes faisaient surtout référence aux données sémantique. Le problème se pose de la même façon pour des accès à la base par l’information spatiale. Pour cela des méthodes d’indexations spatiales ont été imaginées, il s’agit de rapprocher physiquement sur le disque des enregistrement qui sont proche dans l’espace géographique. Par exemple :
Par analogie avec la notion d’identifiant pour les données sémantique, on parle parfois de localisant pour la façon d’accéder à l’information par le spatial.
+ Format de l’information graphique : raster ou vecteur
Le format raster utilise une description matricielle de l’espace géographique. La matrice est une image, chaque élément de l’image ou pixel (picture element) contient un niveau donné qui représente une thématique. Ces images sont généralement issues de scanners ou d’images aériennes ou satellitaires.
- Format raster
Structure de données informatique des raster
Il existe de nombreuses techniques issues du traitement d’images pourcoder des données sous forme raster.
o Matrice raster
Un raster est par définition une matrice de points (pixels). On défini aussi les voxels par analogie au pixel dans un espace à trois dimensions. Le stockage sous cette forme peut être très coûteux en taille, de nombreuses méthodes de codage permettant une compression des données sont utilisées.
o Chain codes
C’est un codage utilisé pour représenter les contours dans une image, il est basée sur le codage directionnel de Freeman :
Les directions élémentaires d, codent pour le passage d’un pixel de contour à un autre, un contour est alors entièrement codé par une suite de d.
o Run Length code
Ce type de compression tire partie de la répétitivité de certaine image. En effet une carte raster peut contenir de larges plages de pixels ayant la même valeur. Par exemple une ligne de 20 pixels contigus tous à la valeur 6 pourra être codée :
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 En codage raster classique ou 20 6 en codage run length. On code ici sur 2 octets le nombre de pixels de la plage et la valeur de la plage, soit un taux de compression de 20/2 = 10.
o Block code
Il s’agit d’une généralisation du cas précédent au cas bidimensionel.
o Quadtree
On découpe une image de façon récursive en quadrant jusqu’à obtenir des régions élémentaires homogènes (de même classe).
Pour une image binaire (2 niveaux: et )
- Format vecteur
Dans le cas d’un codage vectoriel l’espace de représentation est suppose continu, contrairement au codage raster où l’espace est quantifié et la précision géométrique est donc limité. En fait la supposition d’un espace continu ne peut être réellement satisfaite sur les systèmes informatiques, car les systèmes numériques supposent un codage avec une précision finie des valeurs numériques. La taille des « mots machines » sur les ordinateurs fixe la précision des valeurs numériques codées selon leur type mathématique (entier, réel …).
o Codage par primitives graphiques
Cas du codage des polygones
Soient deux polygones connexes POLY1 et POLY2, soient pi les points de contour :
Deux techniques sont utilisées concernant le codage graphique des polygones :
Codage par cou vertu re d’arcs / codage par cou vertu re de polygones
Dans le premier cas chaque polygone contient tous les points de son contour, en concéquence les points communs aux deux polygones connexes sont dupliqués dans P1 et P2.
Dans le second cas les arcs individuels sont codés en tant que tel, on parle de couverture d’arcs, et les polygones ne contiennent que la liste des arcs les constituant.
Structure de données informatique des vecteurs
Les problèmes d’indexation se pose de la même manière que pour les données raster.
1.5 Des formats de donnée SIG
+ Format matriciel (raster)
(Pour comprendre mieux, visiter le site: http://fr.wikipedia.org/wiki/Formats_de_fichier_SIG)
• ADRG (ARC Digitized Raster Graphics) - National Imagery and Mapping Agency -
• BIL - Band Interleaved by Line (utilisé en imagerie satellitaire)
• CADRG (Compressed ARC Digitised Raster Graphics) - National Imagery and Mapping Agency - compression de 55:1 par rapport à ADRG
• CIB (Controlled Image Base) - National Imagery and Mapping Agency - type de Raster Product Format
• Digital raster graphic (DRG) - format des cartes papiers topographiques scannées de l’USGS
• ECW (Enhanced Compressed Wavelet) - ERMapper - Compression par ondelettes, souvent avec perte.
• ESRI grid - fichier binaire ou ASCII utilisé par ESRI
• GeoTIFF - format TIFF enrichie avec des métadonnées relatives au SIG
• IMG - ERDAS IMAGINE[1]
• JPEG2000 - format compressé, permettant une compression avec ou sans perte.
• MrSID (Multi-Resolution Seamless Image Database) - Lizardtech - Compression par ondelettes, souvent avec perte.
+ Formats vecteur
• Coordonnées cartésiennes (XYZ) - simple nuage de point
• Coverage - format propriétaire d’ESRI.
• Drawing eXchange Format (DXF) - AutoCAD
• Geography Markup Language (GML) - dérivé du XML pour encoder, manipuler et échanger des données géographiques. Standard développé par l’Open Geospatial Consortium pour garantir l’interopérabilité des données.
• GeoMedia - Intergraph utilise différentes bases de données pour le stockage de données géographiques vecteur, notamment Microsoft Access.
• GPS eXchange Format (GPX) - format de fichier permettant l’échange de coordonnées GPS
• Keyhole Markup Language (KML) - Google
• MapInfo TAB format - format vecteur de MapInfo utilisant des fichiers TAB, DAT, ID et MAP.
• National Transfer Format (NTF) - National Transfer Format (principalement utilisé par l’Ordnance Survey de Grande-Bretagne)
• Simple Features - Open Geospatial Consortium spécification pour les données vecteur
• Shapefile - Initialement développé par ESRI ce format, devenu un standard de facto, est largement utilisé par un grand nombre de logiciels libres comme propriétaires. Il utilise 3 types de fichiers : SHP, SHX et DBF
• Smart Data Compression (SDC) - format propriétaire d’ESRI
• Spatial Data File - format développé par Autodesk pour MapGuide
• Personal Geodatabase - format propriétaire d’ESRI, stockant des données vecteur dans un fichier Microsoft Access (.mdb).
• File Geodatabase - format ESRI de base de données spatiales stockée comme des répertoires dans un système de fichiers.
• Topologically Integrated Geographic Encoding and Referencing (TIGER) - Bureau du recensement des États-Unis
• Vector Product Format (VPF) - National Imagery and Mapping Agency format de la NIMA pour de grande base de données géographique.
Modèle numérique de terrain [modifier]
• USGS DEM (Digital Elevation Model) - USGS
• DTED (Digital Terrain Elevation Data) - National Imagery and Mapping Agency (NIMA)
• GTOPO30 - USGS - couverture de la terre entière avec une résolution de 30 secondes d’arc (~ 1km)
• SDTS - successeur du format DEM de l’USGS
Autres formats [modifier]
• Binary Terrain - format du Virtual Terrain Project [2]
• Well-known text (WKT) – format ASCII défini par l’Open Geospatial Consortium
• Well-known binary (WK
- format binaire défini par l’Open Geospatial Consortium
• World file - pour géoréférencer une image matricielle (ex JPEG, BMP)
Références:
[1] Introduction aux SIG - systèmes d’informations géographiques (Institut National Agronomique Paris-Grignon)
[2] http://en.wikipedia.org/wiki/Raster_graphics
[3] http://fr.wikipedia.org/wiki/Formats_de_fichier_SIG
[4] Guide projet SIG (École nationale des sciences géographiques)
[5] http://www.forumsig.org/
