关于树的代数连通度的Fiedler不等式的新证明(英文)

设T为含n个顶点的树,L(T)为其Laplace矩阵.L(T)的次小特征值a(T)称为T的代数连通度.Fiedler给出如下关于a(T)的界的经典结论. a(Pn)≤a(T)≤a(Sn),其中Pn,Sn分别为含有n个顶点的路和星.Merris和Mass独立地证明了:a(T)=a(Sn)当且仅当T=Sn.通过重新组合由Fiedler向量所赋予的顶点的值,本文给出上述不等式的新证明,并证明了:a(T)=a(Pn)当且仅当T=Pn.

化学图论与极值图论中的代数方法

图论是离散数学最重要的分支之一，主要研究有限个对象的二元或多元关系，或有限集的子集系统，在数学、自然科学和社会科学等领域都有着重要的理论意义和应用价值．

关于混合图的特征向量的结构(英文)

设G为一个混和图. 它是通过对一个无向图定向其中的某些边而获得. 若G 为简单图, 关于G的对应次小特征值的特征向量的结构, Fiedler 给出一个值得注意的结论. 当G 为恰含一个非奇异圈的混合图时, 关于G的对应最小特征值的特征向量的结构, 根据Fiedler 的结论, 获得一个类似结果.

非二部图的最小特征值

设G是一个简单图,其特征值定义为它的邻接矩阵的特征值。在给定阶数的非二部图中,本文确定了最小特征值达到极小的图,并在文末提出一个问题及相关的猜想。

关于一致超图直积的循环指数

设G和H为m-一致超图,G×H为G和H的直积.研究直积G×H的循环指数c(G×H)和因子超图的循环指数c(G),c(H)之间的联系,证明了G×H是谱[c(G),c(H)]-对称的,从而[c(G),c(H)]整除c(G×H),其中[a,b]记正整数a,b的最小公倍数.

关于树的Large Laplace谱扰动(英文)

讨论树在添加一条边后其Laplace谱发生的扰动,刻画了满足如下条件的匹配数为2或3的树添加一条边后所有变化的特征值以整数增加.对于每个μ≥2(或n≥5),构造了一个匹配数为μ(或顶点数为n)的树,以满足上述性质.

基于图割的图像匹配算法

用标号表示视差,建立能量函数,把匹配问题转化为能量函数最小化问题;通过构造网络,使能量与网络的割的容量相联系;利用图的网络流理论给出能量函数的最小化,从而获得图像匹配的视差数据.与目前已有基于图割的匹配算法相比,本算法将标号从1维向量推广到2维向量,适用于更一般情形下的视觉匹配,并且在全局上获得能量函数最小.实验结果表明,所提的匹配算法准确率较高.

基于图的Laplace谱的特征匹配

为了能对等距变换和相似变换后的图像进行精确匹配,提出了一种基于图的Laplace谱的特征匹配方法,该方法是首先给定两幅图像的特征点,然后分别定义其Laplace矩阵,再通过分析该矩阵的特征值及特征向量来构造特征点匹配矩阵;最后根据匹配矩阵元素的大小和位置信息来实现特征点匹配,并从理论上证明了该算法在对图像进行等距变换或相似变换情况下能获得精确匹配。实验结果表明,该方法对真实图像的匹配精度可达到82%。

一种结合形状上下文分析的Laplace谱匹配算法

提出了一种结合形状上下文分析的Laplace谱匹配算法。工作主要侧重于如何提高Laplace谱匹配算法对点的位置随机抖动的鲁棒性。首先,使用Laplace矩阵的特征向量和特征值以及双随机矩阵的方法计算初始匹配概率。然后,借助于概率松弛算法,将用形状上下文表示的局部相似性融入Laplace谱匹配算法以优化谱匹配的结果。对真实和合成数据的实验表明该方法具有比较高的精度。

一种基于修正的最小生成树及其邻接谱的特征匹配算法

提出一种基于修正的最小生成树及其邻接谱的特征匹配算法.该算法利用两幅图像的特征点分别构造最小生成树,并对最小生成树进行修正,然后对修正的最小生成树的赋权邻接矩阵进行SVD分解,获得点的特征表示,进而利用特征值及特征向量来构造匹配矩阵,实现特征匹配.该算法的优点在于采用图的最小生成树(而不是整个图),可以减少多余信息的干扰,提高匹配精度,实验结果表明,该算法具有较高的匹配精度.

基于谱特征的图像匹配算法

传统基于谱图的图像匹配算法大多利用特征点集中点的位置关系进行匹配,并未充分利用特征点周围的灰度信息,为此,文中提出了一种基于谱特征的图像匹配算法,该算法利用线图谱来反映特征点周围灰度的变化,对特征点周围的邻域点进行分层,并对每层中的点构造线图,通过线图谱获取特征点的谱特征;理论分析表明,该谱特征具有旋转不变性、亮度线性变化不变性及对噪声的较高鲁棒性.最后,利用匈牙利算法求解匹配问题,输出匹配结果.实验结果表明,文中算法具有较高的匹配精度,在待匹配图像间存在较大形变时,也可以获得较好的匹配结果.

基于线图Q-谱的点模式匹配算法

针对大多数谱方法不能够较好地处理不同大小点集匹配的问题,提出了一种基于线图Q-谱的点模式匹配算法.首先,对相关点集构造赋权完全图,再对每个点利用与其关联的前k条最短边来构造线图;然后,根据线图构造无符号Laplacian矩阵,对其进行谱分解,并利用谱分解所获得的特征值(Q-谱)来表示点的特征,通过这些特征计算点之间的匹配概率;最后,通过KM算法来寻找点集之间的最优匹配.实验结果表明,文中算法具有较高的匹配精度,可以处理不同大小点集的匹配问题.

基于局部相对形状上下文与Q-谱的点模式匹配算法

本文提出了一种基于局部相对形状上下文与Q-谱的点模式匹配算法,对每个点构造相应的线图,并对线图的无符号Laplacian矩阵进行谱分解;利用谱分解所获得的特征值(Q-谱)作为点的特征,进而计算点的初始匹配概率;通过定义局部相对形状上下文计算点的相似性距离;将Q-谱方法与局部相对形状上下文结合进行概率松弛迭代获得匹配结果.实验结果表明了本文算法的可行性与有效性.

一种基于矩形的摄像机自标定方法

提出了一种求解摄像机内参数的方法.首先从空间单个矩形的图像获得含参数r的圆环点图像,其中,r为该矩形的长宽比;进而根据圆环点对摄像机内参数约束获得一组非线性方程;通过求解一个次数为3的多项式方程的正根,把非线性方程组转化为线性方程组,从而确定摄像机的内参数.同时,给出了此约束方程组具有惟一解的充要条件.实验结果表明,所给出的方法具有较高的求解精度.

基于一维移动物体的双目装置自标定

给出了平移运动的一维物体所在平面的虚圆点图像及其对摄像机内参数的约束,和约束方程的数值求解方法,从而获得摄像机的内参数.进一步通过恢复空间点在摄像机坐标系中的坐标,求解出双目摄像机之间的方位,即摄像机的外参数.对于一维物体的一般刚体运动,给出了把它转化为平移运动的方法.模拟实验和真实图像实验结果表明该方法具有较高的求解精度,同时也有一定的应用价值.

一种使用TPS变形模型的Laplace谱匹配算法

提出一种基于图的Laplace谱的点模式匹配算法。该方法在每次迭代过程中,利用Laplace矩阵的特征向量和双随机矩阵计算点之间的匹配概率,然后求解已知匹配点之间的TPS(thin plate spline)变换关系,再利用获得的TPS变换参数使待匹配点集相互逼近。随着点集的接近,由Laplace谱分析方法获得的匹配精度也随之提高。对真实和合成数据的实验验证了该方法的有效性。

一种基于平面模板的摄像机自定标方法

给出仿射坐标系下场景中平面与像平面的单应关系、绝对二次曲线及其图像的表示 .通过对场景中一个平面模板获取 3幅图像 (该模板是由含内切圆的等边三角形构成 ) ,利用上述单应关系并结合圆环点对摄像机内参数的约束 ,获得一组线性方程 ,进而确定摄像机的内参数 .实验结果表明 ,所给出的方法切实可行 。

补图为2-点或2-边连通的图的最小特征值(英文)

图的最小特征值定义为图的邻接矩阵的最小特征值,是刻画图结构性质的一个重要代数参数.在所有给定阶数的补图为2-点或2-边连通的图中,刻画了最小特征值达到极小的唯一图,并给出了这类图最小特征值的下界.

三对角线逆M-矩阵

研究同时为三对角线矩阵和逆M 矩阵的一类特殊矩阵 ,称之为三对角线逆M 矩阵。用图论的方法探讨三对角线逆M 矩阵的结构 ;并给出三对角线非负矩阵为逆M 矩阵的充分必要条件。最后 ,我们还证明了三对角线逆M

癌症基因分类的Laplace谱方法

本文尝试着将图的Laplace谱理论应用于癌症基因表达谱数据的分类上.计算出训练集中每个类的均值作为类中心,选出与类中心欧式距离最小的若干样本用laplace矩阵构造完全图,记为代表该类的标准图.用待测样本依次替换标准图中所有的点,将生成的新图与标准图进行特征点匹配,并计算匹配点数总和.将待测样本划分为总匹配点数最多的那个类.通过对白血病两个亚型(ALL与AML)与结肠癌数据进行留一法实验,验证了本文方法的有效性.