С интерактивной игровой площадкой благодаря WebAssembly

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

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

Весь код для этого поста находится здесь: https://github.com/kurtschelftthout/quadtrees.

Основы деревьев квадрантов

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

В таком дереве мы можем хранить различную информацию, обычно связанную с двумерными данными, например расположение объектов на плоскости, сводку части изображения, например, его средний цвет, или информацию о линиях или формах в изображении. область рисунка. Почему бинарные деревья, квадродеревья и октодеревья используются чаще, чем 5-мерные или 12-мерные деревья? Из-за отношения к одно-, двух- и трехмерному пространству. Чтобы разбить (одномерный) отрезок линии, требуется два отрезка, четыре квадрата для разбиения квадрата и восемь кубов для разбиения куба в трехмерном пространстве.

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

В этом посте мы рассмотрим конкретно деревья квадрантов. Дерево квадрантов региона разбивает 2D-пространство на регионы — каждый узел в дереве квадрантов региона представляет собой прямоугольную область. Области можно разделить на четыре подобласти, которые можно разделить по очереди, пока не будет достигнуто желаемое разрешение.

Представление изображений с помощью деревьев квадрантов

Я буду использовать quadtrees для представления версии изображения с более низким разрешением. Идея состоит в многократном разделении изображения на четыре области. Каждая область, которая может содержать множество пикселей, аппроксимируется одним значением — «большим пикселем». Я возьму среднее значение значений RGB в регионе как цвет этого большого пикселя.

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

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

Далее в дереве, на среднем уровне, каждая область имеет размер два на два пикселя и является лишь приближением к оригиналу. В верхнем левом и нижнем правом углах приближение оказывается точным. На корневом уровне есть только один большой пиксель.

Благодаря волшебству WebAssembly, который скомпилировал мой код Rust ниже во что-то, что запускается в браузере, вы можете поиграться с деревьями квадрантов на более реалистичном изображении:

Площадка для полных деревьев квадрантов, примененных к изображению HAL 9000

Вот скриншот игровой площадки в действии. Исходное изображение слева, изображение, представленное регулируемым уровнем в дереве квадрантов справа.

Это работает достаточно хорошо для симметричных изображений, таких как приведенное выше, но у большинства изображений есть части, о которых мы меньше заботимся. Было бы неплохо, если бы мы могли сфокусировать дерево квадрантов, чтобы разделить только интересные части изображения на более мелкие области. Для этого у нас больше не может быть полного дерева квадрантов — интересные регионы получат больше уровней, чем неинтересные, и дерево будет несбалансированным.

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

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

Вот демонстрация дерева квадрантов регионов в действии. Вы можете интерактивно настроить желаемую ошибку и минимальную длину области.

Площадка для квадродеревьев регионов, примененных к изображению совы

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

Реализация дерева квадрантов региона в Rust

Это все, что касается демонстраций, давайте посмотрим на код для дерева квадрантов регионов — второй подход.

Представление дерева квадрантов региона является простым:

struct Region {
    x: usize,
    y: usize,
    width: usize,
    height: usize,
}

enum RegionQuadTree {
    Leaf(Region, Rgba),
    Branch([Box<RegionQuadTree>; 4]),
}

Квадрант — это либо лист, либо ветвь. Лист хранит область, которую он представляет, и его цвет в виде значения RGBA (красный + зеленый + синий + альфа). Я выбрал RGBA просто потому, что именно так HTML-холст представляет пиксель данных изображения. Вы можете хранить любую информацию о регионе в листовых узлах. Ветка имеет ссылки только на своих четырех дочерних элементов. Обычно имеет смысл хранить больше информации о ветках, например, о регионе, к которому они относятся, но здесь мне это не понадобилось.

Драйвером для демонстрации является следующая функция:

pub fn subdivide_until(&mut self, error_threshold: f32, min_region_length: usize) {
    loop {
        let new_quadtree =
            self.quadtree
                .subdivide(&self.image, error_threshold, min_region_length);
        match new_quadtree {
            Some(qt) => self.quadtree = qt,
            None => break,
        }
    }
}

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

fn subdivide(
    &self,
    image: &Image,
    error_threshold: f32,
    min_region_length: usize,
) -> Option<RegionQuadTree>

Он возвращает новое разделенное дерево квадрантов или None, если соблюдается либо порог ошибки, либо минимальная длина области:

fn subdivide(
    &self,
    image: &Image,
    error_threshold: f32,
    min_region_length: usize,
) -> Option<RegionQuadTree> {
    let region = self.region();
    if self.get_error(image) < error_threshold
        || region.height <= min_region_length
        || region.width <= min_region_length
    {
        return None;
    }
    match self {
        RegionQuadTree::Leaf(region, _) => {
            /// ...
        }
        RegionQuadTree::Branch(children) => {
            /// ...
        }
    }
}

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

Подразделение листа означает разделение его на четыре области, стараясь не пропустить ни одного пикселя, а затем создание новой ветви для хранения четырех новых дочерних элементов:

match self {
    RegionQuadTree::Leaf(region, _) => {
        let half_width_l = (region.width as f64 / 2.0).floor() as usize;
        let half_width_r = (region.width as f64 / 2.0).ceil() as usize;
        let half_height_up = (region.height as f64 / 2.0).floor() as usize;
        let half_height_dwn = (region.height as f64 / 2.0).ceil() as usize;
        let children = [
            Box::new(RegionQuadTree::leaf(
                region.x,
                region.y,
                half_width_l,
                half_height_up,
                image,
            )),
            Box::new(RegionQuadTree::leaf(
                region.x,
                region.y + half_height_up,
                half_width_l,
                half_height_dwn,
                image,
            )),
            Box::new(RegionQuadTree::leaf(
                region.x + half_width_l,
                region.y,
                half_width_r,
                half_height_up,
                image,
            )),
            Box::new(RegionQuadTree::leaf(
                region.x + half_width_l,
                region.y + half_height_up,
                half_width_r,
                half_height_dwn,
                image,
            )),
        ];
        Some(RegionQuadTree::Branch(children))
    }
    RegionQuadTree::Branch(children) => {
        // ...
    }
}

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

match self {
    RegionQuadTree::Leaf(region, _) => {
        // ...
    }
    RegionQuadTree::Branch(children) => {
        // call subdivide on all children - zip with existing children to use 
        // as default later.
        let sub_children: Vec<_> = children
            .iter()
            .map(|child| child.subdivide(image, error_threshold, min_region_length))
            .zip(children)
            .collect();
        // all children returned None - avoid returning a superfluous new tree.
        if sub_children.iter().all(|c| c.0.is_none()) {
            return None;
        }
        // replace any None result on children with the "old" child.
        let children = sub_children
            .into_iter()
            .map(|(nc, oc)| Box::new(nc.unwrap_or(*oc.clone())))
            .collect::<Vec<_>>()
            .try_into()
            .unwrap();
        Some(RegionQuadTree::Branch(children))
    }
}

Это самые важные биты — вы можете посмотреть остальной код в репозитории.

Существует также реализация полного дерева квадрантов. Основное отличие дерева квадрантов региона состоит в том, что мы можем заранее определить количество узлов. Например, полное дерево квадрантов с тремя уровнями (не считая корня) имеет 1+4+16+64 узла. Как и в случае с бинарным деревом, это можно использовать для хранения полного дерева квадрантов в массиве и использования индексов для представления структуры родитель-потомок: дочерние элементы узла с индексом i сохраняются с индексами от 4*i + 1 до 4*i + 4.

Какое это имеет отношение к z-порядку?

В последнем откусывании я сказал, что кривые Z-порядка полезны для создания деревьев квадрантов. Я не использовал их здесь, но стоит изучить связь. Если вы внимательно посмотрите на создание четырех новых листовых узлов в случае RegionQuadTree::Leaf из subdivide выше, вы увидите, что листья создаются в z-порядке: верхний левый, нижний левый, верхний правый, нижний правый. Это верно рекурсивно, поскольку создание новых ветвей сохраняет тот же порядок, что и существующие дочерние элементы. Это немного яснее в полном дереве квадрантов, потому что все его области имеют одинаковый размер.

Если области для вставки известны, можно избежать накладных расходов при создании дерева, если передать аргументы процессору создания дерева в z-порядке. Таким же образом можно распараллелить создание дерева квадрантов.

В заключение

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

Спасибо за прочтение! Я пишу один кусок каждый месяц. Чтобы узнать больше, подпишитесь на мою рассылку и следите за мной в Twitter или Mastodon.

Рекомендации