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

Гузеев Алексей Валерьевич

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

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

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

АВТОРЕФЕРАТ

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

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

Москва-2011

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

Научный руководитель: кандидат технических наук, доцент, Свет Сергей Дарьевич

Официальные оппоненты: д.т.н., профессор Шелухин Олег Иванович к.т.н., доцент Казанский Николай Александрович

Ведущая организация: Федеральное государственное унитарное предприятие научно-исследовательский институт радио (ФГУП НИИР)

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

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

Автореферат разослан « 11 » мая 2011 г.

Учёный секретарь совета по защите докторских и кандидатских диссертаций С. Д. Ерохин

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

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

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

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

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

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

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

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

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

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

Задачами исследования являются:

1. Анализ современных методов повышения эффективности передачи информации по мультисервисным сетям связи.

2. Анализ известных алгоритмов сжатия, современных стандартов кодирования и их классификация.

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

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

5. Разработка алгоритма формирования распределения вероятностей появления блоков в изображении.

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

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

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

9. Разработка рекомендаций по использованию предложенных алгоритмов.

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

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

Методологическая и теоретическая основа исследования Теоретическую основу исследования составили труды в области теории информации В. В. Панина, В. В. Лидовского, Р. Фано, К. Шеннона, Дж. Вольфовица. В области теории кодирования использовались труды сотрудников Массачусетского технологического института Л. Крафта и Д. Хаффмана, а также публикации Дж. Рисаннена и Г. Ленгдона в области арифметического кодирования. Исследования влияния искажений на восприятие человеком бинарных изображений основывались на работах в области психофизиологии человеческого зрения Ч.А. Измайлова, А.М. Черноризова, С.Д. Света, а также Е.И.

Ковалевского, в области офтальмологии. В области обработки цифровых сигналов использовались работы Д.Сэломона, Р. Гонсалеса, Р. Вудса, Я. Уиттена, А. Моффата, Т.

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

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

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

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

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

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

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

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

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

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

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

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

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

в ЗАО «СПЕЦВИДЕОПРОЕКТ» при проектировании и реализации проектов цифровых систем видеонаблюдения (акт внедрения);

в ООО «СИБИНТЕК» для хранения в сжатом виде базы документов системы электронного документооборота (акт внедрения);

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

Апробация результатов исследования Основные положения и результаты диссертационной работы докладывались и обсуждались на Московской отраслевой научно-технической конференции «Технологии информационного общества» (г. Москва, 2007г.), Международной научно-технической школе-конференции «Молодые ученые – науке, технологиям и профессиональному образованию» (г. Москва, 2008г.), конференции «Телекоммуникационные и вычислительные системы», проходящей в рамках Международного форума информатизации – 2009 (г.

Москва, 2009г.) и Международного форума информатизации – 2010 (г. Москва, 2010г.).

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

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

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

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

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

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

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

Объем работы Диссертационная работа содержит 132 страницы основного текста, 10 приложений на 44 страницах, 43 рисунка и графика, 31 таблицу. В списке литературы 69 наименований.

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

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

В главе 1, с целью определения путей повышения эффективности передачи бинарных изображений, проводится анализ стандартов сжатия, применяемых в мультисервисных сетях связи (МСС). Стандарты сжатия определяются протоколами, которые используются для построения мультисервисных сетей связи. В настоящее время существует два основных сценария построения МСС: на базе протокола Н.323 или на базе протокола SIP (Session Initiation Protocol / Протокол инициирования сеансов). Оба протокола призваны обеспечивать работу мультимедийных приложений в МСС. Приложениями этих протоколов, наряду с речевым трафиком, являются передача видео и данных, а в случае Н.323, добавляется еще и факсимильная передача. Бинарные изображения в МСС относятся к категории данные, поэтому для их передачи используются два протокола: Т.126 – передача неподвижных изображений и Т.127 – передача бинарных файлов. Кроме того, сжатие данных осуществляется протоколом IPCom из стека IPSec. Три указанных протокола задают используемую совокупность стандартов сжатия, включающую в себя следующие стандарты:

Group 3 (T.4), Group 4 (T.6), JPEG (T.81), JBIG (T.82), LZS (RFC 2395) и DEFLATE (RFC 2394), и во многом определяют возможные пути взаимодействия с этими стандартами. На рисунке 1 показана классификация стандартов сжатия, применяемых в МСС.

T.6 (Group 4) статистическое кодирование T.82 (JBIG) Рисунок 1 – Стандарты сжатия в мультисервисных сетях связи В частности установлено, что при взаимодействии с протоколом Т.127 необходимо осуществлять эффективное кодирование (сжатие) на прикладном уровне до представления данных в виде бинарного файла. Для взаимодействия со стандартами сжатия определенными в Т.126 необходимо разработать алгоритм, не осуществляющий сжатие в явном виде, а только упрощающий структуру изображения. То есть, после работы такого алгоритма сжатия не происходит, но создается новое изображение, для которого коэффициент сжатия стандартами из Т.126 будет выше. Для взаимодействия с протоколом IPCom необходимо применение эффективного статистического кодирования на предварительном этапе. Все предложенные в данной диссертации решения позволяют повысить эффективность передачи бинарных изображений мультисервисными сетями связи.

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

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

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

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

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

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

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

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

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

Тогда упрощение структуры может состоять в том, что число различных вариантов блоков, представляющих изображение, ограничивается и новое изображение - «допустимая» копия строится только из небольшого числа так называемых разрешенных блоков, все остальные блоки - запрещенные. Оценить допустимость построенного изображения – копии позволяет разрешающая способность глаза, являющаяся определяющим свойством зрительной системы человека при восприятии черно-белых изображений. У человека со стопроцентным зрением разрешающая способность глаза принимается равной одной угловой минуте. Это означает, что при рассматривании изображения с расстояния в 25 см, такое расстояние является расстоянием наилучшего зрения, он сможет различить две точки, только если эти точки находятся на расстоянии большем или равном 0,073 мм. На основе данного факта показано, что при внесении искажений изменяющих локальный контур на один пиксель относительно оригинального положения, отдельные области изображения будут оставаться различимыми для наблюдателя, так как расстояние между ними будет оставаться больше, чем минимальноразличимое зрительной системой здорового человека. Предлагается использовать критерий, определяющий изменение положения локальных контуров, для оценки качества изображений при удалении визуальной избыточности.

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

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

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

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

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

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

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

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

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

В главе 3 разработана математическая модель бинарного изображения на основе цепи Маркова, которая позволяет выразить вероятность появления полностью белого блока с размерами m n как: P(0; n, m) = P(0) P(0 | 0) n + m 2, где P (0) - вероятность появления белого единичного элемента, а P (0 | 0) - вероятность того, что после белого единичного элемента будет находиться черный. Показано, что предложенная модель может быть использована только для расчета вероятностей появления блоков полностью состоящих из доминирующих пикселей в изображении.

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

Для префиксного блочного кодирования распределение вероятностей можно записать как:

Тогда средняя длина кодового слова определяется, как коэффициент сжатия будет равен:

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

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

Это уравнение получается из последней системы при следующих заменах: x = n = m, a0 = P(0) и a1 = P(0 | 0). Для его решения используется итерационный алгоритм Ньютона, который, в данном случае, для очередного приближения корня функции даст следующее выражение:

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

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

средний коэффициент сжатия Рисунок 4 – Средние коэффициенты сжатия для различных вариантов «Отличное» - качество для вариантов 1,2 и 3 это 128 разрешенных блоков, для вариантов 4 и 5 это Кп=4 и компенсация изображения остовом. «Хорошее» качество для вариантов 1,2 и 3 это 64 разрешенных блока, а для вариантов 4 и 5 это Кп=4.

В среднем по всем предложенным вариантам взаимодействия разработанных алгоритмов для сжатия без потерь коэффициент сжатия составит 19,59, для сжатия с «отличным» качеством – 25,01, для сжатия с «хорошим» качеством – 27,52. Средний выигрыш в коэффициенте сжатия от внесения потерь для сжатия с «отличным» качеством составит 28%, для сжатия с «хорошим» качеством – 40%.

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

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

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

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

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

В заключении представлены основные результаты работы.

1. Проведен анализ современных методов повышения эффективности передачи информации по МСС и установлены следующие факты:

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

при передаче информации при помощи протокола Т.126 используются стандарты, не предназначенные для бинарных изображений (Т.81), не позволяющие получить распространенность (Т.82).

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

использование статистического кодирования с укрупнением алфавита источника;

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

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

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

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

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

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

7. Проведен анализ коэффициентов сжатия разработанных алгоритмов и установлено, что в среднем по всем предложенным вариантам взаимодействия разработанных алгоритмов коэффициент сжатия составит: для сжатия без потерь – 19,59, для сжатия с «отличным»

качеством – 25,01, для сжатия с «хорошим» качеством – 27,52. Средний выигрыш в коэффициенте сжатия от внесения потерь составит: для сжатия с «отличным» качеством – 28%, для сжатия с «хорошим» качеством – 40%. Средний по всем предложенным вариантам взаимодействия разработанных алгоритмов коэффициент сжатия превосходит средние коэффициенты сжатия стандартов, используемых в настоящее время в МСС.

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

9. Разработаны рекомендации по использованию разработанных алгоритмов или вариантов взаимодействия разработанных алгоритмов в МСС в зависимости от требуемых возможностей при реализации пользовательских услуг.

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

1. Гузеев А.В., Свет С.Д. Компактное представление и кодирование графических изображений. Электросвязь. – 2009. - №3. –с. 41-45.

2. Гузеев А.В. Формирование распределения вероятностей появления отдельных сообщений источника при статистическом кодировании. TComm. – 2010. - №6. – с. 12-16.

1. Гузеев А.В., Свет С.Д., Колесник Е.Л. Повышение эффективности сжатия двухградационных изображений. Технологии информационного общества: Тезисы докладов московской отраслевой научно-технической конференции. -М.:

Инсвязьиздат,2007. –с.117.

2. Гузеев А.В., Свет С.Д. Перспективы развития блочного кодирования изображений.

Материалы Международной научно-технической школы-конференции «Молодые ученые – науке, технологиям и профессиональному образованию». – М.: Энергоатомиздат, 2008. – с. 181-183.

3. Гузеев А.В. Сжатие бинарных изображений с помощью блочного кодирования.

Приложение в телемедицине. Международный конгресс «Коммуникационные технологии и сети». Труды конференции «Телекоммуникационные и вычислительные системы». – М.,2009. –с. 338-340.

4. Гузеев А.В. Эффективное кодирование изображений с потерями, допустимыми для зрительной системы человека. Международный конгресс «Коммуникационные технологии и сети». Труды конференции «Телекоммуникационные и вычислительные системы». – М.,2010. –с. 283-285.