Привет, Beegor, сейчас расскажу ...
B>есть один вопрос по нахождению IFS для фрактала. Есть ч\б изображение 2Д (афин. плоскость) фрактала, нужно его проанализировав получить матрицу IFS и по этой матрице сформировать ему подобный фрактал. Может посоветуете куда копать? В инете ничего не нашел по теме (в особенности как распознать IFS из картинки с фракталом).
Обратная задача для фрактального множества (т.е. найти IFS по картинке) — штука непростая, проф. Hutchinson J.E. первый понял как IFS можно аппроксимировать набором линейных (аффинных) отображений. Другой профессор, Barnsley M.F, первым догадался, что эту технику можно приспособить для сжатия изображений.
Суть: картинку разбивают на участки обычно прямоугольной формы (наносят сетку). Ячейка в этой сетке называется ранговой областью, R[i,j]. Для каждой R[i,j] внутри изображения ищут доменную область D[i,j] такую, что расстояние (в выбранной метрике) м-у множествами
Distance(A * D[i,j], R[i,j] ) < e,
т.е. меньше наперёд заданной величины эпсилон.
A — это аффинное преобразование вида:
|a b| |x| |e|
| | * | | + | |
|c d| |y| |f|
Доменные области, в отличие от ранговых могут пересекаться. Но условие сходимости при восстановлении сжатого изображения требует, чтобы D[i,j] по площади был больше чем соотв R[i,j].
Как найти нужный набор коэффициентов для каждого i,j: a,b,c,d,f,e — вопрос нетривиальный. Можно использовать общие методы оптимизации для поиска минимума расстояния, скажем метод Ньютона или Пауэлла. Но делать это долго даже на современных компьютерах. Правда задачу эту можно решать параллельно, т.к. обрабатывать каждый R[i,j] ни что не мешает на отдельном компьютере (!) Однако на практике делают ухищрения другого рода.
1. Ранговая область, играются с её формой и размером. Часто сетку наносят с переменным шагом, она там плотнее (ячейки меньше), где есть контрастные переходы чёрное<->белое.
2. Домены, можно заранее искать не параллелограмм (общий случай), а частность. Скажем постулировать что к-ты b, c равны нулю. Можно ещё радикальнее считать, что достаточно чтобы D[i,j] по форме повторял R[i,j] и был больше в 2 раза. Понятно, что к-во вариантов и точность таким образом у нас уменшатся. Но в скорости подбора домена будет выигрыш.
3. Кэширование промежуточных результатов. Пусть для некоего D[i,j] мы посчитали пару-трёшку неких сигнатур. В следующий раз можно это не делать, а сразу допустить, что домен подходит для R[i,j].
Как восстанавливать изображение ты полагаю знаешь: матрицу изображения набить хаосом из ч/б точек, наложить ранговую сетку и несколько раз итеративно прокрутить через аффинный IFS. Из хаоса образуется порядок
.
Ссылки, они есть но не интернетные, а печаные. Первооснова это статья:
Barnsley M.F., Sloan A.D., A better way to compress images, Byte, vol.13, №1, pp. 215-224, 1988.
У нас она печаталась в журнале Мир ПК за 1992 в 4-м номере, если я не путаю. Вот ещё материалы:
Barnsley M.F., Fractals Everywhere, Academic Press, New York, 1988.
Barnsley M.F., Harringt A.N., The calculus of fractal interpolation functions, Journal of approximation theory, vol.57, №1, pp.14-34, 1989.
Barnsley M.F., Fractal functions and interpolation, Constructive approximation, №2, pp. 303-329, 1986.
Barnsley M.F., Hurd L., Fractal image compression, AK Peters, Ltd., Wellesley, Ma., 1992.
Behnam B.-E., Enhancing the speed of fractal image compression, Optical Engineering, vol. 34, №6, pp.1705-1710.
Carlos A., Iterated fuzzy set systems: a new approach to the inverse problem of fractal sets, Journal of mathematical analysis and applications, vol. 171, №1, pp. 79-100, 1992.
Clarke R.J., Fractals and Image representation, Electronics & Communication Engineering Journal, vol. 5, № 4, pp. 233-239.
Hutchinson J.E., Fractals and self-similarity, Indiana University Journal of Mathematics, vol. 30, pp. 713-747, 1981.
Jaquin A., Fractal image coding based on a theory of iterated contractive image transformations, Proc. SPIE’s Visual Communications and Image processing, pp. 227-239. 1990.
Monro D.M., Nicholls J.A., Real time fractal video for personal communications, Fractals, vol. 2, № 3, pp. 391-394, 1994.
Monro D.M., Woolley S.J., Rate/distortion performance of fractal transforms for image compression, Fractals, vol. 2, № 3, pp. 395-398, 1994.
Monro D.M., Dudbridge F., Fractal block coding of images, Electronic letters, vol. 28, №11, pp.1053-1055, 1992.
Можешь ещё и эту статью почитать, хотя прямого отношения к сжатию изображений она не имеет
.
Melnikov A.V., The fractal sets approximation by Julia set attractors of polynomial Iterated Function Systems (IFS), “Fractals”, vol.7, №1, 1999.
Успехов!
