Попытка понять концепцию Quadtree и применить ее для хранения информации о раскраске изображения

Question

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

Мой вопрос:

Как работает, что листовые узлы содержат только пиксели? Почему другие узлы не содержат пикселей? И как мы узнаем, сколько раз подразделить наш исходный корневой узел для представления данного изображения? Мы просто подразделяем его n раз, где n это высота и ширина (для квадрата)?

Редактировать: Итак, как мне отслеживать листовые узлы, чтобы я знал, когда добавлять пиксели в этом месте? Прямо сейчас у меня есть вспомогательная функция, которая делит регионы для меня, отслеживая ширину и высоту.

Answer 1

Quadtree лучше всего подходят для квадратных изображений, размер которых равен степени 2 (например, для большинства текстур). Вы не должны думать о каждом узле как о представлении «пикселя». Вместо этого думайте об этом как о представлении «квадратного блока пикселей размером 2 ^ k». В случае конечных листьев k равно 0, поэтому каждый конечный узел представляет квадратный блок пикселей размером 1, то есть один пиксель. Внутренние узлы в дереве представляют все большие и большие участки изображения.

Answer 2

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

Как мы узнаем, сколько раз подразделить?Ну, конечно, есть несколько способов сделать это, в зависимости от того, почему вы строите квадродерево.В общем, области изображения с большей энтропией - больше «детализации» - следует подразделить больше, в то время как области с более низкой энтропией, «более плоские» можно разделить меньше.Существует ряд различных алгоритмов для выбора, когда и где делить.Как правило, они сравнивают значения пикселей в пределах области и разделяются, когда различия превышают некоторый порог.

Answer 3

Я думаю, что лучший способ ответить на ваш вопрос - это ответить на два вопроса, которые вы не задавали.

• Что такое квадри?
• Как это можно применить к системам моделирования с неустойчивой плотностью?

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

Применение этогоСжатие изображений и прогрессивное отображение довольно очевидны: если вы делаете обход дерева, ограниченный глубиной n, то вы получаете 4 ^ n элементов информации об изображении, охватывающих все пространство изображения.Если вы на один уровень глубже, каждый пиксель делится на четыре.JPEG2000 работает так, если я правильно помню.Я сказал «элементы информации об изображении», потому что они не должны быть единичными;элементы могут быть 32-битными ARGB или любым другим свойством (или свойствами), описывающим пространство в этой точке.

Answer 4

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

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

И как мы узнаем, сколько раз подразделить наш исходный корневой узел для представления данного изображения?подразделение, вы вдвое меньше ширины и высоты области, поэтому для квадратного изображения размером n вам нужно будет поделить log2(n) раз, для неквадратного изображения размером n*m вам понадобится не болееmax(log2(n), log2(m)) шагов.