Введение к работе
стуальность темы.
С расширением сферы применения компьютерной техники методы
ализа и обработки растровых изображений, полученных при помощи тройств цифрового ввода, приобретают особенную важность. В данном нтексте, проблема компактного представления или, другими словами, :атия таких данных является чрезвычайно актуальной.
Сжатие растровых данных возможно в случае наличия в них ределенных закономерностей, таких как последовательные повторения инаковых пикселей, неравномерность гистограммы значений или малые личия соседних пикселей друг от друга. Применение методов, нованных на выявлении таких закономерностей, во многих случаях иводит к уменьшению объема данных. Однако, существенно лучших епеней сжатия для определенных классов изображений можно достичь пользуя свойства, связанные с их природой.
Свойства изображений традиционно делятся на векторные и стровые. Примерами изображений, имеющих векторную природу, могут ужить полученные с помощью сканера чертежи, карты и планы. Эти ображения могут быть описаны в терминах векторных примитивов, ких как точка, отрезок, окружность и т.п. С другой стороны, ітографические изображения и текстуры характеризуются яркостью, нтрастностью, наличием областей с гладкими изменениями значений кселей. Использование таких особенностей позволяет не только еличить степень сжатия по сравнению с универсальными методами, но кже повысить эффективность дальнейшего использования еобразованных растровых данных в соответствующих компьютерных стемах их обработки.
Следует также отметить, что многие алгоритмы сжатия' растра 'Иводят к незначительному ухудшению качества изображений, однако я данных, полученных «большой ценой», такие изменения допустимы. Таким образом, с внедрением компьютерной техники в
решение все большего числа задач, разработка методов сжатия растровы: данных, в том числе и без потери качества изображений, на основі свойств, связанных с природой этих данных, приобретает все большук актуальность.
Основные цели работы.
Целью диссертационной работы является разработка методов сжати: растровых данных на основе использования свойств, связанных с и: природой, а также оптимизация указанных методов с учетом спецификі их применения в компьютерных системах.
Научная новизна.
В диссертации разработаны оригинальные способы представлена растровых данных, позволяющие сжимать изображения за сче-использования их векторных и растровых свойств. Разработанньи представления также позволяют обрабатывать указанные изображени: соответственно в терминах планарных графов, иерархии приближенны: изображений и. локально наиболее характерных наборов значенні пикселей.
Также, разработаны эффективные методы преобразования растра і указанным представлениям с учетом специфики их применения і компьютерных системах. А именно, разработан алгоритм построения, і при необходимости, упрощения линейных примитивов за один проход П( растру; предложен метод построения иерархии приближенны: изображений с использованием структуры бинарного дерева; разработаї алгоритм поиска локально наиболее характерных значений пикселей. Защищаемые положения.
На защиту выносятся следующие положения: 1. Новый алгоритм построения векторного представления растра
оптимизированный для аппаратной реализации в средствах ввод;
изображений.
. Новый метод иерархического представления растра,
оптимизированный для потоковой передачи изображений по
компьютерным сетям. . Новый метод представления изображений с фиксированной степенью
сжатия, оптимизированный для аппаратной реализации в графических
ускорителях.
Практическая значимость работы.
Разработанное взаимно-однозначное описание растровых областей на ;нове планарных графов позволяет оперировать с ними в терминах янейных примитивов. Алгоритмы построения указанного представления его последующего упрощения в силу своей эффективности по времени и імяти могут применяться как в качестве элементов отдельного риложения, так и в качестве компонент системы обработки векторной зафики, а также могут быть реализованы аппаратно в средствах ввода істровьіх данных.
Предложенный подход использования структуры бинарного дерева для редставления изображений может применяться для иерархического писания растра. Разработанный в данной работе способ позволяет не злько эффективно сжимать фотографические изображения, но и рогрессивно передавать их по соединениям удаленного доступа.
Разработанный метод использования перекрестных локальных палитр эзволяет обеспечить фиксированную степень сжатия и произвольный эрядок доступа к элементам изображения, что необходимо при сжатии петровых данных, используемых в графических ускорителях.
пробация и публикации.
Результаты работы докладывались на 8-ой, 9-ой и 10-ой [еждународных Конференциях по Компьютерной Графике и изуализации ГрафиКон (Россия, Москва, 7-11 сентября 1998 г., Россия, [осква, 26 августа - 1 сентября 1999 г., Россия, Москва, 28 августа - 2 гнтября 2000 г.), на ежегодной конференции Европейской Ассоциации омпьютерной Графики EuroGraphics (Швейцария, Интерлакен, 21-25
августа 2000г.), заседании кафедры вычислительной математик механико-математического факультета МГУ, научно-исследовательско семинаре по автоматизации программирования под руководством прос М.Р.Шура-Бура (ВМиК МГУ), семинаре по машинной графике обработке изображений (ВМиК МГУ), а также на заседании отде/ распознавания образов и обработки видеографической информаци НИИСИ РАН.
Основные результаты работы изложены в 5-ти научных публикациях,
Структура и объем работы.
Диссертация состоит из введения, трех' глав, заключения, списі использованной литературы и приложений. Содержание работы изложен на 97 страницах. Список литературы содержит 42 наименования. В рабе имеется 33 рисунка, 4 таблицы и 9 схем.
Благодарности.
Автор выражает огромную благодарность своим научны руководителям - д.ф.-м.н. Михалеву Александру Васильевичу и к.ф.-м. Кузьмину Евгению Павловичу за постоянное внимание к исследования по теме данной диссертации, а также за неоценимую помощь подготовке необходимого материала.
