回溯法在多孔材料孔徑測量中的應(yīng)用

趙 玲，全書海，石 英

(武漢理工大學(xué)自動化學(xué)院，湖北武漢 430070)

多孔材料是含有大量孔隙的固體物質(zhì)，是一種性能優(yōu)異的新型工程材料，在石油、化學(xué)工業(yè)、能源、環(huán)境和生物等眾多科學(xué)和工程領(lǐng)域以及人類的日常生活中都具有廣泛的應(yīng)用，其擴(kuò)散、導(dǎo)熱和滲流等宏觀物性研究具有很重要的工程應(yīng)用背景和科學(xué)價值［1］。對其微觀特征的表征比僅研究物理統(tǒng)計量的常規(guī)物性更為深入細(xì)致，能正確地反映其宏觀特性。隨著圖像檢測技術(shù)在測量領(lǐng)域中的迅速發(fā)展，基于SEM圖像的直接觀測法［2-3］在多孔材料的微觀結(jié)構(gòu)測量與表征上頗具優(yōu)勢，應(yīng)用該技術(shù)對多孔材料微觀結(jié)構(gòu)參數(shù)進(jìn)行準(zhǔn)確定量分析逐步成為可能。施斌等［4-5］基于圖像定量分析了我國某些典型粘性土微結(jié)構(gòu)單元體的形態(tài)、大小及分布，獲得單元體的定向角分布、主定向角和各向異性率等數(shù)據(jù)。熊承仁等［6］利用重塑粘性土的SEM圖像，計算了平面孔隙比和平面孔隙度，計算值與理論值比較吻合。多孔材料的微觀性質(zhì)包括孔隙面積、孔徑分布、孔隙率和周長等，要得到多孔材料的這些微觀性質(zhì)，就必須先對其SEM圖像的孔洞區(qū)域進(jìn)行標(biāo)記。通常使用的孔洞標(biāo)記算法有迭代算法和遞歸算法。筆者分析了迭代孔洞標(biāo)記和遞歸孔洞標(biāo)記方法的不足之處，結(jié)合回溯法的思想采用一種新的方法對多孔材料進(jìn)行標(biāo)記，大大簡化了程序設(shè)計。

1 迭代孔洞標(biāo)記法與遞歸孔洞標(biāo)記法

1.1 迭代孔洞標(biāo)記

在一幅圖像中［7］，為了對圖像的連通域進(jìn)行標(biāo)記，需要對一幅圖像作從左到右，從上到下的水平掃描，檢測當(dāng)前被掃描到的點是不是與周圍的點連通。如果當(dāng)前像素的值與鄰近像素的值一樣，就表示它們連通，反之，就表示與此鄰近像素不連通，此時就要給當(dāng)前點一個新的標(biāo)記。

迭代孔洞標(biāo)記圖如圖1所示。一個簡單的區(qū)域會出現(xiàn)圖1(a)的情況，圖中不同的紋線密度表示不同的標(biāo)記，采用迭代孔洞標(biāo)記，當(dāng)前掃描到C4這個點的時候，只要C5這一行比它上一行向左多伸出兩個或兩個以上像素點(多一個沒有問題)，那么與C5這個像素點對應(yīng)的鄰近像素點C1，C2，C3，C4的值就全部為 0(孔洞區(qū)域為 1，非孔洞區(qū)域為0)，于是會對C5賦予一個新標(biāo)號。掃描結(jié)束后，在一個區(qū)域中可能會有好幾根掃描線會出現(xiàn)這種情況，結(jié)果導(dǎo)致一個簡單的目標(biāo)域卻被分成幾個連通區(qū)，見圖1(b)。

為了減少等價標(biāo)記的數(shù)目，需要考慮很多特殊情況，考慮不全面會導(dǎo)致結(jié)果嚴(yán)重偏離真實值。

1.2 遞歸孔洞標(biāo)記

圖1 迭代孔洞標(biāo)記圖

一個直接或間接地調(diào)用自身的算法稱為遞歸算法［8］。一個使用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。在計算機(jī)算法設(shè)計與分析中，遞歸技術(shù)是十分有用的。使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡潔且易于理解。遞歸孔洞標(biāo)記從圖像中一個像素點開始，遞歸處理其周圍4鄰域的像素點，從一點逐漸向外膨脹，遞歸返回一次就可以得到其面積。具體步驟如下:

采用遞歸孔洞標(biāo)記最終能訪問完圖像中所有孔洞目標(biāo)區(qū)域，不會產(chǎn)生遺漏。但是遞歸調(diào)用的過程會有很多重復(fù)處理，因此占用的棧空間會比較多，直到所有遞歸完成以后才能釋放資源，當(dāng)數(shù)據(jù)量較大時，遞歸次數(shù)過多，會導(dǎo)致堆棧溢出，程序無法繼續(xù)運(yùn)行［9］。

2 回溯孔洞標(biāo)記法

回溯法［10］是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。確定了解空間的組織結(jié)構(gòu)后，回溯法從開始結(jié)點(根結(jié)點)出發(fā)，這個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴(kuò)展結(jié)點。在當(dāng)前的擴(kuò)展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前擴(kuò)展結(jié)點。如果在當(dāng)前的擴(kuò)展結(jié)點處不能再向縱深方向移動，則當(dāng)前的擴(kuò)展結(jié)點就成為死結(jié)點。換句話說，這個結(jié)點不再是一個活結(jié)點。此時，應(yīng)往回移動(回溯)至最近的—個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴(kuò)展結(jié)點?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點時為止。

回溯孔洞標(biāo)記法在一副經(jīng)過預(yù)處理的圖像中，從左到右，從上到下掃描，直到發(fā)現(xiàn)一個沒有標(biāo)記過的孔洞像素點，以此像素點為起始點，按右、下、左、上的順序?qū)σ粋€連通區(qū)域進(jìn)行深度搜素，直至把整個連通區(qū)域搜索完畢。標(biāo)記各個孔洞，保存信息。具體步驟如下:

(1)判斷當(dāng)前點(孔洞)是否標(biāo)記過，未標(biāo)記轉(zhuǎn)步驟(2)，標(biāo)記過轉(zhuǎn)步驟(3);

(2)孔洞面積加1，并標(biāo)記該點，保存該像素點信息(包括坐標(biāo)，方向)，入棧，進(jìn)入步驟(4);

(3)取棧頂元素，判斷是否所有方向都已搜索完畢，如果該像素點其他方向未搜索，則進(jìn)入步驟(4)，否則轉(zhuǎn)步驟(5);

(4)尋找下一個像素點，繼續(xù)搜索，轉(zhuǎn)步驟(1);

(5)將該像素點出棧，判斷棧是否為空，不為空，繼續(xù)搜索，轉(zhuǎn)入步驟(1)，否則搜索完畢，程序退出。

該方法類似于迷宮問題，迷宮問題只是從入口到出口找到一條通路，而回溯孔洞標(biāo)記則是把與這個通路連通的整個區(qū)域都找出來。一個簡單的迷宮圖如圖2所示。

圖2 迷宮圖

圖2中黑色區(qū)域為迷宮的墻，迷宮問題只要求從入口處(0，0)到出口(3，4)之間找到一條通路，就停止尋找，回溯孔洞標(biāo)記法則繼續(xù)返回搜索，直至把整個連通區(qū)域都遍歷完(搜索方向為右，下，左，上)。具體搜索過程如下:

(3，4)為最末點，走到這里，迷宮問題得到解決。而本算法經(jīng)過判斷后把該點彈出，同理一直回溯到(2，1)點，在(2，1)點繼續(xù)向左搜索。

到(1，0)點時，其4鄰域內(nèi)3個像素都標(biāo)記過，經(jīng)過判斷后彈出該點信息，回溯到(2，1)點，該像素點所有方向都搜索完畢，繼續(xù)向前回溯到(0，0)點，彈出所有像素點后，棧為空，結(jié)束該連通區(qū)域搜索。

采用回溯孔洞標(biāo)記法能完整地遍歷整個圖像，將多孔材料SEM圖像上不同的連通區(qū)域用不同的數(shù)值標(biāo)記出來，而同一個目標(biāo)區(qū)域中所有的像素用同一個數(shù)值表示。該方法在搜索的過程中對搜索過的點進(jìn)行出棧操作，避免了遞歸帶來的堆棧溢出后果。

3 實驗結(jié)果分析

3.1 迭代結(jié)果分析

筆者利用淀粉SEM圖像和陶瓷SEM圖像對該算法予以驗證，在測量之前首先對實驗對象進(jìn)行一系列預(yù)處理，把SEM圖像轉(zhuǎn)化成BMP文件格式，然后采用HSI選取閾值對圖像二值化，得到二值化圖像(白色區(qū)域為孔隙)。圖3～圖5均為回溯孔洞標(biāo)記法測得的實驗結(jié)果。圖3(a)所示為經(jīng)過預(yù)處理后的淀粉SEM圖像，圖5(a)所示為經(jīng)過預(yù)處理后的陶瓷SEM圖像。

圖3 X 5000淀粉SEM圖像實驗結(jié)果

圖4 X 1000淀粉SEM圖像實驗結(jié)果

圖5 X 10000陶瓷SEM圖像實驗結(jié)果

對于圖3～圖5，利用迭代孔洞標(biāo)記法時，會出現(xiàn)孔洞數(shù)目結(jié)果比實際數(shù)目大很多。這是因為圖像中出現(xiàn)了很多等價標(biāo)記。如圖6所示，一個孔洞區(qū)域被分成了7個連通區(qū)。因此圖像中的目標(biāo)孔洞個數(shù)會急劇增加，而且，在對單個孔洞面積進(jìn)行像素累加時也會出現(xiàn)錯誤的結(jié)果。如果要把各種特殊情況考慮進(jìn)去，則會大大增加代碼的復(fù)雜度。一旦考慮不全面，結(jié)果也會和真實值有較大偏差。

圖6 迭代結(jié)果分析圖

3.2 遞歸結(jié)果分析

采用遞歸孔洞標(biāo)記法來處理圖3和圖4時，程序運(yùn)行良好，可以測出與回溯標(biāo)記法相同的正確結(jié)果。而對于圖5，可以看到，其中的一個孔洞面積達(dá)到了十萬個像素以上，遞歸在遇到這種數(shù)據(jù)量的情況下，堆棧溢出，程序則無法正常運(yùn)行。由此說明遞歸算法的性能會受到目標(biāo)區(qū)域大小的影響，如果目標(biāo)區(qū)域太大，就會耗盡棧空間。

4 結(jié)論

迭代標(biāo)記時需要考慮很多特殊情況，算法復(fù)雜;遞歸需消耗大量的內(nèi)存資源，且受到目標(biāo)區(qū)域大小的影響;而回溯孔洞標(biāo)記法代碼精簡，執(zhí)行效率高，測量結(jié)果準(zhǔn)確，在多孔介質(zhì)的微結(jié)構(gòu)測量中有較好的應(yīng)用價值。

［1］LIU W，PENG S W，MIZUKAMI K.A general mathematical modeling for heat and mass transfer in unsaturated porous media:an application to free evaporative cooling［J］.Heat and Mass Transfer，1995，31(1):49-55.

［2］浦紅，楊崢，陳斌.用計算機(jī)圖像處理軟件定量分析SEM 圖像［J］.物理測試，2004(1):30-32.

［3］張季如，祝杰，黃麗，等.土壤微觀結(jié)構(gòu)定量分析的IPP圖像技術(shù)研究［J］.武漢理工大學(xué)學(xué)報，2008，30(4):80-83.

［4］施斌，李生林.粘性土微觀結(jié)構(gòu)SEM圖像的定量研究［J］.中國科學(xué)(A 輯)，1995，25(6):666-672.

［5］毛靈濤，薛茹，安里千.Matlab在微觀結(jié)構(gòu)SEM圖像定量分析中的應(yīng)用［J］.電子顯微學(xué)報，2004，23(5):579-583.

［6］熊承仁，唐輝明，劉寶琛，等.利用SEM照片獲取土的孔隙結(jié)構(gòu)參數(shù)［J］.地球科學(xué):中國地質(zhì)大學(xué)學(xué)報，2007，32(3):415-419.

［7］張修軍，郭霞，金心宇.帶標(biāo)記矯正的二值圖像連通域像素標(biāo)記算法［J］.中國圖象圖形學(xué)報，2003，8(2):198-202.

［8］朱名江.遞歸算法［J］.中文信息，2002(8):36-39.

［9］俞杰，許化溪.一種易于實現(xiàn)的適于細(xì)胞圖像連通區(qū)域的標(biāo)記算法［J］.江蘇大學(xué)學(xué)報:醫(yī)學(xué)版，2005，15(2):152:155.

［10］王曉東.數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計［M］.北京:電子工業(yè)出版社，2002:54-69.