主曲线的算法研究

本程序定义了主曲线和确定主曲线的实际算法。多边形线算法的基本运算法则是首先确定一条直线段，然后在循环算法中通过不断加入新的顶点来增加线段的数量。在加入一个新的顶点以后，所有的顶点位置在一个内部的环中被更新。由算法所产生的曲线如图1，在这个例子中，PL运算法则和HS运算法则在计算的复杂程度和算法的完善程度上作出了比较。4段和15段，由在半圆上任意两个坐标点加入单独的高斯误差而产生。

PL算法[12]在由NIST19号专有数据库产生的单独数据元构成的图像中得到了测试。我们发现PL算法可以有效的找出没有环和分叉的图像的中间轴。这个在图2中有显示。由于中间轴可能是一些曲线连接而成而不是只有一条曲线，所以在这里我们扩展了PL算法，找出数据元的主曲线。扩展了的算法也包含了实现分段线性骨架的两个原则，一种获取字符图像近似轮廓的初始化方法和一系列用来改善由初始化方法获得的骨架结构质量的更改结构工作。为了避免混淆，我们用术语“骨架”来表示近似性中间轴的二元图像，我们把由PL算法产生出的连接曲线看做模板骨架.

应用

主曲线以前被用在图像处理领域。这种图像用来描述在卫星拍摄下的冰川及其轮廓。其主程序用了一个闭合的曲线来估算冰川的轮廓。专家们除去了HS算法[13]中不合适的部分，并且用更完善的粗略估算冰川轮廓的程序来取代HS算法的初始化步骤。此外，采用数据元集合，而不是HS算法所产生的点或线的集合，向中间轴集中的方式来扩展现有的聚合算法。初始化的曲线由SOM算法[12]的一个变量产生，在SOM算法中相互关系被定义为字符图像的一个最小二叉树。HS算法用来使曲线与模板相对应。下一步的要点与SOM算法的更新规则类似。

利用主曲线实现分段线性骨架的方法被Mahmoud、Datta和Parui[14]等人所提出。同样的方法，在SOM算法中用来最优化分段线性骨架的顶点位置。算法在构建骨架方面采用“自顶向下”的策略：近似性地从一个线性拓扑出发，然后逐步加入环和交叉到骨架中，骨架是由基于SOM算法的当前几何样式得出的。SOM算法涉及到一个获取字符图像分段线性骨架的运算法则。这种运算法则以ISODATA算法[12]为基础，ISODATA算法近似于SOM算法。

目的

主曲线算法的目的是找出与字符图像相对应的光滑的分段线性曲线。这些曲线在某个顶点彼此连接，因而在字符图像的中心平面范围内形成一个欧几里德曲线。一个欧几里德曲线G（V，S）在空间中由变量V和S确定，

主曲线算法从一个基于传统稀释方法的初始化工作开始。初始曲线找出字符图像的近似拓扑结构，然而,它不是平滑的，而且它通常包含许多假的分叉和不适合的结构元素。为了解决这两个问题，在前两步中间增加了更改结构的步骤(图3)使得主曲线算法更加有效。在更改结构步骤中，我们运用一些 *** 作手段来调整曲线骨架结构的不完整的地方。\(a)图是在初始化步骤后由主曲线算法生成的曲线骨架；（b）图是经过首次拟合-光滑步骤后生成的曲线骨架；(c)图是经过更改结构后生成的曲线骨架；(d)图是第二次拟合-光滑步骤后产生的曲线骨架(算法输出)。我们重复使用PL算法的扩展版本来构造光滑的骨架曲线，同时保持曲线与字符图像的轮廓的距离近似相等。算法建立在最小能量函数的基础之上

研究动机与意义

自1904年Spearman[13]提出线性主成分分析方法以来，由于这种方法简单且便于使用，至今还是数据统计分析的重要工具之一。线性主成分分析的原理是将数据集合投影到一个矢量，使得投影的均方差最大，由此，将这个矢量称为数据集合的第一主成分。正是这个考虑，在均方差的意义下，这个方法有两个重要的优点：其一，数据集合可以使用一个矢量来描述，从而达到减小信息描述长度的目的，其二，计算第一以及依次主成分，可以变换为求解基于数据自相关矩阵的特征值方程。另外，第一与依次主成分矢量保持正交关系，这意味着，与主成分矢量平行的矢量具有与主成分相同的性质。正是这两个原因，加上在统计上以均方差为保证，主成分分析得到广泛的应用。 由于信息描述长度与信息保持性之间存在矛盾，相对较长的信息描述长度，较短描述长度的信息描述是以损失信息保持性为代价的，而主成分分析的本质是一种在均方差意义下的统计平均。尽管它可以获得较短的信息描述长度，但是，信息保持性的代价相当大，由于信息保持性是对数据分布的规律性认识，因此，对某些问题，这个代价可接受的，但是，另外一些问题，可能就不能接受了。例如，对原始语音信号的分析，单纯的主成分分析就不一定有效。 为了说明信息描述长度与信息保持性之间的关系，下图是一个简单的例子。图5是由300个包含误差的数据点构成的余弦状分布，图5(a)的直线是数据的第一主成分线，其对余弦数据的描述长度显然较图5(b)要短，因为这些数据点将使一个线段描述，因此，只需给出线段起点和终点即可，可以认为图5(a)给出了一个短描述长度的关于数据集合的描述；显然，图5(b)对数据的信息保持性则比图5(a)要好，一方面，它与数据间的距离均方差也要小，另一方面，它勾画出原始信息的轮廓。图5(b)恰恰是本文所讨论的根据主曲线原理所获得的结果。那么，两种描述哪一个更为合理呢？显然，这没有一个一般性的答案，这取决于所需解决问题的需求。

图5 信息描述长度与信息保持之间的关系

图5也说明无监督学习较监督学习困难的原因，问题本身的病态定义导致不得不引入复杂性思想，如统计学习理论中的风险结构最小、贝叶斯学派中的贝叶斯信息准则、Kolmogrov算法[11]复杂度引出的最小描述长度等等，来寻求在信息保持性与数据描述长度之间的折衷。目前，尽管在主曲线的研究中，还存在着大量的数学问题，但是，由于其暗示的广泛应用前景，已引起计算机科学家的关注，现在应用方面已有大量的报道，如线性对撞机中对电子束运行轨迹的控制、图像处理中辨识冰原轮廓、手写体的主曲线模板化、语音识别中对声音数据的约简建模和数据可听化、生态学中寻找种群的有序分布及过程监控。同时，在认知领域Seung[14]提出感知以流形方式存在，并在神经生理学上发现整个神经细胞群的触发率可以由少量的变量组成的函数来描述，如眼的角度和头的方向，这隐含了神经元群体活动性是由其内在的低维结构所控制。主曲线本身是流形的一维形式。

原理、发展脉络以及应用

为了说明主曲线的原理、发展脉络以及应用，首先介绍其原始动机是必要的。Hastie在他关于主曲线的开创性论文中描述了其研究动机，Hastie认为主曲线与非线性回归方法的发展上具有对称性，分别是线性主成分分析与线性回归分析的非线性推广模型，Hastie写到：类似于线性回归方法的非线性推广，使用光滑曲线代替线性主成分总结数据，以求出对称变量之间的曲线，这样的曲线从数据的中部光滑地通过，且不限制于对数据的光滑线性平均，甚至不限制于数据的中部是直线，只希望使得数据点集合到曲线的正交距离最小。这个陈述清晰地指出了他的研究与主成分分析和回归分析的区别，并给出了建模的统计目标。同时，从这个陈述中也可以看出，基于直线的主成分分析只是主曲线的一个特例。因此，主曲线的提出，可以理解为基于线性的主成分分析方法向更精确描述实际世界的非线性分析方法的推广。 应该指出的是，目前，“向非线性”推广是数据统计分析的研究主流，但是，存在着不同的技术路线。

分类

最典型的研究大致可以分为两类：

其一，根据统计学习理论中的核技术，将数据集合映射到特征空间，然后，在特征空间计算数据集合的主成分，称为核主成分分析(KPCA)，这个技术路线的本质还是线性主成分分析。

其二，从数据本身的分布出发，希望找到能最好描述数据内在结构的概率分布模型，如生成式拓扑映射(Generative Topographic Mapping,缩写为GTM)，矢量量化(VQ)及主曲线，以及流形拟合等。提出“主曲线的研究与回归分析有何区别”是自然的，两者的动机都是企望求出一个函数代替数据集合，但是，两者有本质的差别：其一，一般地说，回归分析是假设数据集合的变量有因果关系，换句话说，数据的变量可以表示为一个因果关系的函数，有些是自变量，有些则是因变量。其二，回归分析一般需要给定一个数学基函数，回归分析是根据数据集合中变量的因果关系，计算这个数学基函数待定的参数。这与主曲线的研究动机完全不同。对于前者，主曲线的研究目标是解决数据变量没有必然因果关系的问题，更重要的是后者，认为事先假定数据服从某种分布(如正态分布)的方法(这与给定数学基函数，根据数据确定参数的方法类似)，对某些未知世界的解释是不合理的，因为这个假设可能是错误的，为了保证数据分析不是假设在一个错误结构下，主曲线的研究强调非参数分析。当然，这并不是完全否定了参数法这一经典方法，事实上，参数法在先验知识明确时存在相当大的好处。总之，根据上述讨论的动机，主曲线是寻找一种几何上直观、理论上完备、就解决的问题而言，这个方法与主成分分析一致，但是，主曲线的目标不是仅仅寻找一个数据集合的脊梁骨，而是希望获得数据集合的骨架。数据集合的脊梁骨可以使用线性的方法解决，但骨架就需要借助非线性方法了。应该强调的是，主曲线继承了主成分分析的众多思想，它是主成分分析的非线性推广。另外，尽管这个方法似乎与回归分析的目标类似，都是试图获得对数据集合信息长度更短的表示，但是，这个方法与回归分析完全不同，最大的差别是它不是事先给定一个基函数(或假定一个分布)，从而将问题变换为参数估计问题，而是一种非参数的方法