基于改進(jìn)DBSCAN算法的金相圖像晶粒聚集檢測方法

周 潤，滕奇志

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

0 引 言

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

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

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

1 相關(guān)定義簡介

1.1 DBSCAN

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

（1）領(lǐng)域半徑（E ps）。點(diǎn)p的領(lǐng)域表示為以p為中心、r為半徑計(jì)算歐式距離的圓形區(qū)域。r即為領(lǐng)域半徑。

（2）領(lǐng)域密度閾值（Mi nPt s）。 可簡單表示為以點(diǎn)p為中心，E ps為半徑的區(qū)域中，除點(diǎn)p之外其它點(diǎn)的數(shù)量。

DBSCAN算法通過以上參數(shù)確定領(lǐng)域密度。將所有數(shù)據(jù)點(diǎn)分為3類：

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

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

（3）噪聲點(diǎn)。孤立于核心點(diǎn)和邊界點(diǎn)的其它點(diǎn)。

DBSCAN算法通過一定的距離度量方式，先找出所有數(shù)據(jù)點(diǎn)中的核心點(diǎn)，生成核心點(diǎn)列表。通過遍歷核心點(diǎn)列表，將每個核心點(diǎn)的密度可達(dá)區(qū)域劃分為一個簇，待所有簇劃分完畢，將剩下的點(diǎn)標(biāo)記為噪聲點(diǎn)，算法結(jié)束。

1.2 k-d樹

K-d樹（k-dimensional Tree）［5］用于在k維空間為數(shù)據(jù)點(diǎn)建立索引。常見的KNN算法［6］中，使用線性遍歷的方式查詢目標(biāo)數(shù)據(jù)。當(dāng)數(shù)據(jù)點(diǎn)過多時查詢時間復(fù)雜度較高，使用k-d樹數(shù)據(jù)結(jié)構(gòu)做索引，能夠大幅提高查詢效率。本文實(shí)驗(yàn)中所使用到的二維k-d樹建樹過程如圖2所示。

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

建樹流程如下：

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

（2）確定切分點(diǎn)。將切分平面上的所有數(shù)據(jù)點(diǎn)，按照劃分域?yàn)榛鶞?zhǔn)進(jìn)行大小排序。選擇排在正中的點(diǎn)作為切分點(diǎn)，并建立左、右子樹。

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

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

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

2 本文算法

2.1 預(yù)處理

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

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

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

2.2 改進(jìn)的DBSCAN算法

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

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

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

式中，n表示圖像中晶?？倐€數(shù)，m表示整幅圖像像素點(diǎn)總數(shù)。

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

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

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

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

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

（4）將所有聚類結(jié)果標(biāo)注回原圖，算法結(jié)束。

2.3 算法總體流程

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

圖7 實(shí)驗(yàn)結(jié)果對比圖Fig.7 Comparison of experimental results

圖8 實(shí)驗(yàn)結(jié)果對比圖Fig.8 Comparison of experimental results

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

圖9 不同倍數(shù)下F值對比結(jié)果Fig.9 Comparison results of F values under different multiples

圖10 不同數(shù)據(jù)集大小下時間對比結(jié)果Fig.10 Comparison results of time under different data set sizes

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

4 結(jié)束語

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