Практика. Практическая работа Способы обработки, хранения, поиска информации
 Скачать 0.53 Mb.
|
|
ПРАКТИЧЕСКАЯ РАБОТА 10 Кодирование графической информации Цель: ознакомиться с принципами кодирования информации Теоретические сведения. Кодирование графической информации В видеопамяти находится двоичная информация об изображении, выводимом на экран. В зависимости от способа формирования изображений компьютерную графику принято подразделять на растровую, векторную. Отдельным направлением считается трехмерная (3D) графика, изучающая приемы и методы построения объемных моделей объектов в виртуальном пространстве. В ней сочетаются векторный и растровый способы формирования изображений. Растровое изображение. Форму представления на экране дисплея графического изображения, состоящего из отдельных точек (пикселей), называют растровой. Минимальным объектом в растровом графическом редакторе является точка (пиксель). Растровые изображения представляют собой однослойную сетку точек, называемых пикселами (pixel, от англ. picture element). Код пиксела содержит информацию о его цвете. Для черно-белого изображения (без полутонов) пиксель может принимать только два значения: белый и черный (светится – не светится), а для его кодирования достаточно одного бита памяти: 1 – белый, 0 – черный. Пиксель на цветном дисплее может иметь различную окраску, поэтому одного бита на пиксель недостаточно. Для кодирования 4-цветного изображения требуются два бита на пиксель, поскольку два бита могут принимать 4 различных состояния. Может использоваться, например, такой вариант кодировки цветов: 00 – черный, 10 – зеленый, 01 – красный, 11 – коричневый. Цветовые модели расположены в трехмерной системе координат, образующей цветовое пространство, так как из законов Грассмана следует, что цвет можно выразить точкой в трехмерном пространстве. Первый закон Грассмана (закон трехмерности). Любой цвет однозначно выражается тремя составляющими, если они линейно независимы. Линейная независимость заключается в невозможности получить любой из этих трех цветов сложением двух остальных. Второй закон Грассмана (закон непрерывности). При непрерывном изменении излучения цвет смеси также меняется непрерывно. Не существует такого цвета, к которому нельзя было бы подобрать бесконечно близкий. Третий закон Грассмана (закон аддитивности). Цвет смеси излучений зависит только от их цвета, но не спектрального состава. То есть цвет (С) смеси выражается суммой цветовых уравнений излучений: Любой цвет (С) может быть выражен в цветовом пространстве вектором, который описывается уравнением: которое практически идентично уравнению свободного вектора в пространстве, рассматриваемому в векторной алгебре. Направление вектора характеризует цветность, а его модуль выражает яркость. В основе кодирования цветной графики лежит принцип декомпозиции произвольного цвета на основные составляющие. Применяют несколько систем кодирования. Рассмотрим кратко основные цветовые модели. 1. Принцип метода RGB заключается в следующем: известно, что любой цвет можно представить в виде комбинации трех цветов: красного (Red, R), зеленого (Green, G), синего (Blue, B). Другие цвета и их оттенки получаются за счет наличия или отсутствия этих составляющих. По первым буквам основных цветов система и получила свое название – RGB. Данная цветовая модель является аддитивной, то есть любой цвет можно получить сочетание основных цветов в различных пропорциях. При наложении одного компонента основного цвета на другой яркость суммарного излучения увеличивается. Если совместить все три компоненты, то получим ахроматический серый цвет, при увеличении яркости которого происходит приближение к белому цвету. При 256 градациях тона (каждая точка кодируется 3 байтами) минимальные значения RGB (0,0,0) соответствуют черному цвету, а белому - максимальные с координатами (255, 255, 255). Чем больше значение байта цветовой составляющей, тем этот цвет ярче. Например, темно-синий кодируется тремя байтами (0, 0, 128), а ярко-синий (0, 0, 255). 2. Модель HSB характеризуется тремя компонентами: оттенок цвета (Hue), насыщенность цвета (Saturation) и яркость цвета (Brightness). Можно получить большое количество произвольных цветов, регулируя эти компоненты. Эту цветовую модель лучше применять в тех графических редакторах, в которых изображения создают сами, а не обрабатывают уже готовые. Значение цвета выбирается как вектор, выходящий из центра окружности. Направление вектора задается в угловых градусах и определяет цветовой оттенок. Насыщенность цвета определяется длиной вектора, а яркость цвета задается на отдельной оси, нулевая точка которой имеет черный цвет. Точка в центре соответствует белому (нейтральному) цвету, а точки по периметру - чистым цветам. 3) Принцип метода CMYK. Эта цветовая модель используется при подготовке публикаций к печати. Каждому из основных цветов ставится в соответствие дополнительный цвет (дополняющий основной до белого). Получают дополнительный цвет за счет суммирования пары остальных основных цветов. Значит, дополнительными цветами для красного является голубой (Cyan,C) = зеленый + синий = белый – красный, для зеленого – пурпурный (Magenta, M) = красный + синий = белый – зеленый, для синего – желтый (Yellow, Y) = красный + зеленый = белый – синий. Причем принцип декомпозиции произвольного цвета на составляющие можно применять как для основных, так и для дополнительных, то есть любой цвет можно представить или в виде суммы красной, зеленой, синей составляющей или же в виде суммы голубой, пурпурной, желтой составляющей. В основном такой метод принят в полиграфии. Но там еще используют черный цвет (Black, так как буква В уже занята синим цветом, то обозначают буквой K). Это связано с тем, что наложение друг на друга дополнительных цветов не дает чистого черного цвета. Различают несколько режимов представления цветной графики: а) полноцветный (True Color); б) High Color; в) индексный. При полноцветном режиме для кодирования яркости каждой из составляющих используют по 256 значений (восемь двоичных разрядов), то есть на кодирование цвета одного пикселя (в системе RGB) надо затратить 8×3=24 разряда. Это позволяет однозначно определять 16,5 млн цветов. Это довольно близко к чувствительности человеческого глаза. При кодировании с помощью системы CMYK для представления цветной графики надо иметь 8×4=32 двоичных разряда. Режим High Color – это кодирование при помощи 16-разрядных двоичных чисел, то есть уменьшается количество двоичных разрядов при кодировании каждой точки. Но при этом значительно уменьшается диапазон кодируемых цветов. При индексном кодировании цвета можно передать всего лишь 256 цветовых оттенков. Каждый цвет кодируется при помощи восьми бит данных. Но так как 256 значений не передают весь диапазон цветов, доступный человеческому глазу, то подразумевается, что к графическим данным прилагается палитра (справочная таблица), без которой воспроизведение будет неадекватным: море может получиться красным, а листья – синими. Сам код точки растра в данном случае означает не сам по себе цвет, а только его номер (индекс) в палитре. Отсюда и название режима – индексный. Количество различных цветов К и количество битов для их кодирования b связаны между собой формулой К = 2b. Так, 21 = 2, 22 = 4, 23 = 8, 24 = 16 и т. д. Для получения цветовой гаммы из 256 цветов требуется 8 битов = 1 байт на каждый пиксель, так как 28 = 256. Величина b является битовой глубиной цвета, К – количество цветов, Разрешающая способность монитора (количество точек по горизонтали и вертикали), а также число возможных цветов каждой точки определяются типом монитора. Например: 640×480 = 307 200 точек, 800×600 = 480 000 точек. Объем памяти, необходимой для хранения графического изображения, занимающего весь экран, равен произведению количества пикселей (разрешающей способности) на число бит, кодирующих одну точку. Объем графического файла в битах определяется как произведение количества пикселей на разрядность цвета (битовую глубину) Итак, объем памяти, необходимой для хранения графического изображения в битах V рассчитывается по формуле V = K∙I, где K - количества пикселей, хранящих изображение, I - глубина цвета в битах. Например, при разрешении 640×480 и количестве цветов 16 (4 бита) объем памяти равен: 640×480×4=1 228 800 (бит) = 153 600 (байт) = 150 (Кбайт). Векторная графика Если в растровой графике базовым элементом изображения является точка, то в векторной графике - линия. Линия описывается математически как единый объект, и потому объем данных для отображения объекта средствами векторной графики существенно меньше, чем в растровой графике. Линия - элементарный объект векторной графики. Как и любой объект, линия обладает свойствами: формой (прямая, кривая), толщиной, цветом, начертанием (сплошная, пунктирная). Замкнутые линии приобретают свойство заполнения. Охватываемое ими пространство может быть заполнено другими объектами (текстуры, карты) или выбранным цветом. Простейшая незамкнутая линия ограничена двумя точками, именуемыми узлами или опорными точками. Узлы также имеют свойства, параметры которых влияют на форму конца линии и характер сопряжения с другими объектами. Все прочие объекты векторной графики составляются из линий. Например, куб можно составить из шести связанных прямоугольников, каждый из которых, в свою очередь, образован четырьмя связанными линиями. Возможно представить куб и как двенадцать связанных линий, образующих ребра. В отличие от растровой графики векторное изображение многослойно. Каждый элемент векторного изображения – линия, прямоугольник, окружность или фрагмент текста – располагается в своем собственном слое, пикселы которого устанавливаются независимо от других слоев, и описывается с помощью специального языка (математических уравнения линий, дуг, окружностей и т.д.) Сложные объекты (ломаные линии, различные геометрические фигуры) представляются в виде совокупности элементарных графических объектов. Задание 1.Определить, сколько цветов кодируется при битовой глубине :а)4, б)3 в)5 2. Определить объем памяти для хранения информации в один пиксель при битовой глубине 4. 3. Определить объем памяти для хранения графической информации 480х240 пикселей и количестве цветов 32 4. Определить битовую глубину кодирования графической информации, если известно, что для хранения графического файла размером 640×480 пикселей потребовалось 150Кбайт 5. Определить количество цветов, если известно, что 1 пиксель изображения занимает объем памяти 256 бит Содержание отчета Название и цель работы. Краткое изложение теории/методики Задание и ход его выполнения Выводы ПРАКТИЧЕСКАЯ РАБОТА 11 Кодирование по методу Шеннона—Фано, методу Хаффмена, с проверкой на четность Цель: Ознакомиться с методами кодирования и декодирования; получить практические навыки кодирования и декодирования Краткие теоретические сведения Основные принципы кодирования Под кодированием сигнала понимают процесс преобразования сообщения в сигнал. Как правило, сообщение от источника информации выдается в аналоговой форме, т.е. в виде непрерывного сообщения. Однако как при приеме-передаче информации, так и при ее обработке и хранении значительное преимущество дает дискретная форма представления сигнала. Поэтому в тех случаях, когда исходные сигналы в информационных системах являются непрерывными, необходимо предварительно преобразовать их в дискретные. В связи с этим термин «кодирование» относят обычно к дискретным сигналам и под кодированием в узком смысле понимают представление дискретных сообщений сигналами в виде определенных сочетаний символов. Совокупность правил, в соответствии с которыми производятся эти операции, называется кодом. Процесс кодирования информации обеспечивает достижение нескольких целей. Во-первых, сообщения представляют в системе символов, обеспечивающей простоту аппаратной реализации информационных устройств. Задача кодирования сообщений для этого случая представляется как преобразование исходного сообщении и используемую (как правило, двоичную) систему счисления. Число используемых при этом различных элементарных сигналов называется основанием кода, а число элементов, образующих кодовую комбинацию, — значностью кода. Если все комбинации кода имеют одинаковую значность, то такой код называется равномерным, и противном случае — неравномерным. Кодирование по методу Шеннона—Фано При кодировании по этому методу код строится следующим образом. Буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей. Затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковыми. Всем буквам верхней половины в качестве первого символа приписывается «1», а всем нижним — «0». Каждая из групп разбивается на две подгруппы с одинаковыми суммарными вероятностями и т.д. Процесс повторяется до тех пор, пока в каждой подгруппе не останется по одной букве. Кодирование по методу Хаффмена Этот метод гарантирует построение кода с наименьшим для данного распределения вероятностей средним числом разрядов на букву, Для двоичного кода метод сводится к следующему. Буквы алфавита сообщений выписываются в основной столбец в порядке убывания вероятностей. Две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность. Вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние буквы объединяются. Процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной 1. Кодирование с проверкой на чётность Для этого метода выполняют суммирование цифр по модулю 2, входящих в контролируемый код. Вместе с передаваемым кодом передается один контрольный разряд. Его значение («1» или «О») выбирается с условием, чтобы сумма цифр в передаваемом коде была по модулю 2 равна 0 — для случая четности или 1 — для случая нечетности. При таком кодировании допускается, что может возникнуть только одна ошибка. Задание. 1. Приняты две кодовые комбинации 101011 И 101000. Определить значность кодовых комбинаций их вес и кодовое расстояние между ними. 2. Принята кодовая комбинация 10011 . Известно, что вектор ошибки 111110, определить исходную кодовую комбинацию и ее вес. 3. Принята комбинация 1011110100110101010101011010 Известен вектор ошибки 1011110100110110010101011010 Найти исходную комбинацию и ее вес. Определить значность принятой кодовой комбинации и исходной кодовой комбинации. Содержание отчета Название и цель работы. Краткое изложение теории/методики Задание и ход его выполнения Выводы ПРАКТИЧЕСКАЯ РАБОТА 12-13. Решение задач с использованием оптимального кодирования информации Цель: научиться использовать оптимальное кодирование информации Краткие сведения Информационная избыточность — обычно явление естественное, заложена она в первичном алфавите. Корректирующая избыточность— явление искусственное, заложена она в кодах, представленных во вторичном алфавите. Способ уменьшения избыточности сообщения - построение оптимальных кодов. Оптимальные коды — коды с практически нулевой избыточностью. При построении оптимальных кодов наибольшее распространение нашли методики Шеннона — Фано и Хаффмена Согласно методике Шеннона — Фано построение оптимального кода ансамбля из сообщений сводится к следующему: 1-й шаг. Множество из сообщений располагается в порядке убывания вероятностей. 2-й шаг. Первоначальный ансамбль кодируемых сигналов разбивается на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны. Если равной вероятности в подгруппах нельзя достичь, то их делят так, чтобы в верхней части (верхней подгруппе) оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части (в нижней подгруппе). 3-й шаг. Первой группе присваивается символ 0, второй» группе — символ 1. 4-й шаг. Каждую из образованных подгрупп делят на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны. 5-й шаг. Первым группам каждой из подгрупп вновь присваивается 0, а вторым—1. Таким образом, мы получаем вторые цифры кода. Затем каждая из четырех групп вновь делится на равные (с точки зрения суммарной вероятности) части до тех пор, пока в каждой из подгрупп не останется по одной букве. Построенные по этим методикам коды с неравномерным распределением символов, имеющие минимальную среднюю длину кодового слова, называют оптимальными неравномерными кодами (ОНК). Равномерные коды могут быть оптимальными только для передачи сообщений с равновероятным распределением символов первичного алфавита, при этом число символов первичного алфавита должно быть равно целой степени-числа, равного количеству качественных признаков вторичного алфавита, а в случае двоичных кодов — целой степени двух. |