Approximation of an image by the attractor evolved through iterations of a set of contractive maps is usually known as fractal image compression. The set of maps is called iterated function system (IFS). Several algorithms, with different motivations, have been suggested towards the solution of this problem. But, so far, the theory of IFS with probabilities, in the context of image compression, has not been explored much. In the present article we have proposed a new technique of fractal image compression using the theory of IFS and probabilities. In our proposed algorithm, we have used a multiscaling division of the given image up to a predetermined level or up to that level at which no further division is required. At each level, the maps and the corresponding probabilities are computed using the gray value information contained in that image level and in the image level higher to that level. A fine tuning of the algorithm is still to be done. But, the most interesting part of the proposed technique is its extreme fastness in image encoding. It can be looked upon as one of the solutions to the problem of huge computational cost for obtaining fractal code of images.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W badaniu wielu zjawisk przyrodniczych istotną rolę odgrywają operatory Markowa, nieujemne operatory liniowe oraz ich półgrupy. W szczególności rozważana jest asymptotyczna stabilność. A. Lasota i J. A. Yorke w 1982 r. udowodnili, że warunkiem wystarczającym i koniecznym asymptotycznej stabilności dla operatora Markowa jest istnienie nietrywialnej funkcji dolnej. W niniejszej pracy pokazujemy zastosowanie metody funkcji dolnej do badania zachowania algorytmów genetycznych. Rozpatrywane w pracy algorytmy genetyczne, używane do rozwiązywania niegładkich problemów optymalizacyjnych, są wynikiem złożenia dwóch operatorów losowych: selekcji i mutacji. Złożenie tych operacji jest macierzą Markowa.
EN
Markovian operators, non-negative linear operators and its subgroups play a significant role for the description of phenomena observed in the nature. Research on asymptotic stability is one of the main issues in this respect. A. Lasota and J. A. Yorke proved in 1982 that the necessary and sufficient condition of the asymptotic stability of a Markovian operator is the existence of a non-trivial lower-bound function. In the present paper it is shown how the method of lower-bound function can be applied to the investigation of genetic algorithms. Genetic algorithms considered used for solving of non-smooth optimization problems are compositions of two random operators: selection and mutation. The compositions are Markovian matrices.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
This is an account of my scientific and personal friendship with Prof. Andrzej (Andy) Aleksander Lasota from 1977 until his death 28 December, 2006. It is a tale that fascinates me because of the intertwined links between many people both East and West of several generations, and it illustrates what I feel is the strength and beauty of the personal side of the scientific endeavor.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We characterize the bounded linear operators T in Hilbert space which satisfy T = βI + (1 - β)S where β ∈ (0,1) and S is a contraction. The characterizations include a quadratic form inequality, and a domination condition of the discrete semigroup (T[sup]n)n=1,2,... by the continuous semigroup (e[sup]-t(I-T)t≥o. Moreover, we give a stronger quadratic form inequality which ensures that sup{n||T[sup]n - T[sup]n+1 ||: n = 1, 2,...} < ∞. The results apply to large classes of Markov operators on countable spaces or on locally compact groups.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W pracy zdefiniowano prosty algorytm genetyczny w terminach skończonego multizbioru potencjalnych rozwiązań (osobników danej populacji), na którym są określone operacje krzyżowania, mutacji i selekcji, każda z pewnym prawdopodobieństwem. Działając złożeniem tych operacji na dowolną populację, tworzymy nową populację. Istnienie funkcji przystosowania (dopasowania), określonej na osobnikach populacji, pozwala powiązać prawdopodobieństwo selekcji osobników do nowej populacji z wartościami, jakie funkcja przystosowania przyjmuje na osobniku. Przejście z jednej generacji do drugiej jest realizowane przez operator działający na wektory probabilistyczne charakteryzujące rozkład prawdopodobieństwa pojawienia się każdej z możliwych populacji. Jest to operator Markowa. W teorii operatorów Markowa oraz operatorów dodatnich znanych jest wiele twierdzeń dotyczących istnienia punktów stałych oraz zbieżności ciągu iteracji operatora. Korzystając z tych wyników, znaleźliśmy warunki wystarczające i konieczne stabilności operatora Markowa związanego z pewną klasą algorytmów genetycznych.
EN
The simple genetic algorithm (SGA) and its convergence analysis are main subjects of the article. The SGA is defined on a finite multi-set of potential problem solutions (individuals) together with crossover, mutation and selection operators, each with prescribed probability. The selection operation acts on the basis of the fitness function defined on potential solutions (individuals), and is fundamental for the problem considered. Generation of a new population from the given one is realized by the action of the composition of those operators. The composition is written in the form of a transition operator acting on probability vectors which describe probability distributions of each population. The transition operator is a Markov one. Thanks to the well-developed theory of Markov operators new conditions for stability of the transition operator are formulated. The results obtained are related to the class of genetic operators.
6
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The paper contains an example of three commuting transition probabilities T, S, U inducing continuous transition system and such that the iterates Tk, Sk, Uk admit no trajectories for any natural k.
8
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Continuous Iterated Function Systems are studied. We generalize results proved by A. Lasota and RM. C. Mackey to the case when the systems are defined on Polish spaces.
9
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW