關(guān)鍵詞：標(biāo)靶定位;OpenCL;迭代最近點(diǎn);GPU

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A

0 引言（Introduction）

平面標(biāo)靶即人工標(biāo)志物，在三維重建點(diǎn)云拼接[1]及大型建筑監(jiān)測中發(fā)揮了重要的作用[2-3]。將平面標(biāo)靶安置于基坑、堤壩、隧道等表面，并利用相機(jī)監(jiān)控平面標(biāo)靶的位置，可有效實(shí)現(xiàn)預(yù)警預(yù)測功能。

國內(nèi)外學(xué)者使用的標(biāo)靶定位方法有許多，高超等[4]使用最小二乘法將圓形標(biāo)靶輪廓擬合成橢圓形，并通過相關(guān)幾何變換進(jìn)行定位，該方法在2 m拍攝距離下能達(dá)到0.1 mm的測量精度。何華等[5]針對激光掃描儀圓形平面標(biāo)靶，首先，擬合標(biāo)靶的最佳平面，其次，利用凸包算法提取標(biāo)靶邊緣點(diǎn)，最后，使用抗差最小二乘法求解標(biāo)靶的中心坐標(biāo)，中心定位精度達(dá)到0.4 mm。OLASZEK[6]通過圖像梯度檢測“十”字形標(biāo)靶的邊緣，計(jì)算邊緣坐標(biāo)的算術(shù)平均值，并將其作為目標(biāo)位置，校正后的平均誤差為0.4 pixel。RIBEIRO等[7]通過亮度閾值檢測正方形標(biāo)靶的邊緣并計(jì)算交點(diǎn)的坐標(biāo)，精度約為0.7 pixel。

針對現(xiàn)有的標(biāo)靶定位方法精度不高、效率較慢及同時(shí)定位數(shù)量少的問題，本文提出一種基于OpenCL的多標(biāo)靶加速定位方法，使用邊緣檢測方法獲得當(dāng)前圖像中標(biāo)靶的二維邊緣點(diǎn)集;使用已知現(xiàn)實(shí)標(biāo)靶參數(shù)建立模板點(diǎn)集;使用二維ICP迭代尋找模板邊緣點(diǎn)集與當(dāng)前邊緣點(diǎn)集的最近點(diǎn);使用OpenCL框架并行計(jì)算，修改迭代停止條件，以減少迭代次數(shù)并加快收斂速度，實(shí)現(xiàn)多標(biāo)靶實(shí)時(shí)定位。

1 標(biāo)靶中心定位（Target center positioning algorithm）

本文使用的標(biāo)靶參數(shù)如圖1所示，標(biāo)靶定位方法流程如圖2所示，包括圖像預(yù)處理、邊緣檢測、邊緣點(diǎn)云預(yù)處理等。

1.1 圖像預(yù)處理及標(biāo)靶邊緣檢測

工業(yè)相機(jī)采集到的標(biāo)靶如圖3（a）所示。在實(shí)際圖像采集中，環(huán)境條件的變化常引入椒鹽噪聲、高斯噪聲等干擾。為了減少這些噪聲對邊緣檢測的不利影響，本文方法先使用中值濾波進(jìn)行去噪，再使用Canny算子進(jìn)行邊緣檢測，檢測結(jié)果如圖3（b）所示。

1.2ICP點(diǎn)云配準(zhǔn)

迭代最近點(diǎn)（Iterative Closest Point，ICP）算法[8]是目前使用廣泛的點(diǎn)云配準(zhǔn)算法之一，在三維重建、無人駕駛等領(lǐng)域得到廣泛運(yùn)用。傳統(tǒng)的二維ICP算法大致如下：首先對輸入的目標(biāo)點(diǎn)云構(gòu)建二叉樹數(shù)據(jù)結(jié)構(gòu)，進(jìn)行兩幅點(diǎn)云之間的最近點(diǎn)尋找，對于待配準(zhǔn)點(diǎn)云的每一個(gè)點(diǎn)，尋找出在目標(biāo)點(diǎn)云中的最鄰近點(diǎn)，也就是歐氏距離最短的點(diǎn);其次根據(jù)尋找出的鄰近點(diǎn)對求解最優(yōu)變換，求得旋轉(zhuǎn)矩陣R 與平移矩陣T;最后將剛體變換矩陣作用于待配準(zhǔn)點(diǎn)云，計(jì)算新的待配準(zhǔn)點(diǎn)云與目標(biāo)點(diǎn)云之間的誤差，若誤差滿足最終迭代停止條件，則輸出矩陣與變換后的待配準(zhǔn)點(diǎn)云，否則繼續(xù)迭代，ICP算法流程如圖4所示。

ICP的本質(zhì)是最小化兩幅點(diǎn)云之間的誤差，該誤差通常是每個(gè)點(diǎn)對之間的歐氏距離，也可以是別的誤差度量。ICP求解最優(yōu)剛性變換的基本步驟如下。

1.3 基于ICP的標(biāo)靶中心定位

在獲得當(dāng)前圖像中的標(biāo)靶邊緣后，為了定位標(biāo)靶中心，需要根據(jù)現(xiàn)有的邊緣信息找到標(biāo)靶的圓心。由于標(biāo)靶是二維平面且理想情況下標(biāo)靶與CCD（Charge-Coupled Device）相機(jī)靶面平行，所以使用預(yù)制的模板點(diǎn)云與當(dāng)前獲得的標(biāo)靶邊緣點(diǎn)云進(jìn)行二維迭代最近點(diǎn)，得到的剛性變換矩陣，即可定位當(dāng)前的標(biāo)靶坐標(biāo)。

1.3.1 點(diǎn)云預(yù)處理

在本文中，目標(biāo)點(diǎn)云是通過工業(yè)相機(jī)拍攝標(biāo)靶，然后使用亞像素邊緣檢測得到二維邊緣點(diǎn)云T，點(diǎn)云數(shù)量為n，點(diǎn)云坐標(biāo)單位為像素。待配準(zhǔn)點(diǎn)云為通過已知的標(biāo)靶圖案幾何參數(shù)預(yù)制的模板點(diǎn)云S ，模板點(diǎn)云的外圓直徑為d，內(nèi)圓半徑為r，點(diǎn)云數(shù)量為m，其中心點(diǎn)為原點(diǎn)，預(yù)制的二維模板點(diǎn)云圖如圖5所示。

2 基于OpenCL的ICP加速算法實(shí)現(xiàn)（Acceleratedimplementation of ICP based on OpenCL）

僅用CPU運(yùn)算ICP算法定位標(biāo)靶，隨著標(biāo)靶數(shù)量的增多，計(jì)算時(shí)間隨之增加，從而無法滿足實(shí)時(shí)性處理的需求。圖形處理單元GPU、開放運(yùn)算語言O(shè)penCL、計(jì)算機(jī)視覺與計(jì)算機(jī)圖形學(xué)的發(fā)展，為處理大數(shù)據(jù)量的問題提供了通用、高性能的并行計(jì)算環(huán)境。與CUDA（Compute Unified Device Architecture）只能運(yùn)行在英偉達(dá)圖形處理器（NVIDIA GPU ）上相比，OpenCL可以運(yùn)行在包括NVIDIA（英偉達(dá)）、AMD（Advanced MicroDevices）、ARM（Arm Limited）的眾多硬件廠商生產(chǎn)的計(jì)算設(shè)備上，具有較高的可移植性。此外，OpenCL定義了豐富的API（Application Programming Interface），使開發(fā)者能高效利用異構(gòu)計(jì)算資源，從而有效解決實(shí)時(shí)定位問題。通常，ICP之中搜尋最鄰近點(diǎn)對的算法有KD-tree（K-Dimension Tree）、VP-tree（Vantage Point Tree）等，KD-tree是其中應(yīng)用較為廣泛的數(shù)據(jù)結(jié)構(gòu)。但是，傳統(tǒng)的KD-tree存在無效節(jié)點(diǎn)搜索過多導(dǎo)致的查詢效率不穩(wěn)定問題[9-10]，所以本文采用VP-tree搜尋最鄰近點(diǎn)算法代替?zhèn)鹘y(tǒng)的KD-tree搜尋算法。

VP-Tree是一種用于支持度量空間中高效最近鄰搜索的數(shù)據(jù)結(jié)構(gòu)，是一棵基于連續(xù)距離函數(shù)的二叉平衡樹[11]。VP-tree不僅對低維度、點(diǎn)數(shù)目較少的點(diǎn)集有很好的搜索性能，而且不依賴數(shù)據(jù)的分布形式，查詢性能比KD-tree更穩(wěn)定，其基本思想是選擇一個(gè)優(yōu)勢點(diǎn)，然后基于與該點(diǎn)的距離，將數(shù)據(jù)點(diǎn)集合分成兩部分，即距離參照點(diǎn)較近的點(diǎn)和距離參照點(diǎn)較遠(yuǎn)的點(diǎn)。每個(gè)子集都可以用相同的方法遞歸地構(gòu)建子樹，從而形成一個(gè)二叉樹。

2.3 GPU下的ICP算法

上文構(gòu)造的VP-tree雖然能大大加快數(shù)據(jù)搜索的速度，但是通常情況下，點(diǎn)集中點(diǎn)的數(shù)量成千上萬，在CPU中搜尋速度非常緩慢。為了提高ICP的迭代搜尋速度，將兩組點(diǎn)集的去質(zhì)心化、VP-tree的最鄰近搜索算法、點(diǎn)集矩陣變換、點(diǎn)集之間的歐氏距離計(jì)算等，都傳入GPU中并行計(jì)算，根據(jù)點(diǎn)集的大小，動(dòng)態(tài)設(shè)置全局尺寸，以最快的速度完成點(diǎn)集變換及計(jì)算。

在傳統(tǒng)ICP算法中，初始矩陣起著關(guān)鍵作用，初始矩陣決定了迭代次數(shù)及配準(zhǔn)精度[12]。一般情況下，初始矩陣通常設(shè)置為單位矩陣，在兩個(gè)點(diǎn)集距離較遠(yuǎn)或者相似度不高的情況下，會(huì)嚴(yán)重影響配準(zhǔn)速度及精度。因此，本文算法在傳統(tǒng)ICP算法的基礎(chǔ)上進(jìn)行改進(jìn)，由于在位移監(jiān)控應(yīng)用場景下的標(biāo)靶位置大多數(shù)為線性變化或靜止?fàn)顟B(tài)，將每次配準(zhǔn)的剛性變換矩陣應(yīng)用到下次配準(zhǔn)的初始矩陣，對待配準(zhǔn)點(diǎn)集進(jìn)行粗配準(zhǔn)，可以有效減少迭代次數(shù)。

此外，傳統(tǒng)的迭代停止條件為兩個(gè)點(diǎn)集的誤差小于某個(gè)閾值就停止迭代。由于檢測的標(biāo)靶邊緣點(diǎn)集與人工預(yù)制的模板點(diǎn)集并非完美重合，該閾值在不同應(yīng)用場景下并非通用，若閾值太大，配準(zhǔn)精度將降低，若閾值太小，即使達(dá)到了最優(yōu)配準(zhǔn)位置，其誤差仍然高于這個(gè)很小的閾值，導(dǎo)致迭代無法停止。因此，將傳統(tǒng)的迭代停止條件改為此次迭代誤差與上次迭代誤差的差值小于某個(gè)閾值，改進(jìn)后的算法將大幅降低迭代次數(shù)，減少計(jì)算時(shí)間，提高系統(tǒng)的實(shí)時(shí)性。

本文采用的GPU加速ICP算法流程如圖7所示，具體步驟如下。

（1）在CPU中建立關(guān)于目標(biāo)點(diǎn)集Q（當(dāng)前檢測點(diǎn)云）的VPtree，其中包含子節(jié)點(diǎn)和葉節(jié)點(diǎn)。

（2）將模板點(diǎn)集P、目標(biāo)點(diǎn)集Q以及VP-tree的葉節(jié)點(diǎn)、子節(jié)點(diǎn)傳輸?shù)紾PU緩沖區(qū)中。

（3）使用OpenCL的API進(jìn)行各種初始化操作，例如查詢平臺(tái)、創(chuàng)建上下文、創(chuàng)建命令隊(duì)列、創(chuàng)建內(nèi)存對象等。

（4）根據(jù)數(shù)據(jù)集大小劃分點(diǎn)集數(shù)據(jù)，使其并行執(zhí)行最鄰近點(diǎn)搜索算法（ICP）。

（5）ICP在GPU中的去質(zhì)心化、VP-Tree的最鄰近搜索算法、點(diǎn)集矩陣變換、點(diǎn)集之間的歐氏距離計(jì)算皆由內(nèi)核程序完成計(jì)算，減少GPU與CPU的傳輸耗時(shí)。

（6）完成迭代計(jì)算后，將最后的剛體變換矩陣與配準(zhǔn)誤差輸出至CPU。

3 實(shí)驗(yàn)分析（Experimental analysis）

為了驗(yàn)證本文采用的多標(biāo)靶定位方法，比較改進(jìn)前后的標(biāo)靶ICP定位算法效率，以及CPU和GPU環(huán)境下的標(biāo)靶定位算法效率，本文通過設(shè)計(jì)不同的實(shí)驗(yàn)驗(yàn)證算法效率及本文算法的精度。實(shí)驗(yàn)的系統(tǒng)環(huán)境為Ubuntu 22.04，硬件環(huán)境為四核64位CPU，采用4*Cortex-A76核心，主頻為2.4 GHz，GPU 為Mali-G610 MP4。相機(jī)為“?？怠盡V-CE200-10UC，2 000萬像素CMOS工業(yè)相機(jī)。實(shí)驗(yàn)分別對1～20幅標(biāo)靶進(jìn)行算法效率測試，為了有效比較CPU和GPU環(huán)境下的標(biāo)靶定位算法效率差異，在CPU使用多線程進(jìn)行多幅標(biāo)靶的并行計(jì)算。實(shí)驗(yàn)的模板點(diǎn)集點(diǎn)數(shù)量為1 890個(gè)，檢測到的單個(gè)標(biāo)靶邊緣點(diǎn)集點(diǎn)數(shù)量平均為1 800個(gè)，設(shè)置最大迭代次數(shù)為200次，此次迭代誤差與上次迭代誤差的差值閾值設(shè)置為1×10^-6，誤差閾值設(shè)置為1×10^-5。相機(jī)采集20個(gè)標(biāo)靶圖像（圖8），測量距離約為1.4 m，單個(gè)標(biāo)靶像素的半徑大約為4aAbHUB4onFzfxLB0cB+BFuMcBGmikhjiKJ0xiYskCs0=7 pixel，物理半徑為30 mm，像素當(dāng)量約為0.63 mm/pixel。為了驗(yàn)證本文算法的定位精度，采用千分位移臺(tái)對其中一個(gè)標(biāo)靶進(jìn)行X 方向的階梯型位移測試，位移臺(tái)的最小刻度為0.01 mm，精度為0.01 mm。

圖9為單個(gè)標(biāo)靶定位的迭代耗時(shí)，在CPU和GPU中迭代70次分別需要耗時(shí)4 700 ms和360 ms，在GPU中迭代定位單個(gè)標(biāo)靶時(shí)，使用OpenCL框架在GPU中的計(jì)算時(shí)間相較于CPU，大約減少了92%。優(yōu)化后的ICP算法通過繼承先前時(shí)刻的剛性變換矩陣，減少了迭代計(jì)算時(shí)間，實(shí)現(xiàn)了連續(xù)的快速定位。圖10為不同標(biāo)靶數(shù)量定位單次耗時(shí)，即4種算法進(jìn)行單次標(biāo)靶定位的計(jì)算時(shí)間，在GPU環(huán)境下，本文的改進(jìn)算法有著明顯優(yōu)勢。由表1可以看出，本文算法針對標(biāo)靶數(shù)量小于3個(gè)且進(jìn)行連續(xù)配準(zhǔn)定位時(shí)，CPU 和GPU 的耗時(shí)相差無幾，這是因?yàn)樵贑PU環(huán)境中采用了多線程，同時(shí)CPU需要將數(shù)據(jù)傳輸至GPU，這個(gè)過程相對耗時(shí)。隨著標(biāo)靶數(shù)量增加，傳統(tǒng)ICP定位算法中CPU耗時(shí)顯著增長，且與GPU的耗時(shí)差距逐漸擴(kuò)大，凸顯出在處理大量標(biāo)靶時(shí)，GPU的性能優(yōu)勢更為顯著。使用改進(jìn)后的ICP定位算法，耗時(shí)大幅降低，幾乎可以達(dá)到實(shí)時(shí)定位。

為了驗(yàn)證算法的精度，對其中固定在位移臺(tái)上的標(biāo)靶進(jìn)行位移跟蹤檢測，將第一幀定位得到的位置設(shè)為初始值，后續(xù)的定位位置都減去初始值。使用千分位移臺(tái)對此標(biāo)靶進(jìn)行X 方向的階梯型位移，在91 s、199 s、318 s處施加X 正方向的0.1 mm位移，在407 s、513 s、602 s處施加X 負(fù)方向的0.1 mm位移，測量結(jié)果如圖11所示。經(jīng)計(jì)算，平均絕對誤差約為0.026 1 mm，定位精度約為0.05 mm，即0.081 9 pixel。

綜上所述，改進(jìn)的ICP算法在GPU上相較于CPU在處理多個(gè)標(biāo)靶時(shí)具有顯著的時(shí)間效率優(yōu)勢，尤其是在標(biāo)靶數(shù)量較多時(shí)。在GPU中連續(xù)定位20個(gè)標(biāo)靶僅需要1.2 s左右一次，算法的首次定位耗時(shí)僅為CPU中的19%，后續(xù)連續(xù)定位時(shí)間也展現(xiàn)出顯著的時(shí)間優(yōu)勢，并且定位精度可以滿足系統(tǒng)定位要求。

4 結(jié)論（Conclusion）

本文提出一種基于OpenCL的多標(biāo)靶加速定位方法，使用ICP尋找最優(yōu)配準(zhǔn)位置，定位最佳標(biāo)靶中心。相較于通過幾何形狀進(jìn)行標(biāo)靶定位的傳統(tǒng)算法，本文算法更精確且具有魯棒性。本文在定位方法的實(shí)現(xiàn)上進(jìn)行了改進(jìn)，采用VP-tree的數(shù)據(jù)結(jié)構(gòu)，使用OpenCL框架并行計(jì)算，并且使下一時(shí)刻的邊緣點(diǎn)云繼承上一時(shí)刻的剛性變換矩陣，改進(jìn)了迭代停止條件。與傳統(tǒng)ICP實(shí)現(xiàn)算法相比，減少了迭代次數(shù)并加快了收斂速度，在一定程度上提高了算法效率及精度，滿足了一般應(yīng)用場景的實(shí)時(shí)性需求。但是，本文算法中沒有考慮到噪聲邊緣點(diǎn)的干擾，沒有進(jìn)行錯(cuò)誤對應(yīng)點(diǎn)去除，因此接下來需要對噪聲邊緣點(diǎn)處理進(jìn)行改進(jìn)，繼續(xù)完善ICP算法中的點(diǎn)云預(yù)處理，提升配準(zhǔn)的魯棒性。

作者簡介：

王瑾瑜（1999-），男，碩士生。研究領(lǐng)域：機(jī)器視覺。

羅劍波（1975-），男，博士，講師。研究領(lǐng)域：光電精密檢測，激光直寫。