INFORMATION CHANGE THE WORLD

International Journal of Information Technology and Computer Science(IJITCS)

ISSN: 2074-9007 (Print), ISSN: 2074-9015 (Online)

Published By: MECS Press

IJITCS Vol.7, No.12, Nov. 2015

An Iterated Function System based Method to Generate Hilbert-type Space-filling Curves

Full Text (PDF, 693KB), PP.12-22


Views:68   Downloads:1

Author(s)

Ruisong Ye, Li Liu

Index Terms

Hilbert-type space-filling curve;iterated function system;fractal

Abstract

Iterated function system has been found to be an important method to generate fractal sets. Hilbert space-filling curve is one kind of fractal sets which has been applied widely in digital image processing, such as image encoding, image clustering, image encryption, image storing/retrieving, and pattern recognition. In this paper, we will explore the generation of Hilbert-type space-filling curves via iterated function system based approach systematically. Cooperating a recursive calling of the common Hilbert's original space-filling curve at resolution n-1 and an IFS consisting of four affine transformations, one can generate the vertices for Hilbert-type space-filling curves at any resolution n. The merit is that the recursive algorithm is easy to implement and can be generalized to produce any other Hilbert-type space-filling curves and their variation versions.

Cite This Paper

Ruisong Ye, Li Liu,"An Iterated Function System based Method to Generate Hilbert-type Space-filling Curves", International Journal of Information Technology and Computer Science(IJITCS), vol.7, no.12, pp.12-22, 2015. DOI: 10.5815/ijitcs.2015.12.02

Reference

[1]G. Peano. Sur une courbe qui remplit toute une aire plane. Mathematische Annalen, 36, pp. 157-160, 1890.

[2]H. Sagan, Space-Filling Curve, Springe- Verlag, 1994. 

[3]D. Hilbert. Ueber die stetige abbildung einer linie auf Flaechenstueck. Mathematische Annalen, 38, pp. 459-460, 1891.

[4]L. Tian, S. Kamata, K. Tsuneyoshi and H. J. Tang,  A fast and accurate algorithm for matching images using Hilbert scanning distance with threshold elimination function, IEICE Trans. E89-D, No. 1, pp. 290-297, 2006. 

[5]V. Suresh and C.E. Veni Madhavan, Image Encryption with Space-filling Curves, Defence Science Journal, 62(1), pp. 46-50, 2012.

[6]Zhexuan Song, Nick Roussopoulos, Using Hilbert curve in image storing and retrieving, Information Systems, 27, pp. 523-536, 2002.

[7]J. E. Hutchinson, Fractals and self similarity, Indiana University Journal of Mathematics, 30, pp. 713—747, 1981.

[8]S. Demko,  L. Hodges, B. Naylor, Construction of Fractal Objects with Iterated Function Systems, SIGGRAPH, Volume 3, pp. 271—276, 1985.

[9]M. F. Barnsley, Fractals Everywhere, Academic Press. 1993.

[10]A. E. Jacquin, Image coding based on a fractal theory of iterated contractive image transformations, IEEE Trans. Image Processing, 1, pp. 18—30, 1992..

[11]Y. Fisher, Fractal Iage Compression-Theory and Application, Springer-Verlag, New York, 1994.

[12]R. Butz, Convergence with Hilbert’s Space Filling Curve, Journal of Computer and System Science, 3(2), pp. 128-146, 1969.

[13]J. Quinqueton and M. Berthod, A locally adaptive Peano scanning algorithm, IEEE Trans. Pattern Anal. Mach. Intell., PAMI-3, 4, pp. 403-412, 1981.

[14]T. Agui, T. Nagae and M. Nakajima, Generalized Peano Scans for Arbitrary-sized Arrays, IEICE Trans. Info. and Syst., E74, 5,  pp.1337-1342, 1991.

[15]S. Kamata, R. O. Eason and Y. Bandou,  A New Algorithm for N-Dimensional Hilbert Scanning, IEEE Trans. Image Processing, 8(7), pp. 964-973, 1999.

[16]J. Zhang, S. Kamata, Y. Ueshige, A Pseudo-Hilbert Scan for Arbitrarily-sized Arrays, IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E90-A, No. 3, pp. 682-690, 2007.

[17]Shen-yi Lin, Chih-shen Chen, Li Liu, and Chua-Huang Huang, Tensor Product Formulation for Hilbert Space-Filling Curves, ICCP, pp.99, 2003 International Conference on Parallel Processing (ICPP'03),  2003. 

[18]Xian Liu, Four alternative patterns of the Hilbert curve, Applied Mathematics and Computation, 147, pp. 741-752, 2004.

[19]E. Moore, On certain crinkly curves, Trans. Am. Math. Soc., 1, pp. 72-90, 1900.