面向無人機巡檢的多圖像間重復缺陷自動篩查

陳 帥

（中海廣東天然氣有限責任公司 廣東 珠海 519015）

0 引言

巡檢無人機自主規(guī)劃巡檢路徑對輸電線路桿塔進行巡檢和拍攝后，對拍攝圖像進行實時分析診斷，并自動統(tǒng)計輸出巡檢過程中發(fā)現(xiàn)的缺陷。但存在單個缺陷點反復統(tǒng)計的問題，造成統(tǒng)計種類及數(shù)量遠大于真實情況，嚴重影響巡檢報告的真實性，具體原因是因為同一個缺陷在多個圖像中都會被拍攝并統(tǒng)計[1]。

聚類算法是機器學習的核心任務之一。聚類的目標是把相似的數(shù)據(jù)點劃分到同一個簇中，并最終得到劃分完成的多個簇，根據(jù)簇的數(shù)量可以將數(shù)據(jù)點分為不同的類別。其在機器學習領域上有規(guī)范的應用。對于空間中的三維點云數(shù)據(jù)，通過聚類算法，也能夠進行劃分，得到對應數(shù)量的簇，以此判斷三維點云所代表的三維物體數(shù)量。

K-means 聚類算法為當下最為直觀和方便使用的聚類算法。Ball 和Hall[2]發(fā)明了ISODATA 技術進行k 值的估算，動態(tài)調整集群的數(shù)量k。Figueiredo 和Jain 使用最小信息長度準則并結合高斯混合模型，對k 值進行估計。針對手肘法確定k 值過程中存在的“肘點”位置不明確問題，基于指數(shù)函數(shù)特點、權重調整、偏執(zhí)項及手肘法基本思想，提出了一種改進的k 值選擇算法ET-SSE 算法，但k 值選擇的效果由受到其引入的權重調整變量的影響，在實際場景中需要不斷實驗才能得到優(yōu)于基本手肘法的效果 。

由于means 算法只收斂于局部最小值，因此聚類有可能無法得到全局最優(yōu)結果。為克服這個問題，需要對集群的初始化進行改進。K-means 算法常用歐式距離度量點與聚類中心的距離。利用馬氏距離能夠優(yōu)化K-means 聚類在超橢球集群的度量，但會帶來極高的計算成本，鑒于以上分析的困難，尋找合適的方法與計算技巧是本研究的核心目的。

1 研究目標

對無人機拍攝的多圖像間重復目標進行篩查和定位，靠人工對圖像進行核查是十分耗時耗力的，因此通過建立航拍圖片位姿信息獲取、三維數(shù)據(jù)重建、聚類計算等流程，研發(fā)了“面向輸電線路巡檢的多圖像間重復缺陷自動篩查組件”，以實現(xiàn)對重復缺陷的準確篩查和定位。

（1）在方案步驟中，“讀取圖像并分類”與“三維數(shù)據(jù)重建分析”部分作為已經完成的研究工作，直接為本文提供圖像資料源。如圖1 所示

（2）結合已經獲取的圖像資料，研究三維點云的K-means 聚類，通過對空間中點云的聚類劃分以及聚類結果的評估，對多圖像間同類型缺陷在空間中的實際數(shù)量得到初步結果。

（3）研究三維聚類結果與二維缺陷圖片的關系映射，結合先前研究獲得的約束條件，計算準確得多圖像間同類型缺陷的實際數(shù)量，并輸出得到結果[3]。

2 聚類計算

2.1 技術原理

2.1.1 K-means clustering algorithm（聚類算法）

K-means 聚類算法屬于聚類算法中的一種，其本質是通過迭代的方式把數(shù)據(jù)對象歸于不同的簇里面去，然后求極值。其算法的大致思想為：先從數(shù)據(jù)集中選取K個樣本作為簇中心，后驗算所有樣本點至各個簇的中心之間的間距，再將每個樣本劃分到與其距離最近的簇中心中，對于得到的新的簇，再次計算新的“簇-中心”[4]。

根據(jù)上述描述，可知實現(xiàn)means 算法，主要有如下三點：

（1）簇個數(shù)k 的選擇

（2）各個樣本點到“簇中心”的距離

（3）根據(jù)新劃分的簇，更新“簇中心”

對于不同圖片上的缺陷區(qū)域，總會存在一點，使其投影回圖片上時，會在對應的缺陷區(qū)域內。不同圖片相同缺陷所產生的點，其空間位置應是接近的，而不同圖片不同缺陷所產生的點，則會出現(xiàn)很大偏差。因此，通過means聚類，就能判斷生成的空間點，是否為同一拍攝缺陷所產生的點。

首先，運用“肘”方法確定k 值。

其次，距離的度量：

閔氏距離（Minkowski distance）：

歐氏距離（Euclidean distance），即當p=2 時的閔可夫斯基距離：

曼哈頓距離（Manhattan distance），即當p=1 時的閔可夫斯基距離：

最后，更新“簇中心”，對于劃分好的各個簇，計算各個簇中的樣本點均值，將其均值作為新的簇中心。

2.1.2 聚類效果評估

傳統(tǒng)K-means 聚類算法由于需要提前設定k值，因此需要在使用時，對不同k值下的聚類進行評估，從而判斷合適的k值。對于K-means 聚類效果評估的辦法，常見的為手肘法和輪廓度系數(shù)。肘方法為計算聚類的誤差平方和，按照肘方法理論進行分析和計算如圖2 所示，k取4 時曲率最高，故對于這個數(shù)據(jù)集的聚類而言，最佳聚類數(shù)應該選4。

輪廓度系數(shù)法對每個k值下聚類簇中的成員點，計算其輪廓系數(shù)。具體為：

對于第k個聚類下的點Pi來說，有：

其中，size（i，k）為第k個聚類排除點Pi的情況下成員點數(shù)量，dis(i，j)為點Pi與Pj的歐式距離。由此，a(i，k)的物理意義為：點Pi到第k個簇的所有點的距離的平均值，b(i)為點Pi到所有非所在簇的平均距離的最小值。S(i)即可表示點Pi的輪廓系數(shù)，所有樣本點的輪廓系數(shù)均值，即可表示為當前k聚類下的輪廓度系數(shù)。

2.2 技術方案

對于聚類計算的研究，具體技術路線為圖3 所示。首先根據(jù)缺陷圖像和三維點云，初步估計K值可能的范圍，其次遍歷范圍內的K值，對三維點云進行means 聚類。然后對不同k值下的結果，進行評估。最后根據(jù)評估的結果，選出最合適的k值，并得到該k值下的聚類結果，并根據(jù)k得到初步的實際缺陷數(shù)量判斷。

根據(jù)聚類計算的研究現(xiàn)狀、技術原理、技術路線以及實際實驗的情況，設計并實現(xiàn)了聚類分析模塊，其功能為根據(jù)點云和缺陷圖片，進行means 聚類計算，并比較不同k值下聚類的結果，選取最符合的k值為聚類數(shù)，并獲得對應k值下的聚類簇，以此作為初步的實際缺陷數(shù)量判斷。

2.2.1k值范圍

由于需要對多個不同的k值進行聚類計算，以此若能夠初步確定k值的范圍，便能夠減少許多不必要的計算。根據(jù)缺陷圖像中每張圖像上同類型缺陷的數(shù)量，可以得到k值的下限Kmin:

其中，Pic(n)為第n張圖片下對應缺陷類型的缺陷數(shù)量。同理，可計算k值的上限jmax

其中size為點云的點數(shù)量，each為兩圖片的兩個缺陷計算可靠三維點時，加入到點集進行聚類計算的點數(shù)量。由此可得到聚類的上限值。但在實驗中發(fā)現(xiàn)中，jmax的值仍會偏大，因此在實際使用中，會選取一個合適的數(shù)組，代替jmax，作為k值選取范圍的上界。

2.2.2 中心點打靶

進行means 迭代運算前，需要進行初始聚類中心點的選取，由于傳統(tǒng)means 聚類容易陷入局部最優(yōu)解的情況，因此需要通過合理的初始聚類中心點選取方式，避免在聚類過程中出現(xiàn)情況。因此，設計如下步驟，獲得較好的初始聚類中心點：

（1） 計算點集P中各個點之間的距離

（2）選取點間距最大的兩個點p1，p2，作為初始的兩個聚類中心點，并從P中剔除p1，p2，放入聚類中心點集Pf。

（3）for 2

2.2.3 實現(xiàn)流程

means 聚類算法通過設置初值K，假設點集中聚類的個數(shù)，并以此尋找合適的K個點作為初始點后進行means聚類，從而得到有K個聚類時的聚類結果。對于該算法，其大致步驟為：

（1）獲得圖片集中關于某一缺陷類別生成的樣本點集Pn；

（2）計算選取Pn中的K個點，作為最初的聚類中心點Pfi，其中i∈[1，K]；

（3）for，計算其與各個聚類中心點的歐式距離，并選擇最近的聚類中心點為其所屬的聚類，該點為；

（4）計算各個聚類中樣本點的中心，并以此更新聚類中心點；

（5）重復（3）-（4）步驟直至穩(wěn)定或超過限定次數(shù)；

（6）獲得最終的聚類和聚類中心點。

通過上述步驟，即可得到假設點集是由K個不同缺陷生成時的點分布情況。

2.2.4 最優(yōu)K值獲取

得到指定K值時的聚類情況，但此時的K并不一定與實際的不重復缺陷數(shù)量相同，因此需要對其進行判斷。在此之前，首先需要對已完成means 聚類計算的K聚類結果進行處理。

處理方法大致分為合并和去噪。首先需要計算各個聚類中心點之間的距離和各個聚類的類內距，若聚類中心點距離小于聚類的類內距之和乘以一系數(shù)，則可認為兩個聚類可以合并為一個聚類，因此進行合并。當合并操作結束后，再檢查各個聚類的成員點數(shù)，當點數(shù)過少時，則判斷該聚類為噪聲點距離，并給予篩除。

完成合并和去噪后，得到了處理后的聚類結果，對此，需要計算其可信度，判斷此時的聚類結果是否為實際的聚類結果。經實驗，對于K=n時的聚類結果，其可信度公式為：

其中，Pi為第i個聚類的中心點，dis(p1，p2)為點p1與點p2的距離，numsi為第i個聚類的成員點數(shù)，inner_xisi為第i個聚類的類內距。support的值越大，則K=n時的聚類結果越可信。

因此對于給定的點集和圖片，首先獲得一個K 值選取的范圍后，依次進行means 聚類計算，之后對于不同的K值下聚類結果，計算其可信度，并選取可信度最高時的聚類結果，作為所認為的不重復缺陷的數(shù)量。

2.2.5 仿真運行

聚類計算步驟以及項目的開發(fā)環(huán)境為window 環(huán)境，采用c++作為編程語言。在進行聚類之前設置了篩選系數(shù)coe，將位于圖片組的相機包圍圓一定范圍外的點以及過于靠近相機位置的點篩除后，根據(jù)技術方案的步驟進行實驗，并與預期結果進行比較。

實驗中在取coe=0.8 的情況下，即與相機包圍圓中心距離小于0.8 時的點篩選為可靠點時，根據(jù)上述步驟的最優(yōu)k值選取策略，能夠得到較高準確率的結果。

2.3 小結

聚類計算的研究，通過means 聚類的具體原理、以及常用的聚類效果評估方法入手，在結合實驗對聚類評估和聚類點篩選等方面進行調整，使得最后得到較為準確的支持率算法，通過該支持率算法對聚類進行評估獲得初步的聚類計算結果，為之后的進一步聚類計算結果提供了可靠的數(shù)值參考。同時實驗表明，此時的聚類計算k值選取已有較高的準確率。

3 聚類與缺陷映射

3.1 技術路線

聚類與缺陷區(qū)域的映射關系，實際上為三維空間點與二維圖像的映射關系。此時需要解決的問題，主要為將具體的聚類與具體的缺陷區(qū)域進行一一對應，得到最終的缺陷區(qū)域劃分結果。

由此具體技術路線為：實現(xiàn)將獲得的聚類的中心點，投影至圖片上；其次計算投影后的點與圖片上缺陷區(qū)域的距離百分比；之后根據(jù)距離百分比，尋找缺陷區(qū)域最匹配的投影點，此時認為該缺陷區(qū)域即屬于投影點本身對應的聚類；以上述方式完成聚類與缺陷的映射。最終輸出結果。

3.2 技術方案

聚類與缺陷映射的具體技術方案和步驟如下：

對于分析得到的聚類結果，需要將聚類與圖片的缺陷進行對應。其步驟為：

（1）計算各個聚類的中心點，得到點集PK；

（2）通過變換矩陣模塊，將點集的點投影至圖片上，得到投影后的點集Pk；

（3）計算圖片上對應類型缺陷的中心點位置，得到點集Pd；

（4）選取Pd上內的一點pd，計算其與Pk上各點的距離；

（5）選取與pd距離最近的點pk，將pk投影前所在聚類與pd對應；

（6）將pd、pk分別從Pd、Pk中去除；

（7）重復（4）～（6）直至Pd內沒有剩余點；

（8）完成聚類與缺陷的對應。

由此，完成就聚類與缺陷的對應。

3.3 研究總結

聚類與缺陷映射的研究，將空間的三維點聚類問題，回歸至了原本的重復缺陷篩查問題。通過可靠三維點計算，將二維的圖像問題先轉換成三維的點云分布問題；再通過k-means 聚類算法，解決了三維點云的劃分問題；之后再通過聚類投影至圖片于缺陷進行比較現(xiàn)實映射關系，將三維點云劃分的解決結果，轉換成了需要的缺陷篩查結果，使得最終得到所需要的判斷出現(xiàn)重復的缺陷并篩查的功能。此時得到的結果，能夠將其輸出成研究內容所需要的格式，是組件的收尾步驟，也是研究的收尾問題[5]。

同時，可以再根據(jù)點篩查時得到的缺陷區(qū)域可能存在的互斥的約束條件，修正聚類計算時的聚類結果，得到最終的實際缺陷數(shù)量，輸出正確的結果。

4 研究成果及創(chuàng)新點

4.1 研究成果

通過“面向輸電線路巡檢的多圖像間重復缺陷自動篩查組件”的研發(fā)，研究了K-means 聚類算法以及對應的聚類評估指標，根據(jù)實驗得到了一種準確率高的聚類結果評估方法，能通過means 聚類方法得到初步的聚類結果；研究了三維空間點與二維的缺陷圖像區(qū)域的映射關系，得到了將具體缺陷區(qū)域與聚類中心聯(lián)系起來的方法，并以此獲得最終的缺陷篩查結果，完成了“面向輸電線路巡檢的多圖像間重復缺陷自動篩查組件”的整體流程。

4.2 創(chuàng)新點

（1）采用了K-means 聚類算法作為判斷重復缺陷的主要算法，通過將生成的三維交點聚類，得到大致的缺陷數(shù)量，并通過反投影將聚類中心反投影至圖片，根據(jù)反投影的點與缺陷中心距離，得到各圖片的缺陷區(qū)域與各個聚類之間的聯(lián)系。并在使用K-means 聚類的基礎上，對聚類的結果進行可信度計算，驗證聚類的結果，從而選擇最可信的聚類結果作為實際結果。

（2）針對計算量較大導致的組件計算時間較長的問題，采用了OpenCL 技術，將大部分計算轉至GPU 上運行。在圖片和缺陷較多時，運算的時間由1 分多鐘優(yōu)化只需要3 ～5 s，同時其準確率也得到保證，組件的運算效率有了顯著提高。