基于二分法的车站地形

2013-05-09刘红英北京全路通信信号研究设计院有限公司北京100073

铁路通信信号工程技术 2013年1期

关键词：二分法折线区段

刘红英（北京全路通信信号研究设计院有限公司，北京 100073）

1 问题和现状

精确的火车站的站形图对于机车自动遥控、防护都有极其重要的作用。然而目前还没有有效的手段获取火车站的站形图。基本上有以下几种途径。

1）设计方提供的施工图。火车站在建设的过程中，受地形地貌的影响很大。很多实际建设的线路会和设计图相差较大。所以区段的长度与施工图有很大出入。而施工结束后，并没有对全场进行重新测绘。

2）打点测绘。

使用具有差分功能的测量型双频高精度GPS全球定位仪器，根据调机自动化系统的需要。安排专门的测绘人员，持手持设备对绝缘节数据进行测绘。一方面工作强度大，工作时间长，不利于提高系统的完工时间。另一方面，受人为判断估计因素的影响，数据不够准确。

3）GPS数据。机车走行过程中，所接收的GPS数据以点的形式，描述了机车所走行的轨迹。使用统计的方法，从这些轨迹中自动生成站形图。本文就是采用这种方法自动生成站形图。常用的图形自动生成方式：直方图[1]、聚类等方法。

刘红英,女,毕业于中国农业大学, 高级工程师。主要研究方向为机车信号自动控制，曾参与调车机车自动驾驶系统在编组站的应用、编组站调机自动化系统升级的研究。

2 基于二分法的站场图形生成系统

本文提出的算法可以根据机车上安装的GPS接收设备自动根据GPS坐标生成站场图形，并且在使用的过程中，不断精确化。

2.1 区段点集合

根据机车上安装的GPS设备，在机车运动的过程中，不断记录GPS点的坐标，形成一个点集合。每个点有下列属性：机车号、时间、所属的区段信息，机车头向。根据这些信息，可以获取区段点集合。假定一个点可以用一个向量表示如公式（1）所示，假定整个站场所有点集合为E，共有m个区段，如公式（3）所示，第h个区段有点hn个。如公式（2）所示。

区段是指在一次机车走行过程，不掉头所走过的一段独立的轨道电路。所以这里的区段和实际所说的区段有些区别。

图1所示的是车站常见的一组道岔形成的一个区段。绝缘节的点分别是A，B,C。实际上ABC三点形成了一个区段。本文所述的区段指在一次机车走行过程，不掉头所走过的一段独立的轨道电路，因此机车在一次走行过程中，不可能同时过B点和C点的，在一次走行过程中，只可能形成如(b)或者(c)所示的形状。

本文所述的区段定义如下，假定在该区段上任意取三点，分别为A、X、B，其中A、B在X两侧。他们同时满足下式

公式(4)是对车站地形图的一个保守描述，实际上车站99.9%的线路符合上述要求，限制了两个线段的长度是将一些曲线也纳入到该假设中。比如车站灯泡线。这个条件也是本文下述的二分法的唯一的前提假设条件。

2.2 线段

对于每个区段点集，如何得到对应的直线方程，每个区段的轨迹有可能是单一直线组成，如某些无叉区段，有可能是折线组成，如图1中的AB区段，中间可能还有一些曲线组成的。图1所示的道岔是示意图，实际上车站线路是不存在这些折角的，都会有曲线过渡。但对于这些不规则的曲线，用计算机拟合比较困难，因此本文假定都是折线。对于曲线，采用以折线分段逼近的方式拟合。因此在本文中，假定所有的区段都是折线组成。

1）最小二乘法[2]

对于一个区段点集，系统首先假定它是直线。不失一般性，采用一元线性回归模型

如果站场直线是垂直于坐标系X轴的，公式(5)将不适用。但实际上对于这样的区段点集，只需要简单地坐标旋转一下就可以了。根据克莱姆法则，得到和的值如公式(6)(推导过程参见相关文献)，假定区段点集中的点数是n个点。

图2所示，是采用最小二乘法拟合的直线AB。

2）检验标准

因为区段有可能由不同斜率的折线组成，因此需要有一个标准来判断采用最小二乘法拟合的直线是否可以采纳。比较常用的标准是样本的方差，但在本文中不适用。方差的大小和很多因素有关系，不同的车站，不同调机收集的样本点方差可能差别比较大。因此方差不是一个合适的检验标准。

在本文中采用拟合度来检验最小二乘法的结果是否可用，拟合度[3]定义如下，以表示点集中所有的y的均值。同样，以表示点集中所有的x的均值。而表示对应第i个样本点（xi,yi）的估计值，即采纳最小二乘法拟合出的直线后，根据直线方程计算出来的值。

公式（7）的分子部分SSR表示回归解释方差，就是可以由最小二乘法拟合出的直线方程解释的方差。而分母SST是总变差。SSE表示剩余方差，即没有被回归方程解释的方差。

拟合度γ2的取值范围是在0和1之间。而且该值仅仅表征直线拟合的程度，因此在不同车站，不同点集之间差别不大。因此比较适合作为检验标准。

在本文中，需要确定一个拟合度阈值，当拟合度大于阈值时，认为拟合的直线方程可以采纳，比如对于一些无岔区段，根据区段点集拟合的直线，其拟合度大于阈值，认为该直线可以被采纳，作为站场图形的一部分。否则认为拟合的直线方程不可以采纳。

3）二分法

虽然使用最小二乘法拟合出的直线，如图2中的直线A B，因为拟合度小于阈值，不能作为最终结果，但这条线可以得到区段点集的点的分布状况，需要根据分布状态做进一步处理。

对于拟合度过小的直线，如图2所示。根据直线方向，将区段点集做一次切分。该切分是盲目的，因此在系统中，统一在最小二乘法拟合的直线1/2处切分。如图2的绿色线所切分的那样。

具体如何切分，需要根据应用而有不同的切分方法，在本文所述的系统中，先在拟合的直线方向进行一次直方图统计，滤掉小于均值1/3的点，如图2所示，滤掉A左边的点和B右边的点，在剩下的AB两个点之间取一个中值。如图2中的绿色线路。将区段线集分成两个较小的子区段线集，重新进行二乘法拟合。

图2是一次切分，图3显示了后继的二分法切分的详细过程。在二次切分后，X 1，X3，X 4等3段，其拟合值大于阈值，采纳这3条直线。而X 2还需要继续切分成X 21和X 22（图3（c））。最终形成了图3（d）所示的5段折线。

4）二分法终止标准

* 拟合度大于阈值

很明显，当拟合度大于给定的阈值，则系统认为拟合的直线就是需要的直线。比如图3中的在二次切分后的X 1段。这种情况是二分法正常结束条件。实际上无论是曲线，还是折线，在指定的精度范围内，都可以使用有限个折线来拟合。

* 直线方向距离大于Δl。

采集的点呈正态分布，假定正态分布的方差为σ2,点分布方向的直线长度为L。则应该满足公式(8)

对于不同调机，其采集的点的正态分布的方差差别比较大。系统统一取保守阈值Δl=3 m。虽然该值远大于4×σ，但因为对应用而言，小于3 m以下的细节基本上都是曲线组成。因此没有必要考虑3 m以下的线段。对于小于阈值的Δl，系统将停止切分，并且抛掉该点集。

* 点集中的点数大于Δn

对于最小二乘法算法而言，足够的样本点是一个基本条件。对于本系统，样本点的采集很简单，因此在本系统中设置的样本点阈值是Δn=30。当样本点小于阈值Δn时，系统将停止切分，并且抛掉该点集。

5）二分法完整算法

* 将所有点集压入队列Q；

* 如果Q为空，则退出；

* 取出一个点集Ψh；

* 拟合直线AB；

* 如果γ2＞Δγ，则保存直线AB；

* 如果L＞=Δl且Ψh的点数大于|Ψh|≥Δn，切分点集Ψh为Ψhl和Ψh2，并且将Ψh1和Ψh2分别压入队列Q；

* 回到第二步。

本系统采用的二分法，鲁棒性较好，不仅可以对折线区段进行拟合，而且可以对曲线进行拟合。所需要参数较少，适用性广。

2.3 站场图

通过上述的二分法，得到都是一些局部的线段。还需要将这些散乱的线段，有序的整理结合起来，形成需要的车站地形图。通过拟合的直线，可以知道直线的两个端点，直线所对应的点集。

2.3.1 区段内连接

通过区段点集二分，得到的都是线段，所以连接基本上都是直线和直线之间的连接。区段内点集拟合出的线段都符合公式(4)的假设，并且这些线段之间的邻接关系是确切的。比如对图3拟合的直线，X 1和X 21，X 21和X 22等肯定是邻接的。

图4例举了区段内线段的关系，还有一种是平行关系，平行可以假定其交点在无限远处，归为图4中的（d）。

对于区段内直线合并，是先求交点，如果X和另外两个点形成的折角大于90°，即∠AXD＞90°，符合公式(4)，那么接受这个交点，并且修改对应线段的端点，将两条线段连接起来，并且修改两条直线对应的点集。图4中的前3个示例，其交点是符合公式(4)的假设。因此接受该交点，并且修改直线AB为AX，修改CD为XD。

很显然，图4（d）是不符合公式(4)的假设。对于这种情况，一种方法是将这条直线对应的点集合并为一个点集，重新二分拟合。但这样可能出现相同的结果。因此在系统中采用简单地处理，即根据对应的点集，求其综合的斜率和截距。

假定两条直线分别为li,lj，|Ψi|表示直线li对应的点集个数，|Ψj|表示直线lj对应

区段内的直线都按照上述的方法，顺次连接形成区段直线。如图3中的（d）。这样，每个区段就形成由一条至多条折线，首尾相连，表示一个区段。

2.3.2 区段间相连

1）同一轨道区段的线段处理。

同一轨道区段是指共享一个轨道电路的道岔区，如图5所示。一个大区段包含许多子区段，这些子区段有些重叠，这些子区段都会互相交叉。如图1的AB和AC。合并区段内的子区段时，需要用到一些先验知识，比如道岔的型号、开口角度、大小等。以及站场上的平行线路至少相距5 m等。将重合的部分合成一条直线。合并子段的过程大致如图5所示，根据前面的二分得到两个子段，ABC和DEF。合并步骤如下。

* 合并重叠的直线。将比较靠近，并且近似平行的直线合成一条直线。合并的方法参见公式(9)和(10)。

* 重新计算子段内各个折线的交点。由于AB和DE合成了线段M N，则以前和A B和CD相交的线段BC和EF需要重新计算和新的线段M N的交点。如图5所示，他们的交点R和T。

* 根据道岔的先验知识，R和T肯定是一个点。合并两个点成S，本文就取R和T的中值。

* 合成最终的道岔形状如图5(d)所示。

2）不同轨道区段的线段处理

区段间的线段相互关系如图6所示，大约有4种关系。

在连接不同段时，需要使用段关系表，段关系表是描述子段前后关系的表，可以从段关系表中获取那些段需要连接。在连接两个段时，采用移动端点的方法，不再改变直线另外一个端点。

3）后处理

后处理主要是平滑和削除过多的交点。根据道岔的型号和形状，做一些局部的校正。

4）定位绝缘节。

定位绝缘节是站场图形拟合的关键一步，机车在行驶的过程中，不断接受GPS坐标和轨道电路信息，当轨道电路信息发生变化的GPS点就是绝缘节的位置。定位绝缘节时，需要考虑到机车运行方向，机车速度，轨道电路接收，GPS接收等延迟量。绝缘点的计算主要是采用移动平均的方法，根据很多离散点，计算一个最佳点。不在本文讨论范围。

绝缘节定位好后，根据就近原则，将其镶嵌在前面拟合好的站场图上。然后根据绝缘节的位置，重新划分子段。