Ga door naar hoofdcontent
ArtikelenBevraging en visualisatie van gigantische nD-Puntenwolken met een continue level-of-detail

Bevraging en visualisatie van gigantische nD-Puntenwolken met een continue level-of-detail

Maandag 1 juni 2020Afbeelding Bevraging en visualisatie van gigantische nD-Puntenwolken met een continue level-of-detail

Dit is een deel van een lopend promotieonderzoek van Haicheng Lui. De oorspronkelijke titel is: ‘Towards 1015 Points Management – An nD Pointcloud Approach’.

Puntenwolken, ingewonnen met laserscanning of afgeleid vanuit foto’s, worden steeds vaker direct gebruikt voor inzichtelijke en interactieve visualisatie en analyse. Het is dan wel noodzakelijk dat deze zeer grote x,y,zdatasets met bijbehorende attributen (nDPuntenwolken) op een slimme en efficiënte wijze worden opgeslagen en bevraagd.

Dit lopende promotieonderzoek richt zich op de inzetbaarheid van ruimte vullende krommen (Space Filling Curves, afgekort tot SFC) voor de ruimtelijke clustering en indexering van n-dimensionale puntdata. Ook moet vooraf een goede afweging worden gemaakt welke attribuutinformatie (level, opnametijdstip, classificatie, etc.) naast de locatie (x, y, z) in de sleutel van de ruimte vullende kromme (SFC-key) opgenomen wordt. Op basis van deze sleutel worden de punten geclusterd en geïndexeerd (via een zogenaamde Index Organized Table) waarbij zowel locatie als de andere attributen in de sleutel worden gebruikt voor de data-organisatie. Punten kunnen nu efficiënt worden geselecteerd door de zoekvoorwaarden te vertalen (bijvoorbeeld gebieds- en tijdsinterval) naar relevante delen op de ruimte vullende kromme, de zogenaamde SFC-ranges (zie figuur 1).

De SFC-ranges kunnen grover (minder ranges, maar meer onnodige punten bij selecteren) of fijner (meer ranges, minder onnodige punten bij selecteren) worden gegenereerd afhankelijk van de diepte van verfijning. Nadeel van zeer fijne ranges is dat dit ten koste van de performance gaat; het is zoeken naar juiste balans. Tot slot moet bij de visualisatie sprake zijn van een continue level-of-detail (cLoD), zodat de gehele afbeelding op een evenredige wijze wordt opgevuld, zonder verstorende blokeffecten. Dus in plaats van een beperkt discreet aantal levels, punten volgens cLoD-waarde selecteren afhankelijk van de kijkpositie in het beeld. Deze selectie kan efficiënt verlopen door cLoD samen met x, y (en z) in de SFCkey te stoppen.

Figuur 1 – Selectie op basis van Mortom SFC ranges.
Figuur 2 – SFC ranges met mogelijke vals-positieve punten
Figuur 3 – 3D perspectief selecties op basis van kijkrichting en afstand.

Al deze eisen en onderzoeksvragen hebben geleid tot:

  1. De ontwikkeling van het nD-Puntenwolken concept: opslag van punten in nD georganiseerd volgens een ruimte vullende kromme. Bij selecteren van punten, wordt de fijnheid van de SFC-ranges bepaald afhankelijk van de puntdichtheid (nD-histogram).
  2. De ontwikkeling van een adaptief bevragingsproces op basis van deze HistSFC: bij selecteren van punten, wordt de fijnheid van de SFCranges bepaald afhankelijk van de puntdichtheid (nD-histogram). ‘Vals-positieve’ punten op de grens van het bevragingsgebied worden zoveel mogelijk vermeden (zie figuur 2).
  3. De ontwikkeling van het continue level-ofdetail (cLoD) algoritme voor de berekening van deze waarde voor ieder punt, en voor het integraal opnemen van deze cLoDwaarde in de hiervoor genoemde HistSFC data organisatie.
  4. De ontwikkeling van 3D perspectief selecties, waarbij geleidelijk steeds meer punten worden geselecteerd naar mate de afstand tot de kijkpositie kleiner is (zie figuur 3).
  5. Uitgebreide benchmarks die hebben aangetoond dat deze aanpak de bevraging niet alleen meer functionaliteit biedt (cLoD), maar ook enorm versnelt ten opzichte van de standaard ruimte vullende kromme en de Oracle SDO_PC aanpak.

Het vervolg van dit onderzoek richt zich op een verdere doorontwikkeling van de voorgenoemde methoden, verdere snelheidstesten, andere databronnen, operationaliseren binnen Oracle, de inzet van ‘parallel en distributed computing’, visualisatie in Virtual Reality systemen, ‘streaming data’, en een verdere vergelijking van deze aanpak met andere methoden en technieken voor de opslag en bevraging van zeer grote puntenwolkdata.

Referentie

Met dank aan Edward Verbree, Peter van Oosterom en Martijn Meijer voor de Nederlandse bewerking.

Auteurs