回溯法在多孔材料孔徑測量中的應用

趙 玲，全書海，石 英

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

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

1 迭代孔洞標記法與遞歸孔洞標記法

1.1 迭代孔洞標記

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

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

為了減少等價標記的數目，需要考慮很多特殊情況，考慮不全面會導致結果嚴重偏離真實值。

1.2 遞歸孔洞標記

圖1 迭代孔洞標記圖

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

采用遞歸孔洞標記最終能訪問完圖像中所有孔洞目標區域，不會產生遺漏。但是遞歸調用的過程會有很多重復處理，因此占用的?？臻g會比較多，直到所有遞歸完成以后才能釋放資源，當數據量較大時，遞歸次數過多，會導致堆棧溢出，程序無法繼續運行［9］。

2 回溯孔洞標記法

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

回溯孔洞標記法在一副經過預處理的圖像中，從左到右，從上到下掃描，直到發現一個沒有標記過的孔洞像素點，以此像素點為起始點，按右、下、左、上的順序對一個連通區域進行深度搜素，直至把整個連通區域搜索完畢。標記各個孔洞，保存信息。具體步驟如下:

(1)判斷當前點(孔洞)是否標記過，未標記轉步驟(2)，標記過轉步驟(3);

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

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

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

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

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

圖2 迷宮圖

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

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

到(1，0)點時，其4鄰域內3個像素都標記過，經過判斷后彈出該點信息，回溯到(2，1)點，該像素點所有方向都搜索完畢，繼續向前回溯到(0，0)點，彈出所有像素點后，棧為空，結束該連通區域搜索。

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

3 實驗結果分析

3.1 迭代結果分析

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

圖3 X 5000淀粉SEM圖像實驗結果

圖4 X 1000淀粉SEM圖像實驗結果

圖5 X 10000陶瓷SEM圖像實驗結果

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

圖6 迭代結果分析圖

3.2 遞歸結果分析

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

4 結論

迭代標記時需要考慮很多特殊情況，算法復雜;遞歸需消耗大量的內存資源，且受到目標區域大小的影響;而回溯孔洞標記法代碼精簡，執行效率高，測量結果準確，在多孔介質的微結構測量中有較好的應用價值。

［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］浦紅，楊崢，陳斌.用計算機圖像處理軟件定量分析SEM 圖像［J］.物理測試，2004(1):30-32.

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

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

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

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

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

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

［9］俞杰，許化溪.一種易于實現的適于細胞圖像連通區域的標記算法［J］.江蘇大學學報:醫學版，2005，15(2):152:155.

［10］王曉東.數據結構與算法設計［M］.北京:電子工業出版社，2002:54-69.