Сжатие полутоновых изображений на основе контурных кодирования и интерполяции и дискретного вейвлет-преобразования

Размещено на http://www.allbest.ru/

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

УДК 004.627 + 004.932.2 + 621.397

Сжатие полутоновых изображений на основе контурных кодирования и интерполяции и дискретного вейвлет-преобразования

05.12.13 - Системы, сети и устройства телекоммуникаций

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

Самохвалов Антон Витальевич

Ижевск 2009

Работа выполнена на кафедре «Интеллектуальные информационные технологии» в ГОУ ВПО «Ижевский государственный технический университет» (ГОУ ВПО «ИжГТУ», г. Ижевск).

Научный руководитель: заслуженный изобретатель Российской Федерации, доктор технических наук, профессор Лялин В.Е.

Официальные оппоненты:

доктор технических наук, профессор Сметанин А.М. (ГОУ ВПО «ИжГТУ», г. Ижевск);

кандидат технических наук Кузнецов А.Г. (Межрегиональный филиал сотовой связи ОАО «Уралсвязьинформ», г. Пермь).

Ведущая организация: ГОУ ВПО «Вятский государственный университет» (ГОУ ВПО «ВятГУ», г. Киров).

Защита состоится 26 ноября 2009 г. в 16-00 часов на заседании диссертационного совета Д 212.065.06 в ИжГТУ по адресу: 426069, г. Ижевск, ул. Студенческая, 7.

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

С диссертацией можно ознакомиться в библиотеке университета. С авторефератом можно ознакомиться на официальном сайте ИжГТУ: www.istu.ru.

Автореферат разослан 26 октября 2009 г.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент В.Н. Сяктерев

сжатие графический цифровой полутоновый

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

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

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

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

Разработке эффективных представлений и моделей изображений, методов их обработки и кодирования уделено большое внимание в работах отечественных и зарубежных ученых: Бонгарда М.М., Вудса Р.Е., Гонсалеса Р.С., Журавлева Ю.И., Ковалевского В.А., Лебедева Д.С., Файна В.С., Цуккермана И.И., Ярославского Л.П., Нарасимхана Р., Павлидиса Т., Прэтта У., Розенфельда А., Стокхэма Т., Сэломона Д., Фримена Х., Фу К., Харалика Р.М., Эддинса С.Л. и др.

На сегодняшний день в области сжатия изображений существует ряд проблем. При высокой степени компрессии изображений современными наиболее мощными и популярными стандартами компрессии наблюдается значительное ухудшение визуального качества изображения, которое проявляется либо в виде «блочности» изображения и эффекта ореола вокруг контурных линий (JPEG), либо в виде сильного размытия контуров изображения (JPEG2000). Сохранение качественного отображения контуров на изображении имеет важное значение практически для всех типов изображений, в особенности для изображений, используемых при цифровой обработке геологических карт, геофизических и гидродинамических моделей месторождений полезных ископаемых.

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

Область исследования. Диссертационная работа выполнена в соответствии с пунктами «4. Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации», «5. Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации», «12. Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» паспорта специальности 05.13.01 - «Системный анализ, управление и обработка информации (в науке и технике)» и пунктами «2. Исследование процессов генерации, представления, передачи, хранения и отображения аналоговой, цифровой, видео-, аудио- и мультимедиаинформации; разработка рекомендаций по совершенствованию и созданию новых соответствующих алгоритмов и процедур», «12. Разработка методов эффективного использования сетей, систем и устройств телекоммуникаций в различных отраслях народного хозяйства» паспорта специальности 05.12.13 - «Системы, сети и устройства телекоммуникаций».

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

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

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

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

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

- исследовать алгоритмы нахождения и утолщения контурных линий на полутоновом изображении для разработки методики контурного кодирования полутонового изображения;

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

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

-исследовать возможность применения дискретного вейвлет-преобразования (ДВП) для компрессии контурной информации полутонового изображения и определить оптимальные параметры ДВП для решения данной задачи;

- провести экспериментальные исследования, направленные на определение наиболее эффективного метода компрессии коэффициентов ДВП контурной информации изображения;

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

Методы исследования. В диссертационной работе применялись теоретические и экспериментальные методы исследования.

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

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

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

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

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

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

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

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

- методика контурного кодирования полутоновых изображений, основанная на детекторе контуров, утолщении контурных линий и маскировании исходного изображения;

- метод и алгоритм контурной билинейной интерполяции, осуществляющий восстановление неконтурной информации на полутоновом изображении;

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

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

- экспериментальные исследования разработанных средств и методов, а также сравнение эффективности МКСИ и JPEG2000 при сжатии полутоновых изображений.

Научная новизна результатов диссертационного исследования, полученных лично автором, заключается в следующем:

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

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

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

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

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

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

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

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

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

Полученные результаты использованы в учебном процессе ГОУ ВПО «ИжГТУ» при изучении дисциплин «Компьютерная графика», «Интерактивные графические системы», «Кодирование и цифровая обработка информации».

Апробация работы. Основные положения и результаты диссертации докладывались на российских и международных научно-технических конференциях и симпозиумах: Российской научно-технической конференции «Приборостроение в XXI веке. Интеграция науки, образования и производства» (Ижевск, 2006); Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (Таганрог, 2007); Международной научно-технической конференции «Информационные технологии в инновационных проектах» (Ижевск, 2007); 34-й и 35-й Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (Украина, Крым, Ялта-Гурзуф, 2007, 2008); Международном симпозиуме «Надежность и качество» (Пенза, 2008); IX Международной научно-технической конференции «Искусственный интеллект - 2008; Интеллектуальные системы - 2008» (пос. Кацивели, АР Крым, Украина, 2008).

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

Структура диссертационной работы. Диссертация содержит введение, 4 главы и заключение, изложенные на 165 стр. машинописного текста. В работу включены 68 рис., 11 табл., список литературы из 129 наименований. В приложении представлен акт об использовании результатов работы.

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

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

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

а

б

Рис. 1. а) Общая модель системы сжатия; б) Модель кодера источника

Рис. 2. Эффект размытия контуров при сильном сжатии (JPEG2000)

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

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

, ,

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

а

б

Рис. 3. Структурная схема контурного метода сжатия изображений: а) компрессия; б) декомпрессия

В главе проанализирован механизм обнаружения контурных линий на изображении, основанный на первой и второй производных сигнала изображения. Отмечено, что данный механизм очень чувствителен к шуму, присутствующему в сигнале, в основном, за счет чувствительности второй производной к изменению сигнала. Сопоставлены способы обнаружения контурных линий на изображении, осуществляемые с помощью детекторов Робертса, Превитта, Собела, Канни и детектора «лапласиан гауссиана» (ЛГ).

Рис. 4. Блок контурного кодирования

Проведены сравнительные эксперименты, направленные на выбор оптимального детектора контуров из рассмотренных. Установлено, что детектор Канни оказался самым точным детектором выделения основных контуров изображения (рис.5).

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

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

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

Таблица 1

Временные затраты детекторов контуров

Детектор	Коэффициент временных затрат
Робертса	1,0
Превитта	1,1
Собела	1,1
ЛГ	1,8
Канни	3,5

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

		0	1	0
		1	1	1
		0	1	0

Рис.5. Выбор детектора контуров

Исходное изображение Детектор Собела

Детектор Превитта Детектор Робертса

Детектор ЛГ Детектор Канни

Рис. 6. Структурообразующий элемент

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

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

Ключевая идея билинейной интерполяции заключается в том, чтобы провести обычную линейную интерполяцию сначала в направлении одной оси, затем - другой. Точки Q₁₁, Q₁₂, Q₂₁, Q₂₂ (рис. 8) представляют собой известные значения яркости пикселей. Значение яркости в точке P вычисляется следующим образом:

,

,

.

Установлено, что использование алгоритма классической билинейной интерполяции в случае интерполяции маскированного изображения в чистом виде неприемлемо, так как в случае интерполяции области, окаймленной контурами, опорными точками не являются некие заранее известные диагональные точки Q₁₁, Q₁₂, Q₂₁, Q₂₂.

Для упрощения предложено пустую область рассматривать как квадратный элемент, граничные пиксели которого являются контурными (рис. 9).

Рис. 7. Иллюстрация маскирования изображений: слева - исходное изображение «Sweden», справа - маскированное изображение

Рис. 8. Классическая билинейная интерполяция

Рис. 9. Контурная билинейная интерполяция

Опорные точки предложено определять по принципу «четырех соседей» следующим образом: 1 - ближайший верхний контурный пиксель (по оси X), 2 - ближайший правый контурный пиксель (по оси Y), 3 - ближайший нижний контурный пиксель (по оси X), 4 - ближайший левый контурный пиксель (по оси Y).

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

.

Так как , следовательно , а если учесть, что , то . Таким образом, расстояние между точками 2 и P, 3 и P, 4 и P определяются следующим образом:

,

,

.

Чем меньше значение евклидова расстояния от интерполируемого пикселя P до рассматриваемого пикселя, тем ближе они находятся друг к другу. Ближайшим контурным пикселем в одном из четырех направлений (север, юг, запад, восток) является такой пиксель, который удовлетворяет условиям: 1) пиксель принадлежит множеству контурных пикселей, 2) пиксель лежит на рассматриваемом направлении, 3) евклидово расстояние h от рассматриваемого пикселя до точки P меньше расстояний всех других пикселей, также удовлетворяющих предыдущим условиям (1 и 2) (рис. 10).

Рис.10. Нахождение опорных точек

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

, (1)

где - значение яркости опорного пикселя 1, - значение яркости опорного пикселя 2, - значение яркости опорного пикселя 3, - значение яркости опорного пикселя 4, - весовой коэффициент i-го опорного пикселя.

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

Следовательно, весовые коэффициенты опорных пикселей можно найти по формулам

,

,

,

,

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

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

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

, , , ,(2)

где ; ; - коэффициент расстояния по оси 2-4 («запад-восток»); - коэффициент расстояния по оси 1-3 («север-юг») (рис. 9).

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

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

Таблица 2

Сравнение стандартов сжатия на двухуровневых контурных изображениях

Стандарт сжатия	Размер файла контурного изображения, байт
	«Barbara»	«Iris»	«Propeller»	«Sweden»
BMP (без сжатия)	328304	456626	818504	456620
TIFF Group 3	300093	376954	229060	190224
TIFF Group 4	174462	307065	126985	95602
7-Zip	116630	133531	72156	65873
YBS	133275	168923	84458	80656
RAR	136766	172796	87961	80170
JBIG	65449	75334	25693	32153

а

б

Рис. 11. а) Блок фильтров; б) Спектральные характеристики разложения вейвлет-пакета

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

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

Таблица 3

Доли обнуляемых коэффициентов вейвлет-преобразований (порог обнуления - 5)

Тип вейвлета	Первый тестовый блок	Второй тестовый блок	Третий тестовый блок	Четвертый тестовый блок
Вейвлет Хаара	6,4%	8,0%	20,3%	15,6%
Вейвлет Добеши 4	13,7%	12,7%	19,0%	16,9%
Вейвлет Добеши 8	13,1%	10,2%	21,5%	18,5%
Вейвлет Койфлет 6	14,9%	13,4%	22,3%	16,4%
Вейвлет Симлет 12	12,8%	11,5%	22,7%	20,0%
Вейвлет биортогональный 5-3	15,5%	18,1%	23,1%	22,9%
Вейвлет биортогональный 8-4	20,0%	16,7%	27,1%	28,0%
Вейвлет биортогональный 16-4	19,0%	14,4%	26,7%	24,6%
Вейвлет биортогональный 9-7	12,7%	12,3%	24,1%	19,2%
Вейвлет биортогональный 17-11	13,2%	12,8%	22,9%	19,6%

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



Масштабирующая функция анализа

Масштабирующая функция синтеза

Вейвлет-функция анализа Вейвлет-функция синтеза

Рис. 12. Параметры биортогонального вейвлета 8-4

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

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

Таблица 4

Влияние уровня разложения на эффективность вейвлет-преобразования

Уровень вейвлет- -преобразования	Порог обнуления - 5	Порог обнуления - 10	Порог обнуления - 20
	ДОК	с.к.о. ОВС	ДОК	с.к.о. ОВС	ДОК	с.к.о. ОВС
1	26,6%	1,5535	40,3%	3,8194	48,3%	6,5670
2	31,9%	1,6268	48,5%	4,0617	61,5%	7,4920
3	34,1%	1,6633	52,4%	4,1559	66,5%	7,6521
4	34,8%	1,6656	53,5%	4,1821	68,1%	7,7229
5	34,9%	1,6728	53,5%	4,1829	68,1%	7,7234
6	34,9%	1,6728	53,5%	4,1829	68,1%	7,7236

По результатам эксперимента можно констатировать, что биортогональный вейвлет 8-4 (рис.12) лучше других концентрирует энергию в низкочастотных коэффициентах, так как доля обнуляемых высокочастотных коэффициентов для трех тестовых блоков у него самая высокая. Для одного тестового блока данный вейвлет занял второе место по концентрации энергии, уступив биортогональному вейвлету 5-3.

Таблица 5

Влияние порога обнуления на долю обнуляемых коэффициентов

Порог обнуления	ДОК	с.к.о. ОВС
0	3,2%	0,3149
1	10,3%	0,5058
2	16,5%	0,8615
3	21,0%	1,2185
4	25,4%	1,6709
5	29,2%	2,1479
6	32,2%	2,5537
7	35,3%	2,9753
8	38,2%	3,5903
10	42,6%	4,4968
12	46,4%	5,3805
14	49,9%	6,3294
20	57,9%	8,9172

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

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

Таблица 6

Влияние уровня квантования на ошибку восстановления

Уровень квантования	с.к.о. ОВС
1	0,3149
2	0,6180
3	0,8979
4	1,2263
5	1,5498
6	1,7940
7	1,9925
8	2,2258
9	2,5124
10	2,9810

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

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

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

Сравнение ошибок восстановления сигнала при квантовании коэффициентов ДВП и при установке порога обнуления представлено на рис. 13. На рис. 14 приведены гистограммы значений высокочастотных коэффициентов, нормированных к положительным числам (128 соответствует коэффициентам ДВП равным нулю), при разных уровнях квантования. При увеличении уровня квантования гистограммы сужаются, а количество нулевых коэффициентов увеличивается.

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



Порог обнуления - 3 Порог обнуления - 7

Уровень квантования - 4 Уровень квантования - 10

Рис. 13. Ошибки восстановления сигнала при обнулении и квантовании коэффициентов

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

Самый малый размер файла, содержащего сжатые коэффициенты ДВП, обеспечивает стандарт 7-Zip, основанный на методе PPMII. Относительная неэффективность общепринятого метода КДС+АК (кодирование длин серий и арифметическое кодирование) объясняется специфической структурой данных маскированного изображения, которые и подвергались ДВП.

Уровень квантования-2 Уровень квантования-4

Уровень квантования-8 Уровень квантования-14

Рис. 14. Гистограммы значений высокочастотных коэффициентов при разных уровнях квантования

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

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



Таблица 7

Сравнение методов сжатия коэффициентов ДВП

Метод сжатия	Размер файла, байт
	Уровень квантования - 4	Уровень квантования - 10	Уровень квантования - 18
без сжатия	371125	371124	371127
7-Zip (PPMII)	162991	130890	112891
YBS (ПБУ+ДК)	198680	161685	139613
КДС+АК	256226	222156	200272

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

обработки данных: сегментация изображения - обнаружение контуров на полутоновом изображении (программный модуль CannyDetect); морфологическая обработка изображения - дилатация контурного двухуровневого изображения (Dilatation); маскирование исходного изображения и построчное сканирование маскированного изображения (MaskScan); сжатие двухуровневого контурного изображения (JbigCompress); трансформационное преобразование - вейвлет-преобразование данных отсканированного маскированного изображения (WaveCode); компрессия одномерного массива коэффициентов ДВП (PPMCode); компоновка файла сжатого полутонового изображения (FileConstr); разбиение единого файла сжатого полутонового изображения на две части - сжатое двухуровневое контурное изображение и сжатые коэффициенты вейвлет-преобразования (FileDeconstr); декомпрессия сжатых коэффициентов одномерного дискретного вейвлет-преобразования (PPMDecode); декомпрессия двухуровневого контурного изображения (JbigDecomp); обратное дискретное вейвлет-преобразование данных отсканированного маскированного изображения (WaveDecode); реконструкция маскированного полутонового изображения (MaskRecon); контурная билинейная интерполяция с двунаправленным взвешиванием опорных точек (ContInterp).

Рис. 15. Технологическая схема обработки информации при сжатии изображений МКСИ: ПИ - полутоновое изображение, ВПИ - восстановленное полутоновое изображение

Программный модуль MaskRecon выполняет функцию реконструкции маскированного полутонового изображения на основе отсканированного маскированного изображения с помощью контурного изображения. Так как контурное изображение сохранялось в исходном до утолщения виде, в данном программном модуле осуществляется предварительное утолщение контурного изображения. Для реконструкции маскированного изображения также необходимо сделать копию утолщенного контурного изображения. Далее в процессе построчного сканирования копии утолщенного контурного изображения анализируется каждый пиксель. Если значение анализируемого пикселя контурного изображения равно «1» (то есть, данный пиксель относится к множеству контурных и околоконтурных пикселей), то его значение меняется на значение из массива отсканированного маскированного изображения, после чего осуществляется поступательное продвижение по массиву отсканированного маскированного изображения. Если значение анализируемого пикселя контурного изображения равно «0», то оно не претерпевает никаких изменений. Построчное сканирование осуществляется до тех пор, пока не будет проанализирован последний пиксель контурного изображения.

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

Программные модули были реализованы в пакете прикладных программ для решения задач технических вычислений Matlab.

Рис.16. Алгоритм контурной билинейной интерполяции изображений



В табл. 8-9 представлены результаты экспериментального исследования, направленного на сравнение эффективностей JPEG 2000 и МКСИ. Анализ табл. 8 показал, что МКСИ наиболее эффективен при сжатии низкочастотных изображений. При сжатии высокочастотного изображения среднеквадратическое отклонение ошибок восстановления изображения МКСИ выше, чем JPEG 2000 для каждого уровня квантования коэффициентов ДВП. Это объясняется тем, что при МКСИ высокочастотных изображений коэффициенты сжатия (КС) значительно меньше, чем при обработке низкочастотных изображений. А при низких степенях компрессии JPEG 2000 сжимает изображения качественно, с минимальными ошибками восстановления изображений.

Таблица 8

Сравнение ошибок восстановления изображений JPEG2000 и МКСИ

Уровень квантования КДВП	Низкочастотное изображение	Среднечастотное изображение	Высокочастотное изображение
	КС	с.к.о. ОВС	КС	с.к.о. ОВС	КС	с.к.о. ОВС
		МКСИ	JPEG2000		МКСИ	JPEG2000		МКСИ	JPEG2000
4	38,0	1,1595	1,9945	29,8	1,1631	1,5716	22,3	1,1542	1,2118
6	40,5	1,3727	2,1783	32,2	1,3762	1,7532	24,8	1,3663	1,3967
8	41,4	1,6265	2,3097	33,5	1,6321	1,8867	26,2	1,6202	1,5281
10	43,1	1,8462	2,4518	34,9	1,8499	2,0227	27,5	1,8389	1,6701
14	45,2	2,4927	2,5974	37,0	2,4953	2,1749	29,7	2,4861	1,8147
18	46,8	3,0433	2,9796	38,7	3,0468	2,5465	31,2	3,0370	2,1969

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

В табл. 9 представлен сравнительный анализ ошибок восстановления контурной информации JPEG 2000 и МКСИ, который показал, что разработанный автором метод контурного сжатия значительно лучше (в разы) сохраняет столь важную структурную контурную и околоконтурную составляющую изображения.

Таблица 9

Сравнение ошибок восстановления контурной информации JPEG2000 и МКСИ

Уровень квантования КДВП	Среднеквадратическое отклонение ошибки восстановления сигнала
	Толщина контурной зоны - 3	Толщина контурной зоны - 5	Толщина контурной зоны - 7
	МКСИ	JPEG2000	МКСИ	JPEG2000	МКСИ	JPEG2000
4	1,1897	5,6991	1,1585	5,0658	1,1228	4,6517
6	1,6365	6,5467	1,5848	5,7191	1,5804	5,2107
8	2,3128	7,1394	2,1756	6,1840	2,0812	5,6013
10	2,5812	7,6174	2,4657	6,5617	2,3562	5,9338
14	3,7996	7,9767	3,5545	6,8815	3,3354	6,2327
18	4,9543	8,8300	4,5894	7,5270	4,2643	6,7717

На рис. 17 представлены увеличенные фрагменты исходных низкочастотного (левый столбец) и среднечастотного (правый столбец) изображений, а также те же фрагменты, сжатые МКСИ и JPEG2000 с одинаковыми коэффициентами компрессии, соответствующими уровню квантования коэффициентов ДВП МКСИ равного 4. Визуальное качество изображений было оценено экспертом с помощью шкалы {-3, -2, -1, 0, 1, 2, 3}, отражающей, соответственно, субъективные оценки рейтинга: {значительно хуже, хуже, слегка хуже, одинаково, слегка лучше, лучше, значительно лучше}. Данная система оценивания была описана в первой главе данной диссертационной работы.

С точки зрения визуального качества низкочастотное изображение JPEG 2000 имеет очень сильное размытие контуров (субъективная оценка СО = -3), среднечастотное изображение JPEG 2000 имеет умеренное размытие контуров и ореол около контуров (субъективная оценка СО = -2). Изображения, сжатые разработанным МКСИ, в обоих случаях имеют четкие контуры, что обусловлено сохранением структурной контурной информации изображения (CО = -1 балла). На обоих изображениях присутствуют слабые неоднородности областей изображения, которые подвергались интерполированию. Однако эти неоднородности менее заметны и неприятны глазу, нежели дефекты при сжатии JPEG 2000.

На рис. 18 предста...