Разработка класса «Квадродерево» для реализации операций с квадродеревьями на Object Pascal.
Выполнил:студент группы 3В-201БВобликов Т.И.
Проверил:доцент кафедры 304 Новиков П.В.
Москва 2015
Оглавление
Введение. 3
Общие понятия. 4
Пример квадродерева. 6
Визуализация квадротомированного изображения [1]. 7
Достоинства квадродерева. 8
Недостатки квадродерева. 9
Результаты. 10
Литература. 15
Ссылки на интернет ресурсы.. 16
Введение.
Для того, чтобы объявить класс на Turbo Pascal'е необходимо воспользоваться ключевым словом Object . Так как класс всегда является типом, делать это можно лишь в Type части программы:
Легко заметить, что поля и методы (общее для них название - члены класса) объявляются очень похоже на поля записи и обычные процедуры/функции. Объекты класса объявляются так же, как и обычные переменные:
Var
Object1, Object2: Class1;
Соотвенно, доступ к полям объекта некоторого класса производится аналогично доступу к полям записи:
Object1.V:= Object2.A;
Обращение к методам класса производится аналогичным образом:
Object1.Nothing(Object1.A);
Одной из наиболее изученных и хорошо зарекомендовавших себя структур данных для представления двумерных изображений является квадротомическое дерево или квадродерево (quadtree). Благодаря естественной иерархической структуре и способу организации квадродеревья сочетают в себе значительную экономию объемов памяти с эффективностью доступа к элементам изображения. Идеология квадродеревьев применяется не только для представления растровых изображений, но и используется для эффективной организации больших баз любых пространственных данных, состоящих как из растровых, так и векторных изображений.
Общие понятия.
Квадродерево (квадротомическое дерево) - структура данных, используемая для представления двумерных пространственных данных Существует несколько типов квадродеревьев в зависимости от базового типа данных. (точки, площади, кривые, поверхности или объемы). Наиболее общим типом квадродерева является (См. рисунок 0.)
Рис. 1: Пример квадродерева
Квадродерево растрового изображения (см. рисунок1, рисунок 3 и рисунок4 - Примеры изображения и его бинарного представления, блоков разбиения и квадродерева) [6]. Далее, для конкретности, под пространственными данными везде будем понимать растровое изображение. Следуя [7], под двумерным изображением понимается массив элементов изображения (пикселов). Если каждый из пикселов имеет только два состояния - черный или белый (подсвечен или нет), то изображение называется монохромным. Квадродеревья наиболее широко используются для работы с двухцветными изображениями, будем также в дальнейшем подразумевать, что фоновым в монохромном изображении является белый цвет. При построении квадродерева двумерное изображение рекурсивно подразделяется на квадранты. Каждый из четырех квадрантов становится узлом квадротомического дерева. Больший квадрант становится узлом более высокого иерархического уровня квадродерева, а меньшие квадранты появляются на более низких уровнях. Преимущества такой структуры в том, что регулярное разделение обеспечивает простое и эффективное накопление, восстановление и обработку данных. Простота проистекает из геометрической регулярности разбиения, а эффективность - за счет хранения только узлов с данными, которые представляют интерес. Основополагающая идея квадродерева - комбинирование одинаковых или сходных элементов данных и кодирование больших однородных совокупностей данных малым количеством битов [2]. Корневой узел соответствует изображению в целом и имеет четыре дочерних узла, которые ассоциируются с четырьмя квадрантами исходного изображения (обозначаемыми NW - северо-западный, NE - северо-восточный, SW - юго-западный, SE - юго-восточный). В свою очередь каждый из дочерних узлов корня дерева также имеет по четыре дочерних узла, исходного изображения. Дочерние узлы следующего уровня представляют собой шестьдесят четыре квадранта, составляющих исходное изображение и так далее до конца.
Рис. 1: (a) изображение (b) его бинарный образ (c) его квадротомическое разбиение
В сформированном выше описанном способом квадродереве листовым узлам дерева (узлам, соответствующим каждому одиночному пикселу изображения) приписывают цвет связанного с ними пиксела (черный или белый). Если нелистовой узел имеет среди дочерних узлов, узлы как одного так и другого цвета, ему приписывается серый цвет. Если же все дочерние узлы нелистового узла дерева "окрашены" в один и тот же цвет, то такому узлу приписывается этот цвет, а его дочерние узлы исключаются из дерева. Таким образом, в квадродереве могут отсутствовать некоторые ветки, представляющие собой достаточно большие одноцветные области. Квадродеревья и их варианты оказываются полезными в различных приложениях таких, как обработка изображений, машинная графика, распознавание образов, роботостроении и картографии [8].
Рис. 2:Пример квадродерева
Пример квадродерева.
Рис. 3: (a) первый этап разбиения (b) второй этап разбиния (c) третий этап разбиения (d) изображение полностью разбито
На каждом этапе построения квадродерева изображение разбивается на четыре квадранта и каждому присваивается одно из следующих значений
1) белый --> квадрант полностью белый. Обозначается белым квадратом.
2) черный --> квадрант полностью черный. Обозначается черным квадратом.
3) серый --> квадрант - смесь черного и белого. Обозначается белым кругом.
На нулевом этапе полному изображению (рисунок 1a) сопоставляется корневой узел дерева. Далее четырем равновеликим квадрантам первого этапа разбиения (рисунок 3a) ставятся в соответствие дочерние узлы первого уровня. В показанном на рисунках частном случае северо-западный NW-квадрант обозначен белым квадратом, а остальные три - серыми кругами (рисунок 4). На очередном этапе серые квадранты снова подвергаются разбиению (на рисунке 3b для простоты показано лишь разбиение SW-квадранта). Как видно по рисунку 3b SW-квадрант на этом этапе содержит два белых, один черный и один серый подквадранты. Они представлены в дереве на рисунке 4. узлами второго уровня. Единственный серый квадрант снова разбивается. В данном случае это разбиение является последним, т.к. ни один из получившихся в результате подквадрантов не оказался серым (один белый и три черных). Подобным же образом обрабатываются и остальные квадранты изображения всех уровней. Окончательный вид квадродерева показан на рисунке 4.
Рис. 4: Окончательный вид квадродерева
Визуализация квадротомированного изображения [1].
Визуализация изображения, представленного квадродеревом, представляет собой простую рекурсивную процедуру. Начиная с корня дерева просматривается каждый узел. Если узел не является листовым, то он пропускается и просматривается его первый дочерний узел. Если этот дочерний узел не листовой, то он пропускается и происходит переход к его первый дочерний узел и т.д. При достижении листового узла его цветовое значение отображается в соответствующей позиции. После этого происходит рекурсивный возврат к пропущенному родительскому узлу и аналогичным образом просматривается его второй дочерний узел. Этот процесс продолжается до тех пор, пока не будут посещены все листья дерева. Визуализация полного изображения происходит по мере продвижения по квадродереву.
изображение и так далее до конца.
В сформированном выше описанном способом квадродереве листовым узлам дерева (узлам, соответствующим каждому одиночному пикселу изображения) приписывают цвет связанного с ними пиксела (черный или белый). Если нелистовой узел имеет среди дочерних узлов, узлы как одного так и другого цвета, ему приписывается серый цвет. Если же все дочерние узлы нелистового узла дерева "окрашены" в один и тот же цвет, то такому узлу приписывается этот цвет, а его дочерние узлы исключаются из дерева. Таким образом, в квадродереве могут отсутствовать некоторые ветки, представляющие собой достаточно большие одноцветные области. Квадродеревья и их варианты оказываются полезными в различных приложениях таких, как обработка изображений, машинная графика, распознавание образов, роботостроении и картографии [8].
