Computation complexity of branch-and-bound model selection

Segmentation problems are one of the most important areas of research in computer vision. While segmentation problems are generally solved with clustering paradigms, they formulate the problem as recursive. Additionally, most approaches need the number of clusters to be known beforehand. This requir...

Full description

Saved in:
Bibliographic Details
Main Authors: Thakoor, Ninad, Devarajan, Venkat, Gao, Jean
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Clustering algorithms
Computational complexity
Computer science
Computer vision
Cost function
Image segmentation
Motion segmentation
Sampling methods
Spatial coherence
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Segmentation problems are one of the most important areas of research in computer vision. While segmentation problems are generally solved with clustering paradigms, they formulate the problem as recursive. Additionally, most approaches need the number of clusters to be known beforehand. This requirement is unreasonable for majority of the computer vision problems. This paper analyzes the model selection perspective which can overcome these limitations. Under this framework multiple hypotheses for cluster centers are generated using spatially coherent sampling. An optimal subset of these hypotheses is selected according to a model selection criterion. The selection can be carried out with a branch-and-bound procedure. The worst case complexity of any branch-and-bound algorithm is exponential. However, the average complexity of the algorithm is significantly lower. In this paper, we develop a framework for analysis of average complexity of the algorithm from the statistics of model selection costs.
ISSN:1550-5499
2380-7504
DOI:10.1109/ICCV.2009.5459420