解洪力，韓 明，王善瑞

（華東交通大學(xué)材料科學(xué)與工程學(xué)院，江西 南昌 330013）

電子背散射衍射 （electron backscatter diffraction，EBSD）作為掃描電子顯微鏡的一種常規(guī)附件，同時(shí)具備了X 射線(xiàn)分析和透射電子顯微鏡中電子衍射的特點(diǎn)，在材料科學(xué)和地球科學(xué)等領(lǐng)域得到了廣泛的應(yīng)用，如單晶體取向測(cè)定[1-2]，多晶體織構(gòu)分析[3-4]、相鑒別[5-6]、晶粒尺寸測(cè)量[7-8]、應(yīng)力應(yīng)變測(cè)定[9-10]和地殼構(gòu)造變形分析[11-12]等，EBSD 技術(shù)已經(jīng)成為材料微觀(guān)表征不可或缺的重要手段。

EBSD 花樣含有材料豐富的晶體學(xué)信息， 一張典型的EBSD 花樣通常含有幾十條可見(jiàn)的菊池帶，由于Hough 變換[13]被成功用于識(shí)別這些菊池帶，實(shí)現(xiàn)了已知晶體晶面和帶軸指數(shù)的快速標(biāo)定。 特別是上世紀(jì)九十年代Lassen[14]改進(jìn)的Hough 變換，進(jìn)一步提高了EBSD 花樣的識(shí)別和標(biāo)定速度，EBSD 技術(shù)得到了廣泛推廣。如今，英國(guó)的Oxford 公司、美國(guó)的EDAX 公司和德國(guó)的Bruker 公司幾乎壟斷了EBSD 領(lǐng)域硬件和軟件的國(guó)內(nèi)外市場(chǎng)。從原理上說(shuō)，傳統(tǒng)Hough 變換算法只能識(shí)別圖像中的直線(xiàn)特征，但是EBSD 衍射幾何決定了花樣中的菊池帶具有雙曲線(xiàn)狀的邊界。 為了直接識(shí)別菊池帶的雙曲線(xiàn)邊界，Maurice 等[15]提出了一種三維Hough 變換的算法，然而這種方法依賴(lài)于準(zhǔn)確的投影源（PS）位置，并沒(méi)有從根本上解決Hough 變換結(jié)果誤差大的問(wèn)題，所以該方法并未在EBSD 實(shí)際應(yīng)用中得到推廣。相比于三維Hough 變換，傳統(tǒng)Hough 變換具有穩(wěn)定性高、不受投影源位置誤差影響等優(yōu)勢(shì)，至今上述三大廠(chǎng)商仍采用基于中央處理器（central processing unit，CPU） 的傳統(tǒng)Hough 變換識(shí)別EBSD 花樣中的菊池帶。 由于Hough 變換是一種一對(duì)多的圖像變換算法，即EBSD 花樣X(jué)-Y 坐標(biāo)系中每個(gè)像素映射到ρ-θ 坐標(biāo)系時(shí)都變成一條曲線(xiàn)， 這種映射關(guān)系決定了Hough 變換的耗時(shí)隨圖像像素?cái)?shù)量的增加呈指數(shù)級(jí)增長(zhǎng)，所以計(jì)算量大且耗時(shí)長(zhǎng)是Hough 變換算法的主要短處。 標(biāo)定已知晶體的EBSD 花樣時(shí)，Hough 變換的耗時(shí)幾乎占據(jù)了標(biāo)定的總時(shí)長(zhǎng)， 在花樣像素?cái)?shù)量少且僅識(shí)別四條不共帶軸的菊池帶情況下，目前最先進(jìn)的EBSD 商業(yè)軟件標(biāo)定速度最快可達(dá)到4×103FPS[16]，但仍遠(yuǎn)遠(yuǎn)慢于EBSD 花樣的采集速度。 此外，降低圖像的像素?cái)?shù)量雖然能顯著提高Hough 變換速度， 但會(huì)導(dǎo)致Hough 變換結(jié)果的誤差增大， 從而明顯降低EBSD 花樣標(biāo)定結(jié)果的可信度。 在不影響EBSD 花樣標(biāo)定結(jié)果的情況下，如何快速實(shí)現(xiàn)Hough 變換已成為EBSD 用戶(hù)和廠(chǎng)家共同關(guān)注并亟待解決的關(guān)鍵問(wèn)題。

計(jì)算機(jī)技術(shù)經(jīng)過(guò)近幾十年的發(fā)展，CPU 已經(jīng)成為超大規(guī)模集成電路，芯片中的晶體管數(shù)量不可能無(wú)限制增加，摩爾定律早已失效，為提高計(jì)算速度，CPU 由單核發(fā)展出多核， 但由于保留了大量的緩存，多核CPU 的計(jì)算能力依然受限。NVIDIA 公司于2006 年基于顯卡提出統(tǒng)一計(jì)算設(shè)備架構(gòu)（compute unified device architecture，CUDA）[17]，利用CUDA 可實(shí)現(xiàn)計(jì)算的高度并行化。 從硬件角度來(lái)講，目前一個(gè)CPU 至多擁有十幾個(gè)運(yùn)算核心，而顯卡中運(yùn)算核心的數(shù)量能高達(dá)幾千個(gè)， 龐大的核心數(shù)量為CUDA的并行計(jì)算提供了硬件支持，CUDA 高性能并行計(jì)算是未來(lái)的發(fā)展趨勢(shì)。

本文分別采用CPU 的多線(xiàn)程技術(shù)和CUDA 高性能并行計(jì)算技術(shù)對(duì)EBSD 花樣做Hough 變換，研究了CPU 線(xiàn)程數(shù)量、EBSD 花樣（原始圖像）像素?cái)?shù)量和Hough 變換結(jié)果圖像（目標(biāo)圖像）像素?cái)?shù)量對(duì)Hough 變換時(shí)間的影響， 從不同并行模式和顯卡安裝方式兩個(gè)角度對(duì)比了CPU 和CUDA 的Hough 變換時(shí)間，最后比較了兩者的識(shí)別結(jié)果。

1 方法

本實(shí)驗(yàn)基于容天工作站對(duì)EBSD 花樣做Hough變換，操作環(huán)境為Windows10 系統(tǒng)，編程使用C 語(yǔ)言，CPU 型號(hào)為Xeon E5-2643（6 核），顯卡型號(hào)為T(mén)esla K20c（2496 核），程序基于VS2017 軟件編寫(xiě)，CUDA 版本為10.2，圖像處理使用OpenCV 庫(kù)。

在二維圖像X-Y 平面坐標(biāo)系中， 直線(xiàn)L 的方程可以表示為

式中：k 為斜率，b 為截距。

如圖1（a）所示，連接X(jué)-Y 平面內(nèi)的任意兩點(diǎn)（A1，A2）所形成的直線(xiàn)方程如式（1）所示，過(guò)點(diǎn)O 作直線(xiàn)L 的垂線(xiàn)，垂足為A0，線(xiàn)段OA0與X 軸的夾角為θ，原點(diǎn)O 與直線(xiàn)L 的距離為ρ。 根據(jù)式（2）可以將二維圖像X-Y 坐標(biāo)系中一個(gè)點(diǎn)轉(zhuǎn)換到ρ-θ 參數(shù)坐標(biāo)系中變成一條曲線(xiàn)

圖1 Hough 變換原理圖Fig. 1 Schematic diagram of Hough transform

X-Y 坐標(biāo)系中點(diǎn)A1和點(diǎn)A2分別對(duì)應(yīng)ρ-θ 坐標(biāo)系中曲線(xiàn)a1和曲線(xiàn)a2，所以ρ-θ 坐標(biāo)系中兩條曲線(xiàn)的交點(diǎn)對(duì)應(yīng)X-Y 坐標(biāo)系中直線(xiàn)。 從圖1（b）可以看出，兩條曲線(xiàn)在點(diǎn)N 處相交，即參數(shù)坐標(biāo)系中點(diǎn)N 代表二維圖像坐標(biāo)系中的直線(xiàn)L。通過(guò)上述方式，Hough 變換將二維圖像坐標(biāo)系中直線(xiàn)映射到參數(shù)坐標(biāo)系中形成交點(diǎn)，從而把檢測(cè)任意直線(xiàn)的問(wèn)題轉(zhuǎn)化為統(tǒng)計(jì)交點(diǎn)的問(wèn)題。

本文在研究不同并行模式對(duì)Hough 變換時(shí)間的影響時(shí)，因啟動(dòng)線(xiàn)程、開(kāi)辟資源等需要消耗時(shí)間，若只統(tǒng)計(jì)一張EBSD 花樣的Hough 變換時(shí)間，其結(jié)果具有不確定性， 這里求取1 000 張EBSD 花樣的平均時(shí)間作為Hough 變換時(shí)間，減小了實(shí)驗(yàn)數(shù)據(jù)的誤差與波動(dòng)。 此外，為了保證Hough 變換結(jié)果圖像的真實(shí)性，原始圖像像素?cái)?shù)量應(yīng)該大于目標(biāo)圖像像素?cái)?shù)量。 另一方面，在探究CUDA 技術(shù)對(duì)Hough 變換時(shí)間的影響時(shí)， 顯卡與主板共有兩種連接方式，第一種是通過(guò)PCIE X16 插槽直接將顯卡連接主板，實(shí)現(xiàn)顯卡的內(nèi)置，這也是目前最常見(jiàn)的一種連接方式；第二種是外置顯卡，首先將PCIE X1 轉(zhuǎn)接口的一端連接到主板， 另一端通過(guò)USB3.0 線(xiàn)將PCIE X1 轉(zhuǎn)接板與PCIE X16 底座相連， 最后將顯卡連接到PCIE X16 底座上。 需要指出的是， 利用CUDA 對(duì)EBSD 花樣做Hough 變換，首先從CPU 端將數(shù)據(jù)傳遞到顯卡端， 然后利用CUDA 進(jìn)行計(jì)算，最后從顯卡端將計(jì)算結(jié)果回傳給CPU 端， 所以Hough 變換時(shí)間為數(shù)據(jù)傳遞時(shí)間和CUDA 運(yùn)算時(shí)間之和。

2 結(jié)果與討論

圖2 是一張EBSD 花樣及其Hough 變換的結(jié)果，從圖2（b）中可以看到每個(gè)方框中存在一個(gè)清晰的亮點(diǎn)，在亮點(diǎn)的上下兩側(cè)的箭頭所示位置存在一對(duì)黑點(diǎn)，其中每個(gè)黑點(diǎn)代表菊池帶的一條邊界。

圖2 EBSD 花樣的Hough 變換Fig.2 Hough transform of EBSD pattern

2.1 圖像像素?cái)?shù)量對(duì)運(yùn)算時(shí)間的影響

從圖3 可以看出， 利用CPU 對(duì)EBSD 花樣做Hough 變換， 隨著CPU 線(xiàn)程數(shù)量的增加，Hough 變換時(shí)間明顯減少。在CPU 線(xiàn)程數(shù)量增加至核心數(shù)量之前，Hough 變換時(shí)間減少較快， 如CPU 線(xiàn)程數(shù)量由1 增加至2 時(shí)，Hough 變換時(shí)間幾乎減小一半，這表明CPU 的多核并行計(jì)算優(yōu)勢(shì)得到了充分發(fā)揮；當(dāng)線(xiàn)程數(shù)量超過(guò)核心數(shù)量，即線(xiàn)程數(shù)量大于6，CPU 會(huì)自動(dòng)開(kāi)啟超線(xiàn)程，此時(shí)一個(gè)核心可以同時(shí)調(diào)度兩個(gè)線(xiàn)程。 若持續(xù)增加CPU 的線(xiàn)程數(shù)量，Hough 變換時(shí)間仍會(huì)減少， 但減少幅度會(huì)有所降低， 其原因是CPU 在調(diào)度線(xiàn)程時(shí)存在切換線(xiàn)程和開(kāi)辟資源等方面的時(shí)間損耗，但利用CPU 的多核技術(shù)和超線(xiàn)程技術(shù)，可以減少Hough 變換時(shí)間，加快EBSD 花樣的菊池帶識(shí)別速度。

圖3 CPU 影響Hough 變換的因素Fig.3 Factors influencing Hough transform by CPU

圖3 顯示了在同一CPU 線(xiàn)程數(shù)量情況下，不同原始圖像、 不同目標(biāo)圖像對(duì)Hough 變換時(shí)間的影響，當(dāng)原始圖像像素?cái)?shù)量或者目標(biāo)圖像像素?cái)?shù)量增加時(shí)，Hough 變換時(shí)間都會(huì)對(duì)應(yīng)增加，但兩者的增加幅度有所不同。 以1 個(gè)CPU 線(xiàn)程為例，在A(yíng) 的情況下，即原始圖像和目標(biāo)圖像像素?cái)?shù)量都為40 像素×40 像素，此時(shí)Hough 變換時(shí)間為4.8 ms。 B 與A 相比， 目標(biāo)圖像的橫向和縱向像素?cái)?shù)量都增加一倍，Hough 變換時(shí)間對(duì)應(yīng)增加一倍， 而C 相比于A(yíng) 而言， 原始圖像橫向和縱向像素?cái)?shù)量都增加一倍，Hough 變換時(shí)間增加至原來(lái)的4 倍。由此可見(jiàn)，原始圖像像素?cái)?shù)量對(duì)Hough 變換時(shí)間的影響更大，這是由Hough 變換算法決定的。 原始圖像利用二重循環(huán)掃描每個(gè)像素點(diǎn)得到對(duì)應(yīng)坐標(biāo)，原始圖像橫向和縱向的像素?cái)?shù)量都增加一倍，即X 軸方向和Y 軸方向上像素?cái)?shù)量均增加一倍，掃描所需的工作量增大至原來(lái)的4 倍；目標(biāo)圖像僅通過(guò)一重循環(huán)掃描θ 軸方向的坐標(biāo)，然后利用式（2）求解得出ρ 軸方向的坐標(biāo)，即ρ 軸不需要通過(guò)循環(huán)求解。 所以當(dāng)目標(biāo)圖像橫向和縱向的像素?cái)?shù)量都增加一倍時(shí)，掃描所需的工作量只增加一倍。 D 與A 相比，同時(shí)增加原始圖像和目標(biāo)圖像的像素?cái)?shù)量，Hough 變換時(shí)間大幅增加。 綜上所述，CPU 線(xiàn)程數(shù)量越多，圖像像素?cái)?shù)量越少，Hough 變換時(shí)間越短。

結(jié)合圖3 所示CPU 的Hough 變換數(shù)據(jù)， 表1給出了CPU 與CUDA 的詳細(xì)對(duì)比， 無(wú)論是原始圖像還是目標(biāo)圖像，圖像像素?cái)?shù)量增加，Hough 變換時(shí)間均增加。需要指出的是，CUDA 的加速比與圖像像素?cái)?shù)量有關(guān)，表中第1 行與第3 行的數(shù)據(jù)給出了原始圖像像素?cái)?shù)量對(duì)CPU 時(shí)間、CUDA 時(shí)間和加速比的影響。 當(dāng)原始圖像像素?cái)?shù)量由40×40 增加至80×80 時(shí)，CPU 時(shí)間從0.56 ms 增加至2.19 ms，CUDA時(shí)間從0.056 ms 增加至0.087 ms， 加速比從10 增加至25.17， 可見(jiàn)原始圖像像素?cái)?shù)量增加，CUDA 的加速比增大；第1 行與第2 行的數(shù)據(jù)相比，目標(biāo)圖像像素?cái)?shù)量從40×40 增加至80×80，CPU 時(shí)間和CUDA 時(shí)間都增加， 但加速比從10 降低至7.71，CUDA 的加速程度減小。綜合分析，當(dāng)圖像像素?cái)?shù)量增加時(shí)，CPU 時(shí)間和CUDA 時(shí)間均增加； 原始圖像像素?cái)?shù)量增加，CUDA 的加速比增大，目標(biāo)圖像像素?cái)?shù)量增加，CUDA 的加速比減小。 同理，第1 行與第4 行數(shù)據(jù)相比， 原始圖像像素?cái)?shù)量和目標(biāo)圖像像素?cái)?shù)量均增加，CUDA 的加速比為21.06，處于7.71 至25.17 區(qū)間內(nèi)，符合上述推斷。

表1 CPU 與CUDA 的Hough 變換時(shí)間對(duì)比Tab.1 Comparison of Hough transform time between CPU and CUDA

2.2 不同并行模式下Hough 變換時(shí)間的對(duì)比

如圖4 所示，同一像素?cái)?shù)量的情況下，與CPU相比，基于CUDA 的Hough 變換速度更快，原因是顯卡的線(xiàn)程數(shù)量明顯多于CPU 的線(xiàn)程數(shù)量。

另外， 從圖4 中還可以看出， 基于CPU 的Hough 變換時(shí)間隨原始圖像像素?cái)?shù)量增加呈指數(shù)級(jí)增長(zhǎng)， 這與圖3 所示的CPU 實(shí)驗(yàn)結(jié)果一致。 基于CUDA 進(jìn)行Hough 變換，因原始圖像中一個(gè)像素對(duì)應(yīng)CUDA 中一個(gè)線(xiàn)程， 所以增加原始圖像像素?cái)?shù)量，基于CUDA 的Hough 變換時(shí)間近似呈線(xiàn)性關(guān)系增長(zhǎng)。 此外，目標(biāo)圖像像素?cái)?shù)量增加，θ 軸方向上掃描工作量對(duì)應(yīng)增加，ρ 軸方向上掃描工作量無(wú)影響，所以CPU 和CUDA 的Hough 變換時(shí)間均近似呈線(xiàn)性關(guān)系增長(zhǎng)。

圖4 不同并行模式下Hough 變換時(shí)間的對(duì)比Fig.4 Comparison of Hough transform time under different parallel modes

2.3 顯卡安裝方式對(duì)CUDA 的Hough 變換時(shí)間影響

一般來(lái)說(shuō)，顯卡數(shù)量越多，程序的計(jì)算能力越強(qiáng)，通常主板上的顯卡插槽數(shù)量有限，內(nèi)置顯卡的方式滿(mǎn)足不了日益增長(zhǎng)的計(jì)算需求，可通過(guò)外置方式將顯卡與主板連接。

實(shí)驗(yàn)結(jié)果如圖5 所示，無(wú)論是內(nèi)置顯卡還是外置顯卡，隨著圖像像素?cái)?shù)量增加，Hough 變換時(shí)間均對(duì)應(yīng)增加。 但需注意的是，外置顯卡的Hough 變換時(shí)間約為內(nèi)置顯卡的兩倍，而兩者的Hough 變換計(jì)算時(shí)間相同，時(shí)間差距主要在CPU 端到顯卡端的數(shù)據(jù)傳遞環(huán)節(jié)，可以推斷，外置顯卡雖會(huì)降低數(shù)據(jù)的傳遞速度，但并未影響CUDA 的計(jì)算速度。 另外還可以發(fā)現(xiàn)，基于CUDA 的Hough 變換時(shí)間主要消耗在數(shù)據(jù)傳遞環(huán)節(jié)， 計(jì)算環(huán)節(jié)并未占用過(guò)多時(shí)間，這說(shuō)明顯卡的并行計(jì)算能力并沒(méi)有得到充分發(fā)揮，所以本實(shí)驗(yàn)的程序還存在一定的優(yōu)化空間。

圖5 顯卡安裝方式對(duì)CUDA 的Hough 變換時(shí)間影響Fig.5 Influence of graphics card installation mode on CUDA Hough transform time

由此可見(jiàn)，利用CUDA 高性能并行計(jì)算技術(shù)可以大幅度減少Hough 變換時(shí)間，提高EBSD 花樣中菊池帶的識(shí)別速度。 在內(nèi)置顯卡的情況下，原始圖像像素?cái)?shù)量和目標(biāo)圖像像素?cái)?shù)量均為40×40， 基于CUDA 的Hough 變換總時(shí)間為0.056 ms， 即EBSD花樣中菊池帶的識(shí)別速度最快可達(dá)到1.7×104FPS。這已遠(yuǎn)遠(yuǎn)超過(guò)Oxford 公司商業(yè)軟件4×103FPS 的識(shí)別速度，基于CUDA 的Hough 變換將成為快速識(shí)別EBSD 花樣菊池帶的一個(gè)發(fā)展趨勢(shì)。

2.4 不同并行模式下EBSD 花樣的識(shí)別對(duì)比

從上述實(shí)驗(yàn)結(jié)果可知，基于CUDA 的Hough 變換速度遠(yuǎn)遠(yuǎn)快于CPU，本實(shí)驗(yàn)對(duì)比了CPU 與CUDA的菊池帶識(shí)別結(jié)果。 菊池帶上的數(shù)字代表Hough 變換結(jié)果的最強(qiáng)峰順序，即Hough 變換結(jié)果的峰值越強(qiáng)，菊池帶特征越明顯，EBSD 花樣所對(duì)應(yīng)的菊池帶序號(hào)越小，結(jié)果如圖6 所示。

圖6（e）與圖6（i），圖6（f）與圖6（j）相比，兩種并行模式的菊池帶識(shí)別順序完全一致，識(shí)別結(jié)果無(wú)明顯差異；圖6（g）和圖6（k）所示的菊池帶識(shí)別順序有所不同，具體表現(xiàn)為5 號(hào)菊池帶和6 號(hào)菊池帶的識(shí)別順序相反，這說(shuō)明兩種并行模式Hough 變換結(jié)果圖像的菊池帶特征強(qiáng)弱程度相反；圖6（h）與圖6（l）相比，兩種并行模式識(shí)別的6 號(hào)菊池帶并非同一條菊池帶，但可以肯定的是，兩條6 號(hào)菊池帶都是清晰存在的。 另一方面，從Hough 變換結(jié)果圖像上分析，圖6（a）～圖6（d）與圖6（m）～圖6（p）的對(duì)比可知，CPU 與CUDA 對(duì)同一張EBSD 花樣的Hough變換結(jié)果沒(méi)有可見(jiàn)的差異。 綜上所述，CPU 與CUDA 雖在菊池帶識(shí)別細(xì)節(jié)方面有輕微差異， 但最終兩者的識(shí)別結(jié)果基本相當(dāng)。

圖6 4 張EBSD 花樣中菊池帶的識(shí)別結(jié)果Fig.6 Identification results of Kikuchi bands in four EBSD patterns

3 結(jié)論

本文分別使用CPU 與CUDA 對(duì)EBSD 花樣做Hough 變換，研究了圖像像素?cái)?shù)量、不同并行模式和顯卡安裝方式對(duì)Hough 變換時(shí)間的影響，最后比較了兩者的EBSD 花樣識(shí)別結(jié)果，主要結(jié)論如下。

1） CPU 線(xiàn)程數(shù)量增加，Hough 變換時(shí)間減少；圖像像素?cái)?shù)量增加，CPU 與CUDA 的Hough 變換時(shí)間均增加。

2） CPU 的原始圖像像素?cái)?shù)量與Hough 變換時(shí)間呈指數(shù)關(guān)系增長(zhǎng)，目標(biāo)圖像像素?cái)?shù)量與Hough 變換時(shí)間近似呈線(xiàn)性關(guān)系增長(zhǎng)；CUDA 的原始圖像像素?cái)?shù)量與目標(biāo)圖像素?cái)?shù)量均與Hough 變換時(shí)間近似呈線(xiàn)性關(guān)系增長(zhǎng)。

3） 內(nèi)置顯卡和外置顯卡的Hough 變換計(jì)算時(shí)間幾乎完全相同，但外置顯卡的Hough 變換總時(shí)間約為內(nèi)置顯卡的兩倍，原因在于CPU 端到外置顯卡端的數(shù)據(jù)傳遞需要較長(zhǎng)時(shí)間。

4） CPU 與CUDA 的菊池帶識(shí)別結(jié)果沒(méi)有本質(zhì)區(qū)別，但CUDA 的菊池帶識(shí)別速度遠(yuǎn)遠(yuǎn)快于CPU。