图像分析的数据结构是《图像处理、分析与机器视觉》第四版里最容易被低估的一章。我第一次翻这本书时注意力全在滤波、边缘检测和分割算法上觉得数据结构无非就是把像素存进数组。直到动手实现分割结果的区域关系分析时才发现数组能表示的只是每个点的灰度值而图像经过分析之后产生的区域归属、邻接关系、多尺度层级都需要专门的数据结构来承载。这篇文章是我把这章重新过了一遍之后的整理笔记覆盖金字塔、四叉树、区域邻接图和边界编码这几类核心结构重点说清楚每个结构的适用场景和设计动机给同样在啃这本书的读者一个可以对照的参考。1. 为什么数组不够用存储像素和承载关系是两回事1.1 教材对数据结构的分层框架这本书在讲图像分析之前先把数据结构按表达层次理了一遍。我当时没细看就跳过了后来补课时发现这个框架其实是整章的骨架。大致分四层图标层iconic level最接近原始图像包括二维数组、矩阵、二值模板。滤波、增强这类操作主要在这一层做。分割后图标层每个像素的值不再是灰度而是区域编号也就是标签数组。这是分割算法输出的标准形态。几何层geometric level链码、多边形、边界描述用来表达区域的轮廓和形状。关系层relational level区域邻接图、包含关系树、语义网络表达的是区域和区域之间是什么关系。这其实是一条从像素视图到语义视图的链条。低层操作只要管像素值高层分析和识别则越来越依赖几何层和关系层。教材把这一章放在分割章节之前就是为了让你在学算法之前先有用什么结构装结果的意识。1.2 数组表达不了的三个典型问题用二维数组表示图像能轻松回答第i行第j列的像素值是多少但分析任务里更常问的是另外三类问题这个区域和哪个区域相邻数组本身不含邻接信息答案是遍历一遍边界像素才能算出来的。这块区域的边界长度和曲率是多少数组里没有边界这个概念需要先做边界提取。缩小分辨率后这块均质区域是不是仍然均质数组是单分辨率的没法直接回答跨尺度问题。我做过一个连通域标注练习最初就是用数组硬扫。每标注完一个区域要判断它是否和另一个区域相邻就得重新遍历整幅图数据量稍微大一点性能就惨不忍睹。后来把分割结果转成区域邻接图运行时间从分钟级降到了秒级。这个对比让我对数据结构服务于分析任务这句话有了非常直观的体会。1.3 学这一章的正确姿势这一章不是教你怎么写代码而是教你拿到一个图像分析任务时先想清楚我要对图像的什么特征做查询再决定用什么结构。顺序搞反了后面写再多代码都是在补窟窿。书里反复强调数据结构的选型取决于下游任务而不是取决于图像本身长什么样。2. 金字塔与四叉树两种层次结构的设计动机与构建细节2.1 金字塔是怎么搭起来的金字塔的核心思路是做多分辨率表达。原始图放在最底层往上每一层分辨率减半直到只剩一个像素。每一层都是对下一层的抽象。教材里重点提了两种金字塔。M-金字塔均值金字塔把相邻2×2像素求平均作为上一层对应位置的值。T-金字塔元组金字塔把2×2像素的组合模式编码成一个新的取值保留的信息比单纯求均值更丰富但构造规则也更复杂。以512×512图像为例逐层往上256×256128×128……直到1×1。总存储量是 512²256²128²…1²这是个等比数列求和结果约等于原始图像的4/3。也就是说金字塔带来的额外存储开销只有33%左右工程上完全可以接受。实际构建时有个容易被忽略的细节如果图像尺寸不是2的幂逐层减半到后来会出现无法整除的情况。教科书默认图像尺寸规整但实际数据几乎不会这么听话。我的处理办法是在降采样前做padding把尺寸补齐到2的幂再构建金字塔分析完再映射回原始坐标。2.2 四叉树的构建细节四叉树的构建是自顶向下的分裂过程当前块如果不满足均质条件就分裂成四个子块子块仍不满足就继续分裂直到所有叶子节点都是均质块。这里的均质是个参数可以用灰度方差小于阈值、灰度极差小于阈值或者分类后标签一致来定义。阈值设得大树浅、节点少阈值设得小树深、更贴近像素级细节。举个8×8二值图的例子左上4×4块全为0右下4×4块一半是0一半是1。若定义块内标签一致才算均质左上块直接成为叶子节点右下块继续分裂成四个2×2子块其中两个子块标签一致成为叶子另外两个继续分裂到1×1。四叉树的节点定义很直接class QuadtreeNode: def __init__(self): self.children None # 叶子节点为 None self.value None # 叶子节点的区域标签或灰度均值 self.bounds None # 该节点对应的图像区域范围 def is_leaf(self): return self.children is None叶子节点存区域标签内部节点不存值只存四个子节点的引用。这个结构在内存上的特点是图像越均匀节点越少省得越多。2.3 金字塔和四叉树到底怎么选维度金字塔四叉树构建方式固定逐层降采样与内容无关内容自适应分裂存储量恒为原图的4/3取决于图像复杂度全均质图极少节点多尺度查询直接访问各层O(1)需沿树路径搜索O(log N)均质块定位不直接支持天然支持典型场景多尺度特征提取、模板匹配均质区域检测、大图快速索引我在实际项目里通常这么选下游算法需要在多个分辨率上做检测直接用金字塔省掉重复降采样的代码任务是找图像里哪些块是均质的或者要对超大尺寸图像做预筛四叉树更合适。四叉树的构建成本是O(像素数)这个开销一次付清后续查询都能受益。3. 区域邻接图与链码把分割结果转成可查询的关系3.1 RAG的构建与查询图像分割完成后得到的是一张标签数组。**区域邻接图Region Adjacency GraphRAG**把每个区域当作节点两个区域如果共享边界像素就在节点之间加一条边。构建RAG的做法很朴素遍历标签数组检查每个像素和它的右邻、下邻如果标签不同就在这两个标签对应的区域之间建立邻接关系。复杂度是O(像素数)非常划算。关键点是去重——同一对区域可能通过很多边界像素被重复发现用集合记录边或者用上三角矩阵标记。有了RAG之后区域A与区域B是否相邻就成了一次图的边查询而不是整幅图像的遍历。分割后的目标筛选场景里这个优化极其明显。我做卫星影像地块分析时分割出几百个地块要找出与某个特定地块相邻的所有地块RAG构建好后查询是毫秒级用数组扫描则要遍历整幅影像。def build_rag(label_image): import collections edges set() h, w label_image.shape for i in range(h): for j in range(w): cur label_image[i, j] if i 1 h: down label_image[i 1, j] if cur ! down: edges.add((min(cur, down), max(cur, down))) if j 1 w: right label_image[i, j 1] if cur ! right: edges.add((min(cur, right), max(cur, right))) return edges这段代码构建的边集合就是RAG的核心。后续要算每个区域的面积、均值等属性可以同步遍历一遍标签数组统计。3.2 链码边界压缩与形状描述链码Freeman链码用8个方向码表示边界的跟踪路径。从边界起点开始每一步的移动方向用0~7编号0表示向右1表示右上以此类推顺时针转一圈。一段边界的链码就是一个方向码序列。链码的价值在于紧凑一段几百像素的边界可以用几十个字节描述而且基于链码可以直接计算周长偶数方向码步长1奇数方向码步长√2、曲率变化和形状矩。但是链码有三个需要处理的坑。第一起始点位置不同链码序列就不同。第二旋转一个角度后链码整体偏移。第三缩放会改变步长。工程上常用的做法是循环归一化把链码看成循环序列在环形移位中取字典序最小的那个作为标准形式。我做形状匹配测试时物体一旋转就匹配失败查了一晚上才发现是起始点没有归一化全是链码起点的锅。3.3 从原始图像到关系结构的完整链路一幅图从灰度图变成可分析的关系结构完整链路是这样的灰度图 → 分割算法 → 标签数组 → RAG 区域特征统计标签数组这一步容易被跳过我建议保留它作为中间产物。很多区域特征——面积、灰度均值、纹理统计——都要靠标签数组计算而不是靠RAG。RAG擅长回答谁和谁相邻但不擅长回答某个区域的内在属性。两者配合才是完整的分析底座。4. 空间代价与查询效率三种结构的工程权衡4.1 同一张图三种结构各占多少空间以256×256图像为例粗略估算各结构的元素数量结构元素数量说明二维数组65 536每个像素一个元素金字塔约87 381原图的4/3四叉树覆盖全图的均匀图像1个叶子最坏情况约4/3取决于内容复杂度RAG区域数 边数典型分割结果只有几百到几千个节点和边四叉树有个反直觉的结论它不是任何时候都省内存。如果图像是随机噪声每个1×1块都独立树节点数会接近4n²/3再加上指针开销比数组还要费内存。它是为存在大片均匀区域的图像优化的。分割后的图像恰好有这个特征——每个区域内部标签一致天然适合四叉树表达。这也是为什么教材会把四叉树和分割放在同一个分析框架里讲。4.2 查询模式决定选型我梳理了四种最常见的查询类型和对应的最优结构点查询这个像素的值是多少数组毫无疑问最快一次索引定位。均质块查询这块区域内部是否一致四叉树能跳过大量内部像素只沿树路径做判断。多尺度查询不同分辨率下的表现金字塔各层直接对应不用重新降采样。邻接关系查询两个区域是否相邻RAG构建一次查询无数。举一个卫星影像的例子。分析超大尺寸影像时首先要做的是把目标区域从大量背景中筛出来。用四叉树把影像分成不同粒度的块空白块直接跳过只对嫌疑块做精细推理。这个先粗筛后细查的模式用数组实现代码复杂度会高得多而且性能差一个数量级。4.3 现代工具库里的隐性结构很多图像处理库不直接暴露四叉树或RAG这样的类名但概念以不同形式藏在API里。OpenCV的findContours返回的层级结构本质上是一棵森林connectedComponentsWithStats输出的就是标签数组加区域统计SLIC超像素的邻接信息底层就是一个图。理解了教材这一章再看这些API的输出结构会有一种原来如此的感觉。学习时不妨把课本概念和库函数对应起来印象会深很多。5. 四个常见混淆点和一套自测方法5.1 坑一把四叉树当成分割算法四叉树是表示结构不是分割算法。分割算法依据灰度、纹理等特征把像素归类到不同区域四叉树是在给定均质判定规则后把图像组织成层次树。两者可以配合使用——分割结果可以指导四叉树的均质性判断——但概念上不能混。考试和面试经常拿这个做区分点。5.2 坑二金字塔的层次方向搞反有的同学会把金字塔最顶层当作原始图像。方向搞反的直接后果是代码里索引错乱最后得到一堆毫无意义的数据。建议记忆方式原始图是金字塔的底层层号从底向上递增顶层是1×1的汇总像素。多数教材的插图都是底面朝下层号从下往上数。5.3 坑三RAG是图不是树RAG允许环的存在——三个区域两两相邻就构成一个三角环。因此遍历RAG时必须使用图的访问标记而不是树的递归遍历。直接用树的DFS去跑RAG如果不加visited集合大概率无限递归。这个bug我在代码里见过不止一次排查时往往要花不少时间才能意识到是结构性质的问题。5.4 坑四链码归一化只做了位移没做旋转归一化链码的旋转归一化不只是简单地把起点改一下。旋转45度每个方向码加1模8旋转90度加2。要做完整的形状匹配必须把方向整体偏移和循环移位同时考虑才能保证旋转不变性。我踩过这个坑后养成了习惯写链码相关代码前先想清楚这个特征在旋转、缩放、平移下分别是否不变。5.5 自测三问学完这一章能答上下面三个问题说明核心掌握了一个512×512灰度图构建均值金字塔总存储量约是多少——512²×(4/3)约等于35万个像素单位。同一图像构建RAG节点数的理论上限是多少——由分割区域数决定不超过像素总数实际远小于。链码旋转45度后每个方向码变化多少——整体加1模8归一化应按循环最小字典序处理而不是直接减固定值。这三个问题分别对应层次表示的空间代价、关系表示的数据规模、几何表示的变换不变性正好覆盖这一章的核心内容。这本书的数据结构章节我前后读了不止一遍每次都有新收获。第一次是补齐概念第二次是配合代码实现第三次是在实际项目中用上RAG之后回来看理论才真正理解为什么教材把这章放在分割算法前面。我的建议是不要把这章当纯理论背每学一个结构就追问自己这个结构能回答什么查询不能回答什么查询带着问题去读收获会大得多。最后留一个小提示如果你正在学这一章花一个周末实现一个四叉树构建函数输入一副分割后的标签图输出四叉树的可视化结果。这个练习比任何笔记都管用。