Computing Exact Discrete Minimal Surfaces: Extending and Solving the Shortest Path Problem in 3D with Application to Segmentation
Abstract
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.
Cite
Text
Grady. "Computing Exact Discrete Minimal Surfaces: Extending and Solving the Shortest Path Problem in 3D with Application to Segmentation." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2006. doi:10.1109/CVPR.2006.82Markdown
[Grady. "Computing Exact Discrete Minimal Surfaces: Extending and Solving the Shortest Path Problem in 3D with Application to Segmentation." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2006.](https://mlanthology.org/cvpr/2006/grady2006cvpr-computing/) doi:10.1109/CVPR.2006.82BibTeX
@inproceedings{grady2006cvpr-computing,
title = {{Computing Exact Discrete Minimal Surfaces: Extending and Solving the Shortest Path Problem in 3D with Application to Segmentation}},
author = {Grady, Leo J.},
booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
year = {2006},
pages = {69-78},
doi = {10.1109/CVPR.2006.82},
url = {https://mlanthology.org/cvpr/2006/grady2006cvpr-computing/}
}