面向工業復雜場景的合作靶標橢圓特征快速魯棒檢測

李 洋，程 智，周維虎，高 超，董登峰*

（1.中國科學院 微電子研究所，北京 100094；2.中國科學院大學，北京 100049）

1 引 言

在工業測量領域，激光跟蹤儀、工業全站儀、視覺測量儀等精密光學儀器越來越多地應用于高精度復雜結構的加工裝配質量控制過程［1-4］，并且正在從傳統的離線人工測量朝在線自動測量方向發展。為滿足工業自動測量需求，上述儀器需要具備合作靶標自動檢測功能。在實際工業測量場景中，常用的全反射靶球、平面反射片、立體靶標等合作靶標均包含圓形特征［5］，經透視變換后成為橢圓特征。而在背景環境中出現橢圓特征的幾率較低，所以快速準確檢測場景中的橢圓特征是自動檢測合作靶標的關鍵。

橢圓特征檢測是目標檢測領域中的一項經典問題，國內外學者針對該問題開展了大量研究工作，目前橢圓檢測方法主要分為兩類：基于霍夫變換（HT）的橢圓檢測方法和基于邊緣段連接的橢圓檢測方法。

霍夫變換是用于檢測圖像中各類函數曲線特征的一種通用方法。在橢圓特征檢測中應用霍夫變換的主要問題是橢圓方程包含五個參數，需要構建相應的5維參數空間進行運算，導致算法效率較低，該類算法的主要研究方向是通過減少參與計算的樣本數量、降低參數空間維度等方式優化計算效率［6］。McLaughlin在文獻［7］中提出利用橢圓幾何性質求取中心點坐標，將5維參數空間轉化為3維，然后基于Xu等［8］提出的隨機霍夫變換（RHT）方法求取其余參數；Guil和Zapata等［9］提出的快速橢圓霍夫變換（FEHT）進一步約束了參與霍夫變換的圖像像素范圍，并在霍夫變換階段將3維參數空間分解為2維參數空間進行求取，從而提高了算法效率；Chia等［10］提出的算法采用一維參數空間求取橢圓特征，在提升算法效率同時便于通過并行運算縮短運算時間；鄒榮等［11］利用梯度圖像求取橢圓切線，并利用切線參數在5維霍夫空間中通過少量圖像點獲取橢圓參數。這些算法對霍夫變換進行了一定程度的優化，但仍然無法從根本上解決檢測低效問題，這制約了該類檢測算法在檢測應用領域的推廣。

近年來，基于邊緣連接的橢圓特征檢測技術發展較快，該領域研究重點是對邊緣弧段進行有效約束和聚類，找到屬于同一橢圓特征的弧段集合，同時排除非橢圓邊緣干擾。Prasad等［12］提出了一種基于邊緣弧段曲率與相關凸性約束的橢圓檢測方法，該方法基于幾何特征給出弧段搜索范圍，性能優于傳統的邊緣連續性約束方法；Fornaciari等［13］提出的YAED方法通過凸性和梯度方向，將邊緣弧段分為四個象限組，然后通過幾何特征約束和中心參數約束確定合適的三弧段組進行橢圓擬合；Wang等［14］提出的方法和Liu等［15］提出的方法綜合采用凸性特征、弧段曲率、坐標區域等約束條件對全部邊緣弧段進行分組，但弧段分組約束條件不夠嚴格，在處理包含復雜場景的真實圖像時會產生大量誤匹配弧段組合，導致誤檢率偏高；Meng等［16］提出的AAMED方法在幾何約束基礎上構建鄰接矩陣，通過邊緣弧段搜索與組合驗證來獲得屬于同一橢圓的邊緣弧段組合，該方法有效提高了弧段聚類效率，但仍存在約束條件不嚴格的問題；Jia等［17］提出的CNED方法利用特征數對圖像邊緣弧段進行匹配約束，然后通過遍歷進行弧段組合，該方法提出了相對嚴格的約束條件，但特征數計算和弧段搜索組合效率偏低，難以滿足實時性應用要求。

本文橢圓檢測方法基于邊緣連接技術，能夠避免霍夫變換高維參數空間帶來的處理效率偏低問題，并且提出了基于帕斯卡定理的邊緣弧段橢圓特征匹配方法和基于關系矩陣的弧段聚類方法，通過嚴格的參數約束排除偽橢圓特征，通過矩陣運算提高弧段聚類效率，從而改善系統在復雜環境干擾下的魯棒性，有效克服邊緣連接類橢圓檢測方法實時性不足、易受環境干擾等問題，可以滿足工業復雜場景合作靶標橢圓特征檢測所需。

2 橢圓檢測總體方案

圖1所示為本文橢圓檢測方法流程框圖，主要包括以下步驟：（1）基于幾何特征的邊緣弧段分組；（2）基于帕斯卡定理的鄰接象限弧段匹配；（3）基于弧段關系矩陣的弧段聚類；（4）橢圓特征參數非迭代擬合與橢圓特征篩選。

圖1 橢圓檢測方案流程框圖Fig.1 Block diagram of ellipse detecting process

在步驟（1）中，首先對圖像邊緣弧段進行分割篩選，然后采用文獻［13］方法根據邊緣弧段凸性將其分四個象限弧段組；步驟（2）、（3）為本文提出的弧段匹配和聚類方法，其中步驟（2）基于帕斯卡定理提出了一種更加有效的參數約束條件，可對四個相鄰象限弧段組（I、II象限，II、III象限，III、IV象限，IV、I象限）進行嚴格的橢圓特征匹配，篩除大量非橢圓弧段組，得到滿足橢圓參數約束條件的弧段對組合，步驟（3）把弧段參數約束結果轉化為關系矩陣［18］，通過關系矩陣性質和布爾乘法運算進一步建立匹配于同一橢圓的三弧段組合和四弧段組合，作為橢圓參數擬合數據集；步驟（4）采用文獻［19］ElliFit方法擬合橢圓參數特征，然后根據橢圓參數篩選排除偽特征和重復特征，得到最終檢測結果。

2.1 基于幾何特征的邊緣弧段分組

對數字圖像進行高斯濾波后，采用自適應Canny算子提取圖像單像素二值化邊緣圖，然后采用8-鄰域邊緣跟蹤方法［20］把具有鄰接關系的邊緣點連通形成具有幾何意義的邊緣弧段，建立圖像邊緣弧段集合Arcs。本部分目的是基于弧段集合Arcs構造分屬于圖2所示四個象限的邊緣弧段集合Arcs1~Arcs4。

圖2 弧段象限劃分示意Fig.2 Schematic of classifying arcs by quadrant

如圖3所示，由于集合Arcs中的弧段元素arc可能包含來自多個象限的組成部分，無法直接被歸入某個象限集合，所以需要對各弧段元素在x、y方向梯度值?x=0和?y=0處進行分割，用分割所得子弧段替代原弧段元素，使Arcs全部弧段元素均能被歸入某一象限組。其中方向梯度值由圖像Canny處理過程給出。

圖3 根據方向梯度分割邊緣弧段Fig.3 Segment edge arc by gradient orientation

接下來在各弧段元素中搜索拐點，并將其在拐點處斷開，以獲得無轉折的平滑弧段組。如圖4所示，對弧段以5點一組進行分組，所得端點序列集合為{p1，p2，...，pn}，可求得端點坐標二階差分序列：。若存在某個端點pe，其坐標二階差分（xe，ye）絕對值之和滿足|xe|+|ye|>Threaddiff，則表示弧段在點pe+1前后走向發生了較大變化，點pe+1即為拐點。圖4（b）中拐點p4對應的坐標二階差分為=(-3，-2)，絕對值之和為5，其它點對應的坐標二階差分絕對值之和均小于2。經實驗驗證，取二階差分閾值Threaddiff=4，可獲得較好的拐點篩除效果。

圖4 基于點組坐標差分信息的弧段拐點判斷Fig.4 Turning point recognition based on coordinate dif‐ference information of point groups

對于無拐點的弧段集合Arcs，需要篩除其中的直線段元素，減少非橢圓特征的干擾。如圖5所示，計算弧段中點Pmid1與弧段兩端點連線中點Pmid2距離dm12，若dm12小于給定閾值，則認為該元素為直線段并予以排除。

圖5 直線段元素判斷Fig.5 Recognition of line segment

經上述篩除后，可根據弧段元素端點連線斜率符號，把弧段集合Arcs劃分為屬于I/III象限的集合Arcs13和屬于II/IV象限的集合Arcs24，如圖6所示；同時，還可以根據弧段凸性特征把弧段集合Arcs劃分為屬于I/II象限的凸弧段集合Arcs12和屬于III/IV凹弧段集合Arcs34。然后根據弧段集合關系式（1），即可得到所需的四個象限弧段集合：Arcs1，Arcs2，Arcs3，Arcs4。

圖6 原始圖像與弧段集合Arcs13，Arcs24Fig.6 Original image and groups of arcs Arcs13，Arcs24

2.2 基于帕斯卡定理的鄰接象限弧段匹配

本部分提出了一種基于帕斯卡定理的鄰接象限弧段橢圓特征匹配方法，它的作用是判斷相鄰兩象限弧段集合元素是否匹配于同一橢圓特征，作為下一步構建弧段集合之間關系矩陣的依據。與同類檢測算法常用的弧段鄰近性約束、凸性約束、中心坐標約束等方法相比，本方法采用二次圓錐曲線性質作為約束條件，對橢圓特征的約束性更加嚴格，能夠對非橢圓特征起到更好的篩除效果。

圖7 相鄰象限弧段幾何位置關系Fig.7 Geometric relationship of arcs from adjacent quad‐rants

式（2）中，括號中x，y分別代表弧段端點x，y坐標。顯然，只有滿足以上坐標位置關系，弧段對才有可能匹配于同一橢圓特征。

對于滿足弧段端點坐標位置關系C1的弧段對，基于帕斯卡定理進行橢圓特征匹配性判斷。由帕斯卡定理可知，若一個六邊形的三對對邊交點共線，則該六邊形內接于一條二次圓錐曲線。由于橢圓屬于二次圓錐曲線，所以橢圓以及橢圓弧段上的點均符合帕斯卡定理。

如圖8所示，以I、II象限弧段對為例，首先在兩弧段上任取六點Pp1，Pp2，Pp3，Pp4，Pp5，Pp6，確保以它們為頂點的六邊形H對邊不平行且相鄰點間距盡量大，H的三組對邊延長線分別交于點Pj1，Pj2，Pj3，根據帕斯卡定理，若Pj1，Pj2，Pj3三點共線，則兩弧段屬于同一橢圓特征，如圖8（a）所示；否則若Pj1，Pj2，Pj3三點不共線，則兩弧段不屬于同一橢圓特征，如圖8（b）所示。

圖8 基于帕斯卡定理的相鄰象限弧段對橢圓匹配Fig.8 Adjacent quadrants'arc pair elliptical matching method based on Pascal's theorem

在真實圖像中由于各類干擾因素的存在，上述共線條件無法絕對滿足。設直線Pj1Pj2與直線Pj2Pj3夾角為θp（若夾角為鈍角，則取其補角作為θp），基于帕斯卡定理的橢圓匹配約束關系C2表示為：

式（3）中，參數θt為用來判定Pj1，Pj2，Pj3三點共線程度的角度閾值。對于滿足基本坐標位置關系C1的 弧 段 對，基于本文提出的橢圓匹配約束關系C2進行判斷，能夠排除大量不具備橢圓匹配關系的弧段對，使得本文算法對于真實場景圖像復雜干擾信息具有較強的魯棒性，同時也有助于減小弧段聚類、橢圓擬合過程的數據量，提高處理效率。對于同時滿足C1和C2約束的弧段對，稱其匹配關系為“橢圓匹配”，否則稱其為“橢圓不匹配”。

2.3 基于弧段關系矩陣的弧段聚類

真實檢測圖像存在大量噪聲和非目標對象干擾，為提高檢測結果可靠性，需要對同時匹配于3個或4個不同象限弧段的橢圓特征進行擬合。在這一部分，本文基于關系矩陣概念及其符合運算法則，提出了一種基于弧段關系矩陣（Arcs Relation Matrix，ARM）的聚類方法，該方法可以通過2.2節弧段對匹配結果構建具有橢圓匹配關系的三象限弧段集合和四象限弧段集合，作為下一步橢圓參數擬合數據集。

弧段關系矩陣是專門用于描述兩弧段集合間橢圓匹配二元關系的矩陣。對于兩個相鄰象限弧段集合，首先構建其二鄰接關系矩陣ARM-2。通過2.2節約束條件遍歷各判斷弧段對的橢圓匹配關系，可建立起弧段集A?到弧段集B?的二元關系RA?，B?：

其關系矩陣MA，B表示為：

其中，矩陣各元素值rij由下式給出：

由二鄰接關系矩陣ARM-2構建過程可知，弧段關系矩陣MA，B的元素rij表示兩個弧段對的匹配關系：若rij=1，則表示弧段對橢圓匹配，若rij=0，則表示弧段對橢圓不匹配。

對于四個象限弧段集合，可以構建四個二鄰接關系矩陣ARM-2：MI，II，MII，III，MIII，IV，MIV，I，根據二元關系的復合運算法則，可以進一步求出用以描述三個相鄰象限弧段集合橢圓匹配二元關系的三鄰接關系矩陣ARM-3：MI，II，III，MII，III，IV，MIII，IV，I，MIV，I，II：

以及一個用以描述四個象限弧段集合橢圓匹配二元關系的四鄰接關系矩陣ARM-4：MI，II，III，IV：

式（6）、式（7）中的符號“°”代表布爾乘法運算符。由關系矩陣概念可知，ARM-3關系矩陣中每個“1”值元素表示在相應的三個象限中存在一個具有橢圓匹配關系的三弧段組，例如MI，II，III（i，j）=1表示存在一個三弧段組具有橢圓匹配關系，i，x，j分別代表該組合中的三個弧段在各自所屬象限弧段集合中的序號，其中i，j與矩陣腳標值相同，x可以在求取ARM-3關系矩陣的布爾運算過程中獲得。ARM-4關系矩陣中每個“1”值元素表示存在一個具有橢圓匹配關系的四弧段組，其 中 四 個 弧 段 分 別 屬于四個不同象限，i，x1，x2，j的意義和求取過程與ARM-3關系矩陣類似。

通過求取ARM-3關系矩陣和ARM-4關系矩陣，可以得到以下五個弧段組集合：

在四弧段組集合RI，II，III，IV中，每個元素表示一個來自四個不同象限的四弧段組存在橢圓匹配關系；類似地，在 三弧段組集合RA，B，C中，每個元素表示一組來自三個不同象限的三弧段組存在橢圓匹配關系。上述五個集合中的每個元素都對應于圖像中的一個橢圓特征，通過對各元素對應的弧段組進行擬合就能得到相應的橢圓參數。

在進行橢圓參數擬合之前，注意到存在部分三弧段組集合元素參與構成了四弧段組集合，為避免對同一橢圓特征進行重復擬合，需要從三弧段組集合中排除上述參與構成四弧段組集合的元素。設排除重復元素后的三弧段組集合為，則它們與四弧段組集合RI，II，III，IV的并集ΦD即為橢圓參數擬合數據集。

2.4 橢圓特征參數非迭代擬合與橢圓特征篩選

對橢圓參數擬合數據集ΦE中包含的各弧段組進行最小二乘擬合，即可得到若干組橢圓特征參數，對這些橢圓特征參數進行進一步篩選，排除重復特征和偽特征，最終得出所求的橢圓特征。

在參數擬合階段，采用ElliFit算法對各弧段組數據進行橢圓特征參數非迭代最小二乘擬合，求出各橢圓特征參數向量V(i)=，其中和為橢圓中心坐標，a(i)，b(i)分別為橢圓長、短半軸長度為橢圓長軸與x軸夾角，e(i)為橢圓擬合誤差。所有參數向量共同組成橢圓特征集合ΦE。通過以下規則對集合中橢圓元素進行篩選，最終得到橢圓特征檢測結果：

（1）給定閾值emax，判定橢圓特征V（i）的擬合誤差ei是否超限，如果ei>emax，則表示擬合點與橢圓特征距離較大，從ΦE中剔除該橢圓特征［21］；

（2）給定閾值rmax，判定橢圓特征V（i）的長、短軸長度比ri=a（i）/b（i）是否超限，如果ri>rmax，則表示橢圓形狀過于扁平，存在較大的誤匹配可能，從ΦE中剔除該橢圓特征。

（3）給定閾值dmin，tmin，對于每個橢圓特征V（i），求取該特征與其它每個橢圓特征的中心點歐氏距離dij，若存在橢圓特征V（j）使得dij

3 實驗結果與分析

為驗證本文算法效果，對典型工業測量合作目標進行了一系列實驗驗證，實驗時將被測對象置于復雜環境場景中，模擬現場檢測環境。硬件環境為計算機（CPU主頻3.0 GHz），軟件環境為VC++。

本文算法檢測過程與結果如圖9所示，圖9（a）為平面反射片在實驗室模擬場景中拍攝的原始圖像，（b）為邊緣跟蹤所得的圖像邊緣片段，（c）為篩選分組后的四象限邊緣弧段集合，圖中四種顏色代表四個象限弧段集合，（d）為弧段聚類結果，顏色相同的弧段表示屬于同一橢圓特征，（g）為橢圓擬合結果，（h）為篩選后的最終橢圓檢測結果。

圖9 橢圓檢測過程與檢測結果（橢圓數量n=3）（橢圓數量n=2）Fig.9 Ellipse detection process and result（with 3 ellipses fitted）（with 2 ellipses detected）

經實驗驗證，對于分辨率為640×480 pixels的實驗圖像，本文算法圖像預處理過程用時159.2 ms，弧段預處理過程用時7.2 ms，弧段匹配聚類用時5.9 ms，橢圓擬合用時8.3 ms，擬合結果篩選用時2.6 ms，總用時183.2 ms。應用同一圖像對RHT、YAED、AAMED、CNED算法進行比對實驗，檢測結果如圖10所示，檢測用時如表1所示。由實驗結果可得出結論：與參照算法相比，本文算法對實驗圖片的總體檢測用時最短，能夠從實驗圖像的復雜環境背景中準確提取出平面反射靶的橢圓特征。

表1 不同檢測方法用時比對Tab.1 Time comparison of different detection methods （ms）

圖10 不同檢測方法檢測比對實驗Fig.10 Comparison experiment of different detection methods

通過對各算法用時進一步分析可知，本文算法和CNED算法由于通過相對嚴格的約束條件排除非橢圓弧段組合，在橢圓擬合與篩選步驟均取得了更高的效率；本文算法和AAMED算法通過不同方法優化弧段聚類過程，使得該環節效率與傳統遍歷方法相比提升了一個數量級以上；與RHT算法相比，參與實驗對比的邊緣連接類算法效率普遍占優，更加符合實時應用要求。

為進一步考察本文算法的可靠性，通過改變被測目標類型、檢測距離、環境光照、外界遮擋、檢測方位、噪聲干擾等測量條件，進行了進一步實驗，結果如圖11~16所示。其中圖11為全反射靶球目標檢測結果，圖12為距離目標500 mm和1 000 mm時的檢測結果，圖13~14分別為由于反光不均勻、外界遮擋而導致目標橢圓特征不連續情況下的檢測結果，圖15為目標測量方位發生傾斜變化時的檢測結果，圖16為圖像包含均值為0、方差為0.1的高斯噪聲時的檢測結果。檢測結果表明，本文算法能夠適應復雜場景下合作目標橢圓特征的檢測需求，對常見干擾因素不敏感，魯棒性較強。

圖11 全反射靶球目標原始圖像與橢圓特征檢測結果Fig.11 Original image of SMR and detection result of its elliptical character

圖12 不同距離靶標原始圖像與橢圓特征檢測結果Fig.12 Original images and the elliptical character detec‐tion results of target at different distance

圖13 不均勻反射干擾下靶標原始圖像及橢圓特征檢測結果Fig.13 Original image of target under non-uniform re‐flection interference and its elliptical character de‐tection result

圖14 外界遮擋干擾下靶標原始圖像及其橢圓特征檢測結果Fig.14 Original image of occluded target and its elliptical character detection result

圖15 測量方位傾斜時靶標原始圖像及其橢圓特征檢測結果Fig.15 Original image of tilted target and its elliptical character detection result

圖16 包含高斯噪聲的靶標圖像與橢圓特征檢測結果Fig.16 Target’s image with Gaussian noise and its ellip‐tical character detection result

4 結 論

本文提出了一種在工業復雜場景中準確檢測合作靶標橢圓特征的方法，該方法首先對預處理邊緣圖像進行邊緣跟蹤和弧段分割篩選分組，通過基于帕斯卡定理的鄰接象限弧段匹配方法和基于關系矩陣的弧段聚類方法，對圖像弧段根據橢圓匹配性實現有效聚類，優化了橢圓擬合環節效率，可獲得更加準確可靠的檢測結果。實驗結果表明，本文方法對檢測距離、光照條件、目標方位、噪聲干擾等因素具有顯著的抑制作用，在各種典型復雜場景條件下均能得到可靠的檢測結果；該方法對分辨率為640×480 pixels的實驗圖像檢測時間為183.2 ms，與YAED，CNED，AAMED等同類橢圓檢測方法相比，用時分別縮短了72.9%，22.5%和16.9%，能夠滿足工業測量儀器現場搜索合作靶標性能需求。

本文算法圖像預處理Canny運算邊緣跟蹤處理時間數倍于其它環節，未來將針對上述問題進行優化，進一步提高檢測速度，同時面向激光跟蹤儀、工業全站儀等典型工業精密測量儀器的合作靶標檢測需求，進一步開展應用研究。