Abstract:

Cluatering problems often entail more than a single objective. A typical
goal is to group together similar objects, or pixels in the case of
image processing.  At the same time another goal is to have each group
distinctly dissimilar from the rest and possibly to have the group size
fairly large. These goals are often combined as a ratio optimization
problem. One example of such problem is a variant of the normalized cut
problem, another is the ratio regions problem. We devise here the first
polynomial time algorithms solving optimally the ratio region problem
and the variant of normalized cut, as well as few other ratio problems.
The algorithms are efficient and combinatorial in contrast with nonlinear
continuous approaches used in the image segmentation literature which
often employ spectral techniques.  Such techniques deliver solutions in
real numbers which are not feasible to the discrete partitioning problem.
Furthermore, these continuous approaches are computationally expensive
compared to the algorithms proposed here. The algorithms presented here
use as a subroutine a minimum s,t-cut procedure on a related graph which
is of polynomial size. The output consists of the optimal solution to the
respective ratio problem, as well as a sequence of nested solutions with
respect to any relative weighting of the objectives of the numerator and
denominator.  We will mention additional multiple criteria problems that
are successfuly addressed with combinatorial polynomial time algorithm,
such as the co-segmentation problem.