數(shù)據(jù)結(jié)構(gòu)案例教學(xué)
—二叉樹在圖像分割中的應(yīng)用

劉國英，王煜龍，陳雙浩

(安陽師范學(xué)院 計算機與信息工程學(xué)院，河南 安陽 455002)

?

數(shù)據(jù)結(jié)構(gòu)案例教學(xué)
—二叉樹在圖像分割中的應(yīng)用

劉國英，王煜龍，陳雙浩

(安陽師范學(xué)院 計算機與信息工程學(xué)院，河南 安陽 455002)

[摘要]數(shù)據(jù)結(jié)構(gòu)是計算機相關(guān)專業(yè)的核心基礎(chǔ)課。掌握數(shù)據(jù)結(jié)構(gòu)有關(guān)知識對學(xué)生進一步學(xué)習(xí)后續(xù)課程起著至關(guān)重要的作用，有助于提高學(xué)生設(shè)計復(fù)雜軟件的能力。然而，傳統(tǒng)的教學(xué)方法過于強調(diào)抽象數(shù)據(jù)類型的定義及對應(yīng)的實現(xiàn)方法，而使得讓學(xué)生覺得枯燥和困難。本文以二叉樹在圖像分割中的應(yīng)用為案例，利用最優(yōu)二叉樹的性質(zhì)、二叉樹的遍歷方法等知識點，設(shè)計圖像分割算法，并進行了簡單分析。教學(xué)實踐表明，數(shù)據(jù)結(jié)構(gòu)的案例教學(xué)比傳統(tǒng)教學(xué)更能提高教學(xué)質(zhì)量。

[關(guān)鍵詞]數(shù)據(jù)結(jié)構(gòu);二叉樹;圖像分割;案例教學(xué)

數(shù)據(jù)結(jié)構(gòu)是計算機及相關(guān)專業(yè)的一門核心課程，對學(xué)生深入學(xué)習(xí)計算機專業(yè)知識具有至關(guān)重要的作用。二叉樹作為一種應(yīng)用極其廣泛的數(shù)據(jù)結(jié)構(gòu)，是學(xué)生必須掌握的一個知識點。然而，該結(jié)構(gòu)相對線性結(jié)構(gòu)更加抽象和復(fù)雜，常用教材中采用的案例非常少，這對學(xué)生理解產(chǎn)生巨大障礙。雖然有教師設(shè)計了不同的案例方法[1]，但仍然顯不夠。

當(dāng)前，多媒體智能信息處理技術(shù)一直引領(lǐng)計算機學(xué)科的發(fā)展。其中，圖像分割是圖像及視頻信息處理的一個基礎(chǔ)研究課題，在遙感、農(nóng)業(yè)、軍事等領(lǐng)域應(yīng)用非常廣泛。圖像分割技術(shù)的深入研究對數(shù)據(jù)結(jié)構(gòu)理論體系的發(fā)展和應(yīng)用提出了更高的要求。很多人在圖像分割領(lǐng)域進行了研究[2-5]。因此，為了拓展學(xué)生的知識面，提高學(xué)生學(xué)習(xí)的熱情，本文以圖像分割為背景，設(shè)計數(shù)據(jù)結(jié)構(gòu)中二叉樹的案例教學(xué)方法。

1基本知識

1.1圖像分割與二叉樹結(jié)構(gòu)

對圖像分割的研究一直是圖像處理中的重點和熱點[2]。圖像分割的目的是將圖像劃分為互不重疊的圖像區(qū)域，并要求圖像區(qū)域內(nèi)部的像素具有相同的屬性，比如顏色和紋理。在圖像分割中，獲得的圖像區(qū)域個數(shù)就成為圖像的類別數(shù)。

二叉樹是指樹種任一結(jié)點的度小于2的樹，即任一結(jié)點最多有兩棵子樹，并且二叉樹的子樹有左右之分，其次序不能顛倒[6]。這表明二叉樹或為空，或為一個根節(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。這兩棵子樹也是二叉樹。因此，二叉樹是遞歸定義的。因為二叉樹不同子樹上的節(jié)點是互不相交的，這與圖像分割中各個分割區(qū)域之間互不重疊的要求是一致的。所以，利用二叉樹的性質(zhì)設(shè)計圖像分割算法符合該研究問題的特點。

1.2二叉樹的遍歷

遍歷二叉樹是指按照某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次[6]。由二叉樹的遞歸定義可知，二叉樹是由3個基本單元組成：根節(jié)點、左子樹和右子樹。因此，二叉樹的遍歷即為按照某種順序依次訪問這三部分的算法。根據(jù)根結(jié)點的訪問次序，有三種二叉樹遍歷方法：先序遍歷、中序遍歷和后序遍歷。先序遍歷是指先訪問根節(jié)點，再依次遍歷左子樹和右子樹。中序遍歷是指先遍歷左子樹，再訪問根結(jié)點，最后遍歷右子樹。后序遍歷指先依次遍歷左子樹和右子樹，最后再訪問根結(jié)點。

本文的案例教學(xué)中，在獲得圖像分割過程所對應(yīng)的二叉樹后，使用先序遍歷的方法確定每一結(jié)點屬于哪個類別，并生成最終的分割結(jié)果。

1.3最優(yōu)二叉樹

最優(yōu)二叉樹是指帶權(quán)路徑長度最小的二叉樹，又稱作赫夫曼樹[6]。在該樹種沒有度為1的結(jié)點。因此，一個有n個葉子結(jié)點的最優(yōu)二叉樹共有2n-1個結(jié)點。因為，在構(gòu)造最優(yōu)二叉樹后，經(jīng)常需要從葉子結(jié)點出發(fā)尋找一條到根結(jié)點的路徑。比如，赫夫曼編碼時需要根據(jù)從根結(jié)點到葉子結(jié)點的路徑來確定編碼，本文案例教學(xué)所用的圖像分割實例也需要依據(jù)從葉子結(jié)點到根結(jié)點的路徑來確定葉子節(jié)點對應(yīng)像素所在的類別。為此，在最優(yōu)二叉樹的結(jié)點結(jié)構(gòu)中，除了包含所需的數(shù)據(jù)信息外，一般還包含三個指針：父結(jié)點指針 、左子樹指針和右子樹指針。增加父結(jié)點指針為訪問父結(jié)點提供了便利。

2基于最優(yōu)二叉樹的圖像分割案例

2.1分割算法設(shè)計

假設(shè)待分割圖像表示為像素集合{Pi|i=1,2,…,N}，其中N為圖像的像素個數(shù)。為了減少算法處理的數(shù)據(jù)量，本案例教學(xué)設(shè)計的分割方法針對灰度圖像的256個灰度值進行處理。假設(shè)分割的類別數(shù)為K，基于二叉樹進行圖像分割的算法描述如下：

(1) N個像素構(gòu)成N棵二叉樹的集合F={T1,T2,…,TN}，其中每棵二叉樹只有一個根節(jié)點，其左右子樹均為空；

(2) 采用一定的策略，在F中選取兩棵樹作為左右子樹構(gòu)造一棵新的二叉樹；

(3) 在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中；

(4) 重復(fù)(2)和(3)，直到F中包含的二叉樹的個數(shù)為K。這時，F(xiàn)中每一棵二叉樹對應(yīng)圖像的一個分割區(qū)域。對每一棵二叉樹執(zhí)行葉子結(jié)點的遍歷操作，即可獲得對應(yīng)類別在圖像中的真實分割區(qū)域。

2.2算法順序表示與實現(xiàn)

為了運算簡便，在執(zhí)行步驟(2)時，本文采用如下準(zhǔn)則進行二叉樹選擇：兩個根結(jié)點對應(yīng)圖像區(qū)域的灰度均值最接近。為此，在本案例中，我們設(shè)計如下的最優(yōu)二叉樹結(jié)點結(jié)構(gòu)：

typedef struct{

int rootId; //該結(jié)點的存儲索引

double meanValue; // 灰度均值

int pixlNumber; //以該結(jié)點為根的像素個數(shù)

unsigned int parent, lchild, rchild; //父結(jié)點、孩子結(jié)點在二叉節(jié)點列表中的存儲位置

}BTNode, *BestBiTree;

對應(yīng)的森林F存儲在結(jié)構(gòu)體數(shù)組中，大小為2n-K-1。上述結(jié)構(gòu)體中的三個整形變量表示每一個結(jié)點的父結(jié)點、左右孩子在結(jié)構(gòu)體數(shù)組中的存儲單元下標(biāo)。如果某一結(jié)點的父結(jié)點為0，表示該結(jié)點為樹的根結(jié)點；F中樹的個數(shù)表示當(dāng)前圖像的分割類別數(shù)。因此，構(gòu)造最優(yōu)二叉樹的過程就是圖像分割的過程。圖像分割的算法實現(xiàn)如下：

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

// pImage為指向灰度圖像數(shù)據(jù)的指針， pSegmentation為分割結(jié)果指針

// width和height為圖像的高和寬，K為圖像的分類個數(shù)

{

if (K<2) return;

if(pSegmentation==NULL) return;

int n = 256;// 圖像灰度級的總個數(shù)

//統(tǒng)計每一灰度級出現(xiàn)的頻度, gFred[i]為灰度gId[i]在圖像中出現(xiàn)的次數(shù)

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

// 統(tǒng)計每一灰度級對應(yīng)的像素集合, pxlSet[i]為灰度級gId[i]對應(yīng)的像素位置集合的指針

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

int m = 2*n-1-K; // 獲取最終分割結(jié)果時，F(xiàn)中總共的結(jié)點個數(shù)

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

double disMatrix[m][m]; // 根結(jié)點距離矩陣，取值越小，樹的灰度越接近

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]);// 計算初始的相似度取值

}

// 創(chuàng)建Forest中的每棵二叉樹

for(i=n;i

//選擇根結(jié)點灰度值最接近的兩棵樹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);

}

}

//從構(gòu)造的二叉樹森林中獲取分割結(jié)果

cls = 1;

for(i=0;i

if(Forest[i].parent==0)//節(jié)點i為樹根

InitSet(leavesSet);//將葉子結(jié)點集合leavesSet初始化為空集合

PreOrderTrevers(Forest,i,leavesSet);//先序遍歷獲得葉子結(jié)點集合

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

InitSet(treePixelSet);// 初始化一個空的集合，用來存儲像素的索引

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

//合并同一棵樹的葉子結(jié)點對應(yīng)的像素索引集合

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

}

// 將pSegmentation中的在treePixelSet中的像素索引位置均設(shè)為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案例算法運行結(jié)果

為了檢驗案例算法的分割效果，在教學(xué)過程中我們選用一幅大小為256*256的全色遙感影像進行算法測試。實驗中，我們設(shè)定類別數(shù)K=6，對應(yīng)的分割結(jié)果如圖1所示。分割結(jié)果使用彩色表示是為了增加不同類別之間的視覺差別。從圖中可以看出，使用二叉樹結(jié)構(gòu)進行圖像分割能夠完成圖像分割所要求的功能。

(a)　　　　　　　　　　　　　　　　　(b)圖1 案例算法運行結(jié)果 (a)待分割圖像; (b) 分割結(jié)果

該分割算法只考慮了像素灰度值之間的大小關(guān)系，沒有考慮任何的空間信息。因此，分割結(jié)果中存在較多的類別孤島。為了能夠?qū)⒅T如邊界、鄰域等信息引入分割過程，需要設(shè)計更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，這對進一步深入研究數(shù)據(jù)結(jié)構(gòu)相關(guān)的理論與算法提出了更高的要求。

3結(jié)束語

數(shù)據(jù)結(jié)構(gòu)是計算機相關(guān)專業(yè)學(xué)生公認的難度比較大的一門核心基礎(chǔ)課。傳統(tǒng)的教學(xué)方法完全按照抽象數(shù)據(jù)類型的設(shè)計來安排教學(xué)，內(nèi)容過于抽象。學(xué)生學(xué)習(xí)難度大，且感覺枯燥乏味。采用案例教學(xué)法，能讓學(xué)生從抽象乏味的理論知識中解脫出來，并讓學(xué)生感覺到學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用價值。尤其是結(jié)合計算機學(xué)科的發(fā)展動態(tài)，聯(lián)系學(xué)生感興趣的內(nèi)容進行案例教學(xué)，能在拓展學(xué)生視野的同時，讓大家更好地掌握相關(guān)知識。

[參考文獻]

[1]張曉玲, 黎蔚, 劉欣亮,等. 電腦知識與技術(shù), 2007(13): 295-296.

[2]章毓晉. 中國圖像工程：2003[J]. 中國圖象圖形學(xué)報, 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]周原, 田麗芳. 基于圖論最優(yōu)二叉樹算法的圖像分割研究[J]. 激光雜志, 2014，35(8): 23-25.

[6]嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京：清華大學(xué)出版社, 1997.

[責(zé)任編輯：江雪]

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

[基金項目]計算機科學(xué)與技術(shù)國家級特色專業(yè)(TS11576)；國家自然科學(xué)基金(41001251)；河南省科技公關(guān)項目(152102410042、132102210212)；河南省教育廳資助項目(13A520011)；河南省青年骨干教師項目(2011-148)；安陽師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)》精品資源共享課程。

[作者簡介]劉國英(1979-)，男，博士，副教授，主要從事遙感影像信息提取研究。

[中圖分類號]G642

[文獻標(biāo)識碼]A

[文章編號]1671-5330(2016)02-0128-04