Online shape learning using binary search trees

In this paper we propose an online shape learning algorithm based on the self-balancing binary search tree data structure for the storage and retrieval of shape templates. This structure can also be used for classification purposes. We introduce a similarity measure with which we can make decisions on how to traverse the tree and even backtrack through the search path to find more candidate matches. Then we describe every basic operation a binary search tree can perform adapted to such a tree of shapes. Note that as a property of binary search trees, all operations can be performed in O(logn)O(logn) time and are very efficient. Finally, we present experimental data evaluating the performance of the proposed algorithm and demonstrating the suitability of this data structure for the purpose it was designed to serve.