Twisted window search for efficient shape localization
Many computer vision systems approximate targets' shape with rectangular bounding boxes. This choice trades localization accuracy for efficient computation. We propose twisted window search, a strict generalization over rectangular window search, for the globally optimal localization of a target's shape. Despite its generality, we show that the new algorithm runs in O(n 3), an asymptotic time complexity that is no greater than that of rectangular window search on an image of resolution n × n. We demonstrate improved results of twisted window search for localizing and tracking non-rigid objects with significant orientation, scale and shape change. Twisted window search runs at nearly 10 frames per second in our MATLAB/C implementation on images of resolution 240 × 320 on a quad-core laptop. © 2012 IEEE.
