Prime Object Proposals with Randomized Prim's Algorithm

Santiago Manen, Matthieu Guillaumin, Luc Van Gool

International Conference on Computer Vision 2013

Paper download
Code download


Generic object detection is the challenging task of proposing windows that localize all the objects in an image, regardless of their classes. Such detectors have recently been shown to benefit many applications such as speeding-up class-specific object detection, weakly supervised learning of object detectors and object discovery.

In this paper, we introduce a novel and very efficient method for generic object detection based on a randomized version of Prim's algorithm.Using the connectivity graph of an image's superpixels, with weights modelling the probability that neighbouring superpixels belong to the same object, the algorithm generates random partial spanning trees with large expected sum of edge weights. Object localizations are proposed as bounding-boxes of those partial trees.

Our method has several benefits compared to the state of the art. Thanks to the efficiency of Prim's algorithm, it samples proposals very quickly: 1000 proposals are obtained in about 0.7s. With proposals bound to superpixel boundaries yet diversified by randomization, it yields very high detection rates and windows that tightly fit objects.

In extensive experiments on the challenging PASCAL VOC 2007 and 2012 and SUN2012 benchmark datasets, we show that our method improves over state-of-the-art competitors for a wide range of evaluation scenarios.


These examples show the accuracy of the object proposals for images of the VOC 2007 dataset. The best windows out of 1000 proposed by our method are shown in yellow and for the ground-truth annotations in blue.

BibTex reference

@string{iccv="International Conference on Computer Vision (ICCV)"}
title = {{Prime Object Proposals with Randomized Prim's Algorithm}},
author = {Man\'en, Santiago and Guillaumin, Matthieu and Van Gool, Luc},
booktitle = iccv,
year = {2013},
month = dec,
pdf = pubroot # {Manen2013iccv.pdf},
thumbnail = pubroot # {thumbs/Manen2013iccv.png},


The authors gratefully acknowledge support by Toyota.
This work was supported by the European Research Council (ERC) under the project VarCity (#273940).

Please report problems with this page to Santiago Manen
Last updated on Wednesday, 30th October, 2013