Учебное пособие Курск 2016
 Скачать 0.64 Mb.
|
|
Графический режим. Графический режим вывода изображения на экран монитора определяется величиной разрешающей способности и глубиной цвета. Для того чтобы на экране монитора формировалось изображение, информация о каждой его точке (код цвета точки) должна храниться в видеопамяти компьютера. Рассчитаем необходимый объем видеопамяти для одного из графических режимов, например, с разрешением 800 на 600 точек и глубиной цвета 24 бита на точку. Всего точек на экране: 800×600=480000. Необходимый объем видеопамяти: 24 бит × 480000=11520000 бит=1440000 байт=1406,25 Кбайт=1,37 Мбайт. Аналогично рассчитывается необходимый объем видеопамяти для других графических режимов. В Windows предусмотрена возможность выбора графического режима и настройки параметров видеосистемы компьютера, включающей монитор и видео-адаптер. Кодирование звуковой и видеоинформации. Временная дискретизация звука. Звук представляет собой звуковую волну с непрерывно меняющейся амплитудой и частотой. Чем больше амплитуда сигнала, тем он громче для человека, чем больше частота сигнала, тем выше тон. Для того чтобы компьютер мог обрабатывать звук, непрерывный звуковой сигнал должен быть превращен в последовательность электрических импульсов (двоичных нулей и единиц). В процессе кодирования непрерывного звукового сигнала производится его временная дискретизация. Непрерывная звуковая волна разбивается на отдельные маленькие временные участки, причем для каждого такого участка устанавливается определенная величина амплитуды. Таким образом, непрерывная зависимость амплитуды сигнала от времени А(t) заменяется на дискретную последовательность уровней громкости. На графике это выглядит как замена гладкой кривой на последовательность «ступенек».  Рисунок 7. Временная дискретизация звука. Каждой «ступеньке» присваивается значение уровня громкости звука, его код (1, 2, 3 и т.д.) уровни громкости звука можно рассматривать как набор возможных состояний, соответственно, чем большее количество уровней будет выделено в процессе кодирования, тем большее количество информации будет нести значение каждого уровня и тем более качественным будет звучание. Современные звуковые карты обеспечивают 16-битную глубину кодирования звука. Количество различных уровней сигнала Количество различных уровней сигнала (состояний при данном кодировании) можно рассчитать по формуле: N=2I=216=65536, где I-глубина звука. Таким образом, современные звуковые карты могут обеспечить кодирование 65536 уровней сигнала. Каждому значению амплитуды звукового сигнала присваивается 16-битный код. При двоичном кодировании непрерывного звукового сигнала он заменяется последовательностью дискретных уровней сигнала. Качество кодирования зависит от количества измерений уровня сигнала в единицу времени, то есть частоты дискретизации. Чем большее количество измерений производится за 1 секунду (чем больше частота дискретизации), тем точнее процедура двоичного кодирования. Качество двоичного кодирования звука определяется глубиной кодирования и частотой дискретизации. Количество измерений в секунду может лежать в диапазоне от 8000 до 48000, то есть частота дискретизации аналогового звукового сигнала может принимать значения от 8 до 48 кГц. При частоте 8 кГц качество дискретизированного звукового сигнала соответствует качеству радиотрансляции, а при частоте 48 кГц – качество звучания аудио-CD. Следует также учитывать, что возможны как можно-, так и стерео-режимы. Можно оценить информационный объем стереоаудиофайла длительностью звучания 1 секунда при высоком качестве звука (16 битов, 48 кГц). Для этого количество битов, приходящихся на одну выборку, необходимо умножить на коли-чество выборок в 1 секунду и умножить на 2 (стерео): 16 бит × 48000×2=1536000 бит=192000 байт=187,5 Кбайт. Стандартное приложение Звукозапись играет роль цифрового магнитофона и позволяет записывать звук, то есть дискретизировать звуковые файлы, и сохранять их в звуковых файлах в формате WAV. Эта программа позволяет редактировать звуковые файлы, микшировать их (накладывать друг на друга), а также воспроизводить. Кодирование видеоинформации Видеоинформация включает в себя последовательность кадров и звуковое сопровождение. Так как объемом звуковой составляющей видеоклипа можно пренебречь, то объем видеофайла примерно равен произведению количества информации в каждом кадре на число кадров. Число кадров вычисляется как произведение длительности видеоклипа t на скорость кадров v, то есть их количество в 1 с: V=N×M×C×v×t. При разрешении 800×600 точек, разрядности цвета C=16, скорости кадров v=25 кадров/c, видеоклип длительностью 30 с будет иметь объем: V=800×600×16×25×30=576×107(бит) =72×107 (байт)=687 (Мбайт). Методы сжатия информации. Существует много разных практических методов сжатия без потери информации, которые, как правило, имеют разную эффективность для разных типов данных и разных объемов. Однако, в основе этих методов лежат три теоретических алгоритма: алгоритм RLE(Run Length Encoding); алгоритмы группы KWE(KeyWord Encoding); алгоритм Хаффмана. Алгоритм RLE В основе алгоритма RLE лежит идея выявления повторяющихся последовательностей данных и замены их более простой структурой, в которой указывается код данных и коэффициент повторения. Например, пусть задана такая последовательность данных, что подлежит сжатию: 1 1 1 1 2 2 3 4 4 4 В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия, характеризующий степень сжатия, можно вычислить по формуле:  где Vx - объем памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn - входной последовательности данных. Чем меньше значение коэффициента сжатия, тем эффективней метод сжатия. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений). Алгоритм группы KWE В основе алгоритма сжатия по ключевым словам положен принцип кодирования лексических единиц группами байт фиксированной длины. Примером лексической единицы может быть обычное слово. На практике, на роль лексических единиц выбираются повторяющиеся последовательности символов, которые кодируются цепочкой символов (кодом) меньшей длины. Результат кодирования помещается в таблице, образовывая так называемый словарь. Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации. Алгоритм Хаффмана В основе алгоритма Хаффмана лежит идея кодирования битовыми группами. Сначала проводится частотный анализ входной последовательности данных, то есть устанавливается частота вхождения каждого символа, встречающегося в ней. После этого, символы сортируются по уменьшению частоты вхождения. Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования. Рассмотрим простой пример, иллюстрирующий работу алгоритма Хаффмана. Пусть задан текст, в котором бурва 'А' входит 10 раз, буква 'В' - 8 раз, 'С'- 6 раз , 'D' - 5 раз, 'Е' и 'F' - по 4 раза. Тогда один из возможных вариантов кодирования по алгоритму Хаффмана приведен в таблицы 13. Таблица 13. Кодирование по алгоритму Хаффмана
Как видно из таблицы 13, размер входного текста до сжатия равен 37 байт, тогда как после сжатия - 93 бит, то есть около 12 байт (без учета длины словаря). Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря). На практике программные средства сжатия данных синтезируют эти три "чистых" алгоритмы, поскольку их эффективность зависит от типа и объема данных. В таблице 14 приведены распространенные форматы сжатия и соответствующие им программы - архиваторы, использующиеся на практике. Таблица 14. Распространённые форматы сжатия
Кроме того, современные архиваторы предоставляют пользователю полный спектр услуг для работы с архивами, основными из которых являются : создание нового архива; добавление файлов в существующий архив; распаковывание файлов из архива; создание самораспаковающихся архивов (self-extractor archive); создание распределенных архивов фиксированного размера для носителей маленькой емкости; защита архивов паролями от несанкционированного доступа; просмотр содержимого файлов разных форматов без предварительного распаковывания; поиск файлов и данных внутри архива; проверка на вирусы в архиве к распаковыванию; выбор и настройка коэффициента сжатия. Сжатие с потерей и без потери информации. В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают: Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости; Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании; Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового просторную путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы). Существует много практических алгоритмов сжатия данных, но все они базируются на трех теоретических способах уменьшения избыточности данных. Первый способ состоит в изменении содержимого данных, второй - в изменении структуры данных, а третий - в одновременном изменении как структуры, так и содержимого данных. Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется необратимым. Такие методы часто называются методами сжатия с регулированными потерями информации. Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео- и аудиоданные, а также графические данные. Методы сжатия с регулированными потерями информации обеспечивают значительно большую степень сжатия, но их нельзя применять к текстовым данным. Примерами форматов сжатия с потерями информации могут быть: JPEG - для графических данных; MPG - для для видеоданных; MP3 - для аудиоданных. Если при сжатии данных происходит только изменение структуры данных, то метод сжатия называется обратимым. В этом случае, из архива можно восстановить информацию полностью. Обратимые методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации: GIF, TIFF - для графических данных; AVI - для видеоданных; ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных. Методы сжатия растровой информации делятся на две большие группы: сжатие с потерями и сжатие без потерь. Методы сжатия без потерь дают более низкий коэффициент сжатия, но зато сохраняют точное значение пикселов исходного изображения. Методы с потерями дают более высокие коэффициенты сжатия, но не позволяют воспроизвести первоначальное изображение с точностью до пиксела. Для файлов, создаваемых программами автоматизированного проектирования или электронных таблиц, очень важно сохранить всю информацию, потому что потеря хотя бы одного бита может изменить смысл всего файла. Совсем другое дело с растровыми данными. Человеческий глаз не воспринимает все тонкие оттенки цвета в обычном растровом изображении. Таким образом, некоторые детали могут быть опущены без видимого нарушения информационного содержания картинки. Сначала познакомимся с одним из вариантов группового кодирования (run-lenght encoding - RLE). Идея метода заключается в том, что последовательность повторяющихся значений заменяется парой чисел: одно из них указывает длину группы (число повторений данного значения), а другое - собственно это значение. Это очень общий и очень простой метод без потерь. В том или ином виде он используется во многих популярных сегодня форматах графических файлов и, в частности, в PCX и BMP. В его основе лежит тот факт, что многие изображения избыточны, поскольку содержат большое количество смежных пикселов одного цвета. Посмотрим, например, как с помощью группового кодирования сжимается изображение, в котором встречается подряд 100 пикселов с нулевым значением. Эта последовательность из 100 нулей кодируется парой чисел (100,0). Следовательно такой фрагмент картинки сократится в пятьдесят раз. Другим методом, которому мы также уделим внимание, будет JPEG - метод, сжимающий с потерями. Метод получил свое название от аббревиатуры объединенной группы экспертов в области фотографии (Joint Photographic Expert Group - JPEG), которая его и разработала. JPEG широко используется при сжатии статических изображений для их хранения на компакт-дисках. Этот метод существенно более сложен, чем RLE. Основная идея метода разделить информацию в изображении по уровню важности, и затем отбросить менее важную ее часть, уменьшая тем самым общий объем хранимых данных. Это достигается преобразованием матрицы цветовых значений в матрицу амплитуд, которые соответствуют определенным частотам разложения изображения. (Звуковые колебания, например, можно разложить математическими методами на простые синусоидальные гармоники различных амплитуд и частот, которые при сложении воспроизводят исходный сигнал. Строку или столбец пикселов изображения тоже можно представить амплитудами и частотами. Речь здесь идет не о спектральном составе света, а о форме воображаемых кривых, которые образуют графики, если значения пикселов служат ординатами. Отметим, что формула преобразования матрицы пикселов в матрицу амплитуд совсем не проста.) JPEG-сжатие отбрасывает часть высокочастотных компонент изображения, оставляя компоненты с низкими частотами. Человеческий глаз менее чувствителен к высокочастотным вариациям цвета, поскольку общий вид изображения определяется низкими частотами. Значение пиксела, полученное при восстановлении изображения, несколько отличается от исходного значения, так как часть информации была потеряна, хотя обычно они очень близки. У метода JPEG есть очень интересная особенность: пользователь может задавать коэффициент качества. Высокий коэффициент качества позволяет сохранить больше деталей, но при этом уменьшается степень сжатия. При низком коэффициенте качества степень сжатия увеличивается, но изображение становится менее четким. И это естественно, чем ниже коэффициент качества, тем большее количество информации отбрасывается. Вопрос в том, как найти разумный баланс между степенью сжатия и качеством изображения. Возможно придется прибегнуть к методу проб и ошибок, поскольку эффект JPEG-сжатия неодинаков для разных изображений. Одни картинки можно сжать в десять раз без особого ухудшения качества, в других же, даже при вдвое меньшем коэффициенте сжатия, возникают недопустимые искажения. Когда любой из методов (RLE или JPEG) применяется к полноцветному изображению, то красная, зеленая и синяя компоненты сжимаются независимо. Если в растровой картинке используется палитра или просто оттенки серого, то значения пикселов можно закодировать в один проход. Приступим к детальному рассмотрению методов RLE и JPEG. Как работает алгоритм группового кодирования Если вы внимательно посмотрите на растровое изображение, то обнаружите, что пикселы одного цвета часто оказываются рядом друг с другом. Если начать с левого верхнего угла изображения и исследовать пикселы каждой строки, выписывая последовательно их значения слева направо, то можно заметить, что картинка состоит из множества отрезков, в которых повторяется одно и то число. Количество пикселов в отрезке будем называть длиной отрезка. Начиная с первой строки, программа группового кодирования просматривает значения пикселов слева направо и ищет отрезки повторяющихся пикселов. Всякий раз, когда встречаются три или более идущих подряд пикселов с одинаковым значением, программа заменяет их парой чисел: первое число указывает длину отрезка, второе - значение пикселов. Число, определяющее длину отрезка, будем называть меткой отрезка. На рисунке такие метки обозначены треугольниками. Чтобы идентифицировать серии неповторяющихся значений пикселов, программа также вставляет метки (на рисунке представлены квадратиками), указывающие количество таких значений в серии. Зарезервированный бит необходим для того, чтобы можно было отличить метку отрезка, от метки серии неповторяющихся значений. Например, в 8-ми битах можно специфицировать последовательности длиной до 127 пикселов (максимальное число, представимое 7-ю битами); восьмой бит в каждой метке может отличать отрезок от серии неповторяющихся пикселов. В нашем примере благодаря RLE-сжатию размер строки уменьшился с 32 до 19 байт, т.е. на 40 процентов. Точно так же обрабатывается каждая строка пикселов, и отрезки одинаковых значений пикселов сжимаются во всем изображении. Графическая программа декодирует изображение, считывая сжатый файл и восстанавливая отрезки повторяющихся значений пикселов. Заметим, что восстановленное изображение полностью совпадает с оригиналом. Как работает алгоритм JPEG Прежде всего программа делит изображение на блоки - матрицы размером 8х8 пикселов. Поскольку при использовании метода JPEG время, затрачиваемое на сжатие изображения, пропорционально квадрату числа пикселов в блоке, обработка нескольких блоков меньшего размера делается значительно быстрее, чем обработка всего изображения целиком. К значениям пикселов применяется формула, названная дискретным косинусоидальным преобразованием (Discrete Cosine Transform - DCT). DCT переводит матрицу значений пикселов 8х8 в матрицу значений амплитуд такой же размерности, соответствующую определенным частотам синусоидальных колебаний. Левый верхний угол матрицы соответствует низким частотам, а правый нижний - высоким. Коэффициент качества, введенный пользователем, используется в простой формуле, которая генерирует значения элементов другой матрицы 8х8, названной матрицей квантования. Чем ниже коэффициент качества, тем большие значения будут иметь элементы матрицы. Каждое значение в матрице, получившееся после DCT-преобразования, делится на соответствующее значение из матрицы квантования, затем округляется до ближайшего целого числа. Так как большие числа находятся в правой нижней половине матрицы квантования, то основная часть высокочастотной информации изображения будет отброшена. Поэтому нижняя правая часть матрицы пикселов будет состоять в основном из нулей. Далее программа, двигаясь по матрице зигзагообразно, считывает элементы матрицы и кодирует их последовательно методами без потерь. Заметим, что сжатие существенно зависит от нулей в правой нижней половине матрицы. Чем ниже коэффициент качества, тем больше нулей в матрице и, следовательно, тем выше степень сжатия. Декодирование JPEG-изображения начинается с шага обратного кодированию без потерь, в результате чего восстанавливается матрица квантования пикселов. Значения из матрицы пикселов умножаются на значения из матрицы квантования, чтобы восстановить, насколько это возможно, матрицу, которая была вычислена на шаге применения DCT. На этапе квантования была потеряна некоторая часть информации, поэтому числа в матрице будут близки к первоначальным, но не будет абсолютного совпадения. Обратная к DCT формула (IDCT) применяется к матрице для восстановления значений пикселов исходного изображения. Еще раз отметим, что полученные цвета не будут полностью соответствовать первоначальным из-за потери информации на шаге квантования. Восстановленное изображение, при сравнении с оригиналом, будет выглядеть несколько размытым и обесцвеченным. СПИСОК ЛИТЕРАТУРЫ Хэмминг Р.В. Теория кодирования и теория информации: Пер. с англ. — М.: Радио и связь, 2010 . — 176 с., ил. Фомин С. В. Системы счисления. – М.: Наука, 2011 Андреева Е., Фалина И. Информатика: Системы счисления и компьютерная арифметика. – М.: ЛБЗ, 2009 Душин В.К. Теоретические основы информационных процессов и систем: Учебник.— Издательско-торговая корпорация «Дашков и К», 2008 . – 348 с. Маскаева А.М. Основы теории информации. М. : Форум ИНФРА- М, 2014 Панин В.В. Основы теории информации. М.: БИНОМ Лаборатория знаний, 2012 Хохлов Г.И. Основы теории информации: учеб. / М.: Академия, 2008 | |||||||||||||||||||||||||||||||||||||||||||||