如何在C++的四叉树中存储 bmp 文件?

Question

我想在QuadTree中读取和存储BMP文件：

BMP文件的示例如下：

P1
4 4
1 0 1 1
0 1 0 0
1 1 0 0
1 1 0 0

我想到的QuadTree的结构是：

struct QuadTreeNode{
int size;
struct QuadTreeNode *children[4];
int color;    //0 white, 1 black, -1 div
};

我很难想出建立QuadTree的方法。在读取文件时构建QuadTree的好方法是什么？我应该从leaves开始还是从主要QuadTree开始？

Answer 1

我将开始定义一些不错的结构来存储图像，该结构也能够将子图像映射到原始数据中;

例如

struct Img{
int   width;
int   height;
int   rowstep; ///< in multiples of pixel data type
int*  data; ///< ptr type may be different or void
};

然后我会将文件中的数据读取/转换为一些内存(解析图像值)并创建一个顶级 img：

Img toplevel {4,4, 32, dataptr};

4个子：

Img tl {toplevel.width/2,toplevel.height/2, toplevel.rowstep, toplevel.data};
Img tr {toplevel.width/2,toplevel.height/2, toplevel.rowstep, toplevel.data+toplevel.width/2};
Img bl {toplevel.width/2,toplevel.height/2, toplevel.rowstep, toplevel.data + toplevel.rowstep*toplevel.height/2};
Img br {toplevel.width/2,toplevel.height/2, toplevel.rowstep, toplevel.data + toplevel.rowstep*toplevel.height/2 + toplevel.width/2};

您现在可以递归地将每个 img 拆分为 4 个较小的 img，只要宽度大于 1(递归下降)。
然后，您就有了叶子的颜色值。
在递归提升中，您可以从更深层次对 4 个值求和/平均(如果您不需要它们，请丢弃子图像)。

最后你应该有一个完整的四叉树。

附注：

补充一条评论：

我会尽量不要在四叉树结构中使用原始指针。 也许使用std::array<std::shared_ptr<QuadTreeNode>, 4> children;

Answer 2

变量大小是多少？

您的结构还应包含指向父节点的指针，以便您可以在四叉树中自由移动。

保存颜色的变量应替换为包含 3 个表示颜色的变量的结构，因为像素通常由 3 个组件表示：红色、绿色和蓝色。如果您正在处理二进制图像，布尔值或字符就足够了。

在你的结构中，你需要一个额外的变量，它有四叉树的位置和大小。

您的结构可能如下所示

struct QuadtreeNode{
short x1;
short y1;
short x2;
short y2;
Color_Pixel pixel;        
struct QuadtreeNode *parent;
struct QuadtreeNode *quad[4];
};
struct Color_Pixel{
uchar r;
uchar g;
uchar b;
};

你的问题

我应该从叶子开始还是从主四叉树开始？

您应该从"主四叉树"开始，第一个节点代表整个图像，然后您必须将图像划分为其他节点或"叶子"。 在您的析构函数中，您必须从底部移动到顶部才能正确释放分配的资源，您应该从"叶子"开始。