基于二分法的車站地形

劉紅英（北京全路通信信號研究設(shè)計院有限公司，北京 100073）

1 問題和現(xiàn)狀

精確的火車站的站形圖對于機車自動遙控、防護都有極其重要的作用。然而目前還沒有有效的手段獲取火車站的站形圖?；旧嫌幸韵聨追N途徑。

1）設(shè)計方提供的施工圖。火車站在建設(shè)的過程中，受地形地貌的影響很大。很多實際建設(shè)的線路會和設(shè)計圖相差較大。所以區(qū)段的長度與施工圖有很大出入。而施工結(jié)束后，并沒有對全場進行重新測繪。

2）打點測繪。

使用具有差分功能的測量型雙頻高精度GPS全球定位儀器，根據(jù)調(diào)機自動化系統(tǒng)的需要。安排專門的測繪人員，持手持設(shè)備對絕緣節(jié)數(shù)據(jù)進行測繪。一方面工作強度大，工作時間長，不利于提高系統(tǒng)的完工時間。另一方面，受人為判斷估計因素的影響，數(shù)據(jù)不夠準(zhǔn)確。

3）GPS數(shù)據(jù)。機車走行過程中，所接收的GPS數(shù)據(jù)以點的形式，描述了機車所走行的軌跡。使用統(tǒng)計的方法，從這些軌跡中自動生成站形圖。本文就是采用這種方法自動生成站形圖。常用的圖形自動生成方式：直方圖[1]、聚類等方法。

劉紅英,女,畢業(yè)于中國農(nóng)業(yè)大學(xué), 高級工程師。主要研究方向為機車信號自動控制，曾參與調(diào)車機車自動駕駛系統(tǒng)在編組站的應(yīng)用、編組站調(diào)機自動化系統(tǒng)升級的研究。

2 基于二分法的站場圖形生成系統(tǒng)

本文提出的算法可以根據(jù)機車上安裝的GPS接收設(shè)備自動根據(jù)GPS坐標(biāo)生成站場圖形，并且在使用的過程中，不斷精確化。

2.1 區(qū)段點集合

根據(jù)機車上安裝的GPS設(shè)備，在機車運動的過程中，不斷記錄GPS點的坐標(biāo)，形成一個點集合。每個點有下列屬性：機車號、時間、所屬的區(qū)段信息，機車頭向。根據(jù)這些信息，可以獲取區(qū)段點集合。假定一個點可以用一個向量表示如公式（1）所示，假定整個站場所有點集合為E， 共有m個區(qū)段，如公式（3）所示，第h個區(qū)段有點hn個。如公式（2）所示。

區(qū)段是指在一次機車走行過程，不掉頭所走過的一段獨立的軌道電路。所以這里的區(qū)段和實際所說的區(qū)段有些區(qū)別。

圖1所示的是車站常見的一組道岔形成的一個區(qū)段。絕緣節(jié)的點分別是A，B,C。實際上ABC三點形成了一個區(qū)段。本文所述的區(qū)段指在一次機車走行過程，不掉頭所走過的一段獨立的軌道電路，因此機車在一次走行過程中，不可能同時過B點和C點的，在一次走行過程中，只可能形成如(b)或者(c)所示的形狀。

本文所述的區(qū)段定義如下，假定在該區(qū)段上任意取三點，分別為A、X、B， 其中A、B在X兩側(cè)。他們同時滿足下式

公式(4)是對車站地形圖的一個保守描述，實際上車站99.9%的線路符合上述要求，限制了兩個線段的長度是將一些曲線也納入到該假設(shè)中。比如車站燈泡線。這個條件也是本文下述的二分法的唯一的前提假設(shè)條件。

2.2 線段

對于每個區(qū)段點集，如何得到對應(yīng)的直線方程，每個區(qū)段的軌跡有可能是單一直線組成，如某些無叉區(qū)段，有可能是折線組成，如圖1中的AB區(qū)段，中間可能還有一些曲線組成的。圖1所示的道岔是示意圖，實際上車站線路是不存在這些折角的，都會有曲線過渡。但對于這些不規(guī)則的曲線，用計算機擬合比較困難，因此本文假定都是折線。對于曲線，采用以折線分段逼近的方式擬合。因此在本文中，假定所有的區(qū)段都是折線組成。

1）最小二乘法[2]

對于一個區(qū)段點集，系統(tǒng)首先假定它是直線。不失一般性，采用一元線性回歸模型

如果站場直線是垂直于坐標(biāo)系X軸的，公式(5)將不適用。但實際上對于這樣的區(qū)段點集，只需要簡單地坐標(biāo)旋轉(zhuǎn)一下就可以了。根據(jù)克萊姆法則，得到 和 的值如公式(6)(推導(dǎo)過程參見相關(guān)文獻)，假定區(qū)段點集中的點數(shù)是n個點。

圖2所示，是采用最小二乘法擬合的直線AB。

2）檢驗標(biāo)準(zhǔn)

因為區(qū)段有可能由不同斜率的折線組成，因此需要有一個標(biāo)準(zhǔn)來判斷采用最小二乘法擬合的直線是否可以采納。比較常用的標(biāo)準(zhǔn)是樣本的方差，但在本文中不適用。方差的大小和很多因素有關(guān)系，不同的車站，不同調(diào)機收集的樣本點方差可能差別比較大。因此方差不是一個合適的檢驗標(biāo)準(zhǔn)。

在本文中采用擬合度來檢驗最小二乘法的結(jié)果是否可用，擬合度[3]定義如下，以 表示點集中所有的y的均值。同樣，以 表示點集中所有的x的均值。而表示對應(yīng)第i個樣本點（xi,yi）的估計值，即采納最小二乘法擬合出的直線后，根據(jù)直線方程計算出來的值。

公式（7）的分子部分SSR表示回歸解釋方差，就是可以由最小二乘法擬合出的直線方程解釋的方差。而分母SST是總變差。SSE表示剩余方差，即沒有被回歸方程解釋的方差。

擬合度γ2的取值范圍是在0和1之間。而且該值僅僅表征直線擬合的程度，因此在不同車站，不同點集之間差別不大。因此比較適合作為檢驗標(biāo)準(zhǔn)。

在本文中，需要確定一個擬合度閾值 ，當(dāng)擬合度大于閾值時，認(rèn)為擬合的直線方程可以采納，比如對于一些無岔區(qū)段，根據(jù)區(qū)段點集擬合的直線，其擬合度大于閾值，認(rèn)為該直線可以被采納，作為站場圖形的一部分。否則認(rèn)為擬合的直線方程不可以采納。

3）二分法

雖然使用最小二乘法擬合出的直線，如圖2中的直線A B，因為擬合度小于閾值，不能作為最終結(jié)果，但這條線可以得到區(qū)段點集的點的分布狀況，需要根據(jù)分布狀態(tài)做進一步處理。

對于擬合度過小的直線，如圖2所示。根據(jù)直線方向，將區(qū)段點集做一次切分。該切分是盲目的，因此在系統(tǒng)中，統(tǒng)一在最小二乘法擬合的直線1/2處切分。如圖2的綠色線所切分的那樣。

具體如何切分，需要根據(jù)應(yīng)用而有不同的切分方法，在本文所述的系統(tǒng)中，先在擬合的直線方向進行一次直方圖統(tǒng)計，濾掉小于均值1/3的點，如圖2所示，濾掉A左邊的點和B右邊的點，在剩下的AB兩個點之間取一個中值。如圖2中的綠色線路。將區(qū)段線集分成兩個較小的子區(qū)段線集，重新進行二乘法擬合。

圖2是一次切分，圖3顯示了后繼的二分法切分的詳細(xì)過程。在二次切分后，X 1，X3，X 4等3段，其擬合值大于閾值，采納這3條直線。而X 2還需要繼續(xù)切分成X 21和X 22（圖3（c））。最終形成了圖3（d）所示的5段折線。

4）二分法終止標(biāo)準(zhǔn)

* 擬合度大于閾值

很明顯，當(dāng)擬合度大于給定的閾值，則系統(tǒng)認(rèn)為擬合的直線就是需要的直線。比如圖3中的在二次切分后的X 1段。這種情況是二分法正常結(jié)束條件。實際上無論是曲線，還是折線，在指定的精度范圍內(nèi)，都可以使用有限個折線來擬合。

* 直線方向距離大于Δl。

采集的點呈正態(tài)分布，假定正態(tài)分布的方差為σ2,點分布方向的直線長度為L。則應(yīng)該滿足公式(8)

對于不同調(diào)機，其采集的點的正態(tài)分布的方差差別比較大。系統(tǒng)統(tǒng)一取保守閾值Δl=3 m。雖然該值遠(yuǎn)大于4×σ，但因為對應(yīng)用而言，小于3 m以下的細(xì)節(jié)基本上都是曲線組成。因此沒有必要考慮3 m以下的線段。對于小于閾值的Δl，系統(tǒng)將停止切分，并且拋掉該點集。

* 點集中的點數(shù)大于Δn

對于最小二乘法算法而言，足夠的樣本點是一個基本條件。對于本系統(tǒng)，樣本點的采集很簡單，因此在本系統(tǒng)中設(shè)置的樣本點閾值是Δn=30。當(dāng)樣本點小于閾值Δn時，系統(tǒng)將停止切分，并且拋掉該點集。

5）二分法完整算法

* 將所有點集壓入隊列Q；

* 如果Q為空，則退出；

* 取出一個點集Ψh；

* 擬合直線AB；

* 如果γ2＞Δγ，則保存直線AB；

* 如果L＞=Δl且Ψh的點數(shù)大于|Ψh|≥Δn，切分點集Ψh為Ψhl和Ψh2，并且將Ψh1和Ψh2分別壓入隊列Q；

* 回到第二步。

本系統(tǒng)采用的二分法，魯棒性較好，不僅可以對折線區(qū)段進行擬合，而且可以對曲線進行擬合。所需要參數(shù)較少，適用性廣。

2.3 站場圖

通過上述的二分法，得到都是一些局部的線段。還需要將這些散亂的線段，有序的整理結(jié)合起來，形成需要的車站地形圖。通過擬合的直線，可以知道直線的兩個端點，直線所對應(yīng)的點集。

2.3.1 區(qū)段內(nèi)連接

通過區(qū)段點集二分，得到的都是線段，所以連接基本上都是直線和直線之間的連接。區(qū)段內(nèi)點集擬合出的線段都符合公式(4)的假設(shè)，并且這些線段之間的鄰接關(guān)系是確切的。比如對圖3擬合的直線，X 1和X 21，X 21和X 22等肯定是鄰接的。

圖4例舉了區(qū)段內(nèi)線段的關(guān)系，還有一種是平行關(guān)系，平行可以假定其交點在無限遠(yuǎn)處，歸為圖4中的（d）。

對于區(qū)段內(nèi)直線合并，是先求交點，如果X和另外兩個點形成的折角大于90°，即∠AXD＞90°，符合公式(4)，那么接受這個交點，并且修改對應(yīng)線段的端點，將兩條線段連接起來，并且修改兩條直線對應(yīng)的點集。圖4中的前3個示例，其交點是符合公式(4)的假設(shè)。因此接受該交點，并且修改直線AB為AX，修改CD為XD。

很顯然，圖4（d）是不符合公式(4)的假設(shè)。對于這種情況，一種方法是將這條直線對應(yīng)的點集合并為一個點集，重新二分?jǐn)M合。但這樣可能出現(xiàn)相同的結(jié)果。因此在系統(tǒng)中采用簡單地處理，即根據(jù)對應(yīng)的點集，求其綜合的斜率和截距。

假定兩條直線分別為li,lj，|Ψi|表示直線li對應(yīng)的點集個數(shù)，|Ψj|表示直線lj對應(yīng)

區(qū)段內(nèi)的直線都按照上述的方法，順次連接形成區(qū)段直線。如圖3中的（d）。這樣，每個區(qū)段就形成由一條至多條折線，首尾相連，表示一個區(qū)段。

2.3.2 區(qū)段間相連

1）同一軌道區(qū)段的線段處理。

同一軌道區(qū)段是指共享一個軌道電路的道岔區(qū)，如圖5所示。一個大區(qū)段包含許多子區(qū)段，這些子區(qū)段有些重疊，這些子區(qū)段都會互相交叉。如圖1的AB和AC。合并區(qū)段內(nèi)的子區(qū)段時，需要用到一些先驗知識，比如道岔的型號、開口角度、大小等。以及站場上的平行線路至少相距5 m等。將重合的部分合成一條直線。合并子段的過程大致如圖5所示，根據(jù)前面的二分得到兩個子段，ABC和DEF。合并步驟如下。

* 合并重疊的直線。將比較靠近，并且近似平行的直線合成一條直線。合并的方法參見公式(9)和(10)。

* 重新計算子段內(nèi)各個折線的交點。由于AB和DE合成了線段M N，則以前和A B和CD相交的線段BC和EF需要重新計算和新的線段M N的交點。如圖5所示，他們的交點R和T。

* 根據(jù)道岔的先驗知識，R和T肯定是一個點。合并兩個點成S，本文就取R和T的中值。

* 合成最終的道岔形狀如圖5(d)所示。

2）不同軌道區(qū)段的線段處理

區(qū)段間的線段相互關(guān)系如圖6所示，大約有4種關(guān)系。

在連接不同段時，需要使用段關(guān)系表，段關(guān)系表是描述子段前后關(guān)系的表，可以從段關(guān)系表中獲取那些段需要連接。在連接兩個段時，采用移動端點的方法，不再改變直線另外一個端點。

3）后處理

后處理主要是平滑和削除過多的交點。根據(jù)道岔的型號和形狀，做一些局部的校正。

4）定位絕緣節(jié)。

定位絕緣節(jié)是站場圖形擬合的關(guān)鍵一步，機車在行駛的過程中，不斷接受GPS坐標(biāo)和軌道電路信息，當(dāng)軌道電路信息發(fā)生變化的GPS點就是絕緣節(jié)的位置。定位絕緣節(jié)時，需要考慮到機車運行方向，機車速度，軌道電路接收，GPS接收等延遲量。絕緣點的計算主要是采用移動平均的方法，根據(jù)很多離散點，計算一個最佳點。不在本文討論范圍。

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

3 實踐和結(jié)論

車站地形測繪目前還停留在手工階段，自動測繪還是剛剛出現(xiàn)的一個暫新領(lǐng)域。機車安裝GPS接收設(shè)備為車站自動測繪提供了可能性。

3.1 實踐

本文就是在機車走行過程中接受到的GPS點為基礎(chǔ)自動生成車站地形圖。下面系統(tǒng)圖就是根據(jù)點擬合的區(qū)段。

圖7是根據(jù)GPS點擬合的武漢北站局部地形圖。

3.2 結(jié)論

自動生成的站形圖沒有一個好的評價標(biāo)準(zhǔn)，特別是對于一個新站，但對于舊站，可以通過和人工測繪的站形圖比較來評價自動生成的站形圖。

和傳統(tǒng)方法相比較，自動生成站形圖有以下優(yōu)勢。

1）獲取站形圖的成本小

根據(jù)機車走形軌跡自動生成站形圖和傳統(tǒng)的人工測量相比，成本很小。

2）可以高效、準(zhǔn)確、遞進逼近站場真實地形

隨著使用的深入，GPS點的增加，站形遞進逼近真實地形。

3）快速、方便。

由于車站經(jīng)常會改造，施工等，可以靈活快速地生成站場地形圖滿足實際需要。

3.3 運用與展望

本文所述方法需要攜帶GPS接收設(shè)備的交通工具，因此本文所述的方法不僅可以應(yīng)用于鐵路軌道的自動測繪，也可以應(yīng)用于公路、水路、航空等交通路線的自動測繪。

隨著新技術(shù)的發(fā)展，站形的測量也從傳統(tǒng)的人工測量走向多元化，除了本文所述的根據(jù)走形軌跡，采用統(tǒng)計的方法自動生成外，也可以根據(jù)航拍圖片或者衛(wèi)星圖片，通過圖像識別的方式自動生成站形圖。

[1] 盛驟，謝式千，潘承毅.概率論與數(shù)理統(tǒng)計[M].4版.北京：高等教育出版社，2003.

[2] 威廉·D.貝里.線性回歸分析基礎(chǔ)[M].上海：上海人民出版社，2011.

[3] 王萼芳.線性代數(shù)[M].北京：清華大學(xué)出版社，2007.