四叉树构建与二值图像压缩

周子力大约 7 分钟教学文档算法设计与分析分治法递归四叉树中等Python

四叉树构建与二值图像压缩

题目描述

给定一个 $n\times n$ 的二值网格 grid，其中 $n=2^p$ 、 $p\geq0$ ，每个元素为整数0或1。将网格构造成四叉树，利用同色区域的合并表示减少逐像素记录。

行列下标从0开始。全为0或全为1的区域用一个叶节点表示，叶节点保存颜色；非一致区域划分为四个等大的正方形，内部节点保存四个子节点，顺序固定为左上、右上、左下、右下。空网格、非方阵、边长不是2的幂或含其他值时，抛出 ValueError。

返回四叉树的根。为展示结果，程序另提供嵌套表示：叶子用整数0或1表示，内部节点用上述顺序的四元素列表表示。例如：

对应 [1, 0, 0, 1]。输入 [[1, 1], [1, 1]] 对应一个叶子1。

这里的“压缩”指把一致区域表示为一个节点，保留全部像素信息。不同图像的节点数不同，Python 对象还有存储开销，不能据此保证实际文件一定更小。

题目分析

区域一致则停止，否则四分

定义 build(top, left, size)：构造以 (top, left) 为左上角、边长为 size 的正方形区域。

区域全为同一颜色时直接返回叶子。否则按一半边长构造四个子区域，返回一个连接四个子节点的内部节点。边长1的区域只有一个像素，必定一致，因此一定能够终止。

若每次都遍历区域判断是否一致，复杂图像可能在多层重复扫描同一像素。本实现先建立二维前缀和，使每个区域的一致性判断只需常数次操作。

用二维前缀和判断一致性

定义 $P[r][c]$ 为行区间 $[0,r)$ 、列区间 $[0,c)$ 内所有像素之和，首行、首列均为0。对当前区域令 $bottom=top+size$ 、 $right=left+size$ ，其中1的个数为：

S=P[bottom][right]-P[top][right]-P[bottom][left]+P[top][left].

因为元素只有0、1， $S=0$ 表示全为0， $S=size^2$ 表示全为1；其他情况必须继续划分。前缀和负责快速查询，四叉树负责空间组织，两者任务不同。

正确性依据

叶子颜色由区域和精确判断，能恢复这一整块像素。非一致区域的四个子正方形互不重叠且完整覆盖父区域；假设四个子树分别正确表示各自区域，按固定顺序连接后就能正确表示父区域。对子树递归应用，最终恢复的网格与输入完全一致。

这一结构可与棋盘覆盖比较：都进行四分，但本题的停止条件是区域一致，输出是树结构。

实现代码

Python 前缀和与四叉树实现

class QuadNode:
    def __init__(self, value=None, children=()):
        self.value = value          # 叶子为0或1，内部节点为None
        self.children = children    # 左上、右上、左下、右下

    @property
    def is_leaf(self):
        return not self.children


def build_quadtree(grid):
    n = len(grid)
    if n == 0 or (n & (n - 1)) != 0:
        raise ValueError("边长必须是正的2的幂")
    if any(len(row) != n for row in grid):
        raise ValueError("输入必须是方阵")
    if any(type(v) is not int or v not in (0, 1) for row in grid for v in row):
        raise ValueError("像素必须是整数0或1")

    prefix = [[0] * (n + 1) for _ in range(n + 1)]
    for r in range(n):
        row_sum = 0
        for c in range(n):
            row_sum += grid[r][c]
            prefix[r + 1][c + 1] = prefix[r][c + 1] + row_sum

    def build(top, left, size):
        bottom, right = top + size, left + size
        total = (prefix[bottom][right] - prefix[top][right]
                 - prefix[bottom][left] + prefix[top][left])
        if total == 0:
            return QuadNode(0)
        if total == size * size:
            return QuadNode(1)

        half = size // 2
        return QuadNode(children=(
            build(top, left, half),
            build(top, left + half, half),
            build(top + half, left, half),
            build(top + half, left + half, half),
        ))

    return build(0, 0, n)


def to_nested(node):
    if node.is_leaf:
        return node.value
    return [to_nested(child) for child in node.children]


grid = [
    [1, 1, 0, 0],
    [1, 1, 0, 0],
    [0, 0, 1, 1],
    [0, 0, 1, 1],
]
print(to_nested(build_quadtree(grid)))
print(to_nested(build_quadtree([[1, 1], [1, 1]])))
print(to_nested(build_quadtree([[0]])))

输出：

[1, 0, 0, 1]
1
0

内部节点不存像素颜色，用 None 区分；叶子没有子节点。网格中的0也是合法颜色，不能把 value == 0 理解为“节点不存在”。

算法执行过程

主示例中的 build 状态为“左上角行号、列号、边长”。

调用状态	区域中1的个数	判定与返回
`(0, 0, 4)`	8，既非0也非16	建内部节点，执行四个子调用
`(0, 0, 2)`	4，等于面积	左上返回叶子1
`(0, 2, 2)`	0	右上返回叶子0
`(2, 0, 2)`	0	左下返回叶子0
`(2, 2, 2)`	4，等于面积	右下返回叶子1
返回根节点	四个叶子已经就绪	嵌套表示为 `[1, 0, 0, 1]`

前缀和仍处理全部16个像素，但树只创建1个内部节点、4个叶子。2×2棋盘格 [[0,1],[1,0]] 则不能合并同色区域，需要1个内部节点和4个单像素叶子。

复杂度分析

按像素读写、索引访问及区域和的算术操作为单位成本，令像素总数 $N=n^2$ 。

时间复杂度： $O(N)$ 。检查输入和建立前缀和均为 $O(N)$ ；每个树节点只需常数次区域查询。最坏情况下递归到全部单像素叶子，节点数为：

1+4+\cdots+4^p=\frac{4N-1}{3}=O(N).

因此整个实现即使输入全为同色，也需要线性时间建立前缀和。单独的树构建阶段在该情况下只创建一个节点。

辅助空间复杂度： $O(N)$ ，主要为前缀和；递归栈为 $O(\log(n+1))$ 。输出树最坏为 $O(N)$ ，一致图像的输出树仅有一个节点。to_nested 另创建与输出树节点数量同阶的嵌套表示，其调用栈仍为对数深度。

这里用边长表示的最坏递推为 $T(n)=4T(n/2)+O(1)$ ；若改用像素数表示，则为 $T(N)=4T(N/4)+O(1)$ 。不能将两种规模混用。

易错点

任意矩形直接四等分。 本题限定方阵且边长为2的幂；推广到任意尺寸需重新定义划分和边界。
四个子节点顺序不一致。 构建、显示和解码必须共同使用左上、右上、左下、右下。
只看四个角来判断一致。 中间像素可能不同，必须检查整个区域的信息。
只凭区域和判断非二值网格。 一致性判断依赖像素只能为0或1的前提。
把每层重新扫描的实现也写成线性时间。 本实现使用前缀和；若每个区域都遍历判断，最坏时间可达 $O(N\log n)$ 。

课堂练习

[[0, 1], [1, 0]] 的嵌套表示是什么？共有几个节点？
4×4全为1的网格，输出树有几个节点？完整实现是否只读一个像素？
4×4交替0、1的棋盘格会产生几个叶子和内部节点？
区域查询公式为何要最后加回左上重叠部分？

参考答案

[0, 1, 1, 0]；共有5个节点，其中1个内部节点、4个叶子。
一个叶子。完整实现仍检查并处理16个像素，建立前缀和后根查询即可停止构建。
16个单像素叶子，5个内部节点，共21个节点：1个根、4个2×2区域节点、16个叶子。
减去上方与左方区域时，左上重叠区域被减去了两次，应加回一次，才能恰好得到目标区域的和。