Effective algorithms for subwindow search in object detection and localization
Recently, 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) form matrices. Our experimental experien...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
IEEE Computer society
2009
|
| Online Access: | http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5206822&tag=1 http://hdl.handle.net/20.500.11937/15717 |
| _version_ | 1848748970070769664 |
|---|---|
| author | An, Senjian Peursum, Patrick Liu, Wan-quan Venkatesh, Svetha |
| author2 | Huttenlocher |
| author_facet | Huttenlocher An, Senjian Peursum, Patrick Liu, Wan-quan Venkatesh, Svetha |
| author_sort | An, Senjian |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | Recently, 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) form 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 branch-and-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 well suited for real time object detection. |
| first_indexed | 2025-11-14T07:13:30Z |
| format | Conference Paper |
| id | curtin-20.500.11937-15717 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:13:30Z |
| publishDate | 2009 |
| publisher | IEEE Computer society |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-157172022-12-09T05:23:42Z Effective algorithms for subwindow search in object detection and localization An, Senjian Peursum, Patrick Liu, Wan-quan Venkatesh, Svetha Huttenlocher Medioni Rehg Recently, 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) form 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 branch-and-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 well suited for real time object detection. 2009 Conference Paper http://hdl.handle.net/20.500.11937/15717 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5206822&tag=1 IEEE Computer society fulltext |
| spellingShingle | An, Senjian Peursum, Patrick Liu, Wan-quan Venkatesh, Svetha Effective algorithms for subwindow search in object detection and localization |
| title | Effective algorithms for subwindow search in object detection and localization |
| title_full | Effective algorithms for subwindow search in object detection and localization |
| title_fullStr | Effective algorithms for subwindow search in object detection and localization |
| title_full_unstemmed | Effective algorithms for subwindow search in object detection and localization |
| title_short | Effective algorithms for subwindow search in object detection and localization |
| title_sort | effective algorithms for subwindow search in object detection and localization |
| url | http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5206822&tag=1 http://hdl.handle.net/20.500.11937/15717 |