TY - GEN
T1 - Fast multi-labelling for stereo matching
AU - Zhang, Yuhang
AU - Hartley, Richard
AU - Wang, Lei
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=78149329131&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-15558-1_38
DO - 10.1007/978-3-642-15558-1_38
M3 - Conference contribution
SN - 364215557X
SN - 9783642155574
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 524
EP - 537
BT - Computer Vision, ECCV 2010 - 11th European Conference on Computer Vision, Proceedings
PB - Springer Verlag
T2 - 11th European Conference on Computer Vision, ECCV 2010
Y2 - 10 September 2010 through 11 September 2010
ER -