Efficient subwindow search with submodular score functions
Subwindow search aims to find the optimal subimage which maximizes the score function of an object to be detected. After the development of the branch and bound (B&B) method called Efficient Subwindow Search (ESS), several algorithms (IESS, AESS, ARCS) have been proposed to improve the performan...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
IEEE
2011
|
| Online Access: | http://hdl.handle.net/20.500.11937/10983 |
| _version_ | 1848747683194339328 |
|---|---|
| author | An, Senjian Peursum, Patrick Liu, Wanquan Venkatesh, Svetha |
| author2 | Not known |
| author_facet | Not known An, Senjian Peursum, Patrick Liu, Wanquan Venkatesh, Svetha |
| author_sort | An, Senjian |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | Subwindow search aims to find the optimal subimage which maximizes the score function of an object to be detected. After the development of the branch and bound (B&B) method called Efficient Subwindow Search (ESS), several algorithms (IESS, AESS, ARCS) have been proposed to improve the performance of ESS. For n×n images, IESS's time complexity is bounded by O(n3) which is better than ESS, but only applicable to linear score functions. Other work shows that Monge properties can hold in subwindow search and can be used to speed up the search to O(n3), but only applies to certain types of score functions. In this paper we explore the connection between submodular functions and the Monge property, and prove that sub-modular score functions can be used to achieve O(n3) time complexity for object detection. The time complexity can be further improved to be sub-cubic by applying B&B methods on row interval only, when the score function has a multivariate submodular bound function. Conditions for sub-modularity of common non-linear score functions and multivariate submodularity of their bound functions are also provided, and experiments are provided to compare the proposed approach against ESS and ARCS for object detection with some nonlinear score functions. |
| first_indexed | 2025-11-14T06:53:02Z |
| format | Conference Paper |
| id | curtin-20.500.11937-10983 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T06:53:02Z |
| publishDate | 2011 |
| publisher | IEEE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-109832017-09-13T16:08:58Z Efficient subwindow search with submodular score functions An, Senjian Peursum, Patrick Liu, Wanquan Venkatesh, Svetha Not known Subwindow search aims to find the optimal subimage which maximizes the score function of an object to be detected. After the development of the branch and bound (B&B) method called Efficient Subwindow Search (ESS), several algorithms (IESS, AESS, ARCS) have been proposed to improve the performance of ESS. For n×n images, IESS's time complexity is bounded by O(n3) which is better than ESS, but only applicable to linear score functions. Other work shows that Monge properties can hold in subwindow search and can be used to speed up the search to O(n3), but only applies to certain types of score functions. In this paper we explore the connection between submodular functions and the Monge property, and prove that sub-modular score functions can be used to achieve O(n3) time complexity for object detection. The time complexity can be further improved to be sub-cubic by applying B&B methods on row interval only, when the score function has a multivariate submodular bound function. Conditions for sub-modularity of common non-linear score functions and multivariate submodularity of their bound functions are also provided, and experiments are provided to compare the proposed approach against ESS and ARCS for object detection with some nonlinear score functions. 2011 Conference Paper http://hdl.handle.net/20.500.11937/10983 10.1109/CVPR.2011.5995355 IEEE restricted |
| spellingShingle | An, Senjian Peursum, Patrick Liu, Wanquan Venkatesh, Svetha Efficient subwindow search with submodular score functions |
| title | Efficient subwindow search with submodular score functions |
| title_full | Efficient subwindow search with submodular score functions |
| title_fullStr | Efficient subwindow search with submodular score functions |
| title_full_unstemmed | Efficient subwindow search with submodular score functions |
| title_short | Efficient subwindow search with submodular score functions |
| title_sort | efficient subwindow search with submodular score functions |
| url | http://hdl.handle.net/20.500.11937/10983 |