基於圖像邊緣檢測信號相關性的室內wlan信號地圖繪製與映射方法

2023-07-24 16:34:36

基於圖像邊緣檢測信號相關性的室內wlan信號地圖繪製與映射方法
【專利摘要】本發明涉及一種基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與映射方法，該方法首先利用隨機用戶採集的接收信號強度RSS序列，通過譜聚類構建各RSS序列的聚類圖；其次，利用圖像邊緣檢測法，構建隨機用戶在定位目標區域內的信號邏輯圖；再者，根據相應的映射準則，建立信號邏輯圖中的RSS聚類節點到物理環境圖中的區域位置節點之間的映射；最終利用信號邏輯圖到物理環境圖的映射關係，實現對目標用戶的位置估計，同時利用繪圖技術對信號邏輯圖及物理環境圖進行繪製，提高了圖的可讀性，使得信號邏輯圖及物理環境圖中各節點的連接關係更加明晰。
【專利說明】基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製 與映射方法

【技術領域】
[0001] 本發明涉及一種信號地圖繪製與映射方法，特別涉及一種基於圖像邊緣檢測信號 相關性的室內WLAN信號地圖繪製與映射方法。

【背景技術】
[0002] 隨著無線區域網的廣泛部署，利用WLAN(Wireless Local Area Network)基礎設 施進行定位可以大大降低定位設施和系統維護的投入。目前，基於接收信號強度的室內 WLAN定位技術受到了廣泛的研究，其中典型的基於RSS(Received Signal Strength)位置 指紋的定位系統有微軟研究院開發的RADAR系統和馬裡蘭大學提出的Horus系統。RADAR 系統在2000年由微軟公司首次提出，其基本思想是在離線階段從目標區域內選定一定數 目的參考點，並在每個參考點處測量來自不同接入點AP(A CCesS Point)的信號強度值，建 立位置指紋資料庫；而在在線階段，則利用歐式距離最小準則，將終端實時測量得到的信號 值與位置指紋資料庫中已保存的信號數據進行匹配，找到與終端實時測量信號值的RSS歐 氏距離較小的若干個位置指紋，並利用這若干個位置指紋所對應的位置坐標，對終端進行 位置估計。RADAR定位系統所採用的定位算法簡單且易於實現，但定位精度不高，其最大定 位誤差超過20m。Horus系統沿用了位置指紋的思想，同時又對RADAR定位系統進行了改進， 提出了基於位置指紋的概率定位算法，以及利用最強AP信號聚類等優化措施，使得系統的 定位性能得到了很大程度的提高，其最大定位誤差在5m以內。
[0003] 位置指紋定位算法需要在離線階段對所有參考點處的來自不同AP的信號強度進 行採集，從而消耗了大量的人力和物力資源，並且當參考點數目較多時，離線階段所需的人 力和時間開銷會大大增加，為此，基於SLAM (Simultaneous Localization and Mapping) 的WLAN定位系統應運而生，這類系統利用了其他方式獲得的傳感器信息，如微機電系統 MEMS (Micro Electronic Machine System)中的慣性測量單兀 IMU (Inertial Measurement Unit)等，將用戶當前接收的WLAN信號強度與傳感器採集的信息相結合，從而在不需要大 量位置指紋信息採集的情況下，實現對終端的位置估計。
[0004] 由於位置指紋定位算法在離線階段需要對每個參考點處來自不同AP的信號強度 進行採集，因此，在系統設計前期需要投入大量的人力與時間開銷，以完成位置指紋資料庫 的構建。同時，基於SLAM的WLAN定位算法需要利用傳感器採集的信息，所以對終端設備有 特殊的要求，並且在大多數基於位置的服務LBS (Location-based Service)中，我們無需計 算目標的精確物理位置坐標，而僅需獲知目標所在的大致區域及其周邊物理環境信息。針 對這一目標，本發明提出一種基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與 映射方法。


【發明內容】

[0005] 有鑑於此，本發明的目的在於提供一種基於圖像邊緣檢測信號相關性的室內WLAN 信號地圖繪製與映射方法，該方法首先利用隨機用戶採集的信號強度序列，通過聚類及圖 像邊緣檢測方法，構建用戶在定位目標區域內的信號邏輯圖；其次，根據相應的映射準則， 建立信號邏輯圖中的RSS聚類節點到物理環境圖中的區域位置節點之間的映射；最終， 利用最優信號邏輯圖到物理環境圖的映射關係，實現對終端的位置估計，同時利用繪圖 (Graph Drawing)技術，對信號邏輯圖及物理環境圖進行繪製，提高圖的可讀性，使得信號 邏輯圖及物理環境圖中各節點的連接關係更加明晰。
[0006] 為達到上述目的，本發明提供如下技術方案：
[0007] -種基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與映射方法，該方 法包括以下步驟：
[0008] 步驟一：用戶在定位目標區域內隨機採集若干條WLAN接收信號強度序列為

【權利要求】
1.基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與映射方法，其特徵在於： 該方法包括以下步驟： 步驟一：用戶在定位目標區域內隨機採集若干條WLAN接收信號強度序列為 & ={RSS;I，…，RSS,W = …，z)，其中，Mj為第j條序列的序列長度，z為序列條數； RSSjk=(RSSjkl，…，RSSjkn)(k= 1，…，Mj)為第j條序列中第k個接收信號強度矢量；η為AP個數；RSSjfe(r= 1，…，η)為第j條序列第k個接收信號強度矢量中第r個AP的信號強 度值； 步驟二：根據時間戳順序對1中接收信號強度矢量進行升序排列；將第j條序列中第k個接收信號強度矢量重構為新的n+1維矢量φ7? =化，RSSyil,…，RSSyto；); 步驟三：對中所包含的時間戳信息和接收信號強度信息進行加權，得到混合矢量φ;.Α- =(%/，MmRSSfil,…，WraiRSSiJ,其中加權係數為 &和 Wrss，Wts+Wrss= !; 步驟四：對混合矢量進行譜聚類，得到Sj中每條混合矢量的聚類號； 步驟五：通過中值濾波方法，修正每條混合矢量的聚類號及相應類心； 步驟六：根據I中相鄰聚類之間的轉移關係，以連接圖的形式得到\的類轉移圖； 步驟七：重複步驟2)至步驟6)，得到所有接收信號強度序列的類轉移圖； 步驟八：通過圖像邊緣檢測技術，確定所有類轉移圖中類間距離小於門限Std的類，合 並相應的類，對所有離散的類轉移圖進行拼接，得到待篩選的信號邏輯圖； 步驟九：將定位目標區域內的每個物理叉路口作為區域邊界進行子區域劃分，並對每 個子區域進行序號標記；記區域標號為1，…，A，其中A表示所有的子區域的個數； 步驟十：根據各子區域的物理鄰接關係，將定位目標區域表示為一副由各子區域連通 的物理環境圖； 步驟十一：在定位目標區域內選擇少量標記位置點CP，且保證標記位置點的個數少於 子區域個數； 步驟十二：在各標記位置點處採集NR個來自不同AP的信號強度矢量，並將其均值矢量 作為各標記位置點的代表矢量RV; 步驟十三：在每個邏輯圖中，計算與RV中每個元素Mrssn。與邏輯圖中各類心的歐式距 離=||Mrasee -Il;其中，,表示MrsSn。與第Zj個邏輯圖中的第f3個類心之間的 歐氏距離，為第zj個邏輯圖中的第&個類心；選擇與Mrssn。歐式距離最小的類心所對 應的邏輯節點為該RV中元素Mrssne所對應子區域cpn。存在的映射關係，剔除包含與2個或 以上不同子區域存在映射關係的邏輯節點所對應的信號邏輯圖； 步驟十四：根據步驟十三得到所有未剔除信號邏輯圖，利用映射準則，得到所有未剔除 的信號邏輯圖，以及相應的與物理環境圖的映射關係； 步驟十五：選擇對於所有標記點具有最高平均定位精度的信號邏輯圖作為最優信號邏 輯圖；其中，每個標記點的定位精度定義為：在該標記點上採集的正確映射到所屬子區域 的信號強度矢量個數與信號強度矢量總數的比值，P?4 其中，Pio^表示第X個邏 NR 輯圖的映射關係中第nc個標記點上的定位精度，為第nc個標記點上採集的NR個接收 信號強度矢量中能夠映射到cpn。的接收信號強度矢量的個數；所有標記點的平均定位精度 Pr〇L,">ΡΓ0-?=^Σ,".-,ΡΓ0?.: 步驟十六：根據步驟十五，選擇F〇_,,最大的邏輯圖作為最優信號邏輯圖， 根據步驟十四所確定的映射準則，得到最優信號邏輯圖到物理環境圖的映射關係 Map=(?>ie{l, U，…，NocT}) ;Map=表示第cet個邏輯圖，NocT表示第cet 個邏輯圖中的邏輯節點個數； 步驟十七：利用GraphDrawing正交算法，對最優信號邏輯圖及物理環境圖進行繪製； 步驟十八：根據終端新採集的信號強度矢量，在最優信號邏輯圖中，計算得到與新採集 信號強度矢量具有最小歐式距離的邏輯節點； 步驟十九：根據最優信號邏輯圖到物理環境圖的映射關係，估計終端所在的子區域。
2.根據權利要求1所述的基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與 映射方法，其特徵在於：所述步驟四包括以下步驟： 1) 對於I，構建鄰接矩陣Mwa，如下式：
其中，wPAS」中'(/? = 1,…，竭與〇 = 1,…，M)的相似度，= e-， 卜11表示二範數計算； 2) 在Mwa中設定相似度門限thw，當wM〈thw0^，令wM=O;當thw0^，wM保持不 變； 3) 將Mwa中的每一列求和，得到《二?G= 1,…，M)，構造MXM的對角矩陣Dm，如 下所示：
4) 通過以下公式計算拉普拉斯算子L: L=Dm-Mwa; 5) 通過以下公式計算L的特徵值及特徵向量， LV=vV； (vE-L)V= 0 ；det(vE-L) = 0 ； 其中，E為MXM的單位矩陣；veR為L的特徵值；V表示L的特徵向量，長度為M的列 向量； 6)將凡中的每一行定義為一個混合矢量的重構矢量，從而得到M個重構矢量Nd= (1^(11，...，1^)，其中，1^("江=1，...，。）為凡中第(1行的第€個元素，將釐個重構矢量進行 K均值聚類。
3. 根據權利要求2所述的基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與 映射方法，其特徵在於：所述步驟6)將M個重構矢量進行K均值聚類包括以下步驟： (1) 確定所需聚類的K均值聚類個數K(K〈〈M);隨機在M個重構矢量中選取K個樣本Sab =(sabl,sab2, · · ·，sabc)(b= 1，…，K)作為初始類心，其中私 ;sabf(f= 1，…，c) 為Sab中第f個元素； (2) 逐個計算剩餘的M-K個樣本與所有初始類心的歐式距離，並將樣本分配到與其歐 氏距離最小的初始類心所對應的聚類中；其中M-K個樣本中的每個樣本與每個初始類心的 歐氏距離計算為 ,.^l-sahl )2 (Sah^Nil); (3) 通過以下公式重新計算K個聚類的聚類中心，並將新的K個聚類的聚類中心作為初 始類心，
其中，Cb表示第b個聚類的所有樣本；X表示Cb中的每個樣本；Nub表示Cb的樣本個數；Zb表示第b個聚類的新類心； (4) 通過以下公式計算出所有聚類類心偏離度J，
(5) 重複步驟（2)步至步驟（4)，直到J達到最小值，Sab(b= 1，…，K)為各聚類類心； 將g||Z-Z6If 從小到大排序，得到各類的類號，同類中的樣本的類號相同。
4. 根據權利要求1所述的基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與 映射方法，其特徵在於：所述步驟八包括以下步驟： 1) 將採集到的RSS序列排列為
2) 分別計算Γ中不同接收信號強度矢量的歐式距離，進而得到距離矩陣Mdis,
其中，Mr為序列Γ中的接收信號強度矢量數目；?,，犯， 也>7(?丨，2,…，Μ)為Γ中第Cli1個接收信號強度矢量與第di2個接收信號強度矢 量的歐氏距離；1與別表示r中第Cli1與第虹2個接收信號強度矢量中來自第 虹3個AP的信號強度值； 3) 設定門限std，當也響 < ?時，令也響=1;當炎ν,:乏?時，令炎/響=〇 ; 4) 對矩陣Mdis進行中值濾波處理，包括以下步驟： (1) 選擇大小為3X3的窗口win作為中值濾波的基本單元，如下所示，
其中，win中共有9個元素，Winwinl(winl= 1，2,…，9)為win中的第winl個元素； (2) 將矩陣Mdis做補O處理得到Mdisn，如下所示，
(3)將win中的Win5對芥Mdis_n中的元累Mdis_n(dis_nl, dis_n2),其中dis_nl= 2, 3,· · ·，Mr+1,dis_n2 = 2, 3,· · ·，Mr+1,Mdisn(dis_nl, dis_n2)為Mdisn中第dis_nl行第 dis_n2列的元素； (4) 取出當前win對應於Mdisn*的元素，將所有元素按從大到小排列並依次標號為1， 2，···，9,且將矩陣Mdis中第（dis_nl)-l行第（dis_n2)-l列的元素更新為標號為5的元素； 5) 對矩陣Mdis進行腐蝕處理，包括以下步驟： (1) 選擇大小為5X5的窗口ero,如下所示，
(2) 將ero中第三行第三列的元素依次對齊Mdis中的元素Mdis(dis_l，dis_2)，其中 dis_l= 3, 4, · · ·，Mr-2,dis_2 = 3, 4, · · ·，Mr-2,Mdis(dis_l,dis_2)為Mdis中第dis_l行 第dis_2列的元素； (3) 當對齊於ero的所有Mdis中元素全為1時，令Mdis(dis_l，dis_2) = 1，而當對齊於 ero的所有Mdis中元素不全為1時,令Mdis(dis_l,dis_2) = 0 ; 6) 對矩陣Mdis進行邊緣檢測處理，包括以下步驟： (1)選擇大小為3X3的邊緣檢測窗口edg，如下所示：
(2) 將edg中的元素edgji齊矩陣Mdis中的元素Mdis(dis_a，dis_b)，其中dis_a= 2, 3, · · ·，ΜΓ_1，dis_b= 2, 3, · · ·，Mr_l，Mdis (dis_a，dis_b)為Mdis中第dis_a行第dis_b列 的元素； '+I +2 +1 (3) 選定橫向及縱向邊緣檢測的Sobel卷積因子^及67，其中Gr=OOO , -I -2 -I
(4) 將對齊於edg的Mdis中元素分別與G,及Gy相乘，得到關於當前元素Mdis (dis_a，dis_ b)在橫向及縱向上的灰度差分值Gxdisa及Gydisb，其中， Gx-diS-a=Mdis((dis_a)+l，（dis_b)+l)+2Mdis((dis_a)，（dis_b)+l) +Mdis((dis_a)_l，（dis_b)+l)-[Mdis((dis_a)+l，（dis_b)_l) +2Mdis((dis_a), (dis_b)-l)+Mdis((dis_a)_l，（dis_b)_l)] Gy_dis_b=MdiS((dis_a)+l, (dis_b)+1)+2Mdis((dis_a)+1, (dis_b))； +Mdis((dis_a)+1, (dis_b)-l)-[Mdis((dis_a)-l, (dis_b)+l) +2Mdis((dis_a)-l, (dis_b))+Mdis((dis_a)-l, (dis_b)_l)] (5) 得到關於當前元素Mdis(dis_a，dis_b)的灰度差分值Gxy，Gxy=IGxdisaI+ |Gy_disbI; (6) 設定灰度差分門限Gth，當Gxy彡Gth時，令Mdis(dis_a，dis_b) = 1，當Gxy〈Gtl#，令 Mdis(dis_a，dis_b) = 0 ; 7) 對矩陣Mdis的邊緣信息進行提取，得到序列Γ中不同接收信號強度矢量距離小於Std 的序列塊的長寬，以及其在Γ中的位置信息； 8) 根據步驟7)中得到的C〇 4，將離散的信號邏輯圖進行拼接。
5.根據權利要求4所述的基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與 映射方法，其特徵在於：所述步驟7)包括以下步驟： (1) 設定空矩陣CO1; (2) 遍歷矩陣Mdis中的所有元素Mdis(dis_c,dis_d),其中dis_c= 1，2,…，Mr,dis_ d= 1，2,…，Mr，Mdis(dis_c,dis_d)表示矩陣Mdis中第dis_c行第dis_d列的元素；當 Mdis(dis_c,dis_d) = 1 時，將坐標（dis_c,dis_d)記錄於COj中； ⑶設定空矩陣co_2,。〇_3及CO_4; (4) 令遍歷號vinu= 1 ; (5) 若vinu>vile則步驟結束，其中，vile為coj中坐標個數，若vinuc〇i(vinu，2)Jl^Sco-1-(vinu；^W'^i^*#nef1，nef2，nef3，n ef4, Iiee1, nee2, nee3, nee4，其中，八鄰域中的四鄰域坐標Iief1, nef2, nef3, nef4及八鄰域中的 對角坐標Iiee1, nee2, nee3, nee4為：
(10)確定坐標Iief1, nef2, nef3,!^:^在co」中的個數，若nef p nef2, nef3, nef4* 有fo(fo = 0, I, 2, 3, 4)個坐標存在於co」1=!11,貝U令四鄰域標記量n f。= fo;確定坐標 Iiee1, nee2, nee3, nee4在co衝的個數，若nee nee2, nee3, nee4中有ei (ei = 0, I, 2, 3, 4)個 坐標存在於⑶^中，則令對角標記量n ei= ei ; (11)若prnu= 1，則令prnu= prnu+l並轉步驟（12);若prnu# 1，則轉步驟（13); (12) 若％。關0,則將步驟（10)中的nf。個坐標中的任意一個設為當前坐標c〇i(vinu)， 將剩餘的％。-1個四鄰域坐標及Iieii個對角坐標存入co_3並返回步驟（5);若nf。= 0,則將 步驟（10)中的Iieii個坐標的任意一個設為當前坐標coi(vinu),將剩餘的Iieii-I個對角坐標 存入C〇 3並返回步驟（5); (13)若化。關0,則將步驟（10)中的n f。個坐標與co 2中的坐標進行比較，若nf。個坐 標不全包含於c〇_2，則將不包含於c〇_2中的任意一個坐標設為當前坐標co I(Vinu)，將剩餘 的不包含於c〇2中的四鄰域坐標及不包含於co 2中的對角坐標存入co 2並返回步驟（5); 若％。個坐標全部包含於co 2，則將步驟（10)中的知個坐標與co 2中的坐標進行比較，若 坐標不全包含於c〇_2，則將不包含於c〇_2中的任意一個坐標設為當前坐標co I(Vinu)，將剩 餘的不包含於co_2中的對角坐標存入CO_2並返回步驟（5);若步驟（10)中的rid個坐標全 部包含於co 2，則將co 2中的坐標與co 3中的坐標進行比較，如果CO 2與co3中有相同的坐 標，則取co 2中所有橫縱坐標中的最大值和最小值存入co 4中，其中，存儲的橫縱坐標的最 大值和最小值的形式為（Xniin, X_，Yniin, y_)，其中（Xniin, X111J及Gniin, y_)分別為CO2中橫 縱坐標的最大值和最小值，令Vinu= vi nu+l，返回步驟（5);如果CO 2與CO3中沒有相同的 坐標，令vinu= vinu+l，返回步驟（5);若nf。= 0,則轉步驟（14); (14)若nf。= 0,則步驟（10)中的n ei個坐標與co _2所包含的坐標進行比較,若坐標 不全部包含於c〇_2，則將不包含於c〇_2中的任意一個坐標設為當前坐標co I(Vinu)，將剩餘 的不包含於co 2中的對角坐標存入co 2並返回步驟（5);若坐標全部包含於co 2，則將co 2 中的坐標與co 3中的坐標進行比較，如果CO 2與co 3中有相同的坐標，取co2中所有橫縱 坐標中的最大值和最小值存入co 4中，其中存儲的橫縱坐標的最大值和最小值的形式為 (Xmin，XmaX，ymin，ymaX)，其中，（XmtoXmax)及（ymin，ymJ分別為中橫縱坐標的最大值和最小 值，令Vinu=vinu+l，返回步驟（5);如果。〇_2與co_3中沒有相同的坐標，令vinu=vinu+l， 返回步驟（5)。
6. 根據權利要求1所述的基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與 映射方法，其特徵在於：所述步驟十四中每一個信號邏輯圖到物理環境圖的映射準則具體 步驟為： 1) 計算物理環境圖中各子區域的鄰接度AD，各子區域的AD定義為該子區域和其鄰 接子區域所鄰接的子區域個數總和，一個子區域與另一個子區域鄰接表示這兩個區域能夠 不經過其他區域到達彼區，此外，在所有子區域的AD中，得到最大得到最大ADAmag和最小 ADAmig; 2) 對於第X(X=l，一，y)個未剔除信號邏輯圖Gx，其中，y為未剔除信號邏輯圖個數， 計算&中除標記點所在子區域IcpnJ對應的邏輯節點外的邏輯節點的AD，各邏輯節點的AD 定義為該邏輯節點和其鄰接邏輯節點所鄰接的邏輯節點個數總和，一個邏輯節點與另一個 邏輯節點鄰接表示這兩個邏輯節點能夠不經過其他邏輯節點到達彼節點； 3) 計算得到&中的最大ADAmal和最小ADAmil，對於除標記點所在子區域IcpnJ對應的 邏輯節點外的邏輯節點的ADVad1，通過以下公式將其修正為Vads,
4) 選擇物理環境圖中與Vads距離最小的AD所對應的子區域，作為該邏輯節點的初始映 射子區域，即此邏輯節點與該子區域具有初始映射關係，此處距離定義為二者之差的絕對 值；用MarC(/""=l，…，Λω')表示第X個未剔除信號邏輯圖中的第ma個邏輯節點所對應 的映射子區域，Nodx表示第X個未剔除信號邏輯圖的節點數；標記點所在子區域{cpn。}對 應的邏輯節點的映射子區域即為相應的標記點子區域； 5) 重複步驟2)至步驟4)，可得所有未剔除信號邏輯圖與物理環境圖的初始映射關係， 利用中心點對上述得到的初始映射關係進行校正，得到最終的映射關係。
7. 根據權利要求1所述的基於圖像邊緣檢測信號相關性的室內WLAN信號地圖繪製與 映射方法，其特徵在於：所述步驟十七包括以下步驟： 1) 初始圖G= (V，E)，隨機選擇兩個點，一個點標記為s，另一個點標記為t，其中，V是 G中所有點的集合，表示為V={vej(i= 1，2,. . .，nve) ;E是G中所有邊的集合，表示為E ={edj}(j= 1，2, · · ·，ned) !Vei表示G中的第i個的點，ed』表示G中的第j條邊，nve及ned 分別表示G中點及邊的數目； 2) 找出包含s的所有邊及所有邊包含的點，以s為源點，以其餘所有邊包含的點為終點 作有向邊，並在所有邊包含的點中，選擇所有不為t的終點為新的起點； 3) 對於每一個新的起點，找出包含該點的所有邊及所有邊包含的點，以該新的起點為 源點，以其餘所有邊包含的點為終點作有向邊，當某條有向邊的兩個點都為新的起點時，規 定該邊的繪製方向為從左往右或從上到下； 4) 重複步驟3)，直到對所有新的起點都進行了從該點到相應終點的有向邊的繪製，然 後令步驟3)中的所有不為t的終點為新的起點； 5) 重複步驟3)至步驟4)，直到遍歷完G中所有的點，從而構成了有向圖G' ； 6) 在圖G'中將點s的值賦為O;並令其為起點； 7) 令初始賦值i_=O;賦值間隔iit= 1 ; 8) 從起點開始，對圖G'中的每條有向邊的所關聯的兩個點賦值，所滿足的條件為該邊 的終點的賦值大於起點的賦值，具體賦值規則為： (1) 確定包含起點的所有邊，再找到所有邊所對應的終點； (2) 將去掉點t的所有終點構成終點集，將所有終點賦值為inum+iit; (3) 若終點集中存在連接兩個終點的有向邊，則將該邊所對應的終點的值賦為起點值 加1，並將步驟2)所確定的所有終點令為新的起點； (4) 重複步驟（1)至步驟（3)，直到遍歷完除t點以外的所有點； (5) 確定與點t相鄰的點，並將所有與點t相鄰的點的賦值中的最大值加1賦給點t， 此時，圖G'中每個點的賦值為該點在圖中的縱坐標； 9) 構建另一有向圖Dn，具體步驟為： 確定有向圖三部分點集；第一部分點集為圖G'中的邊所構成的所有最小區域， 其中，最小區域定義為圖G'中不存在其它邊再把該區域進行分割的區域；第二部分點集為 圖G'以外空間所形成的兩個區域，這兩個區域滿足：區域的併集為圖G'以外的所有空間， 而交集為空，此外，點s及t在兩個區域的邊界上，且定義兩個區域中的左邊區域為s*，該區 域的邊界包含三段：第一段為連接s到t的最左邊的無向路徑Π'，其中，最左邊的無向路 徑為不存另一條連接s到t的無向路徑Π使得Π在Π'的左邊或者Π中的某條無向邊 在Π'的某條無向邊的左邊；第二段為連接s及s'的無向邊Π"，其中，s'為包含於圖G' 以外空間的某一點，Π"包含於圖G'以外空間且s'與s的距離趨於無窮；第三段為連接t 及t'的無向邊Π" '，其中，t'為包含於圖G'以外空間的某一點，Π" '包含於圖G'以 外空間且t'與t的距離趨於無窮，同時，定義兩個區域中的右邊區域為為t* ;第三部分點 集為圖G'中路徑所構成的點集，路徑的確定步驟為： (1) 確定圖G'中所有非s及t點的所有點，構成處理點集； (2) 遍歷處理點集中的所有點，對於每一個點，當入邊數為奇數時，規定其入邊為所有 入邊的最中間一條邊，而當入邊數為偶數時，規定其入邊為所有入邊的最中間兩條邊中偏 左的一條邊；其中，一個點的入邊為以該點為終點的所有邊，對於每一個點，當出邊數為奇 數時，規定其出邊為所有出邊的最中間一條邊，而當出邊數為偶數時，規定其出邊為所有入 邊的最中間兩條邊中偏右的一條邊，其中，一個點的出邊為以該點為起點的所有邊； (3) 連接所有點所確定的邊，構成所有確定的路徑，並將圖G'中剩餘的邊作為單獨的 路徑，所有的路徑就構成了第三部分點集； 10) 確定有向圖Dn的有向邊集，具體為： (1) 對於圖Dn的點集中的每一個代表區域的點，在圖G'中遍歷由步驟9)所確定的所 有tnu條路徑，對於圖G'中第tnul (tnul= 1，2,. ..，tJ條路徑IItnul，若其所包含的某一條 邊包含於該區域代表點在圖G'中對應區域的邊界，則在有向圖Dn*，以該區域代表點為起 點，以所代表的點為終點作有向邊； (2) 對於圖Dn的點集中的每一個代表路徑的點，在圖G'中遍歷由步驟9)所確定的所 有anu個區域，對於圖G'中第anul(anul=1，2, . . .，anu)個區域4"",，若其邊界包含該路徑代 表點在圖G'中對應路徑的某一條邊，則在有向圖Dn*，以該路徑代表點為起點，以所代 表的點為終點作有向邊； 11)在圖Dn*，將點s*的值賦為-0. 5;並令其為起點； 12)令初始賦值inum= -0. 5;賦值間隔iit=0. 5; 13)執行步驟8)，其中，在步驟8)中所有對t的操作修改為對t*的操作，且對圖Dn中 所有點的賦值修改為圖G'中所有邊的橫坐標； 14)遍歷圖G'中的所有點，對於每一個點，其縱坐標為此點的賦值，橫坐標有兩個，分 別為包含該點的路徑在有向圖Dn中賦值的最大值與最小值，連接該兩個點，即得關於該點 的坐標表示線； 15)遍歷圖G'中的所有邊，對於每一條邊，其橫坐標為此邊所在路徑在有向圖Dn中的 賦值，縱坐標有兩個，分別為該邊在有向圖G'中的起點和終點的賦值，連接該兩個點，即得 關於該邊的坐標表示線； 16)在得到G'中所有點和所有邊的坐標表示線後,在所有點的坐標表示線上畫出一個 實點，且實點的位置規則為：對於每一條坐標表示線，實點的位置在與此點的坐標表示線相 交的邊的坐標表示線的交點上。
【文檔編號】G06T11/00GK104463929SQ201410783008
【公開日】2015年3月25日 申請日期:2014年12月16日 優先權日:2014年12月16日
【發明者】周牧, 張巧, 田增山, 邱楓, 範馨月, 周祥東, 蔣青, 周翊 申請人:重慶郵電大學