
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An Implementation of the Hilbert Scanning Algorithm and Its Application to Data Compression
Seiichiro KAMATA Richard O. EASON Eiji KAWAGUCHI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E76D
No.4
pp.420428 Publication Date: 1993/04/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on Image Processing and Understanding) Category: Keyword: Hilbert scanning, data compression, quadtree expression, lookup table,
Full Text: PDF>>
Summary:
The Hilbert curve is one of the simplest curves which pass through all points in a space. Many researchers have worked on this curve from the engineering point of view, such as for an expression of twodimensional patterns, for data compression in an image or in color space, for pseudo color image displays, etc. A computation algorithm of this curve is usually based on a lookup table instead of a recursive algorithm. In such algorithm, a large memory is required for the path lookup table, and the memory size becomes proportional to the image size. In this paper, we present an implementation of a fast sequential algorithm that requires little memory for two and three dimensional Hilbert curves. Our method is based on some rules of quadtree traversal in two dimensional space, and octtree traversal in three dimensional space. The two dimensional Hilbert curve is similar to the scanning of a DF (Depth First) expression, which is a quadtree expression of an image. The important feature is that it scans continuously from one quadrant, which is obtained by quad tree splitting, to the next adjacent one in two dimensional space. From this point, if we consider runlengths of black and white pixels during the scan, the runlengths of the Hilbert scan tend to be longer than those of the raster scan and the DF expression scanning. We discuss the application to data compression using binary images and three dimensional data.


