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

РОССИЙСКАЯ АКАДЕМИЯ НАУК Ордена Ленина Сибирское отделение Вычислительный Центр

л ;* п

'Г 1 и

0.1

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

0 ;..;! Ь-.О

Бакланова Ольга Евгеньевна

УДК 081.3.06

ЭКСПЕРИМЕНТАЛЬНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПО СЖАТИЮ ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ И ЦВЕТНЫХ ИЗОБРАЖЕНИЙ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

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

Новосибирск, 1993

Работа выполнена в Вычислительном центре Сибирского отделения Российской Академии наук, г. Новосибирск.

Научный руководитель - доктор физико-математических

наук, профессор Василенко В.А.

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

Ведущая организация - Новосибирский институт инженеров геодезии, аэрофотосъемки и картографии

на заседании Специализированного совета по защите докторских диссертаций Д 002.10.02 при Вычислительном центре Сибирского отделения Российской Академии наук по адресу: 630090, г. Новосибирск-90, пр. Академика Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра СО РАН.

Автореферат разослан " /б " ___ 1993

наук, профессор Кузин В.И.

кандидат технических наук Перетягин Г.И.

Защита состоится

года.

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

Г.И. Забиняко

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

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

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

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

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

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

Пели работы состоят:

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

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

Научная новизна и практическая ценность работы.

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на Международном симпозиуме по численному анализу - 18КА-92 (Прага, 1992), на XXIV Региональной Математической молодежной школы-конференции (Екатеринбург, 1993), на XX Дальневосточной математической школе-семинаре им. академика Е.В. Золотова по проблемам математического моделирования и численного анализа (Находка, 1992), на VII Всесибирской школе по методам вычислительной математики (Красноярск, 1991), на VIII Всесибирской

школе по методам вычислительной математики (Шушенское, 1993), на III Региональной конференции по теории аппроксимации и задачам вычислительной математики (Новосибирск, 1991), на объединенном семинаре отдела математического обеспечения обработки изображений и отдела автоматизации проектирования и машинной графики ВЦ СО РАН под руководством профессора В.П. Пяткина (1993), на семинаре по пакетам прикладных программ ВЦ СО РАН под руководством профессора В.П.Ильина (1993).

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

Объем работы. Диссертационная работа состоит из введения, двух глав, заключения, списка литературы и трех приложений. Основной текст диссертации содержит 88 страниц, 26 рисунков и 3 таблицы. Список литературы включает 64 наименования. В приложениях (на компьютерной дискете) содержится 50 цветных иллюстраций.

Содержание работы

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

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

В параграфе 1.1 приводятся необходимые сведения из теории так называемой ЕП-аппроксимации. Общая идея

таких приближений состоит в замене с заданной точностью вещественной функции двух абстрактных переменных суммой произведений одномерных функций. Оптимизация этих приближений в среднем квадратичном рассматривалась для функций непрерывного или дискретного аргумента различными авторачми (Е.Шмидт, 1907, М.Р.Шура-Бура, 1957, В.В.Поспелов, 1978, Р.Л. Баглай и К.К.Смирнов, 1975). Наиболее общая постановка и вычислительный алгоритм решения даны В.А. Василенко в 1990 году.

Пусть и Y(Qy) - гильбертовы функциональные про-

странства на областях 0,х С R"1 и Qy С R"y. Через О обозначим декартово произведение хОу, а через Z(£l) - гильбертово пространство функций, являющихся тензорным произведением ) ® Y(ily). Требуется найти наилучшее приближение f(x,y) £ Z(Cl) функцией вида

$

¿ф

к = 1

где Ф(кЦх) и принадлежат конечномерным подпро-

странствам А'„(ПГ) и У„,(Пу) пространств и У(Оу) соот-

ветственно. .

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

'о F и = А " Л '0 ' и

F* 0 V 0 в V

где F - л х »»-¡матрица из элементов:

Jij = if(x,y)'<Pi(x)>l'j(y))z, 7

а матрицы А и В суть матрицы Грама базисных элементов <р{(х) и ф]{у) подпространств Х„ и Ут.

При этом для ошибки приближения справедливо равен-

ГТйп

41 = 11/111-¿А1 к = 1

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

Отметим, что функция / € Л',,(ПХ) ® Ут(Пу) может быть восстановлена с помощью ЕП-приближения точно; количество членов приближения при этом не может превышать величины тш{п, т}.

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

В параграфе 1.2 описывается реализация алгоритма на сплайновых зависимостях.

Пункт 1.2.1 посвящен реализации алгоритма на непрерывных сплайнах. В этом случае, подпространства Х„ и Ут тензорного произведения одномерных соболевских гильбертовых пространств объявляются пространствами одномерных полиномиальных сплайнов дефекта 1, либо их дискретных аналогов. Как известно, такие подпространства обладают удобным базисом из локальных 5-сплайнов. Это обеспечивает ленточность матриц Грама при реализации ЕП-алгоритма. В данном пункте приводится конкретная вычислительная схема, полученная на основе алгоритма ЕП-аппроксимации.

Пункт 1.2.2 диссертационной работы посвящен реализа-

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

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

В параграфе 1.3 описываются функциональные возможности комплектов программ РНЕ$8-^РЬ (сжатие непрерывных сплайновых зависимостей) и РЛЕ55_05РЬ (сжатие дис-

кретных данных).

• В комплекте РИЕЗЭ-^РЬ исходная информация подается в виде коэффициентов разложения двумерного сплайна по В-сплайнам любой степени. Задавал требуемый уровень точности в любой (а не только в допустимой гильбертовой кросс-норме, можно получить оптимальный ЕП-аналог двумерного сплайна, содержащий значительно меньшее число коэффициентов, чем в исходном сплайне. Данный комплект предоставляет пользователю дополнительные возможности по выполнению постобработки после сплайн-интерполяции данных.

« В комплекте программ РЛЕЗЗ-ББРЬ исходной информацией являются значения Д,-, заданные в узлах равномерной сетки. Этот комплект основан на применении ЕП-аппроксимации на дискретных сплайнах. Этот комплект интересен прежде всего при сжатии полутоновых и цветных изображений.

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

Основные результаты этой главы опубликованы в работах [2, 3].

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

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

Параграф 2.1 является обзорным и содержит описание некоторых известных цветовых моделей (стандарты МКО, PAL, SECAM, NTSC). Здесь приводятся матрицы преобразований и иллюстрации к разложениям PAL и NTSC. Особое внимание уделено (пункт 2.1.2) алгоритму JPEG, в последнее время ставшему в области сжатия цветных изображений общепринятым стандартом.

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

Пусть в цветовом пространстве RGB имеется палитра изображения 7Г/у:

7tn = {P¿ = (Rí.Gí, В,), i = 1,2, ...,ЛГ},

где Ri, Gi, Bi - компоненты вектора интенсивности красного, зеленого, синего цветов, соответствующие точке палитры. Определим так называемый "центр тяжести" - точку, минимально удаленную в среднеквадратичном смысле от точек палитры. Это будет вектор Р° с координатами

Д°=(5>)/ЛГ, B°=(¿B,)/.V.

i=i i=i i=i

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

Прямую Ь будем искать в виде

Ь = {Р £ Я3 : Р = Ро + Ьи, -оо < I < +оо},

где ^ - это вектор единичной евклидовой длины. Такая задача сводится к отысканию собственного вектора для 3 х 3-матрицы, отвечающего максимальному собственному значению. Ява других собственных вектора определяют оставшиеся факторы в разложении изображения. Уровень "важности" компонент, как мы предполагаем, регулируется соотношением А1 : : Л3.

В соответствии с этим трехфакторным анализом палитры цветное 1ШВ-изображение разлагается в 3 компоненты (ЗГА-разложение) , Р-л по следующему правилу:

/ л \ / «4'М / Л- \

с- 6'°

\ 'з/ \ 43)) \ в- /

Этот тип разложения цветного изображении будем называть ЗГА-стандартом [4].

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

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

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

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

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

Основные результаты этой главы опубликованы в работах [1,4].

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

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

2. На их основе создано программное обеспечение по сжа-

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

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

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

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

G. Создано экспериментальное программное обеспечение по сжатию цветных изображений. Проведены эксперименты по сравнению различных разложений для разных типов цветных изображений на 'эффективность их сжатии на основе алгоритма EÍI-апнроксймации. При этом продемонстрировано преимущество ЗГА-стандарта перед стандартом PAL.

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

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

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

Необходимые пояснения по использованию компьютерной информации даны непосредственно в тексте (см. Приложения 1-3).

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

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

ратории прикладного численного анализа ВИ СО РАН к.ф.-м.н. АЛО. Бежаеву и к.ф.-м.н. А.Ю.Шадрину за предоставление мне исходного программного обеспечения по сплайн-аппроксимации, которое после переработки стало частью комплекта РПЕББ-^РЬ. Я также благодарю к.ф.-м.н. А.И.Роженко за консультации при использовании ЬАТЕХ-макроса для оформления текста диссертации.

Список опубликованных работ по теме

[1] Baklanova О.Е., Vasilenko V.A. Colour roundoff via octree algorithm. -NCC Bulletin, series "Computer Sciences", 1993, issue 1. - NCC Publisher, Novosibirsk, p. 1-4.

[2] Baklanova O.E., Vasilenko V.A. Data compression with ЕП-approximations based on splines. - Aplikace Matematiky, special issue "Proceedings of the ISNA-92", 1993, Praha.

[3] Baklanova O.E., Vasilenko V.A. Data compression with ЕП-approxirnations based on splines. - NCC Bulletin, series "Numerical Analysis", 1993, issue 2. - NCC Publisher, Novosibirsk, p. 11-18.

[4] Baklanova O.E., Vasiienko V.A. Three-factors analysis of the computer paletta and compression of the colour images. - NCC Bul. letin, series "Computer Sciences", 1993, issue 2. - NCC Publisher,

Novosibirsk, p. 1-10.

Л,