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

• Илюшин, Сергей Валерьевич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Илюшин, Сергей Валерьевич

Введение.

Глава 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 наименования).

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

Заключение