基于Kittler最小誤差分割算法的小視場星圖分割

時春霖 ，楊培章 ，張 超 ，杜 蘭 ,，葉 凱 ,5，范承嘯 ，李 建 ，祖安然

（1. 信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450001；2. 中國人民解放軍61206部隊，北京 100042；3. 中國人民解放軍空軍政治工作部，北京 100843；4. 北京衛(wèi)星導(dǎo)航中心，北京 100094；5. 北京航天飛行控制中心，北京100089）

天文測量是通過觀測恒星位置以確定載體的天文坐標(biāo)，或者確定兩點間天文方位角的測量工作[1-3].天文測量在大地網(wǎng)起始數(shù)據(jù)和垂線偏差測定，以及精密工程和國防科技領(lǐng)域，都有著不可替代的作用.隨著精密測量儀器的飛速發(fā)展，天文測量正在逐漸擺脫人工模式向高效自動化發(fā)展.

視頻全站儀將 CCD （charge coupled device）技術(shù)與全站儀一體化，從而推動了自動天文測量向小型化和智能化發(fā)展. CCD 相機獲取恒星影像，全站儀獲取恒星方位信息（水平角和垂直角），數(shù)字圖像處理技術(shù)提取恒星的像點坐標(biāo)，最終利用坐標(biāo)轉(zhuǎn)換和天文定位原理等獲得測站的天文坐標(biāo)[4-7].

視頻全站儀通常僅拍攝單顆恒星的小視場星圖. 一方面，其CCD為小視場角的長焦相機；另一方面，為提高天文觀測可靠性和效率，天文觀測星表嚴(yán)格限制“雙星”出現(xiàn). 但是，這種小視場星圖仍存在背景復(fù)雜和噪聲較高的特點. 除星空背景光的干擾，還經(jīng)常會摻入視場燈的影響，給目標(biāo)恒星識別和坐標(biāo)提取帶來了很大的困難.

閾值分割算法是小視場星圖識別的重要一環(huán).其中，局部閾值法針對這種結(jié)構(gòu)單一的星圖并不適用，效率低且容易造成“過曝”[8-10]. 因此，應(yīng)選用光強適應(yīng)較好、抗噪能力較強的全局閾值算法. 文獻[11]指出，即使傳統(tǒng)常用的全局閾值分割算法處理星圖失效時，一維最大熵法仍能夠具有良好的分割效果. 但是其運算效率在全局閾值法中較低，無法滿足日益增長的實時化要求.

小視場星圖的圖像特征恰好符合Kittler最小誤差法的適用條件. Kittler算法要求理想的前景和背景灰度分布服從混合高斯分布，而二者又均服從同一高斯分布[12-19]. 實際中符合此特征中的圖像并不多見，因而大大限制了Kittler算法的應(yīng)用. 但是，小視場星圖中，灰度值較低的夜景占有很大比例，而灰度值較高的星點像素數(shù)很少，整幅圖像灰度呈現(xiàn)近似高斯分布的數(shù)學(xué)特征. 因此，針對這種星圖，Kittler算法不僅可最大限度減少背景和前景錯分可能，且其時間復(fù)雜度較低，可加快圖像處理速度.

本文以Leica-60全站儀（簡稱TS60）為測量平臺，提出Kittler最小誤差分割算法，替代目前使用的一維最大熵法處理小視場星圖. 首先，介紹了基于Kittler最小誤差的閾值分割算法；其次，對比了幾種閾值分割效果和運行效率，給出了定性定量評價，指出Kittler最小誤差算法對小視場星圖具有良好的處理效果的同時，可以大幅減少處理時間；然后，采用一維最大熵和最小誤差法對室內(nèi)星圖處理結(jié)果進行比較，證明該算法的適用性和準(zhǔn)確性；最后，通過實際野外天文測量，利用基于該算法的自動天文測量模式，證明了該算法的可靠性.

1 基于視頻全站儀的天文定位

基于全站儀的天文定位與常規(guī)天文定位的流程和儀器基本相同. 例如，測量員預(yù)先編制等高星表，通過北極星實現(xiàn)天文定向，天文授時采用GNSS（global navigation satellite system）接收機，守時采用計算機的內(nèi)部晶振.

視頻全站儀的測量自動化流程如下：測量機器人根據(jù)觀測星表，自動轉(zhuǎn)向待測恒星進行連續(xù)跟蹤；測量員啟動觀測鍵，激活CCD圖像記錄模式，則進入自動測量. 然后進行下一顆恒星的轉(zhuǎn)向-跟蹤-測量.

自動測量則通過星圖處理，提取星點CCD坐標(biāo)并轉(zhuǎn)換為恒星的觀測坐標(biāo)，進而解算得到本地的天文坐標(biāo). 因此，星圖的處理能力和效率，決定了自動天文測量的數(shù)據(jù)解算質(zhì)量.

2 Kittler最小誤差閾值分割算法

2.1 Kittler算法

Kittler最小誤差分割算法對于目標(biāo)和背景呈現(xiàn)高斯分布的圖像具有良好的處理效果，且效率較快. 1986年，Kitter和Illingworth基于貝葉斯最小誤差理論的思想，將圖像閾值分割問題轉(zhuǎn)化為最小誤差化的高斯分布擬合問題[12-13]. 文獻[14-15]從相對熵理論（又稱KL（Kullback-Leibler）散度或信息散度）對Kittler最小誤差法進行了解釋和論證，為其奠定了理論基礎(chǔ). 文獻[15-16]對其圖像分割效果和執(zhí)行效率進行了分析. 該算法要求拍攝的圖像灰度直方圖與假設(shè)的混合高斯分布之間差別最小，本質(zhì)是最小誤差化的高斯密度擬合問題[17-18].

假設(shè)圖形前景和背景均符合一混合高斯分布，即

式中：j = 0，1分別代表背景和前景；Pj為背景A0和前景A1的先驗概率，且Aj的概率分布p(i│j) 全部服從均值為 μj、方差為的高斯分布[19-21]，

若g 為圖像的分割閾值，即A0=（0，1，···，g）， A1=（g+1，g+2，···，255），則它們各自的先驗概率 P0（g）和 P1（g）分別為

基于貝葉斯最小分類錯誤的原理，Kittler和Illingworth對其進行了改造，得到了最小誤差目標(biāo)函數(shù) J（g）[12-13].

遍歷整幅圖灰度值，當(dāng) J（g）= min J 時 ，g 為最佳分割閾值，即

其基本流程如下所示：

步驟1 設(shè)置初始閾值g = 0；

步驟4 計算當(dāng)前背景與前景的均值和方差；

步驟6 遍歷整個灰度（0～255），將每一個灰度作為分割閾值，重復(fù)步驟2～5，確認(rèn)誤差目標(biāo)函數(shù)最小值，并將此時的g作為最終閾值.

2.2 圖像評價標(biāo)準(zhǔn)

良好的閾值分割效果不但應(yīng)該清晰分開前景與圖像背景，并且可以較完善地保留前景目標(biāo). 采用的定性定量分析和評價標(biāo)準(zhǔn)如下：

1） “優(yōu)度法”. 即人眼主觀判斷分割效果[22-23].

2） 區(qū)域一致性和區(qū)域?qū)Ρ榷? 星圖內(nèi)容整體上較為單一，但是影響成像質(zhì)量的因素較多且復(fù)雜，因而選用較為通用的區(qū)域一致性和區(qū)域?qū)Ρ榷萚11,24-28]作為此類圖像分割質(zhì)量的評價指標(biāo). 其中，區(qū)域一致表征的是圖像各區(qū)域自身內(nèi)部的共性和相似度，其數(shù)值越大一致性越強；而區(qū)域?qū)Ρ榷确从车氖乔熬昂捅尘爸g的差異性，其差異性越大，證明圖像分割后的效果越好. 文獻[11]對常見的幾種閾值分割算法進行了相關(guān)分析比較.

3） 時間復(fù)雜度. 算法的計算工作量和處理效率也是衡量其優(yōu)劣的重要指標(biāo)，常用O(n)表示，其中n為算法規(guī)模. 算法的時間復(fù)雜度由小到大如式（4）所示[29-31].

3 實驗結(jié)果與分析

首先，分別采用2種常用的局部閾值法（Bernsen算法、Niblack算法）和4種全局閾值法（迭代法、Otsu算法、一維最大熵法、Kittler算法）對實拍星圖進行閾值分割處理；利用視覺判斷、區(qū)域一致性和區(qū)域?qū)Ρ榷仍u定圖像分割質(zhì)量，并對比算法的運算效率. 然后，模擬仿真多幅星點分布于不同位置的星圖，進而評定基于Kittler最小誤差的星點提取算法的準(zhǔn)確性. 最后，通過野外天文觀測得到經(jīng)緯度測量精度，驗證基于該算法的天文測量的可靠性.

3.1 星圖分割效果

用“優(yōu)度法”對采用不同閾值分割算法處理后的拍攝星圖進行分析. 圖1（a）分別顯示了上述6種算法對TS60星圖灰度圖閾值分割后的效果，圖1（b）給出了經(jīng)驗算法和Kittler最小誤差算法分割比較圖.

圖1 分割效果的對比Fig. 1 Contrast of image segmentation

目測分割效果表明：

1） 一維最大熵法和Kittler最小誤差算法對此類星圖具有良好的處理效果，能夠順利實現(xiàn)圖像分割（圖1（a）⑤～⑥）. 通過這兩種算法處理過后，星點目標(biāo)呈現(xiàn)清晰明顯，能夠容易分辨前景和背景，圖像分割效果良好. 而常規(guī)分割算法均處理失敗，全局閾值法易產(chǎn)生大量噪聲（圖1（a）①～②），局部閾值法在處理時易出現(xiàn)目標(biāo)偽影或丟失目標(biāo)輪廓（圖 1（a）③～④）.

2） 因星圖特點單一，采用經(jīng)驗算法人工選取高灰度作為分割閾值也可以實現(xiàn)分割，但分割效果較一維最大熵法和Kittler最小誤差算法欠佳（圖1（b）②）.閾值設(shè)置過低會導(dǎo)致圖像出現(xiàn)大量“偽星點”，甚至可能將其錯分為正常的待測目標(biāo)（圖1（b）③）. 當(dāng)設(shè)置過高時，目標(biāo)范圍受到嚴(yán)重影響，原有的星點輪廓大概率發(fā)生畸變（圖1（b）④）.

表1列出了6種算法處理上述星圖的區(qū)域一致性、區(qū)域?qū)Ρ榷取r間復(fù)雜度和處理時間. 其中，由于局部閾值法效率較低，處理時間為單幅圖所用時間，全局閾值法為100幅圖的處理時間. 顯然，一維最大熵法和最小誤差法在評價標(biāo)準(zhǔn)上結(jié)果相當(dāng)，都可以良好地分割拍攝星圖，與人眼觀測結(jié)果一致.

表1 星圖閾值分割算法效果評價Tab. 1 Resultevaluation of star image threshold segmentation algorithms

值得注意的是，對于實時處理的數(shù)據(jù)，算法執(zhí)行效率十分重要. 進行天文測量需要處理的星圖往往需要數(shù)百幅，若對多個天文點多個時段進行測量時，星圖數(shù)量可達上千幅. 實驗表明，相較于一維最大熵法的復(fù)雜度，最小誤差法算法效率更高，可以在較好滿足優(yōu)度法、區(qū)域一致性和區(qū)域?qū)Ρ榷鹊那疤嵯?，大幅提高計算效率，更適合對實時要求較高測量數(shù)據(jù)處理. 對某天文點某時段拍攝的300幅星圖進行處理，平均處理效率比一維最大熵法提高5～6倍，處理時間減少約70%. 特別是當(dāng)拍攝圖像質(zhì)量不佳，甚至出現(xiàn)星點目標(biāo)離焦、模糊時，最小誤差算法明顯快于一維最大熵法.

3.2 室內(nèi)試驗精度

圖像分割特征的良好性是星點提取精度的前提. 由于星點質(zhì)心坐標(biāo)真值無法獲得，現(xiàn)對50幅基于野外真實拍攝的半仿真星圖和50幅實拍星圖進行處理，其中仿真星圖星點僅為人工添加（圖2給出了其中一幅）.

圖2 試驗星圖Fig. 2 Experimental star maps

求取星點質(zhì)心坐標(biāo)的流程如下：對星圖采用YUV（luminance-bandwidth-chrominance）色彩空間法進行灰度化處理，采用均值濾波和中值濾波去噪，通過連通域法進行星點提取，并利用灰度質(zhì)心法求取星點的質(zhì)心坐標(biāo). TS60的相機參數(shù)決定了天文精度指標(biāo)參數(shù)，若質(zhì)心提取精度優(yōu)于0.18個像素，可以滿足一等天文測量精度.

圖3給出了Kittler算法和一維最大熵方法分割提取的星點坐標(biāo)誤差分布. 顯然，兩種算法提取誤差均落在一等天文精度的誤差圓中，且集中在圓心附近. 一維最大熵法的水平（x）和垂直（y）方向均方根誤差（root mean squared error，RMSE）分別為0.021 像素和0.019像素，Kittler算法水平和垂直方向 RMSE則分別為0.025像素和0.019像素.

圖3 算法誤差分布Fig. 3 Algorithm error profile

實驗數(shù)據(jù)表明兩種算法提取真實星圖恒星坐標(biāo)的精度相當(dāng)，同3.1節(jié)星圖閾值分割效果的結(jié)果相符.其中，水平方向最大互差為0.205像素，最小互差0.038像素，平均互差為0.018像素，垂直方向最大互差0.233像素，最小互差0.002像素，平均互差0.019像素. 表2進一步給出了基于兩種分割算法得到的部份野外星圖質(zhì)心坐標(biāo)比較，表中Δx、Δy分別為質(zhì)心坐標(biāo)x、y的誤差.

表2 星點提取精度誤差表Tab. 2 Errors of star extraction accuracy

3.3 天文定位精度

為進一步驗證Kittler算法的可靠性，進行了野外自動天文測量. 在不同的基本天文測量點，分別選取8個時段，獲取900余幅星圖. 采用Kittler最小誤差法進行閾值分割，通過連通域法進行星點提取，并利用灰度質(zhì)心法求取星點的質(zhì)心坐標(biāo)，進而解算基本天文點的天文經(jīng)緯度.

天文點位置解算的精度評估方法如下：

1） 內(nèi)符合精度，用來衡量觀測值與觀測均值之間的誤差，表3給出了其具體精度指標(biāo).

2） 外符合精度，用來評定測量值與基本天文測量點的誤差.

表3 野外天文測量精度指標(biāo)Tab. 3 Accuracy index of astronomical survey

按照一等天文測量精度要求，對同一天文點兩次測量結(jié)果差值的中誤差分別為

式中：mlong、mlat分別為經(jīng)、緯度中誤差；mlong1、mlong2和mlat1、mlat2分別為第 1、2次測量得經(jīng)度值和緯度值.

若取2倍中誤差作為限差，則對同一天文點兩次測量結(jié)果差值中誤差分別為

測量數(shù)據(jù)顯示基于Kittler最小誤差算法的定位結(jié)果內(nèi)符合精度和外符合精度良好，滿足一等天文測量的要求. 測量結(jié)果如表4、表5所示，其中表4給出了內(nèi)符合精度分布，經(jīng)、緯度內(nèi)符合平均精度分別優(yōu)于0.015 s和0.22″. 表5給出了外符合精度分布，與已知的天文大地點坐標(biāo)相比，經(jīng)、緯度方向RMSE分別為0.023 s和0.33″，所有經(jīng)、緯度測量結(jié)果按2倍中誤差衡量均滿足一等測量精度要求.表6進一步給出了部分時段的野外測量結(jié)果.

表4 內(nèi)符合精度Tab. 4 Internal accordant accuracy

表5 外符合精度Tab. 5 External accordant accuracy

表6 野外實測結(jié)果Tab. 6 Fieldtest results

可以明顯看出，由于受到星點提取誤差、時間延遲不穩(wěn)定和坐標(biāo)轉(zhuǎn)換誤差等因素的影響，天文定位整體外符合精度低于內(nèi)符合精度，測量結(jié)果符合理論預(yù)期.

4 結(jié) 論

面向基于視頻測量機器人的自動天文測量，以TS60系列全站儀為具體測量平臺，針對常用閾值分割算法效果不佳或效率較低的局限，在取得良好星圖處理效果的基礎(chǔ)上，為進一步滿足實時化處理要求，提出采用Kittler最小誤差算法處理拍攝星圖. 根據(jù)小視場星圖的圖像特征，對比了不同閾值算法的分割效果，給出了Kittler算法和一維最大熵室內(nèi)星點質(zhì)心提取精度的比較，最后利用基于Kittler最小誤差法的數(shù)據(jù)處理方法解算野外實測數(shù)據(jù)，得到了基于該算法的實際天文定位結(jié)果. 試驗表明：

1） Kittler最小誤差算法對小視場星圖均具有良好的分割效果. 對實際拍攝星圖進行分割處理，其效果與一維最大熵法處理效果相仿，優(yōu)于常見的閾值分割效果，具有良好的適用性.

2） Kittler最小誤差算法計算復(fù)雜度低、執(zhí)行效率高，可以進一步滿足天文測量的實時化處理要求.通過對大量星圖處理，結(jié)果表明較一維最大熵法，其處理效率大幅提高，平均處理時間可以減少約70%.

3） 基于Kittler最小誤差法的星點提取算法可以準(zhǔn)確獲取星點像素坐標(biāo)，與一維最大熵法精度相當(dāng). 其中，與模擬星點真實坐標(biāo)相比，水平方向RMSE為0.025像素，垂直方向RMSE為0.019像素，與一維最大熵提取真實星圖質(zhì)心坐標(biāo)相比，水平方向平均互差為0.018像素，垂直方向平均互差0.019像素.

4） 野外實測表明：基于Kittler最小誤差法的自動天文測量模式具有可靠性，定位結(jié)果的內(nèi)符合精度與外符合精度良好. 其中，經(jīng)、緯度內(nèi)符合平均精度分別優(yōu)于0.015 s和0.22″，與基本天文測量點坐標(biāo)相比，經(jīng)緯度RMSE分別優(yōu)于0.025 s和0.35″.

值得說明的是，在進行CCD觀測時無論是否打開儀器視場燈，其星圖整體灰度分布依舊呈現(xiàn)高斯分布，利用Kittler最小誤差算法同樣可以順利分割圖像，證明最小誤差法對此類星圖的光照分布不均勻并不敏感. 但是，對于如魚眼相機等拍攝的某些超大視場星圖，其灰度整體分布不同于小視場星圖，且這類星圖的光照條件嚴(yán)重影響星圖灰度分布，此時Kittler最小誤差算法圖形分割失敗，不再適用.