在第三章中，我们介绍了初步得到的矢量地图中基本信息并不能完全正确的反映实际的城市道路位置和拓扑状况，并对其中具有普遍性意义的一些错误情况进行了分类和原因分析。造成这些误差的原因是多方面的，如果要从根本原因上解决这些问题，需要对预处理的各个阶段进行改进以保证结果的高度正确性。然而要做到这一点有很高的难度：选用的道路识别、提取以及细化、矢量化等处理方案都已经具有较高的准确性和快速性，要在保证快速性的同时进一步提高算法的准确性可能性并不大；在道路交通地图的处理中总是会因为一些不同的特殊情况出现而引入误差，这些误差如果单纯依靠图像处理的方法很难被正确校正。鉴于以上原因，本文并不希望依靠对前面处理的全方位改进来对误差进行校正。
本章根据城市道路交通的规则知识，针对第三章提出的各种问题，提出相应的解决算法。在保证不引入新的误差的前提下，对原有矢量地图基本的位置和拓扑信息进行了有效的校正。校正算法的算法复杂度较小，而且由于采用了相关参数的自适应选取，算法的适应性和自动化程度也较高。
4.1 基于道路规则的校正算法的提出
试图从矢量地图误差的产生处即采用图像处理的方法来解决问题是不大可行的，我们需要寻找其他的切入点，来对矢量地图信息加以校正。因此，这里根据城市道路交通地图的特殊性，以城市道路的普适规则为约束来设计校正算法。
城市道路的分布与设计有一定的基本规则可循[32]。同样的，反映到矢量地图中，作为实际意义上地点和道路精确的指代物，点和弧的分布也应该保持着原有道路交通的规则和特性。换而言之，矢量地图信息中的点和弧不但具有其本身的几何和拓扑特征，而且同样被赋予了地点和道路的实际意义，其本身也服从实际城市道路交通的一些分布规律。在矢量化地图的生成过程中，这些潜在的规则信息并没有得到考虑，事实上，这些规则为矢量地图的点弧等基本信息提供了大量的约束，利用这些基本约束可以从矢量地图中搜索、判定及校正各种含有误差的信息。这就意味着避免了图像处理的复杂操作，直接对矢量地图基本信息做分析处理，也就避免了大量的运算，节省了处理时间。基于以上原因，本文通过对城市道路基本规则的分析，结合第三章对于矢量地图误差的分析，给出对于矢量地图基本元素的约束，并实现对已有矢量地图信息的校正。这正是本文中校正算法的动机和出发点。
4.1.1 城市道路基本规则介绍及分析
城市交通道路在建设时根据城市整体规划以及实用型的需要，要有一定的设计原则。其中城市道路交通规划设计规范（ GB50220-95 ） [33-34 ]和城市道路设计规范(CJJ37-90)[35-36]是两个很重要的规范，在这两个规范中，对于城市道路交通的设计和规划做出了基础性的规定，是城市道路设计的基础。然而，这些规范的大部分内容都是从道路的实际设计着眼，它们所限定的内容并不能有效反映到矢量地图中。因此，在这里我们通过对这两个规范的学习和分析，并结合我们对于大量实际地图的分析和日常生活经验的总结，得出一些具有普遍适用性的基本规则备用，这些规则设计城市道路分布的各个方面，并与第三章中提出的各个问题互相关联，可以作为矢量地图点弧信息的有效约束条件：
规则1：连接每两个地点间的路段具有一定的长度，并且该长度不可能很短。
规则2：在同一条道路上交叉口出现的“频率”是一定的，即两个相邻交叉路口之间的距离不会过短。
规则3：对于原本基本上保持直线形态的道路，其各组成路段斜率应当与其总体斜率基本一致。
规则4：中间出现丁字路口的道路应该是直线道路，且相交道路基本上保持直交，斜交的话角度也会大于45 度。
规则5：城区道路较为密集的地区不出现较为接近的断路点。
规则6：道路网节点上相交道路的条数宜为4 条，并不得超过5 条。道路宜垂直相交，最小夹角不得小于45 度。
规则7：道路相交时宜采用正交，必须斜交时交叉角应大于或等于４５度，不宜采用错位交叉，多路交叉和畸形交叉。
规则8：平面交叉口的形式有十字形、Ｔ型、Ｙ型、Ｘ型及环型交叉等。
规则9：应避免设置错位的丁字型路口。
下面对于以上的规则结合其在矢量地图中的表现加以解释说明：
规则1 说明：这一条是显而易见的，在城市道路中，道路和路口的设置必须符合一定的密度，如果太密是对城市空间的巨大浪费，所以不会出现极近两个路口的情况。反映到矢量地图中，以上规则可描述为：每条弧具有一定的长度，该长度有一个下限值(见图4.1)。
规则2 说明：这里交叉口的“频率”是指交叉口在同一方向道路单位空间内出现的次数。交叉口的设计是城市道路交通设计的重点，其目的是便于城市道路上车行交通和人行交通的组织和转换，同时，交叉口也造成了城市道路通行能力的下降，因此，交叉口的分布应该具有一定的密度，过密的交叉口不但没有必要，而且会造成空间的浪费，在实际生活中也不大可能出现。
因此，在矢量地图中，出现的具有交叉特性的点之间也应该有一定的距离(见图4.2)。
规则3 说明：本规则的出发点是对于一条总体上符合直线形状的道路，其各个路段也应该同样保持着类似的直线走向。
因此，反映到矢量地图中，对于基本上反映同一道路的各个弧段，其中心点应该在同一中心线上，并且各弧段的斜率应该与该道路的平均斜率相差很小（见图4.3）。
规则4 说明：所谓的丁字路口，就是在主干道路中间某点上有一个与另一条直交道路（多为支路）公用的路口且非交叉口。其交叉类型与Y 型交叉路口相似但是成因完全不同，Y 型交叉路口是三条不同道路之间的交叉，而丁字路口是两条基本直交道路之间的关系。
因此，反映到矢量地图上，它们的区别也就在于三条弧段间交角的关系(见图4.4)。
规则5 说明：城区的道路密集地区，多为城市的繁华地带，交通较为发达，在该地区很难出现几乎孤立的断路点，否则会对城市交通带来极大的不便。
因此，在矢量地图中，在点弧密集地区，孤立的断点也不应该出现（见图4.5）。
另外，在城市道路交通规划设计规范和城市道路设计规范中，有一些与交叉口相关的基本规定，这些规则具有普遍性，而且具有较为浅显的语义，便于编程实现。在这里我们也把它们作为实际规则加以利用：
规则6，7，8 说明：这三条规定了道路交叉口处的道路密度以及交叉类型，对于普通的平面交叉口构成了较强的约束。在实际生活中，违反以上三条的交叉口也很难找到。
在矢量地图中，代表交叉口的相应点和弧段也应该服从以上的约束条件（见图4.6）
规则９说明：丁字路口，如前所述，往往是在一条干道上出现的，对于城市的主要干道来说，要保证其交通的顺畅性，其中的丁字路口个数和分布是有一定限制的。错位的丁字路口意味着在很短的区间内设置两个路口，这对于干道交通的影响是很大的，所以实际上也很少能看到在干道上的错误丁字路口。
在矢量地图中，同样的情况也需要避免(见图4.7)。
以上所述及的城市道路基本规则还是文字层面上的描述，要把这些规则反映到我们实际的矢量地图信息中，需要用点弧的基本形式来对它们加以描述。这里首先对矢量地图的各要素规定统一的记号表示：
以上给出了一些可能用到的道路规则，这些规则一些可以用作对于各种问题点的检测与判定，一些可以用作对问题点的校正。要把这些规则有效的加以利用，以解决在第三章中所分析出的各类问题，还需要设计较为完善的校正算法。
4.1.2 算法流程介绍
这里的校正算法主要以对点的校正来实线对整体地图的校正。在地图中，弧的信息实际上是由其两个端点的性质所决定的，也就是说，矢量地图的信息事实上点信息的各种组合，各种误差也往往表现为点的误差，因此，对于点进行校正，同时修改相应的弧乃至路段的信息，就可以达到对地图的校正；同时，上一小节的规则大多数是针对点的规则，以点为基本处理对象，能够充分发挥规则的约束作用。
以点的误差为处理对象，本文中的校正算法分为如下几个步骤：
1）初始化数据结构以及各种阈值信息。
2）可能问题点的搜索。
3）问题点的判定。
4）各种问题点的处理。
5）更新结果，如收敛则结束，否则更新数据结构及相关阈值，返回2）。
以下对于各步骤加以说明：
1)本算法中，原有的矢量地图文件中只包含点的位置信息和弧的基本组成信息，为了便于后续的算法处理，在我们设计的数据结构中包含有诸如相邻点的信息等附加信息(数据结构具体定义见5.1)，因此需要在校正算法开始时对原数据进行分析，对以上的数据结构进行初始化；另外，以上的规则中涉及到大量的阈值，这些阈值的选取当然可以采取人工选取的方式，但事实上，在已有经验的基础上结合地图自身的特点，可以设计出其自动选取的方法，其具体方案将在本章最后一节介绍。
2) 在矢量地图的点集中，有错误或者误差的点往往只占小部分。因此，为了提高算法的处理速度，先通过一个粗的筛选来选取有可能出现误差的点，从而大大缩小处理范围。
3)以上得出的是可能的问题点，要对其进行进一步的处理，还需要判定其是否真的有错误或误差，判定其问题类别。第三章中涉及的各种问题点都有自身的特征，结合我们给出的规则和其他知识可以判断出其问题的性质。
4)对于已经确定其误差类型的问题点，根据其类别的不同，结合规则，可以给出不同的解决方法。
5)问题点处理结束后，应及时更新矢量地图信息。如果此时的地图已经满足设定的收敛条件，则输出结果；如果仍需要改进，则更新算法中的数据结构和阈值信息，继续处理。这里的收敛条件将在后文讨论。
综上所述，算法总体流程如图4.8 所示。在本章的剩余部分，我们将详细介绍算法各部分的实现。
4.2 问题点搜索策略
4.2.1 搜索规则
一幅矢量地图一般都含有几百上千个的点，而有可能是问题点的往往只是其中的一小部分。对于大多数点来说，它们自身的信息以及和它们有关的弧信息是符合实际地点和道路情况的，而且也很容易通过一定的规则证明其位置和拓扑正确性，从而避免在下面的校正算法中涉及，从而降低算法的复杂度，并提高计算速度。由于我们的校正算法所面对的问题点包括交叉点、断点、丁字路口点等。除了3.4.1中的丁字路口点之外，其他的问题点有一个共同的特点：在问题点发生的极小邻域内，往往会有其他点出现。按照我们在4.1 中分析得出的规则1，在实际的道路情况下，地点都是尽量稀疏分布的，不应该在很小的距离内(几十米内)分布两个意义不同的地点，也就是说如果在矢量地图中如果出现两个距离很近的点(无论是有邻接关系的还是之间断开的)，就很有可能在这里产生了问题。再结合对部分丁字路口的判断，就形成了一种简单可行的搜索策略：对于矢量地图内任一点c P ，如果该点满足以下条件中的一个，则把该点列为可能的问题点：
以上两个搜索判据中，1）可以搜索出错误的交叉点、断点以及拓扑错误的丁字路口点，2）可以搜索出位置信息有误差的丁字路口点。尽可能把所有有问题的点都分析到，这是我们校正算法的一个基本原则。因此这两条准则本身设计得较为宽泛，从而涵盖的点范围较大，这样做是为了保证有问题的点基本上都能被包括进来。事实上，正确反映了真实地图信息的点绝大多数也不满足以上两条准则，也就是说，这样的搜索策略一方面尽可能的把可能的问题点搜索出来，另一方面也没有把大量正确点错分为问题点，从而保证了算法的处理速度。
当然，矢量地图中有时会出现极个别反常规的错误情况，多与原地图数据模糊不清有关，这样的错误用我们上述的搜索规则也不易检出。要搜索出这样的问题点，必须比对原图并在原图上做详细的道路语义分析，这样做难度和复杂度都会很高，效果却未必会好，可能会造成对正确道路点的误判和误处理，这违反了我们对矢量地图做校正的另一个基本原则：在处理原有问题时不引入新的误差或错误。因此这里主要考虑各种具有一般性的错误问题，对于极个别的特殊问题留待将来解决。
4.2.2 搜索阈值的选取
对于判据1），决定搜索范围的阈值是R ，它反映着在该地图中实际地点间的间距下限，它的设定与地图的比例尺和该地域的道路疏密程度有关。如果该城市城区面积较大，地图比例尺较小，则图上较小的坐标差往往反映着实际状况下较大的距离，则T 的取值应当较小，反之则应相应取得大些，对于普通的城市道路交通地图来说，一般一个像素的跨度反映着实际场景中10 米~30 米间不等的距离。同时，在同一幅城市地图中，各部分的道路疏密程度是不致的，城市中心的道路和地点的分布往往较为密集，在该区域进行搜索，R 的取值应该略小以避免把大量正常点判为问题点；而城市外围道路的分布较为稀疏，各个地点间距离较远，因此可以把R 设大一些以保证把各种问题点包含进来。
对于判据2），其搜索的对象是有位置误差的丁字路口。由于丁字路口与Y 型交叉路口在形态上存在较大的相似性，其区别往往在于其中两条弧是否在同一直线上，为了不把Y 型路口误分为丁字路口，我们在这里将q 的取值取小一些，另外由于Y 型路口自身的交叉角度也有一定的范围(见4.1 规则7)，因此我们认为q 大于3 度小于20 度时满足准则2）的交叉点应该是位置有误差的丁字路口点，需要按照丁字路口点的处理规则加以校正。
以上是关于搜索过程中阈值选取的分析，基于这些结论，可以实现对阈值的自适应选取，具体的实现将在4.6 节中介绍。
4.3 交叉路口问题的解决方案
交叉路口处出现的问题一般是比较严重的拓扑问题，涉及到多余的点和弧的出现，因此在判定和处理时往往以拓扑问题的处理为主。对于仅仅是位置上的误差这里并不做分析，也是因为交叉路口自身占据面积较大，目标较为明显，在识别和矢量化的过程中不易出现位置上的较大误差。
4.3.1 问题交叉路口的判定
如3.4 节所述，交叉路口出现的问题点有两种基本的表现形式：多余分路口的情况和多余回路的情况。因此在判别的时候也应该遵循各自的法则进行。
4.3.1.1 多余分路口的判定
解释说明：以上实际给出了多余分路口的最常见的一种情况：十字交叉口的判别。事实上在交叉口中，十字交叉口在地图中出现的频率最高，出错的频率也最高，因此有必要着重处理。考虑到十字路口原本是由两条直线相交得到，即使出错之后相关的弧也应该保持原有直线的走向，我们这里利用弧的斜率来对这种情况加以判定。这里对应弧的夹角阈值v 一般取值设为20 度以下。
4.3.1.2 多余回路的判定
多余回路一般是在交叉路口处出现新的短弧将本无直接相连关系的节点相连，并形成回路。出现这种情况的路口多为Y 型和X 型交叉路口，并且回路往往是由3 条短弧所构成。因此，满足以下两个条件的若干个点可以视为组成了一个多余回路
1）在一个很小的区域S 内有3 个点或4 个点，每个点的连结弧数大于或等于3；
2）它们之间由3 条或4 条短弧形成一个小的回路。
以上的判据的约束力在于区域S 大小的定义上。在城市中心区域，道路网格较为密集，所以S 的大小一定要小于一般网格的大小，以避免误判别的情况发生。事实上，正因为出现这种情况的路口多为Y 型和X 型的占地范围较大的交叉路口，这样的路口在城市中心出现的可能性本来就很小，所以出现多余回路的可能性更小。所以，对于道路较密集的情况下，只需选取很小的S 就可以了
4.3.2 问题的解决
同样的，错误交叉口的解决也分为两种情况。
4.3.2.1 多余分路口的解决
多余分路口的情况一旦得到了确定，解决起来相对比较简单。只需要把原本是一个点的两个点合并，并且删除掉连接它们的短弧即可。合并得到的新点的位置可以选其中任一个点，但为了在位置上更加逼近真实情况，这里选这两个点的中点作为新点的位置。这样的选取可能会造成一定的位置误差，但一般不会有大的影响，而且可以在后续的整体调整中校正。
4.3.2.2 多余回路的解决
多余回路的处理与多余分路口的情况类似，直接将形成回路的几个点合成同一个点并删除相应连接弧即可。新点的位置坐标由该回路多边形的重心坐标决定。这里之所以选择重心，是因为重心的选取不受单个较远点的显著影响，更接近实际交叉点的位置。事实证明，选取重心带来的误差也最小。
4.4 断路问题的解决方案
4.4.1 断路的判定
以上的条件1）、2）是形成断点的基本条件。其中间距Dis的选取也要根据地图比例尺和所在区域的道路密集程度而定。由于一旦确定为断点，所做的校正操作会大大改变原地图的拓扑情况，所以对于断点的判定必须要格外小心，因此Dis的选取要很小。同时为了避免出现误判断的情况，我们这里设计了条件3）、4）来加强限定。由于断点在一般情况下都是孤立的断点，用条件3）可以起到一定的限定目的；另一方面，断点往往出现在一个互相连通的道路网络中，也就是说这两个断点可以通过其他途径相连接，因此在这里我们用条件4）对于这一性质加以限定，这样就避免了把本属两个道路集合但相互接近的点相互连接。
4.4.2 问题的解决
断点的处理方法比较直接，在两个断点间增加一条弧,将二者连接起来即可。但是，为了进一步的减少冗余的点数，我们分析新增加的弧与原有弧的关系，如果新弧的长度很短并且走向与其某条相邻弧相似，则可以把这条新的弧并入这条相邻的弧中，并删除相应多余的节点。
4.5 丁字路口问题的解决方案
事实上，丁字路口问题包括相近丁字路口造成的拓扑上的问题和一般丁字路口的位置偏移问题。前者事实上是一种特殊的十字路口问题，可以在4.3 的处理中加以解决。因此这里我们主要判定和处理一般丁字相交处出现的位置偏移问题。
4.5.1 丁字路口问题点的判定
4.5.2 问题的解决
有位置偏移误差的丁字路口点，需要把丁字点的位置做调整来校正其位置误差。在这里，其新位置由形成丁字路口的两条道路来决定。首先，将被弯曲的直线道路“变直”，即根据其另外两个节点获得其直线方程，然后求第三条弧所在直线与这条直线的交点，这个交点即是该丁字路口的新位置。事实证明，这样计算在绝大多数情况下减小了位置误差，故是有效的。
4.6 道路整体调整
在经过以上的处理后，矢量地图中各种拓扑错误和一些大的位置误差得到了相应的校正，除了极少数复杂的错误情况外，各种问题基本得到了抑制。然而，对于一些不明显的位置误差以及由于校正操作造成的新的较小的位置误差，还有进一步校正的可能。
以上的操作多是从局部着眼，没有利用全局的路段信息。因此，在这里我们利用4.1 节中的规则3，来对矢量地图再做一次整体调整。
以上的调整可以将原本在同一直线道路上的点基本调整至同一直线上，这无疑更符合该道路的实际情况。为了防止把原本不在同一路段的各点强行移至同一直线上，只需把e 的取值取小一些即可。
4.7 算法相关内容分析
4.7.1 阈值的自适应选取
4.7.2 处理结束后的数据更新
在我们校正算法的每次迭代结束后，需要根据当前的结果来更新原矢量地图的相关点弧数据。对于仅仅是位置上的修改，只需要修改相应点的坐标值即可；如果涉及到了点和弧的拓扑变动，则以点为基准进行更新：删除一个点，则遍历所有点和弧的信息，修改与这个点相关的内容，并做相应的调整；增加一个点，在前面的处理过程中会给出这个点的相邻点，因此只需更新这些相邻点的信息并增加相应的弧即可；如果一条弧的点数变为1 或者变为0，意味着这条弧也会被删除掉，只需更新相关内容。
4.7.3 算法的迭代终止条件
我们的校正算法是迭代进行的，在一次处理结束之后还需要对新生成的地图进行新的一次处理，这样便于逐步解决地图中存在的各种问题。这样的迭代操作也需要设定一个较合适终止条件，以避免浪费计算时间。如果把迭代终止条件设为没有问题点出现，则会导致迭代的效率非常低，可能几次的循环仅仅是为了解决一些并不重要的位置误差问题；同时，反复的代可能会出现死循环，即这次的处理在处理原有位置误差后又引入了新的位置误差，导致下次循环的校正又针对这些新的误差进行。所以，我们在这里把迭代终止条件设为：当本次循环通过搜索检测到的错误点数小于3，误差点数小于5时终止迭代。
