Matching spatial relations using DB-tree for image retrieval

Spatial relations between objects are widely used in content-based image retrieval. This paper presents an algorithm for matching spatial relations using dynamic bintree (DB-tree). A DB-tree is balanced and has no coordinates. Its leaf nodes contain the images objects, and the internal nodes and the tree structure indicate the spatial relations among image objects. The time complexity of our matching algorithm is O(n lg m+n), where n and m are the number of objects in a query image and a database image. We have compared the DB-tree data structure and the matching algorithm with other schemes, such as 2D-strings. For applications like “Campus Event” image retrieval, the theoretical analysis and experimental results show that the DB-tree approach out-performs 2D-strings in several aspects