兵工自动化 测控技术 O. I. Automation 2004 年第 23 卷第 6 期 Measurement and Control Technique 2004, Vol. 23, No. 6 文章编号：1006-1576（2004）06-0063-02 基于四叉树的图像分割技术 宋宇彬，张秉权，郝永平 （沈阳理工大学 计算机系，辽宁 沈阳 110168） 摘要：基于四叉树的图像分割法将场景空间按 X/Y 方向分割成 4 个子方格组成空间四叉树，以分辨率对图像编码， 实现不同层次间图像多分辨率及平移、旋转等变换，细化图像的不同层次。采用兄弟线索化存储结构，把 Buffer 颜色索 引赋值到四叉树节点，以存取 BMP 颜色，显示 BMP 文件。同层节点通过兄弟指针访问，不同层次节点用后代指针访问。 关键词：四叉树；图像分割；线索化；图像编码 中图分类号：TP391.41 文献标识码：A Quad-Tree-Basing Structure Image Segment Technology (Dept. of Computer, Shenyang University of Science & Technology, Shenyang 110168, China) SONG Yu-bin, ZHANG Bing-quan, HAO Yong-ping Abstract: Whole scene space was divided into 4 child-segments with image segment method based on Quad-tree structure along direction of the x-axis/y-axis, thereby constructs the stereo Quad-tree. The image was coded according to resolution ratio, and multi-resolution transform, position transform, image thinning and rotation transform of image between different distinct layers was implemented. The color index was stored into the nodes of Quad-tree to record the BMP color information and display the BMP file by using store construction of the brother clue. The nodes in the same layer were accessed by brother point, and the nodes in different layer were accessed with the offspring point. Key words: Quad-tree; Image segment; Thread; Image coding 1 引言 图像识别和编码由于计算量大，至今不能在中 低档工作站及微机上实现实时动态绘制。基于四叉 树的图像分割比基于区域的分割速度快，保持图像 细节更优越，在分割结束同时可获得目标大小、边 缘和个数。故采用四叉树对图像快速分割和操作， 并给出用四叉树对小车图像层次化的对比图。 2 四叉树的构造与图像存取显示 2.1 空间四叉树剖分技术 空 间 四 叉 树 算 法 是 一 个 空 间 均 匀 网 络 剖 分 算 法，该算法将含有整个场景的空间按 x、y 方向分割 成四个子方块网格，组织成一棵四叉树。若某一子 方块网格中所含的景物大于给定阈值，则对该子方 块网格做进一步剖分。如此递归直到四叉树的每一 叶子节点子方块所含景物均小于给定的阈值为止。 图 1 给出了一场景的四叉树剖分。 1 4 2 3 图 1 四 叉 树 剖 分 图 2.2 四叉树的数据结构及其编码（图 2） (1) 四叉树的数据结构 Root Node N=0 C[0] C[1] C[2] C[3] N=1 C[0] C[1] C[2] C[3] C[0] C[1] C[2] N=2 C[3] 图 2 四 叉 树 的 数 据 结 构 （N 为 层 数 ） 四叉树的存储，一种把整棵四叉树线索化，另 种让同层兄弟线索化。由于本次任务主要对图像进 行不同层次细化，故选择同层兄弟线索化的存储结 构。四叉树叶子表示所需的结点数与四叉树的 4 的 深度 4 次方成正比。即 N∝4 的（Depth-1）次方， 其中 N 为叶子结点总数，Depth 是四叉树的深度。 四叉树需记录颜色位置 X、Y（int 型），层次 信息 Level（int 型），颜色 color 信息，指向下一个 兄弟 next 指针，4 个孩子指针 Children[4]。如图 3。 四叉树的数据结构： typedef struct tQuadTree { int color; //RGB 颜色索引值; int level; //当前四叉树深度, 根节点 level=0; int x; //象素的横坐标; int y; /象素的纵坐标; tQuadTree *next; //指向兄弟节点的指针; tQuadTree *Children[4]; //每节点有四个指向子节点的指针; } QuadTree,*pQuadTree; 收 稿 日 期 ： 2004-06-07； 修 回 日 期 ：2004-08-31 基 金 项 目 ：CAD/CAM 网 络 化 协 同 设 计 （42001080501） 作 者 简 介 ： 宋 宇 彬 （1980-）， 男 ， 广 东 人 ，2002 年 南 京 理 工 大 学 毕 业 ， 现 沈 阳 工 业 学 院 在 读 硕 士 生 ， 从 事 计 算 机 网 络 研 究 。 ·63· 

兵工自动化 测控技术 O. I. Automation 2004 年第 23 卷第 6 期 Measurement and Control Technique 2004, Vol. 23, No.6 Color Level X Y Next Children[0] Children[1] Children[2] Children[3] 图 3 四 叉 树 记 录 颜 色 表 示 法 TC2.0 下 int 型数据需要 2 个字节，每个指针 也需要 2 个字节，故每个结点需要 20 个字节，一棵 6 层的树需约 1 兆的存储空间。一棵 6 层的四叉树， 其叶子结点最多能记录 4 的（Depth-1）次方个颜 色信息，即 1024 个颜色信息，也即一幅 32×32 的 BMP 图片信息。当层次提高时，所需存储空间将以 4 的倍数增长，将造成 TC2.0 的内存不足。经编程 测试，不采取别的措施，TC2.0 最多能生成一棵 7 层的四叉树，即最多能显示一幅 64×64 图片。 (2) 四叉树结点的访问 四叉树的结点访问分为同层结点和不同层结点 的访问。不同层结点可通过后代结点指针 Children 来访问，同层结点的访问可通过兄弟指针 next 来访 问。如果从根结点开始查找某一结点，可先找到相 应层的最左结点 Children[0]，然后通过它的 next 指针找到所需要的结点。同一层次的结点操作通过 next 指针完成，几种节点的访问方式如图 4～6。 Level=0 Next Level=0 Next … Level=n Next 图 4 同一层次结点的访问 Level=0 Children[0] Level=1 Children[0] … Children[0] Level=n 图 5 不同层次结点的访问 Level=0 Children[0] Next Level=1 Children[0] Next …… Level=n Children[0] Next … Level=n Children[0] Next 图 6 任意结点的访问 3 用四叉树实现 BMP 图像的存取和显示 3.1 用四叉树存取 BMP 颜色信息 从 BMP 文件一次性读出的颜色索引值全部存 放在 Buffer，要求空间较大，一幅 32×32 的图像 需要 1024 个单元，64×64 的图像要 4096 个单元， 当图像大小达 250×250 时要 64K 个单元。在 TC2.0 下，最大可用的内存是 64K，即图像大小不能超过 256×256，考虑到构造树和其他需要内存的操作， 实际的图像不能超过 256×224。上述的问题虽可通 过多次读入 Buffer 解决，但由于本程序需要对整图 进行操作（旋转，平移等），这些操作都是基于 Buffer 进 行 的 ， 故 要 求 整 幅 图 像 的 颜 色 信 息 都 应 该 在 Buffer 里，而不应该每次从图像文件读入部分的颜 色值存入 Buffer 中。 完成了图像文件中颜色信息到 Buffer 的输入 后，就把 Buffer 里的颜色索引值赋到四叉树叶子结 点中。为每个结点都赋了位置信息，根据位置信息 可找到 Buffer 里对应的颜色信息。叶子结点里的位 置 信 息 是 (X,Y) ， 那 么 它 所 对 应 的 颜 色 信 息 就 是 Buffer[Y*width＋X-1]。 读出来的 BMP 图像信息只是 RGB 颜色在调色 板 中 的 索 引 值 ， 显 示 图 像 还 需 要 把 索 引 值 转 化 成 RGB 颜色显示，这可通过查找调色板来实现。 3.2 用四叉树显示 BMP 文件 四叉树显示 BMP 文件就是把四叉树所有叶子 结点的颜色信息在相应的位置（X，Y）中显示出来。 如果采用一次性把 Buffer 里的颜色赋进树里， 对于一幅 64×64 的图需要一棵 7 层的四叉树，试验 得出 TC2.0 下最多能生成一棵 6 层的四叉树。解决 的办法是生成一棵 6 层的四叉树，不断改变四叉树 的颜色和位置信息来达到更大图像的显示。如图 7。 32×32（2） 32×32（1） 32×32（4） 32×32（3） 图 7 64×64 的 一 幅 图 像 一幅 64×64 的图像可划分成 4 个 32×32 部分。 先把(1)的位置赋入四叉树中并显示，然后改变四叉 树的颜色和位置信息为(2)并显示，(3)，(4)部分进 行同样的操作，就可用一棵 6 层的四叉树实现较大 图像的显示。不同层数显示同一图像的效果如图 8。 6 层 4 层 3 层 ·64· 图 8 不同层四叉树显示图像的效果 （下转第 69 页） 

兵工自动化 测控技术 O. I. Automation 2004 年第 23 卷第 6 期 Measurement and Control Technique 2004, Vol. 23, No. 6 口大容易产生虚警，太小又会漏检，因此合适的小 窗口对检测效果也是很重要的。 4 结论 小模板小波变换算法，计算速度快，可有效检 测信噪比小＜3 的小目标。从各原始图像的灰度曲 面图上，几乎看不到很弱的小目标频谱。该方法对 小目标图象，在目标处都有明显的尖峰，从信噪比 （表 1）中也可看出信噪比有较大程度的提高。当 小目标图象的信噪比稍小时，本小波变换滤波法得 到的图像中非零的尖峰也较多，对应目标所在的位 置尖峰也明显高出很多，方便检测小目标。 参考文献： [1] Donoho D L. Denoising by Soft-Thresholding [J]. IEEE Trans. Inf. Theory, 1995, (41): 613-627. [2] 李强, 王正志. 基于小波分析的噪声抑制和数据压缩综 合技术－SAR 图像的噪声抑制与数据压缩[J]. 系统工 程与电子技术, 1998, (12). [3] Donoho D L. Wavelet Shrinkage, W.V.D -A Ten- in Wavelet Analysis and Minute Tour. Progress Application [Z]. 1993. [4] 程正兴. 小波分析算法与应用[M]. 西安: 西安交通大学 出版社, 1998. [5] Stephane Mallat. 信号处理的小波导引（第二版）[M]. 北京: 机械工业出版社, 2002. [6] 亓兰秋, 阮文. 基于小波变换的红外动目标检测[J]. 红 外与激光工程, 1997, 27: 209-211. [7] 陈明奇, 娄国伟, 李兴国. 小波变换在毫米波雷达目标 识 别 中 的 应 用 [J]. 红 外 与 毫 米 波 学 报 , 1998, 17: 308-312. [8] 汪敏, 李兴国. 复杂背景下毫米波雷达目标识别的一种 方法[J]. 系统工程与电子技术, 1997, 19 (12): 29-33. ******************************************************************************************************* 欢迎广大读者订阅 欢迎各位作者赐稿 欢迎商家广告惠顾 ******************************************************************************************************* （上接第 62 页） 确定线性回归方程是否有实用价值，通常相关 系数检验法和方差分析检验法。用相关系数检验法 来检验回归方程。首先求出相关系数 γ xy yy γ＝ SS xx (7) S 由式(7) 求得相关系数 γ＝0.9292。查相关系数 的临界值表，可知，对于 n＝4，置信水平 α＝0.05， γ0.05＝0.900。比较 γ 与 γ0.05，知 γ>γ0.05，说明 DO 和 COD 之间存在线性相关关系，从而说明确立的 回归方程是有意义的。 4 结论 实验和理论分析表明，好氧曝气池中溶解氧在 线模糊控制系统具有 MSBR 工艺的全部优点，具有 较高的自控水平。由于对好氧曝气池和两个 SBR 池 的溶解氧均采用模糊在线控制，使得溶解氧始终保 持在最佳范围，避免了氧不足或者浪费。本实验系 统可连续在线监测 DO 大小，并可在上位机上得到 相应的变化曲线，有利于实时研究 DO 的变化和各 指标之间的关系，实施有效控制。 参考文献： [1] 张 化 光, 何 希 勤 , 等. 模 糊 自 适 应 控 制 理 论 及 其 应 用 [M]. 北京: 北京航天航空大学出版社, 2002. [2] 赵忠富, 付忠志. 污水 MSBR 系统工艺设计[J]. 给水排 水, 2000, (11): 6-9. [3] 张统. 间歇式活性污泥法污水处理技术及工程实例[M]. 北京: 化学工业出版社, 2002. （上接第 64 页） 4 结论 在 BMP 图像四叉树表示基础上的图像分层次 表示和旋转变换方法，对分块显示大图像有效，更 大的图像因一次性读入的 Buffer 太小而无法处理。 因此，通过四叉树对图像的分割得到图像物体的大 小，提取物体的个数边缘等，是今后研究的目标。 参考文献： [1] 崔 屹. 数 字 图 像 处 理 技 术 与 应 用[M]. 北 京: 电 子工 业 出版社, 1997. [3] Kenneth R Castleman. 数字图像处理[M]. 朱志刚, 等 译. 北京: 电子工业出版社, 1998. [4] 杨崇源, 张继贤, 林宗坚. 虚拟地形场景绘制中的实时 LoD算法[J]. 测绘学报, 2001, 30 (2): 133-138. [5] TC256. TC 下 如 何 实 现 256 色 显 示 [DB /OL]. http://www.tc256.com/, 2002. [6] R Koch. Dynamic 3-D Scene Analysis through IEEE Pattern Synthesis Feedback Control Analysis and Machine Intelligence, 1993, 15 (6): 556-568. [J]. [7] H Li P. Roivainen R Forchheimer. 3-D Motion Estimation in Model-Based Facial Image Coding [J]. IEEE Pattern Analysis and Machine Intelligence, 1993, 15 (6): 545-555. 金鸡引项 新年吉祥 ·69·