Читайте также:
|
Для сжатия используется преимущество трёх обобщённых свойств графических данных: избыточность, предсказуемость и необязательность.
1 алгоритм сжатия – алгоритм Хаффмана.
Использует предсказуемость, основан на кодировании битовыми группами. Перед началом кодирования происходит частотный анализ кодов цветов, выявляется частота кодов каждого. Чаще всего встречаемый цвет кодируется меньшим количеством бит. Результат – иерархическая структура, прикладывается к сжатому файлу в качестве таблицы соответствия. Поэтому на файлах малого размера алгоритм не эффективен. В чистом виде на практике не применяется.
Пример:
| Цвет | Частота, % | Код | Размер, бит |
Нельзя использовать код на основе одного нуля, т.к. он будет совпадать с начальной частью других, более длинных кодов. Здесь 5 байтов сжимаются в 14 битов + таблица. Т.е. в среднем на различных изображениях размер результирующего изображения будет на 40% меньше исходного.
Алгоритм группового кодирования (RLE).
Использует избыточность данных. Работает по принципу выявления повторяющихся последовательностей данных и замены их простой структурой с коэффициентом повтора.
Пример:
0; 0; 0; 127; 127; 0; 255; 255; 255; 255
0; 3; 127; 2; 0; 1; 255; 4
Алгоритм LZW.
Использует избыточность данных, но процедура сжатия сложнее, чем в RLE. Метод основан на поиске шаблона внутри изображения и сохранении их. По алгоритму считываются значения цветовых кодов рисунка, и строится таблица кодов повторяющихся пиксельных узоров. Каждое повторением заменяется ссылкой на первое появление. В среднем, алгоритм сжимает до 1/3 первоначального размера файла. Можно сжать и до 1/10, если рисунок достаточно насыщен.
Алгоритм JPEG.
Использует свойство необязательности данных. В отличии от предыдущего сжимает с потерями.
Этапы сжатия:
- преобразование цвета – процесс подвыборок. Т.к. человек изменение цвета замечает хуже, чем изменение яркости, в изображении выделяется канал яркости. Уже после этого размер файла уменьшается, хотя это ещё не сжатие.
- запись информации о быстроте изменения яркости в виде изменения частот с помощью дискретного косинусного преобразования. Оно применяется для каждой пиксельной компоненты выбранной области 8х8 или 9х9. Разница между пикселями записывается в виде матрицы коэффициентов.
- усреднение частот в соответствии с плавающей шкалой относительной влажности – регулирование потери;
- сжатие методом Хаффмана усреднённых данных. Здесь тоже потери, т.к. результат округляется до ближайшего целого.
При восстановлении – всё в обратном порядке.
Наиболее эффективная аппаратная реализация алгоритма сжатия. Программная реализация занимает больше времени.
Достоинства:
- возможность управлять процессом сжатия для достижения приемлемого уровня потерь.
Форматы графических данных
Существует несколько десятков форматов, но лишь часть из них стала стандартами. Различают растровые, векторные форматы и метафайлы. Часто в собственных приложениях используются свои форматы, которые наиболее эффективны для данных приложений. Например, CDArr для CorelDraw. Однако их могут не знать другие приложения, либо не будут эффективными.
Примеры растровых форматов: bmp, jpeg, gif.
1. bmp – аппаратно независимый аппаратный формат винды. Расширение файлов – bmp и dip. Удобен, прост. Большой размер файла.
2. gif – был разработан для обмена графикой пользователей сети ComputeCerf. Был стандартизирован в 1977г. Сжатие по lzw. Достоинства – поддержка любыми платформами, использование в инете. Недостатки – малое количество цветов.
4. tif – разработан как универсальный открытый формат, допускающий модификации фирмами Microsoft, Aidus. Сжатие по lzw. Достоинства – мультиплатформенность, удобство, высокое качество, межплатформенная переносимость. Недостатки – большой размер и модификации.
5. jpeg – формат, который программно реализует алгоритм сжатия. Не зависит от программных и аппаратных средств. Коэффициент сжатия от 0.1 до 0.01.
Примеры векторных графических форматов: hpjl, dxf
1. hpjl – один из основных языков программного проектирования. Используют для вывода на принтеры и плоттеры. Расширение файла – pgl. Оригинальный формат очень прост, использовался для первых плоттеров. Сейчас применяется модифицированный формат hpgl/2/. Используется большинством программ САПР на PC, настольными издательскими системами, некоторыми векторными редакторами.
2. dxf – формат обмена рисунками. Векторный, поддерживаемый всеми САПР начиная с AutoCad и заканчивая Compas. Но из-за его сложности некоторые могут только читать dxf-файлы. Сердце элементов содержит описание всех объектов. Описываются они соответствующими числовыми и ASKII кодами.
Примеры форматов типа метафайл: sjm, eps, vmf, pict
Формат метафайл – разновидность векторных форматов, описывает рисунки в векторном виде, но также может обрабатывать растровые изображения и текст. Состоит кроме описания изображения из команд интерфейса и графических устройств, создавших изображение и выводящих его. Обеспечивает независимость от устройств, средства хранения и выборки графических изображений. Типичный носитель данного формата – это языки описания графики в составе страниц документа. Целью их создания была разработка языка, описывающего структуру изображения документа с текстовой графикой, независящего от устройства вывода. Их команды – часто вызов модулей, выполнение которых зависит от предыдущих команд, определяющих среду, в которой рисуется фигура.
Пост-скрипт – 1 из наиболее популярных и сложных языков данного типа. Он содержит расширяемый словарь команд. Применяется в частности для кодирования шрифтов масштабируемых шрифтов. Лазерные принтеры, фотонаборные автоматы и другие устройства высокого класса получают от компьютера информацию в виде программы на пост-скрипт. Растровый процессор интерпретирует язык и выполняет растеризацию изображения.
CGM – используется для переноса данных на другие платформы, т.к. платформы независимы. … – новая версия данного формата, которая делает его универсальным для использования. Использует векторные редакторы, САПР и издательские пакеты.
IPS – формат описания как векторных, так и растровых изображений на языке пост-скрипт фирмы AdobeSystems в сотрудничестве с фирмой AltSize.
Т.к. пост-скрипт универсальный язык, то в файле может храниться как растровая, так и векторная графика (шрифты, маски, параметры калибровки оборудования, контуры затравки, цветовые профили). Для отображения на экране векторного содержимого – формат WML. Для растрового – tif. Но экранная копия лишь в общих чертах отображает реальное изображение. Это относится к недостаткам.
WMF – для обмена растровыми векторными рисунками между приложениями OS и Windows. Подходит для хранения векторных и растровых файлов с последующей печатью. Представляет собой набор команд, участвующих в создании изображения.
PICT – для использования в маках. Большую часть формата занимают вызовы процедур бла бла бла. Расширение для PC платформ – pct.
Загораживание
Проблема удаления невидимых линий возникла ещё в процессе визуализации каркасных изображений на векторных дисплеях. Для растровых дисплеев при создании реалистичных картин проблема существует больше как удаление скрытых поверхностей, т.е. выявление всех её видимых участков для отображения на экране монитора или на листе бумаги.
В алгоритме Унчи обычно предполагают расположение экранов в проекционной плоскостью z=0, со сценой позади его и центром проекции перед экраном. Тогда при проецировании 3Д объектов видимыми будут те точки на объекте, которые вдоль направления проецирования расположены ближе к картине.
Несмотря на кажущуюся простоту установки, нет универсального решения задачи загораживания: высокопроизводительного, универсального алгоритма Унчи.
Выбор конкретного алгоритма в существенной степени зависит от характера решаемой задачи. Например, для задачи реального времени, требуются быстрые алгоритмы даже в ущерб некоторого качества. Для создания качественных статических рисунков можно использовать менее быстродействующие алгоритмы.
Известные методы решения задач загораживания различаются между собой по 4 характеристикам:
- выбор структуры данных для представления поверхности объектов;
- способ визуализации поверхности;
- использование специфических геометрических свойств объектов изображения или сцены в целом;
- пространство работы алгоритма.
1. Поверхность можно описать аналитической, полигональной или полиномиальной сеткой.
2. Визуализировать можно только каркас изображаемой поверхности, а можно её закрасить, наложить текстуру или узор.
3. Примеры использования геометрических свойств объектов:
- для выпуклых многогранников или гладких несамопересекающихся поверхностей алгоритмом загораживания можно воспользоваться когерентностью по видимости: у них нет частичной видимости граней; при наличии приоритетов в сцене для обработки данных ею пользуются в алгоритме; если можно поделить сцену на отдельные независимые части, то обработку каждой части выполняют отдельно (можно параллельно).
4. Разделение видимых и невидимых элементов сцены можно осуществить как в пространстве объекта, так и в пространстве изображения.
Алгоритмы, работающие в пространстве объекта, имеют дело с системой координат, в которой он описан. Каждый n-й элемент сцены сравнивается с оставшимися n-1 элементами. Объём вычислений пропорционален квадрату числа элементов в сцене (
. Точность вычисления ограничена размером ячеек памяти компьютера. В качестве элемента выступает, например, ребро или грань.
Алгоритмы, работающие в пространстве изображения, работают в приборной системе координат экрана, т.е. где отображаются. Объём вычислений пропорционален
где n – количество элементов сцены;
N – разрешение экрана (количество пикселей).
Точность вычислений ограничена разрешением экрана. Последние алгоритмы более эффективны, т.к. для них легче воспользоваться преимуществом когерентности при растровой реализации.
Дата добавления: 2015-01-07; просмотров: 33 | Поможем написать вашу работу | Нарушение авторских прав |