An online self-balancing binary search tree for hierarchical shape matching

In this paper we propose a self-balanced binary search tree data structure for shape matching. This was originally developed as a fast method of silhouette matching in videos recorded from IR cameras by firemen during rescue operations. We introduce a similarity measure with which we can make decisions on how to traverse the tree and backtrack to find more possible matches. Then we describe every basic operation a binary search tree can perform adapted to a tree of shapes. Note that as a binary search tree, all operations can be performed in O(log n) time and are very fast and efficient. Finally we present experimental data evaluating the performance of our proposed data structure.