在第三节，我们介绍了经过一次性全局变换来校正矢量地图的整体线性校正算法，并给出了算法实例。无论从理论，还实际的校正的效果来看，整体线性校正算法（最小二乘法，变尺度法等）只能达到全局的最优，而无法使得局部也达到最优的效果。尤其，对于矢量地图中存在的非线性误差，使用线性的方法无法进行有效的校正。随着研究的进步，提出了离散非线性校正的算法，这种算法是为了弥补线性自动校正的缺陷，得到精度更高的矢量地图自动校正。
本章介绍早期提出的一种离散非线性校正算法，在应用于成都、合肥等城市矢量地图的校正时取得了相当满意的效果。尽管随着相关研究的深入，发现了这种算法的很多不完善之处。但作为最早提出的离散非线性校正方法，它为离散非线性校正思想的完善奠定了基础，也有助于我们对矢量地图自动校正这一研究领域的发展有着更为全面的了解。
4.1 算法产生的动机
前面我们在分析矢量地图整体线性校正算法的局限性同时发现了手动逐点校正方法的某些优点。将矢量地图整体线性校正算法与手动逐点校正方法作一个对比分析是很有意义的。
矢量地图整体线性校正过程是自动的；它均匀地使用所有样本点的信息获得一个线性变换规则并同时对地图全平面内的所有节点进行校正；矢量地图整体线性校正算法不可能克服原地图存在的任何非线性误差。与此形成鲜明对照的是手动逐点校正方法。手动逐点校正方法应该归属于矢量地图的非线性校正范畴。手动逐点校正是人工而非自动的；它逐点使用样本点的信息并且仅对当前所选择的样本点进行校正而放弃使用其它节点原本可以提供的校正信息；手动逐点校正的方法对任何一个样本点的任何位置误差均能一次得以校正，但同时却造成矢量地图在该样本点邻域上的非线性程度加剧。能否对这两种校正方法扬长避短，找到一种新的算法，使其能自动进行，能充分地使用已知精确位置的样本点的明显的和潜在的校正信息，又能逐块有效地克服原地图存在的任何非线性误差。这就是本论文重点讨论的矢量地图离散非线性校正算法的最初动机。
以上的分析给我们的有益提示如下：矢量地图离散非线性校正算法的“离散”（或者说“分块”）是同时针对矢量地图整体线性校正算法的“整体”和手动逐点校正过程的“逐点”而提出的。也就是说，针对矢量地图整体线性校正算法只能获得全局的最优这一特点，离散非线性校正算法企图进一步达到任意一个“分块”局部区域的最优校正；针对手动逐点校正过程每次校正只能调整一个节点的位置，离散非线性校正算法企图“以点带面”，达到整个“分块”内的局部区域优化校正。
4.2 算法的基本思想
离散非线性校正算法的基本思想描述如下：
1) 整个校正过程由n 个已知精确位置的样本点的累加校正过程组成。（样本点在校正前，是指它在矢量地图节点坐标数据库中的坐标数据。在校正后这一数据被其已知精确位置的相应坐标数据所替代。这种相互对应的点对为地图的校正提供了丰富的信息参考。）在地图平面上，每个样本点及其邻近区域组成的一个分块区域，我们称之为一个离散块。校正是分步进行的，每一步校正过程只对该步所选择的离散块内的所有矢量节点进行位置校正。因此离散非线性校正算法要引入“离散”的概念，并遵循系统离散建模的相关理论。
2) 离散块中的校正算法选择。离散块内的校正是基于当前所选的样本点在校正前后的两个坐标数据的差值（反映为样本点位置的移动），在保证矢量地图节点间的网络拓扑关系不发生变化的前提下，由样本点的位置移动获得该离散块中所有其它节点的相应移动数据。另外，为了遵循整幅地图的离散建模，保证所有离散块之间可以实现无缝衔接，离散块中的校正算法还必须保证离散块边缘上的节点位置不变。离散块中的校正算法不可能是简单的线性变换，一定是某类非线性校正算法。因此算法要引入“非线性”的概念，同时要满足该变换的边界条件，即保证任何时刻全平面的无缝拼接。
3) 关于离散块的选取。
校正过程中，已经得到校正的样本点在以后的校正过程中位置保持不变。这也是新算法确定离散或“分块”的唯一原则。这样做的理由是，样本点得到校正，相当于发生了位置移动，坐标变为其精确的地理位置坐标。这种精确的地理位置信息是已知的，将其固定不动，才能作为参照物提供信息参考。这样以来，那些属于整幅矢量地图节点集合，却不属于样本点集的节点，其位置会随离散块的不同而不断地发生变化，直到离散校正算法完成。可见，算法中的“离散”概念不是对地图平面的静态离散（对比离散线性系统理论中离散概念仅是时间上的静态离散）, 而是基于地图平面上随时刻（已校正样本点数）而不同的动态离散。
同时，由于样本点的个数是有限的，离散非线性校正的分步次数也是有限的。从测量的角度来说，多次测量可以减小误差。因此，为了在有限次数的离散分块校正过程，尽可能地提高精度，应当尽可能地选择最大的块，以保证可以对更多的点进行尽可能多次数的校正。
从以上两方面考虑，离散非线性校正算法确定“分块”的原则就是：每选择一个新的样本点进行位置校正前，在根据当前时刻的已校正结果形成的整体地图平面上进行分块；只要保证已校正过的样本点位置固定不动，不仅不需要考虑历次分块的情况，而且应该取以新选择的校正点为核心（不是中心）尽可能大的分块区域。
可以推知，随着离散非线性校正过程的推进，不动点（已经得到校正的样本点）的增多，新的待校正离散块必将越来越小。形象地说，以时间回顾，多层离散块重叠交错地分布在时间轴上；以地图平面回顾，一张被揉捏过的矢量地图，如同平面保持但又挤压变形的柔性铁丝网经历多次的单点牵拉定位。
综合以上的思路，简单地说，矢量地图离散非线性校正的思想关键在于两点——离散块的确定和离散块内节点校正方法的确定。上面的讨论中明确了算法必须遵循的原则。利用这些原则，可以指导算法的具体实施。
离散非线性校正思想自提出之日起，就备受关注。下面将对早期的离散非线性校正算法的具体操作方法进行说明。这些都是我们后续讨论和改进的基础。
4.3 离散块的选择
这里首先把离散非线性校正算法中与当前时刻的校正点、离散块等概念有关的表达符号再次明确如下。
假设选取待校正地图上的n 个点构成样本点的集合G ，它们对应的精确位置构成点集G* ，即：
下面的叙述涉及视觉效果的内容是以计算机屏幕上所显示出的矢量地图为准的。矢量地图的显示必须先确定矢量地图定标比例系数(ScaleX，ScaleY ) ，坐标对应原点经纬度p(x0,y0) 及方向角q 。中国科大GPS实验室开发的矢量地图自动生成平台采用的是GPS道路轨迹自动完成矢量地图初始定标过程。在这个轨迹自动定标之后，才开始校正算法的步骤。下面的说明中凡是涉及每一个新的样本点数据的输入操作，都不需要从键盘输入数字，而是直接在屏幕显示的矢量地图上用鼠标点取该点在校正前和校正后的位置来完成。点取该点校正后的精确位置，实际上就是获取位于该点的GPS轨迹记录，自动完成该点精确位置经纬度数据的输入。下面给出离散非线性自动校正算法的具体实现步骤：
步骤1,2 两点定标--矢量地图最小校正系统
4.5 校正算法实例
前面的内容里，从理论方面详细地介绍了矢量地图的“离散非线性校正算法”。下面给出实际的工程中该算法的应用实例，帮助我们体会算法的有效性。
4.5.1 合肥市矢量地图校正实例
把离散非线性校正算法应用于合肥市矢量地图的校正，得到了如下的结果。在图4.5.1 中，我们给出了校正前的合肥市矢量地图以及准确的车辆轨迹，并选取了六对样本点，对整个矢量地图进行校正。对于每一步校正后的矢量地图节点的变换情况，图4.5.2 到图4.5.7 给出了清晰的演示。图4.5.8 到图4.5.10 给出了采用十二对样本点进行校正的实例。从图中可以看到，随着校正点的增加，校正后的矢量地图误差越来越小，并最终达到很好的效果。
4.5.2 算法分析
把上面的校正结果同第三章中整体线性校正得到的结果进行比较分析，可以得到这样的结论：
传统的整体校正方法如最小二乘法等，只能使校正过的矢量地图达到全局最优，而不能达到局部区域的最优校正，即无法完全准确无误地校正好整个地图区域。离散非线性校正算法通过对整个地图平面进行分块非线性校正，使得在合理选取校正样本的情况下，能够对整个地图的所有的局部区域达到最优的校正，从而提高了校正后的矢量地图的精度。从适用性这一点上来说，只要矢量地图的道路间的相对位置是正确的，则通过选取合理的样本点，此算法一定能达到较好的校正效果。
由于离散非线性校正采用分块校正的思想，根据已校正点来确定离散块，并且只对离散块内部的节点进行校正。因此，样本点选取的数目、次序以及位置都成为影响校正效果和校正效率的很大因素。图4.5.7 和图4.5.10 在局部区域校正效果的差异也验证了这一点。因此，样本点的选取成为本算法需要改进和完善的地方之一。
4.5.3 算法的综合运用
在实际的运用中，我们把整体校正算法与离散非线性校正算法结合起来使用，效果更好。即：针对一幅未校正的矢量地图，我们先采用整体校正算法，对地图作一个全局的伸缩和旋转变换。然后采用离散非线性校正算法进行二次校正。下面是我们综合运用这两种方法对成都市矢量地图进行校正的结果。最后两幅图提供了车辆轨迹的检查以及成都市矢量地图在监控系统中的良好运用。
