Сжатие растровых данных

Существуют различные способы сжатия растровых данных. В данном случае рассмотрим два из них – наиболее типичных: способ лексикографического кода и способ квадратомического дерева.

0 1 2 3 4 5 6 7 8



15
15
15
15
15
15

Рис.5

Способ лексикографического кода рассмотрим на примере рис.5. на нем приведено некоторое изображение, состоящее из пикселов белого цвета – 15, красного – 4, голубого – 1, зеленого – 2 цветов. Если выполнить сжатие информации построчно, то получим следующий лексикографический код: 9 – 15, 9 – 4, 3 – 15, 5 – 1, 1 – 15, 3 – 15, 4 – 1, 2 – 15, 2 – 15, 6 – 2, 1 –15, 2 – 15, 6 – 2, 1 – 15, 9 – 15. В этом коде пара чисел например 9 – 15 обозначает, что белый цвет 15 повторяется 9 раз. Всех пар в данном случае 18. Для их хранения потребуется 36 ячеек памяти. Для хранения несжатой информации понадобилось бы 9*9=81 ячейка памяти.

Широкое распространение имеет второй способ сжатия растровой информации, получивший название квадратомического дерева.

В этом случае вся территория или изображение разбиваются на вложенные ячейки.

1 2 3 4

5 6 7 8

9 10

рис.6

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

В иерархии разбиения узел относится к блоку соответствующего разбиения (декомпозиции): он называется родительским узлом. Конечный узел рассматривается как листок. В квадратомическом дереве эти листковые узлы заполнены или пустые в зависимости от хранимости в них объекта. Многовариантные данные могут храниться с назначением соответствующих атрибутов к листовым узлам. Такое дерево будет называться цветным.

уровень 1

уровень 2

9 10

уровень 3

5 4 7 8

рис.7

Тогда запись соответствующей информации можно организовать в виде следующей таблицы (таблица 1).

Таблица 1

№	Координаты левого верхнего угла квадрата	уровень иерархии	атрибут
	Х	У
	Х₉	У₉
	Х₁₀	У₁₀
	Х₅	У₅
	Х₄	У₄
	Х₇	У₇
	Х₈	У₈