數據結構案例教學
—二叉樹在圖像分割中的應用

劉國英，王煜龍，陳雙浩

(安陽師范學院 計算機與信息工程學院，河南 安陽 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