Original paper

DijkstraFPS: Graph Partitioning in Geometry and Image Processing

Schindler, Falko; Förstner, Wolfgang

Abstract

Data partitioning is a common problem in the field of point cloud and image processing applicable to segmentation and clustering. The general principle is to have high similarity of two data points, e.g. pixels or 3D points, within one region and low similarity among regions. This pair-wise similarity between data points can be represented in an attributed graph. In this article we propose a novel graph partitioning algorithm. It integrates a sampling strategy known as farthest point sampling with Dijkstra's algorithm for deriving a distance transform on a general graph, which does not need to be embedded in some space. According to the pair-wise attributes a Voronoi diagram on the graph is generated yielding the desired segmentation. We demonstrate our approach on various applications such as surface triangulation, surface segmentation, clustering and image segmentation.

Kurzfassung

Datenpartitionierung ist eine elementare Aufgabe im Bereich Punktwolken- und Bildverarbeitung, vor allem zur Segmentierung und zum Clustern. Das generelle Prinzip ist es, hohe Ähnlichkeit zwischen zwei Datenpunkten derselben Region und geringe Ähnlichkeit zwischen verschiedenen Regionen zu erreichen. Diese paarweise Ähnlichkeit kann als attributierter Graph auf den gegebenen Daten repräsentiert werden. In diesem Artikel stellen wir einen neuen Graphpartitionierungsalgorithmus vor. Er integriert eine Samplingstrategie namens Farthest Point Sampling mit dem Verfahren von Dijkstra zur Ableitung einer Distanztransformation auf einem allgemeinen Graphen, der nicht in einen Raum eingebettet sein muss. Gemäß der paarweisen Attribute wird ein Voronoi-Diagramm auf dem Graphen generiert, das die gewünschte Segmentierung liefert. Wir demonstrieren unseren Ansatz für verschiedene Anwendungen, wie die Oberflächentriangulierung, die Oberflächensegmentierung, das Clustering und die Bildsegmentierung.

Keywords

graph partitioningsurface segmentationtriangulationclusteringimage segmentation