基于Kittler最小误差分割算法的小视场星图分割

时春霖 ，杨培章 ，张 超 ，杜 兰 ,，叶 凯 ,5，范承啸 ，李 建 ，祖安然

（1. 信息工程大学地理空间信息学院，河南 郑州 450001；2. 中国人民解放军61206部队，北京 100042；3. 中国人民解放军空军政治工作部，北京 100843；4. 北京卫星导航中心，北京 100094；5. 北京航天飞行控制中心，北京100089）

天文测量是通过观测恒星位置以确定载体的天文坐标，或者确定两点间天文方位角的测量工作[1-3].天文测量在大地网起始数据和垂线偏差测定，以及精密工程和国防科技领域，都有着不可替代的作用.随着精密测量仪器的飞速发展，天文测量正在逐渐摆脱人工模式向高效自动化发展.

视频全站仪将 CCD （charge coupled device）技术与全站仪一体化，从而推动了自动天文测量向小型化和智能化发展. CCD 相机获取恒星影像，全站仪获取恒星方位信息（水平角和垂直角），数字图像处理技术提取恒星的像点坐标，最终利用坐标转换和天文定位原理等获得测站的天文坐标[4-7].

视频全站仪通常仅拍摄单颗恒星的小视场星图. 一方面，其CCD为小视场角的长焦相机；另一方面，为提高天文观测可靠性和效率，天文观测星表严格限制“双星”出现. 但是，这种小视场星图仍存在背景复杂和噪声较高的特点. 除星空背景光的干扰，还经常会掺入视场灯的影响，给目标恒星识别和坐标提取带来了很大的困难.

阈值分割算法是小视场星图识别的重要一环.其中，局部阈值法针对这种结构单一的星图并不适用，效率低且容易造成“过曝”[8-10]. 因此，应选用光强适应较好、抗噪能力较强的全局阈值算法. 文献[11]指出，即使传统常用的全局阈值分割算法处理星图失效时，一维最大熵法仍能够具有良好的分割效果. 但是其运算效率在全局阈值法中较低，无法满足日益增长的实时化要求.

小视场星图的图像特征恰好符合Kittler最小误差法的适用条件. Kittler算法要求理想的前景和背景灰度分布服从混合高斯分布，而二者又均服从同一高斯分布[12-19]. 实际中符合此特征中的图像并不多见，因而大大限制了Kittler算法的应用. 但是，小视场星图中，灰度值较低的夜景占有很大比例，而灰度值较高的星点像素数很少，整幅图像灰度呈现近似高斯分布的数学特征. 因此，针对这种星图，Kittler算法不仅可最大限度减少背景和前景错分可能，且其时间复杂度较低，可加快图像处理速度.

本文以Leica-60全站仪（简称TS60）为测量平台，提出Kittler最小误差分割算法，替代目前使用的一维最大熵法处理小视场星图. 首先，介绍了基于Kittler最小误差的阈值分割算法；其次，对比了几种阈值分割效果和运行效率，给出了定性定量评价，指出Kittler最小误差算法对小视场星图具有良好的处理效果的同时，可以大幅减少处理时间；然后，采用一维最大熵和最小误差法对室内星图处理结果进行比较，证明该算法的适用性和准确性；最后，通过实际野外天文测量，利用基于该算法的自动天文测量模式，证明了该算法的可靠性.

1 基于视频全站仪的天文定位

基于全站仪的天文定位与常规天文定位的流程和仪器基本相同. 例如，测量员预先编制等高星表，通过北极星实现天文定向，天文授时采用GNSS（global navigation satellite system）接收机，守时采用计算机的内部晶振.

视频全站仪的测量自动化流程如下：测量机器人根据观测星表，自动转向待测恒星进行连续跟踪；测量员启动观测键，激活CCD图像记录模式，则进入自动测量. 然后进行下一颗恒星的转向-跟踪-测量.

自动测量则通过星图处理，提取星点CCD坐标并转换为恒星的观测坐标，进而解算得到本地的天文坐标. 因此，星图的处理能力和效率，决定了自动天文测量的数据解算质量.

2 Kittler最小误差阈值分割算法

2.1 Kittler算法

Kittler最小误差分割算法对于目标和背景呈现高斯分布的图像具有良好的处理效果，且效率较快. 1986年，Kitter和Illingworth基于贝叶斯最小误差理论的思想，将图像阈值分割问题转化为最小误差化的高斯分布拟合问题[12-13]. 文献[14-15]从相对熵理论（又称KL（Kullback-Leibler）散度或信息散度）对Kittler最小误差法进行了解释和论证，为其奠定了理论基础. 文献[15-16]对其图像分割效果和执行效率进行了分析. 该算法要求拍摄的图像灰度直方图与假设的混合高斯分布之间差别最小，本质是最小误差化的高斯密度拟合问题[17-18].

假设图形前景和背景均符合一混合高斯分布，即

式中：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对其进行了改造，得到了最小误差目标函数 J（g）[12-13].

遍历整幅图灰度值，当 J（g）= min J 时 ，g 为最佳分割阈值，即

其基本流程如下所示：

步骤1 设置初始阈值g = 0；

步骤4 计算当前背景与前景的均值和方差；

步骤6 遍历整个灰度（0～255），将每一个灰度作为分割阈值，重复步骤2～5，确认误差目标函数最小值，并将此时的g作为最终阈值.

2.2 图像评价标准

良好的阈值分割效果不但应该清晰分开前景与图像背景，并且可以较完善地保留前景目标. 采用的定性定量分析和评价标准如下：

1） “优度法”. 即人眼主观判断分割效果[22-23].

2） 区域一致性和区域对比度. 星图内容整体上较为单一，但是影响成像质量的因素较多且复杂，因而选用较为通用的区域一致性和区域对比度[11,24-28]作为此类图像分割质量的评价指标. 其中，区域一致表征的是图像各区域自身内部的共性和相似度，其数值越大一致性越强；而区域对比度反映的是前景和背景之间的差异性，其差异性越大，证明图像分割后的效果越好. 文献[11]对常见的几种阈值分割算法进行了相关分析比较.

3） 时间复杂度. 算法的计算工作量和处理效率也是衡量其优劣的重要指标，常用O(n)表示，其中n为算法规模. 算法的时间复杂度由小到大如式（4）所示[29-31].

3 实验结果与分析

首先，分别采用2种常用的局部阈值法（Bernsen算法、Niblack算法）和4种全局阈值法（迭代法、Otsu算法、一维最大熵法、Kittler算法）对实拍星图进行阈值分割处理；利用视觉判断、区域一致性和区域对比度评定图像分割质量，并对比算法的运算效率. 然后，模拟仿真多幅星点分布于不同位置的星图，进而评定基于Kittler最小误差的星点提取算法的准确性. 最后，通过野外天文观测得到经纬度测量精度，验证基于该算法的天文测量的可靠性.

3.1 星图分割效果

用“优度法”对采用不同阈值分割算法处理后的拍摄星图进行分析. 图1（a）分别显示了上述6种算法对TS60星图灰度图阈值分割后的效果，图1（b）给出了经验算法和Kittler最小误差算法分割比较图.

图1 分割效果的对比Fig. 1 Contrast of image segmentation

目测分割效果表明：

1） 一维最大熵法和Kittler最小误差算法对此类星图具有良好的处理效果，能够顺利实现图像分割（图1（a）⑤～⑥）. 通过这两种算法处理过后，星点目标呈现清晰明显，能够容易分辨前景和背景，图像分割效果良好. 而常规分割算法均处理失败，全局阈值法易产生大量噪声（图1（a）①～②），局部阈值法在处理时易出现目标伪影或丢失目标轮廓（图 1（a）③～④）.

2） 因星图特点单一，采用经验算法人工选取高灰度作为分割阈值也可以实现分割，但分割效果较一维最大熵法和Kittler最小误差算法欠佳（图1（b）②）.阈值设置过低会导致图像出现大量“伪星点”，甚至可能将其错分为正常的待测目标（图1（b）③）. 当设置过高时，目标范围受到严重影响，原有的星点轮廓大概率发生畸变（图1（b）④）.

表1列出了6种算法处理上述星图的区域一致性、区域对比度、时间复杂度和处理时间. 其中，由于局部阈值法效率较低，处理时间为单幅图所用时间，全局阈值法为100幅图的处理时间. 显然，一维最大熵法和最小误差法在评价标准上结果相当，都可以良好地分割拍摄星图，与人眼观测结果一致.

表1 星图阈值分割算法效果评价Tab. 1 Resultevaluation of star image threshold segmentation algorithms

值得注意的是，对于实时处理的数据，算法执行效率十分重要. 进行天文测量需要处理的星图往往需要数百幅，若对多个天文点多个时段进行测量时，星图数量可达上千幅. 实验表明，相较于一维最大熵法的复杂度，最小误差法算法效率更高，可以在较好满足优度法、区域一致性和区域对比度的前提下，大幅提高计算效率，更适合对实时要求较高测量数据处理. 对某天文点某时段拍摄的300幅星图进行处理，平均处理效率比一维最大熵法提高5～6倍，处理时间减少约70%. 特别是当拍摄图像质量不佳，甚至出现星点目标离焦、模糊时，最小误差算法明显快于一维最大熵法.

3.2 室内试验精度

图像分割特征的良好性是星点提取精度的前提. 由于星点质心坐标真值无法获得，现对50幅基于野外真实拍摄的半仿真星图和50幅实拍星图进行处理，其中仿真星图星点仅为人工添加（图2给出了其中一幅）.

图2 试验星图Fig. 2 Experimental star maps

求取星点质心坐标的流程如下：对星图采用YUV（luminance-bandwidth-chrominance）色彩空间法进行灰度化处理，采用均值滤波和中值滤波去噪，通过连通域法进行星点提取，并利用灰度质心法求取星点的质心坐标. TS60的相机参数决定了天文精度指标参数，若质心提取精度优于0.18个像素，可以满足一等天文测量精度.

图3给出了Kittler算法和一维最大熵方法分割提取的星点坐标误差分布. 显然，两种算法提取误差均落在一等天文精度的误差圆中，且集中在圆心附近. 一维最大熵法的水平（x）和垂直（y）方向均方根误差（root mean squared error，RMSE）分别为0.021 像素和0.019像素，Kittler算法水平和垂直方向 RMSE则分别为0.025像素和0.019像素.

图3 算法误差分布Fig. 3 Algorithm error profile

实验数据表明两种算法提取真实星图恒星坐标的精度相当，同3.1节星图阈值分割效果的结果相符.其中，水平方向最大互差为0.205像素，最小互差0.038像素，平均互差为0.018像素，垂直方向最大互差0.233像素，最小互差0.002像素，平均互差0.019像素. 表2进一步给出了基于两种分割算法得到的部份野外星图质心坐标比较，表中Δx、Δy分别为质心坐标x、y的误差.

表2 星点提取精度误差表Tab. 2 Errors of star extraction accuracy

3.3 天文定位精度

为进一步验证Kittler算法的可靠性，进行了野外自动天文测量. 在不同的基本天文测量点，分别选取8个时段，获取900余幅星图. 采用Kittler最小误差法进行阈值分割，通过连通域法进行星点提取，并利用灰度质心法求取星点的质心坐标，进而解算基本天文点的天文经纬度.

天文点位置解算的精度评估方法如下：

1） 内符合精度，用来衡量观测值与观测均值之间的误差，表3给出了其具体精度指标.

2） 外符合精度，用来评定测量值与基本天文测量点的误差.

表3 野外天文测量精度指标Tab. 3 Accuracy index of astronomical survey

按照一等天文测量精度要求，对同一天文点两次测量结果差值的中误差分别为

式中：mlong、mlat分别为经、纬度中误差；mlong1、mlong2和mlat1、mlat2分别为第 1、2次测量得经度值和纬度值.

若取2倍中误差作为限差，则对同一天文点两次测量结果差值中误差分别为

测量数据显示基于Kittler最小误差算法的定位结果内符合精度和外符合精度良好，满足一等天文测量的要求. 测量结果如表4、表5所示，其中表4给出了内符合精度分布，经、纬度内符合平均精度分别优于0.015 s和0.22″. 表5给出了外符合精度分布，与已知的天文大地点坐标相比，经、纬度方向RMSE分别为0.023 s和0.33″，所有经、纬度测量结果按2倍中误差衡量均满足一等测量精度要求.表6进一步给出了部分时段的野外测量结果.

表4 内符合精度Tab. 4 Internal accordant accuracy

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

表6 野外实测结果Tab. 6 Fieldtest results

可以明显看出，由于受到星点提取误差、时间延迟不稳定和坐标转换误差等因素的影响，天文定位整体外符合精度低于内符合精度，测量结果符合理论预期.

4 结 论

面向基于视频测量机器人的自动天文测量，以TS60系列全站仪为具体测量平台，针对常用阈值分割算法效果不佳或效率较低的局限，在取得良好星图处理效果的基础上，为进一步满足实时化处理要求，提出采用Kittler最小误差算法处理拍摄星图. 根据小视场星图的图像特征，对比了不同阈值算法的分割效果，给出了Kittler算法和一维最大熵室内星点质心提取精度的比较，最后利用基于Kittler最小误差法的数据处理方法解算野外实测数据，得到了基于该算法的实际天文定位结果. 试验表明：

1） Kittler最小误差算法对小视场星图均具有良好的分割效果. 对实际拍摄星图进行分割处理，其效果与一维最大熵法处理效果相仿，优于常见的阈值分割效果，具有良好的适用性.

2） Kittler最小误差算法计算复杂度低、执行效率高，可以进一步满足天文测量的实时化处理要求.通过对大量星图处理，结果表明较一维最大熵法，其处理效率大幅提高，平均处理时间可以减少约70%.

3） 基于Kittler最小误差法的星点提取算法可以准确获取星点像素坐标，与一维最大熵法精度相当. 其中，与模拟星点真实坐标相比，水平方向RMSE为0.025像素，垂直方向RMSE为0.019像素，与一维最大熵提取真实星图质心坐标相比，水平方向平均互差为0.018像素，垂直方向平均互差0.019像素.

4） 野外实测表明：基于Kittler最小误差法的自动天文测量模式具有可靠性，定位结果的内符合精度与外符合精度良好. 其中，经、纬度内符合平均精度分别优于0.015 s和0.22″，与基本天文测量点坐标相比，经纬度RMSE分别优于0.025 s和0.35″.

值得说明的是，在进行CCD观测时无论是否打开仪器视场灯，其星图整体灰度分布依旧呈现高斯分布，利用Kittler最小误差算法同样可以顺利分割图像，证明最小误差法对此类星图的光照分布不均匀并不敏感. 但是，对于如鱼眼相机等拍摄的某些超大视场星图，其灰度整体分布不同于小视场星图，且这类星图的光照条件严重影响星图灰度分布，此时Kittler最小误差算法图形分割失败，不再适用.