iccv iccv2013 iccv2013-329 iccv2013-329-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Michael Maire, Stella X. Yu
Abstract: We reexamine the role of multiscale cues in image segmentation using an architecture that constructs a globally coherent scale-space output representation. This characteristic is in contrast to many existing works on bottom-up segmentation, whichprematurely compress information into a single scale. The architecture is a standard extension of Normalized Cuts from an image plane to an image pyramid, with cross-scale constraints enforcing consistency in the solution while allowing emergence of coarse-to-fine detail. We observe that multiscale processing, in addition to improving segmentation quality, offers a route by which to speed computation. We make a significant algorithmic advance in the form of a custom multigrid eigensolver for constrained Angular Embedding problems possessing coarseto-fine structure. Multiscale Normalized Cuts is a special case. Our solver builds atop recent results on randomized matrix approximation, using a novel interpolation operation to mold its computational strategy according to crossscale constraints in the problem definition. Applying our solver to multiscale segmentation problems demonstrates speedup by more than an order of magnitude. This speedup is at the algorithmic level and carries over to any implementation target.
[1] P. Arbel ´aez, M. Maire, C. Fowlkes, and J. Malik. Contour detection and hierarchical image segmentation. PAMI, 2011.
[2] M. Brezina, T. Manteuffel, S. McCormick, J. Ruge, G. Sanders, and P. Vassilevski. A generalized eigensolver based on smoothed aggregation (GES-SA) for initializing smoothed aggregation multigrid (SA). Numerical Linear Algebra with Applications, 15(2-3):249–269, 2008.
[3] B. Catanzaro, B.-Y. Su, N. Sundaram, Y. Lee, M. Murphy, and K. Keutzer. Efficient, high-quality image contour detection. ICCV, 2009.
[4] C. Chennubhotla and A. D. Jepson. Hierarchical eigensolver for transition matrices in spectral methods. NIPS, 2005.
[5] T. Cour, F. Benezit, and J. Shi. Spectral segmentation with
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17] multiscale graph decomposition. CVPR, 2005. C. Fowlkes, S. Belongie, F. Chung, and J. Malik. Spectral grouping using the Nystr ¨om method. PAMI, 2004. N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIREV, 2011. D. Kushnir, M. Galun, and A. Brandt. Efficient multilevel eigensolvers with applications to data analysis tasks. PAMI, 2010. M. Maire. Simultaneous segmentation and figure/ground organization using angular embedding. ECCV, 2010. M. Maire, S. X. Yu, and P. Perona. Object detection and segmentation from joint embedding of parts and pixels. ICCV, 2011. S. Maji, N. K. Vishnoi, and J. Malik. Biased normalized cuts. CVPR, 2011. 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. ICCV, 2001 . E. Sharon, M. Galun, D. Sharon, R. Basri, and A. Brandt. Hierarchy and adaptivity in segmenting visual scenes. Nature, 442:810–813, 2006. J. Shi and J. Malik. Normalized cuts and image segmentation. PAMI, 2000. S. X. Yu. Segmentation induced by scale invariance. CVPR, 2005. S. X. Yu. Angular embedding: A robust quadratic criterion. PAMI, 2012. S. X. Yu and J. Shi. Segmentation given partial grouping constraints. PAMI, 2004. 2191