автореферат диссертации по радиотехнике и связи, 05.12.17, диссертация на тему:Гибридный метод компрессии изображений с масштабно-инвариантным декодированием

од

г Г

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

Приёмов Денис Георгиевич

ГИБРИДНЫЙ МЕТОД КОМПРЕССИИ ИЗОБРАЖЕНИЙ С МАСШТАБНО-ИНВАРИАНТНЫМ ДЕКОДИРОВАНИЕМ

Специальность: 05.12.17 — Радиотехнические и телевизионные системы и устройства

АВТОРЕФЕРАТ

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

Санкт-Петербург —1998

Работа выполнена в Санкт-Петербургском государственном электротехническом университете имени В.И.Ульянова (Ленина).

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

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

доктор технических наук, профессор Н.Н.Красильников; кандидат технических наук, доцент В.Н.Малышев.

Ведущая организация — Научно-исследовательский институт телевидения, г. Санкт-Петербург.

Защита состоится ч/б » _ 1998 г. в £ & часов на заседа-

нии диссертационного совета Д 063.36.03 Санкт-Петербургского государственного электротехнического университета по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке СПбГЭТУ.

Автореферат разослан « /К ¿Г 1998 г.

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

Егорова С.Д.

—1 —

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

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

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

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

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

Цель работы

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

Задачи исследования

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

2. Выделение характеристик объектов (моделей изображений), хорошо моделируемых каждым из методов в отдельности.

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

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

5. Экспериментальное исследование разработанного гибридного метода.

Методы исследования

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

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

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

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

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

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

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

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

Внедрение результатов работы

Основные теоретические и экспериментальные результаты работы использованы при выполнении НИР ГБ-2/ТУ/Т-9 и ГБ-2/ГР/Т-17.

Апробация работы

Основные положения и результаты диссертационной работы докладывались и Обсуждались на 49-й, 50-й и 51-й НТК ППС СП61ЭТУ в 1996, 1997 и 1998 годах; на научных семинарах института искусстве! шого интеллекта технического университета г. Дрездена (Германия) в 1996 и 1997 годах; международной научно-технической конференции "Цифровые технологии в кино и телевидении", Санкт-Петербург, 1996 г.

Публикации

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

Структура и объем работы

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

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

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

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

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

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

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

При ИК изображение представляется двумерной функцией /(х,у) е £?(Ш>2), принадлежащей классу непрерывных функций определенных

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

(ИФС).

Процесс вторичной дискретизации, называемый

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

' г /

г'тп =ХЕ2(/-—-),

кл +1 к„+1

т = 1,2,...,

Lkd +1.

, п -1,2,...,

J

fcrf+l.

где 5 - символ Кронекера; |_-J - округление до ближайшего целого не превышающего исходного значения; kd - коэффициент децимации, равный числу пропускаемых отсчетов. Декодирование в этом случае состоит в интерполяции образующейся сетки отсчетов. Для билинейной интерполяции процесс восстановления описывается формулой

/(*, у)» fix, = 4J) (* - Y (у - .V;)'.

i=0/=0

где а00' =гу,а0]-'=-а,у

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

2", для возможности выполнения вычислений с использованием только

целочисленных операций).

Выбор билинейной интерполяции был продиктован следующими причинами. Данный метод интерполяции, обладая минимальными временными затратами, позволяет достаточно точно восстанавливать НЧ-составляющую спек-

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

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

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

4от, - /и0 + 3

где ["■"] - округление до ближайшего целого не меньшего исходного значения; р - глубина квадродерева (0 <г < р)\ т, - число бит на представление блока на /-том уровне квадродерева; Лг( - число блоков на г'-том уровне. Данный критерий позволяет проверить эффективность структуры квадродерева с точки зрения обеспечения максимального коэффициента компрессии.

Далее в главе рассматриваются основные теоретические аспекты ФКИ Ставится задача фрактального моделирования, заключающаяся в представле-

Ый>

нии исходного сигнала х, принадлежащего пространству X с метрикой с/, аттрактором ха (неподвижной притягивающей точкой многомерного пространства) некоторого преобразования со: X X. Существование аттрактора гарантируется теоремой Банаха о сжатом отображении, ставящей в соответствие лю-

тивности) уникальную неподвижную точку хш-(о(х10). При моделировании аттрактора решается обратная задача, когда для имеющейся неподвижной точки находится соответствующее сжатое преобразование. Данная задача, известная в литературе под названием инверсной проблемы, не имеет однозначного решения, т.к. одному и тому же аттрактору может соответствовать множество отображений. Единственным ограничением на используемое преобразование является требование его нелинейности, поскольку любому линейному сжатому отображению соответствует нулевая точка. В ФКИ используются аффинные преобразования, т.е. отображения вида ах + р, а, ¡5 е К. Параметры аффинных отображений определяются с помощью субоптималыюго решения инверсной проблемы, даваемого теоремой коллажа. Теорема коллажа дает оценку верхней границы ошибки аттрактора d(x,xcl ) по отношению к моделируемому сигналу (точке в многомерном векторном пространстве) на основе ошибки коллажа d{x, ra(.v)), т.е. на основе разности между исходной точкой и ее отображением, а

именно, d{x, х0> )< (1 - s) 1 dix, й)(х)).

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

бому отображению с фактором Липшица 5 = sup

jrcX

Н4

< 1 (требование контрак-

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

где (у) - скалярное произведение и || - согласованная с ним норма; е, и е2

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

Непосредственный способ восстановления сигнала, представленного параметрами сжатого преобразования, основан на теореме Банаха. А именно, изображение декодируется последовательностью итераций преобразования хю х = (0°п(ху) от произвольной точки пространства с X (на практике Ху = 0). Данный метод декодирования, известный под названием детерминистического алгоритма, был использован в моделируемых методах компрессии пространственных сигналов. Поскольку изображение восстанавливается при конечном разрешении, число итераций также конечно (типичное значение 1020 итераций).

а =

(е!,е2)2 -Ы'Ы!2

Р =

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

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

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

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

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

1) большая вычислительная сложность кодирования и декодирования;

2) наличие блочных артефактов;

3) сравнительно большие затраты на представление информации.

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

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

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

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

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

Третий алгоритм классификации блоков основан на особенности аффинной аппроксимации, с помощью которой осуществляется векторное квантование при ФК. Процесс аффинной аппроксимации РБ можно интерпретировать

как проецирование вектора х на двумерное подпространство. Кодовое пространство в этом случае имеет размерность равную числу пикселей РБ. Фиксированный вектор постоянной составляющей е2 =1 и вектор е,, соответствующий децимированному ДБ, образуют аппроксимационное подпространство. С учетом контрактивности и допустимой ошибки аппроксимации совокупность доменов образует набор гиперпараллелепипедов, частично заполняющих кодовое пространство. Все гиперпараллелепипеды вращаются вокруг фиксированного вектора и, т.о., НЧ блоки оказываются представленными в избытке, а некоторые ВЧ, текстурные блоки не представлены вообще. Т.е., вероятность построения хорошей аппроксимации для фрактальных блоков резко убывает с увеличением размерности кодового пространства. Поэтому размер РБ является достаточно точной оценкой его принадлежности к ВЧ или НЧ области. А именно, чем больше размер РБ, тем выше вероятность того, что блок является топологическим. В данном алгоритме вводится дополнительный параметр, глубина переключения, определяющий размеры топологических и фрактальных блоков.

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

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

На этапе кодирования оба субкодера работают независимо. При декодировании, вследствие зависимости субкодеров, возникает проблема стыковки. Топологические области декодировались в первую очередь и затем итеративно

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

(е,,е2)

е. ->е,

2

1-2

После ортогонализации удается исключить перекрестное влияние базисных векторов на коэффициенты аффинной аппроксимации по яркости. В этом случае необходимую информацию можно получить из коэффициента ¡1, равного среднему значению РБ по яркости .г: Ъ (*'!> -

р = —— = х, при этом а = а.

й2

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

Была проведена теоретическая оценка вычислительных затрат адаптивной билинейной децимации и фрактального кодирования. При кодировании блока размера пхп пикселей в случае АБИ требуется САБИ = 4пг + 5п операций, а при ФК — СФК - 7Ы0п2, где N 0 - число блоков в доменом пуле. Т.о., СФК к1.75М0Саби , что в типичном случае при размере доменного пула в 9...36 блоков и учете 8 симметрий свидетельствует о более чем на два порядка меньшей сложности АБИ: САБИ « СФК. Аналогичное соотношение имеет место и при декодировании: С АБИ = 2п2 +4п и СФК = Ш,п2, где К, - число итераций в декодере, и, т.о., СФК к 4АГ,САБИ.

Сравнение количества бит, необходимых на представление блока обоими методами, показало преимущество БИ по отношению к ФК при моделировании топологических блоков. При выбранном количестве бит на представление коэффициентов аффинной аппроксимации по яркости в случае ФК требуется УФК =15 + 1о^2 бит, а в случае АБИ — VАШ = 8 бит. Т.е., VАШ < УФК при любом числе блоков доменом пуле.

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

1

/

0/ + l + zi0 +-J

I < i, j < и ,

где индексы i и j соответствуют локальным координатам обрабатываемого блока.

Для устранения блочных артефактов, возникающих при ФК, использовалось взвешенное усреднение граничных пикселей z, и z2:

zj —> z[ ~WtZt +h'2z2 и z2 —> z'2 =w2z, +w,z2. В зависимости от размера блока весовые коэффициенты изменялись.

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

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

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

PSNR{z,z') = - 201g*"

max z - mm 2

где z = {z, }"=] - исходный и z' = {z'}"=1 - восстановленный сигнал.

В качестве стандартных тестовых изображений использовались 2 изображения размера 256x256 и 6 изображений размера 512x512 пикселей.

На первом этапе эксперимента проводилось исследование влияния дополнительного параметра гибридного алгоритма, глубины переключения. При глубине переключения, равной минимальной глубине квадродерева, т.е., когда топологическими классифицируются блоки максимального размера 32x32 пикселя, происходит двух-трех кратное уменьшение времени кодирования и декодирования с сохранением точностных показателей аппроксимации по сравнению с эквивалентным методом фрактального кодирования. При увеличении глубины переключения на единицу, когда к топологическим блокам принадлежат блоки размера 32x32 и 16x16 пикселей, становится заметными потери точности и происходит уменьшение временных затрат в три-четыре раза. Так для тестового изображения Bird размера 256x256 пикселей при коэффициенте сжатия 82:1 фрактальный кодер при неперекрывающемся локальном доменном пуле размера 3x3 блока обеспечивает ПОСШ 25.65 дБ. В случае гибридного метода при аналогичных параметрах и минимальной глубине переключения ПОСШ снижается на 0.15 дБ, время кодирования уменьшается в 2.4 раза, а декодирования — в 3.4 раза; при увеличении глубины переключения на единицу ПОСШ снижается на 1 дБ, время кодирования уменьшается в 4.7 раза, а декодирования — в 4.4 раза. Т.о., незначительное уменьшение ПОСШ в случае гибридного метода сопровождается существенным выигрышем по временным затратам кодирования и декодирования.

Второй этап эксперимента заключался в проверке влияния размера доменного пула. Исследовались варианты с локальным пулом размера 3x3, 4x4 и 5x5 доменов. Для сохранения точностных показателей для дальнейших исследований глубина переключения была зафиксирована на уровне минимальной глубины квадродерева. В зависимости от класса изображения коэффициент компрессии изменялся от 20 до 200, а ПОСШ — от 35 до 24 дБ. Результаты эксперимента показали, что гибридный метод во всех случаях позволяет существен-

но снизить временные затраты кодирования и декодирования (в 2-5 раз), сохраняя практически неизменными показатели точности.

Т.о., экспериментально была доказана эффективность предложенного гибридного метода компрессии, сохраняющего свойство масштабной инвариантности фрактального декодера и позволяющего получить при значительных коэффициентах сжатия (от 40 до 200) и показателях точности восстановления 24...26 дБ ПОСШ сокращение временных затрат кодирования/декодирования в 2...5 раз по сравнению с эквивалентным методом фрактального кодирования.

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

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

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

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

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

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

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

1.5...4 раза) и декодирования (в 2...4 раза) по сравнению с эквивалентным фрактальным методом компрессии при незначительном уменьшении ПОСШ (0.2... 1%), проявляющееся лишь при больших коэффициентах сжатия (около 40...200), а также устранить блочные артефакты в низкочастотных фрагментах изображения.

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

1. Егорова С.Д., Приёмов Д.Г. Процедуры интерполяции для компрессии пространственных сигналов//Связь. Проблемы информатики: Сборник научных трудов. - Челябинск, 1995. - С.19-23.

2. Процедуры интерполяции в технологии преобразований пространственных сигналов/ Егорова С.Д., Приемов Д.Г., Мончак A.M., Леонов A.B. //Радиоэлектроника в Санкт-Петербургском государственном электротехническом университете: Сборник научных трудов. — Вып. 1. — СПбГЭТУ, 1995. — С.34-36.

3. Приёмов Д.Г. Метод фрактальной компрессии с неитеративным декодером //Пятая международная "Санкт-Петербургская Видеоярмарка". НТК "Цифровые технологии в кино и телевидении". Тез. докл. — 30 сентября - 3 октября 1996 г. — С. 63.

4. Egorova S.D., Priyomov D.G. Statistical coding of interpolation errors //Pattern Recognition and Image Analysis. — Vol.7, № 3. — 1997. — pp.369373.