автореферат диссертации по радиотехнике и связи, 05.12.04, диссертация на тему:Разработка алгоритмов быстрого фрактального сжатия цифровых изображений

005055475

На правах рукописи

Илюшин Сергей Валерьевич

Разработка алгоритмов быстрого фрактального сжатия цифровых изображений

Специальность 05.12.04 - Радиотехника, в том числе системы и устройства телевидения

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

2 2 НОЯ 2012

Москва-2012

005055475

На правах

Илюшин Сергей Валерьевич

Разработка алгоритмов быстрого фрактального сжатия цифровых изображений

Специальность 05.12.04 - Радиотехника, в том числе системы и устройства телевидения

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Москва - 2012

Работа выполнена на кафедре мультимедийных сетей и услуг связи Федерального государственного образовательного бюджетного учреждения высшего профессионального образования Московский технический университет связи и информатики (ФГОБУ ВПО МТУ СИ)

Научный руководитель:

кандидат технических наук, доцент, ¡Свет Сергей Дарьевич!

Официальные оппоненты: Дворкович Александр Викторович

доктор технических наук, ФГУП ГРЧЦ, начальник управления

Синева Ирина Сергеевна

кандидат физико-математических наук, доцент, ФГОБУ ВПО МТУСИ, доцент кафедры ТВ и ПМ

Ведущая организация:

ЗАО «Московский научно-исследовательский телевизионный институт»

Защита состоится « 4 » декабря 2012 г. в 15 часов на заседании совета по защите докторских и кандидатских диссертаций Д 219.001.01 при МТУСИ по адресу: 111024, Москва, ул. Авиамоторная, д. 8а, ауд. А-448

С диссертацией можно ознакомиться в библиотеке МТУСИ

Автореферат разослан « 3 » ноября 2012 г.

Учёный секретарь

Диссертационного совета Д.219.001.01 к.т.н., доц.

Иванюшкин Р.Ю.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Целью сжатия изображений является минимизация числа бит, требуемых для представления изображения. Существующие способы сжатия цифровых изображений могут быть поделены на две большие категории: без потерь и с потерями. Сжатие без потерь означает, что восстановленное после сжатия изображение с точностью до пикселя соответствует оригиналу. Сжатие без потерь не приводит к высоким коэффициентам сжатия (в 2-10 раз, но обычно не более 3-х раз), в то время как алгоритмы сжатия с потерями позволяют достигать компрессии до 50-ти раз без заметного ухудшения качества.

Используемые сегодня форматы сжатия с потерями JPEG и JPEG 2000 были разработаны Объединённой группой экспертов по машинной обработке фотографических изображений (Joint Photographie Expert Group - JPEG). Общая идея, лежащая в основе этих методов, заключается в применении к изображению преобразования, концентрирующего большую часть энергии в относительно малом количестве коэффициентов. За счёт более грубого квантования значительная часть коэффициентов преобразования, отвечающих за мелкие детали оригинала, обращается в нуль, что позволяет эффективно закодировать полученную битовую последовательность энтропийным кодером. За высокие степени сжатия приходится расплачиваться ухудшением детализации и размытием контуров. Из-за этого в некоторых отраслях, где предъявляются повышенные или специфические требования к качеству изображений, например в медицине, спутниковой фотографии, издательстве, сжатие с потерями практически не используется.

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

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

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

Предметом исследования является ускорение фрактального сжатия изображений.

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

1. Анализ существующих методов сжатия с потерями, их достоинств и недостатков.

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

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

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

Методы исследования. Для решения поставленных задач были использованы как экспериментальные, так и теоретические методы исследования. Теоретическую основу исследования составили труды в области обработки изображений Ю.Б. Зубарева, В.П Дворковича, А.В. Дворковича, А. Жакана, М. Барнсли, Ю. Фишера, Д. Сопа, М. Полвере, М. Наташ, С. Тонга, С. Уэлстида. В работе использованы методы теории фракталов, теории систем итерируемых кусочно-определенных функций, теории сложности вычислений, теории вероятностей и математической статистики, аналитическое моделирование на ЭВМ и машинные расчеты в среде МаАСАО.

Научная новизна диссертационной работы состоит в следующем:

. 1. Обосновано использование в адаптивных схемах разбиения изображения на ранговые блоки в качестве критерия перехода на другой уровень разбиения среднеквад-ратического отклонения (СКО) яркости пикселей рангов вместо среднеквадратиче-ской ошибки сравнения рангов и доменов. Использование нового критерия позволяет напрямую сформировать схему разбиения изображения на ранги, без выполнения многочисленных сравнений рангов и доменов.

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

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

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

5. Рассмотрено распределение координат центров масс доменов на полярной плоскости с точки зрения их корреляции с рангами, то есть с точки зрения критерия оптимальности. Экспериментально показано, что хорошо коррелированные ранговые и доменные блоки могут находиться в пространственно разнесённых частях изображения. В результате разработаны новые алгоритмы классификации блоков изображения по полярному углу центров масс блоков. Использование классификации позволило ускорить фрактальное сжатие в 3-12 раз в зависимости от изображения по сравнению с полным перебором доменов без визуально заметной деградации качества восстановленного изображения. Таким образом, в результате применения модификаций, разработанных в настоящей работе, удалось ускорить фрактальное сжатие изображений до двух порядков.

Личный вклад соискателя. Все основные научные результаты и выводы, изложенные в диссертации, получены автором самостоятельно.

Практическая ценность. Результаты, полученные в диссертации, позволяют создать

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

Использование результатов работы. Основные теоретические положения и практические результаты диссертационной работы были рассмотрены и использованы:

- в обществе с ограниченной ответственностью «Форт-Телеком» при разработке комплекса контроля доступа и видеонаблюдения на необслуживаемых объектах телекоммуникационных сетей / нефтегазотранспортных систем / железнодорожного транспорта (акт внедрения);

- в открытом акционерном обществе «ТАКТ» при разработке новой платы передачи данных (в частности - изображений) в процессе развития универсальной аппаратуры гибкого мультиплексирования ОГМ-ЗОЕ (акт внедрения);

- в учебном процессе при чтении лекций по курсу «Системы документальной электросвязи» (акт внедрения).

Апробация результатов. Основные результаты диссертационной работы докладывались на научных конференциях: 6-й всероссийской научной конференции «Проблемы развития технологических систем государственной охраны, специальной связи и информации», Орёл, 2009г.; 3-й всероссийской научной конференции «Проблемы создания и развития информационно-телекоммуникационной системы специального назначения», Орёл, 2003г.; научной конференции профессорско-преподавательского, научного и инженерно-технического состава МТУ СИ, Москва, 2003г.

Публикации. По материалам диссертации опубликовано 6 печатных работ, из них: 3 статьи в ведущих научных журналах, рекомендованных ВАК РФ.

Основные положения, выносимые на защиту:

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

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

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

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

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

6. Разработанные алгоритмы классификации блоков изображения по полярному углу центров масс блоков позволяют дополнительно ускорить процесс сжатия в 3-12 раз с визуально незаметным снижением качества по сравнению с полным перебором доменов.

Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников и приложения. Общий объем работы — 180 страниц, из них 153 страницы - основное содержание, включая 45 рисунков и 18 таблиц, 19 страниц -приложение, 8 страниц — список использованных источников (123 наименования).

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В главе 1 диссертации проведён аналитический обзор современных методов сжатия с потерями - JPEG, JPEG 2000 и фрактального FIF (Fractal Image Format - формат фрактального изображения). Методы сравниваются друг с другом, оцениваются их достоинства и недостатки. Экспериментально демонстрируется, что фрактальное сжатие опережает своих конкурентов по качеству передачи контуров. На основании проведенного анализа делается вы-

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

Глава 2 целиком посвящена исследованию проблемы фрактального сжатия изображений Изложена математическая теория, лежащая в его основе Кратко рассмотрим, как фрактальное сжатие осуществляется на практике.

1. Для отыскания самоподобия изображение разбивается на блоки двух типов. Для простоты будем считать, что блоки имеют квадратную форму. Большие блоки принято называть доменами, а маленькие - рангами (см. рисунок 1). Сторона домена в два раза больше стороны ранговой области.

Ранговые области

Доменные области

Рисунок 1. Преобразование блоков при фрактальном сжатии изображения

2. Домены уменьшаются до размеров ранга путём усреднения яркости соседних пикселей.

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

Г(£)) = л;£) + о/, (1)

где |s| < 1 - коэффициент контраста, о е [-255,255] - коэффициент яркости. Налагаемые ограничения необходимы для того, чтобы гарантировать сходимость при восстановлении изображения, I- единичная матрица.

Вычисляются коэффициенты преобразования контраста s и яркости о для каждого домена по формулам:

N N N N N N

*2ZZ4A,- ZZA.ZZ^,

''I /'I_1-1 M M /H

N N С N N >

ZZA,

1-1 /-1 V'-1 M .J

=0,TO5 = 0; (2)

Î=I /=i ;=i ) ... . .

N N N N

—^^—, . . . (3)

где DhR- матрицы, представляющие собой соответственно домен, уменьшенный до размера ранга, и ранг, N—размер стороны рангового блока.

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

4. На основе рассчитанных коэффициентов преобразования оценивается соответствие домена и ранга по среднеквадратической метрике:

W W ( N N N N N Ы \ ( N H ' \

Z2X, H sYLDh-*ZZA, д, +*ZZA, H ^TL*,.,

_ i'i M_V "1 _M_M y V '■=' /'1 J /44

N2

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

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

R = sD+oI (5)

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

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

Далее в главе 2 проведен обзор, систематизированы и обобщены исследования и научные статьи по фрактальному сжатию изображений с момента его создания. Рассмотрены различные варианты разбиения изображения на ранговые блоки; преобразования, применяемые к блокам; способы организации доменного пула; стратегии поиска доменов, позволяющие ускорить фрактальное сжатие. На основе обзора выделяются наиболее перспективные области для дальнейшего исследования путей ускорения фрактального сжатия изображений.

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

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

квадродерева.

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

Глава 3 посвящена разработке новых алгоритмов повышения эффективности фрактального сжатия, которая велась по трем направлениям:

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

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

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

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

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

В алгоритме квадродерева, предложенном Фишером, в качестве критерия, определяющего переход на другой уровень разбиения, используется среднеквадратическая ошибка, равная где г - величина, вычисляемая по формуле (4). Для среднеквадратической ошибки устанавливается пороговое значение. Если после сравнения ранга со всеми доменами текущего уровня разбиения не удалось подобрать доменную область, обеспечивающую покрытие ранга с ошибкой, меньше пороговой, то ранг разбивается на 4 субблока. Очевидно, что для формирования мозаичной схемы разбиения такой подход использовать не удастся.

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

Дня этого необходимо выбрать новый критерий перехода на другой уровень разбиения. Формулу (4) можно переписать в виде:

В формуле (2) в числителе фактически записана ковариация ранга и домена, а в знаменателе - дисперсия домена. Если числитель и знаменатель умножить на среднеквадрати-ческое отклонение (СКО) ранга, то коэффициент преобразования контраста можно выразить через коэффициент корреляции ранга и домена:

г =

(б)

ЛГ2

(7)

Коэффициент преобразования яркости (3) можно переписать в виде:

где /¡ий- средние значения яркости пикселей ранга и домена соответственно. Если подставить (7) и (8) в (6), получится:

Область значений выражения {\-р2 (Л, £>)) Лежит в интервале [0,1]. Если домен с точностью до пикселя преобразуется в текущий ранг при помощи коэффициентов 5 и о, то тогда коэффициент корреляции В) = 1 и г = 0. Если же домен абсолютно не коррелирован с рангом, то тогда р(Я, О)-0 и значение г достигает своего максимума для данного ранга и становится равным его дисперсии г = сг2Я. На практике часто вместо дисперсии удобнее использовать СКО стЛ = л/<т2Я . Таким образом, СКО ранга является ограничением сверху среднеквадратической ошибки при сравнении данного ранга с любыми доменами, и, следовательно, его можно использовать в качестве критерия для уменьшения размеров рангов при адаптивном разбиении изображения. При помощи СКО рангов можно напрямую сформировать адаптивную схему разбиения, что хорошо подходит для мозаики. Для увеличения степени сжатия при разработке мозаичной схемы было решено использовать перекрывающиеся ранговые блоки. В результате проведенных исследований был разработан гибкий двухпроходный алгоритм, который позволил сократить количество блоков в схеме разбиения на 40% по сравнению с методом квадродерева при аналогичных параметрах разбиения (см. рисунок 2). Уменьшение количества ранговых блоков влечет за собой повышение коэффициента сжатия. Использование перекрывающихся рангов во фрактальном сжатии снижает блочный эффект. Хотя борьба с блочным эффектом не ставилась в качестве задачи при разработке, в предлагаемом автором алгоритме можно принудительно устанавливать глубину перекрытия для блоков всех размеров, кроме наименьшего. Введение принудительного перекрытия блоков, с одной стороны, способствует уменьшению блочного эффекта, а с другой - приводит к увеличению количества рангов, и, следовательно, к увеличению времени обработки и сокращению коэффициента сжатия. Из-за снижения эффективности самого сжатия принудительное перекрытие в экспериментальной части данной работы не рассматривалось.

а б

Рисунок 2. Изображение «Lena», разбитое на ранги методом квадродерева (а) и предлагаемым автором двухпроходным мозаичным методом с перекрывающимися блоками (б) Второе направление исследований связано с изменением критерия оптимальности, используемого при сравнении рангов и доменов. Как уже отмечалось, каждый ранг сравнивается с множеством доменов. Упростив процедуру этого сравнения, можно получить значительный выигрыш в скорости сжатия.

Для ускорения процесса автором было предложено в качестве критерия оптимальности вместо (4) использовать коэффициент корреляции Пирсона:

r' = p(R,D). (10)

Чем лучше реальная зависимость R от D аппроксимируется линейной (1), тем ближе по модулю к 1 будет их коэффициент корреляции. Использование коэффициента корреляции позволяет, в отличие от (4), сразу оценить оптимальность текущего домена для данного ранга без расчета коэффициента преобразования контраста (2) и яркости (3). Таким образом, коэффициенты преобразования контраста и яркости для каждого ранга будут рассчитываться только один раз, а не для каждого сравнения ранг-домен, как это необходимо при использовании (4). Формулу (2) для коэффициента преобразования контраста так же можно переписать через коэффициент корреляции (7). СКО яркостей пикселей рангов и доменов можно подсчитать заранее, а не вычислять при каждом сравнении, что позволит увеличить скорость обработки на компьютере. Для коэффициента преобразования контраста должно выполняться условие < 1. Коэффициент корреляции, являющийся первым сомножителем в формуле

(7), не может быть больше единицы по абсолютному значению. Таким образом, если второй сомножитель аЯ/оП < 1, то |«| < 1 для любых Л и £>. Чтобы обеспечить выполнение этого условия, в качестве кандидатов в ранговую область для данного ранга мы должны рассматривать только те домены, которые удовлетворяют неравенству:

сгО > <тЛ. (11)

Практически условие (11) означает, что контрастность домена должна быть выше контрастности ранга.

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

о' = Л. (12)

Очевидно, что о'е [0,255] для любого Л в отличие от ое [-255,255], что позволяет сэкономить 1 бит на знаке и, следовательно, увеличить сжатие по сравнению с (3).

Формулу (3) можно переписать в виде (8), подставляя (8) в (1) получим:

Г(£)) = «£> + о/=«(0-25/) + Л/. (13)

Восстановление ранговой области происходит аналогично методу, описанному выше,. только вместо формулы (5) с учётом (13) и (12) будет использоваться формула:

Л = 5(£>-Д/) + о7. (14)

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

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

В большом числе работ для сокращения доменного пула предлагается использовать различные способы классификации блоков. Классификационные методы используют те чис-

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

Яркостная конфигурация блока определяется пространственным распределением значений (или масс) пикселей внутри блока, таким образом, схожие распределения должны соответствовать похожим конфигурациям. Поскольку координаты центров масс схожих распределений располагаются близко друг к другу, их можно использовать в качестве критерия для исключения непохожих блоков. Координаты центра масс для блока В размером пикселей вычисляются по формулам:

1 » " ЛГ + 1

д:

1 » « .в if+l (15)

N N

где В,, - значение яркости (масса) пикселя с координатами (i,j), M = - масса

tel м

блока. Желательно, чтобы критерий классификации блоков был инвариантен относительно преобразований (1). Если блок В умножить на коэффициент контраста s, то координаты центра масс не изменятся. При добавлении коэффициента яркости о центр масс будет перемещаться вдоль прямой, проходящей через начало координат, в связи с чем для представления центра масс блока удобней координаты, полученные по формуле (15), перевести в полярные. Это позволит нам отделить инвариантную составляющую координат центра масс блока - полярный угол - от меняющегося полярного радиуса.

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

Каждый класс формируется из доменов, чьи центры масс оказались в паре секторов,

угол между биссектрисами центральных углов которых равен к. Для того, чтобы охватить все домены изображения, нам надо разбить интервал [0, к\ на т классов. На этапе сжатия,

рассчитав полярный угол центра масс ранга, мы сможем определить, к какому классу он относится, и поиск домена вести в том же классе.

Классификацию можно проводить двумя способами. Первый - с фиксированными центральными углами и различным количеством доменов в классах. Второй - с фиксированным количеством доменов в классах и «плавающими» углами (см. рисунок 3).

Рисунок 3. Классификация с фиксированными центральными углами (1-й способ, а) и с «плавающими» центральными углами (2-й способ, б) Предлагаемые способы классификации по полярному углу центров масс блоков, позволят нам проводить сравнение с доменами, которые были отобраны по всему изображению и при этом хорошо коррелированы с рангом. Так же мы можем гибко регулировать объем доменного пула, тем самым управляя качеством и скоростью сжатия.

Использование классификации позволило сократить время сжатия в зависимости от типа изображения и количества используемых классов в 3 - 12 раз по сравнению с полным перебором доменов. Эксперименты показали превосходство второго способа классификации (с «плавающими» границами классов и постоянным количеством доменов в классах) над

первым (с равными центральными углами, определяющими границы классов).

В главе 4 описываются результаты экспериментов по сжатию изображений при использовании разработанного метода, его сравнение с алгоритмом-прототипом по времени и качеству получаемых изображений. Также проводится сравнение созданного фрактального алгоритма со сжатием по методам JPEG и JPEG 2000. Сравнение проводится как с использованием стандартных тестовых изображений, так и медицинских изображений. По результатам сравнения нового метода с алгоритмом-прототипом делается вывод о том, что разработанные в данной диссертации модификации позволяют создать алгоритм фрактального сжатия изображений, работающий быстрее в 30 - 120 раз, чем прототип, при этом превосходящий его по качеству и коэффициенту сжатия. Сравнение с другими способами сжатия выявило превосходство фрактального алгоритма по передаче контуров, а также показало, что использование фрактального сжатия на медицинских изображениях приводит к понижению шумов. По соотношению качество/коэффициент сжатия фрактальный алгоритм опередил сжатие по методу JPEG, показав результаты, сходные с JPEG 2000. Более того, при степенях сжатия более 10-ти раз использующийся сегодня стандарт JPEG не может обеспечить высокого качества, необходимого для медицинских изображений.

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

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

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

1. Обосновано использование среднеквадратического отклонения яркости пикселей ранга в качестве критерия уменьшения размера рангового блока вместо среднеквадратической ошибки сравнения ранга с доменами, использовавшейся в алгоритме квадродерева.

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

ях, к которым относятся рентгеновские изображения.

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

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

5. По величине PSNR разработанный алгоритм опережает сжатие по алгоритму JPEG и не уступает перспективному алгоритму JPEG 2000.

6. При визуальной оценке разработанный фрактальный алгоритм превосходит своих конкурентов по качеству передачи контуров.

7. Применение фрактального сжатия к изображениям типа ультразвуковых приводит к подавлению шумов.

СПИСОК РАБОТ ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ В ведущих периодических изданиях, входящих в перечень ВАК

Илюшин C.B., Свет С.Д. Фрактальное сжатие телемедицинских изображений. // Электросвязь. - 2009. - №4. - С.36-40.

Илюшин C.B. Подавление спекла на медицинских ультразвуковых изображениях при помощи фрактального кодирования//T-Comm. - 2011. -№3. -С.22-26. Илюшин C.B. Ускорение фрактального сжатия изображений путём классификации блоков по полярному углу их центров масс // T-Comm. - 2011. №4. С.43-47.

В других изданиях

Свет С.Д., Илюшин C.B. Фрактальное сжатие растрированных изображений // Тез. докл. Науч. конф. профессорско-преподавательского, научного и инженерно-технического состава МТУСИ. - М.: МТУСИ, 28-30 янв. 2003г. - Книга 2. - С.23. Илюшин C.B., Свет С.Д. Повышение эффективности фрактального сжатия цифровых изображений // Проблемы создания и развития информационно-телекоммуникационной системы специального назначения: Сборник докладов и тезисов 3-й Всероссийской науч. конф., 11-12 фев. 2003г. Часть 2. / под общей редакцией д.т.н., проф. генерал-лейтенанта Гусева В.В. - Орел: Академия ФАПСИ, -2003. — С.64-65.

Илюшин C.B. Фрактальное сжатие изображений с отбором доменов в полярной системе координат // Проблемы развития технологических систем государственной охраны, специальной связи и информации: Материалы 6-й Всероссийской науч. конф., 5-6 фев. 2009г. Часть 5 / под общ. ред. проф. В.М. Щекотихина. - Орел: Академия ФСО России, - 2009. - С.66-68.

Подписано в печать 26.10.2012. Формат 60x84/16. Печать офсетная Печ.л. 1,5. Тираж 100 экз. Заказ 194.

Оперативная полиграфия «Брис - М» 111024, г. Москва, ул. Авиамоторная, д.8

Введение.

Глава 1 Анализ современных методов сжатия неподвижных цифровых изображений с потерями.

1.1 Постановка задачи.

1.2 Общие принципы сжатия цифровых изображений.

1.3 Оценка качества изображения, сжатого с потерями.

1.4 Анализ технологии сжатия, лежащей в основе стандарта JPEG.

1.5 Анализ технологии сжатия, лежащей в основе стандарта JPEG 2000.

1.6 Анализ фрактальной технологии сжатия на примере формата FIF.

1.7 Сравнение современных методов сжатия.

Выводы по главе 1.

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

2.1 Постановка задачи.

2.2 Принцип фрактального сжатия изображений.

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

2.3.1 Варианты разбиения изображения на ранговые блоки.

2.3.2 Блочные преобразования.

2.3.3 Способы организации доменного пула.

2.3.4 Стратегии поиска.

2.3.5 Представление параметров преобразования.

2.4 Сравнение различных вариантов фрактального алгоритма.

Выводы по главе 2.

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

3.1 Постановка задачи.

3.2 Критерий уменьшения размера ранга при адаптивном разбиении изображения.

3.3 Мозаичное разбиение на ранговые блоки.

3.4 Мозаичная схема с перекрывающимися ранговыми блоками.

3.5 Мозаичная схема с перекрывающимися ранговыми блоками и последующим исключением лишних блоков.

3.6 Изменение алгоритма сравнения ранга с доменами.

3.7 Классификация блоков.

Выводы по главе 3.

Глава 4 Описание проведённых экспериментальных исследований.

4.1 Постановка задачи.

4.2 Сравнение корреляционного алгоритма сравнения ранга с доменами с алгоритмом-прототипом

4.3 Сжатие с полным перебором доменов.

4.4 Сравнение мозаичных схем разбиения на ранги с квадродеревом.

4.5 Сравнение фрактального сжатия с другими способами компрессии с потерями

4.6 Применение алгоритмов сжатия с потерями к медицинским изображениям.

Выводы по главе 4.

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

Целью сжатия изображений является минимизация числа бит, требуемых для представления изображения. Существующие способы сжатия цифровых изображений могут быть поделены на две большие категории: без потерь и с потерями. Сжатие без потерь означает, что восстановленное после сжатия изображение с точностью до пикселя соответствует оригиналу. Сжатие без потерь не приводит к высоким коэффициентам сжатия (в 2-10 раз, но обычно не более 3-х раз [6]), в то время как алгоритмы сжатия с потерями позволяют достигать компрессии до 50-ти раз без заметного ухудшения качества [6]. Дело в том, что цифровое изображение имеет существенное количество излишней информации, которая может быть устранена практически без визуальной за-метности. Другими словами, существует много способов изменить изображение таким образом, что возникшие в результате этого искажения с точки зрения наблюдателя, для которого предназначено это изображение, будут несущественны, зато представление информации в новой форме позволит значительно увеличить компрессию по сравнению со сжатием без потерь.

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

Используемые сегодня форматы сжатия с потерями JPEG и JPEG 2000 были разработаны Объединённой группой экспертов по машинной обработке фотографических изображений (Joint

Photographie Expert Group - JPEG). Общая идея, лежащая в основе этих методов, заключается в применении к изображению преобразования, концентрирующего большую часть энергии в относительно малом количестве коэффициентов. За счёт более грубого квантования значительная часть коэффициентов преобразования, отвечающих за мелкие детали оригинала, обращается в О, что позволяет эффективно закодировать полученную битовую последовательность энтропийным кодером. За высокие степени сжатия приходиться расплачиваться ухудшением детализации и размытием контуров. Из-за этого в некоторых отраслях, где предъявляются повышенные или специфические требования к качеству изображений, например в медицине, спутниковой фотографии, издательстве, сжатие с потерями практически не используется. В этих отраслях сжатие либо не допускается, либо используется сжатие без потерь, которое, как уже отмечалось выше, не позволяет радикально сократить объем цифровых изображений. Отказ от использования сжатия с потерями приводит к увеличению затрат на хранение изображений и их передачу. При наличии широкополосного доступа в Интернет передача больших объёмов информации не является серьёзной проблемой, однако в области развития современных информационных технологий Россия, к сожалению, отстаёт от западных стран. Доступ к современным технологиям связи сосредоточен в крупных городах. На периферии практически отсутствуют провайдеры, предлагающие доступ к широкополосному Интернету, поэтому идея создания высокоэффективного алгоритма сжатия изображений с потерями, лишённого недостатков способов группы JPEG, является весьма актуальной задачей, особенно в нашей стране. Разработка такого алгоритма позволила бы построить на его основе специальные форматы сжатия для применения в узких областях, например в здравоохранении, где предъявляются особые требования к качеству изображений.

Существует ли алгоритм сжатия цифровых изображений с потерями, альтернативный способам, разработанным группой JPEG? Да, существует. Фрактальный алгоритм сжатия изображений получил самое пристальное внимание со стороны мирового научного сообщества. Из всех способов компрессии изображений с потерями фрактальное сжатие наиболее точно передаёт контуры исходного изображения [54], что является его неоспоримым преимуществом перед алгоритмами группы JPEG. Если в форматах JPEG и JPEG 2000 сжатие достигается за счёт отбрасывания информации о мелких деталях (к которым относятся и контуры), то во фрактальном алгоритме -за счёт устранения избыточности, связанной с подобием между областями разного размера, так называемым самоподобием, существующим на реальных изображениях. Изображение разбивается на блоки, для каждого из которых находится подобная (после некоторых преобразований) область того же изображения большего размера. Сохраняются только коэффициенты преобразований подобия, объем которых значительно меньше объёма исходного изображения. С математической точки зрения изображение представляется в качестве неподвижной точки (аттрактора) системы сжимающих преобразований. Восстановление происходит путём итеративного выполнения всего набора сохранённых коэффициентов, начиная с произвольного стартового изображения, которое разбивается на блоки аналогично оригиналу.

Однако, несмотря на очевидные преимущества, фрактальное сжатие не лишено и недостатков, основной из которых заключается в необходимости провести большое количество сравнений различных областей изображения для отыскания «самых похожих». Это приводит к большим временным затратам на сжатие одного изображения, что является главным препятствием на пути практического применения фрактального алгоритма. Восстановление изображения происходит быстрее, чем в JPEG [2].

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

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

Предметом исследования является ускорение фрактального сжатия изображений.

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

1. Анализ существующих методов сжатия с потерями, их достоинств и недостатков.

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

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

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

Методы исследования. Для решения поставленных задач были использованы как экспериментальные, так и теоретические методы исследования. В работе использованы методы теории фракталов, теории систем итерируемых кусочно-определённых функций, теории сложности вычислений, теории вероятностей и математической статистики, аналитическое моделирование на ЭВМ и машинные расчёты в среде МаШСАГ).

Научная новнзиа диссертационной работы состоит в следующем:

1. Обосновано использование в адаптивных схемах разбиения изображения на ранговые блоки в качестве критерия перехода на другой уровень разбиения среднеквадратического отклонения (СКО) яркости пикселей рангов вместо среднеквадратической ошибки сравнения рангов и доменов. Использование нового критерия позволяет напрямую сформировать схему разбиения изображения на ранги, без выполнения многочисленных сравнений.

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

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

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

5. Рассмотрено распределение координат центров масс доменов на полярной плоскости с точки зрения их корреляции с рангами, то есть с точки зрения критерия оптимальности. Экспериментально показано, что хорошо коррелированные ранговые и доменные блоки могут находиться в пространственно разнесённых частях изображения. В результате разработаны новые алгоритмы классификации блоков изображения по полярному углу центров масс блоков. Использование классификации позволило ускорить фрактальное сжатие в 3-12 раз в зависимости от изображения по сравнению с полным перебором доменов без визуально заметной деградации качества восстановленного изображения. Таким образом, в результате применения модификаций, разработанных в настоящей работе, удалось ускорить фрактальное сжатие изображений в среднем на два порядка.

Личный вклад соискателя. Все основные научные результаты и выводы, изложенные в диссертации, получены автором самостоятельно.

Областью применения результатов диссертации выбрана медицина. В последние годы в рамках программы модернизации здравоохранения большое количество региональных больниц получило современное медицинское диагностическое оборудование, сохраняющее результаты в цифровом виде, но отсутствие широкополосного доступа в интернет и низкая пропускная способность каналов связи в периферийных областях страны не позволяют организовать телеконсультации и обмен медицинской информацией между региональными больницами и столичными медицинскими центрами, где квалификация врачей выше. Несмотря на высокую актуальность телемедицины для России, сдерживающим фактором её развития является недостаточное развитие современных технологий связи, обеспечивающих широкополосный доступ в Интернет, в удалённых регионах страны [10]. Поэтому особую актуальность приобретает разработка эффективного алгоритма сжатия медицинских изображений, который позволит осуществлять информационный обмен между периферийными клиниками и профильными медицинскими центрами в реальном времени. Создание такого алгоритма позволит спасать здоровье и жизни людей.

Медицинские изображения оцениваются врачами визуально. Человеческое зрение оценивает в первую очередь контуры изображения, их искажения наиболее чувствительны для глаз; информация о яркости имеет меньшее значение. Контуры внутренних органов представляют наибольший интерес для медиков [60]. В настоящее время для хранения медицинских изображений используются методы компрессии без потерь, что не позволяет достичь высоких коэффициентов сжатия. Применение алгоритмов, разработанных группой JPEG, предусмотрено стандартом на медицинские цифровые изображения DICOM 3, однако из-за вносимых ими искажений они практически не используются. Поэтому качественная передача информации о контурах фрактальным алгоритмом сжатия приобретает решающее значение в медицинских приложениях, а высокая степень компрессии, которую можно достичь с его помощью, позволяет значительно повысить эффективность использования пропускной способности каналов связи. Сжатие с потерями вообще и фрактальное сжатие в частности ещё не получило широкого распространения в медицине, чем обусловлена новизна данной работы.

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

JPEG. Сжатие видео можно осуществлять путём обработки каждого кадра как отдельного изображения подобно тому, как это делается в стандартах M-JPEG и M-JPEG 2000, что хорошо согласуется с медицинским стандартом DICOM и принципом работы систем видеонаблюдения.

Использование результатов работы. Основные теоретические положения и практические результаты диссертационной работы были рассмотрены и использованы:

- в обществе с ограниченной ответственностью «Форт-Телеком» при разработке комплекса контроля доступа и видеонаблюдения на необслуживаемых объектах телекоммуникационных сетей / нефтегазотранспортных систем / железнодорожного транспорта (акт внедрения);

- в открытом акционерном обществе «ТАКТ» при разработке новой платы передачи данных (в частности - изображений) в процессе развития универсальной аппаратуры гибкого мультиплексирования ОГМ-ЗОЕ (акт внедрения);

- в учебном процессе при чтении лекций по курсу «Системы документальной электросвязи» (акт внедрения).

Копии актов внедрения приведены в приложении Д.

Апробация результатов. Основные результаты диссертационной работы докладывались на научных конференциях: 6-й всероссийской научной конференции «Проблемы развития технологических систем государственной охраны, специальной связи и информации», Орёл, 2009г. [15]; 3-й всероссийской научной конференции «Проблемы создания и развития информационно-телекоммуникационной системы специального назначения», Орёл, 2003г. [17]; научной конференции профессорско-преподавательского, научного и инженерно-технического состава МТУСИ, Москва, 2003г. [30].

Публикации. По материалам диссертации опубликовано 6 печатных работ, из них: 3 статьи - в ведущих научных журналах, рекомендованных ВАК РФ [12, 14, 16], 2 публикации в сборниках научных трудов всероссийских конференций [15, 17] и 1 публикация в сборнике научных трудов научной конференции профессорско-преподавательского, научного и инженерно-технического состава МТУСИ [30].

Основные положения, выносимые на защиту:

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

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

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

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

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

6. Разработанные алгоритмы классификации блоков изображения по полярному углу центров масс блоков позволяют дополнительно ускорить процесс сжатия в 3-12 раз с визуально незаметным снижением качества по сравнению с полным перебором доменов.

Структура н объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка использованных источников и приложения. Общий объем работы - 180 страниц, из них 153 страницы - основное содержание, включая 45 рисунков и 18 таблиц, 19 страниц - приложение, 8 страниц - список использованных источников (123 наименования).

Заключение