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

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

□03483781

УДК 004.627 + 004.932.2 + 621.397

САМОХВАЛОВ Антон Витальевич

СЖАТИЕ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИИ НА ОСНОВЕ КОНТУРНЫХ КОДИРОВАНИЯ И ИНТЕРПОЛЯЦИИ И ДИСКРЕТНОГО ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ

Специальности:

05.13.01 - Системный анализ, управление и обработка информации (в науке и технике); 05.12.13 - Системы, сети и устройства телекоммуникаций

\ 9 НОЯ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Ижевск-2009

003483781

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

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

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

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

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

кандидат технических наук Кузнецов А.Г.

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

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

Защита состоится 26 ноября 2009 г. в_часов

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

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

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

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

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

В.Н. Сяктерев

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

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

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

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

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

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

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

Область исследования. Диссертационная работа выполнена в соответствии

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

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

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

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

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

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

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

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

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

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

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

ной информации изображения;

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

Матриц |||ч>1Л||Л»4пиа Г? т^^^лт^пНАиилм пойпта пптмткгпплт.

"'V " МД"- .»^МЧ-^и»-»»*«««! Ч риии 1 и 1111» I. ■ 1 «Л II «М

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- предложена технолошческая схема обработки информации доя метода контур-

11СГО С/КаТЯЯ (ГЗСбрЗ^КСши', обсСиб-й^ВшСшДл ПОЛ^'ЧСНйС На ВЫХОДС ПОССIапОБЛСНгТОТТ>

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

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

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

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

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

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

Дх.У) Кодер Канал | Декодер ГМ

связи |

а)

Международном симпозиуме «Надежность и качество» (Пенза, 2008); IX Международной научно-технической конференции «Искусственный интеллект - 2008; Интеллектуальные системы 2008» (пос. Кацивели, АР Крым, Украина, 2008).

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

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

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

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

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

изображений, представляющих собой особый тип данных. Рассмотрены критерии верности восстановления изображений, а также виды избыточности данных в изображениях: кодовая, межэлементная, визуальная. На рис.1, представлена общая модель сжатия изображений. Отмечено, что этап трансформационного кодирования (дискретное преобразование Фурье, ДВП и пр.) - важнейшая составляющая современных систем компрессии изображений как с потерями, так и без них. Рассмотрены самые популярные и самые мощные на сегодняшний день стандарты сжатия изображений: JPEG, JPEG!000. Оба стандарта при высоких степенях компрессии приводят к сильному размытию контуров на изображении, что негативно воспринимается человеческим зрением (рис.2).

А*,у) р

Поеобразователь —>* Квантователь —> символов

Канал связи

Канал Декодер Обратный к*, у)

связи символов преобразователь

в)

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

Шт

îsSSÎT'

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

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

классификация изображений с учетом существующих.

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

гтппАттог! ио 1Лип Л

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

Маска {контурное изображение) б)

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

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

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

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

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

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

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

Таблица 1.

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

Летектпк

Рпйептса

Собела

Каннн

Коэффициент ввемеккых затпат

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

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

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

иымюмйиШИЩЕйДВдвш ■ЙИЯНИШММВ

Детектор ЛГ Детектор Канни ТерПОЛЯЦИИ В ЧИСТОМ виде не ПОДХОДЯТ

Рис.5. Выбор детектора контуров для контурной интерполяции изобра-

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

Ключевая идея билинейной интерполяций заключается в том, чтобы провести обычную линейную интерполяцию сначала в направлении одной оси,, затем - другой. Точки 0,2, <221, 0.22 (рис. 8) представляют собой известные значения яркости- пикселей. Значение яркости в точке Р вычисляется следующим образом:

0 1 0

1 1 I 1 1

0 1 0

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

.Уг~У

Уг-Ух

Ур-Уг

У2 УI

ЛЛ) = ^/(й:) - 1

X. X, X.

Установлено, что использование алгоритма классической билинейной интерполяций в случае интерполяции маскированного изображения в чистом виде неприемлемо, так как в случае интерполяции области, окаймленной контурами, опорными точками не являются некие заранее известные диагональные точки Оц, 01>, б71,022.

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

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

точки Р, равно Нр] = ^ур -у,} . Так как ур= у,, следовательно

Г, 3"

кр, = — х,^ , а если учесть, что хр>х1, то = хо-хг. Таким образом, расстояние между точками 2 я Р, 3 и Р, 4 и Р определяются следующим образом:

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

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

1 1 1 Tl 1 - 1

- \р -

_____ г

II 1 1зМ - 1

Рис. 8. Классическая Рис. 9. Когпуриая

билинейная интерполяция билинейная интерполяция

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

ДР) = /(l)w, + f(l)w2 + /(3)w3 + /(4)w4, 2>, = 1, (1)

где /(i) = f(l,yF) - значение яркости опорного пикселя i, /(2) = f{xt,n) - значение яркости опорного пикселя 2, /(3) = f(m,yp) - значение яркости опорного пикселя 3, /(4) = f{x, 1) - значение яркости опорного пикселя 4, w, - весовой коэффициент г'-го опорного пикселя.

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

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

формулам ^l^-D-fe-DJ^ !("-')-("

2 т -1 2 й, 2 п -1 2 hy

1 («-!)-(»-*,)ajdk, .^("-ч-^-ЦН,где h _

3 2 т-\ 2 h, 4 2 п-1 2 hy '

евклидово расстояние между опорными точками 1 и 3 (опорные точки по направлению «север-юг»), hy - евклидово расстояние между опорными точками 2 и 4 (опорные точки по направлению «запад-восток»), hpl - евкпвдово расстояние от точки Р

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

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

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

=kK~hJK. =кК-К*/К> w3 = кКЛ.¡К> = кК-Кг/К. (2) где hmnn = mm{hpl,hp,); hmm2, =mm(hp2,hj; kf^^h^Jih^+h^) - коэффициент расстояния по оси 2-4 («запад-восток»); fc/г,, = 1 - kh7i — коэффициент расстояния по оси 1-3 («север-юг») (рис. 9).

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

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

Таблица 2 невых изображений с Сравнение стандартов сжатия на двухуровневых целью определения

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

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

контурных изображениях

Стандарт сжатия Размер файла контурного изображения, байт

«Barbara» «Iris» «Propeller» «Sweden»

BMP (беа сжатия) 32830 45662 81850 45662

TIFF Group 3 30009 37695 22906 19022

TIFF Group 4 ' 17446 30706 12698 9560

7-Zip 11663 13353 7215 6587

YBS 13327 16892 8445 8065

RAR 13676 17279 8796 8017

JBIG 6544 7533 2569 3215

H M")

m-

|«И1

| hfjn) j —»2 -| ft,(л) )——» 3

а)

V» V

б)

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

. построчного сканирования, отбрасывая при этом пустые области.

Результатом сканирования является одномерный сигнал, который подвергается вейвлет-преобразованию. При сжатии данных предложено использовать субполосное вейвлет-кодирование, схема и спектральные характеристики кото-роге представлены на рис. 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%

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

НЧ-фильтр анализа ВЧ-фильтр анализа НЧ-фильтр синтеза

1,

0.5

ВЧ-фильтр синтеза 1 ■

0,5

Т 5"

■Г' 1

I I

.1.1.

0,51

о!»

«"1.......1

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

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

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

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

Рис. 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 Влияние порога обнуления на

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

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

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

долю обнуляемых кю( фщиентов

Порог обнуления ДОК с.к.о. ОВС

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

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

Таблица 6 в табл. 5 представлены результаты экспе-

Влняние уровня квантования на ,

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

Уровень с.к.0. ОВГ

квантования

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

фициентов и стандартного отклонения ошиоки

ПОолтогIлппотУтг«г г»т»-г"1ТТ/-1 гтп гглтт «п>>1тт тл^ т».л.

4/1-11 пш1а ирп раахшхл у рисилл пи'

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

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

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

-30 -20 -10 0 10 20 30 40 отклонение (ошибка восстановлен ия)

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

-30 -20 -10 0 10 20 30 40 отклонение (ошибка восстановления)

Порог обнуления - 7 .г"!_

-20 -15 -10 -5 О 5 10 15 20 25 отклонение (ошибка еоссгенониеним)

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

А I

-20 -15 -10-5 О 5 10 15 20 25 отклонение (ошибка восстановлен,«)

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

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

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

количество

5000

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

количество

13000 г

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

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

После квантования высокочастотных коэффициентов ДВП была осуществ-

ттлттл тю» тполпигг т/"«"»тл ттт1'»^лгт1пт|от?тт IV тохг т* от тллтгл1т0лт/уг1ггг IV г/'Л^ЛлЛ^тттютттлп ТТТЭТТ

Л^ГШ IVиIV 1<.и\ ЛЛ ишишл; "Ю^ 1 11Ш1Л ХЧШ^/^ПЦЛ VI I1VI) / I.

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

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

количество

значение коэффициента Уровень квантования-8

значение коэффициента Уровень квантования-14

значение коэффицне!

значение коэффициента

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

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

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

Таблица 7 ные на контекстном модели/-- ал. 1ГОТТ ровании, что и доказывает

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

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

Метод сжатия Размер файла, байт

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

без сжатия 37112 37112 37112

7.Zip (РРМ11) 16299 13089 11289

УВв (ПБУ+ДК) 19868 16168 13961

КДС+АК 25622 22215 20027

пи

Контурное кодирование

И

MaskScan

CannyDetect

Компрессия

комплекса программ, обеспечивающих выполнение всех необходимых процедур

обработки данных: сегментация изображения -обнаружение контуров на

Контурная интерполяция

Со ntlnterp

MaskRecon

WaveCode —J PFMCcda

»

JblgCompnss FileConstr

канал передачи информации

Декомпрессия

JbigDecomp FHeDeconsfr

i

WaveDecode PPM Décodé

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

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

жения (МаэкБсап)-, сжатие двухуровневого контурного изображения (ЗЫ%Сот-ргт); трансформационное преобразование - вейвлет-преобразование данных отсканированного маскированного изображения (\VaveCodey, компрессия одномерного массива коэффициентов ДВП (РРМСос1е)\ компоновка файла

сжатого полутонового изображения (РИеСогМг); разбиение единого файла сжатого полутонового изображения на две части - сжатое двухуровневое контурное изображение и сжатые коэффициенты вейвлет-преобразования {РИейе-соШг)\ декомпрессия сжатых коэффициентов одномерного дискретного вейвлет-преобразования (РРАЮесоЛе)-, декомпрессия двухуровневого контурного изображения {JbigDecomp)^, обратное дискретное вейвлет-преобразование данных отсканированного маскированного изображения (У¥агеОесос1е); реконструкция маскированного полутонового изображения (Ма$Шесоп)\ контурная билинейная Рис. 16. Алгоритм реконструкции интерполяция с двунаправленным взве-маскированногб изображения шиванием опорных точек (СопПгЛегр). Программный модуль МазкЯесоп выполняет функцию реконструкции маскированного полутонового изображения на основе отсканированного маскированного изображения с помощью контурного изображения. Так как контурное изображение сохранялось в исходном до утолщения виде, в данном программном модуле осуществляется предварительное утолщение контурного изображения. Для реконструкции маскированного изображения также необходимо сделать копию утолщенного контурного изображения.

Реконструкция маскированного изображения осуществляется следующим обра-

0

зом (рис. 16): в процессе построчного сканирования копии утолщенного контурного изображения /ки анализируется каждый пиксель.

Если значение анализируемого пикселя контурного изображения равно «1» (то есть, данный пиксель относится к множеству контурных и околоконтурных пикселей), то его значение меняется на значение из массива отсканированного маскированного изображения ОМИ, на которое указывает счетчик /. После этого значение счетчика г увеличивается на единицу, то есть осуществляется поступательное продвижение по массиву отсканированного маскированного изображения. В самом начале счетчик i был установлен в значение «1», то есть он указывал на начало массива. Если значение анализируемого пикселя контурного изображения равно «О», то оно не претерпевает никаких изменений. Построчное сканирование осуществляется до тех пор, пока не будет проанализирован последний пиксель контурного изображения.

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

Таблица 8

Сравнение эффективности ЗРЕаООО и МКСИ

т

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

Уровень квантования КДВП Низкочастотное изображение Средпсчастотное изображение Высокочастотное изображение

КС С.К.О. ОВС КС С.К.О. ОВС КС С.К.О. ОВС

МКСИ Л>Е(Ш0 МКСИ 1РЕС2т МКСИ л>Еат

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

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

Исходное изображение, СО = О

ДРЕС 2000, СО = -3

МКСИ, СО = -1 МКСИ. СО -1 ~

Рис. ¡8. Сравнение визуального качества изображений

— _ н шдрадряз Лучше всего МКСИ

' на : ^ ^ьос^^.-

Рис. 19. Июбр&жшия ошибок восстйновл6кия° л) для ковлеиия у вы~

.1РЕС» 2000, б) для МКСИ шс для каждого уровня

квантования коэффициентов ДВП. Это объясняется тем, что при применении МКСИ к высокочастотным изображениям достигаемые коэффициенты сжатия

правленного на сравнение эффективности самого мощного на сегодня стандарта сжатия ,/Р£С2000 и предложенного метода контурного сжатия изображений.

(КС) значительно меньше, чем при применении МКСИ к низкочастотным изображениям, а при низких степенях компрессии JPEG2000 сжимает изображения качественно, с малыми ошибками восстановления изображений.

Установлена следующая зависимость: чем более высокочастотно исходное изображение, тем меньше по значению коэффициенты сжатия при одних и тех же уровнях квантования коэффициентов ДВП. Данное явление связано с тем фактом, что чем более высокочастотно исходное изображение, тем больше контурных линий будет выделено при контурном кодировании, что приведет одновременно к меньшему сжатию маски, и к увеличению множества используемых контурных и околоконтурных пикселей. Количество контурных и околоконтурных пикселей прямо пропорционально сохраняемому объему данных и, следовательно, обратно пропорционально степени сжатая данного изображения методом МКСИ. На рис. 18 представлены увеличенные фрагменты исходных низкочастотного (левый столбец) и среднечастотного (правый столбец) изображений, а также те же фрагменты, сжатые МКСИ и JPEG2000 с одинаковыми коэффициентами сжатия (уровень квантования коэффициентов ДВП МКСИ = 4). Визуальное качество изображений было оценено экспертом с помощью шкалы {-3, -2, -1, 0, 1, 2, 3}, отражающей, соответственно, субъективные оценки рейтинга: {значительно хуже, хуже, слегка хуже, одинаково, слегка лучше, лучше, значительно лучше}. С точки зрения визуального качества изображения, сжатые стандартом JPEG 2000, в случае низкочастотного изображения имеют очень сильное размытие контуров (субъективная оценка СО = -3), в случае среднечастотного — умеренное размытие контуров и «ореол» около контуров (СО = -2). Изображения, сжатые разработанным МКСИ, в обоих случаях имеют четкие контуры. На обоих изображениях присутствуют слабые неоднородности тех областей изображения, которые подвергались интерполированию. Однако эти неоднородности гораздо менее заметны и менее неприятны глазу, нежели дефекты при сжатии JPEG2000. СО = -1 для обоих изображений. На рис. 19 представлены изображения ошибок восстановления для обоих рассматриваемых методов. Так как ошибки восстановления имеют и отрицательные, и положительные значения, а их величины достаточно незначительны по сравнению с диапазоном яркости полутонового изображения, ошибки были приведены к средней линии яркости (256/2=128), а их значения увеличены для более удобного восприятия. Чем больше положительная ошибка в конкретном пикселе восстановленного изображения, тем цвет пикселя изображения ошибок ближе к белому, чем больше отрицательная ошибка - тем цвет пикселя ближе к черному. Серый цвет пикселей соответствует небольшому значению ошибки или ее отсутствию вовсе. Легко заметить, что основные ошибки на изображении JPEG 2000 сконцентрированы около контуров, а ошибки на изображении МКСИ более равномерно распределены по всей плоскости изображения.

Для сравнения количества времени, затрачиваемого на работу МКСИ и JPEG 2000, в среде Matlàb были реализованы основные блоки стандарта сжатия изображений JPEG2000. На этапе компрессии МКСИ выполняется на 40% медленнее, а на этапе декомпрессии на 20% медленнее, чем JPEG2000 на соответствующих этапах сжатия. Асимметричность МКСИ по времени выполнения связана с тем, что контурное кодирование, основанное на обнаружении контуров с помощью детектора

Камни, выполняется несколько медленнее, чем контурная билинейная интерполяция. Прямое и обратное ДВП требуют одинаковое время на выполнение.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

7. Установлено, что метод контекстного сжатия является наиболее эффективным для компрессии коэффициентов ДВП контурной информации изображения: его коэффициенты сжатия больше коэффициентов ПБУ+ДК в среднем на 23,2% и больше коэффициентов КДС+АК в среднем на 72,6%. Неэффективность общепринятого метода, основанного на совместном использовании кодирования

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

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

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

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

К специальности 05.13.01 - «Системный анализ, управление и обработка информации» относятся пп. 2, 3, 4, 5, 6, 7. К специальности 05.12.13 - «Системы, сети и устройства телекоммуникаций» относятся пп. 1, 8,10.

НАУЧНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Самохвалов A.B., Лялин В.Е. Применение алгоритма группового кодирования на этапе предобработки данных для арифметического сжатия // Весгаик Московской Академии рынка труда и информационных технологий, 2006. -№ 9 (21). -С. 156-163.

2. Самохвалов A.B. Определение типа изображения на основе существующих алгоритмов компрессии // Вестник Московской Академии рынка труда и информационных технологий, 2006. -№ 9 (21). - С. 182-186.

3. Мурынов А.И., Петров А:В., Самохвалов A.B. Дискретные представления и методы кодирования графических изображений для интеллектуальных телекоммуникационных систем // Вестник Московской Академии рынка труда и информационных технологий, 2006. - № 22 (44). - С. 105-113.

4. Мурынов А.И., Петров A.B., Самохвалов A.B. Распознавание структурных элементов изображения на дискретном растре // Ж. АН Украины «Искусственный интеллект» - № 4. - Донецк: Изд-во Наука i освгга, 2007. - С. 317-327.

5. Мурынов А.И., Петров A.B., Самохвалов A.B. Обнаружение и распознавание структурных элементов изображений на основе центроидного преобразования // Многопроцессорные вычислительные и управляющие системы: Материалы Ме-ждунар. науч.-техн. конф. - Таганрог: Изд-во ТТИ ЮФУ, 2007. - Т. 2. - С. 187-191.

6. Лялин В.Е., Самохвалов A.B. Метод обучения нейросетевых моделей на основе генетического алгоритма с вещественным кодированием // Информационные технологии в науке, образовании, телекоммуникации и бизнесе: Материалы 34-й Междунар. конф. - Украина, Крым, Ялта-Гурзуф: Прилож. к журн. «Открытое образование», 2007.-С. 159-161.

7. Самохвалов Л.В. Пространственный метод улучшения качества изображения, основанный на гистограммной подгонке // Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Труды 34-й юбилейной междунар. конф. - Украина, Крым, Ялта-Гурзуф: Прилож. к журн. «Открытое образование», 2008. - С. 178-180.

8. Самохвалов A.B. Классификация изображений, ориентированная на выбор оптимального алгоритма сжатия изображения // Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Труды 35-й юбилейной междунар. конф. - Украина, Крым, Ялта-Гурзуф: Прилож. к журн. «Открытое образование», 2008. - С. 155-158.

9. Самохвалов A.B. Кодирования изображений контурным методом с помощью цифровой интерполяции // Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Труды 35-й юбилейной междунар. конф. - Украина, Крым, Ялта-Гурзуф: Прилож. к журн. «Открытое образование», 2008. - С. 158-160.

10. Самохвалов A.B. Комплексное использование алгоритма кодирования длин серий и арифметического кодирования для сжатия изображений // Надежность и качество. Труды международного симпозиума: В 2-х томах / Под ред. II.K. Юркова. - Пенза: Изд-во Пенз. гос. ун-та, 2008. - Т. 1. - С. 237-240.

11. Самохвалов A.B. Адаптивное цветотоновое преобразование при кодировании графической информации // Надежность и качество. Труды международного симпозиума: В 2-х томах / Под ред. Н.К. Юркова. - Пенза: Изд-во Пенз. гос. ун-та, 2008. - Т. 1. - С. 250-253.

12. Петров A.B., Самохвалов A.B. Обобщенный алгоритм обучения Хебба при решении задачи кодирования изображений II Ж. АН Украины «Искусственный интеллект» - № 4. - Донецк: Изд-во Наука i освгга, 2008 - С. 412-417.

13. Самохвалов A.B., Петров A.B. Кодирование изображений на основе адаптивного анализа главных компонентов // Искусственный интеллект. Интеллектуальные системы: Материалы IX Междунар. науч.-техн. конф. - Донецк: ИЛИИ «Наука i освгга», 2008. - Т. 2. - С. 70-73.

14. Самохвалов A.B. Разработка метода интерполяции полутоновых изображений с большими пустыми областями II Вестник Ижевского государственного технического университета, 2009. - № 2 (42). - С. 138-141.

Лицензия ЛР № 020764 от 29.04.98

Подписано в печать 21.10.2009. Формат 60x84 1/16. Отпечатано на ризографе. Уч.-изд. л. 1,74. Усл. печ. л. 1,39 Тираж 100 экз. Заказ №984/3

A.B. Самохвалов

Издательство Института экономики УрО РАН 620014, г. Екатеринбург, ул. Московская - 29

Введение.

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

1.1. Основы сжатия данных.^

1.2. Универсальные методы сжатия данных без потерь.^

1.2.1. Метод кодирования длин серий

1.2.2. Статистические методы сжатия данных

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

1.2.4. Методы сжатия, основанные на контекстном моделировании.

1.2.5. Методы, основанные на преобразовании Барроуза-Уилера

1.3. Сжатие изображений.

1.3.1. Методы обхода плоскости изображений.

1.3.2. Виды избыточности данных в изображениях.

1.3.3. Общая модель системы сжатия изображений.

1.3.4. Методы сжатия изображений без потерь.

1.3.5. Методы сжатия изображений с потерями.

1.3.6. Критерии верности восстановления изображений

1.4. Стандарты сжатия изображений.

1.4.1. Стандарты сжатия двоичных изображений.

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

1.5. Восприятие изображений человеческим зрением.

1.6. Классификация изображений.^

1.7. Полученные результаты и выводы.^

1.8. Постановка цели и задач исследований.^

Глава 2. Контурные кодирование и интерполяция полутоновых изображений.

2.1. Контурное кодирование полутонового изображения.

2.1.1. Задача обнаружения контуров на полутоновом изображении.

2.1.2. Определение оптимального способа обнаружения контуров.

2.1.3. Утолщение контурных линий.

2.1.4. Маскирование полутонового изображения.

2.2. Контурная интерполяции изображений.

2.2.1. Реконструкция маскированного изображения.

2.2.2. Задача интерполяции.

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

2.3. Полученные результаты и выводы.

Глава 3. Компрессия контурного и маскированного изображений

3.1. Компрессия контурного изображения.

3.2. Компрессия контурной информации.

3.2.1. Трансформационное кодирование.

3.2.2. ВейвлетХаара.

3.2.3. Одномерное вейвлет-преобразование.

3.2.4. Выбор фильтров вейвлета.

3.2.5. Выбор уровня разложения.

3.2.6. Выбор уровня квантования.

3.2.7. Сжатие коэффициентов одномерного дискретного вейвлет-преобразован ия.

3.3. Полученные результаты и выводы.

Глава 4. Программно-алгоритмические средства и технология обработки информации в МСКИ.

4.1. Алгоритмы, программное обеспечение и технология обработки информации в МКСИ.

4.2. Экспериментальные данные и результаты.

4.3. Полученные результаты и выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

3. Установлено, что JBIG является наиболее эффективным методом сжатия контурной маски. Для низкочастотных изображений коэффициент сжатия в 4-5 раз больше чем у TIFF Group 4, для среднечастотных изображений — в 3-4 раза больше и для высокочастотных изображений в — 2-3 раза больше.

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

5. Показано, что данные отсканированного маскированного изображения являются весьма специфичными: в отличие от данных целого изображение они имеют гораздо более высокочастотных характер, так как представляют собой значения яркости контурных и околоконтурных пикселей. Установлено, что для такого рода данных при трансформационном преобразовании наиболее эффективно использование биортогонального вейвлета 8-4, так как он лучше других концентрирует энергию данных такого рода: лучше биортогонального вейвлета 5-3 — в среднем на 3%, лучше биортогонального вейвлета 16-4 — в среднем на 1,8%.

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

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

8. Установлено, что метод контекстного сжатия РРМ11 является наиболее эффективным для сжатия коэффициентов ДВП данных отсканированного маскированного изображения: его коэффициенты сжатия больше коэффициентов ГТБУ+ДК в среднем на 23,2% и больше коэффициентов КДС+АК в среднем на 72,6%. Относительная неэффективность метода, основанного на совместном использовании кодирования длин серий и арифметического кодирования, объясняется специфической структурой данных маскированного изображения, которые и подвергаются ДВП.

9. Проведены экспериментальные исследования разработанных средств и методов. На этапе компрессии МКСИ выполняется на 30% медленнее, а на этапе декомпрессии на 15% медленнее, чем №ЕС2000 на соответствующих этапах сжатия. Асимметричность МКСИ по времени выполнения связана с тем, что контурное кодирование, основанное на обнаружении контуров с помощью детектора Канни, выполняется медленнее, чем контурная билинейная интерполяция. Прямое и обратное ДВП требуют одинаковое время на выполнение.

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

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

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

К специальности 05.13.01 — «Системный анализ, управление и обработка информации» относятся пп. 2, 3, 4, 5, 6, 7, 8, 9, 12.

К специальности 05.12.13 — «Системы, сети и устройства телекоммуникаций» относятся пп. 1, 10, 11.

1.В., Горский Н.Д. Представление и обработка изображений. Л.: Наука, 1985.

2. Алексеев К.А. Вейвлет-анализ сигналов датчиков. 4.1. Континуальный анализ // ИИЦ ПГУ, 2001.

3. Алексеев К.А. Вейвлет-музыка // Датчики систем измерения, контроля и управления, ИИЦ ПГУ, 2001.

4. Алексеев К.А. Вейвлет-ряды в задаче оценивания собственных частот датчиков // Датчики и системы, 2001, №12, С. 2 5.

5. Алексеев К.А. Модели и алгоритмы вейвлет-обработки сигналов датчиков с применением лифтинга. 4.1 Теоретические основы лифтинга // Датчики и системы, 2002, №1, С. 3 - 9.

6. Алексеев К.А. Модели и алгоритмы вейвлет-обработки сигналов датчиков с применением лифтинга. 4.2 — Численное моделирование // Датчики и системы, 2002, №2, С. 2 5.

7. Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений. М.: Высшая школа, 1983. - 295с.

8. Артюшенко В.М., Шелухин О.И., Афонин М.Ю. Цифровое сжатие видеоинформации и звука. М.: Дашков и К°, 2003. - 426 с.

9. Астафьева Н.В. Вейвлет-анализ: основы теории и примеры применения //УФН, 1996, №11, С. 1145- 1170.

10. Бахвалов Н.С. , Жидков Н.П. Методы вычислений. Изд. ФизМат-Лит. Москва. 1962.11 "Бахвалов Н.С. , Жидков Н.П., Кобельков Г.М. . Численные методы. Изд-во ""Лаборатория базовых знаний"". 2003."

11. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.

12. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

13. Боглаев Ю.П. Вычислительная математика и программирование. -М.: Высшая Школа, 1990.

14. Ватолин Д. Алгоритмы сжатия изображений. М.: Диалог-МГУ, 1999.

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

16. Ватолин Д., А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: Диалог-МИФИ, 2002. 384 с.

17. Воробьева Г.Н., Данилова А.Н. Практикум по вычислительной математике. М.: Высшая Школа, 1990.- 207 с.

18. Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974.

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

20. Гончаров В. Л., Теория интерполирования и приближения функций, 2 изд., М., 1954.

21. Демидович Б.П., Марон И.А. Основы вычислительной математики. -М.: Наука, 1970.-664 с.

22. Добеши И. Десять лекций по вейвлетам. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

23. Дорот В.Л. Элементы вычислительной математики. Интерполирование, приближенное вычисление интегралов: учеб. пособие Л: ЛПИ, 1977. - 518 с.

24. Дремин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их применение // УФН, 2001, №5, С.465 501.

25. Дринфельд Г.И. Интерполирование и способ наименьших квадратов. -Киев: Высшая школа., 1984. 102 с.

26. Ибрагимов И.И. Методы интерполяции функций и некоторые их применения. И.: Наука, 1971. - 518с.

27. Иванов B.B. . Методы вычислений на ЭВМ. Справочное пособие. Изд-во "Hayкова думка". Киев. 1986."

28. Интерполяционные формулы / сост. Ю.И. Гросберг, JI.3. Румшин-ский. М., 1961. - 16 с.

29. К. Де Бор. Практическое руководство по сплайнам. Изд-во "Радио и связь". Москва. 1985.

30. Калиткин H.H. Численные методы М.: Наука, 1978.32' Касами Т., Токура Н., Ивадари Е., Инагаки Л. Теория кодирования. М.: Мир, 1978.

31. Клевачев В.И. Численные методы анализа (интерполяция). Учеб. пособие. М: МГПИ, 1978. -55с.

32. Климов А. С. Форматы графических файлов // С.-Пб.: ДиаСофт. 1995.

33. Колесник В.Д., Мирончиков Е.Т. Декодирование циклических кодов. М.: Связь, 1968.

34. Кривошеев М.И. Основы телевизионных измерений. М.: Радио и связь, 1989.

35. Кричевский P.E. Сжатие и поиск информации. М.: Радио и связь, 1989.

36. Крылов В.И. Начала теории вычислительных методов: интерполирование и интегрирование. Минск: Наука и техника., 1983. - 287 с.

37. Мак-Вильяме Ф., Слоэн Н.Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

38. Мак-Кракен Д., Дорн У. Численные методы. 2-е изд. - М.: Мир, 1977.

39. Марков A.A. Введение в теорию кодирования. М.: Наука, 1982.

40. Марр Д. Зрение. Информационный подход к изучению представления и обработки зрительных образов. -М.: Радио и связь, 1987.

41. Мастрюков Д. Сжатие графической информации.// Алгоритмы сжатия информации. Часть 7. Сжатие графической информации// Монитор, N6, 1994. С12-17.

42. Методы компьютерной обработки изображений / Ред. Сойфер. В.А. М.: Физматлит, 2001.

43. Методы передачи изображений. Сокращение избыточности / Прэтт У.К., Сакрисон Д.Д., Мусман Х.Г.Д. и др. / Ред. Прэтт УК. — М.: Радио и связь, 1983.

44. Мурынов А.И., Вдовин A.M., Лялин В.Е. Оценка геометрико-топологических параметров деталей изображений на основе метода центроид-ной фильтрации // Химическая физика и мезоскопия. Т.4, 2002, №2. С. 145-160.

45. Мурынов А.И., Петров A.B., Самохвалов A.B. Распознавание структурных элементов изображения на дискретном растре // Ж. АН Украины «Искусственный интеллект» № 4. - Донецк: Изд-во Наука i освгга, 2007. - С. 317-327.

46. Носач В.В. Решение задач аппроксимации с помощью персональных компьютеров. М.: МИКАП, 1994. - 332 с.

47. Обработка изображений и цифровая фильтрация. / Ред. Хуанг Т. — М.: Мир, 1979.

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

49. Петров A.B., Самохвалов A.B. Обобщенный алгоритм обучения Хеб-ба при решении задачи кодирования изображений // Ж. АН Украины «Искусственный интеллект» № 4. - Донецк: Изд-во Наука i осв1та, 2008 - С. 412-417.

50. Прокопенко В. Т., Трофимов В. А., Шарок Л.П. Психология зрительного восприятия/ Учебное пособие. СПб: СПбГУИТМО, 2006. - 73с.

51. Прэтт У. Цифровая обработка изображений. Кн. 1. - М.: Мир, 1982. - 312с. - Кн. 2. - М.: Мир, 1982. - 480с.

52. Распознавание образов при помощи цифровых вычислительных машин / Ред. Хармон Л. — М.: Мир, 1974.

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

54. Романов В. Ю. Популярные форматы файлов для хранения графических изображений на IBM PC // М.: Унитех, 1992.

55. Самарский A.A., Гулин A.B. Численные методы. М,: Наука., - 1989.

56. Самарский A.A. Введение в численные методы. М.: Наука, 1982.

57. Самохвалов A.B. Определение типа изображения на основе существующих алгоритмов компрессии // Вестник Московской Академии рынка труда и информационных технологий, 2006. № 9 (21). - С. 182-186.

58. Самохвалов A.B. Разработка метода интерполяции полутоновых изображений с большими пустыми областями // Вестник Ижевского государственного технического университета, 2009. С. 120-123.

59. Самохвалов A.B., Уфимкин А.Я. Применение алгоритма группового кодирования на этапе предобработки данных для арифметического сжатия // Вестник Московской Академии рынка труда и информационных технологий, 2006. № 9 (21). - С. 156-163.

60. Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике. Теория и приложения. — Ижевск: НИЦ «Регулярная и хаотическая динамика». 2002.

61. Сэломон Д. Сжатие данных изображений и звука. М.: Техносфера, 2004. - 368с.

62. Трибель X. Теория интерполяции, функциональные пространства, дифференциальные операторы . -М: Мир., 1980. 664с.

63. ТуДж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.

64. Турецкий А.Х. Теория интерполирования в задачах. Минск: Высш. шк., 1968. - 318 с.

65. Турчак Л.И. Основы численных методов. М.: Наука, 1987.- 320 с.

66. Ульман Ш. Принципы восприятия подвижных объектов. М.: Радио и связь, 1983.

67. Фано P.M. Передача информации. Статистическая теория связи М.: Мир, 1965.80 "Форсайт Дж. , Мальком М., Моулер К. . Машинные методы математических вычислений. Изд-во «Мир». Москва. 1980."

68. Фу К. Последовательные методы в распознавании образов и обучении машин. М.: Наука, 1979.

69. Фу К. Структурные методы в распознавании образов. М.: Мир, 1977.

70. Ханова A.A., Макарова И.Г. Лабораторный практикум по математическому моделированию и методам в расчетах на ЭВМ. Астрахань: Изд-во АГТУ, 1998.- 93 с.

71. Хорн Б.К.П. Зрение роботов. М.: Мир, 1989.

72. Хэмминг Р.В. Теория кодирования и теория информации. М.: Радио и связь, 1983.

73. Цифровая обработка изображений в информационных системах: Учебное пособие / Грузман И.С., Киричук B.C. и др. Новосибирск, НГТУ, 2002.

74. Цифровая обработка телевизионных и компьютерных изображений /Дворкович A.B., Дворкович В.П., Зубарев Ю.Б. и др. М.: Меж-дународный центр научной и технической информации, 1997.

75. Цифровое кодирование телевизионных изображений / Цуккерман И.И., Кац Б.М., Лебедев Д.С. и др. М.: Радио и связь, 1981.

76. Чисар И., Кернер Я. Теория информации: теоремы кодирования для дискретных систем без памяти. М.: Мир, 1985.

77. Чуй К. Введение в вейвлеты. М.: Наука, 2001.

78. Шашлов Б А Цвет и цветовоспроизведение — М.: МГАП «Мир книга», 1995.

79. Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963.

80. Шкарин Д. Повышение эффективности алгоритма РРМ // Проблемы передачи информации. 2001. Т. 34(3). С. 44-54.

81. Шуп Терри Е. Прикладные численные методы в физике и технике. -М.: Высшая Школа, 1990. 254 с.

82. Эндрюс Г. Применение вычислительных машин для обработки изоб-ражений. —М.: Энергия, 1977.96 "Яблонский С. В. ""Введение в дискретную математику"" // М.: Наука, 1986. Раз. ""Теория кодирования""."

83. Яглом А.М., Яглом ИМ. Вероятность и информация. М.: Наука, 1973.

84. Яншин В.В. Анализ и обработка изображений: принципы и алгоритмы.— М.: Машиностроение, 1994.

85. Ярославский Л. П. Введение в цифровую обработку изображений. -М.: Сов. радио, 1969. -312 с.

86. Ageenko Е., Franti P. Compression of large binary images in digital spatial libraries. Computers & Graphics, 24 (1), pp.91-98, Elsevier Science, February 2000.

87. Aldus Corporation Developer's Desk. TIFF Revision 6.0, Final. 1992. June 3.

88. Bell T., Witten I, Cleary J. Modeling for Text Compression. ACM Computing Surveys, Vol.21, No.4, pp.557-591, Dec. 1989.

89. Bloom C. Solving the problems of context modeling // California Institute of Technology. 1996.

90. Burrows M., Wheeler D.J. A Block-sorting Lossless Data Compression Algorithm // SRC Research Report 124, Digital Systems Research Center, Palo Alto, California, May 1994.

91. Canny J. F. Finding edges and lines in images. // M.I.T. Artificial Intell. Lab., Cambridge, MA, Rep. AI-TR-720, 1983.

92. Cleaiy J. G-, Witten I. H. Data compression using adaptive coding and partial string matching // IEEE Transactions on Communications April 1984. Vol. 32(4). P. 396-402.

93. Hamilton E. JPEG File Interchange Format // Version 1.2. September 1,1992, San Jose CA: C-Cube Microsystems, Inc.

94. Howard P., Vitter J. Practical Implementations of Arithmetic Coding. Technical Report No. 92-18. Revised version, April 1992. Brown University, Department of Computer Science.

95. Jeff Prosise. How Computer Graphics Work. Ziff-Davis Press, 1994. - 182 p.

96. JPEG 2000 Committee. JPEG 2000 IMAGE CODING SYSTEM. JPEG 2000 FINAL COMMITTEE DRAFT VERSION 1.0, 16 MARCH 2000.

97. Karen L. Gray .The JPEG2000 Standard, echnische Universit. at M. un-chen Lehrstuhl f. ur Kommunikationsnetze.

98. Langdon, G. G. and Rissanen, J.: Compression of black-white-images with arithmetic coding, in: IEEE Trans. Commun. COM 29, Nr. 6, S. 858-867.

99. Malvar H.S. Fast Adaptive Encoder for Bi-Level Images. Proceedings of IEEE Data Compression Conference, Snowbird, Utah, March 27-29, 2001.

100. Marcellin M., Gormish M., Bilgin A., Boliek M. An Overview of JPEG-2000. Proceedings of the 2000 IEEE Data Compression Conference, pp. 523-541, Snowbird, Utah, March 2000.

101. Marr, D. and Ullman, S. (1981). Directional selectivity and its use in early visual processing. Proceedings of the Royal Society of London B, 211:151—180.

102. Meyer, Y. Wavelets and Operators. Cambridge University Press, 1993.

103. Meyer, Y. Wavelets: Algorithms and Applications, SIAM, 1993.

104. Moffat A. Implementing the PPM Data Compression Scheme. IEEE Transactions on Communications, Vol. 38, No. 11, pp. 1917-1921, Nov. 1990.

105. Moffat A., Neal R., Witten LH. Arithmetic Coding Revisited // ACM Transactions on Information Systems, 16(3), 1998, p. 256-294.

106. Motta G., Storer J., Carpentieri B. Adaptive Linear Prediction Lossless Image Coding. Proceedings of IEEE Data Compression Conference, Snowbird, Utah, March 29-31, 1999.

107. Pennebaker W.B., Mitchell J.L., Langdon G.G., Arps R.B. An overview of the basic principles of the Q-Coder adaptive binary arithmetic coder. BM Journal of Research and Development, Vol. 32, number 6, page 717-726, 1988

108. Rissanen J. J., Langdon G. G. Universal modeling and coding // IEEE Transactions on Information Theory. Jan. 1981. Vol. 27(1). P. 12-23.

109. Ryabko B. Ya. Data Compression by Means of a "Book Stack"// Problems of Information Transmission. Vol. 16(4). 1980. P. 265-269.

110. Wallace G. The JPEG Still Picture Compression Standard. IEEE Transactions on Consumer Electronics, Dec. 1991.

111. Welch T. A Technique for High-Performance Data Compression // Computer, June, 1984.

112. Wickerhauser, M.V. Adapted wavelet analysis. AKPeters, 1994.

113. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery NUMERICAL RECIPES. The Art of Scientific Computing. Third Edition. — New York: Cambridge University Press, 2007. - 1235 p.

114. Witten I., Neal R., Cleary J. Arithmetic Coding For Data Compression // Communications of the ACM, vol. 30, no. 6, P.520-540, June 1987.

115. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression. EEE Transactions on Information Theory, Vol. IT-23, No. 3, May 1977, P. 337-343.