venkatesh-efficientalgorithms-2009.pdf (439.55 kB)
Efficient algorithms for subwindow search in object detection and localization
conference contribution
posted on 2009-01-01, 00:00 authored by S An, P Peursum, W Liu, Svetha VenkateshSvetha VenkateshRecently, a simple yet powerful branch-and-bound method called Efficient Subwindow Search (ESS) was developed to speed up sliding window search in object detection. A major drawback of ESS is that its computational complexity varies widely from O(n2) to O(n4) for n × n matrices. Our experimental experience shows that the ESS's performance is highly related to the optimal confidence levels which indicate the probability of the object's presence. In particular, when the object is not in the image, the optimal subwindow scores low and ESS may take a large amount of iterations to converge to the optimal solution and so perform very slow. Addressing this problem, we present two significantly faster methods based on the linear-time Kadane's Algorithm for 1D maximum subarray search. The first algorithm is a novel, computationally superior branchand- bound method where the worst case complexity is reduced to O(n3). Experiments on the PASCAL VOC 2006 data set demonstrate that this method is significantly and consistently faster (approximately 30 times faster on average) than the original ESS. Our second algorithm is an approximate algorithm based on alternating search, whose computational complexity is typically O(n2). Experiments shows that (on average) it is 30 times faster again than our first algorithm, or 900 times faster than ESS. It is thus wellsuited for real time object detection.
History
Event
IEEE Computer Society Conference on Computer Vision and Pattern Recognition (2009 : Miami, Fla.)Pagination
264 - 271Publisher
IEEELocation
Miami, Fla.Place of publication
Washington, D. C.Start date
2009-06-20End date
2009-06-25ISSN
1063-6919ISBN-13
9781424439911ISBN-10
1424439914Language
engNotes
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.Publication classification
E1.1 Full written paper - refereedCopyright notice
2009, IEEETitle of proceedings
CVPR 2009 : Proceeding of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition WorkshopsUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC