P3 & beyond: move making algorithms for solving higher order functions
In this paper, we extend the class of energy functions for which the optimal \alpha-expansion and \alpha \beta-swap moves can be computed in polynomial time. Specifically, we introduce a novel family of higher order clique potentials, and show that the expansion and swap moves for any energy functio...
| প্রধান লেখক: | , , |
|---|---|
| বিন্যাস: | Journal article |
| ভাষা: | English |
| প্রকাশিত: |
IEEE
2008
|
| _version_ | 1826313374026170368 |
|---|---|
| author | Kohli, P Pawan Kumar, M Torr, PHS |
| author_facet | Kohli, P Pawan Kumar, M 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 \alpha \beta-swap moves can be computed in polynomial time. Specifically, we introduce a novel family 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 {\cal P}^n Potts model. Our results enable the use of powerful \alpha-expansion and \alpha \beta-swap move making algorithms for minimization of energy functions involving higher order cliques. Such functions have the capability of modeling the rich statistics of natural scenes and can be used for many applications in Computer Vision. We demonstrate their use in one such application, i.e., the texture-based image or video-segmentation problem. |
| first_indexed | 2024-09-25T04:13:50Z |
| format | Journal article |
| id | oxford-uuid:5e73ec7f-c5fa-43e5-a212-100439db263e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:13:50Z |
| publishDate | 2008 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:5e73ec7f-c5fa-43e5-a212-100439db263e2024-07-08T16:03:44ZP3 & beyond: move making algorithms for solving higher order functionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:5e73ec7f-c5fa-43e5-a212-100439db263eEnglishSymplectic ElementsIEEE2008Kohli, PPawan Kumar, MTorr, PHSIn this paper, we extend the class of energy functions for which the optimal \alpha-expansion and \alpha \beta-swap moves can be computed in polynomial time. Specifically, we introduce a novel family 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 {\cal P}^n Potts model. Our results enable the use of powerful \alpha-expansion and \alpha \beta-swap move making algorithms for minimization of energy functions involving higher order cliques. Such functions have the capability of modeling the rich statistics of natural scenes and can be used for many applications in Computer Vision. We demonstrate their use in one such application, i.e., the texture-based image or video-segmentation problem. |
| spellingShingle | Kohli, P Pawan Kumar, M Torr, PHS P3 & beyond: move making algorithms for solving higher order functions |
| title | P3 & beyond: move making algorithms for solving higher order functions |
| title_full | P3 & beyond: move making algorithms for solving higher order functions |
| title_fullStr | P3 & beyond: move making algorithms for solving higher order functions |
| title_full_unstemmed | P3 & beyond: move making algorithms for solving higher order functions |
| title_short | P3 & beyond: move making algorithms for solving higher order functions |
| title_sort | p3 beyond move making algorithms for solving higher order functions |
| work_keys_str_mv | AT kohlip p3beyondmovemakingalgorithmsforsolvinghigherorderfunctions AT pawankumarm p3beyondmovemakingalgorithmsforsolvinghigherorderfunctions AT torrphs p3beyondmovemakingalgorithmsforsolvinghigherorderfunctions |