In previous years of the project, the team developed a storage and compression scheme in which quadtrees are combined with common compression techniques to produce an indexing of the compressed image data.
This quadtree-based indexing does not induce a space overhead because it is actively used to contribute to better compression. In particular, our implementation that combines quadtree-based indexing and Huffman coding achieves better compression than popular algorithms like JPEG. The combination of the quadtree-based indexing with other codings, like arithmetic or fractal, is part of our current research.
The advantage of the scheme is that it improves the performance of queries for image subregions, while achieving good compression as mentioned above. The improvement in subregion retrieval comes from the utilization of the quadtree indexing to locate, load, uncompress and process only the compressed data that are needed to reconstruct the requested image subregion.
A scheme like this is especially useful to environments like ADL: the number and size of the image data (mainly satellite images or airphotos) is large. Processing an image using traditional schemes would require time and memory at least proportional to the size of the image, resources which may not be readily available. Our scheme only needs time and space proportional to the size of the image subregion requested. Furthermore, a user may elect to view a large subregion or a whole image in a lower resolution, which reduces the computation even further. If the user later elects to view a part of the subregion in a higher resolution, the intermediate results can be used to eliminate redundant computation.
Last year the scheme has been extended to work in a client/server environment. Progressive delivery of subregions was supported and data are sent compressed over the network. In a client/server environment there is a choice of executing the various tasks on the server or the client side. For instance, one could perform all the computations on the server side and then send the reconstructed image (or image subregion) to the client. This could be useful when, say, the client side does not have sufficient computational resources. The other extreme is to have the server just locate, load and send the necessary compressed data to the client, who then has to uncompress and process them. This could be useful when the load on the server is high. There are intermediate partitions of the work between the server and the client, and our scheme's implementation on the client/server environment supports a number of them. SWEB++ utilizes this feature and performance results have been derived (see below).
Parts of the code that are executed on the client side have been ported to Java and contributed to the ADL demonstrations. The porting of the remaining code that could be executed on the client side to Java is under development.