Efficient algorithms for coding Hilbert curve of arbitrary-sized image and application to window query

摘要

Previously, several efficient Hilbert scan-based operations were presented, but they all suffer from the constraint that the image size must be 2' x 2'. Considering an image with arbitrary size I-1 x I-2, this paper first presents an efficient snake scan-based algorithm for coding the Hilbert curve of the given image. The proposed coding algorithm takes 0(k + log U) time to code the Hilbert order of one pixel where k denotes the number of the quadrants and U = min(I-1, I-2). Next, a memory-saving Hilbert curve representation called HCGL is presented for representing the encoded Hilbert curve and it can be constructed in O(L-2 log L) time where L = max(I-1, I-2). Based on the HCGL representation of arbitrary-sized image, an application to window query is presented and the proposed window query algorithm takes O(M log L + P) time where M denotes the number of generated maximal quadtree blocks and P denotes the number of output codes. Under the same PSNR (Peak Signal to Noise Ratio), experimental results demonstrate that our proposed HCGL representation outperforms some existing related algorithms in terms of execution-time and BPP (Bit Per Pixel). In addition, our proposed window query algorithm has been justified in the GIS (Geographical Information System) application. (C) 2006 Elsevier Inc. All rights reserved.