Математическое и программное обеспечение методов повышения временной эффективности фрактального сжатия изображений тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Винокуров, Станислав Владимирович

• Винокуров, Станислав Владимирович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Винокуров, Станислав Владимирович

ВВЕДЕНИЕ.

ГЛАВА 1. ФРАКТАЛЬНОЕ СЖАТИЕ ИЗОБРАЖЕНИЙ, ЕГО

ОСОБЕННОСТИ И ОБСЛАСТИ ПРИМЕНЕНИЯ.

Введение.

1.1. Математические основы фрактального сжатия изображений.

1.2. Фрактальное сжатие изображений в градациях серого.

1.3. Методы повышения временной эффективности фрактального алгоритма.

1.4. Фрактальное сжатие цветных изображений.

1.5. Особенности и области применения фрактального сжатия.

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечение методов повышения временной эффективности фрактального сжатия изображений»

2.1. Математические основы фрактального сжатия с использованием ближайшего соседнего элемента.57

2.2. Современные методы поиска ближайшего соседнего элемента в многомерном метрическом пространстве.61

Заключение.71

ГЛАВА 3. АДАПТАЦИЯ ПРОСТРАНСТВЕННО-ЧУВСТВИТЕЛЬНОГО ХЕШИРОВАНИЯ ДЛЯ СОЗДАНИЯ ЭФФЕКТИВНЫХ МЕТОДОВ

ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ.72

Введение.72

3.1. Понятие пространственно-чувствительного хеширования.72

3.2. Применение пространственно-чувствительного хеширования для решения задачи фрактального сжатия изображений.73

3.3. Адаптация пространственно-чувствительных хеш-функций к фрактальному сжатию изображений на основе р-устойчивых распределений.75

3.4. Преимущества использования метода пространственно-чувствительного хеширования при фрактальном сжатии изображений.78

Заключение.83

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПРИМЕНЕНИЕ И ЭКСПЛУАТАЦИЯ ЭФФЕКТИВНОГО АЛГОРИТМА ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ.84

Введение.84

4.1. Описание алгоритма фрактального сжатия при помощи пространственно чувствительного хеширования (FracLSH). 84

4.2. Оценка временной эффективности алгоритма FracLSH. 91

4.3. Комплексный критерий качества алгоритмов сжатия и восстановления растровых изображений на основе нормированных оценок. 92

4.4. Сравнение FracLSH с другими современными алгоритмами сжатия изображений. 102

Заключение. 106

ЗАКЛЮЧЕНИЕ. 107

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.110

ПРИЛОЖЕНИЕ. 121

ВВЕДЕНИЕ

Актуальность темы

Актуальность исследований в области повышения временной эффективности алгоритмов фрактального сжатия изображений определяется существующими в настоящее время тенденциями к применению таких алгоритмов для сжатия статических изображений и динамической видеоинформации. Именно фрактальные алгоритмы потенциально способны обеспечить наилучшее соотношение степени сжатия и качества восстановленного изображения, что важно в системах подготовки мультимедиа информации к тиражированию. Однако, существующие реализации таких алгоритмов весьма требовательны к ресурсам вычислительной системы, что несколько сужает область их применения. К алгоритмам и системам сжатия видеоинформации предъявляется ряд достаточно жестких требований по временной эффективности, обусловленных комфортностью работы с программными системами, в которых применяются данные алгоритмы, а также необходимостью использования сжатия. Решение этой задачи не может опираться только на возрастающие мощностью современных компьютеров и связано с разработкой эффективных алгоритмов сжатия.

В связи с этим разработка эффективных алгоритмов фрактального сжатия изображений представляет собой актуальную задачу в области создания эффективного математического и программного обеспечения вычислительных машин, комплексов и компьютерных сетей.

Состояние проблемы

При разработке, исследовании и развитии методов фрактального сжатия изображений охватывается широкий круг проблем связанных с повышением временной эффективности методов фрактального сжатия изображений, их алгоритмического обеспечения, оценки качества алгоритмов сжатия и восстановления растровых изображений, в исследование и развитие которых внесли значительных вклад российские и зарубежные ученые: Н. А. Ваганова, Д. С. Ватолин, Н.Б. Новинский, В.В. Нечепаев, М. Barnsley, Т. Bedford, J. Bentley, A. Bogdan, L. Chen, F. Dekking, Y. Fisher, J. R. Finkel, Friedman, M. Gharavi-Alkhansari, R. Hamzaoui, J. Hutchinson, A. Jacquin, W. Kinser, C. Lee, S. Lepsey, H. Lin, B. Mandelbrot, H. Meadows, G. 0ien, D. Saupe, A. Venetsanopoulos, L. Wall, и др.

Большинство современных публикаций по тематике исследования алгоритмов фрактального сжатия посвящены повышению временной эффективности фрактального кодирования. Несмотря на интенсивные исследования в области классической теории алгоритмов фрактального сжатия растровых изображений некоторые вопросы остаются нерешенными. В первую очередь это касается вопроса поиска эффективных методов построения систем итерируемых функций для заданного входного изображения. Отметим в данном контексте работы Д. С. Ватолина (Московский государственный университет) по методам оптимизации алгоритмов фрактального сжатия статических растровых изображений и Н. А. Вагановой (Институт вычислительной математики и математической геофизики) по методам фрактального сжатия динамических изображений. Большой вклад в разработку методов обработки растровых изображений внесли работы, выполненные в институте систем обработки изображений РАН, в частности работы В. В. Сергеева и В. А. Сойфера.

Тем не менее, большинство публикаций по тематике исследования методов фрактального сжатия изображений свидетельствуют о том, что в настоящее время задача построения эффективних по времени алгоритмов фрактального сжатия растрового изображения остается актуальной с точки зрения практических характеристик их программных реализаций.

Объект исследования

Объектами исследования диссертационной работы являются вычислительные (компьютерные) алгоритмы фрактального сжатия изображений в аспекте их временной эффективности при ограничениях, налагаемых особенностями и спецификой их применения в разрабатываемых программных средствах и системах.

Целью работы является повышение временной эффективности компонентов алгоритмического обеспечения программных средств фрактального сжатия изображений за счет разработки эффективных методов сопоставления доменно-ранговых областей на основе метода пространственно чувствительного хеширования.

Научная новизна диссертации заключается в:

1. Обосновано применение метода пространственно чувствительных хэш-функций для поиска множества ближайших соседних элементов (решение fr,cj-NN задачи) в применении к фрактальному сжатию изображений.

2. Предложен способ построения семейства хеш-функций, адаптированных к особенностям задачи фрактального сжатия изображений.

3. Разработан ресурсно-эффективный комбинированный алгоритм фрактального сжатия статических изображений.

Практическая ценность результатов работы заключается в возможности решения: задачи повышения временной эффективности алгоритмического обеспечения фрактального сжатия изображений с использованием разработанного метода фрактального сжатия изображений на основе применения модифицированного метода приближенного решения задачи поиска ближайшего соседнего элемента при помощи пространственно-чувствительного хеширования; задачи разработки комбинированных алгоритмов фрактального сжатия изображений, включающих в себя алгоритмы, рациональные по различным требованиям к качеству декодированного изображения и времени сжатия; задачи экспериментального исследования временной эффективности алгоритмов фрактального сжатия изображений с использованием разработанных программных средств.

Основные результаты, выносимые на защиту:

1. Применение метода пространственно чувствительных хэш-функций для поиска множества ближайших соседних элементов (решение fr,cJ-NN задачи) в применении к фрактальному сжатию изображений.

2. Способ построения семейства хеш-функций, адаптированных к фрактальному сжатия изображений.

3. Асимптотические оценки временной эффективности разработанного алгоритма фрактального сжатия изображений.

4. Ресурсно-эффективный комбинированный алгоритм фрактального сжатия статических изображений, разработанный на основе предложенных методов.

Апробация работы

Основные положения и результаты диссертационной работы докладывались на всероссийских конференциях и семинарах: I Всероссийский семинар аспирантов, 2006 г.; Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации», Алушта, 2005 г.; VIII Всероссийской научно-технической конференции «Новые информационные технологии», Москва,

2005 г.; VIII Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права», Сочи, 2005 г.;

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ

Rm — ранговый блок с номером т, представленный как вектор, полученный путем построчного сканирования соответствующей области изображения в линейном векторном пространстве 91".

Dk — ранговый блок с номером к, представленный как вектор, полученный путем построчного сканирования соответствующей области изображения в линейном векторном пространстве 9Г. d(-,-) — функция, вычисляющая расстояние между своими операндами представляющими точки в полном метрическом пространстве. s — коэффициент масштабирования (scaling). о — смещение (offset). w(-) — сжимающее (как правило афинное) преобразование. fix, у) —изображение, рассматриваемое как вещественная функция. ЕЩ„,Ц) — функция, вычисляющая ошибку приближения (расстояние, между ранговым и доменным блоками.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Винокуров, Станислав Владимирович

Основные результаты работы

1. Математические модели и основы применения метода поиска ближайшего соседнего элемента при помощи пространственно чувствительных хэш-функций к фрактальному сжатию изображений.

2. Метод повышения временной эффективности алгоритма фрактального сжатия, основанный на сведении задачи фрактального сжатия изображений к задаче поиска ближайшего соседнего элемента в многомерном пространстве, и модифицированного метода приближенного решения задачи поиска ближайшего соседнего элемента при помощи пространственно-чувствительного хеширования.

3. Ресурсно-эффективный комбинированный алгоритм фрактального сжатия изображений в составе комплексных программных систем, разработанный на основе предложенных методов.

Перспективы развития исследований

Предложенный в работе метод фрактального сжатия изображений с применением пространственно-чувствительного хеширования, безусловно, подлежит дальнейшему улучшению. Многие вопросы остались за рамками диссертационного исследования. С точки зрения автора представляют интерес следующие направления развития метода:

Применение энтропийного кодирования к полученному фрактальному коду изображения, что позволит улучшить степень сжатия в среднем еще на 20%.

- Совмещение данного метода с другими метода повышения временной эффективности фрактального сжатия, или с векторным квантованием.

- Разработка и применение пространственно-чувствительных хеш-функций специального вида, приспособленных к фрактальному сжатию изображений заданного типа.

- Распараллеливание процесса сжатия изображения. Фрактальное сжатие традиционно хорошо поддается процессу распараллеливания, что позволяет построить создавать аппаратное обеспечение, специально приспособленное для эффективного решения данной задачи.

Фрактальное сжатие является вычислительно сложной задачей. За повышенное качество изображение и высокие коэффициенты сжатия приходится платить свою цену. Это делает фрактальное сжатие наиболее подходящим для применения в приложениях телекоммуникации и хранения информации, где сжатие не требуется выполнять в реальном времени. Фактически, именно по этой причине данные методы нашли свое применение на рынке программных систем и при подготовке компакт дисков.

ЗАКЛЮЧЕНИЕ

В диссертации рассмотрены теоретические и практические вопросы разработки и построения эффективных методов фрактального сжатия изображений. Фрактальное сжатие изображений представляет собой новый подход к сжатию растровых изображений. Фрактальный кодировщик позволяет использовать свойства самоподобия изображения — повторяющиеся похожие друг на друга блоки изображения на различных уровнях разрешения. Реалистичные природные изображения не являются случайным набором точек, и, очевидно, что они в большей части состоят из повторяющихся одинаковых блоков, который могут в значительной степени варьироваться от изображения к изображению, и эту особенность можно использовать для эффективного сжатия изображения.

Класс методов обобщенного фрактального сжатия изображений достаточно широк, однако, все они основываются на методе, предложенном Джеквином, который достаточно прост в реализации, а математические основы этого метода хорошо изучены. Однако, данный метод обладает большим недостатком — он имеет очень низкую временную эффективность. Поэтому в настоящее время существует целый класс работ, в том числе и данная диссертация, посвященных улучшению временной эффективности базового метода фрактального сжатия и расширению горизонтов его практического применения.

Несмотря на то, что фрактальное сжатие изображений является относительно новой сферой исследований, и методы, применяемые здесь, в корне отличны от методов классических алгоритмов сжатия изображений, эффективность фрактального сжатия с точки зрения соотношения качества изображения и степени сжатия сравнима с лучшими современными методами сжатия. Однако сложность фрактального кодирования очень высока, что обуславливает значительные затраты по времени на процесс сжатия изображения.

В диссертационной работе предложен и опробирован новый метод повышения временной эффективности фрактального сжатия растровых изображений.

Список литературы диссертационного исследования кандидат технических наук Винокуров, Станислав Владимирович, 2007 год

1. Александров В.В., Горский Н.Д. Представление и обработка изображений: рекурсивный подход II Jl-д.: Наука 1985, 190 с. СойферОЗ] В. А. Сойфер. Методы компьютерной обработки изображений, ФИЗМАТЛИТ 2003, 784 с.

2. Алимов Ш.А. Принцип сжатых отображений (Методы прикладного анализа). М.: Знание, 1983.64 с.

3. Балханов В.К. Введение в теорию фрактального исчисления. Улан-Удэ: Б ГУ, 2001.

4. Божокин С.В., Паршин Д.А. Фракталы и мулътифракталы. М., Ижевск: РХД, 2001.

5. Бондаренко В.А., Дольников В.Л. Фрактальное сжатие изображений по Барнсли-Слоану,! Автоматика и телемеханика. 1994. №5. С.12-20.

6. Ваганова Н. А., Фрактальное сжатие динамических изображений, Информационные технологии, Новосибирск 1999.

7. Васильев К.К., Наместников С.М. Анашз методов сжатия изображений при разных критериях оценки качества восстановленного изображения. Труды IX международной научно-технической конференции «Радиолокация, навигация, связь», Воронеж, 2003, с. 1060-1067.

8. Ватолин Д. С., Фрактальное сжатие изображений, Computerworld N06,1996.

9. Ватолин Д.С., Использование ДКП для ускорения фрактального сжатия изображений, Программирование, Номер 3, 1999, стр. 51-57.

10. Ватолин Д.С. Алгоритмы сжатия изображений И ISBN 5-89407-041-4 М.: Диалог-МГУ, 1999.

11. Ватолин Д.С. Тенденции развития алгоритмов архивации графики // Открытые системы. Номер 4, 1995.

12. Вишик М.И. Фрактальная размерность множеств. II Соросовский образовательный журнал, № 1, 1998.

13. Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных системах научных исследований. М.: Наука, 1982. - 213 с.

14. Горбачев А.А. Колданов А.П., Потапов А.А., Чигин Е.П., Нелинейная радиолокация. Серия "Фракталы. Хаос. Вероятность", М.: Радиотехника, 2005.

15. Гонсалес Р., Вудс Р., Цифровая обработка изображений — М.: Техносфера, 2005. — 1072 с.

16. Добеши И .Десять лекций по вейвлетам И Пер. с анг. Е.В. Мищенко, под ред. А.П.Петухова. М.: Ижевск 2001,464 стр.

17. Дьяконов В. П., Вейвлеты. От теории к практике. Изд. 2-е, перераб. И доп. М.: СОЛОН-Пресс, 2004. - 400 с.

18. Забарянский С.Ф. Фрактальное сжатие изображений. // Компьютеры + программы, № 6(39), 1993.

19. Зельдович Я.Б., Соколов Д.Д. Фракталы, подобие, промежуточная асимптотика. IIУФН, Т. 14, Вып. 3, 1985.

20. Иванов С.С. Оценка фрактальной размерности самоаффинных множеств: метод встречного масштабирования дисперсий. II ДАН, 1993, N 1, Т.332.

21. Карпов П.М. Быстрый фрактачьный алгоритм сжатия изображений, Научная сессия МИФИ, 2006. Том 15.

22. Колмогоров А.Н. К логическим основам теории информации и теории вероятностей. //Проблемы передачи информации, 1969, том V, вып. 3, сс. 3-7.

23. Морозов А.Д., Введение в теорию фракталов. Москва-Ижевск: Институт компьютерных исследований, 2004, 160 стр.

24. Павлидис Т. Алгоритмы машинной графики и обработка изображений И М.: Радио и связь 1986, 400 с.

25. Потапов А.А., Фракталы в радиофизике и радиолокации: Топология выборки. II Университетская книга, 2005.

26. Претт У. Цифровая обработка изображений в двух томах // М.: Мир 1982,790 с.

27. Розеншельд А. Распознавание и обработка изображений II М.: Мир 1972,232 с.

28. Смирнов Б.М. Физика фрактальных кластеров. М.: Наука, 1991.

29. Сойфер В.А., Сергеев В. В., Попов С. Б., Мясников В. В., Теоретические основы цифровой обработки изображений.; М-во образования Рос. Федерации и др. -Самара : СГАУ, 2000. 255 с.

30. Сойфер В.А., Компьютерная обработка изображений, Часть 1. Математические модели. Соросовский образовательный журнал N2, 1996.

31. Сойфер В. А., Компьютерная обработка изображений, Часть 2. Методы и алгоритмы. Соросовский образовательный журнал N2, 1996.

32. Странные аттракторы. // Под редакцией Синая Я.Г. и Шильникова Л.И. -М.: Мир, 1981.

33. Транковский С. Красота хаоса // Наука и жизнь, № 4, 1994.

34. Шабаршин А. А. Фрактальное сжатие и восстановление видеоинформа-ijuu в реальном масштабе времени, Научные школы УПИ-УГТУ 1997.

35. Шабаршин А.А. Метод фрактального сжатия изображений, Научные школы УПИ-УГТУ 1997. №1. С.70-82.

36. Шредер М. Фракталы, хаос, степенные законы. М., Ижевск: РХД 2001.

37. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. Учебное пособ.- М.: Изд. Триумф, 2003 320 с. Эфрос82] Эфрос A.JT. Физика и геометрия беспорядка. - М.: Наука, 1982.

38. Федер Е. Фракталы. М.: Мир, 1991.

39. Фоменко А.Т. Наглядная геометрия и топология. М.: МГУ-ЧеРо, 1998.

40. Фракталы. И Компьютерная газета, N 36 (226), 1999.

41. Яншин В.В. Анализ и обработка изображений (принципы и алгоритмы) II М.: Машиностроение, 1995.

42. ANN: Approximate Nearest Neighbors, http://www.cs.umd.edu/~mount/ANN.

43. Arya S., Mount D.M., Netanyahu N. S., Silvernam R., Wu A., An optimal algorithm for approximate nearest neighbour searching, Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms (1994) 573-582.

44. Bani-Eqbal В., Speeding up fractal image compression, in: Proceedings from IS&T/SPIE 1995 Symposium on Electronic Imaging: Science & Technology, Vol. 2418: Still-Image Compression 1995.

45. Barnsley M. F., Fractals Everywhere, New York: Academic, 1988.

46. Barthel K. U., Schiittemeyer J., Voye Т., Noll P., A new image coding technique unifying fractal and transform coding, in: Proc. ICIP-94 IEEE International Conference on Image Processing, Austin, Texas, Nov. 1994.

47. Bedford Т., Dekking F.M., Keane M. S., Fractal image coding techniques and contraction operators, Nieuw Arch. Wisk. (4) 10,3 (1992) 185-218.

48. Breazu M., Toderean G., Region-based fractal image compression using deterministic search, IEEE ICIP 98, Chicago, Oct. 1998.

49. Bogdan A., Meadows H., E., Kohonen neural network for image coding based on iteration transformation theory, in: Proceedings from SPIE Neural and Stochastic Methods in Image and Signal Processing, Vol. 1766, pp. 425-436, 1992.

50. Boss R. D., Jacobs E. W., Archetype classification in an iterated transformation image compression algorithm, in: Fractal Image Compression Theory and Applications, Y. Fisher (ed.), Springer-Verlag, New York, 1994.

51. Burkhard W. A., Keller R. M. Some approaches to best-match file searching. Commun. ACM, 16:230-236, 1973.

52. Caso G., Obrador P., Kuo C.-C. J., Fast methods for fractal image encoding, in: Proceedings from IS&T/SPIE 1995 Symposium on Electronic Imaging: Science & Technology, Vol. 2501, pp. 583-594, 1995.

53. Chambers J.M., Mallows C.L., and Stuck B. W. A method for simulating stable random variables. J. Amer. Statist. Assoc., 71:340-344, 1976.

54. Chavez E., Navarro G., Baeza-Yates R., and Marroquin J. L. Searching in metric spaces. ACM Computing Surveys, 33(3): 273-321, 2001.

55. Ciscar G., On entropy coding Fisher's fractal quadtree code, June 1996.

56. Darrell Т., Indyk P., Shakhnarovich G. (eds.), Locality-sensitive hashing using stable distributions, Nearest Neighbor Methods in Learning and Vision: Theory and Practice, MIT Press, 2006.

57. Dekking F.M., An inequality for pairs of martingales and its applications to fractal image coding, Technical Report 95-10, Faculty of Technical Mathematics and Informatics, Delft University of Technology, 1995.

58. Dekking F.M., Fractal image coding: some mathematical remarks on its limits and its prospects, Technical Report 95-95, Faculty of Technical Mathematics and Informatics, Delft University of Technology, 1995.

59. Devroye L., Gyorfi L., Lugosi G. A Probabilistic Theory of Pattern Recognition. Springer-Verlag, New York, 1996.61 . Dony R., Vrscay E., IFS coding using an MPC network library, 1998 Canadian Conf. Eleclr. and Сотр. Engineering, ON, May 1998.

60. Fibush D.K. Practical application of objective picture quality measurements, Broadcasting Convention, 1997. International Volume , Issue , 12-16 Sep 1997. pp. 504 -513.

61. Fisher Y., Fractal image compression, SIGGRAPH'92 Course Notes. 1992. Vol.12. P.7.1-7.19, 21 p.

62. Fisher Y., Fractal Image Compression: Theory and Application. New York: Spriger-Verlag, 1995.

63. Fix E., Hodges J. L. Jr., Discriminatory analysis, non-parametric discrimination. Technical Report 4, USAF School of Aviation Medicine, 1951. Project 21-49-004.

64. Friedman J. H., Bentley J. L., Finkel R. A., An algorithm for finding best matches in logarithmic expected time, ACM Trans. Math. Software 3,3 (1977) 209-226.

65. Frigaard C., Gade J., Hemmingsen Т., Sand Т., Image compression based on fractal theory, Institute for Electronic Systems, Aalborg University, Denmark, 1994.

66. Forte В., Vrscay E. R., Solving the inverse problem for function/image approximations using iteratedfunction systems, I. Theoretical basis, Fractals 2,3 (1994) 325-334.

67. Gharavi-Alkhansari M., Fractal-based image and video coding using matching pursuit, PhD Thesis, University of Illinois, 1997.

68. Gray R.M., Neuhoff D. L. Quantization. IEEE Trans. Inform. Theory, 44:23252383,1993.

69. Hamzaoui, Codebook clustering by self-organizing maps for fractal image compression, in: NATO ASI Conf. Fractal Image Encoding and Analysis, Trondheim, July 1995, to appear in a special issue of Fractals.

70. Hjaltason G.R., Samet H. Index-driven similarity search in metric spaces. ACM Trans. Database Syst. 28(4):517-580, 2003.

71. Hurtgen В., Stiller C., Fast hierarchical codebook search for fractal coding of still images, in: EOS/SPIE Visual Communications and PACS for Medical Applications'93, Berlin, 1993.

72. Hurtgen В., Performance bounds for fractal coding, Proceedings oflCASSP-1995 IEEE International Conference on Acoustics, Speech and Signal Processing, Vol. 4, Detroit, 1995.

73. Hutchinson J., Fractals and self-similarity, Indiana Univ. J. Math. 30, 713-7471981).

74. Indyk P., Motwani R. Approximate nearest neighbor: towards removing the curse of dimensionality. Proceedings of the Symposium on Theory of Computing, 1998.

75. Indyk P. Stable distributions, pseudorandom generators, embeddings and data stream computation. Proceedings of the Symposium on Foundations of Computer Science, 2000.

76. Jacquin, A.E., A Fractal Theory of Iterated Markov Operators with Applications to Digital Image Coding, PhD Thesis, Georgia Institute of Technology, 1989.

77. Jacobs E. W., Fisher Y., Boss R. D., Image compression: A study of the iterated transform method, Signal Processing 29 (1992) 251-263.

78. Kominek J., Algorithm for fast fractal image compression, Proceedings of SP1E, Volume 2419, 1995.

79. Knuth Donald Ervin. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, Boston, 1998.

80. Lee C.-H., Chen L. H., Fast closest codeword search algorithm for vector quantization, IEE Proc.-Vis. Image Signal Process. 141, 3 (1994) 143-148.

81. Lepsoy S., Attractor Image Compression: Fast Algorithms and Comparisons to Related Techniques, PhD Thesis, The Norwegian Institute of Technology, Trondheim, Norway, June 1993.

82. Leps0y S., 0ien G. E., Fast attractor image encoding by adaptive codebook clustering, in: Fractal Image Compression Theory and Application, Y. Fisher (ed.), Springer-Verlag, New York, 1994.

83. Lin H., Venetsanopoulos, A.N., Fractal-based image coding by nonlinear contractive functions, in: Proceedings of the 17th Biennial Symposium on Communications, Kingston, Ontario, pp. 295-298, May-June 1994.

84. Linde Y., Buzo A., Gray R. M. An algorithm for vector quantizer design. IEEE Transactions on Communications, 28:84-95, 1980.

85. Lu N. Fractal Imaging, San Diego: Academinc Press, 1997.

86. Mandelbrot B.B., The Fractal Geometry of Nature. New York: W. H. Freeman and Company, 1982.

87. Mayur Datar, Nicole Immorlica, Piotr Indyk, Vahab S. Mirrokni. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. Symposium on Computational Geometry 2004: 253-262.

88. Mico M. L., Oncina J., Vidal E. A new version of the nearest-neighbour approxi-maning and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements. Pattern Recognition Letters, 15(1):9-17, 1994.

89. Monro D.M., Dudbridge F., Fractal approximation of image blocks, in: Proceedings of ICASSP-1992 IEEE International Conference on Acoustics, Speech and Signal Processing,Vol. 3, pp. 485-488, 1992.

90. Motwani R., Naor A., Panigrahy R., lower bounds on Locality Sensitive Hashing. Proceedings of the Symposium on Foundations of Computer Science, 2005.

91. Nolan J.P. An introduction to stable distributions. http://academic2.american.edu/~jpnolan/stable/chap 1 .pdf.

92. Novak M., Attractor coding of images, Licentiate Dissertation, Dept. of Electrical Engineering, Linkoping University, May 1993.

93. Omohundro S. Five balltree construction algorithms. Technical report, International Computer Science Institute, 1989.

94. Saupe D., Hamzaoui R., Hartenstein H., Fractal image compression An introductory overview, in: Fractal Models for Image Synthesis, Compression, and Analysis, ACM-SIGGRAPH'96 Course Notes, 66 p.

95. Sarnoff Corporation, JND: A human vision system model for objective picture quality measurements, Sarnoff Technical Report from www.jndmetrix.com, (2001).

96. Saupe D., Lean domain pools for fractal image compression, in: Proceedings from IS&T/SPIE 1996 Symposium on Electronic Imaging: Science & Technology Still Image Compression II, Vol. 2669, to appear Jan. 1996.

97. Saupe D., Hartenstein H., Lossless acceleration of fractal image compression by fast convolution, in: Proc. ICIP-96 IEEE International Conference on Image Processing, Lausanne, Sept. 1996.

98. Saupe D., Accelerating fractal image compression by multi-dimensional nearest neighbor search, in: Proceedings DCC'95 Data Compression Conference, J. A. Storer and M. Cohn (eds.), IEEE Сотр. Soc. Press, March 1995.

99. Saupe D., Breaking the time complexity of fractal image compression, Technical Report 53, Institut fur Informatik, Universitat Freiburg, 1994.

100. Saupe D., From classification to multi-dimensional keys, in: Fractal Image Compression Theory and Application, Y. Fisher (ed.), Springer-Verlag, New York, 1994.

101. Saupe D., Fractal Image compression via nearest neighbour search, in: Conf. Proc. NATO ASI Fractal Image Encoding and Analysis, Trondheim, July 1995, Y. Fisher (ed.), to appear in Springer-Verlag, New York, 1995.

102. Saupe D., Hamzaoui R., A guided tour of the fractal image compression literature, in: New Directions for Fractal Modelling in Computer Graphics, J. Hart (ed.), ACM SIGGRAPH'94 Cource Notes 13, 1994.

103. Shasha D., Wang T.-L. New techniques for best-match retrieval. ACM Trans. Inf.Syst., 8(2): 140-158, 1990.

104. Uhlmann J. K., Satisfying general proximity/similarity queries with metric trees. Inform. Proc. Letters, 40:175-179, 1991.

105. Vidal E. An algorithm for finding nearest neighbours in (approximately) constant average time. Pattern Recognition Letters, 4:145-157, 1986.

106. Wall L., Kinser W., A fractal block coding technique employing frequency sensitive competitive learning, in: Proc. Of IEEE Communications, Computers and Power, pp. 320-329, 1993.

107. Wohlberg В., Jager G, A Review of the Fractal Image Coding Literature, IEEE Trans. On Image Processing, Vol. 8, No.12, pp. 1716-1729, 1999.

108. Zolotarev V.M. One-Dimensional Stable Distributions. Vol. 65 of Translations of Mathematical Monographs, American Mathematical Society, 1986.

109. Винокуров С.В. Особенности фрактального сжатия изображений. II Автоматизация и современные технологии №12, М.: Машиностроение, 2005, с. 2732.

110. Винокуров С.В. Методы повышения временной эффективности алгоритмов фрактального сжатия изображений. II Материалы конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики», сборник Информатика, МГАПИ, 2005, с. 53-59.

111. Винокуров С.В. Подход к фрактальному сжатию изображений с использованием пространственно-чувствительного хеширования II Методы автоматизации управления: Сборник научных трудов МАДИ ГТУ, 2006, с. 14-19.

112. Винокуров С.В. Построение пространственно-чувствительных хеш-функций, адаптированных к задаче фрактального сжатия изображений // Методы автоматизации управления: Сборник научных трудов МАДИ ГТУ, 2006, с. 19-25.

113. Винокуров С.В. Эффективный алгоритм фрактального сжатия изображений с использованием пространственно-чувствительного хеширования // Открытое образование, 4(57)'2006, с. 62-70.

114. Винокуров С.В., Ульянов М.В. Комплексный критерий качества алгоритмов сжатия и восстановления растровых изображений на основе нормированных оценок II Вестник МГУПИ Серия: Технические и естественные науки 7, 2006, С. 43-52.