Dynamic graph cuts for efficient inference in Markov random fields
In this paper, we present a fast new fully dynamic algorithm for the st-mincut/max-flow problem. We show how this algorithm can be used to efficiently compute MAP solutions for certain dynamically changing MRF models in computer vision such as image segmentation. Specifically, given the solution of...
| Main Authors: | , |
|---|---|
| Formato: | Journal article |
| Idioma: | English |
| Publicado: |
IEEE
2007
|
| _version_ | 1826313509785305088 |
|---|---|
| author | Kohli, P Torr, PHS |
| author_facet | Kohli, P Torr, PHS |
| author_sort | Kohli, P |
| collection | OXFORD |
| description | In this paper, we present a fast new fully dynamic algorithm for the st-mincut/max-flow problem. We show how this algorithm can be used to efficiently compute MAP solutions for certain dynamically changing MRF models in computer vision such as image segmentation. Specifically, given the solution of the max-flow problem on a graph, the dynamic algorithm efficiently computes the maximum flow in a modified version of the graph. The time taken by it is roughly proportional to the total amount of change in the edge weights of the graph. Our experiments show that, when the number of changes in the graph is small, the dynamic algorithm is significantly faster than the best known static graph cut algorithm. We test the performance of our algorithm on one particular problem: the object-background segmentation problem for video. It should be noted that the application of our algorithm is not limited to the above problem, the algorithm is generic and can be used to yield similar improvements in many other cases that involve dynamic change. |
| first_indexed | 2024-09-25T04:14:45Z |
| format | Journal article |
| id | oxford-uuid:fb2100c8-955c-48c5-b35c-d7200290a05d |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:14:45Z |
| publishDate | 2007 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:fb2100c8-955c-48c5-b35c-d7200290a05d2024-07-11T13:35:42ZDynamic graph cuts for efficient inference in Markov random fieldsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:fb2100c8-955c-48c5-b35c-d7200290a05dEnglishSymplectic ElementsIEEE2007Kohli, PTorr, PHSIn this paper, we present a fast new fully dynamic algorithm for the st-mincut/max-flow problem. We show how this algorithm can be used to efficiently compute MAP solutions for certain dynamically changing MRF models in computer vision such as image segmentation. Specifically, given the solution of the max-flow problem on a graph, the dynamic algorithm efficiently computes the maximum flow in a modified version of the graph. The time taken by it is roughly proportional to the total amount of change in the edge weights of the graph. Our experiments show that, when the number of changes in the graph is small, the dynamic algorithm is significantly faster than the best known static graph cut algorithm. We test the performance of our algorithm on one particular problem: the object-background segmentation problem for video. It should be noted that the application of our algorithm is not limited to the above problem, the algorithm is generic and can be used to yield similar improvements in many other cases that involve dynamic change. |
| spellingShingle | Kohli, P Torr, PHS Dynamic graph cuts for efficient inference in Markov random fields |
| title | Dynamic graph cuts for efficient inference in Markov random fields |
| title_full | Dynamic graph cuts for efficient inference in Markov random fields |
| title_fullStr | Dynamic graph cuts for efficient inference in Markov random fields |
| title_full_unstemmed | Dynamic graph cuts for efficient inference in Markov random fields |
| title_short | Dynamic graph cuts for efficient inference in Markov random fields |
| title_sort | dynamic graph cuts for efficient inference in markov random fields |
| work_keys_str_mv | AT kohlip dynamicgraphcutsforefficientinferenceinmarkovrandomfields AT torrphs dynamicgraphcutsforefficientinferenceinmarkovrandomfields |