A new pointerless quadtree representation method is proposed for applications in geographic information systems, image processing and computer graphics. The proposed method is advantageous over the Gargantini's linear quadtree in space saving and other respects. The color of gray nodes in new tree structure is redefined as the dominant color among their four sons, and each node is encoded complementarily.
The new scheme, termed complementary quadtree, not only reduces the storage space more than 30 percent of the space required by linear quadtree, but also guarantees gentle approximation and is efficient in computing geometric properties and set operations. The space efficiency of the proposed representation method is investigated and compared with that of linear quadtree. The algorithms for computing geometric properties and set operations using the new data structure are developed. For applications in the area of graphic image compression and transmission, a new coding method based on the complementary quadtree structure is also proposed.
Empirical tests show that the new coding method is more advantageous in compression ratio and more suited for progressive transmission than the old preorder traversal methods. The new structures are expected to offer many advantages in applications involving large and/or multivalued quadtree, and can also be extended to the octrees.
지도정보 처리시스템 및 컴퓨터 그래픽스등의 분야에서 영상데이타의 계층적표현 및 기억공간의 압축기술은 중요한 과제중의 하나로 최근 쿼드트리에 의한 영상데이타의 표현 방법에 많은 연구가 진행되고 있다. 최근에 자주 이용 되고있는 linear quadtree는 기존의 quadtree에서 포인터를 제거하고 black node 만을 저장함으로서 기억 공간을 60% 이상 절감하였다. 본 논문은 linear quadtree가 black node만을 저장함으로서 발생하는 계층구조의 손실을 보완하고 동시에 기억공간을 더욱 줄일 수 있는 새로운 방법인 상보 quadtree를 제안하였다.
제안된 데이타 구조에서 각 레벨의 gray node는 하부 quadrant들의 dominant 값을 가지게 되고, 각 계층의 quadrant들 중 이러한 dominant값과 다른 값을 갖는 quadrant들 만을 저장하였다. 제안된 상보 quadtree는 기존의 linear quadtree에 비하여 약 30% 정도의 기억공간이 절약 되었으며 또한 근사화, 기하학적인 특성의 계산, 집합연산등에서도 우월한 특성을 가지게 됨을 실험을 통해 확인하였다.
또한 이러한 상보 quadtree의 개념을 그래픽 영상의 progressive 전송분야에 적용하기 위하여 새로운 coding 방법을 제안하였다. 제안된 coding 방법은 기존의 방법인 D-F 표현법 및 tree code등에 비하여 압축율이 개선되었으며 또한 더욱 양질의 그래픽 영상의 progressive 전송이 가능하였다.