We propose Twisted Window Search to generalize the traditional rectangular window search in object localization. We give an O(n) algorithm to compute the globally optimal twisted window in an image of n pixels. We also use regularization to control the shape of a twisted window and show that the optimal twisted window with regularization can be computed in O(n^1.5) time. Experiments highlight the advantages of our method in terms of precision and speed.
A twisted window is any shape that intersects with an arbitrary horizontal line in at most two points on the boundary. Here are the MATLAB/C++ [code] and the [technical report].