Investigation of measures for grouping by graph partitioning
Investigation of measures for grouping by graph partitioning
复制标题
DOI：
10.1109/cvpr.2001.990482
复制
发表时间：
2001-12
期刊：
影响因子：
--
通讯作者：
P. Soundararajan;Sudeep Sarkar
中科院分区：
文献类型：
--
作者：
P. Soundararajan;Sudeep Sarkar
逐图分割是感知组织的有效引擎。这种图划分过程主要是出于计算效率的考虑，通常被实现为递归二分区，其中在每个步骤中，图基于分区度量被分成两部分。我们研究了四个这样的措施，即，最小切割，平均切割，Shi-Malik规范化切割，和Shi-Malik规范化切割的变化。使用概率分析，我们表明，最小化的平均削减和归一化的削减措施，使用递归二分区，平均而言，会导致正确的分割。平均而言，最小切割和归一化切割的变化不会导致正确的分割，并且我们可以精确地表达条件。基于严格的经验评估，我们还表明，在实践中，使用最小值，平均值或归一化切割生成的组的质量在统计上是等同的对象识别，即最好的，平均值和质量的变化在统计上是等同的。我们还发现，对于某些图像类，如空中和场景与人造物体在人造环境中，分组分区的性能是最差的，无论切割措施。
Grouping by graph partitioning is an effective engine for perceptual organization. This graph partitioning process, mainly motivated by computational efficiency considerations, is usually implemented as recursive bi-partitioning, where at each step the graph is broken into two parts based on a partitioning measure. We study four such measures, namely, the minimum cut, average cut, Shi-Malik normalized cut, and a variation of the Shi-Malik normalized cut. Using probabilistic analysis we show that the minimization of the average cut and the normalized cut measure, using recursive bi-partitioning will, on an average, result in the correct segmentation. The minimum cut and the variation of the normalized cut will, on an average, not result in the correct segmentation and we can precisely express the conditions. Based on a rigorous empirical evaluation, we also show that, in practice, the quality of the groups generated using minimum, average or normalized cuts are statistically equivalent for object recognition, i.e. the best, the mean, and the variation of the qualities are statistically equivalent. We also find that for certain image classes, such as aerial and scenes with man-made objects in man-made surroundings, the performance of grouping by partitioning is the worst, irrespective of the cut measure.