Efficient subwindow search with submodular score functions

An, Senjian, Peursum, Patrick, Liu, Wanquan and Venkatesh, Svetha 2011, Efficient subwindow search with submodular score functions, in CVPR 2011 : Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE, Washington, D. C., pp. 1409-1416.

Attached Files
Name Description MIMEType Size Downloads

Title Efficient subwindow search with submodular score functions
Author(s) An, Senjian
Peursum, Patrick
Liu, Wanquan
Venkatesh, SvethaORCID iD for Venkatesh, Svetha orcid.org/0000-0001-8675-6631
Conference name Computer Vision and Pattern Recognition. Conference (2011 : Colorado Springs, Colo.)
Conference location Colorado Springs, Colo.
Conference dates 20-25 Jun. 2011
Title of proceedings CVPR 2011 : Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
Editor(s) [Unknown]
Publication date 2011
Conference series Computer Vision and Pattern Recognition. Conference
Start page 1409
End page 1416
Total pages 8
Publisher IEEE
Place of publication Washington, D. C.
Keyword(s) complexity theory
feature extraction
linear matrix inequalities
object detection
optimization methods
search problems
Summary 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 [2], AESS [2], ARCS [3]) have been proposed to improve the performance of ESS. For nn 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.
ISBN 9781457703942
ISSN 1063-6919
Language eng
Field of Research 089999 Information and Computing Sciences not elsewhere classified
Socio Economic Objective 970108 Expanding Knowledge in the Information and Computing Sciences
HERDC Research category E1.1 Full written paper - refereed
Copyright notice ©2011, IEEE
Persistent URL http://hdl.handle.net/10536/DRO/DU:30044526

Document type: Conference Paper
Collections: School of Information Technology
2018 ERA Submission
Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 3 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 409 Abstract Views, 12 File Downloads  -  Detailed Statistics
Created: Fri, 20 Apr 2012, 11:29:41 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.