基於空間拓撲關係的新型標誌區域校驗方法
2023-09-10 10:56:00
基於空間拓撲關係的新型標誌區域校驗方法
【專利摘要】本發明是一種基於空間拓撲關係的新型標誌區域校驗方法，解決在室內大型三維仿真射擊指向遊戲中，在紅外識別技術對於指向的目標不準確甚至是錯誤的情況下，根據標誌點的排布的空間關係，判斷出所指向的標誌點區域是否為完好的。由於攝像頭所拍攝到的區域是整個屏幕的一部分，而且因為是大規模多人遊戲，很有可能因阻擋而造成標誌點部分區域的不完整性，得出不正確的區域中心坐標，從而得出錯誤的區域指向定位坐標。為了解決前面的紅外燈識別可能造成的不正確的區域中心坐標以及區域標誌點數量，要應用本技術對區域檢測結果進行錯誤排除，保留正確區域，放棄錯誤區域，從而能夠大幅度提高射擊指向定位準確性。
【專利說明】基於空間拓撲關係的新型標誌區域校驗方法
[0001]【【技術領域】】
本發明應用於仿真射擊遊戲產業的指向定位校驗系統，涉及一種基於空間拓撲關係的新型標誌區域校驗算法。
[0002]【【背景技術】】
隨著大型遊戲產業的發展，人們越來越追求室內遊戲的三維逼真效果。在仿真射擊遊戲方面，遊戲者對畫面的實時效果要求較高，需要開發出比較實時和精確的指向定位技術。本校驗算法應用於大規模的指向定位系統，對指向定位的結果進行校驗和糾正，以便於完成對指向區域更加精確更加快速地定位。本發明採用了一種類似於計算機網絡的路由表算法，將紅外燈標誌點排布於劃分好的各個區域，以標誌點的數量作為區域的編碼。每個區域作為中心區域，即路由表的表頭，區域的鄰域按照空間順時針排列作為子網拓撲。本算法通過讀取中心區域，及其所對應的鄰域的空間統計關係，來進行空間標誌點區域校驗。
[0003]本發明要解決的技術問題以及目的在於:本發明的目的在於提供一種能夠大幅度提高射擊指向定位準確性的新型標誌區域校驗的方法，解決在室內大型三維仿真射擊指向遊戲中，在紅外識別技術對於指向的目標不準確甚至是錯誤的情況下，根據標誌點的排布的空間關係，判斷出所指向的標誌點區域是否為完好的。由於攝像頭所拍攝到的區域是整個屏幕的一部分，而且因為是大規模多人遊戲，很有可能因阻擋而造成標誌點部分區域的不完整性，得出不正確的區域中心坐標，從而得出錯誤的區域指向定位坐標。為了解決前面的紅外燈識別可能造成的不正確的區域中心坐標以及區域標誌點數量，要應用本技術對區域檢測結果進行錯誤排除，保留正確區域，放棄錯誤區域。
[0004]本發明解決其技術問題所採用的技術方案是:
將需要定位的大屏幕按照等距離等面積的方式劃分為多個區域，在每一個區域內排布不同數量的標誌點。區域間的最小距離大於區域內標誌點之間距離最大值的2倍，避免在圖像畸變情況下區域識別出現錯誤，即將不是同一個區域的紅外標誌點劃分為同一個區域。區域的個數最為η個(η ≥3)，具體的區域個數根據屏幕大小來設計。每個區域內標誌點的個數表徵了區域的屬性，即若某區域內有5個標誌點，那麼我們稱這個區域為5號區域，以此來表徵與其他區域的不同；
每個區域都有相對應的鄰域，按照各個區域的相鄰與否劃分出每個區域的鄰域。當選定鄰域半徑時，距離待 判定區域近於鄰域半徑的區域都是鄰域區域。由於待判定區域與鄰域之間的關係具有旋轉不變性，包括待判定區域與鄰域的標誌點個數關係以及鄰域的角度關係。這種某特定區域與其鄰域間的空間拓撲關係可以用路由表的形式表徵出來。為了路由表的唯一性，我們將鄰域中標誌點最少的區域排在鄰域表的首位。為了便於理解，以下文中的圖1為例，屏幕上布置了 11個區域，固定鄰域半徑後，可以得到如圖2所示的路由表。當待判定的區域為I號區域時，其鄰域為2號區域和7號區域，且2號區域排在最前面。當待判定的區域為2號區域時，其鄰域按照順時針方向排列，且I號區域排在最前面，依次為I號區域、3號區域、8號區域和7號區域。可見，按照這種設計，待判定區域與其鄰域間可以通過路由表唯一確定。因此，由具有唯一性的路由表可以判定中心區域的對錯，保留正確的區域進行坐標計算；
將攝像頭所拍攝到的各個區域進行統計，算出所有區域的個數和每個區域的標誌點數
量;
求出上述各個區域之間的距離並排序得出區域間最小距離Dis_Reg_Min，設定區域間閾值為Threshold_Region = (1.3~1.9)* Dis_Reg_Min,區域間最小距離的倍數是根據整個大屏幕的的大小、區域的排布數量以及排布方式等具體實驗環境來進行確定；
根據區域間閾值ThresholcLRegion判斷每個區域的鄰域，如果滿足兩個區域之間的距離小於或者等於區域間閾值，則可以認為一個區域為另一個區域的鄰域，並求出每個區域的所有鄰域Neighbour_Region以及鄰域的個數nTotalNeighbour ；
對比路由表，查找並判斷一個區域的鄰域是否與路由表裡的相應鄰域對應，如果能夠找到路由表裡相對應的鄰域，則正確鄰域數加上I ;如果沒能找到，則錯誤的鄰域數加上1，並判斷每個區域的鄰域的正確率PercentCorrectNeighbour,以此為依據判斷此區域是否正確；正確率的計算方法為正確的鄰域的個數除以所有的鄰域的個數，如果一個區域的正確率大於0.5，則初步判斷此區域為正確區域，並將此區域保存下來，存為正確區域；然後算出正確區域的個數為ReserveRegion,正確區域的坐標為X_Region_Reserve, Y_Region_Reserve ;如果一個區域的正確率小於或者等於0.5,則初步判斷此區域為錯誤區域；
求出保留後各個區域之間的距離Dis_Reg_C0nfirm，然後再次求保留後各個區域的距離鄰域的閾值Threshold_Region_Confirm,先求出保留區域之間的最小距離Dis_Reg_Min，然後根據最小距離的1.3^1.9倍來求出保留區域距離的閾值；再對每個保留區域為中心求出鄰域 Neighbour_Region_Confirm ；
判斷鄰域的角度Reg_Angle,判斷方法如下:首先求出中心區域與鄰域的X軸和Y軸坐標差值Dist_x, Dist_y。然後根據Dist_x和Dist_y的正負判斷其角度Reg_Angle ；
將鄰域的角度按照由小到大排列，對比按照順時針排序的路由表，判斷保留區域的正誤，如果有任何一個鄰域不滿足角度關係，判斷該初步保留的中心區域是錯誤的，則排除這個區域是射擊的區域；如果所有鄰域滿足路由表所規定的角度順序，則繼續保留這個區域，並最終確定為是射擊的區域。
[0005]本發明是一種應用於大規模指向定位校驗系統的基於空間拓撲關係的新型標誌區域校驗算法，具有以下優點:
(1)在本發明的技術方案中，採用了區域化分型標誌點，將屏幕按照均面積和均距離的規律劃分為多個區域，區域之間具有鄰域的相互關係，將各個區域的鄰域計入路由表中，各個區域相互關聯形成固定的拓撲關係。
[0006](2)在本發明的技術方案中，由於相鄰區域的距離相等，每個區域都有不同的鄰域，這樣無論旋轉還是障礙物遮擋都不能改變區域的相對位置，使得該校驗方法抗幹擾能力(魯棒性)強，準確性高，從而能夠大幅度提高射擊指向定位準確性。
【專利附圖】
【附圖說明】
[0007]圖1是本發明實施例一的標誌點的排布示意圖(在屏幕上布設11個標誌點區域時)，其中每個格子方塊代表一個標誌點排布編碼區域，每個格子方塊中黑點代表排布的標誌點。這只是以上技術的一個實現案例，便於講述後面的【具體實施方式】；圖2是本發明實施例一的空間排布路由表；
圖3是本發明實施例二的標誌點的排布示意圖(在屏幕上布設8個標誌點區域)；
圖4是本發明實施例二的空間排布路由表；
圖5是本發明實施例三的標誌點的排布示意圖(在屏幕上布設22個標誌點區域)
圖6是本發明實施例三的空間排布路由表。
[0008]上述三個路由表，是區域排布對應其中每個區域的鄰域按照空間方位順時針排列的，其中第一列是待判定區域所具有的標誌點數量，即中心區域的編號，後面各列是鄰域所對應的編號。
【具體實施方式】
[0009]在實施例一中，一種基於空間拓撲關係的新型標誌區域校驗方法包括如下步驟:
1、劃分區域:如圖1所 示，將用於射擊的大屏幕按照等距離等面積的方式劃分成11個
區域，根據本發明要求，在每個區域內排布不同數量的標誌點，每個區域內標誌點的數量作為該區域的編號。標誌點的排布必須遵循下面的要求，即各個區域間的最小距離大於區域內標誌點之間距離最大值的2倍；
2、建立標誌點區域空間排布路由表:將每個區域作為中心區域，即路由表的表頭；將該區域的相鄰區域(下面簡稱為鄰域)按照空間順時針排列作為子網拓撲，然後將每個區域的鄰域按照空間方位順時針排列製成路由表，其中第一列是待判定區域所具有的標誌點數量，後面各列是各鄰域所對應的編號，如圖2所示，這是根據各個區域之間的空間相互關聯形成固定的拓撲關係；
3、將攝像頭所拍攝到的區域進行統計，這部分區域可能包括幾個完整的區域(及該區域的所有標誌點都能被拍到)或部分不完整的區域，算出所有區域的個數和每個區域的中心坐標及標誌點數量。區域中心坐標為數組X_Region, Y_Region (X_Region是X軸方向坐標,對應於水平方向；Y_Region是Y方向坐標,對應於豎直方向),每個區域的標誌點數量為nLabelRegion,得到的所有區域的個數為NumberAlIRegion。
[0010]4、首先求出各個區域之間的距離Dis_Reg，距離公式運用了數學上基本的兩點間距離公式。將區域距離排序得出區域間最小距離Dis_Reg_Min，設定區域間閾值為Threshold_Region =(1.3~1.9) * Dis_Reg_Min。即區域間閾值設定為區域間最小距離的的1.3^1.9倍，這個倍數不是固定的，他應該根據整個大屏幕的的大小、區域的排布數量以及排布方式等具體實驗環境來進行確定，這個倍數的範圍在1.3^1.9之間。
[0011]5、根據區域間閾值Threshold_Region判斷每個區域的鄰域。如果滿足兩個區域之間的距離小於或者等於區域間閾值，則可以認為一個區域為另一個區域的鄰域。按照這個公式求出每個區域的所有鄰域Neighbour_Region以及鄰域的個數nTotalNeighbour。
[0012]6、對比路由表TabRoute (如圖2所示),查找並判斷一個區域的鄰域是否與路由表裡的相應鄰域對應。如果能夠找到路由表裡相對應的鄰域，則正確鄰域數加上I ;如果沒能找到，則錯誤的鄰域數加上I。判斷每個區域的鄰域的正確率PercentCorrectNeighbour,以此為依據判斷此區域是否正確。正確率的計算方法為正確的鄰域的個數除以所有的鄰域的個數(正確區域與錯誤區域之和)。如果一個區域的正確率大於0.5，則初步判斷此區域為正確區域，並將此區域保存下來，存為正確區域。正確區域的個數為ReserveRegion，正確區域的坐標為X_Region_Reserve, Y_Region_Reserve。如果一個區域的正確率小於或者等於
0.5，則初步判斷此區域為錯誤區域。
[0013]7、求出保留後各個區域之間的距離Dis_Reg_C0nfirm，距離公式運用了數學上基本的兩點間距離公式。然後再次求保留後各個區域的距離鄰域的閾值Thresh0ld_Regi0n_Confirm,先求出保留區域之間的最小距離Dis_Reg_Min,然後根據1.3至1.9倍的最小距離求出保留區域距離的閾值。以每個保留區域為中心求出鄰域Neighbour_Region_Confirm。
[0014]8、判斷鄰域的角度Reg_Angle,判斷方法如下:首先求出中心區域與鄰域的X軸和Y軸坐標差值Dist_x,Dist_y。然後根據Dist_x和Dist_y的正負判斷其角度Reg_Angle。這個方法根據區間及其坐標的正負關係，準確的判斷出每個保留區域的鄰域的對應角度Reg—Angle。
[0015]9、將鄰域的角度按照由小到大排列。對比按照順時針排序的路由表，判斷保留區域的正誤。如果有任何一個鄰域不滿足角度關係，判斷該初步保留的中心區域是錯誤的，則排除這個區域。如果所有鄰域滿足路由表所規定的角度順序，則繼續保留這個區域。這個保留的區域就成為射擊的正確區域，從而完成區域的校驗。
[0016]其中，所述【具體實施方式】的步驟3到步驟6屬於通過路由表中的區域內標誌點數目關係對指向區域進行初次的判斷，可能會出現少許的錯判和誤判。
[0017]其中，所述【具體實施方式】的步驟7到步驟9是對前面初次判斷的結果利用角度排列順序進行再次的檢查和糾正。
[0018]由於先對比路由表，初次判斷某一區域的正確性；再次通過對比角度順時針排列路由表，對初次判斷的結果進行再次的檢查和糾正。無論角度的旋轉還是障礙物遮擋都不能改變區域的相對位置，通過這兩個環節的校驗，使得該校驗方法抗幹擾能力(魯棒性)強，準確性高，從而能夠大幅度提高射擊指向定位準確性。
[0019]在圖3、4所示的實施例二中，【具體實施方式】和實施例一基本一致，但由於其屏幕尺寸比實施例一的小，為此將屏幕分成8個標誌點區域；另外屏幕上各個標誌點區域的大小和標誌點區域之間的距離是基本一致的。
[0020]在圖5、6所不的實施例三中，【具體實施方式】也和實施例一基本一致,但由於其屏幕尺寸比實施例一的大，為此將屏幕分割成22個標誌點區域；另外，屏幕上各個標誌點區域的大小和標誌點區域之間的距離是基本一致的。
[0021]以上所具體描述的，是一種應用於大規模的指向定位校驗系統的基於空間拓撲關係的新型標誌區域校驗算法。文中對本發明的原理，技術方案和實施方式進行了詳細的闡述，以上具體實施步驟內容只是為了幫助理解，並不限定本發明的保護範圍，本發明適用於三個區域以上的具有唯一路由表所限定的空間拓撲關係的空間定位場合，凡在本發明的核心思想和原則之內，做的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。
【權利要求】
1.一種基於空間拓撲關係的新型標誌區域校驗方法，其特徵在於包括如下步驟: 1)、劃分區域:將用於射擊的大屏幕按照等距離等面積的方式劃分成不少於3個區域，在每個區域內排布不同數量的標誌點，區域間的最小距離大於區域內標誌點之間距離最大值的2倍； 2)、建立路由表:將每個區域作為中心區域，即路由表的表頭，區域的鄰域按照空間順時針排列作為子網拓撲，然後將每個區域的鄰域按照空間方位順時針排列製成路由表，其中第一列是待判定區域所具有的標誌點數量，後面各列是各鄰域所對應的編號； 3)、將攝像頭所拍攝到的各個區域進行統計，算出所有區域的個數和每個區域的標誌點數量； 4)、求出上述各個區域之間的距離並排序得出區域間最小距離Dis_Reg_Min，設定區域間閾值為 Threshold_Region = (1.3~1.9)* Dis_Reg_Min ； 5)、根據區域間閾值ThresholcLRegion判斷每個區域的鄰域，如果滿足兩個區域之間的距離小於或者等於區域間閾值，則可以認為一個區域為另一個區域的鄰域，並求出每個區域的所有鄰域Neighbour_Region以及鄰域的個數nTotalNeighbour ； 6)、對比路由表，查找並判斷一個區域的鄰域是否與路由表裡的相應鄰域對應，如果能夠找到路由表裡相對應的鄰域，則正確鄰域數加上I ;如果沒能找到，則錯誤的鄰域數加上I,並判斷每個區域的鄰域的正確率PercentCorrectNeighbour,以此為依據判斷此區域是否正確；正確率的計算方法為正確的鄰域的個數除以所有的鄰域的個數，如果一個區域的正確率大於0.5，則初步判斷此區域為正確區域，並將此區域保存下來，存為正確區域；然後算出正確區域的個數為ReserveRegion,正確區域的坐標為X_Region_Reserve, Y_Region_Reserve ;如果一個區域的正確率小於或者等於0.5,則初步判斷此區域為錯誤區域； 7)、求出保留後各個區域之間的距離Dis_Reg_C0nfirm，然後再次求保留後各個區域的距離鄰域的閾值Thresho I d_Region_Conf irm,先求出保留區域之間的最小距離Di s_Reg_Min，然後根據最小距離的1.3^1.9倍來求出保留區域距離的閾值；再對每個保留區域為中心求出鄰域 Neighbour_Region_Confirm ； 8)、判斷鄰域的角度Reg_Angle,判斷方法如下:首先求出中心區域與鄰域的X軸和Y軸坐標差值Dist_x, Dist_y,然後根據Dist_x和Dist_y的正負判斷其角度Reg_Angle ； 9)、將鄰域的角度按照由小到大排列，對比按照順時針排序的路由表，判斷保留區域的正誤，如果有任何一個鄰域不滿足角度關係，判斷該初步保留的中心區域是錯誤的，則排除這個區域是射擊的區 域；如果所有鄰域滿足路由表所規定的角度順序，則繼續保留這個區域，並最終確定為是射擊的區域。
【文檔編號】G06F19/00GK103793615SQ201410062261
【公開日】2014年5月14日 申請日期:2014年2月25日 優先權日:2014年2月25日
【發明者】種衍文, 張大勝, 潘少明, 王瑩瑩, 王澤文 申請人:武漢大學, 中山市金馬科技娛樂設備有限公司