Hierarchical Data Structures data structures based on quadtrees

Abstract

In the present thesis, a size-based hierarchical ordering of the codes of the linear quadtree, called the Linear Hierarchical Quadtree (LHQT), is shown to reduce the time spent while exploring the adjacencies, without any extra space requirements. The LHQT permits two approaches for image processing operations:

Top-down approach: Analyzing the codes corresponding to the largest area first and pixels last. Bottom-up approach: Analyzing the codes corresponding to pixels first and those corresponding to the largest area last.

Taking Connected Component Labelling as a typical example, it is shown that the bottom-up approach is superior to the top-down approach. It is known that, in the case of linear quadtrees, exploring adjacencies entails searches over the whole quadtree. One of the contributions of the thesis is the introduction of a Threaded Linear Hierarchical Quadtree (TLHQT) to eliminate the need for such searches completely. The basic idea is to include, in every node of the LHQT, the addresses of its neighbors at the same or higher levels of hierarchy. Thus, at the expense of a marginal increase in storage over the linear quadtree, fast and simple algorithms can be designed to compute geometric properties such as:

Perimeter Distance transform Euler number Connected component labelling

Most of these algorithms are shown to execute in time proportional to B, where B is the number of black nodes. Another contribution of the thesis is the development of space-efficient algorithms to build the linear quadtree from a raster scan of the binary image. It is shown that the time complexity of the LHQT construction is the same as that of the linear quadtree construction. Finally, it is shown that, with a marginal increase in space and time, the TLHQT can also be constructed from the raster. The thesis concludes by indicating the directions in which the results can be extended to three dimensions, and by outlining the process of evolving parallel algorithms to compute geometric properties from the TLHQT.