image - 使用四叉树进行图像合并

Question

我们如何使用四叉树合并两个图像？我正在浏览Quadtree的维基百科，看到图像可以使用 quad-tree 来表示。谷歌采访中也曾有人问过这个算法。

Answer 1

好吧，我刚刚阅读了有关四叉树的信息，据我了解，四叉树是一棵树，它的每个根都恰好有 4 个孩子。
还要注意的是，以根为整个图像的方式表示图像是一种很好的结构，他的 4 个孩子将图像分成 4 等份，依此类推。
在这张图片中可以很好地看到这一点：

现在我看到它的方式，整个图像必须形成一个正方形，因为有 4 个相等的正方形总是形成一个正方形，为了从四叉树中获得一个矩形，它必须有正方形剩余部分的“空”填充，如从上图中的“白色”方块可以看出。

所以假设我们有 2 个矩形，我们想将它们水平附加在一起，我理解的最直接的方法就是创建一个新树，有一个新的根，并将第一个图像添加为该根的第一个孩子，第二个图像作为该根的第二个孩子，第三个和第四个孩子将有“空”的填充物。
这样，如果图像很好地相互附加，您将获得良好的图像效果。

Answer 2

假设树是这样表示的，

class Node {
  Color color;
  List<Node> children;
}

像这样的工作吗？

Node mergeNode(Node first, Node second) {
  if ( first == null || second == null )
  {
    return first == null ? second : first;
  }
  else
  {
    List<Node> newKids = new ArrayList<Node>();
    for ( int i = 0 ; i < 4 ; ++i )
    {
        Node merged = mergeNode(first,second);
        newKids.set(i,merged);
    }
    return new Node(mergeColors(first,second),newKids));
  }
}

您解决颜色合并的策略在哪里mergeColors（类似于真值表）。