基于改進弧段切點弦的多橢圓檢測

張鵬，季愛明

（蘇州大學 軌道交通學院，江蘇蘇州 215100）

橢圓檢測是圖像處理中的一個重要技術。橢圓檢測被廣泛應用于相機校準[1]、工業零部件檢測[2]、細胞檢測[3]、瞳孔識別[4]等領域。而在實際應用中，圖像中往往存在多個待檢測的橢圓，因此，多橢圓檢測具有十分重要的研究價值。

橢圓檢測算法大致可以分為三類：基于霍夫變換的方法[5-6]、基于最小二乘的方法[7]和基于弧段提取的方法。

霍夫變換方法往往計算量過大，運行時間較長。最小二乘方法則對噪聲較為敏感。這兩種方法均是基于邊緣點來檢測橢圓，忽視了邊緣的連續性，且不太適用于多橢圓的快速檢測?；诨《翁崛〉姆椒▌t從邊緣段出發，尋找屬于同一橢圓的弧段組，通過弧段組檢測目標，能有效實現多橢圓的快速、高精確度檢測。文獻[8]利用梯度信息與凹凸性將弧段分類到四個象限，組合不同象限的弧段，利用橢圓弧段間的位置關系和橢圓中心應與平行弦中點共線的特點篩選弧段組以檢測橢圓。文獻[9]同樣將弧段分類到四個象限，并基于橢圓內包多邊形為凸多邊形的性質對弧段組進行篩選?；《谓M篩選效果越好，基于弧段進行多橢圓檢測的效果越好。因此，如何快速準確地篩選弧段組是基于弧段提取檢測多橢圓方法的關鍵點。

為了提高圖像中多橢圓檢測的精確度，該文在弧段分象限的基礎上提出了基于改進弧段切點弦的多橢圓檢測算法。使用弧段切點弦方法計算弧對橢圓中心，篩選弧段組。為了減小切點數字化誤差對中心計算的影響，一方面在弧對上多次取不同切點計算多個橢圓中心坐標，然后采用中值濾波；另一方面使用抑制數字化誤差影響的弧段切線斜率估計方法估計弧段上點的切線斜率。最后，通過實驗驗證了該文方法的性能。

1 弧段分象限檢測

弧段分象限檢測首先對輸入圖像進行邊緣檢測，提取物體邊緣輪廓；然后結合邊緣點梯度信息和弧段凹凸性將邊緣弧段按象限分為四類；再對由不同象限弧段組成的弧段組合進行篩選；擬合篩選后的弧段組；驗證并聚類候選橢圓。

篩選弧段組時常用位置約束和中心約束方法。中心約束篩選時通過弧段組構造兩個弧對，計算每個弧對的橢圓中心?；谇悬c弦計算橢圓中心的示意圖如圖1 所示。在弧段αa上取兩個相異點P1、P2，過該兩點作切線交于點Pa，連接P1、P2構成弦P12，連接Pa與弦P12中點的直線經過橢圓中心。同理，在另一條弧段上也能得到經過中心的直線。兩直線交點即為弧對的橢圓中心。

圖1 基于切點弦計算中心示意圖

切點弦方法簡便、易于計算，但它的精確度易受邊緣切點數字化誤差的影響。對此，該文對切點弦方法作出了改進。

2 切點弦弧段篩選

首先通過橢圓兩個相鄰象限弧段間的位置關系初步篩選出弧段組[10]。然后通過弧段組τabc構造兩個弧對(αa,αb)和(αb,αc)，利用弧對的中心約束進一步篩選弧段組。

基于切點弦計算弧對中心的方法只計算單個中心，易受邊緣切點數字化誤差的影響而出現較大偏差[11]，從而影響弧段篩選的準確度。為了降低邊緣切點數字化誤差對弧段篩選的影響，該文對切點弦弧段篩選算法作出了改進。改進的切點弦弧段篩選算法如算法1 所示。

算法1：改進的切點弦弧段篩選算法

輸入：三個弧段的邊緣點集Pa、Pb、Pc；中心數Ns。

輸出：若弧段組τabc滿足中心約束則輸出true，不滿足則輸出false。

該算法多次從弧對的兩個弧段上取不同切點計算過中心線，由多對過中心線計算得到多個橢圓中心坐標，然后采取中值濾波的方法減小數字化誤差的影響。實驗表明中心坐標數Ns取6 時可以較好地平衡精確度和時間。為了使切點的尋找范圍盡可能大，從弧段的中點處開始向左右兩端取切點計算過中心線。計算兩個弧對中心Cab(xab,yab)和Cbc(xbc,ybc)的歐式距離discenter。如果discenter小于閾值Thcenter，則該弧段組滿足中心約束，認為該弧段組的三個弧段屬于同一個橢圓。Thcenter取M×N×0.05[8]，M×N為圖像大小。

3 抑制數字化誤差弧段切線斜率估計

切線斜率估計如圖2 所示。

圖2 切線斜率估計

如圖2 所示，對于橢圓上的點P0(x0,y0)，設以P0為圓心，R為半徑的圓與橢圓交點為P1(x1,y1)、P2(x2,y2)，P1為左交點，P2為右交點。用直線P1P2的斜率來近似P0處的切線斜率m0。的計算公式如式（1）所示：

為了使足夠近似m0，R的取值有上限約束，如式（2）所示[12]：

其中，Δθmax為P1與P0的離心角最大差值，b為橢圓短半軸長。Δθmax取π10，則有R≤0.174 3b。此外，受邊緣點數字化誤差的影響，實際計算出的與理論值之間存在誤差，可以用實際計算出的切線與理論切線間的角度差?φ衡量該誤差[13]。設P1、P2坐標的數字化誤差為Δx1、Δy1、Δx2、Δy2，變化范圍在±0.5 之間，則?φ如式（3）所示：

基于Δx1、Δy1、Δx2、Δy2所能取的最大、最小值對?φ的公式進行討論，可得到誤差最大值?φmax如式（4）所示：

由式（4）可以看出，(1+2)(x2-x1)越大，則?φmax越小。直線P1P2的方程如式（5）所示：

點P1、P2的歐式距離公式如式（6）所示：

將式（5）代入式（6）可得式（7）：

所以，P1P2的距離越大，?φmax越小。而R值越大，P1P2的距離越大。因此，R值越大，?φmax越小。當R取0.174 3b時，?φmax最小。

因為橢圓短半軸長b無法預先得知，所以該文基于橢圓的最小外接矩形估計短半軸長。如圖3 所示，橢圓最小外接矩形的寬等于橢圓的短軸長。對弧段組(αa,αb,αc)提供的點集，使用旋轉卡殼法找到弧段組的最小外接矩形，根據該最小外接矩形的寬估計短半軸長。由于弧段組中各個象限的弧段可能因為噪聲而并不完整，由弧段組找到的最小外接矩形可能略小于完整橢圓的最小外接矩形。因此，估計的短半軸長等于或略小于實際的橢圓短半軸長b，使得R值可能略小于0.174 3b，從而使得?φmax比理論可取的最小值稍大，但確保了可以足夠近似m0。

圖3 橢圓最小外接矩形

基于誤差分析選取合適R值的抑制數字化誤差影響的弧段切線斜率估計算法如算法2 所示。

算法2：抑制數字化誤差影響的弧段切線斜率估計算法

4 實驗與分析

為了驗證該文算法的性能，通過在Matlab 平臺上編程來實現該算法。首先使用自適應Canny 邊緣檢測器檢測邊緣點；然后利用梯度信息與弧段凹凸性將邊緣弧段分類到四個象限；選取三個象限的弧段構成弧段組后，使用位置約束和基于改進弧段切點弦方法的中心約束進行篩選；對篩選出的弧段組用最小二乘法進行擬合；最后對擬合出的候選橢圓進行驗證和聚類。

實驗使用的數據集為虛擬圖像集Dataset #1 和真實圖像集Prasad 數據集。Dataset#1 數據集為100張600×600 像素的虛擬圖像，其中，包含殘缺橢圓和遮擋橢圓。Prasad 數據集為橢圓檢測常用數據集，包含198 張真實圖像，圖片大小為170×138 像素到800×540 像素。實驗評價標準為橢圓檢測常用的精確度P、召回率R、F 值和運行時間T，時間單位為s。P、R、F 值計算如式（8）-（10）所示：

其中，Ψ 為檢測到的橢圓個數，γ為檢測出的真實橢圓個數，Ω為圖像中的真實橢圓個數。當檢測到的橢圓與真實橢圓的重疊面積比大于0.8時，視為真實橢圓。

在計算弧對中心坐標時，弧段中心個數Ns越大，最終的中心坐標精確度越高，使得檢測算法的精確度越高，但也會增加算法的計算時間。為了選取合適的Ns值，從Prasad 數據集中選取了50 幅圖像，測試Ns對F 值和時間的影響，如圖4-5 所示。

圖4 Ns 對F 值的影響

由圖4、圖5 可以看出，隨著弧段中心個數Ns的增大，時間在不斷增加，而當Ns大于6時，對F 值的提升變得微弱。因此，Ns取6 時可以較好地平衡算法的精確度和時間。

圖5 Ns 對時間的影響

為了對比算法的檢測效果，在Matlab平臺上復現了其他幾種基于弧段的算法，并與該文算法進行比較。實驗結果如表1-2所示，實驗對比圖如圖6所示。

表1 Dataset#1數據集上的對比結果

圖6 Prasad數據集上的對比圖

從表1 可以看出，在Dataset #1 數據集上，與文獻[8]算法相比，該文算法在P、R、F 值和運行時間上都取得了更好的效果。與文獻[9]算法相比，雖然運行時間增加了2.4%，但是P提高了13.7%、R提高了9.5%，F 值提高了11.4%。與文獻[14]算法相比，雖然R損失了1.7%，但是P提高了2.1%，F 值提高了0.09%，運行時間減少了9.6%。因此，綜合考慮可知，該文算法性能更好。

從表2可以看出，在Prasad數據集上，與文獻[8]算法相比，該文算法在P、R、F 值和運行時間上都取得了更好的效果。與文獻[9]算法相比，雖然運行時間增加了0.8%，但是P提高了12.3%、R提高了2.3%，F 值提高了4.6%。與文獻[14]算法相比，雖然R損失了3.0%，F 值損失了1.9%，但是P提高了4.8%，時間上減少了18.4%。因此，綜合考慮，該文算法性能更好。

表2 Prasad數據集上的對比結果

5 結論

為了提高圖像中多橢圓檢測的精確度，該文提出了基于改進弧段切點弦的多橢圓檢測算法。改進了基于弧段切點弦計算弧對中心的方法，計算多個橢圓中心坐標，然后使用中值濾波。使用抑制數字化誤差影響的弧段切線斜率估計法計算切線。有效減小了切點數字化誤差對弧對中心計算的影響。實驗表明，該方法有效提高了圖像中多橢圓檢測的精確度，能快速有效地檢測出多橢圓圖像中的目標。