Table of contents

Cut Metrics and Geometry of Grid Graphs

Outline

Part I: “Cut Metrics” vs. “Path Metrics” on Graphs

Standard “Path Metrics” on graphs

“Distance Maps” for Path Metrics

Cut Metrics on graphs

Cut Metrics vs. Path Metrics

Cut metric “distance” for graphs with homogeneous topology

“Distance Maps” for Cut Metrics

Motivation

Part II: Integral Geometry and Graph Cuts (Euclidean case)

Integral Geometry and Cauchy-Crofton formula

Example of an application for Cauchy-Crofton formula

Cut Metric approximating Euclidean Metric

Part III: Differential Geometry and Graph Cuts

Non-Euclidean Metric

Cut Metric approximating Non-Euclidean Metric

“Distance Maps” for Cut Metrics in Non-Euclidean case

General Riemannian Metric on R

Cauchy-Crofton formula in case of Riemannian metric on R

Cut Metric approximating Riemannian Space

“Geo-Cuts” algorithm

Geo-Cuts vs. Level-Sets

Conclusions

Author: Yuri Boykov,Vladimir Kolmogorov