International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 7, No. 12, 8 Nov. 2015
Cover page and Table of Contents: PDF (size: 694KB)
An Iterated Function System based Method to Generate Hilbert-type Space-filling Curves
Full Text (PDF, 694KB), PP.12-22
Views: 0 Downloads: 0
Author(s)
Ruisong Ye
1,*
Li Liu
1
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.