В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 148
Текст из файла (страница 148)
Например, строка из 200 черных точек подряд может быль выражена как 64 . 3 + 8. Для этого сектором 1Т11-Т были определены восемь образцов докуме!гсов и рассчитаны вероятности нахохсцения в документах серий различных длин. Поскольку для серий из черных и белых точек эти вероятности различаются, были сосчитаны два множества вероятностей.
На основе полученной информации были составлены две таблицы (табл. 20.3). Длина серии делится на 64, после чего частное и остаток от деле!п!я кодируются двумя кодовыми словами. Если длина серии меньше 64 (частное от деления равно нулю), то такая длина серии кодируется только кодовым словом остатка. Серии длиной более 64 точек кодируются двумя кодами: кодом остатка (п) и кодом кратности (т), Имеется еше несколько деталей, касаюшихся этого кода.
Кахсдая строка заканчивается уникальным кодовым словом ЕО1. (Епе! 011зпе — конец строки). Это кодовое слово, никогда не встречающееся в строках данных, обеспечивает восстановление синхронизации в случае ошибок. Внутри строки должны чередоваться кодовые слова для белых н черных серий. Ооратите внимание нато, что для белых и черных серий используются различные кодовые слова. Это обеспечивает дополнительную защиту от ошибок. Наконец, по соглашению кюкдая строка начинается с белой серии. Если первая то пса в линии черная, то используется белая серия нулевой длины. Кодо 0 1 2 3 4 5 б 7 8 9 10 1! 12 13 14 15 1б 17 18 19 20 21 22 23 24 25 2б 27 28 29 ЗО 31 32 ЗЗ 34 35 Зб 37 38 39 00110101 000111 0111 1000 1011 ! тоо 1110 1111 10011 10100 00111 01000 ОО!000 000011 110100 110101 101010 101011 0100111 0001100 0001000 0010111 00000! 1 0000100 0101000 0101011 0010011 0100100 0011000 00000010 00000011 00011010 00011011 00010010 00010011 00010100 00010101 00010110 00010111 00101000 0000110111 010 11 10 011 0011 0010 00011 000101 000100 0000100 0000101 000011! 00000100 00000!11 000011000 0000010111 ООООО!1000 0000001000 ОООО!100111 00001101000 00001101100 00000110111 00000101000 00000010111 00000011000 000011001010 000011001011 000011001100 000011001101 000001101000 000001101001 00000110т010 000001101011 000011010010 000011010011 000011010100 000011010101 000011010110 000011010111 20.2.
Факсимильное сжатие 639 638 Глава 20, Сжатие без потерь таБлица 20.3 (продолжение) Черная сарая Белая сарая Длина серии Черная серия Белая серия Длина серии 011010110 О!1010111 011011000 011011001 01Ю11010 01101!011 010011000 010011001 о!ооыою 011000 010011011 000000000001 0000001110101 0000001110110 0000001110111 00000010100!О 0000001010011 0000001010100 0000001010101 0000001011010 0000001011011 0000001100100 0000001100101 000000000001 1088 1152 1216 !28О 1344 1408 1472 1536 1600 !ББ4 1728 501. выа слова кратности 64 0000001111 000011001000 000011001001 000001011011 000000110011 000000110100 000000110101 0000001101100 0000001101101 0000001001010 00000010010!1 0000001001100 0000001001101 0000001110010 0000001110011 0000001110100 11011 10010 010111 0110111 00110110 00110111 01100100 01100101 О!101000 011001!1 011001!ОО 011001101 011010010 011010011 011010100 011ОЮ101 40 41 42 43 44 45 4Б 47 48 49 50 51 52 53 54 55 56 57 58 59 БО Б1 62 63 Кало 64 128 !92 256 320 384 448 512 576 640 704 7Б8 832 896 9БО Ю24 0010100! 00101010 00101011 00101100 00101101 00000100 00000101 00001010 ОООО!О!! 01010010 01010011 01010100 01010101 00100100 00100101 01011000 01011001 01011010 01011011 010010!О 01001011 00110010 001100!1 00110100 000001101100 000001101101 000011011010 000011011011 000001010100 0000010Ю101 000001010110 000001010111 000001100100 000001100Ю1 000001010010 000001010011 000000100100 0000001 Ю111 000000111000 000000100111 000000101000 000001011000 000001011001 000000101011 000000101100 000001011010 000001100110 000001100111 МодиФицированный код ВЕА0 Использование модифицированного кода Хаффмана значительно сокращает количество передаваемых битов по сравнению с передачей несжатого растрового изображения.
Дополнительного увеличения производительности можно добиться, зная о корреляции между последовательностями черно-белых серий точек в двух соседних линиях. В самом деле, в типичных документах, передаваемых по факсу, приблизительно 50 % черно-белых и бело-черных переходов находятся точно под соответствующими переходами в предыдущей строке, а еще 25 % отличаются всего на одну точку [2071, Поэтому примерно 75 % всех переходов можно с большой эффективностью определить относительно предыдущей строки. Эти соображения и послужили ос!юной для создания модифицированного кода КЕМ (Мог)16!ег1 КВАТ, МК). В схеме МК длины серий кодируются в соответствии с расположением так называемых переключающих алементов.
Переключающий элелтектл (сЬапп1ий е!ешепт) определяется как точка цвета, отличного от цвета предыдугцей точки той же самой линии. Переключающий элемент а, кодируется расстоянием от одной из двух опорных точек: либо от предыдущего переключшощего элемента эа в той же линии, либо от переключающего элемента Ь, в предыдущей линии. Выбор переключающего элемента аа или Ь, зависит от конкрепюй конфигурации, о чем будет подробнее сказано далее. Парис.
203 показаны пять переключающих элементов, определенные для этой схемы следующим образом: + аа — опорный, или стартовый, переключающий элемент кодируемой ливии, который в начале копируемой линии устанавливается на воображаемый белый переключающий элемент, располага!ощийся левее первого элемента линии, а в процессе кодирования липин переопределяется после кюклого шага кодирования; + а1 — следующий переключающий элемент справа от элемента аа в кодируемой ли~ни; 640 Глава 20. Сжатие без потерь 20.2. Факсимильное сжатие 641 + а, — следующий переключающий элемент справа от элемента а| в кодируе- мой линии; + Ь| — первый расположенный на опорной линии правее элемента ае переклю- чающий элемент, цвет которого противоположен цвету а„; + Ьг — следующий переключающий элемент вправо от Ь| на опорной линии. вертикальный режим Опорная линия Кодируемэя лнн Горизонтальный режим Вертикальный н п|риэонтэльный режимы ь Ь Опорная линия Ксднруемэя линия а, Режим пропуска Рис.
20.3. Переключающие элементы иэображения в схеме МП Процедура кодирования, которую иллюстрирует табл. 20.4, выглядит следую|цим образом: 1. На первом шаге выбирается один из двух возможных вариантов действий: + Если переклк|чающий элемент Ъг расположен левее переключающего элемента аь это кодируется словом 0001. После кодирования позиция а| сдвигается так, чтобы переключающий элемент а| располагался под Ьг. Это называется режимом пропуска. Затеи повторяется шаг 1.
Если предыдущее условие не выполняется, переходим к шагу 2. 2. 1.1а втором шаге тоже выбирается один из двух возможных вариантов действий: Если позиция переключающего элемента а, находится в пределах трех точек от позиции переключающего элемента Ь ~ ((а|Ь г! < 3), тогда а| кодируется вертикально, после чего старая позиция а| становится новой поЗИЦИЕй ае, аг СтаНОВ1ГГСЯ а| И т. Д.
Если позиция переключагошего элемента а| не находится в пределах трех точек от позиции переключающего элемента Ь|, тогда а, кодируется пн ризонтально. Следом за кодом горизонтального режима 001 ага| и а|а| кодируются при помощи одномерного модифицированного кодирования Хаффмана. Затем старая позиция а| становится новой позицией ае. Кодируеыые элементы Нотация Кодовое алово Пропуск Горизонтальный % Вертикальный а ача,а, а| точно под Ь, а, правее Ь, а,ь, =о У(0) Уя(1) Уе[2) уе(3) У|(1) У,(2) У|(З) а,Ь,=З а,Ь, = 1 а,Ь! — — 2 а, левее Ь, Шаг 1 используется для перемещения позиций переключающих элеме|ггов Ь| и гпослев Ь после выполнения шага 2. Кроме того, шаг 1 позволяет избежать больших длин серий.
а й. На шаге 2, если текущий кодируемый переключающий элемент оказывается в пределах трех позиций от такого же перехода в предыдущей линии, тогда его позиция кодируется одним из семи несмежных значений при помощи модифицированного кодирования Хаффмана. Эта ситуация сохраняется большую часть времени. В редьп|х случаях, когда переход в текущей линии не находится в пределах трех позиций от такого же перехода в предыдущей линии, следующие две серии кодируются прн помощи модифицированного кодирования Хаффмана. Схема МК в Гюльшей степени чувствительна к ошибкам, чем схема модифицированного кодирования Хаффмана. Результат ошибки может распространяться на непредс казуемые расстояния.
Чтобы избежать этого, для каждой К-й липни при- ТБ-Т екоменяется модифицированная схема кодирования Хаффмана. Сектор 1 - рекомендует значение К = 2 для разрешения 3,85 линии на миллиметр и К = 4 для разрешения 7,7 линии на миллиметр. Дважды модифицированный код НЕА0 Дважды модифицированный алгоритм КЕАР (Мос()1)ее) Мог)(бес( КЕАР, ММК) определен для аппаратуры факсимильной связи группы 4 в рекомендации Т.6 сектора 1Т()-Т. Он отличается от модифицированного алгоритма КЕАР (МК) тем, что из него была удалена проверка ошибок, что позволило увеличить степень сжатия алгоритма.
Поскольку аппаратура группы 4 предназначена для работы на высококачественных линиях с низкой вероятностью ошибок, такой компромисс кажется разумным. Таблица 20.5 иллюстрирует эффективность работы модифицированной схел|ы кодирования Хаффмана и обеих модифицированных схем КЕАР с одним и тем (14). же набором страниц в качестве образца. Об этих результатах сообщалось в ( Сходные результаты приводятся в 1183) н 1243). Результаты работы этих схем кодирования также сравниваются со стандартом кодирования ) В1б () о)пГ В1шайе ехрег(з Огоср — объединенная группа экспертов по двухуровневой обработке изображений), определенным в рекомендациях Т.82'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
