'Sliced' Subwindow Search: a Sublinear-complexity Solution to the Maximum Rectangle Problem

Autor:	Reuter, Max, Bercea, Gheorghe-Teodor, Fong, Liana
Rok vydání:	2019
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Computational Complexity Computer Science - Computer Vision and Pattern Recognition
Druh dokumentu:	Working Paper
Popis:	Considering a 2D matrix of positive and negative numbers, how might one draw a rectangle within it whose contents sum higher than all other rectangles'? This fundamental problem, commonly known the maximum rectangle problem or subwindow search, spans many computational domains. Yet, the problem has not been solved without demanding computational resources at least linearly proportional to the size of the matrix. In this work, we present a new approach to the problem which achieves sublinear time and memory complexities by interpolating between a small amount of equidistant sections of the matrix. Applied to natural images, our solution outperforms the state-of-the-art by achieving an 11x increase in speed and memory efficiency at 99% comparative accuracy. In general, our solution outperforms existing solutions when matrices are sufficiently large and a marginal decrease in accuracy is acceptable, such as in many problems involving natural images. As such, it is well-suited for real-time application and in a variety of computationally hard instances of the maximum rectangle problem. Comment: 8 pages, 7 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1908.00140 Zobrazit plný text záznamu View this record from Arxiv