Файл: Методы кодирования данных (Кодирование и методы кодирования ).pdf

Использование кодов ТЭСИ требует обеспечения высокой степени достоверности кодированной информации. В классификаторах ТЭСИ для выявления ошибок в кодах используется метод контрольных чисел.

Контроль правильности записи кодов при обработке информация основан на принципе делимости чисел. Иначе его называют контролем по модулю. Суть метода заключается в том, что к коду добавляется ещё один проверочный знак --контрольное число, связанный с кодом определенной математической зависимостью. При вводе кодированной информации в базу данных, ее обработке или использовании в ЭВМ специальной программой контроля выполняется проверка этой зависимости по каждому коду. Если зависимость нарушается, машина выдает информацию о наличии ошибки в коде.

Контроль по модулю широко используется в классификаторах ТЭСИ как у нас в стране, так и за рубежом. В качестве модуля используют различные числа, но наибольшее распространение получил в настоящее время контроль по модулю 11. Для общероссийских классификаторов расчет контрольных чисел осуществляется в соответствии с методикой, разработанной ВНИИКИ". В соответствии с этой методикой контрольным числом является остаток от деления на 11 суммы произведений весов на значения разрядов кода. Весом (весовым коэффициентом) является порядковый номер разряда в коде слева направо. [13]^[7]

Формула, по которой вычисляется контрольное число, имеет следующий вид:

КЧ=? a_ix_i-11

где КЧ - контрольное число по модулю 11,

a_i - вес i-го разряда кода,

x_i - значение I -го разряда кода,

? a_ix_i - модуль 11, т.е целая часть суммы произведений значений разрядов кода на их веса.

Методика ВНИИКИ предлагает использовать в качестве весов натуральный ряд чисел от 1 до 10. Если разрядность кода больше 10, то набор весов повторяется. При использовании данного метода остаток может получить значение от 0 до 10. Так как методика предусматривает использование одноразрядных контрольных чисел, то при получении остатка, равного 10, следует сделать повторный расчет контрольного числа со сдвигом строки весов. В этом случае весовой ряд начинается с 3 до 10, а если разрядность кода больше, то дальше веса идут с 1 до 10. В случае повторного получения контрольного числа, равного 10, в качестве контрольного числа используется 0. В случае, если сумма произведений весов на значения разрядов получается меньше 10, то эта сумма и является контрольным числом.

ГЛАВА 2. СУЩЕСТВУЮЩИЕ МЕТОДЫ КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ И ВИДЕО ДАННЫХ

2.1.КОДИРОВАНИЕ ИЗОБРАЖЕНИЙ

2.1.1. АЛГОРИТМЫ БЕЗ ПОТЕРИ ДАННЫХ

Алгоритмы сжатия информации без потери данных – это метод компрессии, при котором можно восстановить сжатье изображение с точностью до бита. Сжатие основано на статистической избыточности [1]^[8] - соседние пикселы имеют одинаковое или близкое друг другу значения цветового тона и яркости. Например изображение серых гор на фоне голубого неба с белыми облаками.

Но у этих алгоритмов есть недостаток. Если в изображении значения цвета и яркости пикселов никак не совпадают, то есть отсутствует статистическая избыточность, то сжатия статистическими методами не добиться.

2.1.2. КОДИРОВАНИЕ ДЛИН СЕРИЙ RLE

RLE (Run-Length Encoding) – один из самых старых и самых простых методов кодирования. Он основан на замене последовательности одинаковых элементов парами кодовых элементов – количество одинаковых значений и само значение [2]^[9]. Если встречается последовательность не из одинаковых значений, то первое значение пары устанавливается 0, а второе является счетчиком, который показывает количество неповторяющихся элементов.

Коэффициент сжатия, которое обеспечивает данный алгоритм можно рассчитать по формуле (1)

где k – коэффициент сжатия; m – число уровней квантования яркости в кодируемом изображении; нов - вероятность появления новой последовательности; N – максимальная протяженность последовательности

Для записи числа повторений одинаковых отсчетов в последовательности необходимо затратить log₂N двоичных единиц, а также необходимо затратить log₂m двоичных единиц для записи значения самой величины [2]^[10].

Формула показывает, что коэффициент сжатия зависит от вероятности появления новой последовательности. При 265 уровнях квантования эта вероятность, по статистике, приближается к единице. Тогда коэффициент сжатия окажется равен меньше единицы – «сжатое» изображение окажется объёмней исходного. Объясняется это тем, что добавляется информация о длительности последовательности, хотя эта длительность почти всегда равна единице.

К достоинствам данного алгоритма можно отнести простоту и быстродействие [7].^[11]

Данный метод предназначен для узкоспециализированной графики, такой как чертежи, плакаты и т.п., так как такие графические изображения содержат однородные участки, большие последовательности одинаковых пикселов. Применяется в графических форматах BMP, TIFF, GIF, TGA, PCX.

2.1.3. КОДИРОВАНИЕ МЕТОДОМ LZW

Алгоритм назван по первым буквам фамилий разработчиков - Лемпель-Зив-Велч (Lempel-Ziv-Welch, LZW). Предком LZW является алгоритм LZ78, созданный Абрахамом Лемпелем (Abraham Lempel) и Якобом Зивом (Jacob Ziv) в 1978г. Однако в то время алгоритм воспринимался как математическая абстракция. В 1984 году был доработан Терри Уэлчем (Terry Welch). Опубликование алгоритма произвело большое впечатление на всех специалистов по сжатию информации [2].^[12]

Сжатие происходит следующим образом. Создается таблица, в которую записываются все символы исходного алфавита. В общем случае 8-битного алфавита, первые 256 записей (отдельные символы с номерами от 0 до 255) заносятся в словарь до поступления сжимаемых файлов [8]. Далее в таблицу записываются коды очистки 256 и конца записи 257. Алгоритм накапливает поступающие символы в строке. После добавления нового символа кодер ищет строку в таблице. Если строка присутствует в таблице, то добавляется следующий символ. Когда строка не обнаруживается в таблице, полученная последовательность символов записывается в таблице, а на вывод поступает код предыдущего «опознанного» кода. Во входной строке остаётся только что поступивший символ. Код очистки используется, чтобы не допустить переполнения таблицы, которая по принятому соглашению ограничена 12 двоичными единицами (максимум 4095 значений). При использовании кода очистки стираются значения, записанные в таблицу, начиная с кода 258. Тем самым освобождается место для следующих встречающихся в изображении комбинаций. Код конца записи говорит о том, что кодируемая последовательность закончилась.

Таким образом, алгоритм кодирования можно описать следующими шагами:

Создать первоначальную таблицу кодов;

Во входную строку занести первый символ из сообщения «Х»;

Считать следующий символ «Y»;

Если «Y» - код конца записи, то на выход отправить код, соответствующий символу «Х», иначе:

а) Если фразы «XY» нет в таблице, на выход отправить код символа

«Х», а фразу «XY» записать в таблицу. Во входной строке остается символ

«Y»;

б) Если фраза «XY» есть в таблице, перейти к считыванию следующего символа входной последовательности (шаг 3).

Декодирование построено так, что для получения исходного файла не нужно передавать таблицу кодов последовательностей. Она создаётся в процессе декодирования тем же методом, что и при кодировании.

В начале создается таблица с кодами символов исходного алфавита. Во входную строку поступают коды символов, которые используются как указатели для таблицы. Когда во входной строке появляется отсутствующая в таблице последовательность, она записывается. Так как таблица кодов декодирования заполняется «синхронно» или шаг в шаг с таблицей кодирования, не может оказаться неопознанных значений на входе декодера.

Алгоритм LZW ориентирован на 8-битные изображения, построенные на компьютере, применяется в графических форматах TIFF, PDF, GIF, PCD, PNG [15]^[13]. Может быть достигнут коэффициент сжатия до 1000 раз.

Но метод сжатия может быть применен не только для компрессии данных, каждая единица которых имеет размер в один байт (например отсчеты яркости полутонового черно-белого изображения), но так же для сжатия данных произвольного размера.

2.1.4. МЕТОД КОДИРОВАНИЯ ХАФФМАНА

Дэвид Хаффман в 1952 году будучи аспирантом Массачусетского технологического института разработал алгоритм сжатия данных при написании курсовой работы.

Алгоритм заключается в создании так называемого бинарного дерева или кодовой таблицы. Для каждого символа определяется частота его появления в потоке, при этом часто встречающимся символам сопоставляют короткие кодовые слова, а для редких символов – длинные.

Построение таблицы начитается с того, что два символа с наименьшей частотой появления объединяются в узел кодового дерева, которому приписывается их суммарная частота [19]^[14]. Этот процесс продолжается до тех пор, пока ветви не сойдутся к одному единственному узлу. Далее ветви, в зависимости от их расположения, обозначаются нулями или единицами (например ветви, идущие влево от узла, обозначим нулями, вправо - единицами или наоборот). Чтобы определить значение кодового слова, кото- рое приписано к определенному символу, нужно пройти от вершины дерева к данному символу, записывая нули или единицы пройденных ветвей.

Алгоритма Хаффмана в чистом виде не применяется для сжатия изображений, а используется как один из этапов. Модификация CCITT Group 3 – алгоритм, предложенный третьей группой по стандартизации Международного консультационного Комитета по Телеграфии и Телефонии (Consultative Committee International Telegraph and Telephone), используется для сжатия черно-белых изображений [17].^[15]

В алгоритме последовательности подряд идущих черных и белых точек заменяются числом, равным их количеству. А этот ряд уже сжимается алгоритмом Хаффмана с фиксированной таблицей, полученной с помощью анализа частоты появления большого количества изображений.

В изображении каждая строка сжимается независимо. Считается, что на изображении преобладает белый цвет и каждая строка начинается с белой точки. Если строка начинается с черной точки, то считаем, что строка начинается с последовательности белых точек длинной нуль. Так например последовательность 0,5,362,6… значит, что в начале строки пять черных точек, далее 362 белые, далее 6 черных точек и так далее. Когда в изображении преобладает черный цвет, то перед сжатием изображение инвертируется и информация об этом записывается в заголовок файла.

В среднем, алгоритм CCITT Group 3 имеет коэффициент сжатия в 2 раза, но при применении к файлу с часто чередующимися черных и белых точек размер файла может увеличиться до пяти раз. Используется в формате TIF.

2.1.5. АРИФМЕТИЧЕСКОЕ КОДИРОВАНИЕ

Идея данного алгоритма состоит в том, чтобы присваивать коды не отдельным символам, а их последовательностям. Алгоритм состоит из не- скольких этапов: декорреляция, определение вероятностей каждого символа и чтение всего входного файла символ за символом с добавлением битов к сжатому файлу [11].^[16] При этом задаётся «текущий интервал» [0,1), который далее делится на зоны пропорционально вероятностям кодируемых символов. Информация о вероятности и зоны каждого символа составляются в таблицу, которую должен знать как кодер так и декодер.

Шаги кодирования:

Задаётся «текущий интервал» [0,1);

Действия, повторяющиеся для каждого символа входного файла:

«Текущий интервал» делится на части пропорционально вероятностям каждого символа;

Сместить «текущий интервал» в зону кодируемого символа;

На выходе алгоритма объявляется любая точка, однозначно определяющая «текущий интервал», то есть любая точка внутри интервала.