Sub-linear Indexing for Large Scale Object Recognition

A method capable of recognising one of N objects in log(N) time, which preserves all the strengths of local affine region methods – robustness to background clutter, occlusion, and large changes of viewpoints.

Abstract

Realistic approaches to large scale object recognition, i.e. for detection and localisation of hundreds or more objects, must support sub-linear time indexing.In the paper, we propose a method capable of recognising one of N objects in log(N) time.The "visual memory" is organised as a binary decision tree that is built to minimise average time to decision.Leaves of the tree represent a few local image areas, and each non-terminal node is associated with a 'weak classifier'.In the recognition phase, a single invariant measurement decides in which subtree a corresponding image area is sought.The method preserves all the strengths of local affine region methodsrobustness to background clutter, occlusion, and large changes of viewpoints.Experimentally we show that it supports near real-time recognition of hundreds of objects with state-of-the-art recognition rates.After the test image is processed (in a second on a current PCs), the recognition via indexing into the visual memory requires milliseconds.