AV1编码块点查询的高效数据结构构建与块重构问题

给定如下格式的数据，如何采用最高效的表示方式实现像素点所属编码块的快速查询？

我需要将视频帧的AV1编码块解析为某种数据结构，以快速查询任意像素点所属的编码块。仅有的信息是一个2D数组，每个(x,y)位置的元素表示起始于(4x,4y)的4x4块所属的编码块尺寸（该数组为原帧4x4下采样结果），但未知编码块的起始位置（信息来自libaom库）。最终编码块由视频编码器通过对固定尺寸（64x64或128x128）的超级块进行递归分割生成，分割类型为AV1规定的10种类型之一。

我尝试将问题拆分为两步：

1. 基于该数组信息重构编码块，得到每个块的(x,y,width,height)参数；
2. 构建数据结构/算法存储空间相邻的块，实现快速点查询。

问题1：块重构 #

最初尝试DFS，将当前块的3个角点作为下一个潜在块的起始位置，但会出现错误地添加小块而非正确大块的情况；BFS也存在类似问题。
随后采用基于优先队列的BFS，优先选择y坐标最小的块，y相同时选择x坐标最小的块，但有时会生成重叠的非法分区；而使用曼哈顿距离的优先队列则能正常工作，但无法理解原因，希望得到原理性解释。

问题2：点查询优化 #

我提出两种非最优方案（n为帧内块数量）：

• 线性搜索：遍历所有块判断点是否在内部，预处理O(1)，查询O(n)；
• 二分搜索：先按x坐标排序块，查询时找到最大的<=查询点x坐标的块，再筛选符合条件的块，预处理O(nlog(n))，查询O(ceil(frameHeight/4))。
  尝试过四叉树、线段树等树形结构，但受非正方形分割和非矩形区域限制无法实现，希望获得更优方案。

样本数据：JSON格式的样本帧数据中，blockSize数组的每个元素对应(4x,4y)起始的4x4块所属编码块的尺寸标识，如(0,0)的标识6对应16x16的编码块。

一、块重构的原理与正确实现 #

为什么曼哈顿距离优先的BFS能工作 #

AV1编码块的分割逻辑是从超级块（64x64/128x128）开始递归向下拆分，所有块都对齐到超级块边界，且同一编码块内的所有4x4子块，尺寸标识完全一致。

普通BFS/DFS出错的核心原因：你选的“潜在块起始位置”可能已经属于某个更大的块，导致误将小块当成独立块创建。而曼哈顿距离（从超级块左上角(0,0)计算x+y）优先的队列，本质是优先处理更靠近超级块左上角的块——AV1的分割规则中，大块必然从超级块或其父块的左上角起始，先处理这些位置的块，就能先标记它覆盖的所有4x4子块为已访问，后续遇到这些子块时直接跳过，不会再创建重复或错误的小块。

而按y最小、x最小排序的队列有时出错，是因为这种排序可能先处理同一行右侧的块，但右侧的块可能属于左侧一个跨列的大块，提前创建小块会导致后续大块与它重叠冲突。

正确的重构步骤 #

1. 按超级块尺寸（64x64或128x128）划分整个帧，每个超级块独立处理；
2. 为每个超级块初始化一个已访问标记矩阵，记录4x4子块是否已被归属到某个编码块；
3. 使用优先队列（按曼哈顿距离x+y从小到大排序），初始将超级块的左上角（对应超级块内的相对坐标(0,0)）加入队列；
4. 取出队列头部的(x,y)，若该4x4子块已被访问，直接跳过；
5. 从blockSize数组获取该位置的块尺寸标识，转换为对应的4x4子块数量S（比如标识6对应16x16块，即S=4，因为16/4=4）；
6. 计算该编码块覆盖的4x4子块范围：从(x,y)到(x+S-1, y+S-1)；
7. 检查该范围内所有4x4子块的尺寸标识是否均为当前值（AV1编码块的核心约束：块内所有子块标识一致），若一致则创建编码块（转换为原像素坐标：x4, y4, S4, S4）；
8. 标记该范围内所有4x4子块为已访问；
9. 将该编码块周边未被访问的4x4子块左上角加入队列；
10. 重复步骤4-9直到队列为空。

二、点查询的高效实现方案 #

方案1：行级区间索引（平衡内存与查询效率） #

利用视频帧逐行分布的特性，构建行级块索引：

• 预处理：
  1. 按4x4子块的行（对应原帧每4行），为每一行创建一个区间数组row_blocks[y]；
  2. 数组元素为三元组(start_x, end_x, block)，表示该行中从start_x*4到end_x*4-1的x坐标范围属于该编码块；
  3. 对每个row_blocks[y]的三元组按start_x排序。
• 查询：
  1. 将查询点(px, py)转换为4x4子块坐标：x = px // 4，y = py // 4；
  2. 在row_blocks[y]中用二分查找找到第一个start_x <= x且end_x > x的三元组，对应的block即为结果。
• 复杂度：预处理O(n)，查询O(log K)（K为该行的块数量，远小于n）。

方案2：像素级映射数组（最快查询速度） #

如果内存允许，直接构建与原帧尺寸一致的映射数组：

• 预处理：创建一个和原帧像素尺寸相同的2D数组pixel_to_block，每个位置存储对应像素所属编码块的引用或索引；
• 查询：直接通过pixel_to_block[py][px]获取结果，查询时间O(1)；
• 优缺点：查询速度最快，内存占用可接受（比如1080P帧仅需约8MB内存）。

方案3：超级块四叉树（适配AV1分割逻辑） #

AV1的所有分割块都是矩形，且基于超级块递归拆分，可构建超级块级四叉树：

• 预处理：每个超级块作为根节点，根据其实际分割类型（垂直二分、水平二分、四等分等）构建子节点，叶子节点对应最终编码块；
• 查询：先定位查询点所属的超级块，再递归遍历该超级块的四叉树，判断点属于哪个子节点，直到找到叶子节点（编码块）；
• 复杂度：预处理O(n)，查询O(log S)（S为超级块尺寸，比如128x128仅需约5层递归）。

内容的提问来源于stack exchange，提问作者LeoMinor