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

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

Носков Алексей Борисович

СИСТЕМА ПРЕДИКАТИВНОГО СЖАТИЯ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ НА ОСНОВЕ ЕЕ ПРЕДСТАВЛЕНИЯ В ВИДЕ ПОЛЕВОЙ СТРУКТУРЫ

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

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

САНКТ-ПЕТЕРБУРГ 2004

Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича.

Научный руководитель: к.т.н, проф. Ю.Ф. Болтов

Оффициальные оппоненты: д.т.н, проф. В.М. Дегтярев

к.т.н, доц. А.Г. Буткарев

Ведущее предпрятие: СПбГЭТУ «ЛЭТИ»

Защита диссертации состоится »^Й^^&у "20(У/г. в >7 Тна заседании диссертационного совета К 219.004.0 Г при/банкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191186 Санкт-Петербург, наб. р. Мойки, 61.

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

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

Автореферат разослан 200Уг.

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

X. Харитонов

Подписано к печати 28.10.2004 Объем 1 печ. л. Тираж 80 экз. Зак.

Тип. СПбГУТ. 191186 СПб, наб. р. Мойки, 61

2-0Р6-4-(198

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

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

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

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

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

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

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

- вероятностная оценка эффективности разделения исходного изображения на предикативное и остаточное поле;

- построение адекватной алгоритмической и программной модели;

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

изображений.

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

РОС. НАЦИОНАЛЬНАЯ БЧЬ.ПИОТЕКА

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

3. Усовершенствовать (увеличить конкурентоспособность) системы сжатия визуальной информации, решаемая в двух аспектах:

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

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

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

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

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

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

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

5. Введение «поля цветности», которое в сумме с частным решением уравнения Пуассона в первом приближении соответствует общему решению, существенно приближает предикативное поле к исходному изображению.

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

7. Метод сжатия, основанный на полевой модели, является более универсальным, чем, например, метод JPEG или GIF.

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

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

Научная новизна. Показатели, характеризующие данную работу с точки зрения новизны:

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

2. Осуществлен переход для обобщенных функций от непрерывной модели к цифровой;

3. Произведены вероятностные оценки данного способа сжатия;

} 4. Построена алгоритмическая модель сжатия, основанная на разделении

изображения на две составляющие, каждая из которых сжимается отдельно;

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

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

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

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

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

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

вершенствования модели и понимания основ концепции предикативных методов сжатия графической информации. Результаты диссертационной работы используются в лекционных и лабораторных занятиях по специальности 220400 «Программное обеспечение вычислительной техники и автоматизированных систем», в НИРС № 190-93-54 (раздел «Разработка алгоритмов сжатия информации для передачи по каналам связи») и УИРС.

Апробация работы. Результаты работы докладывались на конференциях: 5-я ГСЫАБ (СПб, 1998), 51 - 54-я НТК (СПбГУТ, 1998 - 2001). Алгоритмы данной системы использованы при создании системы телеконференций в ООО НПФ «Беркут» (акт внедрения от 18.05.2004).

Публикации. По материалам диссертации опубликовано 9 печатных работ.

Объем и структура диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы из 48 наименований и 9 приложений. Основная часть изложена на 120 страницах машинописного текста, имеет 28 рисунков и 13 таблиц. Общий объем приложений составляет 250 страниц А4.

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

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

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

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

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

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

Также в этой главе кратко описываются характеристики основных форматов хранения и сжатия изображений: TIFF, GIF, JPEG, BMP.

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

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

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

максимально возможному сжатию.

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

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

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

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

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

Если имеется непрерывная функция, описывающая исходное изображение U(x,y), то его можно разделить так:

U(x,y)=bU(x,y) + Uu„,

где Ьи(х,у) - остаточное (плавное) поле;

^ист = ¡¡8(х< У'£> 5) * /(*> у,Е,£,)дед!; (1)

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

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

Функция Грина является решением уравнения Пуассона, где в правой части стоит дельта-функция.

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

81(х,у,хО,уО)=]п((х-хО)2+(у-уО)2У(4хп), где хО,уО - координаты особой точки.

Функция Грина для непрерывного поля, расположенного относительно начала координат (лЮ^уО), имеет вид:

(Нх-хЬу- уО) = + = ~ -л .у- У0) + к2Оу(х -хО,у- уО), (2)

(х-хОу +(у-уО) ) 2я

где к\икг - проекции нормали к линии контура на оси X и У.

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

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

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

Как показали тесты, построенная цифровая модель имеет существенные недостатки:

• погрешность в 10% в окрестностях особой точки;

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

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

Формула улучшенной цифровой модели:

2%'-' х2 + (у-у0) (х-хО) +у2 где х2 = х-х0-0.5 + -—^^—, у2 = у-у0-0.5 +——; и(х,у)ю- поле источников; &их(х0,у0),А[/у(х0,у0)-разницы значения полей в особой и предыдущей точках вдоль осей X и У; суммирование производится по всем особым точкам.

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

Применял (3) без учета поправочного коэффициента (считаем, что он неизвестен), построено остаточное поле. Далее меняя значения поправочного коэффициента с, исследуется изменение фона изображения на границе поля источника. Ищется такое с, при котором переход в фон на границах поля происходит наиболее плавно.

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

Из построенной таблице видно, что наименьшая разница на границе поля достигается при с в диапазоне от 0.06 до 0.07. Проводя дальнейшие эксперименты с помощью программного моделирования и добавляя еще несколько типов изображений (например, точка и квадрат), получаем наиболее «плавное» поле во всех случаях, если с=0.068.

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

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

п_с

Минф=-2>г1о&2(Р/)> Ы

где п_с - число возможных состояний; р, - вероятность г-го состояния.

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

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

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

Требования, предъявляемые к первоначальной модели:

должна экспериментально проверить правильность предложенной концепции, что должно было определить дальнейший ход всей работы;

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

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

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

- вычисления особых точек и их процентного соотношения от их общего числа;

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

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

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

- распространена эта процедура, в которой фигурируют функции с разрывами, на дискретное пространство;

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

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

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

Глава 3. Система сжатия должна удовлетворять основным требованиям:

- строиться по образу практической системы сжатия;

I - содержать компоненты, позволяющие проводить на ее основе разнооб-

разные исследования по теме диссертационной работы.

Исходный материал построения замкнутой системы:

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

- математическая (макроподход) и алгоритмическая модели подсистемы сжатия цепочек источников, разработанные в СПбГУТ;

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

- открытые коды JPEG для сжатия остаточного поля.

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

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

- стать промежуточным этапом при разработке усовершенствованной системы сжатия;

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

Результаты исследования на данном этапе:

1. Разработана схема сжатия и восстановления изображений.

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

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

4. В систему включены коды JPEG и ZIP, что дало возможность сделать ее замкнутой.

5. Исследования по качеству и величине сжатия, проведенные на разработанной системе:

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

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

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

В главе 4 рассмотрены два варианта усовершенствования системы сжатия на основе полевой модели с улучшением предикативного поля.

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

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

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

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

В этой модели поле внутри зоны: и, = ахХ + рхУ + ухЛ'хУ, где постоянные определяются из средних значений градаций цветности в соседних зонах.

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

Эксперимент, результаты которого приведены в диссертации, выполнен для идеального поля особых точек, при этом предикативное поле, интерпрети-

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

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

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

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

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

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

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

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

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

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

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

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

Сама подсистема построения контурной структуры на основе кромок разработана в рамках НИР № 190-93-54 и внедрена в систему предикативного сжатия изображений, представленных в виде полевой структуры.

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

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

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

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

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

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

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

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

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

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

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

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

Конечный результат диссертационной работы получен на основе следующих решенных задач.

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

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

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

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

Параметры Ajpeg, âgif и Крсв - обозначают степень сжатия методов указанных в индексах (PCB - разработанный метод сжатия). Из представленной диаграммы видно, что наибольшего преимущества метод предикативного сжатия на основе представления изображения в виде полевой структуры достигает на изображениях близких к цветовым схемам, сохраняя требуемую резкость, чего не дает JPEG. В тех фотографиях, где контур составляет большую часть изображения, предлагаемый метод также дает значительное преимущество. Все изображения, используемые в эксперименте подобраны так, чтобы остаточное поле получалось наиболее «чистым», поскольку мелкие алгоритмические ошибки в программной системе сжатия исправить в рамках данной работы не представляется возможным, в то время как они серьезно влияют на качество восстановления.

Показатели сжатия методами JPEG, GIF и PCB для различных типов изображений

1200,00

400.00

Степень сжатия

цв фото и рисунки

цв чертежи

ч/б чертежи

типы изображений

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

• Первоначальная модель системы сжатия.

• Промежуточная программная система сжатия.

• Программа расчета поля цветности для «улучшения» остаточного поля.

• Иллюстрации к эксперименту по использованию «поля цветности» для тестового изображения.

• Процедуры формирования, сжатия и восстановления кромки.

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

• Конечная, улучшенная система сжатия.

' • Тестовые изображения на различных этапах сжатия-восстановления.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

1. Носков А Б и др. Сжатие графической информации на основе представления изображения в виде полевой структуры // Труды учебных заведений связи / СПбГУТ, 1998. № 164. С. 88.

2. Носков А Б. и др. Концепция сжатия графической информации на основе представления изображения в виде полевой структуры // 5-я ICNAS: сб. докл. / ЛОНИИС. СПб, 1998.

3. Носков А.Б. и др. Алгоритм компрессии и декомпрессии графической информации, представленной в виде полевой структуры // 52 НТК: тез. докл. / СПбГУТ, 1999. С. 36.

4. Носков А.Б. Построение TCP/IP стека для обучающих целей //51-я НТК: тез. докл. / СПбГУТ. СПб, 1998. С. 117.

5. Носков А.Б. и др. Разработка подсистемы сжатия информации в виде упорядоченных цепочек // 52-я НТК: тез. докл. / СПбГУТ. СПб, 1999. С. 36.

6. Носков А.Б. Построение системы сжатия графической информации для передачи по каналам связи с помощью протокола TCP/IP в режиме реального времени // 52-я НТК: тез. докл. / СПбГУТ. СПб, 1999. С. 38.

7. .Носков А Б. Разработка Интернет-приложения с использованием предикативного метода сжатия графической информации // 2-я Межд. НТК «ТЕХНИКА И ТЕХНОЛОГИЯ СВЯЗИ» / СПбГУТ. СПб, 2000. С. 32.

8. Носков А.Б и др. Система предикативного сжатия изображения на основе полевой модели // Труды учебных заведений связи / СПбГУТ. СПб, 2000. № 166. С. 36.

9. Носков А.Б. Применение метода сжатия информации в виде полевой структуры для передачи изображений в режиме реального времени по Интернет // 53-я НТК' мат-лы / СПбГУТ. СПб, 2000. С. 21.

t

V

!

РНБ Русский фонд

2006-4 1198

О. Í

J 9 НОЯ 2004