An Iterated Function System based Method to Generate Hilbert-type Space-filling Curves
Автор: Ruisong Ye, Li Liu
Журнал: International Journal of Information Technology and Computer Science(IJITCS) @ijitcs
Статья в выпуске: 12 Vol. 7, 2015 года.
Бесплатный доступ
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.
Hilbert-type space-filling curve, iterated function system, fractal
Короткий адрес: https://sciup.org/15012407
IDR: 15012407
Список литературы An Iterated Function System based Method to Generate Hilbert-type Space-filling Curves
- G. Peano. Sur une courbe qui remplit toute une aire plane. Mathematische Annalen, 36, pp. 157-160, 1890.
- H. Sagan, Space-Filling Curve, Springe- Verlag, 1994.
- D. Hilbert. Ueber die stetige abbildung einer linie auf Flaechenstueck. Mathematische Annalen, 38, pp. 459-460, 1891.
- 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.
- V. Suresh and C.E. Veni Madhavan, Image Encryption with Space-filling Curves, Defence Science Journal, 62(1), pp. 46-50, 2012.
- Zhexuan Song, Nick Roussopoulos, Using Hilbert curve in image storing and retrieving, Information Systems, 27, pp. 523-536, 2002.
- J. E. Hutchinson, Fractals and self similarity, Indiana University Journal of Mathematics, 30, pp. 713—747, 1981.
- S. Demko, L. Hodges, B. Naylor, Construction of Fractal Objects with Iterated Function Systems, SIGGRAPH, Volume 3, pp. 271—276, 1985.
- M. F. Barnsley, Fractals Everywhere, Academic Press. 1993.
- A. E. Jacquin, Image coding based on a fractal theory of iterated contractive image transformations, IEEE Trans. Image Processing, 1, pp. 18—30, 1992..
- Y. Fisher, Fractal Iage Compression-Theory and Application, Springer-Verlag, New York, 1994.
- R. Butz, Convergence with Hilbert’s Space Filling Curve, Journal of Computer and System Science, 3(2), pp. 128-146, 1969.
- J. Quinqueton and M. Berthod, A locally adaptive Peano scanning algorithm, IEEE Trans. Pattern Anal. Mach. Intell., PAMI-3, 4, pp. 403-412, 1981.
- 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.
- 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.
- 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.
- 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.
- Xian Liu, Four alternative patterns of the Hilbert curve, Applied Mathematics and Computation, 147, pp. 741-752, 2004.
- E. Moore, On certain crinkly curves, Trans. Am. Math. Soc., 1, pp. 72-90, 1900.
