Memory efficient max flow for multi-label submodular MRFs

Thalaiyasingam Ajanthan; Richard Hartley; Mathieu Salzmann

doi:10.1109/CVPR.2016.632

Memory efficient max flow for multi-label submodular MRFs

Thalaiyasingam Ajanthan, Richard Hartley, Mathieu Salzmann

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flow based on an encoding of the labels proposed by Ishikawa, in which each variable Xi is represented by l nodes (where l is the number of labels) arranged in a column. However, this method in general requires 2 l2 edges for each pair of neighbouring variables. This makes it inapplicable to realistic problems with many variables and labels, due to excessive memory requirement. In this paper, we introduce a variant of the max-flow algorithm that requires much less storage. Consequently, our algorithm makes it possible to optimally solve multi-label submodular problems involving large numbers of variables and labels on a standard computer.

Original language	English
Title of host publication	Proceedings - 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016
Publisher	IEEE Computer Society
Pages	5867-5876
Number of pages	10
ISBN (Electronic)	9781467388504
DOIs	https://doi.org/10.1109/CVPR.2016.632
Publication status	Published - 9 Dec 2016
Event	29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016 - Las Vegas, United States Duration: 26 Jun 2016 → 1 Jul 2016

Publication series

Name	Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
Volume	2016-December
ISSN (Print)	1063-6919

Conference

Conference	29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016
Country/Territory	United States
City	Las Vegas
Period	26/06/16 → 1/07/16

Access to Document

10.1109/CVPR.2016.632

Cite this

Ajanthan, T., Hartley, R., & Salzmann, M. (2016). Memory efficient max flow for multi-label submodular MRFs. In Proceedings - 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016 (pp. 5867-5876). Article 7781001 (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition; Vol. 2016-December). IEEE Computer Society. https://doi.org/10.1109/CVPR.2016.632

@inproceedings{1f137b72716445e48db7c7d03bcdcb0a,

title = "Memory efficient max flow for multi-label submodular MRFs",

abstract = "Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flow based on an encoding of the labels proposed by Ishikawa, in which each variable Xi is represented by l nodes (where l is the number of labels) arranged in a column. However, this method in general requires 2 l2 edges for each pair of neighbouring variables. This makes it inapplicable to realistic problems with many variables and labels, due to excessive memory requirement. In this paper, we introduce a variant of the max-flow algorithm that requires much less storage. Consequently, our algorithm makes it possible to optimally solve multi-label submodular problems involving large numbers of variables and labels on a standard computer.",

author = "Thalaiyasingam Ajanthan and Richard Hartley and Mathieu Salzmann",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016 ; Conference date: 26-06-2016 Through 01-07-2016",

year = "2016",

month = dec,

day = "9",

doi = "10.1109/CVPR.2016.632",

language = "English",

series = "Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition",

publisher = "IEEE Computer Society",

pages = "5867--5876",

booktitle = "Proceedings - 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016",

address = "United States",

}

Ajanthan, T, Hartley, R & Salzmann, M 2016, Memory efficient max flow for multi-label submodular MRFs. in Proceedings - 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016., 7781001, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2016-December, IEEE Computer Society, pp. 5867-5876, 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, United States, 26/06/16. https://doi.org/10.1109/CVPR.2016.632

Memory efficient max flow for multi-label submodular MRFs. / Ajanthan, Thalaiyasingam; Hartley, Richard; Salzmann, Mathieu.
Proceedings - 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016. IEEE Computer Society, 2016. p. 5867-5876 7781001 (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition; Vol. 2016-December).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Memory efficient max flow for multi-label submodular MRFs

AU - Ajanthan, Thalaiyasingam

AU - Hartley, Richard

AU - Salzmann, Mathieu

PY - 2016/12/9

Y1 - 2016/12/9

N2 - Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flow based on an encoding of the labels proposed by Ishikawa, in which each variable Xi is represented by l nodes (where l is the number of labels) arranged in a column. However, this method in general requires 2 l2 edges for each pair of neighbouring variables. This makes it inapplicable to realistic problems with many variables and labels, due to excessive memory requirement. In this paper, we introduce a variant of the max-flow algorithm that requires much less storage. Consequently, our algorithm makes it possible to optimally solve multi-label submodular problems involving large numbers of variables and labels on a standard computer.

AB - Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flow based on an encoding of the labels proposed by Ishikawa, in which each variable Xi is represented by l nodes (where l is the number of labels) arranged in a column. However, this method in general requires 2 l2 edges for each pair of neighbouring variables. This makes it inapplicable to realistic problems with many variables and labels, due to excessive memory requirement. In this paper, we introduce a variant of the max-flow algorithm that requires much less storage. Consequently, our algorithm makes it possible to optimally solve multi-label submodular problems involving large numbers of variables and labels on a standard computer.

UR - http://www.scopus.com/inward/record.url?scp=84986253734&partnerID=8YFLogxK

U2 - 10.1109/CVPR.2016.632

DO - 10.1109/CVPR.2016.632

M3 - Conference contribution

T3 - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition

SP - 5867

EP - 5876

BT - Proceedings - 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016

PB - IEEE Computer Society

T2 - 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016

Y2 - 26 June 2016 through 1 July 2016

ER -

Memory efficient max flow for multi-label submodular MRFs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this