Разработка методов представления растровых данных и их преобразования в вычислительных системах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Иванов, Денис Владимирович

• Иванов, Денис Владимирович
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Иванов, Денис Владимирович

Введение.

Глава 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. Разработанный метод представления изображений с фиксированной степенью сжатия позволяет осуществлять быстрый доступ к произвольным элементам растра. Алгоритм восстановления элементов изображения оптимизирован для аппаратного использования в графических ускорителях.

Список литературы диссертационного исследования кандидат физико-математических наук Иванов, Денис Владимирович, 2001 год

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.