Кодирование участков из нулей

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

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

где n– количество нулей, M и N – размеры изображения, m – предполагаемое количество удаляемых нулей.

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

На третьем этапе выполняется пирамидальное кодирование нулевых зон. Карта нулей представляет собой первый уровень пирамиды и содержит признаки нулевых и ненулевых отсчётов. Второй уровень имеет размеры M/2 а N/2 и каждый элемент его соответствует квадрату 2 на 2 элементов первого уровня, как это показано на рисунке 7.

Рис. 7. Пирамидальное кодирование зон из нулей

В элементах первого и последующих уровней содержатся выигрыши в битах, которые будут получены при кодировании соответствующего участка. Значения выигрышей второго уровня складываются из стоимостей вырезаемых из сигнала нулей за вычетом 4 бит накладных расходов. Выигрыши последующих уровней складываются из выигрышей предыдущих и, также, за вычетом 4 бит накладных расходов. На верши-не пирамиды получится суммарный выигрыш или проигрыш от всего кодирования. Если кодирование зон из нулей выгодно, то пирамида просматривается в обратном порядке и строится граф, описывающий выгодную часть пирамиды. До некоторых нулей первого уровня ветви графа не дойдут. Это означает, что на их описание требуются слишком большие затраты. Алгоритм вырежет не только повторяющиеся, но и отдельно стоящие нули, если это будет выгодно.

На четвёртом этапе происходит удаление части нулей из сигнала. При этом двумерная структура изображения разрушается и в дальнейшем выполняется обработка уже одномерного сигнала.