基于改進DBSCAN算法的金相圖像晶粒聚集檢測方法

周 潤，滕奇志

（四川大學 電子信息學院圖像信息研究所，成都610065）

0 引 言

金相組織的定量分析是為了更加準確的檢測材料的成分、顯微組織等特性。其中包括平均晶粒度、粗大晶粒尺寸及粒度分布等。結構均勻的硬質合金材料，其強度、壽命均優于含有較多粗大晶粒或晶粒聚集的材料。因此，在晶粒度分析過程中，需提取圖像中長徑超過6微米的粗大晶粒，以及3個以上晶粒聚集區域。由于不同成分的合金材料將會應用在不同環境中，而含有較多粗大晶粒或晶粒聚集的合金材料，在惡劣環境下將出現疲勞現象，進而發生危險事故。早期的晶粒聚集檢測工作是由專業人員目測聚集區域，并通過手動測量的方式進行。近年來，數字圖像處理技術雖已逐步應用在金相分析領域，但針對晶粒聚集檢測還沒有較好的提取方法。本文實驗中用到的金相圖像是在光學顯微鏡30x、75x物鏡下，由數字攝像頭拍攝所得。如圖1所示，一個視域的金相圖像需提取晶粒密度相對較高的區域，如圖1（c）中綠色標注區域。為提取目標區域，初步采用OTSU閾值分割算法分割出聚集區域，效果如圖1（b）所示。此時，聚集周圍有較多小型晶粒也被分割出來。進一步使用去噪算法剔除小型晶粒，效果如圖1（c）。由于去噪后聚集區域內部一些晶粒被當作噪聲剔除，無法較好的提取完整聚集區域。因此，上述方法不適用于晶粒聚集的檢測。

從圖像分析的角度看，聚集區域的晶粒坐標位置相對集中，因此考慮采用空間坐標聚類方法進行檢測。常見的密度聚類算法有DBSCAN、OPTICS［1］等。本文在借鑒密度聚類算法的基礎上，提出一種基于DBSCAN的金相圖像晶粒聚集檢測方法，并針對DBSCAN算法需確定Eps和MinPts參數的問題作出改進，使其能夠根據圖像，自適應地調整參數。同時使用k-d樹數據結構對算法進行加速。實驗結果表明，使用本文算法在不同放大倍數和不同聚集密度的情況下，均可以自適應地找出聚集區域且無需人為干預，具有較強的魯棒性和穩定性。

圖1 75x金相圖像和預處理過后的圖像Fig.1 75x metallographic image and pre-processed images

1 相關定義簡介

1.1 DBSCAN

DBSCAN（density-based spatial clustering of applications with noise）算法由Martin Ester等人于1996年提出［2］，是一種典型的基于密度的聚類算法。相較于k-means等［3-4］其它類型的聚類算法，DBSCAN算法不需要事先指定類別數，且能夠處理不同大小形狀的簇，同時能夠正確處理噪聲點和離群點，常被應用于圖像處理等領域。DBSCAN算法需要指定的基本參數：

（1）領域半徑（E ps）。點p的領域表示為以p為中心、r為半徑計算歐式距離的圓形區域。r即為領域半徑。

（2）領域密度閾值（Mi nPt s）。 可簡單表示為以點p為中心，E ps為半徑的區域中，除點p之外其它點的數量。

DBSCAN算法通過以上參數確定領域密度。將所有數據點分為3類：

（1）核心點。在以點p為中心，E ps為半徑的區域中，含有超過Mi n P t s閾值的點，則將點p稱為核心點。

（2）邊界點。在以點p為中心，E ps為半徑的區域中，點的數量小于Mi n Pt s閾值，但點p落在其它核心點包含的區域中，則稱點p為邊界點。

（3）噪聲點。孤立于核心點和邊界點的其它點。

DBSCAN算法通過一定的距離度量方式，先找出所有數據點中的核心點，生成核心點列表。通過遍歷核心點列表，將每個核心點的密度可達區域劃分為一個簇，待所有簇劃分完畢，將剩下的點標記為噪聲點，算法結束。

1.2 k-d樹

K-d樹（k-dimensional Tree）［5］用于在k維空間為數據點建立索引。常見的KNN算法［6］中，使用線性遍歷的方式查詢目標數據。當數據點過多時查詢時間復雜度較高，使用k-d樹數據結構做索引，能夠大幅提高查詢效率。本文實驗中所使用到的二維k-d樹建樹過程如圖2所示。

圖2 二維k-d樹建樹過程Fig.2 2-dimensional k-d tree building process

建樹流程如下：

（1）確定劃分域。首先計算所有數據點x坐標和y坐標的均值，再以該均值為基準，計算數據點在x方向和y方向上的方差，選擇方差更大的作為劃分域。方差更大表示在該坐標軸上的數據點較分散，如圖2所示的建樹過程，是以x軸作為劃分域。

（2）確定切分點。將切分平面上的所有數據點，按照劃分域為基準進行大小排序。選擇排在正中的點作為切分點，并建立左、右子樹。

（3）確定子空間。將切分好的兩個子空間按照步驟（1）遞歸切分，直到某一子空間中只有一個或者沒有數據點，則切分結束。

K-d樹的查詢過程如圖3所示。以查詢標星點p的最近鄰點為例，查詢其最近鄰點需先在樹中找到其直屬的葉子節點q，并以點q作為臨時最近鄰點，計算出點p到點q的距離di s t，最后以點p為圓心，d i st為半徑做圓，真正的最近鄰點一定會在圓內，如點x。

圖3 二維k-d樹查詢過程Fig.3 2-dimensional k-d tree query procedure

2 本文算法

2.1 預處理

因金相圖像拍攝時受到亮度、景深、放大倍數等方面因素影響，直接使用OTSU閾值分割方法對圖像提取晶粒時效果欠佳，如圖4（b）所示。為解決此類問題，本文需對金相圖像做預處理工作。圖4（a）中金相圖像的直方圖如圖5所示。從直方圖中可以看出，圖像的灰度值分布有明顯的雙峰形狀，因此先使用對比度增強算法［7］調整晶粒和背景的對比度后，用直方圖雙峰法做初步的閾值分割，分割效果如圖4（c）所示。可以看出，此時能將完整的聚集區域提取出來，但周圍小型晶粒過多，直接使用聚類算法可能會有誤分類。為進一步降低小型晶粒對聚類結果的影響，將上一次分割的結果映射回原圖，再次遍歷圖像。此時只統計上次被分割區域中的最大和最小灰度值，并使用這兩個灰度值作為閾值，使用OTSU雙閾值分割算法再次分割圖像，分割結果如圖4（d）所示。此時聚集區域能被完整提取出來，且周圍小型晶粒較少。

圖4 閾值分割效果圖Fig.4 Threshold segmentation renderings

圖5 圖像直方圖Fig.5 Image histogram

2.2 改進的DBSCAN算法

DBSCAN算法用Mi n Pt s和E ps兩個參數來描述聚類的密度閾值，將超過密度閾值的大集合聚成一個簇。因此，該算法對這兩個參數的取值十分敏感，取值不當可能會導致聚類結果不正確。為此，很多國內外學者致力于研究自適應尋找Mi nPt s和E p s參數的方法。文獻［8］根據數據點在每個維度密度分布不同的特點，提出一種自適應調整E p s的算法，該算法使用恒定的Mi n P t s；文獻［9］根據確定密度峰值點的方式，提出一種自適應調整E ps的SALEDBSCAN算法，但該算法仍需要設置固定的Mi n P t s；文獻［10］通過生成候選Mi nPt s和E ps列表，根據參數尋優策略，提出一種完全自適應的KANNDBSCAN算法，但該算法時間復雜度較高，在數據點規模較大時耗時較多。

鑒于以上問題，本文提出一種針對金相圖像的自適應DBSCAN算法，其算法流程如下：

（1）根據金相圖像特征，使用平均晶粒大小作為Mi nPt s，即：

式中，n表示圖像中晶粒總個數，m表示整幅圖像像素點總數。

在具體應用中，除聚集外還需要找出長徑大于6微米的單個粗大晶粒，因此使用平均晶粒大小確定Mi nPt s比較合適。

（2）遍歷圖像生成候選核心點隊列，以每個晶粒的重心作為候選核心點加入隊列，并確定E ps，其表達式為：

式中，R i表示第i個晶粒的內切圓半徑，取晶粒內切圓半徑的五分之一作為每個候選核心點的E ps。

對于DBSCAN算法，在提取粗大晶粒后，繼續將周圍的小型晶粒聚為同一簇。而提取小型晶粒時，如果E ps過大，則將很多分散的小型晶粒聚為一簇。為減少此類情況，使用晶粒的自身特征來確定E ps較為合適。實驗過程中發現，使用1／5R i作為E ps搭配Mi n Pt s效果較好，能夠僅將晶粒自身及其周圍小部分區域聚為一簇。

（3）用候選核心點隊列和對應的E ps作DBSCAN聚類，記錄聚類結果。若此時未完成整張圖像所有數據點遍歷，為判斷剩余點為孤立的小型晶粒，則使用候選核心點列表中最小Eps作為參數進行下一輪聚類，直到遍歷完所有數據點。

（4）將所有聚類結果標注回原圖，算法結束。

2.3 算法總體流程

本文使用的金相圖像待聚類像素點個數平均在十萬左右。使用DBSCAN算法進行聚類時，由于每次尋找最近鄰點時會重復遍歷所有數據并計算每個點之間的距離，算法時間復雜度較高，運行時間較長。為此，本文使用二維k-d樹數據結構劃分數據區域并構建數據點索引，進而減少重復訪問次數。算法整體流程如圖6所示。

圖6 算法流程圖Fig.6 Algorithm flow chart

3 實驗結果分析

本文算法采用C++語言實現，操作系統為Windows10，開發工具為Visual Studio 2010+MFC。為驗證本文算法在金相圖像數據集上的有效性和正確性，選擇不同聚集密度、亮度、形狀的圖像，對比了手動標注圖像、傳統DBSCAN算法和本文算法。其中，所有手動標注圖均由專業人員協助標注。具體實驗過程和結果分析如圖7、圖8所示。

由圖7、圖8可以看出，對于聚集密度不同的圖像，傳統DBSCAN算法需要反復實驗才能找到一個較合適的參數。如圖7所示，為能包含整個聚集區域，適當調大了E ps和Mi n Pt s，但使周圍一些小型晶粒被誤聚類；在圖8中，為使周圍小型晶粒不被誤判為聚集而適當調小參數后，可能導致聚集晶粒區域提取不完整。本文算法能夠自適應地調整E p s，以將整個聚集區域找出且只包含少數小型晶粒。另外，使用F值（F-Sco r e）為聚集結果做定量分析［11］，F值的定義為：

式中，Pre表示正確率，即正確聚類的個數占總聚類個數的百分比，Rec表示召回率，即正確聚類的像素點數占輸入圖像像素點總數的百分比。通過比較F值能夠預估算法對于聚集效果的正確性。

圖7 實驗結果對比圖Fig.7 Comparison of experimental results

圖8 實驗結果對比圖Fig.8 Comparison of experimental results

本文共測試不同放大倍數下共63張金相圖像，在不同放大倍數下的F值對比和不同數據規模下的算法運行時間對比如圖9、圖10所示。

圖9 不同倍數下F值對比結果Fig.9 Comparison results of F values under different multiples

圖10 不同數據集大小下時間對比結果Fig.10 Comparison results of time under different data set sizes

從圖中數據對比可以看出，本文算法在聚集準確度方面優于傳統DBSCAN算法，且通過k-d樹加速后的算法時間復雜度更低，整個檢測過程不需要用戶干預，操作簡潔方便。

4 結束語

本文提出一種基于改進DBSCAN聚類算法的金相晶粒聚集檢測方法，該方法從密度聚類的思想出發，借鑒了許多國內外研究者對于自適應尋找DBSCAN最優參數的方法，提出了一種針對金相圖像的自適應DBSCAN算法。實驗證明，本文方法優于傳統DBSCAN算法且無需人為設置參數，有更低的時間復雜度，能夠準確便捷的完成檢測任務。進一步的主要研究方向，在于如何讓DBSCAN算法在聚類流程中自適應修改MinPts的值，以獲得更加精確的聚類效果，并希望能將該算法嵌入實際工程當中，幫助工作人員高效完成任務。