Key points are not available for this paper at this time.
Wir untersuchen die Wasserscheiden in kantenbasierten Graphen. Wir definieren die Wasserscheide-Schnitte gemäß der intuitiven Idee von Wassertröpfchen, die auf einer topographischen Oberfläche fließen. Zunächst stellen wir die Konsistenz dieser Wasserscheiden fest: Sie können äquivalent durch ihre "Einzugsgebiete" (über eine steilsten Abstiegs-Eigenschaft) oder durch die "Trennlinien" definiert werden, die diese Einzugsgebiete voneinander abgrenzen (durch das Prinzip der Wassertröpfchen). Dann beweisen wir durch einen Äquivalenzsatz ihre Optimalität bezüglich minimaler spannender Wälder. Anschließend führen wir einen Algorithmus in linearer Zeit ein, um sie zu berechnen. Nach unserem besten Wissen werden ähnliche Eigenschaften in anderen Rahmenbedingungen nicht verifiziert, und der vorgeschlagene Algorithmus ist der effizienteste existierende Algorithmus, sowohl in der Theorie als auch in der Praxis. Schließlich werden die definierten Konzepte in der Bildsegmentierung veranschaulicht, was zur Schlussfolgerung führt, dass der vorgeschlagene Ansatz die Qualität der auf Wasserscheiden basierenden Segmentierungen bei den getesteten Bildern verbessert.
Cousty et al. (Mon,) haben diese Frage untersucht.