http://www.math.dcn-asu.ru/Learning/Computational-Geometry/QuadTree/QuadTree.html

Квадродеревья и октодеревья.

Введение
Квадродеревья
Построение квадродерева
Визуализация квадротомированного изображения
Достоинства квадродерева
Недостатки квадродерева
Октодеревья
Как работать с октодеревьями
Достоинства октодерева
Недостатки октодерева
Для чего используются октодеревья
Исходные тексты программ
Литература


 

1. Введение

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

Одной из наиболее изученных и хорошо зарекомендовавших себя структур данных для представления двумерных изображений является квадротомическое дерево или квадродерево (quadtree). Благодаря естественной иерархической структуре и способу организации квадродеревья сочетают в себе значительную экономию объемов памяти с эффективностью доступа к элементам изображения. Идеология квадродеревьев применяется не только для представления растровых изображений, но и используется для эффективной организации больших баз любых пространственных данных, состоящих как из растровых, так и векторных изображений. Аналогичные принципы лежат в основе структуры данных для представления трехмерных изображений и других трехмерных данных - октотомического дерева или октодерева (octtree).


 

2. Квадродеревья

Квадротомическое дерево (квадродерево) - структура данных, используемая для представления двумерных пространственных данных. Существует несколько типов квадродеревьев в зависимости от базового типа данных. (точки, площади, кривые, поверхности или объемы). Наиболее общим типом квадродерева и примером использования является квадродерево растрового изображения (см. рисунок 1, рисунок 3 и рисунок 4 - примеры изображения и его бинарного представления, блоков разбиения и квадродерева). Далее, для конкретности, под пространственными данными везде будем понимать растровое изображение.

Следуя Samet (1990), под двумерным изображением понимается массив элементов изображения (пикселов, pixel). Если каждый из пикселов имеет только два состояния - черный или белый (подсвечен или нет), то изображение называется бинарным. Если пикселы могут принимать более двух значений, то их значения могут трактоваться как оттенки серого, а изображение в этом случае называется изображением в градациях серого (grey-scale). Цветные изображения организованы аналогичным образом. Квадродеревья наиболее широко используются для работы с двухцветными изображениями, поэтому в дальнейшем будем иметь дело преимущественно с бинарными изображениями. Будем также в дальнейшем подразумевать, что фоновым в бинарном изображении является белый цвет.

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

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


(a) изображение (b) его бинарный образ (c) его квадротомическое разбиение

Рис. 1: (a) изображение (b) его бинарный образ (c) его квадротомическое разбиение

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

Как показано Samet and Tamminen (1985), квадродеревья и их варианты оказываются полезными в различных приложениях таких, как обработка изображений, машинная графика, распознавание образов, роботостроении и картографии.


Квадродерево

Рис. 2:Пример квадродерева


 

3. Построение квадродерева


(a)first division (b)second division (c)third division (d)entire image divided

Рис. 3: (a) первый этап разбиения (b) второй этап разбиния
(c) третий этап разбиения (d) изображение полностью разбито

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

На нулевом этапе полному изображению (рисунок 1a) сопоставляется корневой узел дерева (рисунок 4). Далее четырем равновеликим квадрантам первого этапа разбиения (рисунок 3a) ставятся в соответствие дочерние узлы первого уровня. В показанном на рисунках частном случае северо-западный NW-квадрант обозначен белым квадратом, а остальные три - серыми кругами (рисунок 4). На очередно этапе серые квадранты снова подвергаются разбиению (на рисунке 3b для простоты показано лишь разбиение SW-квадранта). Как видно по рисунку 3b SW-квадрант на этом этапе содержит два белых, один черный и один серый подквадранты. Они представлены в дереве на рисунке 4. узлами второго уровня. Единственный серый квадрант снова разбивается. В данном случае это разбиение является последним, т.к. ни один из получившихся в результате подквадрантов не оказался серым (один белый и три черных). Подобным же образом обрабатываются и остальные квадранты изображения всех уровней. Окончательный вид квадродерева показан на рисунке 4.


Final quadtree showing levels

Рис. 4: Окончательный вид квадродерева


 

4. Визуализация квадротомированного изображения

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

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

Этот процесс продолжается до тех пор, пока не будут посещены все листья дерева.

Визуализация полного изображения происходит по мере продвижения по квадродереву.


 

5. Достоинства квадродерева

Большинство приложений квадротомических деревьев к данным было сделано для изображений (Klinger, Dyer, 1976), но были проведены также современные алгоритмические разработки, которые дали результаты, сходные с теми, что используются при обработке географических данных. Сюда входят расчеты площадей, центороидные определения, распознавание образов (Shneier, 1981), классификация изображений, оверлейные операции над изображениями, выявление связанных компонент, определение соседства (Samet, 1981; Burroughs, 1986), преобразование расстояний (Samet, 1982), разделение изображений, сглаживание данных (Ranade, Shneier, 1981) и усиление краевых эффектов (Ranade, 1981). Вследствие этих преимуществ отдельные исследователи (Samet, 1984; Peuquet, 1984; Mark, Lauzon, 1985) предложили использовать квадротомические деревья для хранения географических данных. Основное достоинство квадродеревьев состоит в компактном представлении изображения. Компактность квадродерева целиком зависит от изображения. Изображение с большими областями, окрашенными в один цвет представляются очень компактно, в то время как изображение, в котором все пикселы имеют разные цвета сводит на нет все преимущества квадродерева. (Hunter and Stiglitz,1979)

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

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

Поворот квадродерева на 90 градусов против часовой стрелки может быть осуществлен простым переприсваиванием узлов дерева в следующем порядке:

Поворот по часовой стрелке выполняется аналогично за исключением того, что переприсваивание производится в обратном порядке.

Burroughs (1986) и Samet (1990) также упоминают о том, что квадродерево полезно при изменении разрешения объекта. Рассмотрим, например, квародерево на рисунке 4, которое представляет изображение, приведенное на рисунке 1.a. Если мы хотим изменить разрешение этого изображения, нам необходимо просто заменить все серые узлы второго уровня на черные узлы. Результатом будет новое изображение, показанное на рисунке 5.


Varied Resolution of Quadtree

Рис. 5: Изображение с измененным при помощи квадродерева разрешением

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


 

6. Недостатки квадродерева

Главный недостаток квадродеревьев состоит в том, что почти невозможно сравнить два изображения, которые отличаются, например, лишь поворотом. Это обусловлено тем, что квадродеревья, представляющие такие изображения являются абсолютно различными.

Алгоритмы поворота квадротомированного изображения ограничиваются лишь поворотами на углы, кратные 90 градусам. Повороты на любые другие углы невозможны.

Хотя квадродеревья имеют массу плюсов в ГИС-приложениях, их распространение в других областях сдерживается их недостатками. Большинство проблем связано именно с тем, что при повороте изображения для него приходится заново перестраивать квадродерево. При этом сопоставление квадродеревьев исходного и повернутого изображений становится весьма сложной задачей. Вследствие этого применение квадродеревьев, например, в геометрическом анализе форм и распознавании образов остается достаточно узким.


First image and rotated image, different quadtrees

Рис. 6: Исходное и повернутое изображения, различные квадродеревья


 

7. Октодеревья

Для представления трехмерных изображений и трехмерных графических сцен структурой данных, основанной на сходных принципах, является октотомическое дерево или октодерево (octtree). Подобно квадродереву октотомическое дерево является иерархической структурой, но представляет изображение на уровне объектов или вокселов (voxel - volume element), а не пикселов.

Октотомические деревья являются естественным распространением концепции квадродерева для представления трехмерного пространства. Подобно тому как при построении квадродерева область разбивается на четыре части при построении октодерева трехмерный объект подразделяется на восемь кубов (октантов). Если какой-либо из октантов является однородным, т.е. он располагается либо целиком внутри объекта, либо целиком снаружи, разбиение заканчивается. Иначе, если октант не является однородным, т.е. октант пересекается граничной поверхностью объекта, он разбивается далее на восемь подоктантов. Процесс разбиения завершается, когда все листовые узлы октодерева станут однородными, возможно с некоторой погрешностью (Carlbom and others 1985).

Samet (1990) в качестве простейшего варианта октотомической структуры данных называет октодерево регионов. Октодерево имеет те же недостатки, что и квадродерево, в том смысле, что оно является лишь приближением изображения. Октодерево требует значительных вычислительных затрат на построение, поскольку требуется просмотреть большое количество элементов данных.

Октодеревья обладают той же структурой, что и квадродеревья за исключением того, что каждый родительскийй узел дерева имеет не четыре дочерних узла, а восемь. Сходство структуры квадро- и октодерева можно увидеть на рисунке.


3-D image, its octree block composition and tree representation(Samet 1990)

Рис. 7:Трехмерное изображение, октотомическое разбиение и октодерево (Samet 1990)


8. Как работать с октодеревьями

Принципы работы с октодеревьями почти ничем не отличаются от способов работы с квадродеревьями. Разница заключается в том, что исходными данными при построении октодеревьев являются трехмерные объекты, а не двумерные изображения. Объекты соотносятся с листовыми узлами октодерева, которые формируются в том случае, когда объект либо целиком лежит внутри, либо целиком вне октанта, соответствующего листовому узлу. Корневой узел октодерева соответствует полной трехмерной сцене. Все узлы кроме листовых имеют по восемь дочерних узлов (октантов).


 

9. Достоинства октодерева

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

С помощью октотомического дерева очень просто производятся рассчеты таких величин как площадь поверхности, объем, центр масс.

Октодеревья обладают всеми преимуществами и эффективностью, свойственными любой древесной структуре.


 

10. Недостатки октодерева

К недостаткам октотомического представления трехмерных объектов или сцен можно отнести то обстоятельство, что они лишь аппроксимируются октодеревом и не являются полным представлением (Carlbom and others 1985). Например, октотомическое разбиение сферы независимо от того сколько уровней разбиений оно содержит, никогда не будет точным представлением исходной сферы. Оно будет являться хорошим приближением, но свойства сферы, например, кривизна и гладкость, будут утрачены в процессе построения реалистического изображения.

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


 

11. Для чего используются октодеревья

Одно из популярных применений октодеревьев - ускорение алгоритмов трассировки лучей. Вместо отслеживания пересечения лучей, исходящих из каждого пиксела с каждым объектом сцены при проверках используется квадротомированное представление сцены. Вначале проверяется пересечение луча с октантами, соответствующими дочерним узлам корня октодерева (пересечение с корневым октантом всегда существует). В случае пересечения луча и октанта проверки осуществляются уже для его дочерних октантов. Этот процесс продолжается до тех пор пока не будет найдено пересечение луча и листового узла. Листовой узел либо содержит объект сцены, пересечение луча с которым требуется обработать, либо не содержит таковых. Возникновение последнего случая означает, что луч покидает сцену или достигает ее фона.

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

Другое применение октодеревья находят при квантовании цветов. Квантование цветов - это метод, применяемый для определения достаточно близкого цветового значения при представлении изображения меньшим количеством цветов, чем содержит его оригинал. Такие ситуации возможны, например, при отображении 24-битного изображения (16 миллионов цветов) в 8-битном видеорежиме (256 цветов).

     "Первые 256 различных цветов образуют листовые узлы дерева.

Если дерево уже содержит 256 цветов, то при добавлении очередного
значения, производится предварительное понижение размерности.
При понижении размерности могут быть использованы две стратегии.
В дереве отсекаются узлы либо самого глубокого уровня, либо
узлы, соответствующие самым немногочисленным цветам. ... После
понижения размерности могут быть добавлены один или более цветов
как листовые узлы, либо как усреднение цветов отсеченных узлов.
Таким образом суммарное количество листовых и усекаемых узлов
всегда не превосходит 256, что удобно и с точки зрения затрат
памяти. Сопоставление точек изображения получившейся таблице
цветов осуществляется простым поиском в построенном октодереве."
                                (Burger and Gillies 1989).


 

12. Исходные тексты программ

Здесь содержится какой-то код octree.c для манипуляций с октодеревьями. Есть также и заголовочный файл octree.h.

Имеются еще программы, которые написал Bob Glickstein (bobg@andrew.cmu.edu). Это public domain-программы и могут свободно распространяться, копироваться, изменяться и распространяться. Автор не дает никаких гарантий и несет никакой ответственности за эти программы. Эти файлы могут быть найдены при помощи xarchie.

Они содержатся в файлах:


 

13. Литература


Кошкарев А.В., Тикунов В.С.
Геоинформатика. Москва, Картгеоцентр-Геоиздат, 1993. С. 55-57.
Tobler, W., Zi-tan Chen. (1986)
A quadtree for global Information Storage. - "Geographical Analysis", 1986, October, Vol. 18, No. 4.
Существует перевод:
Тоблер В., Зи-тан Чен.
Квадротомическое дерево для глобального хранения информации. // Картография. Вып. 4. Геоинформационные системы: Сб. перев. статей/Сост., ред и предисл. А.М. Берлянт и В.С. Тикунов. - М.: Картгеоцентр - Геоиздат, 1994. C. 89-101.

Mark D.M. (1986)
Construction of Quadtrees and Octtrees from Reaster Data. A new algorithm Based on Run-Encoding. - "The Australian Computer Journal", 1986, August, Vol. 18, No. 3, p 115-119.
Существует перевод:
Марк Д.М.
Построение квадротомических и октотомических деревьев на базе растровых данных: новый алгоритм быстрого кодирования. // Картография. Вып. 4. Геоинформационные системы: Сб. перев. статей/Сост., ред и предисл. А.М. Берлянт и В.С. Тикунов. - М.: Картгеоцентр - Геоиздат, 1994. C. 102-109.

Bell, S.B., B.M. Diaz, and F.C. Holroyd.(1988)
Digital Image Processing in Remote Sensing. Capturing Image Syntax using Tesseral addressing and arithmetic. Taylor & Francis Ltd: USA.  
Hunter G.M. and Stiglitz K.(1979)
IEEE Transactions on Pattern Analysis and Machine Intelligence. Operations on Images Using Quad Trees. April: 145-153.  
Samet,H. (1990)
The Design and Analysis of Spatial Data Structures. Addison-Wesley Publishing Company, Inc : Reading.  
Samet H.(1981)
Computer Graphics and Image processing. Neighbor Finding Techniques for Imagees Represented Quadtrees. Academic Press 18: 35-57.  
Samet H. and M. Tamminen.(1985)
IEEE Transaction on Patter Analysis and Machine Intelligence. Computing Geometric Properties of Images Represented by Linear Quadtrees. March: 229-240.  
Burroughs,P.A. (1986)
Principles of Geographical Information Systems for Land Resources Assessment.
Clarendon Press : Oxford.  
Foley J.D. and A. Van Dam(1982)
Fundamentals of Interactive Computer Graphics. Addison Wesley.  
Carlbom I., I. Chakravarty and D. Vanderschel (1985)
A Hierarchical Data Structure for Representing the Spatial Decomposition of 3D Objects. In: Frontiers in Computer Graphics (T.L. Kunii ed.), pp. 2-12. Springer-Verlag: New York.  
Burger, P. and D. Gillies (1989)
Interactive Computer Graphics: Functional, Procedural and Device-level Methods. Addison-Wesley Publishing Company: Sydney.