Төртбұрышты ағаш құрылымы және екі өлшемді кеңістікті бөлу

Кіріспе

Екі өлшемді аумақты бөлу үшін әрбір ішкі түйінінің дәл төрт баласы бар ағаш деректер құрылымы.

Квадри ағашы – әрбір ішкі түйінінің дәл төрт баласы бар ағаш деректер құрылымы. Квадри ағаштар – октағаштардың екі өлшемді аналогы және көбінесе екі өлшемді кеңістікті төрт квадрантқа немесе аймаққа рекурсивті бөлу арқылы бөлу үшін қолданылады. Жапырақ жасушасымен байланысты деректер қолданысқа қарай әртүрлі болуы мүмкін, бірақ жапырақ жасушасы «қызықты кеңістіктік ақпараттың бірлігін» көрсетеді. Бөлінген аймақтар шаршы немесе тіктөртбұрышты болуы мүмкін, немесе кез келген пішінге ие болуы мүмкін. Бұл деректер құрылымын 1974 жылы Рафаэль Финкель және Дж. Л. Бентли квадри деп атады. Осыған ұқсас бөлініс Q ағашы деп те белгілі. Квадри ағаштардың барлық түрлерінде ортақ ерекшеліктер бар: Олар кеңістікті бейімделетін жасушаларға бөледі. Әрбір жасушаның (немесе бөліктің) максималды сыйымдылығы бар. Максималды сыйымдылыққа жеткенде, бөлік екіге бөлінеді. Ағаш каталогы квадри ағаштың кеңістіктік бөлінуін қадағалайды. Ағаш пирамидасы (T пирамидасы) – «толық» ағаш; T пирамидасының әрбір түйіні, жапырақ түйіндерін қоспағанда, төрт бала түйініне ие; барлық жапырақтар бір деңгейде орналасқан, бұл деңгей суреттегі жеке пиксельдерге сәйкес келеді. Ағаш пирамидасындағы деректерді толық екілік ағашты массивте ықшам түрде сақтау тәсіліне ұқсас, имплицитті деректер құрылымы ретінде массивте ықшам түрде сақтауға болады.

Түрлері

Квадрат ағаштары бейнелейтін деректер түріне қарай жіктелуі мүмкін, оларға аудандар, нүктелер, сызықтар және қисықтар кіреді. Квадрат ағаштары деректерді өңдеу ретіне тәуелді немесе тәуелсіз болуына қарай да жіктелуі мүмкін. Квадрат ағаштарының ең көп кездесетін түрлері төменде келтірілген.

Облыс төрт бұтақты

Облыс төртбұрышы екі өлшемді кеңістікті төрт тең квадрантқа, субквадранттарға және т.с.с. бөлу арқылы көрсетеді, әр жапырақ түйінінде белгілі бір субоблысқа сәйкес келетін деректер болады. Ағаштың әрбір түйінінің дәл төрт баласы болады немесе балалары болмайды (жапырақ түйіні). Осы ыдырау стратегиясын қолданатын төртбұрыш ағаштардың биіктігі (яғни, субоблыстардағы қызықты деректердің болуына байланысты және оған тәуелді, олардың толыққандырақ көрсетілуі қажет болғанда) кеңістіктегі қызықты аймақтардың таралуына сезімтал және одан тәуелді болады. Облыс төртбұрышы – тридің бір түрі. 2n × 2n пикселден тұратын кескінді көрсету үшін n тереңдігі бар облыс төртбұрышын пайдалануға болады, мұнда әрбір пикселдің мәні 0 немесе 1 болады. Түбір түйіні бүкіл кескін облысын білдіреді. Егер кез келген облыстағы пикселдер толығымен 0 немесе 1 болса, ол бөлінеді. Бұл қолданбада әрбір жапырақ түйіні барлық 0 немесе барлық 1 пикселдерден тұратын блокты білдіреді. Осы ағаштарды кескіндерді сақтау үшін пайдаланғандағы кеңістікті үнемдеу мүмкіндігін ескеріңіз; кескіндерде көбінесе бір түстің мәні бірдей болатын үлкен аймақтар болады. Кескіндегі әрбір пикселдің үлкен 2D массивін сақтаудың орнына, төртбұрыш ағаш сол ақпаратты, мүмкін, пикселдік өлшемдегі жасушалардан гөрі жоғарырақ көптеген бөлу деңгейлерінде сақтай алады. Ағаштың ажыратымдылығы мен жалпы көлемі пиксел және кескін өлшемдерімен шектеледі. Облыс төртбұрышы дерек өрісінің өзгермелі ажыратымдылығы ретінде де қолданылуы мүмкін. Мысалы, белгілі бір аймақтағы температура төртбұрыш ретінде сақталуы мүмкін, әр жапырақ түйіні ол білдіретін субоблыстағы орташа температураны сақтайды.

Тоқ төрт бұтақ

Нүктелік төрт бұтақ – екі өлшемді нүктелік деректерді көрсету үшін қолданылатын екілік ағаштың түрі. Ол барлық төрт бұтақ ағаштардың қасиеттерін бөліседі, бірақ бөліністің ортасы әрқашан нүктеде болатындықтан, бұл нағыз ағаш. Ол екі өлшемді, реттелген дерек нүктелерін салыстыруда өте тиімді, көбінесе O(log n) уақытында жұмыс істейді. Нүктелік төрт бұтақтар толықтығы үшін атауға лайық, бірақ олар жалпыланған екілік іздеу құралдары ретінде k d ағаштарынан басымдық алды. Нүктелік төрт бұтақтар келесідей құрылады. Келесі нүктені енгізген кезде, оның орналасқан ұяшығын тауып, оны ағашқа қосамыз. Жаңа нүкте оны қамтитын ұяшықты, нүкте арқылы өтетін тік және көлденең сызықтармен төрт бөлікке бөліп қосады. Сондықтан ұяшықтар тіктөртбұрышты, бірақ міндетті түрде шаршы емес. Бұл ағаштардың әрбір түйінінде бір кіріс нүктесі болады. Жазықтықтың бөлінуі нүктелерді енгізу тәртібімен анықталатындықтан, ағаштың биіктігі енгізу тәртібіне сезімтал және оған тәуелді. "Нашар" тәртіппен енгізу кіріс нүктелерінің санына пропорционал биіктіктегі ағашқа әкелуі мүмкін (сонда ол тізімге айналады). Егер нүктелер жиынтығы өзгермейтін болса, теңгерімді биіктіктегі ағаш құру үшін алдын ала өңдеу жүргізуге болады.

Нысан-аймақ (PR) төрт бұтақ

Пункттік аймақ (PR) төртбұтақтары аймақтық төртбұтақтарға өте ұқсас. Айырмашылық – жасушалар туралы сақталатын мәліметтердің түрінде. Аймақтық төртбұтақта жапырақтың жасушасының бүкіл ауданына қолданылатын бірыңғай мән сақталады. Ал PR төртбұтағының жасушалары жапырақтың жасушасы ішіндегі нүктелердің тізімін сақтайды. Бұрыңғыда айтылғандай, осы ыдырау стратегиясын қолданатын ағаштардың биіктігі нүктелердің кеңістіктегі таралуына байланысты. Нүктелік төртбұтақ сияқты, PR төртбұтағы да "нашар" жиын берілген кезде сызықтық биіктікке ие болуы мүмкін.

Көлденең төрт бұтақ

Шеті бар төрт бұтақтар (PM төрт бұтақтары сияқты) нүктелердің орнына сызықтарды сақтау үшін қолданылады. Сызықтар ұяшықтарды өте ұсақ деңгейге дейін бөлу арқылы жуықтатылады, нақтырақ айтқанда, әрбір ұяшықта бір ғана сызық сегменті қалғанша. Бұрыштар мен төбелердің жанында шеті бар төрт бұтақтар ыдыраудың ең жоғары деңгейіне жеткенше бөлінуді жалғастырады. Бұл индекстеудің мағынасын жоятын өте теңгерімсіз ағаштарға алып келуі мүмкін.

Көпбұрышты карта (PM) төртбұрышты

Көпбұрышты картаның төртбұрышты ағашы (немесе PM Quadtree) – бұл көпбұрыштар жинағын сақтауға қолданылатын төртбұрышты ағаштың бір түрі, олар бұзылған болуы мүмкін (яғни оқшауланған төбелері немесе қабырғалары бар). PM төртбұрышты ағаштары мен қабырғалық төртбұрышты ағаштардың басты айырмашылығы – егер кесінділер ұяшықта түйіскен болса, қарастырылып отырған ұяшық бөлінбейді. PM төртбұрышты ағаштарының үш негізгі класы бар, олар әрбір қара түйінде қандай ақпарат сақталады дегенге байланысты өзгереді. PM3 төртбұрышты ағаштары кез келген қиылыспайтын қабырғаларды және ең көп дегенде бір нүктені сақтай алады. PM2 төртбұрышты ағаштары PM3 төртбұрышты ағаштарымен бірдей, бірақ барлық қабырғалардың ортақ нүктесі болуы керек. Соңында, PM1 төртбұрышты ағаштары PM2-ге ұқсас, бірақ қара түйіндер нүкте мен оның қабырғаларын немесе нүктемен ортақ болатын қабырғалар жиынтығын қамтуы мүмкін, бірақ нүкте болмаған қабырғалар жиынтығы мен нүктенің бірге болуына рұқсат етілмейді.

Сығымдалған төрт бұрышты ағаштар

Бұл бөлімде Сариел Хар Пеледтің кітабынан алынған кіші бөлім қамтылған. Егер әрбір бөлінген жасушаға сәйкес келетін түйінді сақтасақ, көптеген бос түйіндер жиналуы мүмкін. Мұндай сирек ағаштардың мөлшерін тек қызықты деректері бар жапырақтары бар кіші ағаштарды (яғни "маңызды кіші ағаштарды") сақтау арқылы азайтуға болады. Өлшемді одан да қысқартуға болады. Егер біз тек маңызды кіші ағаштарды сақтасақ, кесу процесі ағашта аралық түйіндердің дәрежесі екіге тең (бір ата-ана және бір балаға сілтеме) болатын ұзын тізбектерді қалдыруы мүмкін. Бұл тізбектің басындағы түйінді сақтау жеткілікті (және алынған түйіндерді көрсету үшін кейбір метадеректерді қосу), содан кейін оның соңында тамырланған кіші ағашты қосу керек. Бұл сығылған ағаштар "жаман" кіріс деректері берілген кезде сызықтық биіктікке ие болуы мүмкін. Осы сығылуды орындағанда ағаштың көп бөлігі кесілсе де, Z қисығын пайдаланып іздеу, енгізу және жою операцияларын логарифмдік уақытта орындау мүмкін. Z қисығы толық төртбұрыштың (соның салдарынан сығылған төртбұрыштың да) әрбір жасушасын уақыттың белгілі бір мерзімінде бір өлшемді сызыққа бейнелейді (және кері бейнелеуді де орындайды), элементтердің толық тәртібін құрады. Сондықтан төртбұрышты тізімделген жиынның дерек құрылымында (онда ағаштың түйіндері сақталады) сақтауға болады. Біз одан әрі жалғастырмас бұрын, мақұлдағысы келген бір шартты айтуымыз керек: екі нақты санды екілік түрінде бергенде, олардың ерекшеленетін бірінші битінің индексін уақыттың белгілі бір мерзімінде есептей аламыз деп есептейміз. Сонымен қатар, төртбұрышты ағаштағы екі нүкте/жасушаның ең төменгі ортақ ата-анасын уақыттың белгілі бір мерзімінде есептей аламыз және олардың Z тәртібін анықтай аламыз, сондай-ақ еден функциясын уақыттың белгілі бір мерзімінде есептей аламыз. Осы шарттарға сәйкес, берілген нүктенің орнын табу (яғни нүктені қамтитын жасушаны анықтау), енгізу және жою операцияларын уақыттың белгілі бір мерзімінде орындауға болады (яғни негізгі тізімделген жиынның дерек құрылымында іздеуді орындауға кеткен уақыт). (яғни, сығылған ағаштағы оның жасушасын табу) үшін нүктенің орнын табу үшін: Z тәртібі бойынша нүктеден бұрын келетін сығылған ағаштағы жасушаны табыңыз. Бұл жасушаны If деп атаңыз. Егер If болса, қайтарыңыз. Әйтпесе, сығылмаған төртбұрышты ағашта нүкте мен жасушаның ең төменгі ортақ ата-анасы қандай болар еді, оны анықтаңыз. Бұл аталық жасушаны шақырыңыз. Z тәртібі бойынша нүктеден бұрын келетін сығылған ағаштағы жасушаны табыңыз және оны қайтарыңыз. Енді егжей-тегжейге тоқталмай, енгізу және жою операцияларын орындау үшін біз алдымен енгізу/жою қажетті нәрсенің орнын анықтаймыз, содан кейін оны енгізу/жою операциясын орындаймыз. Ағашты қажеттілікке қарай қайта пішіп, қажет болған жағдайда түйіндерді құру және жою қажет.

This section summarizes a subsection from a book by Sariel Har Peled. If we were to store every node corresponding to a subdivided cell, we may end up storing a lot of empty nodes. We can cut down on the size of such sparse trees by only storing subtrees whose leaves have interesting data (i. e. "important subtrees"). We can actually cut down on the size even further. When we only keep important subtrees, the pruning process may leave long paths in the tree where the intermediate nodes have degree two (a link to one parent and one child). It turns out that we only need to store the node at the beginning of this path (and associate some meta data with it to represent the removed nodes) and attach the subtree rooted at its end to It is still possible for these compressed trees to have a linear height when given "bad" input points. Although we trim a lot of the tree when we perform this compression, it is still possible to achieve logarithmic time search, insertion, and deletion by taking advantage of Z order curves. The Z order curve maps each cell of the full quadtree (and hence even the compressed quadtree) in time to a one dimensional line (and maps it back in time too), creating a total order on the elements. Therefore, we can store the quadtree in a data structure for ordered sets (in which we store the nodes of the tree). We must state a reasonable assumption before we continue: we assume that given two real numbers expressed as binary, we can compute in time the index of the first bit in which they differ. We also assume that we can compute in time the lowest common ancestor of two points/cells in the quadtree and establish their relative Z ordering, and we can compute the floor function in time. With these assumptions, point location of a given point (i. e. determining the cell that would contain ), insertion, and deletion operations can all be performed in time (i. e. the time it takes to do a search in the underlying ordered set data structure). To perform a point location for (i. e. find its cell in the compressed tree):
Find the existing cell in the compressed tree that comes before in the Z order. Call this cell If , return Else, find what would have been the lowest common ancestor of the point and the cell in an uncompressed quadtree. Call this ancestor cell Find the existing cell in the compressed tree that comes before in the Z order and return it. Without going into specific details, to perform insertions and deletions we first do a point location for the thing we want to insert/delete, and then insert/delete it. Care must be taken to reshape the tree as appropriate, creating and removing nodes as needed.

Квадри ағаштар арқылы суреттерді өңдеу

Квадриттер, әсіресе аймақтық квадриттер, сурет өңдеуге өте ыңғайлы. Біз талқылауды екілік сурет деректерімен шектейміз, бірақ аймақтық квадриттер және олармен орындалатын сурет өңдеу операциялары түсті суреттерге де жарамды. Екі бинарлық сурет берілгенде, сурет одағы (немесе үстінен жабысу) егер кіріс суреттердің біреуінде бірдей орналасқан пиксель қара болса, сол пиксельді қара түске бояйды. Яғни, шығыс суретіндегі пиксель тек екі кіріс суретіндегі сәйкес пиксель ақ болған жағдайда ғана ақ болады, әйтпесе шығыс пикселі қара болады. Операцияны пиксель бойынша орындаудың орнына, квадриттің бір түйінмен бірнеше пикселді бейнелеу мүмкіндігін пайдаланып, одақты тиімдірек есептеуге болады. Төмендегі талқылау үшін, егер кіші ағашта қара және ақ пиксельдердің екеуі де болса, онда сол кіші ағаштың түбі сұр түсті деп айтамыз. Алгоритм екі кіріс квадритті (және ) аралап, шығыс квадритті құру арқылы жұмыс істейді. Формальды емес түрде алгоритм келесідей: суреттердегі бірдей аймаққа сәйкес келетін түйіндерді қарастырыңыз. Егер немесе түйіні қара болса, сәйкес түйін құрылып, қара түске боялады. Егер олардың біреуі ғана қара болса, ал екіншісі сұр болса, сұр түйіннің астында кіші ағаш болады, оны аралаудың қажеті жоқ. Егер (немесе ) түйіні ақ болса, (немесе ) түйіні және оның астындағы кіші ағаш (бар болса) түйінге көшіріледі. Егер екеуі де сұр болса, онда және түйіндерінің сәйкес балалары қарастырылады. Бұл алгоритм жұмыс істейді, бірақ ол өзі минималды өлшемді квадритті кепілдемейді. Мысалы, егер біз шахмат тақтасын (әрбір тікбұрыш пиксель болатын) оның толықтырғышымен біріктірсек, қандай нәтижеге жететінімізді қарастырайық. Нәтижесінде алып қара шар пайда болады, оны тек қара түсті түбір түйінмен бейнелеу керек, бірақ алгоритм орнына 4-арық тереңдігі бар толық ағаш құрайды. Бұл мәселені шешу үшін, біз құрылған квадриттің төменнен жоғарыға қарай аралап шығамыз, төрт бала түйінінің түсі бірдей болса, олардың ата-анасын сол түстің жапырағымен ауыстырамыз. көрсеткендей, осылайша байланысты компоненттерді квадриттің өлшеміне пропорционал уақытта табуға болады. Біз әрбір бірегей белгіні жеке жиын ретінде бастаймыз. Бірінші қадамдағы әрбір эквиваленттілік қатынасы үшін сәйкес жиындарды біріктіреміз. Содан кейін, әрбір қалған ерекше жиын суреттегі ерекше байланысты компонентке сәйкес келеді. Үшінші қадам тағы бір пост-ордер аралауын жүргізеді. Бұл жолы әрбір қара түйін үшін біз union-find операциясының find функциясын (ескі белгісімен) пайдаланып, оның жаңа белгісін (ол бөлігі болып табылатын байланысты компонентке сәйкес) тауып, тағайындаймыз.

Quadtrees, particularly the region quadtree, have lent themselves well to image processing applications. We will limit our discussion to binary image data, though region quadtrees and the image processing operations performed on them are just as suitable for colour images. Given two binary images, the image union (also called overlay) produces an image wherein a pixel is black if either of the input images has a black pixel in the same location. That is, a pixel in the output image is white only when the corresponding pixel in both input images is white, otherwise the output pixel is black. Rather than do the operation pixel by pixel, we can compute the union more efficiently by leveraging the quadtree's ability to represent multiple pixels with a single node. For the purposes of discussion below, if a subtree contains both black and white pixels we will say that the root of that subtree is coloured grey. The algorithm works by traversing the two input quadtrees ( and ) while building the output quadtree Informally, the algorithm is as follows. Consider the nodes and corresponding to the same region in the images. If or is black, the corresponding node is created in and is colored black. If only one of them is black and the other is gray, the gray node will contain a subtree underneath. This subtree need not be traversed. If (respectively, ) is white, (respectively, ) and the subtree underneath it (if any) is copied to If both and are gray, then the corresponding children of and are considered. While this algorithm works, it does not by itself guarantee a minimally sized quadtree. For example, consider the result if we were to union a checkerboard (where every tile is a pixel) of size with its complement. The result is a giant black square which should be represented by a quadtree with just the root node (coloured black), but instead the algorithm produces a full 4 ary tree of depth To fix this, we perform a bottom up traversal of the resulting quadtree where we check if the four children nodes have the same colour, in which case we replace their parent with a leaf of the same colour. showed how we can find and label these connected components in time proportional to the size of the quadtree. We start with each unique label as a separate set. For every equivalence relation noted in the first step, we union the corresponding sets. Afterwards, each distinct remaining set will be associated with a distinct connected component in the image. Step three performs another post order traversal. This time, for each black node we use the union find's find operation (with the old label of ) to find and assign its new label (associated with the connected component of which is part).

Жалпы сілтемелер

14-тарау: Төртбұрышты ағаштар: 291–306 беттер.