Abstract
-
We describe a new fast algorithm for multi-labelling problems.
In general, a multi-labelling problem is NP-hard.Widely used algorithms
like α-expansion can reach a suboptimal result in a time linear in
the number of the labels. In this paper, we propose an algorithm which
can obtain results of comparable quality polynomially faster. We use the
Divide and Conquer paradigm to separate the complexities induced by
the label set and the variable set, and deal with each of them respectively.
Such a mechanism improves the solution speed without depleting
the memory resource, hence it is particularly valuable for applications
where the variable set and the label set are both huge. Another merit of
the proposed method is that the trade-off between quality and time efficiency
can be varied through using different parameters. The advantage
of our method is validated by experiments.