图像分割：高效图基方法

需积分: 10 91 浏览量更新于2024-07-19 1 收藏 338KB PDF 举报

"本文介绍了Efficient Graph-Based Image Segmentation，一种用于图像分割的高效算法，它在Selective Search和R-CNN等应用中具有重要作用。该算法基于图像的图表示，通过定义边界的证据判断来实现区域分割。" 图像分割是计算机视觉领域的一个核心问题，其目的是将图像划分为多个有意义的区域，每个区域内的像素共享相似的特性，如颜色、纹理或亮度。在给定的资源中，作者Pedro F. Felzenszwalb和Daniel P. Huttenlocher提出了一种高效的图基图像分割算法，它利用图像的图结构来衡量两个区域之间的边界证据。该算法的核心是定义一个谓词，用于评估两个相邻区域间的分界线证据。这个谓词可能是基于像素间的差异性、相似性或者其他图像特征的度量。然后，算法采用贪心策略，根据这个谓词的评估结果逐步构建和优化分割。尽管采取了局部决策，但实验表明，该算法能够生成满足全局性质的分割结果，即即使在局部决策过程中，也能得到整体一致的分割。在实现上，算法采用了两种不同的局部邻域来构建图，这可能包括像素的4-邻接或8-邻接，或者更复杂的邻域结构。通过这种方式，算法可以适应不同尺度和形状的图像特征。此外，该方法的一个显著优点是，它能够在低变异性图像区域保留细节，同时忽略高变异性区域的细节，这有助于提高分割的准确性和鲁棒性。在实际应用中，这种图基分割算法运行时间接近于图边数的线性时间复杂度，这意味着它对于大规模图像数据集来说是可扩展的，并且在实际运行速度上也表现出色。关键词包括图像分割、聚类和感知组织，这些都反映了该算法涉及的主要理论和应用领域。 Efficient Graph-Based Image Segmentation提供了一种在效率与精度之间取得平衡的图像分割方法，它对于图像分析、目标检测等任务具有重要价值，特别是在Selective Search和R-CNN等深度学习框架中，作为预处理步骤，能够提升后续任务的性能。

Section 3 makes the problem of ﬁnding a good segmentation NP-hard.

2 Related Work

There is a large literature on segmentation and clustering, dating back over 30 years,

with applications in many areas other than computer vision (cf. [9]). In this section

we brieﬂy consider some of the related work that is most relevant to our approach:

early graph-based methods (e.g., [15, 19]), region merging techniques (e.g., [5, 11]),

techniques based on mapping image pixels to some feature space (e.g., [3, 4]) and

more recent formulations in terms of graph cuts (e.g., [14, 18]) and spectral methods

(e.g., [16]).

Graph-based image segmentation techniques generally represent the problem in

terms of a graph G = (V, E) where each node v

∈ V corresponds to a pixel in the

image, and the edges in E connect certain pairs of neighboring pixels. A weight

is associated with each edge based on some property of the pixels that it connects,

such as their image intensities. Depending on the method, there may or may not

be an edge connecting each pair of vertices. The earliest graph-based methods use

ﬁxed thresholds and local measures in computing a segmentation. The work of Zahn

[19] presents a segmentation method based on the minimum spanning tree (MST)

of the graph. This method has been applied both to point clustering and to image

segmentation. For image segmentation the edge weights in the graph are based on

the diﬀerences between pixel intensities, whereas for point clustering the weights are

based on distances between points.

The segmentation criterion in Zahn’s method is to break MST edges with large

weights. The inadequacy of simply breaking large edges, however, is illustrated by

the example in Figure 1. As mentioned in the introduction, diﬀerences between

pixels within the high variability region can be larger than those between the ramp

and the constant region. Thus, depending on the threshold, simply breaking large

weight edges would either result in the high variability region being split into multiple

regions, or would merge the ramp and the constant region together. The algorithm

proposed by Urquhart [15] attempts to address this shortcoming by normalizing the

weight of an edge using the smallest weight incident on the vertices touching that

edge. When applied to image segmentation problems, however, this is not enough to

provide a reasonable adaptive segmentation criterion. For example, many pixels in

the high variability region of Figure 1 have some neighbor that is highly similar.

Another early approach to image segmentation is that of splitting and merging

regions according to how well each region ﬁts some uniformity criterion (e.g., [5,

11]). Generally these uniformity criteria obey a subset property, such that when

a uniformity predicate U(A) is true for some region A then U(B) is also true for

any B ⊂ A. Usually such criteria are aimed at ﬁnding either uniform intensity or

uniform gradient regions. No region uniformity criterion that has been proposed to

date could be used to correctly segment the example in Figure 1, due to the high

variation region. Either this region would be split into pieces, or it would be merged

with the surrounding area.

A number of approaches to segmentation are based on ﬁnding compact clusters

in some feature space (cf. [3, 9]). These approaches generally assume that the image

is piecewise constant, because searching for pixels that are all close together in some

feature space implicitly requires that the pixels be alike (e.g., similar color). A recent

technique using feature space clustering [4] ﬁrst transforms the data by smoothing

it in a way that preserves boundaries between regions. This smoothing operation

has the overall eﬀect of bringing points in a cluster closer together. The method

then ﬁnds clusters by dilating each point with a hypersphere of some ﬁxed radius,

and ﬁnding connected components of the dilated points. This technique for ﬁnding

clusters does not require all the points in a cluster to lie within any ﬁxed distance.

The technique is actually closely related to the region comparison predicate that we

introduce in Section 3.1, which can be viewed as an adaptive way of selecting an

appropriate dilation radius. We return to this issue in Section 6.

Finally we brieﬂy consider a class of segmentation methods based on ﬁnding min-

imum cuts in a graph, where the cut criterion is designed in order to minimize the

similarity between pixels that are being split. Work by Wu and Leahy [18] introduced

such a cut criterion, but it was biased toward ﬁnding small components. This bias was

addressed with the normalized cut criterion developed by Shi and Malik [14], which

takes into account self-similarity of regions. These cut-based approaches to segmenta-

tion capture non-local properties of the image, in contrast with the early graph-based

methods. However, they provide only a characterization of each cut rather than of

the ﬁnal segmentation.

The normalized cut criterion provides a signiﬁcant advance over the previous work

in [18], both from a theoretical and practical point of view (the resulting segmenta-

剩余25页未读，继续阅读

梅mmmmm

粉丝: 18
资源: 4

图像分割：高效图基方法

Efficient Graph based image Segmentation：一种简单高效的基于图的图像分割算法-matlab开发

Efficient Graph-Based Image Segmentation.rar

论文Efficient Graph- Based Image Segmentation的实现代码，c/c++版本的，支持jpg格式输入输出

Efficient Graph-Based Image Segmentation & k-means Image Segmentation

efficient graph-based im- age segmentation baidu xueshu

efficient_graph.rar_graph_graph Segmentation_graph-based_image s

Efficient_Graph_Based_Image_Segmentation.rar_.ppm_300_image segm

Graph_Based_Image_Segmentation（C++）

分割图像matlab代码-pf-segmentation:Matlab[PFelzenszwalb2004]的图像分割算法

Color image segmentation based on mean shift.pdf

最新资源