P3 and beyond: solving energies with higher order cliques
In this paper we extend the class of energy functions for which the optimal alpha-expansion and alphabeta-swap moves can be computed in polynomial time. Specifically, we introduce a class of higher order clique potentials and show that the expansion and swap moves for any energy function composed of...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
IEEE
2007
|
| _version_ | 1826315003996667904 |
|---|---|
| author | Kohli, P Kumar, MP Torr, PHS |
| author_facet | Kohli, P Kumar, MP Torr, PHS |
| author_sort | Kohli, P |
| collection | OXFORD |
| description | In this paper we extend the class of energy functions for which the optimal alpha-expansion and alphabeta-swap moves can be computed in polynomial time. Specifically, we introduce a class of higher order clique potentials and show that the expansion and swap moves for any energy function composed of these potentials can be found by minimizing a submodular function. We also show that for a subset of these potentials, the optimal move can be found by solving an st-mincut problem. We refer to this subset as the P 3 Potts model. Our results enable the use of powerful move making algorithms i.e. alpha-expansion and alphabeta-swap for minimization of energy functions involving higher order cliques. Such functions have the capability of modelling the rich statistics of natural scenes and can be used for many applications in computer vision. We demonstrate their use on one such application i.e. the texture based video segmentation problem. |
| first_indexed | 2024-12-09T03:18:11Z |
| format | Conference item |
| id | oxford-uuid:3e3e7e12-3978-48de-91d5-a669519e3641 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:18:11Z |
| publishDate | 2007 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:3e3e7e12-3978-48de-91d5-a669519e36412024-10-31T12:47:28ZP3 and beyond: solving energies with higher order cliquesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:3e3e7e12-3978-48de-91d5-a669519e3641EnglishSymplectic ElementsIEEE2007Kohli, PKumar, MPTorr, PHSIn this paper we extend the class of energy functions for which the optimal alpha-expansion and alphabeta-swap moves can be computed in polynomial time. Specifically, we introduce a class of higher order clique potentials and show that the expansion and swap moves for any energy function composed of these potentials can be found by minimizing a submodular function. We also show that for a subset of these potentials, the optimal move can be found by solving an st-mincut problem. We refer to this subset as the P 3 Potts model. Our results enable the use of powerful move making algorithms i.e. alpha-expansion and alphabeta-swap for minimization of energy functions involving higher order cliques. Such functions have the capability of modelling the rich statistics of natural scenes and can be used for many applications in computer vision. We demonstrate their use on one such application i.e. the texture based video segmentation problem. |
| spellingShingle | Kohli, P Kumar, MP Torr, PHS P3 and beyond: solving energies with higher order cliques |
| title | P3 and beyond: solving energies with higher order cliques |
| title_full | P3 and beyond: solving energies with higher order cliques |
| title_fullStr | P3 and beyond: solving energies with higher order cliques |
| title_full_unstemmed | P3 and beyond: solving energies with higher order cliques |
| title_short | P3 and beyond: solving energies with higher order cliques |
| title_sort | p3 and beyond solving energies with higher order cliques |
| work_keys_str_mv | AT kohlip p3andbeyondsolvingenergieswithhigherordercliques AT kumarmp p3andbeyondsolvingenergieswithhigherordercliques AT torrphs p3andbeyondsolvingenergieswithhigherordercliques |