数据结构案例教学—二叉树在图像分割中的应用

刘国英，王煜龙，陈双浩

(安阳师范学院 计算机与信息工程学院，河南 安阳 455002)



数据结构案例教学
—二叉树在图像分割中的应用

刘国英，王煜龙，陈双浩

(安阳师范学院 计算机与信息工程学院，河南 安阳 455002)

[摘要]数据结构是计算机相关专业的核心基础课。掌握数据结构有关知识对学生进一步学习后续课程起着至关重要的作用，有助于提高学生设计复杂软件的能力。然而，传统的教学方法过于强调抽象数据类型的定义及对应的实现方法，而使得让学生觉得枯燥和困难。本文以二叉树在图像分割中的应用为案例，利用最优二叉树的性质、二叉树的遍历方法等知识点，设计图像分割算法，并进行了简单分析。教学实践表明，数据结构的案例教学比传统教学更能提高教学质量。

[关键词]数据结构;二叉树;图像分割;案例教学

数据结构是计算机及相关专业的一门核心课程，对学生深入学习计算机专业知识具有至关重要的作用。二叉树作为一种应用极其广泛的数据结构，是学生必须掌握的一个知识点。然而，该结构相对线性结构更加抽象和复杂，常用教材中采用的案例非常少，这对学生理解产生巨大障碍。虽然有教师设计了不同的案例方法[1]，但仍然显不够。

当前，多媒体智能信息处理技术一直引领计算机学科的发展。其中，图像分割是图像及视频信息处理的一个基础研究课题，在遥感、农业、军事等领域应用非常广泛。图像分割技术的深入研究对数据结构理论体系的发展和应用提出了更高的要求。很多人在图像分割领域进行了研究[2-5]。因此，为了拓展学生的知识面，提高学生学习的热情，本文以图像分割为背景，设计数据结构中二叉树的案例教学方法。

1基本知识

1.1图像分割与二叉树结构

对图像分割的研究一直是图像处理中的重点和热点[2]。图像分割的目的是将图像划分为互不重叠的图像区域，并要求图像区域内部的像素具有相同的属性，比如颜色和纹理。在图像分割中，获得的图像区域个数就成为图像的类别数。

二叉树是指树种任一结点的度小于2的树，即任一结点最多有两棵子树，并且二叉树的子树有左右之分，其次序不能颠倒[6]。这表明二叉树或为空，或为一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。这两棵子树也是二叉树。因此，二叉树是递归定义的。因为二叉树不同子树上的节点是互不相交的，这与图像分割中各个分割区域之间互不重叠的要求是一致的。所以，利用二叉树的性质设计图像分割算法符合该研究问题的特点。

1.2二叉树的遍历

遍历二叉树是指按照某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次[6]。由二叉树的递归定义可知，二叉树是由3个基本单元组成：根节点、左子树和右子树。因此，二叉树的遍历即为按照某种顺序依次访问这三部分的算法。根据根结点的访问次序，有三种二叉树遍历方法：先序遍历、中序遍历和后序遍历。先序遍历是指先访问根节点，再依次遍历左子树和右子树。中序遍历是指先遍历左子树，再访问根结点，最后遍历右子树。后序遍历指先依次遍历左子树和右子树，最后再访问根结点。

本文的案例教学中，在获得图像分割过程所对应的二叉树后，使用先序遍历的方法确定每一结点属于哪个类别，并生成最终的分割结果。

1.3最优二叉树

最优二叉树是指带权路径长度最小的二叉树，又称作赫夫曼树[6]。在该树种没有度为1的结点。因此，一个有n个叶子结点的最优二叉树共有2n-1个结点。因为，在构造最优二叉树后，经常需要从叶子结点出发寻找一条到根结点的路径。比如，赫夫曼编码时需要根据从根结点到叶子结点的路径来确定编码，本文案例教学所用的图像分割实例也需要依据从叶子结点到根结点的路径来确定叶子节点对应像素所在的类别。为此，在最优二叉树的结点结构中，除了包含所需的数据信息外，一般还包含三个指针：父结点指针 、左子树指针和右子树指针。增加父结点指针为访问父结点提供了便利。

2基于最优二叉树的图像分割案例

2.1分割算法设计

假设待分割图像表示为像素集合{Pi|i=1,2,…,N}，其中N为图像的像素个数。为了减少算法处理的数据量，本案例教学设计的分割方法针对灰度图像的256个灰度值进行处理。假设分割的类别数为K，基于二叉树进行图像分割的算法描述如下：

(1) N个像素构成N棵二叉树的集合F={T1,T2,…,TN}，其中每棵二叉树只有一个根节点，其左右子树均为空；

(2) 采用一定的策略，在F中选取两棵树作为左右子树构造一棵新的二叉树；

(3) 在F中删除这两棵树，同时将新得到的二叉树加入F中；

(4) 重复(2)和(3)，直到F中包含的二叉树的个数为K。这时，F中每一棵二叉树对应图像的一个分割区域。对每一棵二叉树执行叶子结点的遍历操作，即可获得对应类别在图像中的真实分割区域。

2.2算法顺序表示与实现

为了运算简便，在执行步骤(2)时，本文采用如下准则进行二叉树选择：两个根结点对应图像区域的灰度均值最接近。为此，在本案例中，我们设计如下的最优二叉树结点结构：

typedef struct{

int rootId; //该结点的存储索引

double meanValue; // 灰度均值

int pixlNumber; //以该结点为根的像素个数

unsigned int parent, lchild, rchild; //父结点、孩子结点在二叉节点列表中的存储位置

}BTNode, *BestBiTree;

对应的森林F存储在结构体数组中，大小为2n-K-1。上述结构体中的三个整形变量表示每一个结点的父结点、左右孩子在结构体数组中的存储单元下标。如果某一结点的父结点为0，表示该结点为树的根结点；F中树的个数表示当前图像的分割类别数。因此，构造最优二叉树的过程就是图像分割的过程。图像分割的算法实现如下：

void BestTreeSegmentation(double *pImage, double *pSegmentation, int width, int height, int K)

// pImage为指向灰度图像数据的指针， pSegmentation为分割结果指针

// width和height为图像的高和宽，K为图像的分类个数

{

if (K<2) return;

if(pSegmentation==NULL) return;

int n = 256;// 图像灰度级的总个数

//统计每一灰度级出现的频度, gFred[i]为灰度gId[i]在图像中出现的次数

[gFreq, gId] = imgHist(pImage, width, height);

// 统计每一灰度级对应的像素集合, pxlSet[i]为灰度级gId[i]对应的像素位置集合的指针

pxlSet = GetPixelSet(pImage, gId, width, height);

int m = 2*n-1-K; // 获取最终分割结果时，F中总共的结点个数

Forest = (BestBiTree)malloc(m*sizeof(BTNode));

double disMatrix[m][m]; // 根结点距离矩阵，取值越小，树的灰度越接近

for(i=0; i

Forest[i].parent = 0;

for(j=0;j

disMatrix[i][j] = Inf;

}

}

for(i=0;i

Forest(i) = {i,gId[i],dFreq[i],0,0,0};

for(j=i+1;j

disMatrix[i][j] = abs(gId[i]-gId[j]);// 计算初始的相似度取值

}

// 创建Forest中的每棵二叉树

for(i=n;i

//选择根结点灰度值最接近的两棵树tree1，tree2

[tree1, tree2] = selectTree(Forest, disMatrix, i);

Forest[tree1].parent=Forest[tree2].parent = i;

Forest[i].pxlNumber = Forest[tree1].pxlNumber+Forest[tree2].pxlNumber;

Forest[i].lchild=tree1; Forest[i].rchild = tree2;

Forest[i].rootId = i;

Forest[i].meanValue = (Forest[tree1].pxlNumber* Forest[tree1].meanValue

+ Forest[tree2].pxlNumber* Forest[tree2].meanValue )/Forest[i].pxlNumber;

// 更新disMatrix取值

for(j=1;j

disMatrix[j][i] = abs(Forest[j].meanValue-Forest[i].meanValue);

}

}

//从构造的二叉树森林中获取分割结果

cls = 1;

for(i=0;i

if(Forest[i].parent==0)//节点i为树根

InitSet(leavesSet);//将叶子结点集合leavesSet初始化为空集合

PreOrderTrevers(Forest,i,leavesSet);//先序遍历获得叶子结点集合

setNumber = Length(leavesSet);// 获得集合大小

InitSet(treePixelSet);// 初始化一个空的集合，用来存储像素的索引

for(j=0;j< setNumber;j++){

//合并同一棵树的叶子结点对应的像素索引集合

treePixelSet = union(treePixelSet, pixelSet[leavesSet[j]]);

}

// 将pSegmentation中的在treePixelSet中的像素索引位置均设为cls

setValues(pSegmentation, treePixelSet, cls);

cls++;

}

}

先序遍历算法的伪代码如下：

void PreOrderTravers(BestBiTree Forest, int root, int * &pixelSet)

{

if(Forest[root].lchild==0 && Forest[root].rchild==0)

pixelSet = union(pixelSet, Forest[root].rootId);

else{

PreOrderTravers(Forest, Forest[i].lchild, pixelSet);

PreOrderTravers(Forest, Forest[i].rchild, pixelSet);

}

}

2.3案例算法运行结果

为了检验案例算法的分割效果，在教学过程中我们选用一幅大小为256*256的全色遥感影像进行算法测试。实验中，我们设定类别数K=6，对应的分割结果如图1所示。分割结果使用彩色表示是为了增加不同类别之间的视觉差别。从图中可以看出，使用二叉树结构进行图像分割能够完成图像分割所要求的功能。

(a)　　　　　　　　　　　　　　　　　(b)图1 案例算法运行结果 (a)待分割图像; (b) 分割结果

该分割算法只考虑了像素灰度值之间的大小关系，没有考虑任何的空间信息。因此，分割结果中存在较多的类别孤岛。为了能够将诸如边界、邻域等信息引入分割过程，需要设计更为复杂的数据结构，这对进一步深入研究数据结构相关的理论与算法提出了更高的要求。

3结束语

数据结构是计算机相关专业学生公认的难度比较大的一门核心基础课。传统的教学方法完全按照抽象数据类型的设计来安排教学，内容过于抽象。学生学习难度大，且感觉枯燥乏味。采用案例教学法，能让学生从抽象乏味的理论知识中解脱出来，并让学生感觉到学习数据结构的应用价值。尤其是结合计算机学科的发展动态，联系学生感兴趣的内容进行案例教学，能在拓展学生视野的同时，让大家更好地掌握相关知识。

[参考文献]

[1]张晓玲, 黎蔚, 刘欣亮,等. 电脑知识与技术, 2007(13): 295-296.

[2]章毓晋. 中国图像工程：2003[J]. 中国图象图形学报, 9A(5): 481～498.

[3]Guoying Liu, Yun Zhang, and Aimin Wang. Incorporating adaptive local information into fuzzy clustering image segmentation. IEEE Transactions on Image Processing, 2015,24(11):3990-4000.

[4]Ji, Z., Liu, J., Cao, G., Sun, Q., and Chen, Q. Robust spatially constrained fuzzy c-means algorithm for brain MR image segmentation[J]. Pattern Recognition, 2014,47(7):2454-2466.

[5]周原, 田丽芳. 基于图论最优二叉树算法的图像分割研究[J]. 激光杂志, 2014，35(8): 23-25.

[6]严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京：清华大学出版社, 1997.

[责任编辑：江雪]

Example Teaching of Data Structure- the Application of Binary Tree in Image Segmentation

LIU Guo-ying, WANG Yu-long, CHEN Shuang-hao

(Department of Computer and Information Engineering, Anyang Normal University, Anyang 455002, China)

Abstract:Data structure is one of the core courses for students who major in computer and other relevant disciplines. It is of the critical roles for students to learn successive courses. Besides, it is also very important for the enhancement of their ability to design complex software systems. However, in the conventional classes, teachers only focus on the definition of abstract data types and their implementation, which make students feel very boring and difficulty. In this paper, we employ image segmentation as an example of the application of binary structure. By making use of the properties of binary tree, such as the properties of the best binary tree and the methods of binary tree traverse, we designed an image segmentation method, and then simply analyzed its performance by using a piece of remote sensing image. Our applications in teaching show that example teaching method can achieve higher teaching quality than the conventional one.

Key words:data structure;binary tree;image segmentation;example teaching

[收稿日期]2016-01-01

[基金项目]计算机科学与技术国家级特色专业(TS11576)；国家自然科学基金(41001251)；河南省科技公关项目(152102410042、132102210212)；河南省教育厅资助项目(13A520011)；河南省青年骨干教师项目(2011-148)；安阳师范学院《数据结构》精品资源共享课程。

[作者简介]刘国英(1979-)，男，博士，副教授，主要从事遥感影像信息提取研究。

[中图分类号]G642

[文献标识码]A

[文章编号]1671-5330(2016)02-0128-04