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

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

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

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

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

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

4848221

2 КЮН 2011

Москва-2011

4848221

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

(МТУСИ)

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

|Свет Сергей Дарьевич|

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

к.т.н., доцент Казанский Николай Александрович

Ведущая организация: Федеральное государственное унитарное

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

г. в^^ча

Защита состоится «/_£_» СС-К''-!^ 2011 г. в ' ^ часов на заседании совета по защите докторских и кандидатских диссертаций Д 219.001.03 при МТУСИ по адресу: 111024, Москва, ул. Авиамоторная, д. 8а, ауд. А-455

С диссертацией можно ознакомиться в библиотеке МТУСИ Автореферат разослан «» 2011 г.

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

С. Д. Ерохин

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

Актуальность темы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Объект исследования и предмет исследования

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

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

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

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

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

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

- официальные документы в виде стандартов, рекомендаций и других нормативных актов;

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

Научная новизна исследования

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

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

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

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

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

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

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

Практическая значимость работы

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

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

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

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

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

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

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

Апробация результатов исследования

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

По результатам исследований, составивших основу диссертации, опубликовано 6 научных работ, включая 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 (Т.4), Group 4 (Т.6), JPEG (Т.81), JBIG (T.82), LZS (RFC 2395) и DEFLATE (RFC 2394), и во многом определяют возможные пути взаимодействия с этими стандартами. На рисунке 1 показана классификация стандартов сжатия, применяемых в МСС.

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

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

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

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

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

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

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

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

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

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

Визуальную избыточность, предлагается удалять с учетом особенностей зрительной

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

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

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

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

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

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

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

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

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

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

В главе 3 разработана математическая модель бинарного изображения на основе цепи Маркова, которая позволяет выразить вероятность появления полностью белого блока с размерами тхп как: Р(0\п,т) = Р(0)■ Р(010)"*""2, где Р(0) - вероятность появления белого единичного элемента, а Р(010) - вероятность того, что после белого единичного элемента будет находиться черный. Показано, что предложенная модель может быть использована только для расчета вероятностей появления блоков полностью состоящих из доминирующих пикселей в изображении.

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

полностью белого блока заданного размера.

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

как:

{Р(0; и, то), при 1=0, полностью белый блок при* = 1,-",2|"°" -1

Тогда средняя длина кодового слова определяется, как 1 = пт(\-Р(0,п,т)) + \ и коэффициент сжатия будет равен:

п-ш п-т п-т

——=— =

/ иш(1 - Рф; п,т)) +1 лш(1- />(0) -Р(0| О)"4™"2) + Г

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

Р{ 0) • Р(010)"""2 • In Р(010)+—i— = 0 п -т

Р(0) • Р(010)"*""3 • In Р(010)+—Ц- = 0 п-т

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

а01па,-а12'"г+-1- = 0.

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

а„ -а, "~2 - Ina, м 1 2а0 -а2"'"2 -In2 а, -3xf

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

N С'„

.где

(=1 ]=\

Р6 - вероятность появления 1-го блока, И = м/-к - размер блока (ширина,

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

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

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

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

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

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

Таблица 1

Сравнение разработанных схем кодирования со стандартами сжатия бинарных __изображений___

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

вз 12,19 вариант 1 18,98 24,04

15,55 вариант 2 20,32 27,42

1ВЮ 23,59 вариант 3 20,68 26,07

№ЕО кач.Ю 2,32 вариант 4 18,98 22,55

1РЕС кач.100 0,86 вариант 5 18,98 24,97

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации в изданиях, рекомендуемых ВАК

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

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

Прочие публикации

1. Гузеев A.B., |Свет С.д! Колесник ЕЛ. Повышение эффективности сжатия двухградационных изображений. Технологии информационного общества: Тезисы докладов московской отраслевой научно-технической конференции. -М: Инсвязьиздат,2007. -с. 117.

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

3. Гузеев A.B. Сжатие бинарных изображений с помощью блочного кодирования. Приложение в телемедицине. Международный конгресс «Коммуникационные технологии и сети». Труды конференции «Телекоммуникационные и вычислительные системы». — М.,2009.-с. 338-340.

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

Подписано в печать:28.04.11 Тираж: 100 экз. Заказ № 3767 Отпечатано в типографии «Реглет» 119526, г. Москва, ул. Фридриха Энгельса, д. 3/5, стр. 2 (495) 661-60-89; www.reglet.ru

Введение.

Актуальность темы.

Цели и задачи исследования.

Объект исследования и предмет исследования.б

Методологическая и теоретическая основа исследования.

Информационная база исследования.

Научная новизна исследования.

Практическая значимость работы.

Использование результатов работы.

Апробация результатов исследования.

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

Объем работы.

Глава 1: Классификация современных алгоритмов сжатия и стандарты кодирования в мультисервисных сетях.

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

1.2 Анализ стандартов сжатия информации в мультисервисных сетях связи.

1.2.1 Основные методы повышения эффективности передачи информации МСС.

1.2.2 Акселерация трафика данных (решения JUNIPER Networks).

1.3 Сжатие изображений и виды избыточности, свойственные изображениям.

1.3.1 Понятие класса изображения.

1.3.2 Понятие избыточности данных.

1.3.3 Кодовая избыточность.

1.3.4 Межэлементная избыточность.

1.3.5 Психовизуальная избыточность.

1.3.6 Понятие документальной информации.

1.3.7 Понятие глубины цветопередачи изображения.

1.3.8 Понятия алгоритма сжатия и формата файла изображения.

1.4 Анализ основных алгоритмов эффективного кодирования.

1.4.1 Классический алгоритм Хаффмана.

1.4.2 Факсимильное сжатие.

1.4.3 Кодирование длин серий.

1.4.4 Словарное кодирование (LZW).

1.4.5 Арифметическое кодирование.

1.4.6 Фрактальное кодирование.

1.4.7 Вейвлет кодирование.

1.5 Анализ стандартов кодирования изображений.

1.5.1 Анализ технологии JPEG.

1.5.2 JBIG: стандарт для сжатия двухградационных изображений.

1.6 Классификация алгоритмов сжатия.

1.7 Выводы.

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

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

2.2 Алгоритм предобработки.

2.2.1 Внесение потерь на базе блочного представления изображений.

2.2.2 Разрешающая способность человеческого глаза.

2.2.3 Разработка алгоритма внесения потерь.

2.2.4 Метрики ошибок.

2.3 Алгоритмы сжатия бинарных изображений.

2.3.1 Модифицированный алгоритм Хаффмана.

2.3.2 Алгоритм префиксного блочного кодирования.

2.3.3 Процедура выделения областей интереса.

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

2.5 Форматы файлов.

2.6 Выводы.

Глава 3: Выбор оптимальных параметров разработанных алгоритмов сжатия.

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

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

3.3 Вычисление вероятности появления блока на основе цепи Маркова.

3.4 Проверка адекватности математической модели.

3.5 Определение оптимальных размеров блока алгоритма ПБК.

3.5.1 Преобразование битового потока.

3.5.2 Вычисление коэффициента сжатия.

3.6 Доказательство оптимальности алгоритма построения шаблона замены.

3.7 Выводы.

Глава 4: Анализ степени сжатия разработанных алгоритмов на основе компьютерного моделирования.

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

4.2 Подготовка компьютерного моделирования.

4.3 Компьютерное моделирование разработанных алгоритмов.

4.3.1 Результаты моделирования для варианта 1.

4.3.2 Результаты моделирования для варианта 2.

4.3.3 Результаты моделирования для варианта 3.

4.3.4 Результаты моделирования для варианта 4.

4.3.5 Результаты моделирования для варианта 5.

4.4 Сравнительный анализ предложенных вариантов.

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

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

4.7 Выводы.

Актуальность темы

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

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

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

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

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

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

Цели и задачи исследования

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

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

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

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

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

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

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

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

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

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

Объект исследования и предмет исследования

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

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

Методологическая и теоретическая основа исследования

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

Черноризова, |С.Д. Света], а также Е.И. Ковалевского, в области офтальмологии. В области обработки цифровых сигналов использовались работы Д.Сэломона, Р. Гонсалеса, Р. Вудса, Яна Уиттена (Ian Witten), А. Моффата (Alistar Moffat), Т. Bejuia(Timothy Bell). Теоретической основой для математического и компьютерного моделирования послужили труды специалистов в области высшей математики, теории статистики и численных методов А. Самарского, А. Гулина, Г.Л. Громыко, Т.Корна и Г.Корна. Для проведения анализа алгоритмов сжатия в мультисервисных сетях связи использовались работы специалистов ЦНИИС А.Е. Кучерявого и А.Л. Цуприкова, книги А.Б. Гольдштейна, и В.Ю. Деарта. При оформлении диссертации использовались материалы Б.А. Райзберга.

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

Информационная база исследования

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

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

- официальные документы в виде стандартов, рекомендаций и других нормативных актов;

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

Научная новизна исследования

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

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

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

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

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

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

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

Практическая значимость работы

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

Использование результатов работы

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

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

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

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

Апробация результатов исследования

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

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

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

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

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

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

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

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

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

Объем работы

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

Основные результаты работы заключаются в том, что:

1. Проведен анализ современных методов повышения эффективности передачи информации по МСС и установлено что: при передаче информации в виде бинарных файлов (протокол Т. 127) отсутствуют алгоритмы сжатия, определенные по умолчанию и предназначенные для сжатия черно-белых изображений; при передаче информации при помощи протокола Т. 126 используются стандарты, не предназначенные для бинарных изображений (Т.81), не позволяющие получить высокие коэффициенты сжатия (Т.4, Т.6) или имеющие ограниченную распространенность (Т.82).

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

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

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

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

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

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

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

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

Заключение

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

2. Ватолин Д.С. Методическое пособие: Алгоритмы сжатия изображений. // МГУ, 1999.

3. Вернер М., Основы кодирования. Учебник для ВУЗов. // М.: Техносфера, 2006.

4. Вольфовиц Дж. Теоремы кодирования теории информации // М.: Мир, 1967.

5. Гольдштейн А.Б., Гольдштейн Б.С. SOFTSWITCH //СПб.: БХВ Санкт-Петербург, 2006.

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

7. ГОСТ 7.0—99. Информационно-библиотечная деятельность, библиография: Термины и определения. Введ. с 01.07.2000.// Система стандартов по информации, библиотечному и издательскому делу: Изд. офиц. М., 1999.

8. Громыко Г.Л. Теория статистики // М.: ИНФРА-М, 2009.

9. Гузеев A.B., ВКР Бакалавра на тему: "Предобработка двухградационных изображений" // МТУ СИ, 2005.

10. Гурлев Д.С. Справочник по фотографии (светотехника и материалы) // К.: Техника, 1986.

11. Деарт В.Ю. Мультисервисные сети связи. Транспортные сети и сети доступа. // М.: Инсвязьиздат, 2007.

12. Измайлов Ч.А., Черноризов A.M. Язык восприятия и мозг // Психология. Журнал Высшей школы экономики. Т.2, №4, с. 22-52, 2005.

13. Ковалевский Е.И. Офтальмология. Учебник. // М.: Медицина, 1995.

14. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров // М.: Наука, 1984.

15. Кунт М. Блочное кодирование графических материалов // ТИИЭР, т.68, №7, 1980.

16. Кучерявый А.Е., Цуприков А.Л., Сети связи следующего поколения. // М.: ФГУП ЦНИИС, 2006.

17. Лидовский В.В. Теория информации // М.: «Компания Спутник*», 2004.

18. Миано Дж., Форматы и алгоритмы сжатия изображений в действии. Учеб.пособ.// М.: Издательство Триумф, 2003.

19. Олифер В.Г., Олифер H.A. Компьютерные сети. Принципы, технологии, протоколы.: Учебник для вузов. 3-е изд. // СПб.: Питер, 2006.

20. Панин В.В. Основы теории информации: учебное пособие для вузов // М.: БИНОМ. Лаборатория знаний, 2007.

21. Райзберг Б.А. Диссертация и ученая степень. Пособие для соискателей. // М.: ИНФРА-М, 2003.

22. Рекомендация МСЭ-Т Т.263, Кодирование видеосигнала для низкоскоростной связи, 2005.

23. Ричардсон Ян, Видеокодирование Н.264 и MPEG-4 стандарты нового поколения // М.: Техносфера, 2005.

24. Самарский А.А., Гулин А.В. Численные методы: учебное пособие для вузов // М.: Наука, 1989.

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

26. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии.Учебное пособие. // М.: Триумф, 2003.

27. Фано P.M. Передача информации. Статистическая теория связи // М.: Мир, 1965.

28. Чепусов Е.Н. Документальная телеконференция: недостающее звено между аудио- и видеоконференц-связью // Сети и системы связи 1998.-№6.

29. Шарыгин М.Е. Сканеры и цифровые камеры // СПб.: БХВ-Петербург; Артлит, 2001.

30. ANSI Х3.241, Data Compression Method -Adaptive Coding with Sliding Window for Information Interchange, 1994.

31. AT&T Inc., Specification of DjVu image compression format// 1999.

32. Cawkell A.E. Progress in documentation: Electronic document delivery systems // J. Doc. -1991.-Vol. 47, N l.-P. 41 -73.

33. CompuServe, Inc. Graphics Interchange Format (GIF) Specification // CompuServe, Columbus, OH, 1987.

34. Golomb S.W. Run-length encoding // IEEE Trans, on Inf. Theory, IT-12. P. 399-401, 1966.

35. Hamilton E. JPEG File Interchange Format Ver. 1.02 // C-Cube Microsystems, 1992.

36. Howard P.G., Vitter J.S. Practical implementations of arithmetic coding // Brown University, tech. rep. № 92-18, 1992.

37. Huffman D.A. A method for the construction of minimum redundancy codes // Proc. of IRE val.40 1962 pp. 1098-1101.

38. ISO/IEC 14496-2, Coding and Audio-Visual Objects. Part 2: Visual // 2001.

39. ITU-T Recommendation H.261, Video codec for audiovisual services at px64 kbits, 1993.

40. ITU-T Recommendation H.264, Advanced video coding for generic audiovisual services, 2009.

41. ITU-T Recommendation H.323, Packet-based multimedia communications systems, 2006.

42. ITU-T Recommendation T.4, Standardization of group 3 facsimile apparatus for document transmission, 2003.

43. ITU-T Recommendation,T.6, Facsimile coding schemes and coding control functions for group 4 facsimile apparatus, 1988.

44. ITU-T Recommendation T.24, Standardized digitized image set, 1998.

45. ITU-T Recommendation T.81, Information technology — Digital compression and coding Of continuous-tone still images Requirements and guidelines, 1993.

46. ITU-T Recommendation T.82, Information technology — Coded representation of picture and audio information — Progressive bi-level image compression, 1993.

47. ITU-T Recommendation T.85, Progressive bi-level image compression (JBIG coding scheme) for facsimile apparatus, 1995.

48. ITU-T Recommendation T.88, Information technology lossy/lossless coding of bi-level images, 2002.

49. ITU-T Recommendation T.120, Data protocols for multimedia conferencing, 2007.

50. ITU-T Recommendation T.126, Multipoint still image and annotation protocol, 2007.

51. ITU-T Recommendation T.127, Multipoint binary file transfer protocol, 2007.

52. ITU-T Recommendation T.800, JPEG 2000 image coding system, 2000.

53. Juniper Networks Inc., Application note Juniper Network WX Client for Mobile and Small Office Users, 2009.

54. Kraft L.C. A Device for Quantizing, Grouping and Coding Amplitude Modulated Pulses // M.S. Thesis, Mass. Inst. Of Techn., Electr. Engin. Depart., 1949.

55. Lempel A., Ziv J., A Universal Algorithm for Sequential Data Compression.// IEEE Trans. Inform. Theory, vol. IT-23, no. 3, May 1977.

56. Lienau H.J., Hartmann K. Usage of an electronic document storage system for a press clipping documentation bank // Proc. Soc. Photo-Opt. Instrum. Eng. 1984. - Vol. 490. - P. 43 - 52.

57. Microsoft Corporation. Win32 Programmer's Reference Volume 5: Messages, Structures and Macros // Microsoft Press, Redmond, WA, 1993.

58. RFC 2394, IP Payload Compression Using DEFLATE, 1998.

59. RFC 2395, IP Payload Compression Using LZS, 1998.

60. RFC 3173, IP Payload Compression Protocol (IPComp), 2001.

61. RFC 3173, IP Payload Compression Protocol (IPComp), 2001.

62. Rissanen J., Landgon G.G., Arithmetic coding. // IBM J. Res. Dev., vol. 23, no. 2, pp. 149162, Mar. 1979.

63. Rissanen J., Landgon G.G., Universal Modeling and Coding // IEEE transactions on information theory, vol. IT-27, no. ljanuary 1981.

64. Scheifler, Robert W. and Gettys J. X Window System // Digital Press, Bedford, MA, 1990.

65. Serra J. Image analysis and mathematical morphology // Academic Press, 1983.

66. Shannon C.E. A mathematical theory of communication //Bell. System. Techn. J., 27, №3, 379-423, 1948.

67. Tuck B. Document ordering and delivery systems in Europe: Projects of the European Commission, services, conditions and prices // Elektronisches Publizieren und Bibliotheken. Frankfurt-am-Main: Vittorio Klostermann, 1996. - S. 58 - 69.

68. Witten I.H., Managing gigabytes: compressing and indexing documents and images //Academic Press, 1999.

69. Wood J.L. Document delivery and new technologies // Interlend. and Doc. Supply. 1983. -Vol. 11,N4.-P. 127- 130.