Binary partitioning, perceptual grouping, and restoration with semidefinite programming
| Autor: | Christoph Schnörr, Jens Keuchel, Daniel Cremers, Christian Schellewald |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Semidefinite programming
Mathematical optimization Binary decision diagram Spectral graph theory Applied Mathematics Graph theory Computational Theory and Mathematics Artificial Intelligence Cut Convex optimization Combinatorial optimization Computer Vision and Pattern Recognition Relaxation (approximation) Software Mathematics |
| Zdroj: | IEEE Transactions on Pattern Analysis and Machine Intelligence. 25:1364-1379 |
| ISSN: | 0162-8828 |
| DOI: | 10.1109/tpami.2003.1240111 |
| Popis: | We introduce a novel optimization method based on semidefinite programming relaxations to the field of computer vision and apply it to the combinatorial problem of minimizing quadratic functionals in binary decision variables subject to linear constraints. The approach is (tuning) parameter-free and computes high-quality combinatorial solutions using interior-point methods (convex programming) and a randomized hyperplane technique. Apart from a symmetry condition, no assumptions (such as metric pairwise interactions) are made with respect to the objective criterion. As a consequence, the approach can be applied to a wide range of problems. Applications to unsupervised partitioning, figure-ground discrimination, and binary restoration are presented along with extensive ground-truth experiments. From the viewpoint of relaxation of the underlying combinatorial problem, we show the superiority of our approach to relaxations based on spectral graph theory and prove performance bounds. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|