Conference proceeding
Fast dynamic programming for labeling problems with ordering constraints
2012 IEEE Conference on Computer Vision and Pattern Recognition, pp.1728-1735
06/2012
DOI: 10.1109/CVPR.2012.6247868
Abstract
Many computer vision applications can be formulated as labeling problems. However, multilabeling problems are usually very challenging to solve, especially when some ordering constraints are enforced. We solve in this paper a five-parts labeling problem proposed in [6, 7]. In this model, one wants to find an optimal labeling for an image with five possible parts: "left", "right", "top", "bottom" and "center". The geometric ordering constraints can be read naturally from the names. No previous method can solve the problem with globally optimal solutions in a linear space complexity. We propose an efficient dynamic programming based algorithm which guarantees the global optimal labeling for the five-parts model. The time complexity is O(N 1.5 ) and the space complexity is O(N), with N being the number of pixels in the image. In practice, it runs faster than previous methods. Moreover, it works for both 4-neighborhood and 8-neighborhood settings, and can be easily parallelized for GPU.
Details
- Title: Subtitle
- Fast dynamic programming for labeling problems with ordering constraints
- Creators
- Junjie Bai - University of IowaQi Song - University of IowaOlga Veksler - Western UniversityXiaodong Wu - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp.1728-1735
- DOI
- 10.1109/CVPR.2012.6247868
- ISSN
- 1063-6919
- Publisher
- IEEE
- Language
- English
- Date published
- 06/2012
- Academic Unit
- Electrical and Computer Engineering; Radiation Oncology; The Iowa Institute for Biomedical Imaging
- Record Identifier
- 9984197227502771
Metrics
19 Record Views