6.4.3. СЖАТИЕ ИЗОБРАЖЕНИЙ С ПОМОЩЬЮ ТЕТРАРНЫХ ДЕРЕВЬЕВ

Представление изображений, описанное в двух предыдущих разделах, можно усовершенствовать несколькими способами. В первую очередь необходимо избавиться от увеличения размера памяти (или опасности появления ошибок округления), требующейся для хранения определяемых по формулам (6.1) значений Необходим метод, обеспечивающий взаимно-однозначное отображение одной четверки чисел в другую.

Утверждение 6.1. Пусть имеется чисел каждое из которых состоит из бит. Предполагается, что равно степени числа 2. В таком случае для запоминания среднего значения этих чисел и отклонений от него, обозначаемых соответственно достаточно бит.

Доказательство. Пусть — сумма чисел, — частное от её деления на — остаток. Для запоминания каждого из чисел, включающих и требуется максимум бит. Для запоминания остатка требуется максимум бит.

Из утверждения 6.1 следует, что при использовании тетрарного дерева каждый уровень требует добавления двух битов, и их накопление, естественно, может превзойти допустимые пределы. С другой стороны, существует определенный баланс между числом битов, затрачиваемых на Если значения чисел очень близки, то для представления требуется очень немного битов, однако для хранения может потребоваться до бит. Если различия между значениями чисел велики, то значение будет малым и для его хранения потребуется меньшее число битов. Это обстоятельство можно использовать для получения представлений, не требующих дополнительных затрат памяти; они рассматриваются в следующем разделе. Здесь мы обсудим, каким образом утверждение 6.1 можно использовать для увеличения эффективности сжатия. Вместо передачи отклонений от среднего значения можно передавать лишь отклонения от (для представления

каждого из которых требуется максимум бит) и последнее Кроме того, можно передавать остатки для представления каждого из которых требуется всего лишь бит (2 бита при использовании тетрарных деревьев). Нетрудно установить, что число остатков равно Таким образом, рост объема памяти будет составлять не 33%, а 33%, умноженные на Для восстановления изображения можно воспользоваться приведенными уравнениями, подвергнутыми очень небольшим изменениям.

Если на изображении имеются большие области с одинаковой яркостью, то можно добиться значительной экономии памяти. Действительно, допустим, что для некоторого участка три разности равны 0. Тогда вместо того, чтобы вводить три нуля в массив используемый в алгоритме 6.4а, можно поместить в него некоторый специальный символ. (В качестве последнего можно взять максимально допустимое значение яркости, поскольку оно не может встретиться как некоторое отклонение от среднего значения.) После окончания просмотра всего изображения все повторные вхождения этого символа можно исключить из всех последующих уровней дерева. Так, для кодирования изображения, характеризуемого одним значением яркости, достаточно этого значения и специального символа (см. задачу 6.6).