A[i;i]works poorly, as decimation disconnects pixels in
the afﬁnity matrix, but the eigenvectors of the decimated
squared afﬁnity matrix A2[i;i]are similar to those of A,
because by squaring the matrix before decimation we
intuitively allow each pixel to propagate information to
all of its neighbors in the graph, maintaining connections even after decimation. Our algorithm works by
efﬁciently computing A2[i;i]asA[:;i]TA[:;i]1(the naive
approach of ﬁrst squaring Aand then decimating it is
prohibitively expensive), computing the eigenvectors of
A2[i;i], and then “upsampling” those eigenvectors back
to the space of the original image by pre-multiplying
byA[:;i]. This squaring-and-decimation procedure can
be applied recursively several times, each application
improving efﬁciency while slightly sacriﬁcing accuracy.
Pseudocode for our algorithm, which we call
“DNCuts” (Downsampled Normalized Cuts) is given in
We propose a unified approach for bottom-up hierarchical image segmentation
and object proposal generation for recognition, called Multiscale Combinatorial
Grouping (MCG). For this purpose, we first develop a fast normalized cuts
algorithm. We then propose a high-performance hierarchical segmenter that makes
effective use of multiscale information. Finally, we propose a grouping
strategy that combines our multiscale regions into highly-accurate object
proposals by exploring efficiently their combinatorial space. We also present
Single-scale Combinatorial Grouping (SCG), a faster version of MCG that
produces competitive proposals in under five second per image. We conduct an
extensive and comprehensive empirical validation on the BSDS500, SegVOC12, SBD,
and COCO datasets, showing that MCG produces state-of-the-art contours,
hierarchical regions, and object proposals.
Jordi Pont-Tuset Pablo Arbelaez Jonathan T. Barron Ferran Marques Jitendra Malik