Квадродерево: Структура данных для двумерного разбиения пространства

Введение

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

Квадричное дерево — это структура данных дерева, в которой каждый внутренний узел имеет ровно четыре дочерних узла. Квадричные деревья являются двухмерным аналогом октричных деревьев и чаще всего используются для разделения двухмерного пространства путем рекурсивного деления его на четыре квадранта или области. Данные, связанные с листовой ячейкой, могут различаться в зависимости от приложения, но листовая ячейка представляет собой «единицу значимой пространственной информации». Разделенные области могут быть квадратными или прямоугольными, либо иметь произвольную форму. Эта структура данных была названа квадричным деревом Рафаэлем Финкелем и Дж. Л. Бентли в 1974 году. Подобное разделение также известно как Q-дерево. Все формы квадричных деревьев имеют некоторые общие характеристики: они разбивают пространство на адаптивные ячейки. Каждая ячейка (или корзина) имеет максимальную ёмкость. При достижении максимальной ёмкости корзина разделяется. Каталог дерева следует пространственному разбиению квадричного дерева. Дерево-пирамида (T-пирамида) — это «полное» дерево; каждый узел T-пирамиды имеет четыре дочерних узла, за исключением листовых узлов; все листья находятся на одном уровне, соответствующем отдельным пикселям изображения. Данные в дереве-пирамиде могут быть компактно сохранены в массиве как неявная структура данных, аналогично тому, как полное двоичное дерево может быть компактно сохранено в массиве.

Типы

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

Регион четырехколесный

Квадратное дерево области представляет собой разделение пространства в двух измерениях путем разложения области на четыре равных квадранта, подквадранта и так далее, при этом каждый листовой узел содержит данные, соответствующие определенному подрегиону. Каждый узел в дереве имеет ровно четыре дочерних узла или не имеет дочерних узлов (является листовым узлом). Высота квадратных деревьев, использующих эту стратегию разложения (то есть, подразделяющих подквадранты до тех пор, пока в подквадранте присутствуют интересные данные, требующие дальнейшего уточнения), чувствительна к и зависит от пространственного распределения интересных областей в разделяемом пространстве. Региональное квадратное дерево является типом префиксного дерева (три). Квадратное дерево области с глубиной n может использоваться для представления изображения, состоящего из 2n × 2n пикселей, где каждое значение пикселя равно 0 или 1. Корневой узел представляет всю область изображения. Если пиксели в любой области не являются полностью 0 или 1, она подразделяется. В этом приложении каждый листовой узел представляет блок пикселей, все значения которых равны 0 или все равны 1. Обратите внимание на потенциальную экономию памяти при использовании этих деревьев для хранения изображений; изображения часто содержат множество областей значительного размера, имеющих одинаковое цветовое значение. Вместо хранения большого двумерного массива для каждого пикселя изображения, квадратное дерево может захватить ту же информацию, потенциально на несколько уровней детализации выше, чем ячейки размером с пиксель, которые потребовались бы в противном случае. Разрешение дерева и общий размер ограничены размерами пикселей и изображения. Региональное квадратное дерево также может использоваться как представление поля данных с переменным разрешением. Например, температуры в области могут храниться в виде квадратного дерева, при этом каждый листовой узел хранит среднюю температуру для подрегиона, который он представляет.

Квадритрей

Точечное квадричное дерево — это адаптация бинарного дерева, используемая для представления двумерных точечных данных. Оно обладает характеристиками всех квадричных деревьев, но является полноценным деревом, поскольку центр подразделения всегда совпадает с точкой. Оно часто оказывается очень эффективным при сравнении двухмерных упорядоченных точек данных, обычно работая за время O(log n). Точечные квадричные деревья стоит упомянуть для полноты, однако их превзошли k d-деревья как инструменты для обобщенного двоичного поиска. Точечные квадричные деревья строятся следующим образом. Для следующей точки, которую необходимо вставить, мы находим ячейку, в которой она находится, и добавляем её в дерево. Новая точка добавляется таким образом, что ячейка, содержащая её, делится на четыре квадранта вертикальными и горизонтальными линиями, проходящими через эту точку. Следовательно, ячейки являются прямоугольными, но не обязательно квадратными. В этих деревьях каждый узел содержит одну из входных точек. Поскольку разделение плоскости определяется порядком вставки точек, высота дерева чувствительна к порядку вставки и зависит от него. Вставка в "неудачном" порядке может привести к дереву высоты, линейной относительно количества входных точек (в этом случае оно вырождается в связный список). Если набор точек статичен, можно выполнить предварительную обработку для создания дерева с сбалансированной высотой.

Квадричное дерево точки-региона (PR)

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

Край четырехколесный

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

Многоугольная карта (ПМ) квадри

Квадрикулярное дерево многоугольной карты (или PM Quadtree) — это разновидность квадрти, используемая для хранения коллекций многоугольников, которые могут быть вырожденными (то есть иметь изолированные вершины или ребра). Основное отличие PM-квадрикуляров от квадрти, основанных на ребрах, заключается в том, что рассматриваемая ячейка не подразделяется, если сегменты сходятся в вершине внутри ячейки. Существует три основных класса PM Quadtrees, различающихся в зависимости от информации, хранящейся в каждом черном узле. PM3 квадрти могут хранить любое количество непересекающихся ребер и не более одной точки. PM2 квадрти аналогичны PM3, за исключением того, что все ребра должны иметь общую конечную точку. Наконец, PM1 квадрти похожи на PM2, но черные узлы могут содержать точку и связанные с ней ребра или просто набор ребер, имеющих общую точку, однако нельзя одновременно хранить точку и набор ребер, не связанных с этой точкой.

Сжатые квадри

В этом разделе резюмируется подраздел из книги Сариэля Хар Пеледа. Если мы будем хранить каждый узел, соответствующий подразделенной ячейке, мы рискуем сохранить большое количество пустых узлов. Мы можем уменьшить размер таких разреженных деревьев, сохраняя только поддеревья, листья которых содержат значимые данные (то есть «важные поддеревья»). Мы можем еще больше сократить размер. Когда сохраняются только важные поддеревья, процесс обрезки может оставлять длинные цепочки узлов в дереве, где промежуточные узлы имеют степень два (одна связь с родителем и одна с потомком). Оказывается, достаточно хранить только узел в начале этой цепочки (и связать с ним метаданные для представления удаленных узлов) и присоединить к нему поддерево, корнем которого является конец цепочки. Даже при «неблагоприятных» входных данных такие сжатые деревья все еще могут иметь линейную высоту. Хотя при таком сжатии мы значительно обрезаем дерево, все равно можно добиться логарифмического времени поиска, вставки и удаления, используя Z-кривые. Z-кривая отображает каждую ячейку полного квадродерева (и, следовательно, даже сжатого квадродерева) за время на одномерную линию (и также отображает обратно за время ), создавая полный порядок элементов. Следовательно, мы можем хранить квадродерево в структуре данных для упорядоченных множеств (в которой хранятся узлы дерева). Прежде чем продолжить, необходимо сделать разумное предположение: мы предполагаем, что, имея два вещественных числа, представленных в двоичном виде, мы можем вычислить за время индекс первого бита, в котором они различаются. Мы также предполагаем, что мы можем вычислить за время наименьшего общего предка двух точек/ячеек в квадродереве и установить их относительный Z-порядок, а также вычислить функцию floor за время . При этих предположениях определение местоположения точки (то есть определение ячейки, содержащей ), операции вставки и удаления могут быть выполнены за время (то есть время, необходимое для поиска в базовой структуре данных упорядоченного множества). Чтобы определить местоположение точки (то есть найти ее ячейку в сжатом дереве):
1. Найдите существующую ячейку в сжатом дереве, которая предшествует в Z-порядке. Назовем эту ячейку .
2. Если , верните .
3. Иначе найдите, каким был бы наименьший общий предок точки и ячейки в несжатом квадродереве. Назовем эту ячейку-предка .
4. Найдите существующую ячейку в сжатом дереве, которая предшествует в 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.

Обработка изображений с использованием quadtrees

Квадри, особенно региональные квадри, хорошо подходят для задач обработки изображений. Мы ограничим наше обсуждение данными двоичных изображений, хотя региональные квадри и операции обработки изображений, выполняемые над ними, также применимы и к цветным изображениям. Для двух двоичных изображений объединение изображений (также называемое наложением) создает изображение, в котором пиксель становится черным, если хотя бы в одном из входных изображений в той же позиции находится черный пиксель. Иными словами, пиксель в выходном изображении будет белым только в том случае, если соответствующие пиксели в обоих входных изображениях белые, в противном случае выходной пиксель будет черным. Вместо выполнения операции попиксельно, мы можем вычислить объединение более эффективно, используя способность квадри представлять несколько пикселей одним узлом. Для целей дальнейшего обсуждения, если поддерево содержит как черные, так и белые пиксели, будем считать, что корень этого поддерева окрашен в серый цвет. Алгоритм работает путем обхода двух входных квадри (и ) при построении выходного квадри. Неформально алгоритм выглядит следующим образом. Рассмотрим узлы и , соответствующие одной и той же области на изображениях. Если или черный, то соответствующий узел создается в и окрашивается в черный цвет. Если черный только один из них, а другой – серый, то серый узел будет содержать поддерево под ним. Это поддерево не требуется обходить. Если (соответственно, ) белый, то (соответственно, ) и поддерево под ним (если оно есть) копируются в . Если оба и серые, то рассматриваются соответствующие дочерние узлы и . Хотя этот алгоритм работает, он сам по себе не гарантирует построение квадри минимального размера. Например, рассмотрим результат объединения шахматной доски (где каждая клетка – пиксель) размера с ее дополнением. Результатом будет гигантский черный квадрат, который должен быть представлен квадри, состоящим только из корневого узла (окрашенного в черный цвет), но вместо этого алгоритм создает полное 4-арное дерево глубины . Чтобы исправить это, мы выполняем обход полученного квадри снизу вверх, проверяя, имеют ли четыре дочерних узла одинаковый цвет, и в этом случае заменяем их родительский узел листом того же цвета. Показано, как можно найти и пометить эти связные компоненты за время, пропорциональное размеру квадри. Мы начинаем с каждой уникальной метки как отдельного множества. Для каждой отмеченной на первом шаге связи эквивалентности мы объединяем соответствующие множества. После этого каждому оставшемуся отдельному множеству будет соответствовать отдельный связный компонент на изображении. Третий шаг выполняет еще один обход в пост-порядке. На этот раз для каждого черного узла мы используем операцию find алгоритма union-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.