3

我正在尝试使用四叉树（四叉树）来保存给定 BMP 中的信息。
我正在努力弄清楚如何在给定任何 BMP 的情况下构建树。

基本上结构是这样的，每片叶子代表一个像素。每个节点有 4 个指针，每个指针指向图像中剩余的四个象限之一。因此每个节点将当前图片分成4个部分。当你在叶子上时，你就在一个特定的像素上。

我不确定如何构建一棵树来映射某个图像。假设图像的尺寸是二次方，我该怎么办。我知道递归函数可能最优雅地做到这一点，但我正在努力弄清楚如何跟踪我将在图像中的位置。

这是在 C++ 中，目前我的 quadtree.h 文件包含一个 Node* 根，其中一个节点被定义为具有像素元素和 4 个指向其他节点的指针的结构。每个内部节点（非叶节点）应该保存它导致的所有 4 个 RGB 值的平均值。

我正在尝试制作一个算法，但我认为我可能需要在 .h 文件中包含一个或两个结构。有没有更好/更干净的方法来解决这个问题？

4

2 回答 2

2

好吧，根据您存储位图数据的方式，您可能会做不同的事情。您是从文件中读取它并将其直接放入树中吗？如果是这样，.BMP 文件（如果我没记错的话）会在顶部告诉您它们的宽度和高度，因此您实际上可以使用它来确定您将拥有多少级别，这可能会帮助您构建一些东西。

此外，根据您的图像有多大，您可以将所有像素存储在一个二维节点数组中，并让树排序“坐在”数组的顶部，这样您的叶子就在数组中，而其他所有东西都在其他地方. 如果你要这样做，你可以编写一些嵌套循环，这些循环会遍历并抓取四个节点的组，计算它们的平均值，并将它们集中在一起，然后对刚刚创建的节点执行相同的操作。这可能比从上到下构建树要快，因为您永远不会平均超过四个像素，而从上到下构建除了最后一个之外，每一步都需要平均超过四个像素。

如果您不想在数组中执行此操作，在我看来，最简单的方法是让每个节点跟踪其 x,y 坐标。这将允许你做与数组基本相同的事情，但你不会只是插入索引。

这有帮助吗？你是如何存储位图的？最终目标是什么？

于 2010-06-01T14:03:06.480 回答
1

STANN 是目前最好的开源实现。

http://sites.google.com/a/compgeom.com/stann/

明智的说法是，使用 Bern 等人的四叉树构造算法并放弃时髦的树操作。

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4634&rep=rep1&type=pdf

  1. 按莫顿顺序对所有点进行排序。
  2. 计算每对连续点之间的四叉树框长度。
  3. 进行所有最接近的最大值计算以找到父母/兄弟姐妹。

我现在正在为 OpenCl 开发一个库。一旦我完成测试，我会发布一个链接。

于 2010-07-05T20:09:58.127 回答