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

Московский Государственный Университет им. М.В. Ломоносова

Механико-Математический Факультет

РГБ ОД

3 о ет т ■

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

Иванов Денис Владимирович

РАЗРАБОТКА МЕТОДОВ ПРЕДСТАВЛЕНИЯ РАСТРОВЫХ ДАННЫХ И ИХ ПРЕОБРАЗОВАНИЯ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

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

АВТОРЕФЕРАТ

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

Москва - 2000

Работа выполнена на кафедре вычислительной математики механике математического факультета Московского Государственног Университета им. М.В. Ломоносова.

Научные руководители проф., д.ф.-м.н. Михалёв A.B.

ст.н.с., к.ф.-м.н. Кузьмин Е.П.

Официальные оппоненты - проф., д.ф.-м.н. Шикин Е.В.

ст.н.с., к.ф.-м.н. Грибков И.В.

Ведущая организация - Институт Прикладной Математики

им. М.В. Келдыша РАН

Защита диссертации состоится «.^»^¿^Й^А^ОО! г. в 11 час. i заседании диссертационного совета Д 053.05.38 при факультете ВМи МГУ по адресу:

119899, г. Москва, Воробьевы Горы, МГУ, 2-й учебный корпу факультет ВМиК, ауд. 685.

С диссертацией можно ознакомиться в библиотеке фак-та ВМиК МГ

Автореферат разослан «.....>>_^£f^£sAV2001 г.

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

Н.П. Трифон

ШМЬ "0/Зс. О f МПШ-в/Ь п

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ етуальность темы.

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

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

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

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

Основные цели работы.

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

Научная новизна.

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

Также, разработаны эффективные методы преобразования растра ] указанным представлениям с учетом специфики их применения ] компьютерных системах. А именно, разработан алгоритм построения, ] при необходимости, упрощения линейных примитивов за один проход п< растру; предложен метод построения иерархии приближенны: изображений с использованием структуры бинарного дерева; разработа! алгоритм поиска локально наиболее характерных значений пикселей. Защищаемые положения.

На защиту выносятся следующие положения: 1. Новый алгоритм построения векторного представления растра

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

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

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

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

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

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

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

пробация и публикации.

Результаты работы докладывались на 8-ой, 9-ой и 10-ой [еждународных Конференциях по Компьютерной Графике и изуализации ГрафиКон (Россия, Москва, 7-11 сентября 1998 г., Россия, [осква, 26 августа - 1 сентября 1999 г., Россия, Москва, 28 августа - 2 гнтября 2000 г.), на ежегодной конференции Европейской Ассоциации омпьютерной Графики ЕигоОгарЫся (Швейцария, Интерлакен, 21-25

августа 2000г.), заседании кафедры вычислительной математик механико-математического факультета МГУ, научно-исследовательско семинаре по автоматизации программирования под руководством прос М.Р.Шура-Бура (ВМиК МГУ), семинаре по машинной графике обработке изображений (ВМиК МГУ), а также на заседании отде/ распознавания образов и обработки видеографической информаци НИИСИ РАН.

Основные результаты работы изложены в 5-ти научных публикациях,

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

Диссертация состоит из введения, трех' глав, заключения, спис! использованной литературы и приложений. Содержание работы изложен на 97 страницах. Список литературы содержит 42 наименования. В рабо" имеется 33 рисунка, 4 таблицы и 9 схем.

Благодарности.

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

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

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

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

2). использовании диаграммы Вороного или триангуляции Делоне;

3). анализе функций, построенных по изображению. Рассмотрение характеристик указанных методов приводит к выводу о

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

Во второй части дается формальное определение векторного редставления связной растровой области, называемое скелетом. Для того на растре рассматривается ортогональная система координат с зчалом отсчета в левом верхнем углу изображения. Каждый пиксел 1итается квадратом размером 2x2 (что позволяет далее оперировать элько с целочисленными координатами), углы которого соответствуют зчкам с четными целыми координатами, а стороны параллельны осям, асстояние между произвольными точками Р и <2 в данной системе лределяется формулой тах|рх ~0х\,\Ру

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

пределенне 2. Рельефом растровой области О. называется график ункции Оп(Р) (рис. 1).

(1)

Рис. 1. Рельеф растровой области

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

Определение 4. Объединение всех ребер рельефа называется хребто

растровой области.

Обозначая ребра рельефа как £,-,г = 1...л, хребет Я(£1) растровой облает

п

С2 определяется как

¿=1

Детальный анализ свойств определенных выше понятий позволя« доказать следующую теорему.

Теорема 1. Для произвольной 4-х связной растровой области С объединение дисков В({х,у),г) с центрами в точках проекции ее хребт Л(0) и радиусами, соответствующими расстоянию от центров до границь совпадает с исходной областью О, т.е. имеет место

!>((*,>;),>-)= П. т

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

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

2). Несвязность. Хребет рельефа растровой области не обязательк является связной структурой. Пример несвязного хребта показа на рис. 1.

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

)пределение 5. Скелетом £(£2) 4-х связной растровой области С1 :азывается объединение следующих множеств:

{£,-}/=1 т - множество всех неугловых ребер рельефа О;

{Ту}.,] ! - множество верхних концов угловых ребер рельефа О;

С - минимальное множество точек рельефа, такое что проекция

объединения (3) является 8-ми связным множеством.

\ (

и с

(3)

S(Q)= \}Е, U [JTJ

\i=1 / W=! /

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

)пределение 6. Для 4-х связной растровой области Q и ее пиксельной троки, рассматривается ассоциированная с ней система координат с ачалом на этой линии (рис. 2а). Обозначая диск с центром в {х,у) и

адиусом г как В((х,у),г), и рассматривая функцию

[ шах ¿и: В({х, у), у) с П}, (х,0) е Q [О, (*,<>)* О

ордой данной строки называется график функции F(x). >пределение 7. В условиях определения 6 рассмотрим вертикальную олосу S, ограниченную растровым сегментом следующей строки (рис. б), и функцию

(шах {у : В((х, у), у) с Д Г) S}, (*,0) е Q П S [o,(x.o)enns

(граниченной хордой строки называется график функции F(x).

F(x)-

(4)

F(X)-

(5)

хорда

Ограниченная хорда

(а) (б)

Рис. 2. Хорда и ограниченная хорда строки растровой области

N

Важность рассмотрения хорд для отыскания скелета облает устанавливается следующими утверждениями.

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

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

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

Схема 1

Псевдокод алгоритма отыскания скелета растровой области Chord = Empty;

while ( Line = NextLine() ) {

BoundedChord = BoundChord( Chord, Line );

Chord = ConstructChord( BoundedChord, Line );

J_

На схеме 1 используются следующие обозначения.

Chord, BoundedChord представляют хорду и ограниченную хорд; соответственно. Хорды задаются массивами узлов, упорядоченных е возрастанию х-координаты (в системе координат, связанной с текуще растровой строкой).

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

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

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

Сопз1:гисЪСЬог<1 () - процедура построения хорды растровой строки з ограниченной хорды предыдущей. Все имеющиеся узлы сдвигаются огласно строго определенным правилам. При этом анализируются точки хождения узлов, символизирующие точки ветвления частей скелета.

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

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

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

1). Количество вычислений линейно зависит от количества точек исходной ветви скелета;

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

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

один проход по растру получать уже упрощенное векторно представление его областей.

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

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

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

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

Для компактного хранения ветвей полученных скелетов предлагаете использовать технику цепного кодирования. Идея данного метода состой в представлении полилинии с помощью начальной точки последовательности сдвигов, символизирующих относительные смещени между точками. Так как ветви скелета есть 8-и связные линии, т существует всего 8 возможных сдвигов на плоскости. Также, необходим хранить изменения высот, которые могут быть ±1 или 0. В совокупное! имеется 8x3=24 варианта, число которых можно сократить до 15, есл

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

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

На схеме 2 показано сравнение степеней сжатия для роизводственного чертежа размером 3648x2890. Стандартные метода катия растра, такие как PCX и GIF, а также оптимизированный для санера метод TIFF, имеет худшие характеристики чем цепное здирование скелета, дополненное стандартным частотным кодирование э методу Хаффмана. Последующее упрощение скелета приводит к зеличению степени сжатия еще в несколько раз.

Схема 2

Сравнение степенен сжатия чертежа

250 ■

200 -150 -100 -50 40

□ PCX (RLE)

□ TIFF (CCITT3-1dim) STIFF (Huffman)

□ Цепной код

□ GIF (LZW)

□ Цепной код + Huffman DTIFF (CCITT3-2dim)

□ Упр. полилинии

□ Упр. пол. + Huffman

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

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

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

1). Чередование пикселей (как это делается в GIF и PING);

2). S-преобразование и его улучшенный вариант - SPIHT1;

3). Использование вейвлетов.

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

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

В работе определяются следующие понятия. Определение 8. Допустимым отображением (р отрезка [0,l] называет! его непрерывное отображение в множество действительных чисел, такс что ^([0,1])с [0,1] и [O,l]\ç>([O,l])*0.

Определение 9. Для произвольного отрезка [a,b\ и его линейно! отображения /:/([a,è])=[0,l], произвольное допустимое отображения <р i [a,b\ определяется как Ç[ab\{x) = /"' °ç> °l(x), х е \a,b\.

1 Set Partitioning In Hierarchical Trees

14

пределение 10. Объединение тождественного / и конечного числа шустимых <pv..(pN отображений называется сжимающей схемой, если для эбого £>0 и для любой точки Pe[0,l] найдется конечная »следовательность отображений еТ, такая что

s [а, Ь\ = <ри о... о <piu ([o,l]) и \а, Ь\<£.

Примеры сжимающих схем указаны в формулах (6) и (7). Ч*, задает :ему бинарного поиска, a Tj определяет 3-х зонную схему.

Т, -L :„(10,.1).[0../2] <6) > ' f /д1 (7)

[i?3:«33([0,lj)=[l/2,lj

На основе сжимающих схем разрабатывается рекурсивная процедура ¡строения бинарного дерева по изображению. Значение интенсивности 1кселей (для полутоновых изображений) рассматривается как 3-я юрдината. Параллелепипед П = + width)x [у, у + height)х [с, с + depth), раничивающий изображение, считается соответствующим корню :рева. Алгоритм формирования узла дерева состоит из следующих гераций:

1). Выбрать (Pi из сжимающей схемы, так что 11 = (р, (П) = [х,х + width) х\у,у + height) х ср. ([с, с + depth)) является ограничивающим;

2). Если <z?(([с,с + depth)) содержит только одно дискретное значение интенсивности, то остановиться;

3). Сформировать П] и Пг делением П пополам по оси х либо у. Перейти к п. (1) для П) и П2.

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

Для хранения дерева в файле (наборе данных с последовательным >ступом) требуется определить отношение строгого порядка между ¡лами. Такое отношение должно, очевидно, сохранять иерархию >дитель-потомок, что необходимо для правильной реконструкции :рева. Стандартным в таком контексте является упорядочивание по

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

Промежуточные изображения формируются по текущему дере заполнением прямоугольников, соответствующих основани; ограничивающих параллелепипедов П, =[х!,х! +й()х[с„с1 + с1

значением с,+¿,/2. Так как значения интенсивностей пикселей лежат объединении всех П,,г'=1 ...М, то имеет место верхняя оценка ( отклонения от оригинала в терминах среднеквадратической ошиб: (МБЕ).

МЖ({П,.})< Л/Жтах({П(}) = -^-|:к2 • -и), (8)

где N — количество пикселей в изображении.

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

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

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

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

10; фг-10; ф3 -111.

В четвертой части проводится сравнительный анализ полученных зультатов с точки зрения степени сжатия и отношения качества омежуточных изображений к объему данных. Из таблицы 1, на которой иведены степени сжатия для изображения «Лена», видно что бинарное рево, построенное на основе 3-х зонной сжимающей схемы, приводит к зультату, сравнимому со SPIHT.

Таблица 1

Сравнение степеней сжатия для изображения «Лена»

Алгоритмы сжатия Размер (бант)

SPIHT (+арифм. код.) 42140 (65%)

3-х зонное дерево 46847 (71%)

PING (черед., LZW) 47383 (72%)

Без кодирования 65536 (100%)

PCX (RLE) 73088 (1 12%)

GIF (LZW) 74206 (113%)

Схема 3 характеризует зависимость качества приближенных ображений от объема данных, необходимых для их восстановления, [чество приближения к оригиналу измеряется в терминах РБЫК1. :обходимо заметить, что алгоритм БРШТ является оптимальным по ому параметру в своем классе методов сжатия.

1 Peak Signal-to-Noise Ratio

Схема

Зависимость качества приближенных изображений от степени сжати:

п_«

--1 -1

------^ t -0-SPIHT —*-3-х зонное дерево —S-преобразование —в—Чередование

S———*— 1 1

в ------ "*"" *

--1-:-1-1-

5% 10% 15% 20% 25% Степень сжатия

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

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

В первой части анализируются существующие методы блочш декомпозиции растра, как обладающие указанными свойствами поэтому, применяемые в современных системах. К таким метод; относятся: (1) TREC (Microsoft Corp.); (2) S3TC (S3, Inc.); (3) FXT1 (3d Interactive, Inc.). TREC использует косинус-преобразование, аппаратн реализация которого относительно сложна, a S3TC и FXT1 основаны формировании небольших непересекающихся палитр для блоков разме 4x4 или 4x8 пикселей. Для повышения степени сжатия, указанные мето/

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

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

пределенне 12. Локальным окружением блока называется квадратный загмент блоков (обычно 2x2 или 3x3), включающий данный, пределенне 13. Шаблоном локальной палитры данного блока зывается матрица размера, соответствующего локальному окружению, нулевые элементы которой указывают на относительное ¡сторасположение блоков, используемых при формировании локальной литры.

В третьей части рассматривается одна из возможных реализаций зработанного подхода, называемая узловой схемой, в предположении ее ибольшей практической значимости. В данной реализации изображение збивается на блоки размером 4x4 пикселя и в каждом узле разованной решетки сохраняется одно значение (рис. 3). Таким разом, для каждого блока палитра формируется из 4-х значений, ответствующих углам, а каждый узел используется в 4-х близлежащих оках. Так как локальная палитра состоит из 4-х значений, то каждый [ксель представляется 2-мя битами. В работе приведен алгоритм кодирования произвольного пикселя изображения.

4x4 пикселя 2 бит/пиксел

Рис. 3. Узловая схема хранения значений для локальных палитр

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

Вводятся следующие понятия:

X - данное цветовое метрическое пространство с метрикой р(у);

Г = {/,,..t, eS - изображение размера N с элементами из

Р = {р1,...,рм}, pt eS - палитра для представления изображения;

б{1,...,Л/} - заданные ограничения палитре. Каждому элементу изображения ставится в соответств непустое (I. >1) множество индексов {г,',...,/^ }, соответствующих ячейк; палитры, которые могут участвовать в представлении tr Определение 14. Кодированием данного изображения Т при помо1 палитры Р и набора ограничений R называется изображение T(T,P,R) процесс преобразования), такое что f( = pm, где

Определение 15. Ошибкой кодирования Е изображения Т при помо! палитры Р и набора ограничений Я называется суммарная усредненн ошибка в каждом пикселе, то есть

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

m = arg min p(t, ,pk).

(9]

(10

итру Р соответствующего размера, так что е{г,Т{Т,Р,R))->min. Для ее аения разрабатывается алгоритм с фиксированным числом шагов, орый часто не достигает теоретического минимума ошибки ;ирования. Однако, на практике различия визуально незаметны, а 1ественная оптимизация скорости исполнения дает основание сделать >од об эффективности разработанного метода для решения указанной ачи.

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

изменение качества изображений при сжатии; (3) скорость становления произвольного пикселя.

Анализ показал, что при статистически одинаковой скорости становления пикселей, узловая схема позволяет формировать альные палитры из 4-х независимых значений, тогда как при S3TC нятся только 2 значения, а остальные линейно интерполируются, ой подход, на практике, приводит к меньшему ухудшению качества тых изображений с точки зрения визуального восприятия. Степень тия в случае узловой схемы составляет 8:1, тогда как для S3TC тот же аметр равен 6:1. Таким образом, совокупность указанных свойств овой схемы блочной декомпозиции, а также простота алгоритма становления пикселей позволяет использовать данный метод в £ических ускорителях.

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

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

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

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

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

Основные положения работы изложены в следующих публикациях:

1. Иванов Д.В., Кузьмин Е.П. Эффективный алгоритм построения octoi растрового изображения // Труды конференции ГрафиКон'98: 7-1 сентября 1998. - Москва: МГУ, 1998. - С. 65-70.

2. Ivanov D., Kuzmin Е., Burtsev S. Progressive image compression usir binary trees // Proceedings of GraphiCon'99: 7-11 September 1999. Moscow: MSU, 1999.-PP. 187-194.

3. Ivanov D., Kuzmin E., Burtsev S. An efficient integer-base skeletonization algorithm // Computer & Graphics. — Elsevier Scienc 2000. - 24. - 1. - PP. 41-51.

4. Ivanov D., Kuzmin E. Color Distribution — a new approach to textu: compression // Proceedings of EuroGraphics'2000: 21-25 August 2000. Interlaken, 2000. - PP. C-283-289.

5. Ivanov D., Kuzmin E. Color Distribution for compression of textural data Proceedings of GraphiCon'2000: 28 August - 2 September 2000. Moscow: MSU, 2000. - PP. 134-139.

Введение.

Глава 1. Векторное представление растровых данных.

1.1. Основные методы векторизации.

1.2. Формальное определение скелета растровой области.

1.3. Построчный алгоритм отыскания скелета.

1.4. Упрощение и фильтрация скелета растровой области.

1.5. Анализ алгоритма векторизации.

Глава 2. Иерархическое представление растровых данных.

2.1. Иерархические методы представления растра.

2.2. Представление с помощью бинарных деревьев.

2.3. 3-х зонные бинарные деревья.

2.4. Анализ полученных результатов.

Глава 3. Блочная декомпозиция изображений.

3.1. Основные методы блочной декомпозиции.

3.2. Метод локальных палитр.

3.3. Узловая схема представления локальных палитр.

3.4. Алгоритм отыскания глобальной палитры.

3.5. Сравнение узловой схемы с представлением S3TC.

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

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

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

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

Для изображений, имеющих векторную природу, проблема состоит в отыскании его векторного представления, которое позволяет не только существенно уменьшить объем данных, но также использовать такие изображения в системах автоматизированного проектирования и производства (САПР), географических информационными системах (ГИС), и других системах анализа и обработки векторной информации. Для решения поставленной задачи, на протяжении десятилетий были разработаны и реализованы многочисленные методы, в целом основанные на 3-х различных подходах, состоящих в: (1) моделировании распространения "фронта огня" [28,42]; (2) построении диаграммы Вороного [6,34]; (3) исследовании графиков специальных функций [8,14].

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

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

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

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

Существующие подходы, очевидно, опираются на иерархические структуры данных. Так, наиболее эффективный алгоритм прогрессивного кодирования, использующий так называемое S-преобразование [3 8], последовательно строит набор изображений меньшего разрешения сходясь к одному пикселю на вершине иерархии, при этом сохраняя при каждом преобразовании дополнительную информацию для восстановления оригинала. Тем не менее, при прогрессивном декодировании, промежуточные, приближенные изображения имеют блочную структуру и не учитывают состав исходных данных, что часто приводит к неудовлетворительному зрительному восприятию. Для того, чтобы адаптировать процесс передачи данных с учетом структуры изображения, был разработан существенно улучшенный вариант того же алгоритма (названный SPIHT [37]), основанный на сложной перегруппировке данных после S-преобразования с целью передачи наиболее важных, насыщенных информацией, фрагментов в первую очередь. Данный подход можно рассматривать оптимальным в своем классе, однако он достаточно сложен в реализации.

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

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

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

Удовлетворяющие указанным требованиям методы, такие как S3TC [36] и FXT1 [17], основаны на блочной декомпозиции растра, однако, в некоторых случаях приводят к существенному, заметному пользователю, искажению качества изображения. Другой предлагаемый метод, TREC [41], достаточно сложно реализуем в реальных условиях из-за использования дискретного косинус-преобразования.

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

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

Основные цели работы.

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

Научная новизна.

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

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

Защищаемые положения.

На защиту выносятся следующие положения:

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

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

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

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

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

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

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

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

Результаты работы докладывались на 8-ой, 9-ой и 10-ой Международных Конференциях по Компьютерной Графике и Визуализации ГрафиКон (Россия, Москва, 7-11 сентября 1998 г., Россия, Москва, 26 августа - 1 сентября 1999 г., Россия, Москва, 28 августа - 2 сентября 2000 г.), на ежегодной конференции Европейской Ассоциации Компьютерной Графики EuroGraphics (Швейцария, Интерлакен, 21-25 августа 2000г.), заседании кафедры вычислительной математики механико-математического факультета МГУ, научно-исследовательском семинаре по автоматизации программирования под руководством проф. М.Р.Шура-Бура (ВМиК МГУ), семинаре по машинной графике и обработке изображений (ВМиК МГУ), а также на заседании отдела распознавания образов и обработки видеографической информации НИИСИ РАН.

Публикации.

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

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

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

Основные результаты данной главы были получены в ходе выполнения исследований в рамках соглашения с компанией Intel Technologies, Corp. и опубликованы в [21,24].

3.1. Основные методы блочной декомпозиции

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

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

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

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

1). обеспечивать высокую степень сжатия;

2). не вносить существенных визуальных искажений;

3). обеспечивать максимально эффективное декодирование;

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

Очевидно, что существующие методы сжатия изображений (JPEG,

PCX, GIF, PING [4,31] и др.) не удовлетворяют последнему требованию, так как используют методы динамического сжатия данных, такие как RLE, LZW, Хаффмана [1,39]. Те подходы, которые удовлетворяют всем вышеперечисленным требованиям можно разделить на две группы: (1) векторная квантизация (VQ) и палитры [15]; (2) блочная декомпозиция и блочные преобразования [33].

Векторная квантизация основана на построении словаря, состоящего из наиболее часто встречающихся блоков небольшого фиксированного размера (обычно 2x2 или 3x3). Далее, каждый блок изображения заменяется подходящим индексом, соответствующим элементу словаря наиболее качественно приближающего исходный фрагмент. Таким образом, для достижения хорошей степени сжатия словарь должен быть небольшим, и обычно имеет 128 или 256 ячеек. Если рассматриваются блоки размера 1x1, то словарь называется палитрой.

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

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

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

1). Texture and Rendering Engine Compression (TREC) [41];

2). S3 Texture Compression (S3TC) [36];

3). 3dfx Texture Compression (FXT1) [17].

TREC был разработан компанией Microsoft и основан на кодировании блоков размера 8x8 пикселей с помощью стандартного косинус-преобразования (аналогично тому как это делается при кодировании JPEG) и последующей специально подобранной квантизации. Однако, косинус-преобразование является относительно сложным с вычислительной точки зрения, и поэтому TREC практически не применяется на практике.

S3TC оригинально был разработан компанией S3, и затем был лицензирован Microsoft для использования в своем графическом интерфейсе DirectX [13]. Этот метод оказался очень эффективным с практической точки зрения и был аппаратно реализован в графическом ускорителе Savage2000 фирмы S3. Он кодирует блоки размера 4x4 пикселя путем формирования локальной палитры из 4-х элементов для каждого отдельного блока. Два элемента палитры в формате RGB565 непосредственно хранятся в блоке, а два других вычисляются с помощью линейной интерполяции (см. рис. 3.1). Каждый пиксель заменяется 2-х битовым индексом элемента в палитре. Следовательно, каждый блок представлен 4x4x2=32 битами индексов и 16x2=32 битами палитры, что обеспечивает степень сжатия 6:1.

Представление блока Восстановленная палитра

Color 00

01 00 01

N» РЛ 00 01 "idir. -.:■; 1

00 01 i»4H '*'*. 00 ■ниш flfl у 00

Color 00

Color 01

ColorOl = (2*Color00 + Colorl 1)/3 Color 10 = (ColorOO + 2*Colorl 1)/3

Рис. 3.1. Кодирование блока изображения с помощью S3TC Метод FXT1 был разработан компанией 3dfx. Он использует ту же схему, что и S3TC, но имеет несколько модификаций, позволяющих также кодировать блоки размера 4x8 пикселей с помощью восстановленных палитр размера 4 и 8 ячеек. За счет большего количества вариаций FXT1 позволяет получать лучшее качество выбирая наиболее подходящую модификацию в каждом случае. Тем не менее, для RGB (24 бита) изображений степень сжатия также равна 6:1.

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

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

3.2. Метод локальных палитр

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

Определение 3.1. Локальной палитрой для данного блока изображения (растрового изображения) называется множество цветов, используемое для представления элементов этого блока.

Оригинал

Кодирование S3 ТС

Рис. 3.2. Потеря качества при кодировании S3TC

Определение 3.2. Локальным окружением блока называется квадратный фрагмент блоков (обычно 2x2 или 3x3), включающих данный.

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

Возможные примеры локальных окружений и шаблонов показаны на рис. 3.3. а) б) в) - Текущий блок - Локальное окружение | - Шаблон локальной палитры

Рис. 3.3. Примеры локальных окружений и шаблонов Таким образом, каждый блок может быть представлен одним цветом, шаблоном локальной палитры (если она отличается от блока к блоку) и соответствующим набором индексов для каждого пикселя. Это позволяет получать для каждого блока 4 или 8 уникальных цветов, что повышает качество закодированного изображения. Если же шаблон одинаков для всех блоков изображения, то нет необходимости его хранить, и наряду с индексами в блоке хранится только один цвет вместо двух, как это делается в S3TC случае.

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

3.3. Узловая схема представления локальных палитр

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

Рис. 3.4. Ассоциирование цветов с узлами решетки разбиения Так как шаблон локальной палитры одинаков для всех блоков, то в блоке хранятся только данные одного цвета (обычно RGB565) и шестнадцать 2-х битовых значений индексов, что в сумме дает 6 байт на один блок. Следовательно, степень сжатия составляет 8:1, что больше чем тот же показатель у S3TC.

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

Схема 3.1

Алгоритм декодирования произвольного пикселя

RGB565 DecodeTexel( int х, int у ) { Ыоскх = х/4; Ь1оску = у/4; index = GetBlocklndex( Ыоскх, Ыоску ) ; index = ExtractTexellndex( index, х%4, у%4 ) ; if ( index&l ) Ыоскх++; // индекс равен 1 или 3 if ( index&2 ) blocky++; // индекс равен 0 или 2 return GetColor( blockx, block у ); }

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

3.4. Алгоритм отыскания глобальной палитры

Если рассмотреть задачу отыскания наиболее репрезентативных цветов для узлов решетки в узловой схеме кодирования изображений с точки зрения квантизации цветов [18,19,25] (отыскания палитры, словаря), то поставленную проблему можно переформулировать следующим образом. Для заданного изображения из N элементов требуется найти глобальную палитру размера N/16, такую что каждый ее элемент может быть использован для представления не более чем 64-х соответствующих пикселей. Далее мы рассмотрим итеративный алгоритм, который явно устанавливает ограничения на элементы палитры (здесь и далее термин палитра употребляется в смысле глобальной палитры, то есть совокупности всех ячеек используемых хотя бы в одной локальной палитре). Некоторые идеи предлагаемого метода берут свое начало из так называемого алгоритма Итеративного Условного Выбора (Iterative Conditional Mode) [11,16,20,26].

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

Так же предполагаем, что цветовая информация представлена тремя RGB компонентами в 3-х мерном цветовом пространстве. Однако, любые цветовые пространства и метрики (например, CIE [12]) могут быть с успехом применены.

Введем следующие обозначения:

X - данное цветовое метрическое пространство с метрикой р(у);

Т = {tv.,tN}, t; eZ - изображение размера TV с элементами из

Р = рм], Pi е£ - палитра для представления изображения;

R = {Rl,.,RN},Ri = \rll,.,r^\r'f е{\,.,М} - заданные ограничения на палитре. Каждому элементу изображения tf ставится в соответствие непустое (Z; >1) множество индексов }, соответствующих ячейкам палитры, которые могут участвовать в представлении tr

В случае узловой схемы блочной декомпозиции каждое ограничение Rt состоит ровно из 4 элементов (Ц=4), соответствующих углам блока 4x4; каждый элемент палитры pt используется ровно в 64 ограничениях, а размер палитры равен N/16.

Определение 3.4. Кодированием данного изображения Т при помощи палитры Р и набора ограничений R называется изображение f(T,P,R) (и процесс преобразования), такое что ti=pm, где т = arg minp(ti,pk). (3.1)

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

Определение 3.5. Ошибкой кодирования Е изображения Т при помощи палитры Р и набора ограничений R называется суммарная усредненная ошибка в каждом пикселе, то есть

3.2)

1=1 iv /=1

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

E(r,f(T,P,R))^> min.

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

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

Для множества ограничений R можно ввести набор двойственных i jf. jj,. i ему ограничений R = ,.,RM /, которые будут определять для каждого элемента палитры те пикселы, которые могут быть закодированы с помощью данной ячейки. То есть ieR)<=>jERr (3.3)

Ik к = 0.М - множества, определяющие в каждый момент работы алгоритма, какие ячейки палитры уже заполнены финальными значениями, а какие нет. Множество NSk состоит из индексов элементов палитры Р, которые не установлены в окончательные значения, а множество Sk содержит индексы элементов, содержащих финальные значения. До начала работы алгоритма ни одна ячейка не установлена, и, следовательно, NS0 = {О.М] , a S0 = 0 . Далее, на каждом шаге устанавливается ровно одна ячейка, и соответствующий элемент переводится из NSk в Sk. По окончании работы NSo = 0 и S0 = {O.M} . Очевидно, верно NS0 з NSi id . з NSM и S0 с S, с. с SM.

- множество ошибок представления каждого пиксела только с помощью элементов из Sk на каждом шаге и с учетом ограничений R. Ошибки вычисляются по формуле min pit,, р: \ если R, f]St JeWk J , где (3.4) максимальное значение, иначе к за максимальное значение берется, максимально возможное значение разности двух цветов (рассматриваются ограниченные цветовые пространства и подходящие метрики). В начале работы алгоритма все равны максимальному значению. sfef,.,dskMk \ - множество возможных изменений средней ошибки в случае, если соответствующий элемент из NSk будет установлен и переведен в Sk. Каждое изменение вычисляется по формуле d£t= t Е^-^яа))- (3.5) j^R*:p{tj,Pi)<ekj

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

До начала итераций требуется установить следующие величины к = 0; NSk = {0.M} ; Sk=0; sf, i = l.N присвоить максимальные значения;

Pi=tj:j = argmm £/>(*„ieNSK; (3 6ч leRi meR* V ' ' установить def, i = l.M согласно формуле (3.5); далее выполнять

1. Если к=М, закончить.

2. Найти / = arg max dsf .

3. NSk+l=NSk\ty}; SM=Sk\jty}.

4. Найти sf+l, i = I.N согласно (3.4).

5. Найти р;, i e NSk+l согласно (3.6).

6. Найти de\+x согласно (3.5).

7. k = k +1.

8. Перейти к п. 1.

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

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

Следует заметить, что в случае узловой схемы все элементы множества ограничений R состоят в точности из 4-х номеров ячеек палитры, а элементы двойственного множества R* содержат по 64 номера пикселей каждый. Следовательно, вычисления в пунктах 4,5,6 алгоритма отыскания цветов палитры следует осуществлять только для тех величин, которые могли измениться с переводом соответствующего элемента палитры в разряд определенных. А именно, требуется пересчитать для 64-х пикселей, окружающих установленный узел разбиения, а отыскание новых возможных кандидатов в еще не определенные ячейки палитры и вычисление соответствующих изменений ошибок dsf+] необходимо произвести не более чем в 8-ми соседних узлах. Таким образом, количество вычислений на каждом шаге не превышает некоторого значения, не зависящего от размеров изображения, и, следовательно, время работы всего алгоритма линейно зависит от количества итераций, которое в точности равно количеству пикселей исходного изображения.

Заключение

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

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

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

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

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

2. Иванов Д., Кузьмин Е. Эффективный алгоритм построения остова растрового изображения // Труды конференции ГрафиКон'98: 7-11 сентября 1998. Москва: МГУ, 1998. - С. 65-70.

3. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. - 478 с.

4. Мюррей Д.Д., Райпер У. Энциклопедия форматов графических файлов: Пер. с англ. К.: Издательская группа BHV, 1997. - 672 с.

5. Blum Н., Nagel R. Shape description using weighted symmetric axis features // Pattern Recognition. 1978. - 10. - PP. 167-180.

6. Bookstein F.L. The line-skeleton II Computer Graphics and Image Processing. 1979. - 11. - 2. - PP. 123-137.

7. Borgefors G. Distance transformations in arbitrary dimensions // Computer Vision, Graphics and Image Processing. 1984. - 27. - 3. -PP. 321-345.

8. Borgefors G. Distance transformations in digital images. // Computer Vision, Graphics and Image Processing. 1986. - 34. - PP. 344-371.

9. Borgefors G. Distance transformation on the hexagonal grid // Pattern Recognition Letters. 1989. - 9. - PP. 97-105.

10. Brandt J.W., Algazi V.R. Continuous skeleton computation by Voronoi diagram // Computer Vision, Graphics and Image Processing. 1992. - 55. - 3. - 329-338.

11. Buhmann J., Fellner D., Held M., Ketterer J., Puzicha J. Dithered Color Quantization // Proc. of EuroGraphics, 1998. 17.- 3.

12. C.I. de L'Eclairage. Colorimetry. CIE pub. 15.2 2nd ed., 1986.

13. Compressed Texture Formats. Microsoft DirectX 7.0, Platform SDK, MSDN. Microsoft, 1999.

14. Deseilligny M.P., Stamon G., Suen C.Y. Veinerization: A new shape description for flexible skeletonization // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1998. - 20. - 5. - PP. 505-221.

15. Effelsberg W., Stainmetz R. Video Compression Techniques: From JPEG to Wavelets. Morgan Kauffman Publishers, 1998. - 126pp.

16. Flohr Т., Kolpatzik В., Balasubramanian R., Carrara D., Bouman C., Allebach J. Model Based color image quantization // Proc. of the SPIE: Human Vision, Visual Processing, and Digital Display IV, 1993. 1913. - PP. 265-270.

17. FXT1: White Paper. 3dfx Interactive, Inc., 1999.

18. Gervauz M., Purgathofer W. A simple method for color quantization: Octree quantization // Graphic Gems. Academic Press, New York, 1990. - PP. 287-293.

19. Heckbert P. Color Image Quantization for frame buffer displays // Computer Graphics. 1982. - 16. - 3. - PP. 297-307.

20. Heitz F., Perez P., Bouthemy P. Multiscale minimization of global energy functions in some visual recovery problems // CVGIP: Image Understanding, 1994. 59. - 1. - PP. 125-134.

21. Ivanov D., Kuzmin E. Color Distribution a new approach to texture compression // Proceedings of EuroGraphics'2000: 21-25 August 2000. - Interlaken, 2000.

22. Ivanov D., Kuzmin E., Burtsev S. Progressive image compression using binary trees // Proceedings of GraphiCon'99: 7-11 September 1999. Moscow: MSU, 1999. - РР 187-194.

23. Ivanov D., Kuzmin E., Burtsev S. An efficient integer-based skeletonization algorithm // Computer & Graphics. Elsevier Science: 2000. - 24. - 1. - PP. 41-51.

24. Ivanov D., Kuzmin E. Color Distribution for compression of textural data // Proceedings of GraphiCon'2000: 28 August 2 September 2000. - Moscow: MSU, 2000. - PP 134-139

25. Jain A., Dubes R. Algorithms for clustering data. Prentice Hall, 1998.

26. Ketterer J., Puzicha J., Help M., Fischer M., Buhmann J., Fellner D. On spatial quantization of color images // Proc. of the European Conference on Computer Vision, 1998.

27. Lee D. Medial axis transformation on a planar shape // IEEE Transactions on Pattern Recognition and Machine Intelligence. -1982. 4. - 4. - PP. 363-369.

28. Leymarie F., Levine M.D. Simulating the grassfire transform using an active contour model // IEEE Transactions on Pattern Recognition and Machine Intelligence. 1992. - 14. - 1. - PP. 56-75.

29. Martinez-Perez M.P., Jimenez J., Navalon J.L. A thining algorithm based on contours. // Computer Vision, Graphics and Image Processing. 1987. - 39. - PP.186-201.

30. Mestetsky L. The continuous skeleton of the digital binary image // Proceedings of the Graphicon'98: 7-11 September 1998. Moscow, 1998. - PP. 71-78.

31. Miano J. Compressed image file formats: JPEG, PNG, GIF, XBM, BMP (ACM Press). Eddison-Wesley Pub Co., 1999. - 264 pp.

32. Muller D.E., Preparata F.P. Finding the intersection of two convex polyhedra // Theoretical Computer Science. 1978. - 7.- 2. - PP. 217-236.

33. Nelson M., Gailly J. The Data Compression Book. IDG Books Worldwide, 1995.

34. Sayood K. Introduction to Data Compression, Second Edition. -Morgan Kauffman Publishers, 2000. 600 pp.

35. Shapiro В., Risa J., Sklansky J. Skeleton generation from x,y boundary sequences // Computer Graphics and Image Processing. -1981. 15. - 2. - PP. 136-153.

36. TREC: White Paper. Microsoft Corporation, 1998.

37. Xia Y. Skeletonization via the realization of the fire front's propagation and extinction in digital binary shapes // IEEE Transactions on Pattern Recognition and Machine Intelligence. -1989. 11. - 10. - PP. 1076-1086.