Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-08T18:32:32.406Z Has data issue: false hasContentIssue false
  • English
  • Français

A stochastic algorithm to compute optimal probabilities in the chaos game

Part of: Communication, information Stochastic processes

Published online by Cambridge University Press:  01 July 2016

Laura M. Morato  and
Paola Siri
Laura M. Morato*
Affiliation:
Università di Verona
Paola Siri*
Affiliation:
Università di Verona
*
∗ Postal address: Facoltà di Scienze MM.FF.NN., Ca' Vignal 2, Strada le Grazie, 37134 Verona, Italia.
∗ Postal address: Facoltà di Scienze MM.FF.NN., Ca' Vignal 2, Strada le Grazie, 37134 Verona, Italia.
Get access Rights & Permissions [Opens in a new window]

Abstract

We present a stochastic algorithm which generates optimal probabilities for the chaos game to decompress an image represented by the fixed point of an IFS operator. The algorithm can be seen as a sort of time-inhomogeneous regenerative process. We prove that optimal probabilities exist and, by martingale methods, that the algorithm converges almost surely. The method holds for IFS operators associated with any arbitrary number of possibly overlapping affine contraction maps on the pixels space.

Keywords

image decompressionstochastic algorithmmartingales

MSC classification

Primary: 94A08: Image processing (compression, reconstruction, etc.)
Secondary: 60G42: Martingales with discrete parameter
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 33 , Issue 2 , June 2001 , pp. 423 - 436
Copyright
Copyright © Applied Probability Trust 2001 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Abenda, S. (1990). Inverse problem for one-dimensional fractal measures via iterated function systems and the moment method. Inverse Problems 6, 885–896.CrossRefGoogle Scholar
[2] Barnsley, M. F. (1988). Fractals Everywhere. Academic Press, San Diego.Google Scholar
[3] Barnsley, M. F. and Lyman, P. H. (1992). Fractal Image Compression. A. K. Peters, Wellesley.Google Scholar
[4] Bertolotto, G. (1998). Approccio probabilistico nella decompressione algoritmica dei dati immagine: ottimalità e problema inverso. Tesi di Laurea, Università di Verona.Google Scholar
[5] Elton, J. (1987). An ergodic theorem for iterated maps. Ergodic Theory Dynam. Systems 7, 481–488.CrossRefGoogle Scholar
[6] Forte, B. and Vrscay, E. R. (1994). Solving the inverse problem for function and image approximation using iterated function systems. I. Theoretical basis. 2, 325–334.Google Scholar
[7] Forte, B. and Vrscay, E. R. (1994). Solving the inverse problem for function and image approximation using iterated function systems. II. Algorithm and computations. Fractals 2, 335–346.CrossRefGoogle Scholar
[8] Forte, B. and Vrscay, E. R. (1995). Solving the inverse problem for measures using iterated function systems: a new approach. Adv. Appl. Prob. 27, 800–820.Google Scholar
[9] Iosifescu, M. and Grigorescu, S. (1990). Dependence with Complete Connections and its Applications. Cambridge University Press.Google Scholar
[10] Iosifescu, M. and Theodorescu, R. (1969). Random Processes and Learning. Springer, Berlin.CrossRefGoogle Scholar
[11] Lutton, E. et al. (1995). Mixed IFS: resolution of the inverse problem using genetic programming. Complex Systems 9, 375–398.Google Scholar
[12] Morato, L. M. (1995). Note integrative per il corso di Processi Casuali a.a. 95/96. Corso di Laurea in Scienze dell'Informazione, Università di Verona.Google Scholar
[13] Vrscay, E. R. (1989). Iterated function systems: theory, applications and the inverse problem. In Fractal Geometry and Analysis. Kluwer, Dordrecht, pp. 405–468.Google Scholar
[14] Vrscay, E. R. and Roehring, C. J. (1989). Iterated function systems and the inverse problem of fractal construction using moments. In Computers and Mathematics, eds Kaltofen, E. and Watt, S. M. Springer, Berlin, pp. 250–259.CrossRefGoogle Scholar