Анализ и разработка алгоритма

Для реализации алгоритма необходимо разобраться в работе бинарных деревьев.

Бинарные деревья представляют собой структуру данных, которая широко используется в машинной графике и в обработке изображений. Ее применение дает наилучшие результаты если изображение представляет собой прямоугольник размерность которого 2ⁿ x 2^m точек. Данный прямоугольник можно разбить на два меньших по размеру прямоугольника: 2^n-1 2^m или 2ⁿ 2^m-1. Процесс такого разбиения можно повторять p раз пока размер прямоугольника не станет равен 1×1. Полученные уровни можно пронумеровать, начиная с 0, которым обозначается изображение в целом, вплоть до p, соответствующего одному пикселю. Каждый выделяемый прямоугольник можно пометить либо 0 либо 1, в зависимости от положения прямоугольника. В результате отдельные пиксели будут снабжены метками, состоящими из p символов. Эту структуру можно представить в виде дерева, вершины которого будут соответствовать отдельным прямоугольникам.

Рис. 1 Часть бинарного дерева

Вершины дерева соединяются, если прямоугольник, соответствующий одной из них, непосредственно содержится в прямоугольнике, соответствующем родительской вершине. Корень дерева (root) соответствует изображению в целом, листья — отдельным пикселям, а все остальные вершины характеризуются степенью исхода, равной 2. Дерево такого вида обычно называют деревом второй степени или бинарным деревом.

Допустим, есть изображение размером 2ⁿ x 2^m точек, где каждая точка характеризуется интенсивностью цвета (изображение в оттенках серого). Для построения соответствующего уровня дерева необходимо просмотреть пары соседних пикселей и проанализировать их (свертка по горизонтали). Пусть f₁ и f₂ — соответствующие уровни серого тона для каждого пикселя. Теперь можно определить два новых уровня:

— средний цвет соседних пикселей.

— коэффициент для восстановления.

При переходе от уровней серого тона f₁ и f₂ к уровню g не происходит никакой потери информации, поскольку значения f₁ и f₂ восстанавливаются по значению g, при помощи следующих формул:

Единственное затруднение связанно с тем, что для представления уровней g, может потребоваться больше битов, чем для уровней f.

Таким образом, получены две матрицы, размерность которых 2^n-1 2^m. Первая содержит информацию о среднем цвете соседних пикселей, а вторая информацию для восстановления исходного изображения. Далее можно точно таким же образом обработать матрицу № 1, но парными считать пиксели не по горизонтали, а по вертикали. Чередуя обработку получающихся прямоугольников по горизонтали и по вертикали можно получить в конце матицу размером 1×1 содержащую информацию о среднем цвете всего изображения, и несколько матриц содержащих информацию об уточнении цвета от уровня к уровню.

Восстановление исходного изображения происходит в обратном порядке. Сначала поступает информация о среднем цвете всего изображения и выводится на экран, при этом происходит масштабирование до исходного размера изображения. Далее поступает информация о коэффициентах сжатия и происходит уточнение (детализация изображения), размер изображения становится 2×1. Последовательно поступает информация о коэффициентах сжатия для каждого следующего уровня. Таким образом, восстанавливается исходное изображение.