Exploiting monge structures in optimum subwindow search
Optimum subwindow search for object detection aims to find a subwindow so that the contained subimage is most similar to the query object. This problem can be formulated as a four dimensional (4D) maximum entry search problem wherein each entry corresponds to the quality score of the subimage contai...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
IEEE
2010
|
| Online Access: | http://hdl.handle.net/20.500.11937/21373 |
| _version_ | 1848750572075745280 |
|---|---|
| author | An, Senjian Peursum, Patrick Liu, Wan-quan Venkatesh, Svetha Chen, Xiaoming |
| author2 | L. Davis |
| author_facet | L. Davis An, Senjian Peursum, Patrick Liu, Wan-quan Venkatesh, Svetha Chen, Xiaoming |
| author_sort | An, Senjian |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | Optimum subwindow search for object detection aims to find a subwindow so that the contained subimage is most similar to the query object. This problem can be formulated as a four dimensional (4D) maximum entry search problem wherein each entry corresponds to the quality score of the subimage contained in a subwindow. For n x n images, a naive exhaustive search requires O(n4) sequential computations of the quality scores for all subwindows. To reduce the time complexity, we prove that, for some typical similarity functions like Euclidian metric, X2 metric on image histograms, the associated 4D array carries some Monge structures and we utilise these properties to speed up the optimum subwindow search and the time complexity is reduced to O(n3). Furthermore, we propose a locally optimal alternating column and row search method with typical quadratic time complexity O(n2). Experiments on PASCAL VOC 2006 demonstrate that the alternating method is significantly faster than the well known efficient subwindow search (ESS) method whilst the performance loss due to local maxima problem is negligible. |
| first_indexed | 2025-11-14T07:38:57Z |
| format | Conference Paper |
| id | curtin-20.500.11937-21373 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:38:57Z |
| publishDate | 2010 |
| publisher | IEEE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-213732023-01-13T07:56:30Z Exploiting monge structures in optimum subwindow search An, Senjian Peursum, Patrick Liu, Wan-quan Venkatesh, Svetha Chen, Xiaoming L. Davis J. Malik Optimum subwindow search for object detection aims to find a subwindow so that the contained subimage is most similar to the query object. This problem can be formulated as a four dimensional (4D) maximum entry search problem wherein each entry corresponds to the quality score of the subimage contained in a subwindow. For n x n images, a naive exhaustive search requires O(n4) sequential computations of the quality scores for all subwindows. To reduce the time complexity, we prove that, for some typical similarity functions like Euclidian metric, X2 metric on image histograms, the associated 4D array carries some Monge structures and we utilise these properties to speed up the optimum subwindow search and the time complexity is reduced to O(n3). Furthermore, we propose a locally optimal alternating column and row search method with typical quadratic time complexity O(n2). Experiments on PASCAL VOC 2006 demonstrate that the alternating method is significantly faster than the well known efficient subwindow search (ESS) method whilst the performance loss due to local maxima problem is negligible. 2010 Conference Paper http://hdl.handle.net/20.500.11937/21373 IEEE fulltext |
| spellingShingle | An, Senjian Peursum, Patrick Liu, Wan-quan Venkatesh, Svetha Chen, Xiaoming Exploiting monge structures in optimum subwindow search |
| title | Exploiting monge structures in optimum subwindow search |
| title_full | Exploiting monge structures in optimum subwindow search |
| title_fullStr | Exploiting monge structures in optimum subwindow search |
| title_full_unstemmed | Exploiting monge structures in optimum subwindow search |
| title_short | Exploiting monge structures in optimum subwindow search |
| title_sort | exploiting monge structures in optimum subwindow search |
| url | http://hdl.handle.net/20.500.11937/21373 |