An efficient implementation of max tree with linked list and hash table

The max tree is a multi-scale image representation based in mathematical morphology which has been applied to image filtering, segmentation, tracking and information retrieval. This paper considers the problem of efficiently building max tree structures from images and retrieving information from them. Our aim is to find an economical data structure that provides fast direct access to the max tree nodes while keeping the memory usage for the tree to a minimum. For this we combine a linked list data structure which allows for dynamic allocation of computer memory and flexible management of tree nodes together with a hash table to give direct access to each tree node as the underlying data structure. Experimental results confirm that using this approach max tree image descriptions can be built in linear time O(n).