Image segmentation with ratio cut
Image segmentation with ratio cut
复制标题
DOI：
10.1109/tpami.2003.1201819
复制
发表时间：
2003-06-01
影响因子：
23.6
通讯作者：
Siskind, JM
中科院分区：
文献类型：
--
作者：
Wang, S;Siskind, JM
本文提出了一种新的成本函数，即切割比，用于使用基于图的方法分割图像。切割比率定义为沿切割边界的两个不同边缘权重的相应总和的比率，并模拟每单位边界长度由边界分隔的线段之间的平均亲和力。这种新的成本函数允许对图像周界进行分割，保证二分生成的片段是连接的，并且不会引入大小、形状、平滑度或边界长度偏差。后者允许它产生边界与图像边缘对齐的分割。此外，切割比成本函数允许有效的迭代的基于区域的分割以及基于像素的分割。这些属性对于某些图像分割应用程序可能很有用。虽然在任意图中找到最小比率切割的问题是 NP 困难的，但我们可以在多项式时间内图像分割期间出现的连通平面图中找到最小比率切割。虽然单独的切割比不足以作为图像分割的基线方法，但当与少量标准技术相结合时，它为图像分割的扩展方法奠定了良好的基础。我们提出了一种用于寻找最小比率切割的实现算法，证明其正确性，讨论其在图像分割中的应用，并展示使用我们的技术分割大量医学和自然图像的结果。
This paper proposes anew cost function, cut ratio, for segmenting images using graph-based methods. The cut ratio is defined as the ratio of the corresponding sums of two different weights of edges along the cut boundary and models the mean affinity between the segments separated by the boundary per unit boundary length. This new cost function allows the image perimeter to be segmented, guarantees that the segments produced by bipartitioning are connected, and does not introduce a size, shape, smoothness, or boundary-length bias. The latter allows it to produce segmentations where boundaries are aligned with image edges. Furthermore, the cut-ratio cost function allows efficient iterated region-based segmentation as well as pixel-based segmentation. These properties may be useful for some image-segmentation applications. While the problem of finding a minimum ratio cut in an arbitrary graph is NP-hard, one can find a minimum ratio cut in the connected planar graphs that arise during image segmentation in polynomial time. While the cut ratio, alone, is not sufficient as a baseline method for image segmentation, it forms a good basis for an extended method of image segmentation when combined with a small number of standard techniques. We present an implemented algorithm for finding a minimum ratio cut, prove its correctness, discuss its application to image segmentation, and present the results of segmenting a number of medical and natural images using our techniques.