Компьютерная графика лекция. Компьютерная графика русс лекц. Тема Введение. Знакомство с программой Corel Draw. Запуск интерфейса. Знакомство с трехмерной сценой
 Скачать 0.66 Mb.
|
Тема 13. Сжатие данных. Алгоритмы сжатия изображений.Для получения растровых изображений фотографического качества требуется высокое разрешение. Это, в свою очередь, сказывается на размерах графических файлов, требующих (если не предпринимать специальных мер) для своего хранения от нескольких единиц до нескольких десятков мегабайтов памяти. Единственный выход из положения — сжатие информации. Алгоритмы сжатия изображений. Поскольку любой используемой нами информации (в том числе и графической) свойственна избыточность (осо- бенно огромным видеофайлам), сжатие позволяет значительно уменьшить ее объем. Степень сжатая может колебаться от 4:1 до 200:1 — это зависит от типа данных и применяемого алгоритма. Более чем пятидесятикратное сжа- тие можно применять для звуковых или видеофайлов, но оно связано с поте- рей качества. Существует множество разных алгоритмов сжатия, учитываю- щих те или иные особенности сжимаемой информации. Однако алгоритма, одинаково хорошо сжимающего файлы любых форматов, пока не создано. С самых общих позиций все существующие алгоритмы сжатия можно разбить на два больших класса: сжатие с потерями; сжатие без потерь. Сжатие без потерь. Большинство схем сжатия без потерь основано на поиске в растровом изображении повторяющихся пиксельных узоров. Такой узор можно запомнить один раз и впоследствии повторить его необходимое количество раз. Подобные схемы сжатия полностью — пиксел за пикселом восстанавливают исходное изображение. При этом в исходных данных ничего не отбрасывается и не теряется. Метод сжатия без потерь (например, используемый в форматах GIF или TIFF) очень эффективен для растровых рисунков, содержащих большие области однотонной закраски, или повторяющихся растровых узоров. В таких случаях чаще всего достигается коэффициент сжатия 10:1. В основе алгоритмов сжатия без потерь лежат несколько методов. Рассмотрим наиболее распространенные из них. Метод сжатия RLE (run length encoding) — кодирование с переменной длиной с троки. Этот алгоритм является одним из простейших. В основе его принципа действия заложен механизм поиска одинаковых пикселов в одной строке. Алгоритм RLE хорошо работает с искусственными картинками и плохо — с фотографиями. В действительности, если фотография детализирована, RLE может даже увеличить размер файла. В настоящее время этот алгоритм используется для сжатия информации в PSD-формате. Сжатие с потерями. Как уже отмечалось, использование алгоритмов сжатия без потерь оказывается неэффективным для растровых изображений фотографического качества, в которых каждый пиксель отличается от соседних. Применение механизма сжатия узоров к изображениям, на которых повторяющихся узоров нет. часто приводит к ничтожным результатам при больших затратах времени. Сжатие с потерями, наоборот, лучше всего работает с теми изображениями, на которых нет повторяющихся узоров или больших областей однотонной закраски. В растровом рисунке, который содержит множество слегка отличающихся друг от друга пикселов (например, 100 немного отличающихся оттенков голубою цвета неба), большие области могут заполняться пикселями одного цвета или пиксельным узором, имитирующим вид исходной области. Ключевым моментом в применении сжатия с потерями является определение «приемлемою уровня» потерь. Уровень этот субъективен и зависит от изображения-оригинала и от того, как он будет использоваться. Если ваше оригинальное изображение — фотография музейного качества, предназначенная для публикации в высокохудожественном издании, то ни о каких «приемлемых потерях» не может рыть и речи. Рисунок должен быть воспроизведен как можно точнее. Другое дело электронная публикация на Web-странице, где одним из главных критериев является малый размер файла. В настоящее время создано несколько алгоритмов сжатия с потерями, самым известным и; которых является JPEG. В последнее время создан новый алгоритм сжатия — WI (Wavelet Compressed Bitmap), в котором применяется схема сжатия, близкая к схеме сжатия JPEG. Однако в основу его работы заложено использование нового и очень перспективного математического аппарата — вейвлетов. Пока «на официальном» уровне этот алгоритм поддерживается только продуктами фирмы Corel. JPEG. На сегодняшний день формат JPEG (Joint Photographic Experts Group) является одним из наиболее распространенных графических форматов для сжатия файлов. Как уже отмечалось, в нем реализован алгоритм сжатия с потерями. Это означает, что в процессе сжатия изображения происходит частичная потеря хранящейся в файле информации. Поэтому в процессе применения этой процедуры сжатия приходится искать, компромисс между степенью сжатия и качеством сохраняемого изображения. Чем больше сжатие, тем ниже качество, и наоборот. Строго говоря, JPEG не формат, а алгоритм сжатия, в основе которого лежит не поиск одинаковых элементов, как в случае RLE и LZW, а поиск разницы между пикселями. Кодирование данных с помощью используемого в JPEG алгоритма сжатия осуществляется в несколько этапов. Сначала графические данные конвертируются в цветовое пространство типа LAB. Затем отбрасывается половина или три четверти информации о цвете (в зависимости от реализации алгоритма). Далее анализируются блоки размером 8x8 пикселов. Для каждого блока формируется набор чисел. Первые несколько чисел представляют цвет блока в целом, в то время как последующие числа отражают тонкие делали. Поскольку спектр деталей базируется на зрительном восприятии человека, то крупные детали более заметны. На следующем этапе в зависимости от выбранного вами уровня качества, отбрасывается определенная часть чисел, характеризующих тонкие детали. На последнем этапе используется кодирование методом Хаффмана для более эффективного сжатия конечных данных. Алгоритм сжатия Хаффмана (Huffman) разработан еще в 1952 году. В нем осуществляется последовательный перебор наборов символов, которые анализируются с целью определения частоты появления каждого символа. Затем наиболее часто встречающиеся символы кодируются с помощью минимально возможного количества битов. Например, в английских текстах чаще всего встречается буква «е». Используя кодировку Хаффмана, вы можете представить «е» всего лишь двумя битами (1 и 0) вместо восьми битов, необходимых для представления буквы «е» в кодировке ASCII Восстановление данных происходит в обратном порядке. Таким образом, чем выше уровень компрессии, тем больше данных отбрасывается и тем ниже качество. Используя JPEG, можно получить файл в 1-500 раз меньше, чем BMP. Этот формат аппаратно независим, полностью поддерживается и PC и Macintosh, однако он относительно новый и не понимается старыми программами (до 1995 года). JPEG не поддерживает индексированные палитры цветов. Первоначально в спецификациях формата не было поддержки цветовой модели CMYK и только в последние годы фирмой Adobe добавлена поддержка цветоделения. Наряду со стандартным вариантом существуют еще два подтипа формата JPEG , ориентированных на применение в Интернете. Baseline Optimized — файлы этого подтипа формата несколько лучше сжимаются, но не читаются некоторыми программами. Однако все основные браузеры его поддерживают. Progressive JPEG также разработан специально для сети, его файлы меньше стандартных, но чуть больше подтипа формата Baseline Optimized. Главная особенность Progressive JPEG состоит в поддержке чересстрочного вывода изображения (использование этого свойства намного сокращает время передачи и вывода на экран насыщенных графикой web-страниц). При сохранении графических изображений в формате JPEG- следует учитывать следующее. JPEG лучше подходит для сжатия растровых картинок фотографического качества, чем для логотипов или схем. Это связано с тем, что в них больше полутоновых переходов, в то время как при сжатии однотонных заливок появляются нежелательные помехи. Лучше сжимаются (и с меньшими потерями) большие изображения для web и изображения с высоким разрешением для печати (200-300 dpi и более), так как в каждом квадрате (8x8 пикселов) переходы получаются более мягкими за счет большего числа квадратов в таких файлах. Нежелательно сохранять в JPEG -формате любые изображения, в которых важны тонкие нюансы цветопередачи (репродукции), так как во время сжатия происходит отбрасывание цветовой информации. Этот формат следует использовать только для сохранения конечного варианта работы, потому что каждое последующее сохранение приводит к новым потерям (отбрасыванию) данных. Основная литература: 3[127-131], Дополнительная литература: 5[105-122] Контрольные вопросы: Алгоритмы сжатия изображений. Способы сжатия изображений. По технологии печати принтеры на какие виды можно разделить? Принцип работы струйных принтеров. Тема 14. Фрактальное сжатие изображенийАлгоритм фрактального сжатия изображений Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Прежде чем рассматривать процесс архивации, разберем, как IFS строит изображение. Строго говоря, IFS - это набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, у координата, яркость). Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге “Фрактальное сжатие изображения”. В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей. Одна шаг Машины состоит в построении с помощью проецирования по исходному изображению нового. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной IFS. Collage Theorem гарантирует наличие ровно одной неподвижной точки для каждой IFS. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении. Наиболее известны два изображения, полученных с помощью IFS треугольник Серпинского и папоротник Барнсли. Первое задается тремя, а второе - пятью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время, как изображение, построенное с их помощью, может занимать и несколько мегабайт. Становится понятно, как работает архиватор, и почему ему требуется так много времени. Фактически, фрактальная компрессия - это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований. В худшем случае, если не будет применяться оптимизирующий алгоритм, потребуется перебор и сравнение всех возможных фрагментов изображения разного размера. Даже для небольших изображений при учете дискретности мы получим астрономическое число перебираемых вариантов. Даже резкое сужение классов преобразований, например, за счет масштабирования только в определенное число раз, не позволит добиться приемлемого времени. Кроме того, при этом теряется качество изображения. Подавляющее большинство исследований в области фрактальной компрессии сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения. До сих пор мы не затронули несколько важных вопросов. Например, что делать, если алгоритм не может подобрать для какого-либо фрагмента изображения подобный ему? Достаточно очевидное решение - разбить этот фрагмент на более мелкие и попытаться поискать для них. Однако понятно, что процедуру эту нельзя повторять до бесконечности, иначе количество необходимых преобразований станет так велико, что алгоритм перестанет быть алгоритмом компрессии. Следовательно, допускаются потери в какой- то части изображения. Для фрактального алгоритма компрессии, как и для других алгоритмов сжатия с потерями, очень важны механизмы, с помощью которых можно будет регулировать степень сжатия и степень потерь. К настоящему времени разработан достаточно большой набор таких методов. Во-первых, можно ограничить количество преобразований, заведомо обеспечив степень сжатия не ниже фиксированной величины. Во-вторых, можно потребовать, чтобы в ситуации, когда разница между обрабатываемым фрагментом и наилучшим его приближением будет выше определенного порогового значения, этот фрагмент дробился обязательно (для него обязательно заводится несколько линз). В третьих, можно запретить дробить фрагменты размером меньше, допустим, четырех точек. Изменяя пороговые значения и приоритет этих условий, можно очень гибко управлять коэффициентом компрессии изображения: от побитного соответствия, до любой степени сжатия. Возможности масштабирования Итак, мы выяснили, что IFS задает фрактальную структуру, сколь угодно близкую к нашему изображению. При внимательном рассмотрении процесса построения изображения с ее помощью становится понятно, что восстанавливаемое изображение может иметь любое (!) разрешение. В самом деле, возвращаясь к аналогии с Фотокопировальной Машиной, можно сказать, что нам не важно до какой сетки растра будет огрубляться установившееся неподвижное изображение. Ведь Машина работает вообще с непрерывными экранами. На этапе архивации проводится распознавание изображения, и в виде коэффициентов хранится уже не растровая информация, а информация о структуре самого изображения. Именно это и позволяет при развертывании увеличивать его в несколько раз. Особенно впечатляют примеры, в которых при увеличении изображений природных объектов проявляются новые детали, действительно этим объектам присущие (например, когда при увеличении фотографии скалы она приобретает новые, более мелкие неровности). Но не все так гладко, как может показаться. Если изображение однородно (на фотографии только скала), то при увеличении получаются отличные результаты, однако, если сжимать изображение натюрморта, то предсказать, какие новые фрактальные структуры возникнут, очень сложно. Впрочем, вдвое-втрое можно увеличить практически любое изображение, при архивации которого задавалась небольшая степень потерь. Масштабирование - уникальная особенность, присущая фрактальной компрессии. Со временем ее, видимо, будут активно использовать как в специальных алгоритмах масштабирования, так и во многих приложениях. Действительно, этого требует концепция "приложение в окне". Было бы неплохо, если бы изображение, показываемое в окне 100х100, хорошо смотрелось при увеличении на полный экран - 1024х768. Основная литература: 4[97-126], Дополнительная литература: 5[55-91] Контрольные вопросы:1. Метод сжатия без потерь LZW 2 .Сравнение JPEG и алгоритма фрактального сжатия Какой диапазон цветового охвата формата PSD? Какой компанией был разработан формат JPEG? Тема 15. Инструментальные средства проектирования.CAD/CAM/CAE/PDM – системы Функции CAD-систем подразделяют на функции двухмерного (2D) и трехмерного (3D) проектирования. К функциям 2D относятся черчение, оформление конструкторской документации; к функциям 3D — построение трехмерных моделей, метрические расчеты, реалистичная визуализация, взаимное преобразование 2D и 3D моделей. Среди CAD-систем различают “легкие” и “тяжелые” системы. Первые из них ориентированы преимущественно на 2D графику , сравнительно дешевы и менее требовательны в отношении вычислительных ресурсов. Вторые ориентированы на геометрическое моделирование (3D), более универсальны, дороги, оформление чертежной документации в них обычно осуществляется с помощью предварительной разработки трехмерных геометрических моделей. Основные функции CAM-систем: разработка технологических процессов, синтез управляющих программ для технологического оборудования с числовым программным управлением (ЧПУ), моделирование процессов обработки, в том числе построение траекторий относительного движения инструмента и заготовки в процессе обработки, генерация постпроцессоров для конкретных типов оборудования с ЧПУ (NC — Numerical Control), расчет норм времени обработки. Наиболее известны следующие CAE/CAD/CAM-системы, предназначенные для машиностроения. “Тяжелые”: Unigraphics (EDS Uni- graphics); Solid Edge (Intergraph); Pro/Engineer (PTC - Parametric Technology Corp.), CATIA (Dassault Systemes), EUCLID (Matra Datavision), CADDS.5 (Computervision, ныне входит в PTC) и др. “Легкие” системы: AutoCAD (Autodesk); АДЕМ; bCAD (Группа, Новосибирск); Caddy (Ziegler Informatics); Компас (Аскон, С. Петербург); Спрут (Sprut Technology, Набережные Челны); Кредо (АСК , Москва). Системы, занимающие промежуточное положение (среднемасштабные): Cimatron, Microstation (Bentley), Euclid Prelude (Matra Datavision), T-FlexCAD (Топ Системы, Москва) и др. C ростом возможностей персональных ЭВМ грани между “легкими” и “тяжелыми” CAD/CAM-системами постепенно стираются. Функции CAЕ-систем довольно разнообразны, так как связаны с проектными процедурами анализа, моделирования, оптимизации проектных решений. В состав машиностроительных CAE-систем прежде всего включают программы для следующих процедур : моделирование полей физических величин, в том числе анализ прочности, который чаще всего выполняется в соответствии с МКЭ; расчет состояний и переходных процессов на макроуровне; имитационное моделирование сложных производственных систем на основе моделей массового обслуживания и сетей Петри. Примеры систем моделирования полей физических величин в соответствии с МКЭ: Nastrаn, Ansys, Cosmos, Nisa, Moldflow. Примеры систем моделирования динамических процессов на макроуровне: Adams и Dyna – в механических системах, Spice – в электронных схемах, ПА 9 – для многоаспектного моделирования, т.е. для моделирования систем, принципы действия которых основаны на взаимовлиянии физических процессов различной природы. Для удобства адаптации САПР к нуждам конкретных приложений, для ее развития целесообразно иметь в составе САПР инструментальные средства адаптации и развития. Эти средства представлены той или иной CASE- технологией, включая языки расширения. В некоторых САПР применяют оригинальные инструментальные среды. Примерами могут служить объектно-интерактивная среда CAS. CADE в системе EUCLID, содержащая библиотеку компонентов, в САПР T-Flex CAD 3D предусмотрена разработка дополнений в средах Visual C++ и Visual Basic. Важное значение для обеспечения открытости САПР, ее интегрируемости с другими автоматизированными системами (АС) имеют интерфейсы, представляемые реализованными в системе форматами межпрограммных обменов. Очевидно, что, в первую очередь, необходимо обеспечить связи между CAE, CAD и CAM-подсистемами. В качестве языков – форматов межпрограммных обменов – используются IGES, DXF, Express (входит в совокупность стандартов STEP), SAT (ядра ACIS) и др. Наиболее перспективными считаются диалекты языка Express, что объясняется общим характером стандартов STEP, их направленностью на различные приложения, а также на использование в современных распределенных проектных и производственных системах. Действительно, такие форматы, как IGES или DXF, описывают только геометрию объектов, в то время как в обменах между различными САПР и их подсистемами фигурируют данные о различных свойствах и атрибутах изделий. Основная литература: 2[211-232], Дополнительная литература: 7[114-166] Контрольные вопросы: Функции PDM – системы Какой формат получил популярность в Интернете благодаря высокой степени сжатия? Для чего используется формат PDF? Для чего предназначен формат TIFF? |