nips nips2010 nips2010-234 nips2010-234-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: William Brendel, Sinisa Todorovic
Abstract: Given an ensemble of distinct, low-level segmentations of an image, our goal is to identify visually “meaningful” segments in the ensemble. Knowledge about any specific objects and surfaces present in the image is not available. The selection of image regions occupied by objects is formalized as the maximum-weight independent set (MWIS) problem. MWIS is the heaviest subset of mutually non-adjacent nodes of an attributed graph. We construct such a graph from all segments in the ensemble. Then, MWIS selects maximally distinctive segments that together partition the image. A new MWIS algorithm is presented. The algorithm seeks a solution directly in the discrete domain, instead of relaxing MWIS to a continuous problem, as common in previous work. It iteratively finds a candidate discrete solution of the Taylor series expansion of the original MWIS objective function around the previous solution. The algorithm is shown to converge to an optimum. Our empirical evaluation on the benchmark Berkeley segmentation dataset shows that the new algorithm eliminates the need for hand-picking optimal input parameters of the state-of-the-art segmenters, and outperforms their best, manually optimized results.
[1] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE TPAMI, vol. 22, no. 8, pp. 888–905, 2000.
[2] M. Pavan and M. Pelillo, “Dominant sets and pairwise clustering,” IEEE TPAMI, vol. 29, no. 1, pp. 167– 172, 2007.
[3] D. Comaniciu and P. Meer, “Meanshift: a robust approach toward feature space analysis,” IEEE TPAMI, vol. 24, no. 5, pp. 603–619, 2002.
[4] M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” IJCV, vol. V1, no. 4, pp. 321–331, 1988.
[5] N. Ahuja, “A transform for multiscale image segmentation by integrated edge and region detection,” IEEE TPAMI, vol. 18, no. 12, pp. 1211–1235, 1996.
[6] X. Ren, C. Fowlkes, and J. Malik, “Learning probabilistic models for contour completion in natural images,” IJCV, vol. 77, no. 1-3, pp. 47–63, 2008.
[7] P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, “From contours to regions: An empirical evaluation,” in CVPR, 2009.
[8] S. Bagon, O. Boiman, and M. Irani, “What is a good image segment? A unified approach to segment extraction,” in ECCV, 2008.
[9] S. Todorovic and N. Ahuja, “Texel-based texture segmentation,” in ICCV, 2009.
[10] B. Russell, A. Efros, J. Sivic, B. Freeman, and A. Zisserman, “Segmenting scenes by matching image composites,” in NIPS, 2009.
[11] L. Trevisan, “Inapproximability of combinatorial optimization problems,” Electronic Colloquium on Computational Complexity, Tech. Rep. TR04065, 2004.
[12] G. Palubeckis, “Iterated tabu search for the unconstrained binary quadratic optimization problem,” Informatica, vol. 17, no. 2, pp. 279–296, 2006.
[13] D. Warrier, W. E. Wilhelm, J. S. Warren, and I. V. Hicks, “A branch-and-price approach for the maximum weight independent set problem,” Netw., vol. 46, no. 4, pp. 198–209, 2005.
[14] S. Sanghavi, D. Shah, and A. S. Willsky, “Message-passing for max-weight independent set,” in NIPS, 2007.
[15] M. Groetschel, L. Lovasz, and A. Schrijver, “Polynomial algorithms for perfect graphs,” in Topics on Perfect Graphs, C. Berge and V. Chvatal, Eds. North-Holland, 1984, vol. 88, pp. 325 – 356.
[16] M. Todd, “Semidefinite optimization,” Acta Numerica, vol. 10, pp. 515–560, 2001.
[17] I. M. Bomze, M. Pelillo, and V. Stix, “Approximating the maximum weight clique using replicator dynamics,” IEEE Trans. Neural Net., vol. 11, no. 6, pp. 1228–1241, 2000.
[18] S. Busygin, C. Ag, S. Butenko, and P. M. Pardalos, “A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere,” Journal of Combinatorial Optimization, vol. 6, pp. 287–297, 2002.
[19] M. P. Kumar and D. Koller, “Efficiently selecting regions for scene understanding,” in CVPR, 2010.
[20] M. Leordeanu, M. Hebert, and R. Sukthankar, “An integer projected fixed point method for graph matching and MAP inference,” in NIPS, 2009.
[21] S. Gold and A. Rangarajan, “A graduated assignment algorithm for graph matching,” IEEE TPAMI, vol. 18, no. 4, pp. 377–388, 1996.
[22] M. Varma and R. Garg, “Locally invariant fractal features for statistical texture classification,” in ICCV, 2007.
[23] D. Martin, C. Fowlkes, D. Tal, and J. Malik, “A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics,” in ICCV, 2001.
[24] J. E. Beasley, “Obtaining test problems via internet,” Journal of Global Optimization, vol. 8, no. 4, pp. 429–433, 1996.
[25] M. Galun, E. Sharon, R. Basri, and A. Brandt, “Texture segmentation by multiscale aggregation of filter responses and shape elements,” in ICCV, 2003, pp. 716–723.
[26] R. Unnikrishnan, C. Pantofaru, and M. Hebert, “Toward objective evaluation of image segmentation algorithms,” IEEE TPAMI, vol. 29, no. 6, pp. 929–944, 2007. 9