Разработка класса 'Квадродерево' для реализации операций с квадродеревьями на Object Pascal

Разработка класса 'Квадродерево' для реализации операций с квадродеревьями на Object Pascal

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

Московский авиационный институт (национальный исследовательский университет) "МАИ"

Кафедра: 304 " Вычислительные машины, системы и сети"

Пояснительная записка к курсовой работе

Разработка класса "Квадродерево" для реализации операций с квадродеревьями на Object Pascal

Москва 2015

Оглавление

Введение

. Общие понятия

. Пример квадродерева

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

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

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

. Результаты

Вывод

Список источников и литературы

Введение

Для того чтобы объявить класс на Turbo Pascal'е необходимо воспользоваться ключевым словом Object. Так как класс всегда является типом, делать это можно лишь в Type части программы:

Type= Object

{список полей} A: Byte; V: Real; {список методов} Procedure Nothing(Var K: Byte); End;

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

, Object2: Class1;

Соответственно, доступ к полям объекта некоторого класса производится аналогично доступу к полям записи:

.V:= Object2.A;

Обращение к методам класса производится аналогичным образом:

.Nothing(Object1.A);

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

1. Общие понятия

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

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

Квадродерево растрового изображения (см. рисунок 2, рисунок 4 и рисунок 5 - Примеры изображения и его бинарного представления, блоков разбиения и квадродерева) [6]. Далее, для конкретности, под пространственными данными везде будем понимать растровое изображение.

Следуя [7], под двумерным изображением понимается массив элементов изображения (пикселов). Если каждый из пикселов имеет только два состояния - черный или белый (подсвечен или нет), то изображение называется монохромным.

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

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

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

квадротомический дерево программа матрица

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

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

Квадродеревья и их варианты оказываются полезными в различных приложениях таких, как обработка изображений, машинная графика, распознавание образов, роботостроении и картографии [8].

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

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

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

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

·              1) белый --> квадрант полностью белый. Обозначается белым квадратом.

·              2) черный --> квадрант полностью черный. Обозначается черным квадратом.

·              3) серый --> квадрант - смесь черного и белого. Обозначается белым кругом.

На нулевом этапе полному изображению (рисунок 2a) сопоставляется корневой узел дерева.

Далее четырем равновеликим квадрантам первого этапа разбиения (рисунок 4a) ставятся в соответствие дочерние узлы первого уровня.

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

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

Подобным же образом обрабатываются и остальные квадранты изображения всех уровней.

Окончательный вид квадродерева показан на рисунке 5.

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

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

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

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

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

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

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

Большинство приложений квадро деревьев к данным было сделано для изображений (Klinger, Dyer, 1976), но были проведены также современные алгоритмические разработки, которые дали результаты, сходные с теми, что используются при обработке географических данных. Сюда входят расчеты площадей, центороидные определения, распознавание образов [4], классификация изображений, оверлейные операции над изображениями, выявление связанных компонент, определение соседства [1], преобразование расстояний [7], разделение изображений, сглаживание данных и усиление краевых эффектов [4]. Вследствие этих преимуществ отдельные исследователи предложили использовать квадротомические деревья для хранения географических данных. Основное достоинство квадродеревьев состоит в компактном представлении изображения. Компактность квадродерева целиком зависит от изображения. Изображение с большими областями, окрашенными в один цвет представляются очень компактно, в то время как изображение, в котором все пикселы имеют разные цвета сводит на нет все преимущества квадродерева [10].

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

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

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

·              Северо-западный (NW) -> Юго-западный (SW)

·              Северо-восточный (NE) -> Северо-западный (NW)

·              Юго-западный (SW) -> Юго-восточный (SE)

·              Юго-восточный (SE) -> Северо-восточный (NE)

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

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

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

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

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

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

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

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

6. Результаты

program Project1;Crt;= 8;= 8;= array[1..XMAX, 1..YMAX] of Byte;= record, Top, Bottom, Right: Integer;;= function(R: TRect): Byte;= ^TQTree;= object: Byte;: TRect;, NE, SW, SE: PQTree;Create(R: TRect; L: Integer; Hint: string; F: TQScan);View(Pad: Integer; S: string);Destroy;;: TMatrix;: TRect;: PQTree;FillMatrix;, y: Integer;;x := 1 to XMAX doy := 1 to YMAX doRandom(6) > 0 then[x, y] := 1[x, y] := 0;;WriteMatrix;, y: Integer;x := 1 to XMAX doy := 1 to YMAX do(M[x, y], ' ');;;;

{$F+}ScanMatrix(R: TRect): Byte;, y: Integer;, BlackFinded: Boolean;:= 0;:= False;:= False;x := R.Left to R.Right doy := R.Top to R.Bottom doM[x, y] = 0 then:= True;M[x, y] = 1 then:= True;WhiteFinded and BlackFinded then;;WhiteFinded and BlackFinded then:= 2if BlackFinded then:= 1if WhiteFinded then:= 0;;

{$F-}TQTree.Create(R: TRect; L: Integer; Hint: string; F: TQScan);, dy: Integer;: TRect;(R.Right >= R.Left) and (R.Bottom >= R.Top) then.Max := F(R);('[', R.Left, ',', R.Right, '], [', R.Top, ',', R.Bottom, ']. Level=', L, ', ', Hint, ' > ', Self.Max);Self.Max < 2 then.NW := nil;.NE := nil;.SW := nil;.SE := nil;:= (R.Right - R.Left) div 2;:= (R.Bottom - R.Top) div 2;

{NW}.Left := R.Left;.Right := R.Left + dx;.Top := R.Top;.Bottom := R.Top + dy;.NW := New(PQTree, Create(TmpR, L + 1, 'NW', F));

{NE}.Left := R.Left + dx + 1;.Right := R.Right;.Top := R.Top;.Bottom := R.Top + dy;.NE := New(PQTree, Create(TmpR, L + 1, 'NE', F));

{SW}.Left := R.Left;.Right := R.Left + dx;.Top := R.Top + dy + 1;.Bottom := R.Bottom;.SW := New(PQTree, Create(TmpR, L + 1, 'SW', F));

{SE}.Left := R.Left + dx + 1;.Right := R.Right;.Top := R.Top + dy + 1;.Bottom := R.Bottom;.SE := New(PQTree, Create(TmpR, L + 1, 'SE', F));;;;TQTree.View(Pad: Integer; S: string);: Integer;@Self <> nil then.NW^.View(Pad + 5, 'NW');.NW^.View(Pad + 5, 'NE');i := 1 to Pad do('-');(S, ':', Self.Max);.NW^.View(Pad + 5, 'SW');.NW^.View(Pad + 5, 'SE');;;TQTree.Destroy;@Self <> nil thenSelf.NW <> nil then(Self.NW, Destroy);Self.NE <> nil then(Self.NE, Destroy);Self.SW <> nil then(Self.SW, Destroy);Self.SE <> nil then(Self.SE, Destroy);;;;;('Source matrix: ');;;('Processing: ');.Left := 1;.Top := 1;.Right := XMAX;.Bottom := YMAX;:= New(PQTree, Create(Rect, 1, 'ROOT', ScanMatrix));;('Tree: ');^.View(1, 'ROOT');;(Root, Destroy);.

Вывод

Использование квадродерева продемонстрировано на классической задаче разбора бинарной матрицы N на M.

Для примера в программе используется матрица 8 на 8, которая заполняется случайным образом.

Сначала выводится матрица, потом выводятся данные по ходу формирования дерева, затем выводится само дерево.

Квадрант помечается цифрой 2, если он содержит и нули и единицы; при этом продолжается дальнейшее разбиение этого квадранта.

Квадрант помечается цифрой 1 или цифрой 0, если он содержит только единицы или только нули соответственно.

Пометки обозначают:- корень,- северо-запад, NE - северо-восток,- юго-запад, SE - юго-восток.- класс, TRect и TQScan - это обычные типы, которые описывают другие вспомогательные структуры

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

Список источников и литературы

Литература

.        Кошкарев А.В., Тикунов В.С. Геоинформатика. Москва, Картгеоцентр-Геоиздат, 1993. С. 55-57.

2.      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.

3.      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.

4.      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.

6.      Samet,H. (1990) The Design and Analysis of Spatial Data Structures. Addison-Wesley Publishing Company, Inc: Reading.

7.      Samet H.(1981) Computer Graphics and Image processing. Neighbor Finding Techniques for Imagees Represented Quadtrees. Academic Press 18: 35-57.

8.      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.

10.    Foley J.D. and A. Van Dam(1982) Fundamentals of Interactive Computer Graphics. Addison Wesley.

11.    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.

12.    Burger, P. and D. Gillies (1989) Interactive Computer Graphics: Functional, Procedural and Device-level Methods. Addison-Wesley Publishing Company: Sydney.

Ссылки на интернет ресурсы

13.    http://loi.sscc.ru/gis/QuadTree/QuadTree.html

.        http://www.kolasc.net.ru/cdo/metod/programmer'scourse/language/oop_pas.htm

.        https://ru.wikipedia.org/wiki/Заглавная_страница