Building a quadtree and its applications on a reconfigurable mesh

摘要

Quadtree is an efficient method to represent binary images. How to build a quadtree for a binary image is worthy of study. The major contribution of this paper is that we first use the Hilbert mapping technique to represent the binary image. Then, based on the reconfigurability of the reconfigurable mesh, a constant time algorithm for building a quadtree for an n × n binary image using n × n processors is derived. For applications of this algorithm two methods for compressing and decompressing binary images are also proposed.