"Sliced" Subwindow Search: a Sublinear-complexity Solution to the Maximum Rectangle Problem
This work addresses a fundamental computational bottleneck in domains like image processing, offering a practical solution for real-time applications where slight accuracy trade-offs are acceptable.
The paper tackles the maximum rectangle problem in 2D matrices by introducing a sublinear-complexity method that interpolates between equidistant sections, achieving an 11x speed and memory improvement with 99% accuracy compared to state-of-the-art solutions.
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.