  Region search is widely used for object localization. Typically, the region
search methods project the score of a classifier into an image plane, and then
search the region with the maximal score. The recently proposed region search
methods, such as efficient subwindow search and efficient region search, %which
localize objects from the score distribution on an image are much more
efficient than sliding window search. However, for some classifiers and tasks,
the projected scores are nearly all positive, and hence maximizing the score of
a region results in localizing nearly the entire images as objects, which is
meaningless.
  In this paper, we observe that the large scores are mainly concentrated on or
around objects. Based on this observation, we propose a method, named level set
maximum-weight connected subgraph (LS-MWCS), which localizes objects with
arbitrary shapes by searching regions with the densest score rather than the
maximal score. The region density can be controlled by a parameter flexibly.
And we prove an important property of the proposed LS-MWCS, which guarantees
that the region with the densest score can be searched. Moreover, the LS-MWCS
can be efficiently optimized by belief propagation. The method is evaluated on
the problem of weakly-supervised object localization, and the quantitative
results demonstrate the superiorities of our LS-MWCS compared to other
state-of-the-art methods.
