Методы сжатия информации

Методы сжатия информации Любые данные можно представить, как последовательность сообщений, которые получаются от некоторого источника информации. При этом очевидно, что каждое состояние источника будет характеризоваться своей вероятностью. Количество информации, что содержится в одном состоянии источника, можно оценить: Эта мера была предложена Харли. Оценить среднее количество информации, которая поступает от одного источника, можно, используя формулу энтропии: где pi – вероятность i-того состояния источника, n – общее количество состояний. Энтропия максимальна, если все состояния источника равновероятны, но таких источников в природе почти не существует, и энтропия должна иметь меньшее значение источника. Можно построить такой код, который разрешает получать среднюю длину кодовой комбинации не больше, чем значение энтропии плюс один бит, и поскольку состояние большинства источников неравновероятное, такой код будет лучше, чем двоичное кодирование источника. Сжатие информации с помощью оптимальных по короткости кодов Если проанализировать любой источник информации, можно заметить, что он генерирует разнообразные сообщения с разной частотой, то есть, можно сказать, что вероятности состояний всех фактических реальных источников информации неодинаковые. Это стало основой главной идеи построения оптимальных по краткости кодов. Идея состоит в том, чтобы представить более вероятные состояния более короткими комбинациями кодов. Любой оптимальный по краткости код соответствует следующим требованиям: 1. Все комбинации кода разные; 2. Более вероятные состояния присваивают более краткой комбинации кода; 3. Свойство префиксности: ни одна комбинация кода не начинается с другой, более краткой. Это свойство разрешает получать мгновенный код – код, который можно передавать без разделителей. При декодировании из входного потока изымается информация про символы, и как только накопленная комбинация совпадет с комбинацией кода, она декодируется. Есть источник: Х1 0 Х2 010 Х3 10 Х4 1 Генерируется последовательность: Х2 Х1 Х3 010 0 10 Из-за невыполнения свойства префиксности возникает неопределенность. 4. Две кодовые комбинации, соответствующие двум состояниям с наименьшей вероятностью, имеют одинаковую длину и различаются только в одном - последнем двоичном разряде. МЕТОД ХАФФМАНА Для построения кода необходимо: 1. Записываем все состояния в порядке убывания их вероятности. 2. Объединяем два состояния с наименьшей вероятностью, заменяя их одним, вероятность которого равна сумме его составляющих. 3. Шаг 1 и 2 повторяем, пока не останется одно состояние, с вероятностью 1. 4. На основании этих шагов строится дерево: верхушка дерева – состояние с вероятностью 1, справа от каждой вершины находятся состояния с большими вероятностями, слева с меньшими. Все правые ветви обозначаются 0, левые 1. 5. Выписываются кодовые комбинации путем обхода дерева от корня к терминальным узлам. Например: Рис. 1. Алгоритм метода Хаффмана. Рис. 2. Построение дерева Хаффмана. Х1 0 Х2 100 Х3 101 Х4 110 Х5 11100 Х6 11101 Х7 11110 Х8 11111 Эффективность построенного кода можно оценить, вычислив среднюю длину кодовой комбинации, сравнив ее с энтропией и длиной комбинации при двоичном кодировании: В среднем при сжатии сообщения, состоящего из 1000 состояний источника, мы потратим 2184 битов. При использовании же простого двоичного кода потребовалось бы 3000 бит. В идеале средняя длина кодовой комбинации должна быть равна среднему количеству информации, получаемой от одного события сгенерированного источника. МЕТОДЫ СЖАТИЯ ТЕКСТОВОЙ И ГРАФИЧЕСКОЙ ИНФОРМАЦИИ. МЕТОД ПОДАВЛЕНИЯ НУЛЕЙ. Один из старейших и самых простых методов сжатия данных известен как подавление нулей (null suppression), или подавление пропусков (blank suppression). В тексте или потоке символов часто встречаются длинные строки пропусков или нулей. В методе подавления нулей передатчик сканирует данные в поисках строк пропусков и заменяет каждую такую строку двухсимвольным кодом. Код состоит из специального управляющего символа, затем указывается количество пропусков в строке. Например, код, в котором символы пропуска, отмеченные b: XYZbbbbbQRX Эта строчка заменяется следующей строчкой, в которой Sc представляет собой специальный управляющий символ: XYZSc5QRX Такая схема позволяет сократить все строки, где есть три и больше пропуска. В методе подавления нулей получатель ищет в потоке входящих символов специальный символ, используемый для индикации удаленных пропусков. Получив такой символ, получатель понимает, что следующий символ содержит количество удаленных пропусков. По этой информации может быть восстановлен первоначальный поток данных. При том что метод подавления нулей является крайне примитивной формой сжатия данных, его преимущество заключается в том, что он очень легко реализуется. Кроме того, выигрыш также при использования такого простого метода может быть не значительным. Практически, при первых внедрениях этого метода выигрыш составил от 30% до 50%. ГРУППОВОЕ КОДИРОВАНИЕ Групповое кодирование (run - length encoding) является простым методом сжатия данных без потерь, достаточно эффективен для сжатия текста. Этот метод также находит применение в факсимильном сжатии. ScXCc Sc – специальный символ, указывает на то, что после него идут сжатые данные; Х – любой повторяющийся символ; Cc – счетчик символов, то есть, количество повторений сжатого символа. Пример: $******55.72 $Sc*655.72 --------- Sc-9 Как и в методе подавления нулей, передатчик ищет последовательности повторяющихся символов. В данном случае он заменяет их на трехсимвольний код. Код состоит из специального индикатора сжатия, за которым следуют сам символ, который повторяется, и количество его повторений. Таким образом, этот метод позволяет сократить место, которое занимает любая последовательность из четырех и более одинаковых символов. Эффективность метода группового кодирования зависит от того, насколько часто в исходных данных встречаются последовательности повторяющихся символов, и средней длины таких серий. Стандартной мерой эффективности сжатия является коэффициент сжатия, который представляет собой отношение длины несжатых данных к длине сжатых данных (включая символы кодировки). Любая схема сжатия будет иметь переменную производительность, которая будет зависеть от исходных данных. Однако в большинстве случаев в тексте содержится достаточное количество повторяющихся символов, чтобы применение даже такого простого метода как групповое кодирование, было оправданным. Групповое кодирование было одним из первых методов сжатия факсимильных сообщений, но теперь оно больше не используется с этой целью. Однако этот метод следует изучить, поскольку он применяется в сложных методах сжатия изображений. При использовании метода группового кодирования для изображений вместо отсканированной и оцифрованной линии передаются длины серий белых и черных элементов изображения. Каждый пиксель представляется как один бит, что означает белый или черный цвет. Код длин серий состоит из длин черных и белых последовательностей, которые чередуются. Поскольку при таком кодировании изображения черный и белый цвета всегда чередуются; нет необходимости в использовании специального символа, который указывает на цвет серии. Таким образом, закодированный поток данных является рядом цифр, обозначающих длины серий черных и белых точек, которые чередуются. В простом примере закодированные данные занимают больше места, чем первоначальные. Но в случае использования этого метода относительно типичной страницы текста, этот метод будет сжимать данные. Тем не менее, это не самый эффективный способ сжатия изображений. Методы сжатия данных очень важны для широкого применения цифровых и факсимильных аппаратов. Для примера рассмотрим типичную страницу, с разрешением в 200 пикселей (белых или черных точек) на дюйм (это является приемлемой, но не высокой степенью разрешения). В результате такая страница содержит 3740000 бит (8,5 дюймов х 11 дюймов х 40 000 пикселей на квадратный дюйм). При базовой скорости службы ISDN в 64 Кбит / с передача такой страницы займет около одной минуты. Сектор ITU-T стандартизировал два метода сжатия данных без потерь для факсимильной связи: модифицированный код Хаффмана и модифицированный метод READ. В типичном документе черные и белые области имеют тенденцию к объединению. Если рассматривать документ как последовательность линий и обратить внимание на расположение участков белого и черного цвета в строке, можно обнаружить длинные серии белых и черных точек. Благодаря этому свойству можно предположить, что сжатие, основанное на методе группового кодирования, даст хороший результат. Входные данные, которые состоят из двух значений, превратятся в длины серий, которые затем кодируются для передачи. Кроме этого, поскольку в общем случае длинные серии черных и белых точек менее вероятны, чем короткие, можно воспользоваться преимуществом кодирования последовательностей переменной длины. ФАКСИМИЛЬНОЕ СЖАТИЕ. МОДИФИЦИРОВАННЫЙ МЕТОД ХАФФМАНА. Факсимильное изображение хорошо поддается сжатию, это связано с тем, что изображения являются бинарными и в них присутствуют длинные последовательности, которые повторяются. Бинарное изображение – изображение с двумя цветами: цвет фона и цвет точки. Минимальное разрешение факса таково, что в одной линии будет не менее 1728 точек, поскольку точки бывают только двух цветов, изображение можно эффективно сжимать с помощью RLE-кодирования. Для кодирования факсов может применяться код Хаффмана, описанный выше. Этот метод можно применить для каждой строки изображения, кодируя последовательности черных и белых точек. Например, предположим, что при сканировании отдельной строки получается следующая последовательность черных и белых точек: W7, В7, W4, В8, W4, В7, W10 (в данном случае W означает белый, а В – черный). Если рассматривать каждый из этих элементов как символ алфавита источника, то для кодирования этих данных может быть использован метод кодирования Хаффмана. Однако, поскольку стандарт ITU-T требует минимум 1728 точек в линии, количество различных кодов, а, следовательно, и средняя длина кода будет очень большой. Альтернативой является модифицированный метод кодирования Хаффмана. В этом методе длина серии N рассматривается как сумма двух слагаемых: N = 64m + n; m = 0, 1, 2…27; n = 0,1, 2, …, 63. То есть длина каждой серии черных или белых точек считается величиной, кратной 64 с остатком. Теперь каждая длина серии может быть представлена двумя значениями, одним для m и другим для n, и эти значения могут кодироваться с помощью метода Хаффмана. Например, строка из 200 черных точек подряд может быть выражена как 64 * 3 + 8. Для этого сектора ITU-T были определены восемь образцов документов и рассчитана вероятность нахождения в документах серий различных длин. Поскольку для серий из черных и белых точек эти вероятности различаются, были сочтены два множества вероятностей. На основе полученной информации были составлены две таблицы. Длина серии делится на 64, после чего доля и остаток от деления кодируются двумя кодовыми словами. Если длина серии меньше 64 (доля от разделения равна нулю), то такая длина серии кодируется только кодовым словом остатка. Серии длиной более 64 точек кодируются двумя кодами: код остатка (n) и кодом кратности (m). Есть еще несколько моментов, касающихся этого кода. Каждая строка заканчивается уникальным кодовым словом EOL (End Of Line - конец строки). Это кодовое слово, которое никогда не встречается в строках данных, обеспечивает восстановление синхронизацию в случае ошибок. Внутри строки должны чередоваться кодовые слова для белых и черных серий. Обратите внимание на то, что для белых и черных серий используются различные кодовые слова. Это обеспечивает дополнительную защиту от ошибок. Наконец, по соглашению каждая строка начинается с белой серии. ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ Табл. 1. Составные коды модифицированного кода Хаффмана. Длина серии Белая серия Черная серия Кодовые слова остатка 00110101 0000110111 1 000111 010 2 0111 11 3 1000 10 4 1011 011 5 1100 0011 6 1110 0010 7 1111 00011 8 10011 000101 9 10100 000100 10 00111 0000100 11 01000 0000101 12 001000 0000111 13 000011 00000100 14 110100 00000111 15 110101 000011000 16 101010 0000010111 17 101011 0000011000 18 0100111 0000001000 19 0001100 00001100111 20 0001000 00001101000 21 0010111 00001101100 22 0000011 00000110111 23 0000100 00000101000 24 0101000 00000010111 25 0101011 00000011000 26 0010011 000011001010 27 0100100 000011001011 28 0011000 000011001100 29 00000010 000011001101 30 00000011 000001101000 31 00011010 000001101001 32 00011011 000001101010 33 00010010 000001101011 34 00010011 000011010010 35 00010100 000011010011 36 00010101 000011010100 37 00010110 000011010101 38 00010111 000011010110 39 00101000 000011010111 40 00101001 000001101100 41 00101010 000001101101 42 00101011 000011011010 43 00101100 000011011011 44 00101101 000001010100 45 00000100 000001010101 46 00000101 000001010110 47 00001010 000001010111 48 00001011 000001100100 49 01010010 000001100101 50 01010011 000001010010 51 01010100 000001010011 52 01010101 000000100100 53 00100100 000000110111 54 00100101 000000111000 55 01011000 000000100111 56 01011001 000000101000 57 01011010 000001011000 58 01011011 000001011001 59 01001010 000000101011 60 01001011 000000101100 61 00110010 000001011010 62 00110011 000001100110 63 00110100 000001100111 Кодовые слова кратности 64 64 11011 0000001111 128 10010 000011001000 192 010111 000011001001 256 0110111 000001011011 320 00110110 000000110011 384 00110111 000000110100 448 01100100 000000110101 512 01100101 0000001101100 576 01101000 0000001101101 640 01100111 0000001001010 704 011001100 0000001001011 768 011001101 0000001001100 832 011010010 0000001001101 896 011010011 0000001110010 960 011010100 0000001110011 1024 011010101 0000001110100 1088 011010110 0000001110101 1152 011010111 0000001110110 1216 011011000 0000001110111 1280 011011001 0000001010010 1344 011011010 0000001010011 1408 011011011 0000001010100 1472 010011000 0000001010101 1536 010011001 0000001011010 1600 010011010 0000001011011 1664 011000 0000001100100 1728 010011011 0000001100101 EOL 000000000001 000000000001 МОДИФИЦИРОВАННЫЙ КОД READ Использование модифицированного кода Хаффмана значительно сокращает количество битов, передаваемых по сравнению с передачей несжатого изображения. Дополнительного увеличения производительности можно достичь, зная о корреляции между последовательностями черно-белых серий точек в двух соседних строках. На самом деле, в типичных документах, передаваемых по факсу, примерно 50% черно-белых и бело-черных переходов находятся точно под соответствующими переходами предыдущей строки, а еще 25% отличаются только на одну точку. Поэтому примерно 75% всех переходов можно с большой эффективностью определить относительно предыдущей строки. Эти соображения и стали основой для создания модифицированного кода READ (Modified READ, MR), (Relative Element Address Designate - относительное определение адресов элементов). В схеме MR длины серий кодируются в соответствии с расположением так называемых переключающих элементов. Переключающий элемент (changing element) определяется как точка цвета, отличного от цвета предыдущей точки той же линии. Переключающий элемент а1, кодируется расстоянием от одной из опорных точек: или от предыдущего переключающего элемента а0 в той же строке, или от переключающего элемента b1 в предыдущей строке. Выбор переключающего элемента а0 или b1 зависит от конкретной конфигурации. а0 – стартовый, переключающий элемент кодированной линии, который в начале кодированной линии устанавливается на воображаемый белый переключающий элемент, расположенный левее первого элемента линии, а в процессе кодирования линии переопределяется после каждого шага кодирования; а1 – следующий переключающий элемент справа от элемента а0 в кодированной линии; а2 – следующий переключающий элемент справа от элемента a1 в кодированной линии; b1 – первый, расположенный на опорной линии правее элемента а0 переключающий элемент, цвет которого противоположен цвету а0; b2 – следующий переключающий элемент правее b1 на опорной линии. Рис. 3. Расположение переключающих элементов MR. Процедура кодирования выглядит следующим образом: 1. На первом этапе выбирается один из двух возможных вариантов действий: a. Если переключающий элемент b2 расположен левее переключающего элемента a1, это кодируется словом 0001. После кодирования позиция a1 смещается так, чтобы переключающий элемент a1 располагался под b2. Это называется режимом пропуска. Затем повторяется шаг 1. b. Если предварительное условие не выполняется, переходим к шагу 2. 2. На втором шаге также избирается один из двух возможных вариантов действий: a. Если позиция переключающего элемента a1 находится в пределах трех точек от позиции переключающего элемента b1 (| a1b1 | <3), тогда а1 кодируется вертикально, после чего старая позиция a1 становится новой позицией а0, a2 становится a1 и тому подобное. b. Если позиция переключающего элемента a1 не находящаяся в пределах трех точек от позиции переключающего элемента b1, тогда a1 кодируется горизонтально. Вслед за кодом горизонтального режима 001 a0a1 и a1a2 кодируются с помощью одномерного модифицированного кодирования Хаффмана. Затем старая позиция а2 становится новой позицией а0. Табл. 2. Процедура кодирования MR. Режим Элементы, которые кодируются Нотация Кодовое слово Пропуск b1b2 P 0001 Горизонтальный a0a1, a1a2 H 001+M(a0a1)+M(a1a2) Вертикальный a1 под b1 a1b1=0 Vr(0) 1 a1 справа от b1 a1b1=1 Vr(1) 011 a1b1=2 Vr(2) 000011 a1b1=3 Vr(3) 0000011 a1 слева от b1 a1b1=1 Vl(1) 010 a1b1=2 Vl(2) 000010 a1b1=3 Vl(3) 0000010 Шаг 1 используется для перемещения позиций переключающих элементов и b2 после выполнения шага 2. Кроме этого, шаг 1 позволяет избежать больших серий. На шаге 2, если текущий переключающий элемент, который кодируется, оказывается в пределах трех позиций от такого же перехода в предыдущий линии, тогда его позиция кодируется одним из семи возможных значений с помощью модифицированного кодирования Хаффмана. Эта ситуация сохраняется большую часть времени. В отдельных случаях, когда переход в текущей линии не находящаяся в пределах трех позиций от такого же перехода в предыдущий линии, следующие две серии кодируются с помощью модифицированного кодирования Хаффмана. Схема MR в большей степени чувствительна к ошибкам, чем схема модифицированного кодирования Хаффмана. Результат ошибки может распространяться на непредвиденные расстояния. Чтобы избежать этого, для каждой К-й линии применяется модифицированная схема кодирования Хаффмана. Сектор ITU-T рекомендует значение К = 2 для разрешения 3,85 линии на миллиметр и К = 4 для разрешения 7,7 линий на миллиметр. СЛОВАРНЫЕ МЕТОДЫ СЖАТИЯ Входную последовательность символов можно рассматривать как последовательность строк, содержащих любое количество символов. Идея словарных методов заключается в замене строк символов на такие коды, которые можно трактовать как индексы строк некоторого словаря. Строки, образующие словарь, далее будем называть фразами. При декодировании осуществляется обратная замена индекса на соответствующую ему фразу словаря. Словарь – это набор таких фраз, которые, как мы считаем, будут встречаться в последовательности, которая обрабатывается. Индексы фраз должны быть построены так, чтобы в среднем их представление занимало меньше места, чем требуют строки, которые замещаются. За счет этого и происходит сжатие. Уменьшение размера возможно в первую очередь за счет того, что обычно в данных, которые сжимаются, встречается лишь небольшая часть всех возможных строк длины n, поэтому для представления индекса фразы нужно, как правило, меньшее количество битов, чем для представления исходной строки. Далее, если у нас есть гипотезы, которые заслуживают доверия, о частоте использования тех или иных фраз или проводился какой-то частотный анализ данных, которые обрабатываются, мы можем назначить наиболее вероятным фразам коды меньшей длины. Обычно просто предполагается, что короткие фразы используются чаще, чем длинные. Поэтому в большинстве случаев индексы строятся таким образом, чтобы длина индекса короткой фразы была меньше длины индекса длинной фразы. Такой прием обычно способствует улучшению сжатия. КЛАССИЧЕСКИЕ АЛГОРИТМЫ ЗИВА-ЛЕМПЕЛА Алгоритмы словарного сжатия Зива-Лемпела появились во второй половине 1970-х годов. Это были так называемые алгоритмы LZ77 и LZ78, которые были разработаны совместно Зивом (Ziv) и Лемпелом (Lempel). В дальнейшем первичные схемы подвергались многочисленным изменениям, в результате чего мы сегодня имеем десятки достаточно самостоятельных алгоритмов и бесчисленное количество модификаций. LZ77 и LZ78 являются универсальными алгоритмами сжатия, в которых словарь формируется на основании уже обработанной части входного потока, то есть адаптивно. Принципиальным отличием является лишь способ формирования фраз. В модификациях первичных алгоритмов это свойство сохраняется. Поэтому словарные алгоритмы Зива-Лемпела разделяют на два семейства – алгоритмы типа LZ77 и алгоритмы типа LZ78. Иногда также говорят о словарных методах LZ1 и LZ2. МЕТОД СЖАТИЯ LZ77 Этот словарный алгоритм сжатия является старейшим среди методов LZ. Описание было опубликовано в 1977 году, но сам алгоритм разработан не позднее 1975 года. Алгоритм LZ77 является «основателем» целого семейства словарных схем - так называемых алгоритмов со словарем (или скользящим окном). Действительно, в LZ77 в качестве словаря используется блок уже закодированной последовательности. Как правило, по мере выполнения обработки, положение этого блока относительно начала последовательности постоянно меняется, словарь «скользит» по входному потоку данных. Окно, которое скользит, имеет длину N (то есть в нем содержатся N символов), и состоит из 2 частей: • Последовательности длиной W = N – n уже закодированных символов, которая и является словарем; • Буфера пред идущего просмотра (lookahead) длины n; обычно n на порядки меньше, чем W. Пусть до настоящего момента времени мы уже закодировали t символов s1, s2, ..., st. Тогда словарем будут W предыдущих символов st-(W-1), st- (W-1) + 1, ... st. Соответственно, в буфере находятся символы, которые ожидают кодирования, st + 1, st + 2, ..., st + n. Очевидно, если W ≥ t, то словарем будет вся уже обработанная часть входной последовательности. Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, который начинается с символа st + 1, и всеми фразами словаря. Эти фразы могут начинаться с любого символа st- (W-1), st- (W-1) + 1, ... st и выходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Итак, фразы не могут начинаться с st + 1, поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза st- (i-1), st- (i-1) +1 ..., st- (i-1) + (j-1) кодируется с помощью двух чисел: 1. Смещения (offset) от начала буфера, i; 2. Длины соответствия, либо совпадения (matchlength), j. Смещение и длина соответственно играют роль указателя (ссылки), который однозначно определяет фразу. Дополнительно во выходной поток записывается символ s, котрый непосредственно следует за строкой буфера, которая совпала. Таким образом, на каждом шаге кодер выдает описание трех объектов: смещение и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s (литерала). Затем окно смещается на j + 1 символов вправо и осуществляется переход к новому циклу кодирования. Размер смещения объясняется тем, что мы реально закодировали именно j + 1 символов: j с помощью указателя на фразу в словаре, и 1 с помощью тривиального копирования. Передача одного символа в явном виде позволяет решить проблему обработки еще ни разу не встречающихся символов, но существенно увеличивает размер сжатого блока. Пример: Попробуем сжать строку «кот_ломом_колол_слона» длиной в 21 символ. Пусть длина буфера равна 7 символам, а размер словаря больше длины строки, которая сжимается. Условимся также, что: • Нулевое смещение зарезервировали для обозначения конца кодирования; • Символ s, соответствует единичному смещению относительно символа st+i, с которого начинается буфер; • Если есть несколько фраз с одинаковой длиной совпадения, тогда выбираем самую ближнюю к буферу; • В неопределенных ситуациях – когда длина совпадения нулевая – смещению назначаем единичное значение. Таблица 3. Пример кодирования методом LZ77. Шаг Окно, которое скользит Фраза, которая совпадает Закодированные данные Словарь Буфер i J S 1 - кот_лом - 1 «к» 2 к от_ломо - 1 «о» 3 ко т_ломом - 1 «т» 4 кот _ломом - 1 « » 5 кот_ ломом_к - 1 «л» 6 кот_л омом_ко о 4 1 «м» 7 кот_лом ом_коло ом 2 2 « » 8 кот_ломом_ колол_с ко 9 2 «л» 9 кот_ломом_кол ол_слон ол 2 2 « » 10 …ломом_колол_ слона - 1 «с» 11 …ломом_колол_с лона ло 5 2 «н» 12 …ом_колол_слон а - 1 «а» Для кодирования i нам достаточно 5 битов, для j нужно 3 бита, и пусть символы требуют 1 байт для своего представления. Тогда всего мы потратим 12 * (5 + 3 + 8) = 192 бита. В начале строка занимала 21*8 = 168 бит, то есть LZ77 кодирует нашу строку еще более расточительным образом. Не следует также забывать, что мы опустили шаг кодирования конца последовательности, который требовал бы еще не менее 5 битов (размер поля i = 5 битов). Процесс кодирования можно описать следующим образом: while ( ! DataFile.EOF() ){ /* Найдем максимальное совпадение; в match_pos получим смещение i, в match_len - длину j, в unmatched_sym - первый символ St + i + j, который не совпал; считаем также, что в функции find_match учитывается ограничение на длину совпадения */ find_match (&match_pos, &match_len, &unmatched_sym); /* Запишем в файл сжатых данных описание найденной фразы, при этом длина битового представления i задается константой OFFS_LN, длина представления j - константой LEN_LN, размер символа s принимаем равным 8 битам */ CompressedFile.WriteBits (match_pos, OFFS_LN); CompressedFile.WriteBits (match_len, LEN_LN); CompressedFile.WriteBits (unmatched_sym, 8); for (i = 0; i <= match_len; i++) { // прочитаем очередной символ с = DataFile.ReadSymbol (); // удалим из словаря одну самую старшую фразу DeletePhrase (); /* добавляем в словарь одну фразу, которая начинается с первого символа буфера */ AddPhrase (); /* сместим окно на 1 позицию, добавляем в конец буфера символ с */ MoveWindow(c); } } CompressedFile.WriteBits (0, OFFS_LN); Пример подтвердил, что способ формирования кодов в LZ77 является неэффективным и позволяет сжимать только сравнительно длинные последовательности. До некоторой степени сжатие небольших файлов можно улучшить, используя коды переменной длины для смещения i. Действительно, даже если мы используем словарь в 32 Кбайт, но закодировали еще только 3 Кбайт, то смещение реально требует не 15, а 12 битов. Кроме того, происходит существенный проигрыш из-за использования кодов одинаковой длины при указании длин совпадения j. Статистический анализ больших фрагментов текста (порядка нескольких мегабайт) указывает, что различные длины совпадений фраз встречаются с разной вероятностью. Что касается декодирования сжатых данных, то оно осуществляется путем простой замены кода на блок символов, который состоит из фразы словаря и символа, который передается явно. Естественно, что декодер должен выполнять те же действия с изменением окна, что и кодер. Фраза словаря элементарно определяется смещением и длиной, поэтому важным свойством LZ77 и других алгоритмов с окном, которое скользит, является очень быстрая работа декодера. Алгоритм декодирования может иметь следующий вид. for (;;) { // читаем смещение match_pos = CompressedFile.ReadBits (OFFS_LN); if (!match_pos) // найден признак конца файла, выходим из цикла break; // читаем длину совпадения match_len = CompressedFile.ReadBits (LEN_LN); for (i = 0; i < match_len; i++) { // находим в словаре очередной символ фразу, которая совпала с = Dict (match_pos + i); // смещаем словарь на 1 позицию, добавляем к его началу с MoveDict (c); // записываем очередной раскодированный символ в исходный файл DataFile.WriteSymbol (c); } /* читаем символ, который не совпал, добавляем его в словарь и записываем в исходный файл */ с = CompressedFile.ReadBits (8); MoveDict (c) DataFile.WriteSymbol (c); } Алгоритмы со скользящим окном характеризуются сильной несимметричностью во времени – кодирование значительно медленней декодирования, поскольку при сжатии много времени тратится на поиск фраз. МЕТОД СЖАТИЯ LZSS Алгоритм LZSS позволяет достаточно гибко сочетать в исходной последовательности символы и указатели (коды фраз), что в некоторой степени устраняет свойственное LZ77 расточительство, которое проявляется в регулярной передаче одного символа в прямом виде. Эта модификация LZ77 была предложена в 1982 году Сторером (Storer) и Жимански (Szymanski). Идея алгоритма заключается в добавлении к каждому указателю символа однобитового префикса f, что позволяет различать эти объекты. Иначе говоря, однобитовый флажок f указывает на тип и, соответственно, длину тех данных, которые непосредственно следуют за ним. Такое представление позволяет: • Записывать символы в явном виде, когда соответствующий код имеет большую длину. Значит, словарное кодирование только вредит; • Обрабатывать символы, которые до этого ни разу не встречались. Пример: Закодируем строку "кот_ломом_колол_слона" из предыдущего примера и сравним коэффициент сжатия для LZ77 и LZSS. Пусть мы переписываем символ в явном виде, если текущая длина максимального совпадения буфера и какой-нибудь фразы словаря меньшей или равной 1. Если мы записываем символ, то перед ним выдаем флаг со значением 0, если указатель - со значением 1. Если есть несколько фраз одинаковой длины, которые совпадают, выбираем ближайшую к буферу. Таблица 4. Кодирование методом LZSS. В 15 строчке ошибка 1-5-2 и фраза «кот_ломом_колол_с» В 16 строчке фраза «… колол_сло» Таким образом, для кодирования строки с помощью алгоритма LZSS нам понадобилось 17 шагов: 13 раз символы были переданы в явном виде, и 4 раза мы использовали указатели. Отметим, что при работе алгоритма LZ77 нам понадобилось только 12 шагов. С другой стороны, если задаться теми же длинами для iи j, размер закодированных с помощью LZSS данных равна 13 * (1 + 8) + 4 * (1 + 5 + 3) = 153 битам. Это означает, что строка действительно была сжатой, потому что ее начальный размер – 168 битов. Декодирование информации, сжатой алгоритмом семейства LZ на примере алгоритма LZSS: 0 'к' 0 'о' 0 'т' 0 '_' 0 'л' 0 'о' 0 'м' 1 2 2 0 '_' 1 10 2 1 8 2 0 'л' 0 '_' 0 'с' 1 5 2 0 'н' 0 'а' Таблица 5.Декодирование информации, сжатой алгоритмом семействаLZ на примере алгоритма LZSS. Из алгоритма декодирования видно, что данный процесс исполняется быстрей, чем процесс кодирования, потому что на каждом шаге не нужно многократно использовать поиск в словаре. СЛОВАРНЫЕ МЕТОДЫ СЕМЕЙСТВА LZ С ТАБЛИЧНЫМ СЛОВАРЕМ. МЕТОД СЖАТИЯ LZ78. В данных методах словарь представляет собой ассоциативный массив, ключом которого является индекс фразы, а значением - самая фраза. Первым методом этого семейства стал алгоритм LZ78. Описание работы алгоритма LZ78.: На каждом шаге выполняется поиск самой длинной фразы из буфера в словаре, если фраза найдена, в выходной поток заносятся ее индекс и символ, следующий за ней; в словарь добавляется новая фраза, которая является конкатенацией из найденной фразы и символа. Если фраза не найдена, в выходной поток заносится зарезервированный индекс (на единицу больше чем текущая длина словаря – при условии, что словарь не заполнен до максимального значения его длины ) и символ из входного потока. Пример: Пусть фраза с индексом "1" означает ситуацию, когда ни одна фраза из буфера не найдена в словаре. Таблица 6. Кодирование методом LZ78 Для индекса достаточно 5 битов информации; символ S - 8 бит; каждый шаг кодирования - 8 + 5 = 13 бит; 13 шагов * 13 бит = 169 бит, а начальная фраза составляла 168. АЛГОРИТМ СЖАТИЯ LZW. Алгоритм работы LZW основан на априорном знании входного алфавита. На первом шаге алгоритма весь алфавит заносится в словарь. Кодирование происходит следующим образом: если фраза найдена в словаре, то никакие действия не выполняются, из входного потока извлекается следующий символ и выполняется поиск в словаре уже найденой фразы. Так продолжается до тех пор, пока не будет построена фраза, которой нет в словаре. Когда это произойдет, в выходной поток выводится индекс последней найденной фразы, а текущей фразой становится последний извлеченный из входного потока символ плюс идущий за ним. Часто используется модификация алгоритма, в которой после выполнения начального словаря, заносится код очистки. Этот код выводится в выходной поток для сброса параметров алгоритма, который позволяет сжимать больший объем информации. Таблица 7. Кодирование методом LZW. Необходимо 6 битов для сохранения словаря. Закодированная фраза занимает 6 * 18 = 108 бит, а начальная фраза составляла 169 бит. Общая характеристика словарных методов: Коэффициент сжатия для методов, использующих скользящее окно, составляет 2-4 раза; для методов с табличным словарем - 2,5-5 раз. Отличие в производительности кодера и декодера в 8-10 раз. Как правило, рассмотренные методы редко применяются в чистом виде. Для достижения большего сжатия, к выходному потоку применяют этап вторичного сжатия с применением метода Хаффмана. МЕТОДЫ ВЫЧИСЛЕНИЯ ЦИФРОВЫХ ДАЙДЖЕСТОВ. Цифровым дайджестом называется набор значений, вычисленных на основании какого-либо набора данных. Алгоритм вычисления цифрового дайджеста всегда формирует последовательность одной и той же длины независимо от объема обрабатываемых данных. Как правило, алгоритмы получения дайджестов характеризуются крайне малым количеством коллизий (часто коллизию не удается получить в течение многих лет распределенных вычислений). Сферы применения дайджестов: 1. Проверка целочисленности информации. 2. Создание цифровой подписки. 3. Криптография (шифрование паролей). Применение цифровых дайджестов в криптографии возможно потому, что алгоритмы фактически необратимые и восстановление начального сообщения возможно только путем полного перебора комбинаций. АЛГОРИТМ MD5. Логику вычисления MD5 можно изобразить схемой: Рисунок 4. Логика вычисления MD5. Согласно алгоритму MD5 каждый блок исходного сообщения (512 бит) обрабатывается независимо; в результате этой обработки с начального значения хэш-кода выходит новый промежуточный результат. После обработки последнего блока будет получен окончательный результат. Предварительная обработка данных осуществляется следующим образом: из исходного сообщения получают расширенное, для этого сообщения дополняют единицей и набором нулевых битов так, чтобы его длина, плюс еще 64 бита, была кратной 512. Если сообщение уже имеет такую ​​длину, то к нему все равно добавляется пустой блок. После этого к результату присоединяют 64битовую длину сообщения. Рисунок 5. Обработка каждого 512-битного блока. Для каждого цикла используется своя логическая функция, согласно которой выполняется преобразование 32-битных слов дайджестом. Используются функции: fF=(B∧C) ∨ (not B∧D) fG=(B∧D) ∨ (C∧ not D) fH=B xor C xor D fL=C xor (B ∧ not D) Схема цикла: Рисунок 6. Схема цикла. Обработка 512-битного слова: CLS - циклический сдвиг влево; T [i] - элемент массива, используется для переименования битов. Общая схема преобразования: A = B + CLSs (A + f (B1C1D1) + X [k] + T [i]); CLSs - циклический сдвиг влево на s позиций. Инициализация: A = 0x1234567 B = 0x89ABCDEF C = 0xFEDCBA98 D = 0x76543210 Благодаря такой инициализации даже для пустого сообщение будет вычислено нетривиальное значение хеш-функции. Все сложения при вычислении MD5 выполняются по модулю 2. MD5 имеет достаточную устойчивость для использования при шифровании паролей; для полного перебора понадобится 2128 вычислений хеш-функций, а для поиска коллизии 2128/2 операций, то есть 264. АЛГОРИТМ ИСЧИСЛЕНИЯ ДАЙДЖЕСТА SHA1. Рисунок 7. Логика исчисления SHA1. Логика построения расширенного сообщения совпадает с той, что используется в MD5. Отличается начальная инициализация хэш-кода: A = 0x67452301 B = 0xEFCDAB89 C = 0x98BADCFE D = 0x10325476 E = 0xC3D2E1F0 Обработка каждого 512-битного блока: Рисунок 8. Обработка каждого 512-битного блока. 0≤t≤19 kt=0xA827999 Целая часть 20≤t≤39 kt=0x6ED9EBA1 Целая часть 40≤t≤59 kt=0x8F1BBCDC Целая часть 60≤е≤79 kt=0xCA62C1D6 Целая часть Рисунок 9. Схема цикла. ЛОГИКА ВЫПОЛНЕНИЯ ROUNDХ Таблица 7. Логика выполнения ROUNDX Номер цикла Ft (B, C, D) 0≤t≤19 (B^C) ∨ (~B^D) 20≤t≤ 39 B xor C xor D 40≤t≤ 59 (B^C) ∨ (B^D) ∨ (C^D) 60≤t≤ 79 B xor C xor D Слова Wt вычисляются на основании исходных данных, по которым ведется обработка. Рисунок 10. Вычисление слов. Wt=Wt-16 xor Wt-14 xor Wt-8 xor Wt-3 Таблица 8. Сравнение MD5 и SHA1 Дайджест MD5 SHA1 Длина дайджеста 128 бит 160 бит Размер блока обработки 512 бит 512 бит Количество итераций 64 (4 по 16) 80 Количество эл. лог. ф-ий 4 3 Количество доп. констант 64 4 Реализация MD4, MD5, SHA1: C++; OpenSSL; Java; java.security; System.Security.Cryptography МЕТОДЫ ХРАНЕНИЯ И СЖАТИЯ графической информации. Форматы графических файлов Изображение на экране монитора формируется из маленьких квадратиков (иногда их называют точками) - пикселей. В зависимости от типа монитора и видеокарты количество таких точек на экране может быть разной. Современные видеокарты обеспечивают разрешение 1024 на 768 пикселей и более. Каждому пикселю соответствуют один или несколько байтов видеопамяти, задающие атрибуты пикселя: цвет, яркость. Итак, изображение на экране - это массив в видеопамяти, каждый элемент которого содержит значение атрибутов для одного пикселя. Все графические файлы можно разделить на два больших класса: растровые файлы и векторные. Растровое изображение - это изображение, составленное с помощью отдельных точек. Векторное изображение - изображение, составленное из группы более сложных объектов и представленное с помощью их описания. Изображение, построенное с помощью отдельных точек - пикселей, называется растровым. Реально изображение делится на квадратики (пиксели) и данные о каждом из них кодируются. Такая схема уже много веков назад была придумана для вышивания узоров крестиком. Заметим, что растровые рисунки в компьютерах имеют прямоугольную форму: к любому изображению прилагается фон, превращает рисунок в прямоугольник. Не зная размера пикселя, нельзя построить изображение на основе закодированных данных. На практике используют не размер пикселя, а задают ширину и высоту (в пикселях, в сантиметрах или в других единицах) рисунка и его разрешения. Разрешение экрана - это плотность размещения пикселей. Оно зависит от качества кинескопа монитора. Принятой единицей измерения разрешения является количество точек на дюйм - dpi (Dot Per Inch). При отображении рисунков на мониторе, используют разрешение от 72 dpi до 120 dpi. При печати распространенным разрешением для вывода текста является 300 dpi, но для высококачественной печати можно использовать и более разрешение (1440 dpi). Устройства, которые формируют изображение из отдельных точек, называются растровыми. Видеомонитор, матричный и лазерный принтеры являются растровыми устройствами. Недостатки растровых изображений: • Плохое масштабирование. При уменьшении изображения несколько соседних точек превращаются в одну, потому теряются мелкие подробности. При увеличении масштаба происходит увеличение размера каждой точки, из-за чего происходит ступенчатый эффект. • Большой размер файла, поскольку включены данные про каждый пиксель изображения. ФОРМАТ BMP Формат bmp (от слов BitMaP - битовая карта, или, битовый массив) представляет собой несжатое изображение. Оно достаточно легко читается и выводится в ОС Windows, поскольку в нее включены специальные функции API, которые в этом помогают. По решению разработчиков формат Bmp файла не привязан к конкретной аппаратной платформе. Этот файл состоит из четырех частей: заголовка, информационного заголовка, таблицы цветов (палитры) и данных изображения. Если в файле хранится изображение с глубиной цвета 24 бита (16 млн. цветов), то таблица цветов может отсутствовать. Заголовок файла начинается с сигнатуры "BM", а затем идет длина файла, выраженная в байтах. Следующие 4 байта зарезервированы для дальнейших расширений формата, а заканчивается этот заголовок смещением от начала файла до записанных в нем данных изображения. При 256 цветах это смещение составляет 1078. Информационный заголовок начинается с собственной длины (она может меняться, но для 256-цветного файла составляет 40 байт) и содержит размеры изображения, разрешение, характеристики представления цвета и другие параметры. Ширина и высота изображения задаются в точках растра и объяснений, пожалуй, не требуют. Количество плоскостей могло применяться в файлах, имеющих небольшую глубину цвета. При количестве цветов 256 и больше оно всегда равняется 1, поэтому сейчас это поле уже можно считать устаревшим, но для совместимости оно сохраняется. Глубина цвета считается важнейшей характеристикой способа представления цвета в файле и измеряется в битах на точку. В данном случае она равна 8. Компрессия. В Bmp-файлах обычно не используется, но поле в заголовке для нее предусмотрено. Обычно она равна 0, и это означает, что изображение несжатое. В дальнейшем будем использовать только такие файлы. Размер изображения - количество байт памяти, требуемых для хранения этого изображения, кроме данных палитры. Горизонтальное и вертикальное расширение измеряются в точках растра на метр. Они особенно важны для сохранения масштаба отсканированных картинок. Изображения, созданные с помощью графических редакторов, как правило, имеют в этих полях нули. Количество цветов позволяет сократить размер таблицы палитры, если в изображении реально присутствует меньше цветов, чем это допускает выбранная глубина цвета. Однако на практике такие файлы почти не встречаются. Если количество цветов приобретает значение, максимально допустимого глубиной цвета, например, 256 цветов при 8 битах, поле становится нулевым. Количество основных цветов - идет с начала палитры, и его желательно выводить без искажений. Это поле бывает важным тогда, когда максимальное количество цветов дисплея было меньше, чем в палитре Bmp-файла. При разработке формата, очевидно, принималось, что цвета, которые чаще всего встречаются, будут располагаться в начале таблицы. Сейчас это требование практически не соблюдается, то есть цвета не упорядочиваются по частоте, с которой они встречаются в файле. Это очень важно, поскольку палитры двух разных файлов, даже состоящих из одних и тех же цветов, удерживали бы их (цвета) в разном порядке, что могло существенно осложнить одновременный вывод таких изображений на экран. Вслед за информационным заголовком следует таблица цветов, является массивом из 256 (по числу цветов) 4-байтовых полей. Каждое поле соответствует своему цвету в палитре, а три байта из четырех - компонентам синей, зеленой и красной составляющих для этого цвета. Последний, самый старший байт каждого поля зарезервирован и равен 0. После таблицы цветов находятся данные изображения, которое по строкам растра записано снизу вверх, а внутри строки - слева направо. Поскольку на некоторых платформах невозможно считать единицу данных, которая меньше 4 байт, длина каждой строки выровнена на границу в 4 байта, то есть при длине строки, некратной четырем, она дополняется нулями. Это обстоятельство обязательно нужно учитывать при считывании файла, хотя, возможно, лучше заранее позаботиться, чтобы горизонтальные размеры всех изображений были кратны 4. СТРУКТУРА BMP-ФАЙЛА Таблица 9. Структура BMP-файла. Имя Длина Смещение Описание Заголовок файла (BitMapFileHeader) Type 2 Сигнатура «BM» Size 4 2 Размер файла Reserved 1 2 6 Зарезервировано Reserved 2 2 8 Зарезервировано OffsetBits 4 10 Смещение изображения от начала файла Информационный заголовок (BitMapInfoHeader) Size 4 14 Длина заголовка Width 4 18 Ширина изображения, точки Height 4 22 Высота изображения, точки Planes 2 26 Количество плоскостей BitCount 2 28 Глубина цвета, бит на точку Compression 4 30 Тип компрессии (0 – несжатое изображение) SizeImage 4 34 Размер изображения, байт XpelsPerMeter 4 38 Горизонтальное расширение, точек на метр YpelsPerMeter 4 42 Вертикальное расширение, точек на метр ColorsUsed 4 46 Количество цветов, которые используются (0 – максимально возможное для данной глубины цвета) ColorsImportant 4 50 Количество основных цветов Таблица цветов (палитра) (ColorTable) ColorTable 1024 54 256 элементов по 4 байта Данные изображения (BitMap Array) Image Size 1078 Изображение, которое записано по строкам слева направо и снизу-вверх. ФОРМАТ GIF Рисунок 11. Минимально необходимый набор блоков – самый простой не анимированный gif. Таблица 10. Таблица для разных глубин цвета изображения. Таблица 11. Таблица для разных размеров палитр и количества цветов картинки СЖАТИЕ РАСТРОВЫХ ИЗОБРАЖЕНИЙ Пиксель является неразделимой точкой в графическом изображении растровой графики на экране монитора. Он характеризуется прямоугольной формой и размерами, определяющих пространственное разрешение изображения. Беда растровых файлов в том, что они большие, даже очень большие. Если пренебречь заголовками файла и другими неграфические данными, его размер пропорционален количеству пикселей в изображении и количеству битов, необходимых для представления каждого пикселя. Полноцветная картинка размером 1024х768 пикселей занимает более двух мегабайт памяти. Используя метод, называемый сжатием изображений, можно резко уменьшить в размере графические файлы. Существует два способа сжатия: 1. Без потерь информации 2. С потерями. Если мы сохраняем чертежи, то, естественно, что сжатие с потерями нас не устроит, сохраняя же какую-то картинку, обобщения оттенков ее цветов вполне допустимо, а иногда приводит и к удачным спецэффектам. Краткое описание формата GIF: GIF один из самых распространенных и популярных в Интернете форматов изображений. Такое широкое распространение GIF во многом определяется особенностями его формата Общие данные:   • Размер картинки-от 1х1 до 65535х65535 пикселей.   • Количество цветов палитры - от 2 до 256.   • Каждый цвет палитры имеет глубину 24 бита / пиксель (выбор из 16000000 цветов). • Карта прозрачности - 1-битная (полупрозрачных цветов нет). • Количество повторов анимации - от 1 до 65535, а также бесконечное. • Время показа одного кадра анимации - от 1/100 секунды до 655 секунд. • Количество кадров анимации – неограниченное • Количество невидимых текстовых комментариев и размер каждого комментария – неограниченно. Структура GIF-файла: 1. Файлы формата GIF имеют блочную структуру. Это означает, что они состоят из отдельных блоков, которые в большинстве случаев никак не связаны друг с другом. Программы, не распознают некоторые типы блоков, могут просто пропускать их - для этого у каждого нестандартного блока в заголовке указан его размер. Блоки графики (картинки), идущие один за другим, составляют анимацию. Они меняются на экране и создают иллюзию движения. До или после них (или даже между ними) в файле могут находиться другие блоки: 1. Комментарии. Скрытый текст, его можно увидеть только с помощьюспециальных программ - например, GIF-аниматоров, таких, как UleadGIFAnimator. 2. Простой текст. Строки символов с ограниченными возможностями форматирования. Сейчас не используется. 3. Блоки управления графикой, задающие параметры вывода отдельных картинок. 4. Глобальная и локальные палитры цветов, определяющих, какие именно цвета будут у картинок. 5. Особые блоки, которые могут использоваться только теми программами, которыезнают об их существовании и назначения - например, блок Netscape, задает количество циклов анимации. Без него анимация после загрузки страницы срабатывает только один раз. Минимальный необходимый набор блоков для простогонеанимированного GIF (смотреть рис. 11): 1. Дескриптор логического экрана. 2. Глобальная палитра. 3. Дескриптор изображения. 4. Изображение. В начале каждого файла GIF находится заголовок. поскольку сразу за ним идет дескриптор логического экрана, заголовок считается его частью. Он состоит из текста "GIF87a" или "GIF89a", в зависимости от версии Дескриптор - это просто "описатель" или "описание". Логический экран - область реального экрана компьютера, куда выводятся все картинки данного файла GIF. Они могут иметь разный размер и занимать различное положение на логическом экране. W, H - ширина и высота логического экрана в пикселях, то есть размер области вывода картинок. Изображения, которые не умещаются на логическом экране, должны обрезаться по его размеру. BG - номер цвета фона. Если в файле присутствует глобальная палитра, то этим цветом заливаются области фона, где нет картинок. Но если при этом в первом, еще до всех картинок, расширении управления графикой включена прозрачность, то этот цвет считается прозрачным. R - соотношение сторон исходного изображения. В версии GIF87a это поле зарезервировано, и здесь стоят нули. Насколько известно, этот параметр никогда и никем не используется. Предполагалось, что пиксель экрана может быть и не квадратным, как было в старых компьютерах и как сейчас бывает при некоторых режимах DOS, и для вывода таких изображений необходимо менять разрешение экрана или растягивать изображение так, чтобы оно выглядело реалистичным. CT - наличие глобальной палитры. Если этот флажок установлен, то сразу после дескриптора глобального экрана должна начинаться глобальная палитра. Размер палитры определяется полем Size. Color - цветовое разрешение начальной картинки. Число битов, которое приходится на каждый из трех основных цветов. Если файл GIF создан непосредственно с полноцветного изображения, то Color равен 7, а если с уже индексированного, то его значение будет зависеть от глубины цвета этой индексированной картинки, причем очень приблизительно. Например, если файл создан на основе 16-цветной картинки, то Color должно быть равным 1, и начальная палитра должна равняться 1, начальная палитра предполагается 64 цветной. - флажок сортировки палитры. В версии GIF87a этот бит зарезервирован, и здесь стоит ноль. Указывает, что палитра отсортирована по значимости цветов, когда первыми идут наиболее значимые цвета. Значимость цвета определяется тем, какую площадь изображения он занимает по отношению к другим цветам. - размер палитры и количество цветов картинки. Если флажок глобальной палитры сброшен, то в этом поле должны стоять нули. Глобальная палитра Изображения, хранящиеся в файле GIF – это индексированные картинки состоящие не из полноцветных пикселей, а из номеров цветов, а сами цвета находятся в палитре. Палитра составлена из триад, которые в свою очередь состоят из байтов красного, зеленогои синего основных цветов. Из всего разнообразия цветов (современные компьютеры и мониторы могут показывать на экране до 16 миллионов цветов) используется только от 2 до 256. Возведение числа цветов к минимуму без значительного ухудшения качества изображения и без потери информации - сродни искусству, и автоматизации поддается плохо. Многие графические редакторы - такие как Adobe Photoshop, например - позволяют интерактивно выбрать лучший вариант индексации картинки «на глаз» Если она есть, глобальная палитра идет сразу за дескриптором логического экрана. Наличие палитры определяется флагомдескриптора, а размер – полем Глобальная палитра действует на все картинки, в которых нет своей локальной палитры. В том аварийном случае, если в файле нет не глобальной, не локальных палитр, программа просмотра может действовать по своему усмотрению - например, использовать системную палитру. Однако рекомендуется, чтобы первые два цвета в ней черными и белыми, чтобы в любом случае на экран вывелось хоть что-то. Дескриптор изображения Действует на графический блок (картинку), что идет за ним. Без него картинка выводится не будет, так что его можно считать неотъемлемой частью графического блока. Между дескриптором и блоком графики может находиться только локальная палитра. - ширина и высота картинки в пикселях. - положение картинки на логическом экране. - наличие локальной палитры. Если этот флажок установлен, то сразу после дескриптора изображения должно начинаться локальная палитра. Размер палитры определяется полем - через строчная или обычная развертка картинки при выводе на экран. При скачивании картинки из Интернета через строчная развертка позволяет быстрее получить первое впечатление о картинке, хотя оно будет еще недостаточно четким. Однако файлы с через строчная разверткой немного больше по размеру, а при просмотре в отключенном режиме такие картинки могут выводиться медленнее. - флажок сортировки палитры. В версии GIF87a этот бит зарезервирован, и здесь стоит ноль. Указывает, что палитра отсортирована по значимости цветов, когда первыми идут наиболее значимые цвета. Значимость цвета определяется тем, какую площадь изображения он занимает по отношению к другим цветам. - размер глобальной палитры и число цветов картинки (см. выше). Если флажок локальной палитрысброшен, то должны стоять нули. Локальная палитра Если она есть, должна идти сразу за дескриптором изображения. Наличие палитры обозначается флажком , а размер – полем . Действует она только на тот графический блок (картинку), который идет сразу за ней. Для уменьшения размера файла лучше ограничиться одной глобальной палитрой, не прибегая к локальным - особенно, если речь идет о многоцветных картинках. Максимальный размер палитры при 256 цветах - 768 байт, а если умножить на число картинок в анимации, то сумма набегает солидная. Графический блок Картинка, сжатая с помощью метода LZW. Она разбита на отдельные субблоки по 255 байт. Число картинок в файле, как и размер каждой картинки, ничем не ограничены. Анимированным GIF становится в том случае, если в нем больше одной картинки. Тогда при просмотре файла в браузере автоматически включается анимация. MC - начальный размер LZW-кода. Равный глубине цвета картинки, исключая двухцветные, когда MC равен не 1, а 2. Таблица 12. Начальный размер LZW-кода S - размер субблока данных, не включая сам байт S. Во всех субблоках, кроме последнего, размер должен быть равен 255 байт. У последнего субблока (или если он вообще один) размер может быть любым - от 1 до 255 байт. Расширение управления графикой Введено в версии GIF89a. Действует на первый же графический блок (картинку), что идет за ним. Между ним и блоком графики могут быть вставлены другие блоки (например, комментарий) - это его работе не мешает. Delay - время задержки, в 1/100 сек. Время, в течение которого эта картинка остается на экране. Минимальное значение - 1/100 секунды, максимальное - примерно 655 секунд. Таймер начинает отсчет только после того, как картинка выведена на экран, поэтому в различных программах просмотра время задержки может существенно различаться. Например, если попытаться сделать анимированные GIF - часы, то они могут, в зависимости от браузера, в минуту спешить или отставать более чем на секунду. Tr - номер прозрачного цвета. Если есть локальная палитра, это номер цвета в ней, если же локальной палитры нет, то это номер цвета в глобальной палитре. Disp - способ замены картинки после показа: Таблица 13. Способ замены картинки UI - ожидается реакция пользователя. Еще один никогда и никем не используемый параметр. Предполагалось, что если этот флажок установлен, то после вывода этой картинки для продолжения анимации и вывода следующих необходимо, например, щелкнуть кнопкой мыши. TF - флажок прозрачности. Если он установлен, эта картинка выводится с прозрачным фоном, цвет которого определяется параметром Tr. Расширение простого текста Введено в версии GIF89a. Предполагалось, что вместе с картинками будут передаваться текстовые сообщения, появляющиеся на экране в паузах между ними или поверх них. Поскольку символы больше 0xF7 не выводимы (заменяются на пробелы), это делает расширение непригодным для вывода символов кириллицы (русских букв). Сейчас все тексты в файлах GIF идут в виде картинок, так что это расширение никогда и никем не используется. Left, Top-положение области текста на логическом экране. W, H - размер области текста. Строки, которые выходят за ее рамки, обрезаются. Переносы строки должны быть заранее вставлены в текст. cW, cH - размер символов. Рекомендуется использовать значение 8х8 или 8х16 пикселей, что сейчас годится только для DOS. FG - номер цвета текста. BG - номер цвета фона. Этим цветом заливаются области фона, где нет текста. S - размер субблока данных, не включая сам байт S. Во всех субблоках, кроме последнего, размер должен быть равен 255 байт. У последнего из субблоков (или если он вообще один) размер может быть любым - от 1 до 255 байт. Расширение комментария Введено в версии GIF89a. В основном сюда записывают данные об авторских правах создателей файла GIF - и людей, и программы. Длинный текст можно ожидать в том случае, если программа бесплатная или условно бесплатная. Длина текста ничем не ограничивается. S - размер субблока данных, не включая сам байт S. Во всех субблоков, кроме последнего, размер должен быть равен 255 байт. У последнего субблоков (или если он вообще один) размер может быть любым - от 1 до 255 байт. Расширение дополнения Введено в версии GIF89a. Расширение приложения - это специальные блоки данных - не картинки и не текст. С ними могут работать только те программы (приложения), для которых они предназначены. Крупнейшим известным стало расширение приложения Netscape, которое описывается ниже. ID - идентификатор приложения. Текст из 8 символов, по которому программа просмотра определяет, сможет ли она прочитать данные, и какого они типа. Code - код идентификатора. Предполагалось, что программа, которая создала GIF, будет синтезировать двоичный код для подтверждения своих прав на это расширение. На деле здесь тоже находится текст с 3 символов. S - размер субблока данных, не включая сам байт S. Во всех субблоках, кроме последнего, размер должен быть равен 255 байт. У последнего субблока (или если он вообще один) размер может быть любым - от 1 до 255. Расширение дополнения NetScape Должен идти сразу после глобальной палитры (если она есть) или дескриптора логического экрана (если ее нет). Единственная цель этого расширения - установить количество циклов анимации. Как можно догадаться, первым применением, которое могло использовать эту информацию, был браузер Netscape 2.0. Сейчас это расширение присутствует почти во всех файлах GIF, где есть анимация. ? - Здесь стоит 0x01, но это значит, неизвестно. Возможно, сначала этот байт предполагалось использовать, но затем он оказался ненужным. Loop - количество циклов анимации, от 0 до 65535. Здесь есть некоторые особенности. Во-первых, без расширения Netscape цикл анимации срабатывает, но только один раз. Если же вставить расширения Netscape в файл и установить Loop = 1, то цикл будет прокручиваться дважды, как и при Loop = 2. А при Loop = 0 анимация крутится бесконечно, так что необходимо ее отключение, для того, чтобы выводилась только одна первая картинка, в другом случае это оказывается невозможным. Вывод Может показаться, что формат GIF со своими 256 цветами уже окончательно устарел, однако по сравнению с другой техникой вывода изображений он даже может в чем-то и выигрывать. Например, применение для создания анимированных кнопок и баннеров вместо картинок GIF техники Flash предполагает, что на каждом браузере установлен плагин Flash или элемент ActiveX Flash нужной версии. Это может в отдельных случаях привести к тому, что пользователи не только не смогут увидеть рекламу, но и вообще не смогут попасть на этот сайт, тогда как поддержка GIF встроена во все браузеры, начиная с самых первых версий. Формат PNG, который завоевывает все большую популярность, при всех своих неоспоримых плюсах (полноцветная картинка, прозрачность с альфаканалом), не может обеспечивать такого сильного сжатия малоцветных изображений, не говоря уже об анимации. Его анимированная модификация MNG пока не поддерживается ни одним браузером. Другие новые форматы - такие, как JPEG 2000 - ориентированы в основном на фотографические изображения и не составляют серьезной конкуренции формату GIF, тем более что пройдет еще много времени, пока браузеры во всем мире будут пользоваться поддержкой этих новых форматов. В настоящее же время GIF, вместе с JPEG, остается одним из двух основных форматов изображений, используемых в Интернете, и, скорее всего, будет служить нам еще долго. АЛГОРИТМ JPEG В алгоритме JPEG исходное изображение представляется двумерной матрицей размера N * N, элементами которой являются цвет или яркость пикселя. Упаковка значений матрицы выполняется в три этапа. 1. Дискретное косинусное преобразование 2. Этап Квантования 3. Этап Вторичного сжатия Высокая эффективность сжатия, которую дает этот алгоритм, основана на том факте, что в матрице частотных коэффициентов, которая образуется из исходной матрицы после дискретного косинусного преобразования, низкочастотные компоненты расположены ближе к левому верхнему углу, а высокочастотные - внизу справа. Это важно потому, что большинство графических образов на экране компьютера состоит из низкочастотной информации, так что высокочастотные компоненты матрицы можно безболезненно выбросить. «Выброс» выполняется путем округления частотных коэффициентов. После округления отличные от нуля значения низкочастотных компонент остаются, главным образом, в левом верхнем углу матрицы. Округленная матрица значений кодируется с учетом повторов нулей. В результате графический образ сжимается более чем на 90%, теряя очень немного в качестве изображения только на этапе округления. Дискретное косинусное преобразование Дискретное косинусное преобразование (ДКП) является преобразованием массива пикселей в массив значений пространственной частоты. Это преобразование является обратным с точностью до ошибок округления. Оно позволяет переходить от пространственного представления изображения к его спектральному представлению и обратно. Изображение, представленное матрицей размера NxN, может быть представлено с помощью коэффициентов двумерного косинусного преобразования следующим образом: Само ДКП выглядит следующим образом: В алгоритме JPEG используют ДКП исходного изображения блоками размера 8х8 пикселей. Размер выбран так, чтобы не сильно увеличивать вычислительную сложность алгоритма и при этом иметь минимум визуальной потери качества изображения. ДКП для удобства осуществляется последовательно, в несколько этапов. Сначала создается ДКП матрица 8х8, использующая формулу: В результате имеем: Начальное изображение поддается смещению уровня яркости так, чтобы значения яркости были симметричны относительно 0. Для изображений, содержащих 256 цветов, данная процедура совершается путем отнимания от значений яркости пикселей 128. Например, нам нужно сжать следующий фрагмент изображения: Вот формула, по которой приводится ДКП: RES = DCT * IMG * DCT Для начала надо рассчитать промежуточную матрицу: TMP = IMG * DCT Потом умножаем ее на ДКП матрицу: RES = TMP * DCT Этап квантования На этом этапе мы вычисляем матрицу квантования, используя этот псевдо код: for i:=0 to 7 do for j:=0 to 7 do Q[i,j] = 1+((1+i+j)*q); Где q – коэффициент качества, от него зависит степень потери качества сжатого изображения. Для q = 2 имеем матрицу квантования: Теперь надо каждое число в матрице RES разделить на число в соответствующей позиции в матрице квантования, в результате получим: Как видим, тут достаточно много нулей, мы получаем наиболее длинную последовательность нулей, если будем использовать алгоритм зигзагообразного обхода блока: Таблица 13. Зигзагообразный обход блока 1 2 6 7 15 16 28 29 3 5 8 14 17 27 30 43 4 9 13 18 26 31 42 44 10 12 19 25 32 41 45 54 11 20 24 33 40 46 53 55 21 23 34 39 47 52 56 61 22 35 38 48 51 57 60 62 36 37 49 50 58 59 63 64 Итак, мы получили последовательность: 30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0 0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Этап вторичного сжатия Наиболее распространенным методом вторичного сжатия является метод Хаффмана и его разновидности. Восстановление изображения, сжатого с помощью алгоритма JPEG. При распаковке изображения выполняется обратная последовательность шагов: 1. Выполняется декодирование данных, полученных в результате вторичного сжатия. На этом этапе восстанавливается матрица квантованных коэффициентов. 2. Выполняется деквантование матрицы, в результате чего получается матрица близкая к исходной матрице, полученной после косинусного преобразования. Она близка, но не точна, за счет округления на этапах квантования и деквантования. 3. Выполняется обратное дискретное косинусное преобразование, которое восстанавливает первоначальный массив пикселей. JPEG без потерь Это самый простой режим работы без потери данных, основанный на прогнозируемой модели. Как правило, этот метод позволяет достичь коэффициента сжатия около 2:1, что значительно меньше, чем коэффициенты, которые могут быть достигнуты в методах, основанных на ДКП. Одно из отличий: обрабатывается все изображение, а не блок размера 8х8. При сканировании изображения каждое значение пикселя заменяется значением: Результат = Пиксель - Прогноз Здесь «Прогноз» – значение, основанное на значениях некоторых отсканированных ранее соседних пикселях. Смысл заключается в следующем: как правило, значение пикселя на реальном изображении близкое к значениям соседних точек. Поэтому прогноз, основанный на значениях соседних пикселей, должно быть близким к фактическому значению или совпадать с фактическим значением. Если преобразовать матрицу пикселей в разностную матрицу, основанную на прогнозах, многие значения окажутся равными нулю, а остальные будут небольшие. Преобразованное изображение должно упаковываться компактнее. Для упаковки, как правило, применяют метод Хаффмана. Схема JPEG без потерь позволяет использовать прогноз, основанный на значениях некоторых или всех пикселей, смежных с текущим, но встреченных ранее в процессе сканирования слева направо или сверху вниз для каждого пикселя, кроме пикселей левого столбца и верхнего ряда, у которых есть только один предыдущий пиксель. рис. 13 Размещение пикселей Возможны следующие режимы кодирования: табл. 14 Режимы кодирования Режим кодирования Прогноз Отсуствует 1 A 2 B 3 C 4 A+B+C 5 A+((B-C)/2) 6 B+((A-C)/2) 7 (A+B)/2 Как видно из рисунка и таблицы, алгоритм сжатия без потерь может быть настроен для любой комбинации предыдущих точек. В режимах с 1 по 3 используются одномерные прогнозы. В режимах с 4 по 7 – двумерные. Какие из них задействуются, зависит от реализации и положения пикселя, который кодируется. В любом случае задействуются следующие правила: 1. Значение прогноза для левого верхнего пикселя равно 2^(P - 1), где P – глубина цвета исходного изображения. 2. Для других точек верхнего ряда прогноз основывается на значении левого соседа (режим 1). 3. Для других точек левого столбца прогноз основывается на значении соседа сверху (режим 3). Основы сжатия изображений Основные задачи, решаемые при цифровой обработке изображений: Пример кодирования JPEG DCT-матрица для блока 8х8 пикселей Начальное изображение: Изображение после смещения яркости: Матрица IMG * DCT Результирующая матрица ДКП: Матрица квантования для q = 2: Результат квантования: Результат обхода: 30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0 0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Обратное ДКП: Принцип превращения матрицы изображения в JPEGбез потерь: Результат = Пиксель – Прогноз ОБРАБОТКА ЗВУКОВЫХ СИГНАЛОВ Звуковая информация представляется в цифровом виде в двух принципиально разных формах – WAVE и MIDI. WAVE – форма используется для цифровых аудиодисков, а MIDI - в электронных музыкальных инструментах. WAVE-форма звука WAVE-форма звука получается при оцифровке, или дискретизации, непрерывной звуковой волны (англ. wave – волна), точнее, аналогового аудиосигнала. При оцифровке специальное устройство – аналого-цифровой преобразователь (АЦП) – измеряет амплитуду волны через равные промежутки времени со скоростью несколько тысяч измерений в секунду и запоминает в Wave-файл измеренные значения. Они называются выборками (по англ. sample, откуда еще одно название дискретизации – сэмплинг). Обратное преобразование WAVE-формы звука в аналоговый сигнал осуществляется цифро-аналоговым преобразователем (ЦАП). На рис. 14 представлена фонограмма первых 10 секунд 40-й симфонии Моцарта, содержащий 2 205 000 выборок. Если на вашем компьютере установлена звуковая плата, вы сможете ее прослушать, щелкнув мышью на картинке. На рис. 15 показан фрагмент записи, содержащий только 50 выборок, начиная с места, отмеченного на рис. 14 вертикальной чертой. рис. 14 Фонограмма первых 10 секунд 40-ой симфонии Моцарта рис. 15 Фонограмма симфонии Моцарта WAVE-форма цифрового звука характеризуется пятью параметрами: • Частотой дискретизации, • Разрядностью выборок, • Количеством каналов или звуковых дорожек, • Алгоритмом компрессии/декомпрессии – кодеком, • Форматом хранения. Чистота дискретизации Под дискретизацией сигналов понимают преобразование функций непрерывных переменных в функции дискретных переменных, по которым исходные непрерывные функции могут быть восстановлены с заданной точностью. Каждое значение функции дискретной переменной называется отсчетом. Очень часто роль отсчетов выполняют квантованные значения функций в дискретной шкале координат. Под квантованием понимают преобразование непрерывной по значениям величины в величину с дискретной шкалой значений из конечного множества разрешенных, которые называют уровнями квантования. Сущность квантования состоит в округлении мгновенных значений входной функции до ближайших значений уровней квантования. Если уровни квантования нумерованы, то результатом преобразования является число, которое может быть выражено в любой числовой системе. Количество выборок в секунду называется частотой дискретизации и измеряется в герцах и килогерцах (1 кГц=1000 выборок в сек.). При определении количества выборок следует учитывать, что чем меньше интервал между отсчетами (выборками) dt, тем больше будет частота дискретизации и сигнал будет описан точнее. С другой стороны, для обработки такого сигнала будет нужен больший объем памяти, большие ресурсы процессора, больше времени. Поэтому для определения оптимальной частоты дискретизации пользуются теоремой Котельникова (Котельникова - Найквиста). Теорема гласит: Если непрерывный сигнал x(t), который существует на всей числовой оси и имеет ограниченный спектр [- w, w] заменить отсчетами с минимальным шагом dt=pi/Wm=1/2Fm, то по этой множественном числе отсчетов возможно безошибочное восстановление сигнала x(t). То есть теоретически, для правильного восстановления аналогового сигнала по его цифровой записи достаточно, чтобы частота дискретизации более чем в два раза превосходила максимальную частоту звука. рис. 16 Определение оптимальной частоты дискретизации Таким образом, для качественного воспроизведения самого звука 20 кГц, что возможно услышать, нужна частота дискретизации не менее 40 кГц. Стандарт CD - DA цифровых аудиодисков требует частоты дискретизации 44,1 кГц (так называемое CD-качество). Используются также частоты 22,05 (радио - качество) и 11,025 и 8 кГц (телефонное качество), что во многих случаях дают удовлетворительные результаты (например, для записи речи). Звук является сложным сигналом, но, как и любой другой сигнал, он может быть представлен с помощью ряда Фурье в виде суммы постоянных составляющих, а также синусов и косинусов, то есть гармонических сигналов (или гармоник). Но при оцифровке звука дискретизируются и высокочастотные гармоники с частотой, превышающей половину частоты дискретизации (это высокочастотный, неслышимый шум). При этом появляются новые нежелательные гармоники из слышимого диапазона (низкочастотный шум, см. рис. 17). рис. 17 Появление низкочастотных помех Поэтому для получения качественного цифрового звука процесс дискретизации строится по следующей схеме: • частичное подавление высокочастотных помех в аналоговом сигнале с помощью аналогового фильтра; • оверсэмплинг – дискретизация с частотой, что значительно превышает требуемую (при этом шум, что образуется, все еще лежит в нечувствительном диапазоне); • подавление высокочастотного шума в цифровом звуке с помощью цифрового фильтра; • преобразование к требуемой частоте дискретизации. Оверсэмплинг применяется и при обратном преобразовании к аналоговому сигналу. При этом используются различные методы линейной и нелинейной интерполяции. Разрядность выборки Измеренная амплитуда (выборка) превратится в целое число с некоторой погрешностью, которая определяется разрядностью этого числа. Это преобразование в числа с заданной разрядностью называется квантованием. Погрешность при квантовании вносит шум тем больше, чем меньше разрядность. Теоретически, при n-разрядном квантовании отношение сигнал/шум (динамический диапазон) будет 6n дБ. Таким образом, при 8-разрядном оцифровке динамический диапазон 48 дБ (качество УКВ-радио, достаточная для языка), а при 16-разрядной оцифровке он равен 96 дБ и практически покрывает весь нормально слышимый диапазон. Другими словами, при 8-разрядном кодировании различаются 256 уровней громкости, а при 16-разрядном – 65536, что дает более точную запись. На CD-DA применяется 16-разрядное квантование. Звуковые платы компьютеров обычно используют 8 и 16-разрядное квантование. Применение оверсэмплинга в АЦП и ЦАП позволяет значительно уменьшить шум, который добавляется при квантовании. Каналы Обычные звуковые платы позволяют использовать 1 или 2 звуковых канала (дорожки) WAVE-звука – "моно" и "стерео". Оба канала обрабатываются отдельно по одним и тем же алгоритмам, хоть и одновременно. Поэтому нет принципиальных ограничений на число каналов. Увеличение количества каналов ведет к пропорциональному увеличению объема памяти, которую занимает звуковая информация. Основные методы обработки звука: сжатие, аналоговая фильтрация, цифровая фильтрация. Компрессия звука Обозначим • W – объем памяти в байтах для хранения 1 секунды звука в WAVE-форме, • w – скорость потока звуковых данных в WAVE-форме в бит/сек, • H – частоту дискретизации (число выборок в секунду), • B– разрядность квантования (число разрядов на выборку), • C – количество каналов. Тогда очевидно, что w = H*B*C, если B кратно 8, W = w/8. Итак, • скорость потока данных CD-качества (H=44100, B=16, C=2) составляет 1 411 200 бит/сек или 1378,125 Кбит/сек (такая скорость обеспечивается только CD -дисководом с не менее, чем 2-кратной скоростью), • 1 час звука с качеством CD-DA нуждается 605,6 Мбайт (поэтому на аудиодиске помещается около 70 минут несжатого звука), • скорость потока данных телефонного качества (H=8000, B=8, C=1) составляет 64000 бит/сек или 62,5 Кбит/сек (такая скорость обеспечивается далеко не каждым модемом, поэтому такой звук не может использоваться в Интернет - телефонии). С целью уменьшения объема и потока звуковых данных в WAVE-форме используются различные специальные алгоритмы компрессии/декомпрессии (кодеки), поскольку обычные алгоритмы сжатия информации здесь не дают эффекта. Сжатие аудиоданных возможно лишь с некоторой потерей информации, но учет психофизиологических особенностей восприятия звука (например, не все частоты в слышимом диапазоне существенные для восприятия), позволяет в ряде случаев сделать эти потери практически незаметны. Однако следует учитывать очень высокую чувствительность человеческого слухового аппарата, особенно временных характеристик звука. Наиболее известными являются следующие кодеки, которые используются в мультимедиа под Windows: • PCM (PulseCodeModulation) – импульсно-кодовая модуляция (ИКМ) – сжатие может достигаться только за счет выбора меньших значений величин H, B и C (фактически, это несжатая звук); квантование происходит по равномерной шкале из 2B значений; • DPCM (DifferentialPCM) – дифференциальная ИКМ (ДИКМ) – выборка представляет разницу от предыдущей, что требует меньше B битов; сжимает в несколько раз; • ADPCM (AdaptiveDPCM) – адаптивная ДИКМ (АДИКМ) – то же, что ДИКМ, только квантование происходит не по равномерной шкале, а с учетом динамики изменений амплитуды; сжимает в несколько раз; • MPEG (MotionPictureExpertsGroup) – стандарты Группы экспертов в области кино; для сжатия звуковой информации используются стандарты MP2 и MP3; применяется психоакустическая компрессия, при которой удаляются звуки, не воспринимаемые человеческим ухом; сжимает в несколько десятков раз при достаточно высоком качестве; • RealAudio – метод, разработанный фирмой RealNetworks, сжимает в несколько десятков раз, но с невысоким качеством; используется в Интернете для проигрывания звуковых файлов в реальном времени. Для цифровой телефонии используются, как правило, другие кодеки. Спектральная (частотная) форма представления сигналов использует разложение сигнальных функций на периодические составляющие. Периодичность гармонических колебаний исследовал еще в VI веке до нашей эры Пифагор и даже распространил ее на описание гармонического движения небесных тел. Термин «spectrum» («спектр») впервые применил И. Ньютон в 1571 году при описании разложения солнечного света, пропущенного через стеклянную призму, на многоцветную полосу. Он же дал и первое математическое трактовку периодичности волновых движений. В 18-м веке решениями волновых уравнений (в приложении к струнам) занимались Даниил Бернулли и Леонард Эйлер. По сути, уже Бернулли и Эйлера показали, что произвольные периодические функции представляют собой суммы простейших гармонических функций – синусов и косинусов кратных частот. Эти суммы получили название рядов Фурье, после того, как в 1807 году французский инженер Жан Батист Фурье обосновал метод вычисления коэффициентов тригонометрического ряда, которым можно показать с абсолютной точностью (при бесконечном количестве членов ряда) или аппроксимировать с заданной точностью (при ограниченном количестве членов ряда) любую периодическую функцию, определенную на интервале одного периода T = b - a, и что удовлетворяет условиям Дирехле (ограниченная, кусочно-непрерывная, с конечным числом разрывов 1-го рода). А если быть точнее: На первых этапах своего развития данное направление разложения функций, получившее название гармонического анализа, имело более теоретический характер и использовалось, в основном, в естественных науках для выявления и изучения периодичности и состава периодических составляющих (в том числе скрытых) в различных явлениях и процессах (активность солнца, девиация магнитного поля Земли, метеорологические наблюдения, высота приливов в гаванях и тому подобное). Положение резко изменилось с появлением электротехнических и радиотехнических отраслей науки и техники и развитием радиосвязи, где гармонический состав сигналов приобрел конкретного физического смысла, а математический аппарат спектрального преобразования функций стал основным инструментом анализа и синтеза сигналов и систем. Сегодня спектральный анализ является одним из основных методов обработки экспериментальных данных во многих отраслях науки и техники. В качестве базисных функций разложения сигналов, в общем случае, принимаются комплексные экспоненциальные функции exp(jft), от которых с использованием формул Эйлера можно перейти к вещественным синус – косинусных функций. Термин «частотная» обязан происхождением обратная переменной f = 1/|t| временного представления сигналов и функций. Понятие частотного преобразования не следует связывать только с временными аргументами, поскольку математический аппарат преобразования не зависит от физического смысла независимых переменных. Так, например, при переменной "х", как единице длины, значение f будет пространственной частотой с размерностью 1/|х – число периодических изменений сигнала на единице длины. В математическом аппарате частотного анализа удобно использовать угловую частоту ω = 2πf. Для процессов с другими независимыми переменными в технической литературе вместо индекса частоты f часто используется индекс v, а для угловой частоты индекс k = 2πv, который называют волновым числом. РАЗЛОЖЕНИЕ СИГНАЛОВ ПО ГАРМОНИЧЕСКИМ ФУНКЦИЯМ Понятие собственных функций Удобство использования частотного представления сигналов заключается в том, что гармонические функции являются собственными функциями операций переноса, интегрирования, дифференцирования и других линейных операций, инвариантных по координатам. Предположим, что начальная функция является линейной комбинацией функций синуса и косинуса: 𝑠(𝑥) = 𝐴sin(𝑥) + 𝐵cos(𝑥) Осуществим произвольный сдвиг функций с аргументом на величину h. При этом получаем: 𝑠(𝑥 + ℎ) = 𝐶sin(𝑥) + 𝐷cos(𝑥) 𝐶 = 𝐴cos(ℎ) − 𝐵sin(ℎ) 𝐷 = 𝐴sin(ℎ) + 𝐵cos(ℎ) где коэффициенты C и D, как и в начальном выражении коэффициенты А и В, не зависят от аргумента, при этом C2+D2=А2+В2. Таким образом, при произвольном переносе функции с аргументом (а равно и при интегрировании, дифференцировании и других линейных преобразованиях) любую линейную комбинацию синуса и косинуса можно представить линейной комбинацией этих же функций. Экспоненциальная комплексная запись гармонических функций делает это свойство еще нагляднее. Для произвольной гармонической функции имеем: cos(𝜔𝑡 − 𝜑) = 𝐴cos(𝜔𝑡) + 𝐵sin(𝜔𝑡) де𝐴=cos(𝜑),𝐵=sin(𝜑),𝜑–начальный фазовый угол колебания при t = 0. Переходя к комплексной записи данной функции с использованием тождеств Эйлера: Получаем: Где, - величина, комплексно сопряженная с С. Применяя в качестве гармонической составляющей разложения сигнала функцию ехр(jωt), можно рассматривать вторую функцию ехр(–jωt), комплексно сопряженную с первой, как такую же составляющую, но с отрицательной частотой. Естественно, что отрицательная частота является чисто математической абстракцией, но нужно помнить, что пара таких комплексно сопряженных составляющих в сумме всегда дает вещественную функцию. Экспоненциальные функции также являются собственными функциями линейных операций. Для операции переноса с использованием экспоненциальных функций: , где - собственное значение операции переноса, независимое от переменной. Для операции дифференцирования: Для операции интегрирования: В общей форме для любых операций преобразования: где T[.] – произвольный линейный оператор, Н(ω) – собственное значение операции, независимо от аргумента. У специалистов-практиков существует предубеждение против использования комплексных функций с их мнимыми частотами. Поэтому в дальнейшем будем использовать и вещественные функции, и их комплексные аналоги, по крайней мере, до тех пор, пока простота и удобство использования последних не станет очевидной. Ряды Фурье Разложению в ряды Фурье подвергаются периодические сигналы. Периодическую функцию любой формы, заданную на интервале одного периода Т = b - a ту, что удовлетворяет на этом интервале условиям Дирехле (ограниченная, кусочно - непрерывная, с конечным числом разрывов 1-го рода), можно представить в виде ряда Фурье: , где весовые коэффициенты Snряда определяются по формуле: Ряд Фурье является ансамблем комплексных экспонент exp(jnΔωt) с частотами, образующими арифметическую прогрессию. Функцию весовых коэффициентов S(nΔω) принято называть комплексным спектром периодического сигнала или Фурье-образом функции s(t). Спектр периодического сигнала является дискретной функцией, поскольку он определен только для целых значений n с шагом по частоте, обратным к периоду: Δω = 2π/Т (илиΔf = 1/T). Первую частотную составляющую спектра при n = 1, равную ω1 = 1*Δω = 2π/T (или f1 = 1/T), называют основной частотой сигнала (первой гармоникой), другие частоты дискретного спектра nω1 при n>1 называют гармониками сигнала. Значение S(nω1) по положительным и отрицательным значениях n являются комплексно сопряженными. С чисто математических позиций множество функций exp(jnΔωt) образует бесконечномерный базис линейного пространства L2[a, b] ортогональных синус-косинусных функций, а коэффициенты Sn по (2) являются проекциями сигнала s(t) на эти базисные функции. Соответственно, сигнал s(t) в форме ряда Фурье (1) - это бесконечномерный вектор в пространстве L2[a, b]. Подынтегральную функцию экспоненты в выражении (2) с использованием тождества Эйлера exp(-jωt)=cos(ωt) – j*sin(ωt) можно разложить на косинусную и синусную составляющие и выразить комплексный спектр в виде действительной и мнимой частей: На рис. 18 приведен пример периодического сигнала (прямоугольный импульс на интервале (1-3.3), повторяющийся с периодом Т=40) и форма действительной и мнимой части его спектра. Обратим внимание, что действительная часть спектра является четным относительно нуля функцией A(n) = A(- n), поскольку при вычислении значений A(n) по формуле (4) используется парная косинусна функция cos(nt) = cos(-nt). Мнимая часть спектра является нечетной функцией B(n) = -B(-n), поскольку для ее вычисления по (5) используется нечетное синусная функция sin(nt) = - sin(-nt). рис. 18 Сигнал и его комплексный спектр. Комплексные числа дискретной функции (3) могут быть представлены в виде модулей и аргументов комплексной экспоненты, что дает следующую форму записи комплексного спектра: Sn = Rn exp(jn), (4.1.3') Rn2≡ R2(n) = A2(n)+B2(n), n ≡ (n) = arctg(-B(n)/A(n)). рис. 19 Модуль и аргумент спектра. Модуль спектра R(n) называют двусторонним спектром амплитуд, а аргумент спектра (последовательность фазовых углов (n)) - двусторонним спектром фаз. Спектр амплитуд всегда является четной функцией: R(n) =R(- n),  а спектр фаз нечетную(: n(-) = -n).  Пример спектра в амплитудном и фазовом представлении для сигнала, показанного на рис. 18, приведен на рис. 19. При рассмотрении спектра фаз следует учитывать периодичность 2 угловой частоты (при уменьшении фазового значения до величины меньше - происходит сброс значения - 2). рис. 20 Ортогональность функций Если функция s(t) является четной, то все значения B(n) по (5) равны нулю, поскольку четные функции ортогональные синусным гармоникам и подынтегральное произведение s(t) - sin(nt) дает нулевой интеграл. Следовательно, спектр функции будет представлен только вещественными коэффициентами. Наоборот, при нечетности функции s(t) обнуляются все значения коэффициентов А(нечетные функции ортогональным косинусным гармоникам) и спектр является чисто мнимым. Этот фактор не зависит от выбора границ задачи периода функции на числовой оси. На рис. 20(А) можно наглядно видеть ортогональность первой гармоники синуса и четной функции, а на рис. 20(В) соответственно косинуса и нечетной функции в пределах одного периода. Учитывая кратность частот следующих гармоник первой гармонике спектра, ортогональность сохраняется для всех гармоник ряда Фурье. При n = 0 имеем Во = 0, и получаем постоянную составляющую сигнала: Тригонометрическая форма ряда Фурье. Объединяя в (1) комплексно комбинированные составляющие (члены ряда, симметричные относительно центрального ряда S(0), можно перейти к ряду Фурье в тригонометрической форме: Значение An, Bn вычисляются по формулам (4-5), значения Rn и φn - по формулам (3'). Рядом (6) является разложение периодического сигнала s(t) на сумму вещественных элементарных гармонических функций (косинусных и синусных) с весовыми коэффициентами, удвоенные значения которых (т. е. значения 2An, 2Bn) не что иное, как амплитуды соответствующих гармонических колебаний с частотами n. Совокупность амплитудных значений этих гармоник образует односторонний физически реальный (только для положительных частот n) спектр сигнала. Для сигнала на рис. 18, например, он полностью повторяет правую половину приведенных на рисунке спектров с удвоенными значениями амплитуд (за исключением значения Ао на нулевой частоте, которое, как это следует из (6), не удваивается). Но такое графическое отображение спектров используется довольно редко (за исключением чисто технических приложений). Широкое применение для отображения физически реальных спектров находит формула (6'). Спектр амплитуд косинусных гармоник при таком отображении называется амплитудно-частотным составом сигнала, а спектр фазовых углов гармоник - фазовой характеристикой сигнала. Форма спектров повторяет правую половину соответствующих двусторонних спектров (см. рис. 19) также с удвоенными значениями амплитуд. Для четных сигналов отсчеты фазового спектра могут принимать только значения 0 или, для нечетных соответственно /2. рис. 21 Разложение сигнала в комплексный ряд Фурье Ряды Фурье произвольных аналоговых периодических сигналов могут содержать бесконечно большое количество членов. Однако одним из важных достоинств преобразования Фурье является то, что при ограничении (усечение) ряда Фурье до любого конечного числа его членов обеспечивается лучшее по средней квадратической погрешности приближение к исходной функции (для этого количества членов). На рис. 21 показано разложение в комплексный ряд Фурье модельного сигнала, выполненное в среде Mathcad. Модель сигнала задана с тремя разрывами первого рода (скачками). Любой скачок функции содержит все частоты диапазона до бесконечности, в связи с чем ряд Фурье также бесконечен и очень медленно затухает. На рисунке приведены значения только первых 100 членов ряда, при этом график спектра сигнала, как это обычно принято на практике, построенный в виде той, что огибает значений модулей коэффициентов ряда Sn и только по области положительных значений n. Программа на рис. 22 продолжает программу рис. 21 и показывает реконструкцию сигнала по его спектру при ограничении числа членов ряда Фурье. На верхнем графике рисунка приведен реконструированный сигнал при N = 8 (гармоники первого пика спектра, центр которого соответствует главной гармонике сигнала и члену ряда n = s/, N = 16 (гармоники двух первых пиков) и N=40 (пять первых пиков спектра). Естественно, что чем больше членов ряда включено в реконструкцию, тем ближе реконструированный сигнал к форме исходного сигнала. рис. 22. Реконструкция сигнала (продолжение программы на рис. 21) Принцип последовательного приближения к изначальной формы наглядно видно на нижнем графике рисунка. На нем же можно видеть и причины появления пульсаций на реконструкции скачков функций, которые носят название эффекта Гиббса. При изменении количества суммированных членов ряда эффект Гиббса не исчезает. Не изменяется также относительная амплитуда пульсаций (по отношению к амплитуде скачка) и относительное затухание (по коэффициенту последовательного уменьшения амплитуды пульсаций по отношению к максимальному выбросу), меняется только частота пульсаций, определяемая частотой последних суммированных гармоник. ИСПОЛЬЗОВАНИЕ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(ДПФ) Дискретная временная область. Дискретная частотная область. Дискретное преобразование Фурье (ДПФ). Обратное ДПФ. • Цифровой спектральный анализ • Анализаторы спектра • Обработка языка • Обработка изображений • Распознавание образов • Проектирование фильтров • Вычисление импульсной характеристики по частотной • Вычисление частотной характеристики по импульсной Быстрое преобразование Фурье (БПФ) - это простой алгоритм для эффективного вычисления дискретного преобразования Фурье (ДПФ) рис. 23 Семейство преобразований Фурье как функция сигнала во временной области Дискретное преобразование Фурье (ДПФ), которое оперирует дискретной по времени выборкой периодического сигнала во временной области. Для того, чтобы быть представленным в виде суммы синусоид, сигнал должен быть периодическим. Но в качестве набора входных данных для ДПФ доступно только конечное число отсчетов (N). Эту дилемму можно разрешить, если мысленно поместить бесконечное число одинаковых групп отсчетов до и после группы, обрабатывается, образуя, таким образом, математическую (но не реальную) периодичность. Фундаментальное уравнение для получения N -точечного ДПФ выглядит следующим образом: По отношению к этому уравнению следует сделать некоторые терминологические разъяснения. X(k) (прописная буква X) является частотным выходом ДПФ в k-й точке спектра, где k находится в диапазоне от 0 до N-1. N является числом отсчетов при вычислении ДПФ. Значение x(n) (строчная буква x) представляет собой n-й отсчет во временной области, где n находится в диапазоне от 0 до N-1. В общем уравнении x(n) может быть вещественным или комплексным. Обратите внимание, что косинусоидальные и синусоидальные компоненты в уравнении могут быть выражены в полярных или прямоугольных координатах, связь между которыми определяется по формуле Эйлера: e jθ = cos θ + j sin θ Выходной спектр ДПФ X(k) является результатом вычисления свертки между выборкой, состоящей из входных отсчетов во временной области, и набором из N пар гармонических базисных функций (косинус и синус). Концепцию хорошо иллюстрирует рис. 24, на котором представлена вещественная часть первых четырех точек спектра (показаны только косинусоидальные гармонические базисные функции). Подобная процедура используется для вычисления мнимой части спектра на основе синусоидальных функций. Первая точка X(0) является простой суммой входных отсчетов во временной области, потому что cos(0) = 1. Коэффициент масштабирования 1/N не учитывается, но должно присутствовать в конечном результате. Обратите внимание, что X(0) - это среднее значение отсчетов во временной области, или просто смещение по постоянному току. Вторая точка ReX(1) получена умножением каждого отсчета из временной области на соответствующее значение косинусоиды, что имеет один полный период на интервале N, с последующим суммированием результатов. Третья точка ReX(2) получена умножением каждого отсчета из временной области на соответствующее точку косинусоиды, которая имеет два полные периоды на интервале N, с последующим суммированием результатов. Так же, четвертая точка ReX(3) получена умножением каждого отсчета из временной области на соответствующее точку косинусоиды с тремя полными периодами на интервале N и суммированием результатов. Этот процесс продолжается, пока не будут вычислены все N выходных отсчетов. Подобная процедура, но с использованием синусоид, применяется для вычисления мнимой части частотного спектра. Косинусоиды и синусоиды являются базисными функциями данного преобразования. рис. 24 Свертка отсчетов во временной области с базисными функциями при БПФ для N=8 Предположим, что входной сигнал является косинусоидальным, таким, что имеет период N, то есть он содержит один полный период в нашей выборке. Также примем его амплитуду и фазу идентичными первой косинусоидальной базисной функции cos(2πn/8). Выходной спектр содержит одну ненулевую точку ReX(1), а все другие точки ReX(k) являются нулевыми. Предположим, что теперь входная косинусоида сдвинута вправо на 90. Значение свертки между ней и соответствующей базисной косинусоидальной функцией равен нулю. Но алгоритм преобразования предполагает вычисление свертки с базисной функцией sin(2πn/8), необходимое для получения ImX(1). Это показывает, почему необходимо исчислять и вещественные, и мнимые части спектра для определения и амплитуды и фазы частотного спектра. Обратите внимание, что свертка синусоидальной/косинусоидальной функции любой частоты, отличной от частоты базовой функции, дает нулевое значение и для ReX(1), и для ImX(1). Подобная процедура применяется при вычислении обратного ДПФ для восстановления отсчетов во временной области x(n) из отсчетов в частотной области X(k). Соответствующее уравнение выглядит следующим образом: Существуют два основных типа ДПФ: вещественное ДПФ и комплексное ДПФ. Комплексное ДПФ, где и входные, и выходные величины являются комплексными числами. Поскольку входные отсчеты во временной области являются вещественными и не имеют мнимой части, мнимая часть входных отсчетов всегда принимается равной нулю. Выход ДПФ X(k) содержит вещественную и мнимую компоненты, которые могут быть преобразованы на амплитуду и фазу. Вещественное ДПФ выглядит несколько проще и, в основном, является упрощением комплексного ДПФ. Большинство алгоритмов вычисления быстрого преобразования Фурье (БПФ) составленны с использованием формата комплексного ДПФ, поэтому важно понимать, как работает комплексное ДПФ и как оно соотносится с вещественным ДПФ. В частности, если известны исходные частоты вещественного ДПФ и требуется использовать обратное комплексное ДПФ для вычисления отсчетов во временной области, нужно знать, как разместить исходные точки вещественного ДПФ в формате комплексного ДПФ перед выполнением обратного комплексного ДПФ. Быстрое преобразование Фурье Алгоритмы БПФ основаны на том, что при уменьшении длины последовательности решене задачи также уменьшается, но не пропорционально, а гораздо больше. Пусть сигнал x(n) имеет N отсчетов, причём N=2m. Разобьем сигнал на две последовательности: Тогда спектры этих последовательностей будут определены как: Тогда общий спектр будет выглядеть как: Этот алгоритм называется БПФ с прореживанием по времени. Число отсчетов в этом алгоритме не зря выбрано как степень числа 2. Это позволяет разбивать последовательность к двухточечному преобразования Фурье: рис. 25 Вычисления 8-точечного БПФ в трех каскадах с использованием прореживания по времени Пример вычисления БПФ для 8 отсчетов Дискретное преобразование Фурье: ФормулаЭйлера: e jθ= cos θ + j sin θ Обратная ДПФ: