Abstract

We describe a new fast algorithm for multi-labelling prob- lems. In general, a multi-labelling problem is NP-hard. Widely used algo- rithms 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 respec- tively. 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 effi- ciency can be varied through using different parameters. The advantage of our method is validated by experiments.