Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23]

@

Journal of Information Science and Engineering, Vol. 26 No. 5, pp. 1917-1930 (September 2010)

Linear Quadtree Construction in Real Time*

CHI-YEN HUANG AND YU-WEI CHEN+
Department of Information Management
National Taipei College of Business
Taipei, 100 Taiwan
+Graduate Institute of Information and Logistics Management
National Taipei University of Technology
Taipei, 106 Taiwan

The paper presents a novel method for encoding the linear quadtree of a given image. In this method, the pixels of the image are scanned in row major order. In each encountered pixel, the result codes in the linear quadtree are updated simultaneously in real time. The linear quadtree is thus obtained after all pixels are processed. This method is quite different from those in previous studies, which need huge memory space to store the input pixels for further processing, or need post processing to rearrange the sequence of the final codes to put them back in increasing order. Moreover, since this method adopts simpler and more efficient operations than previous methods, it is found to be faster in experiments.

Keywords: linear quadtree, linear bintree, spatial data structure, image encoding, locational code

Full Text () Retrieve PDF document (201009_23.pdf)

Received May 1, 2008; revised March 26 & June 2 & July 23 & August 3, 2009; accepted August 5, 2009.
Communicated by Suh-Yin Lee.
* The authors would like to thank the National Science Council of R.O.C., Taiwan for financially supporting this research under Contract No. NSC 97-2221-E-027-118.