Computing Exact Discrete Minimal Surfaces: Extending and Solving the Shortest Path Problem in 3D with Application to Segmentation

Shortest path algorithms on weighted graphs have found widespread use in the computer vision literature. Although a shortest path may be found in a 3D weighted graph, the character of the path as an object boundary in 2D is not preserved in 3D. An object boundary in three dimensions is a (2D) surface. Therefore, a discrete minimal surface computation is necessary to extend shortest path approaches to 3D data in applications where the character of the path as a boundary is important. This minimal surface problem finds natural application in the extension of the intelligent scissors/ live wire segmentation algorithm to 3D. In this paper, the discrete minimal surface problem is both formulated and solved on a 3D graph. Specifically, we show that the problem may be formulated as a linear programming problem that is computed efficiently with generic solvers.