基于二分法的車站地形

2013-05-09 12:48:10劉紅英北京全路通信信號研究設計院有限公司北京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接收等延遲量。絕緣點的計算主要是采用移動平均的方法，根據很多離散點，計算一個最佳點。不在本文討論范圍。

絕緣節定位好后，根據就近原則，將其鑲嵌在前面擬合好的站場圖上。然后根據絕緣節的位置，重新劃分子段。