Message Board

Respected readers, authors and reviewers, you can add comments to this page on any questions about the contribution, review,        editing and publication of this journal. We will give you an answer as soon as possible. Thank you for your support!

Name
E-mail
Phone
Title
Content
Verification Code
Volume 43 Issue 11
Nov.  2018
Turn off MathJax
Article Contents

WANG Zhangang, WU Zixing, WANG Xianghong. Disjoint Region Merging and Topological Relation Computing Induced by Semantic Scale[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1712-1718. doi: 10.13203/j.whugis20170009
Citation: WANG Zhangang, WU Zixing, WANG Xianghong. Disjoint Region Merging and Topological Relation Computing Induced by Semantic Scale[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1712-1718. doi: 10.13203/j.whugis20170009

Disjoint Region Merging and Topological Relation Computing Induced by Semantic Scale

doi: 10.13203/j.whugis20170009
Funds:

The National Natural Science Foundation of China 41672326

The National Natural Science Foundation of China 41202238

More Information
  • Author Bio:

    WANG Zhangang, PhD, associate professor, specializes in the mathematical geology, 3D geological modeling and geological information system.E-mail:millwzg@163.com

  • Received Date: 2017-12-25
  • Publish Date: 2018-11-05
  • Topological relations vary with the changes of semantic scales.Complex regions with diffe-rent semantic scales are merged by a finite number of simple regions and their topological relations have to be updated.The current methods make use of inferred combinatorial tables based on basic topological relations between simple regions.However, these methods are generally only applicable to simple objects and have multiple solutions.This paper presents a computation approach of modeling scale dependences of topological relations based on the 9-intersection (9I) model.In terms of the disconnected region merging and adjacent region merging, 9I-based matrix operators are defined for computing directly topological relations of the coarse semantic scale from the relations of the detailed scale.The computation results of the 9I-based matrix operators have no multiple solutions, and the computation domain can cover for all possible topological relations between complex regions.The 9I-based matrix operators can be extended to process composite regions composed of disconnected simple regions by eliminating ambiguities.
  • [1] Goodchild M F.Metrics of Scale in Remote Sensing and GIS[J].International Journal of Applied Earth Observation and Geoinformation, 2001, 3(2):114-120 doi:  10.1016/S0303-2434(01)85002-9
    [2] 李志林.地理空间数据处理的尺度理论[J].地理信息世界, 2005, 3(2):1-5 doi:  10.3969/j.issn.1672-1586.2005.02.001

    Li Zhilin.A Theoretical Discussion on the Scale Issue in Geospatial Data Handling[J].Geomatics World, 2005, 3(2):1-5 doi:  10.3969/j.issn.1672-1586.2005.02.001
    [3] 李霖, 李德仁.GIS中二维空间目标的非原子性和尺度性[J].测绘学报, 1994, 23(4):315-321 doi:  10.3321/j.issn:1001-1595.1994.04.012

    Li Lin, Li Deren.Non-atomic Feature and Scale Effect of Two Dimensional Spatial Objects in GIS[J].Acta Geodaetica et Cartographica Sinica, 1994, 23(4):315-321 doi:  10.3321/j.issn:1001-1595.1994.04.012
    [4] 刘凯, 毋河海, 胡洁, 等.地理信息尺度的三重概念及其变换[J].武汉大学学报·信息科学版, 2008, 33(11):1178-1181 http://ch.whu.edu.cn/CN/abstract/abstract1746.shtml

    Liu Kai, Wu Hehai, Hu Jie, et al.Three-Tiered Concepts of Scale of Geographical Information and Its Transformation[J].Geomatics and Information Science of Wuhan University, 2008, 33(11):1178-1181 http://ch.whu.edu.cn/CN/abstract/abstract1746.shtml
    [5] 李霖, 应申.空间尺度基础性问题研究[J].武汉大学学报·信息科学版, 2005, 30(3):119-123 http://ch.whu.edu.cn/CN/abstract/abstract2133.shtml

    Li Lin, Ying Shen.Fundamental Problem on Spatial Scale[J].Geomatics and Information Science of Wuhan University, 2005, 30(3):119-123 http://ch.whu.edu.cn/CN/abstract/abstract2133.shtml
    [6] 吴凡, 李霖.空间数据多尺度表达模型及其可视化[M].北京:科学出版社, 2005

    Wu Fan, Li Lin.Spatial Data Multi-scale Expression Model and Its Visualization[M].Beijing:Science Press, 2005
    [7] 杜世宏.多尺度空间关系理论与实践[M].北京:科学出版社, 2014

    Du Shihong.Theory and Practice of Multi-scale Spatial Relations[M].Beijing:Science Press, 2014
    [8] Tryfona N, Egenhofer M J.Consistency Among Parts and Aggregates:A Computational Model[J].Transactions in GIS, 1996, 1(3):189-206 doi:  10.1111/tgis.1996.1.issue-3
    [9] Nguyen V H, Parent C, Spaccapietra S.Complex Regions in Topological Queries[C].The International Conference on Spatial Information Theory: COSIT97, Pennsylvania, USA, 1997
    [10] Du S H, Wang Q, Guo L.Modeling the Scale Dependences of Topological Relations Between Lines and Regions Induced by Reduction of Attributes[J].International Journal of Geographical Information Science, 2010, 24(11):1649-1686 doi:  10.1080/13658811003591672
    [11] Du S, Guo L, Wang Q.A Scale-Explicit Model for Checking Directional Consistency in Multi-resolution Spatial Data[J].International Journal of Geographical Information Science, 2010, 24(3):465-485 doi:  10.1080/13658810802629360
    [12] Du S H, Feng C C, Wang Q.Multi-scale Qualitative Location:A Direction-Based Model[J].Computers, Environment and Urban Systems, 2013, 41(4):151-166 http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0231547114/
    [13] Du S H, Feng C C, Guo L.Integrative Representation and Inference of Qualitative Locations About Points, Lines, and Polygons[J].International Journal of Geographical Information Science, 2015, 29(6):980-1006 doi:  10.1080/13658816.2015.1004333
    [14] Zhou X G, Chen J, Zhan F B, et al.A Euler Number-Based Topological Computation Model for Land Parcel Database Updating[J].International Journal of Geographical Information Science, 2013, 27(10):1983-2005 doi:  10.1080/13658816.2013.780607
    [15] Egenhofer M J.Deriving the Composition of Binary Topological Relations[J].Journal of Visual Languages and Computing, 1994, 5(2):133-149 doi:  10.1006/jvlc.1994.1007
    [16] Egenhofer M J, Franzosa R D.Point-set Topological Spatial Relations[J].International Journal of Geographical Information Systems, 1991, 5(2):161-174 doi:  10.1080/02693799108927841
    [17] Egenhofer M J, Herring J R.Categorizing Binary Topological Relations Between Regions, Lines, and Points in Geographic Databases[R].Department of Surveying Engineering, University of Maine, Orono, 1990
    [18] Herring J R.OpenGIS Implementation Specification for Geographic Information-Simple Feature Access-Part 2: SQL Option[EB/OL].http://www.opengeospatial.org/standards/sfs/,2010
    [19] Schneider M, Behr T.Topological Relationships Between Complex Spatial Objects[J].ACM Transactions on Database Systems, 2006, 31(1):39-81 doi:  10.1145/1132863
    [20] Li S J.A Complete Classification of Topological Relations Using the 9-Intersection Method[J].International Journal of Geographical Information Science, 2006, 20(6):589-610 doi:  10.1080/13658810600661383
    [21] Clementini E, Felice P D.A Spatial Model for Complex Objects with a Broad Boundary Supporting Queries on Uncertain Data[J].Data & Knowledge Engineering, 2001, 37(3):285-305 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=JJ0210250879
    [22] Worboys M F, Bofakos P.A Canonical Model for a Class of Areal Spatial Objects[C].The 3rd International Symposium on Advances in Spatial Databa-ses, Singapore, 1993
    [23] 王占刚, 杜群乐, 王想红.复杂区域对象拓扑关系分解与计算[J].测绘学报, 2017, 46(8):1047-1057 http://d.old.wanfangdata.com.cn/Periodical/chxb201708014

    Wang Zhangang, Du Qunle, Wang Xianghong.Dividing and Computing Topological Relations Between Complex Regions[J].Acta Geodaetica et Cartographica Sinica, 2017, 46(8):1047-1057 http://d.old.wanfangdata.com.cn/Periodical/chxb201708014
  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(6)

Article Metrics

Article views(3359) PDF downloads(194) Cited by()

Related
Proportional views

Disjoint Region Merging and Topological Relation Computing Induced by Semantic Scale

doi: 10.13203/j.whugis20170009
Funds:

The National Natural Science Foundation of China 41672326

The National Natural Science Foundation of China 41202238

  • Author Bio:

Abstract: Topological relations vary with the changes of semantic scales.Complex regions with diffe-rent semantic scales are merged by a finite number of simple regions and their topological relations have to be updated.The current methods make use of inferred combinatorial tables based on basic topological relations between simple regions.However, these methods are generally only applicable to simple objects and have multiple solutions.This paper presents a computation approach of modeling scale dependences of topological relations based on the 9-intersection (9I) model.In terms of the disconnected region merging and adjacent region merging, 9I-based matrix operators are defined for computing directly topological relations of the coarse semantic scale from the relations of the detailed scale.The computation results of the 9I-based matrix operators have no multiple solutions, and the computation domain can cover for all possible topological relations between complex regions.The 9I-based matrix operators can be extended to process composite regions composed of disconnected simple regions by eliminating ambiguities.

WANG Zhangang, WU Zixing, WANG Xianghong. Disjoint Region Merging and Topological Relation Computing Induced by Semantic Scale[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1712-1718. doi: 10.13203/j.whugis20170009
Citation: WANG Zhangang, WU Zixing, WANG Xianghong. Disjoint Region Merging and Topological Relation Computing Induced by Semantic Scale[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1712-1718. doi: 10.13203/j.whugis20170009
  • 尺度是空间数据的主要特性之一, 也是多尺度空间数据建模与分析中的重要内容。在地理学、地理信息科学等研究领域, 不同的认知过程, 其尺度含义不同[1-4], 如可划分为空间尺度、时间尺度和语义尺度等[4]。尺度变化可能导致空间数据的维数、几何形态、属性信息以及空间关系的变化[5-6]。多尺度数据处理与分析的一个主要内容是根据尺度变化对空间信息进行概化和综合, 通过对详细尺度的空间数据进行空间综合(选取、合并、化简)和属性综合, 达到自动或者半自动处理粗略尺度下的空间数据的目的。由尺度变化引起的拓扑关系、方向关系等空间关系的变化称为尺度依赖性建模[7], 主要应用于拓扑关系、方向关系的一致性分析[8-11]、多尺度空间数据查询[12-13]等领域。语义尺度影响下的拓扑关系多尺度计算是空间关系尺度依赖性建模问题之一[7, 14]。Tryfona等[8]、杜世宏等[7, 10]指出该问题的语义尺度主要表现为多尺度属性划分, 通过属性归纳从详细尺度向粗略尺度转换; 尺度变化后的空间对象通过区域合并进行概化综合, 此过程不改变区域对象的维数和几何形态, 空间关系由推理得到。

    目前, 拓扑关系的多尺度计算主要依赖组合推理的方法, 通过简单对象间的基本拓扑关系(简单区域间的8种基本关系, 线面间的19种关系等), 构建出推理组合表进行查表运算, 比如区域合并组合推理[8]、简单区域间的组合推理[15]等。这种方法简单直观, 易于理解, 但其不足主要表现为:①由于基于空间对象间的基本关系, 其推理结果的值域仍是基本关系; ②只能适用于简单空间对象的处理, 复杂空间对象间的推理组合不易实现; ③推理结果存在多解性。

    在拓扑关系的描述模型中, 9交模型[16-17]仍是广泛使用的一种方法, 被OpenGIS采用[18]。9交模型通过两个对象间内部(°)、边界(∂)和外部(+)的交集形成一个9交矩阵描述拓扑关系, 已被应用于描述复杂对象的拓扑关系, 如复杂区域对象间存在33种拓扑关系[19-20]。基于9交模型可以提供多种层次的空间查询, 包括谓词查询和9交矩阵查询[18, 21]。如果直接基于9交矩阵进行拓扑关系的多尺度计算, 可弥补现有方法的不足, 一方面可以不限于简单对象, 另一方面计算结果的值域可扩展为9交模型表达的所有拓扑关系。针对语义尺度影响下的拓扑关系多尺度计算, 本文提出了基于9交矩阵的计算方法, 通过定义9交关系矩阵操作算子, 直接计算出9交矩阵。

  • 区域对象在OpenGIS[18]和文献[19, 22]中进行了详细描述。设区域对象AR2, 满足$A = \overline {A^\circ }, \overline {A^\circ } $是包含A°的最小正则闭包; -AA的补集, 即-A= R2-A°。R2=A°∪ ∂AA+, -A=∂AA+, -(-A) = A。简单区域是一种特殊的区域对象, 同胚于一个圆盘, 具有完全连通的内部、边界和外部。

    对于R2上的两个简单区域A1A2, 如图 1所示, 将两个相离区域的并A1A2记为A1+A2, 其合并结果是一个复杂区域, 称为组合区域; 两个相邻区域(存在公共边, 拓扑关系为边相接)的并A1A2记为A1A2, 其合并结果是一个去除公共边内部的简单区域。

    Figure 1.  Definition of Region Objects

    语义尺度主要表现为多尺度属性划分[7], 比如:①概念划分, 即部分和整体的关系, 如行政区划, 村庄是县的一部分, 县是市的一部分; ②多尺度分类系统。属性是表征空间对象可被人类认知理解的概念化语义、符号或者名称。语义尺度的变化引起空间区域的多尺度划分, 表现为不同尺度下平面空间被划分成有限个区域对象的集合[7]

    定义1:语义尺度属性集S是一组属性的集合, 记为S ={ s1sm} (m>1)。语义尺度属性集S2比语义尺度属性集S1详细, 则存在映射f:S2S1, f表示部分和整体的关系或者分类关系映射。

    定义2:A是语义尺度S1下的一个区域对象, P ={ p1pn} (n>1)为一个简单区域集合, 称PA在语义尺度S2下的一个区域划分, 当且仅当下列条件满足:

    1) 语义尺度S2比语义尺度S1详细。

    2) p1pn均为简单区域。

    3) ∀ i, j = 1…nij, pipj的拓扑关系只能是边相接和相离情况之一。

    4) $A = \bigcup\nolimits_{i = 1}^n {{p_i}} $。

    5) pi属于语义尺度S2下的某一个属性。

    6) 同一属性的区域间只能是相离关系。

    以上区域划分是一个无缝划分, 不允许由粗到细的划分过程中出现空白区域。边相接关系说明相邻区域须存在公共边。区域合并是区域划分的逆过程, 即从一个详细的语义尺度S2向粗略语义尺度S1转换的过程。

  • 9交模型[16-17]是通过两个区域对象AB的内部(°)、边界(∂)和外部(+)的交集来描述拓扑关系。由一个3×3的0/1型9交矩阵R(A, B)表示:

    R(A, B)所能表达的拓扑关系总数为33种[19]。若AB均为简单区域, 仅存在8种关系:相离、相接、相交、包含、覆盖、包含于、覆盖于和相等。

  • 如果一个粗尺度下的区域对象B由两个相离的简单区域B1B2构成, 即B=B1+B2, 则简单区域AB的9交拓扑关系可通过AB1B2的拓扑关系分解计算得到[23]:

    式中, 运算符⊻称为相离区域间拓扑关系加算子。⊻满足交换律R(A, B1)⊻ R(A, B2)= R(A, B2)⊻ R(A, B1), 并且, R (B1+B2, A)=[R(A, B1+B2)]T=[R(A, B1)⊻ R(A, B2)]T, T表示矩阵转置。

  • 如果一个粗尺度下的区域对象B由两个边相接的简单区域B1B2构成, 记为B=B1B2, 此时利用运算符⊻不能计算出正确的拓扑关系。文献[8]通过推理组合表定性处理, 将计算结果限定在某几个关系中, 再根据实际交集情况逐一排查。如图 2所示, AB1B2的拓扑关系均为相交, 利用式(1)计算出的结果是相交, 显然与图示A包含于B不相符。利用文献[8]中的推理表, 图 2R(A, B)可以是相交、覆盖于和包含于3种取值情况之一, 这导致了推理的多解性。

    Figure 2.  Regions Merging with Common Boundaries and Topological Relations Computing

    由于9交矩阵以及8个基本拓扑关系是一种定性方法, 这类拓扑关系的描述模型通过0和1概化处理交集关系时, 已经丢失了大量的信息, 推理表只能给出取值的多种可能性。要消除这一多解问题, 显然需要补充信息, 弥补概化造成的信息损失。

    通过分析图 2拓扑关系计算失败的原因, 可以发现:①区域对象B1(或B2)的外部与B2(或B1)的内部相交, 通过9交矩阵R(A, B1)无法区分哪些部分是B2的内部; ②区域对象B1B2的公共边界属于B的内部, 从R(A, B1)和R(A, B2)无法获知A是否与公共边界相交。因此, 相邻区域合并后, 从9交矩阵无法有效判断出AB的外部和边界的真实交集信息。

    因此增加辅助信息, 使得拓扑关系可直接计算。当区域对象B由两个边相接的简单区域B1B2构成时, 增加辅助区域对象b1bn (n>1), 用以区分B的外部。添加规则如下:

    1) b1bn均为简单区域。

    2) 在{ b1bn, B1, B2}中, 其任意两个区域的关系只能是边相接和相离情况之一。

    3) 任意biB1或者B2存在边相接关系, 其中i=1…n

    4) B的边界是辅助区域对象边界的一部分, 即$\left( {\partial {B_{1}} \cup \partial {B_2}} \right)-\left( {\partial {B_{1}} \cap \partial {B_2}} \right) \subset \bigcup\nolimits_{i = 1}^n {\partial {b_i}} $。

    5) B1B2公共边界的两个端点位于辅助区域对象边界, 即$\partial {B_{1}} \cap \partial {B_{2}} \subset \bigcup\nolimits_{i = 1}^n {\partial {b_i}} $。

    图 3所示, 增加辅助区域对象, 图 3(b)图 3(c)为合理的添加规则; 而图 3(d)为不合理的添加规则, 因为b1b2不为边相接关系。图 4为区域合并后形成洞的情况, 洞内也需要增加辅助区域。

    Figure 3.  Extra Regions Added to Solve Ambiguities When B1 Meets B2 with Common Boundaries

    Figure 4.  Adding Extra Regions with Holes to Merge B1 and B2 with Common Boundaries

    当添加辅助区域后, 区域对象B的内部、边界和外部将分别由式(3)至式(5)计算得到:

    当区域对象B由两个相邻的简单区域B1B2构成时, 则简单区域AB的9交拓扑关系可通过AB1B2以及辅助区域对象b1bn (n>1)间的拓扑关系计算得到:

    式中, ⊥表示互换9交矩阵的第1列和第3列; ∧表示矩阵对应元素进行逻辑与运算。

    证明:设Ma={A°, ∂A, A+}, ∀aMa, 可得:

    式中, $\mathop \wedge \limits_{i = 1}^n $表示n-1个逻辑与运算; $\mathop \vee \limits_{i = 1}^n $表示n-1个逻辑或运算。由于AB1B2以及辅助区域对象b1bn (n>1)均为简单区域, AB1B2间的计算可以记为R(A, B1+ B2), 而A与辅助区域对象b1bn的计算可以记为R(A, b1 + b2 +…+ bn)。R(A, b1 + … + bn)的第1列与第3列调换, 即得R(A, B)= R(A, B1+ B2) ∧ [⊥R(A, b1 + b2 +…+ bn)]。

  • 图 5所示的气象信息系统空气污染条件中, 图 5(a)为华北4省市(北京市、天津市、河北省和山西省)气象信息系统某一时段的空气污染状况。其中一项查询服务为查询行政区域组合与污染条件分布区的拓扑关系。气象信息系统中, 最详细的尺度为县区级行政区(见图 5(b)), 系统只存储县区级区域和空气污染分布区域间的拓扑关系。县区级行政区采用简单区域对象进行表达, 省、市或者特定地区的区域对象由县区级行政区合并而成, 系统内仅存储了其对县区级行政区域的构成关系。由于存在相邻区域合并情况, 故在整个地图(华北4省市)外部增加了两个附加的县区级区域, 如图 6所示。

    Figure 5.  Meteorological Conditions of Air Pollution in Four Provinces of North China (At 6:00 on October 5, 2016)

    Figure 6.  Administrative Regions of Hebei Province and the Added Extra Regions

    A为某一时段某一等级空气污染条件分布区域(简单区域), 多个县区级行政区域合并与A之间的拓扑关系计算步骤为:

    1) 获取查询区域内所有县级区域对象的集合MB={B1Bm} (m>1)。

    2) 将MB中的区域对象根据相邻和相离关系拆分成多个相离部分Ci, 即MB= ∪Ci。其中, Ci满足:Ci中任意区域对象与非Ci中其他区域对象是相离关系, 且Ci中任意区域对象必与Ci中另一区域对象是相接关系, 否则Ci中只有一个区域对象。

    3) 对任意Ci, 存在与Ci中的对象为相接关系但不属于Ci的区域对象, 构成辅助区域对象集合Mb={b1bn} (n>1)。

    4) 针对任意Ci, 按式(6)计算ACi的拓扑关系。

    5) 按式(2)计算AB的拓扑关系。

    查询实例:计算2016年10月5日6时河北省与五级空气污染分布区的拓扑关系。步骤如下:

    1) 记简单区域A为五级空气污染分布区。

    2) 记区域B为河北省区域, 其由兴隆县等172个县级区域构成, 即:

    MB={B1B172}={兴隆县…宽城}

    图 6(a)可知, 河北由两个相离部分构成, 划分为两个区域, 即区域1(C1)和区域2(C2)。

    3) C1由169个县级区域构成, 即C1={B1B169}={兴隆县…}。记Mb= {b1b32, b33}={延庆…附加区域1, 附加区域2}, 按式(6)计算AC1的拓扑关系为:

    4) C2由3个县级区域构成, 即C2={B1, B2, B3}={三河, 大厂, 香河}。记Mb={b1b6}={通州, 顺义, 平谷, 武清, 蓟县, 宝坻}, 计算AC2的拓扑关系为:

    5) 按式(2)计算AB的拓扑关系为:

    通过计算可得9交矩阵R(A, B)的拓扑语义为“包含于”。

  • 空间数据间的拓扑关系往往随着尺度的变化而变化, 快速有效地计算拓扑关系有助于多尺度空间数据查询以及拓扑一致性分析。针对区域合并导致的拓扑关系变化与多尺度计算, 区别于目前组合推理的方法[8-10], 本文提出了直接基于9交矩阵的拓扑关系多尺度计算方法, 并进行了应用分析。不同语义尺度下的复杂区域由有限个简单区域合并而成, 包括相离区域合并和相邻区域合并, 通过定义两个9交矩阵操作算子, 可利用详细语义尺度下的拓扑关系计算出粗略语义尺度下的拓扑关系。该方法的特点为:计算结果值域为复杂区域间所有可能的拓扑关系, 可以适用于不同层次的查询分析; 主要针对数据变化不大的情况, 通过增加辅助信息消除了相邻区域合并引起的拓扑关系计算多解性; 目前只考虑了多个相离或相邻的简单区域合并情况。

    由于布尔型9交矩阵对真实拓扑关系进行了简化, 需进一步研究采取增加信息的办法, 扩展本方法适用于尺度变化引起的拓扑关系计算问题, 并结合栅格领域、方向关系消除计算歧义性; 同时后续研究还可考虑将该方法扩展到带洞区域或者其他类型的空间对象(比如点、线)的多尺度分析中等。

Reference (23)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return