Content-Addressable Memories for Quadtree-8ased Images

Abstract

Quadtrees are attractive for storing and processing mages with area coherence, but performance has been limited by software overheads. A Content-Addressable Memory (CAM) with ternary storage allows single-cycle searches by pixel coordinate, quadrant or rectangle. To use thiS feature effectively the authors have reviewed a range of quadtree processing functions relevant to computer graphics and Image processing, and some new algorithms have been discovere. The proposed VLSI chip has microcoded logic on each row, as well as its CAM cells. This architecture has been simulated in fine detail with the aid of the Connection Machine as well as by much slower, conventional computers. The combination of quadtrees and CAMs offers significant improvement in performance for display systems and image processing.