图模型匹配:一种新的凹松弛函数及算法

将问题中的置换矩阵放松为双随机矩阵是近年来近似图匹配算法的一个重要发展方向. 它的本质在于将离散的图匹配问题转换成一个连续优化问题,而一般来讲, 相对于离散优化,连续优化问题的近似求解将更为容易. 但随之带来的一个问题是如何有效地将连续优化得到的双随机矩阵重新映射回一个置换矩阵. 最近文献中提出了一种针对于无向无自环图的凹松弛(Concave relaxation)函数,使得算法中的双随机矩阵可以平滑地收敛到一个置换矩阵, 并得到优异的匹配精度.但除了无向且无自环图,文献中还没有针对其他类型图模型的凹松弛函数. 本文提出一种针对于有向无自环图匹配问题的凹松弛函数, 并在此基础上给出一种图匹配算法.大量对比实验验证了本文提出模型及算法的有效性.     

基于Hessian图正则稀疏NMF的高光谱解混

基于非负矩阵分解(Nonnegative Matrix Factorization, NMF)的高光谱解混(Hyperspectral Unmixing,HU)方法引起了大家的关注,因为可以将一个非负高光谱图像(Hyperspectral Imagery, HSI)数据矩阵分解为两个非负矩阵的乘积,分别对应于端元矩阵和丰度系数矩阵。目前,图约束的NMF算法已经被证明对高光谱解混是有效的,因为它们可以捕获HSI的几何特性。为了挖掘数据在混合过程中的几何结构和稀疏性,提出了一种稀疏的Hessian图正则化NMF(SHGNMF)算法。SHGNMF算法是将丰度矩阵的L1/2正则化器和Hessian图正则化项都添加到每个NMF模型中,同时采用乘法更新规则。最后用模拟数据和真实数据进行实验,验证了所提出的SHGNMF算法相对于其他NMF算法的优越性。     

鲁棒结构正则化非负矩阵分解

现有的非负矩阵分解方法既忽略数据的非局部结构,又难以有效应对噪声和野值点。为了解决上述问题,提出一种新的用于聚类的鲁棒结构正则化非负矩阵分解算法。所提出的算法分别构建一个近邻图和一个最大熵图描述数据的局部结构和非局部结构,并使用L_2,1范数代价函数尝试解决噪声问题,从而学习到鲁棒具有判别力的表征。给出一个最优的迭代算法求解两个非负因子,该优化算法的收敛性已被理论和实验证明。在七个图像数据集上的聚类实验结果表明,所提出的算法在无噪声和有噪声情况下聚类均优于其他主流方法。     

面向卷积混叠环境下的盲源分离新方法

卷积混叠环境下的盲源分离(Blind source separation, BSS)是一个极具挑战性和实际意义的问题.本文在独立分量分析框架下,建立非负矩阵分解(Nonnegative matrix factorization, NMF)模型,设计新的优化目标函数,通过严格的数学理论推导,得到新的模型参数更新规则;并对解混叠矩阵进行标准化处理,避免幅度歧义性问题;在源信号的重构阶段,通过实时更新非负矩阵分解模型参数,避免源信号的排序歧义性问题.实验结果验证了所提算法在分离中英文语音混叠信号、音乐混叠信号时的有效性和优越性.     

计算机视觉中图匹配研究进展: 从二图匹配迈向多图匹配

图匹配试图求解二图或多图之间节点的对应关系.在图像图形领域,图匹配是一个历久弥新的基础性问题.从优化的角度来看,图匹配问题是一个组合优化问题,且在一般情形下具有非确定性多项式复杂程度(non-deter-ministic polynomial, NP)难度的性质.在过去数十年间,出现了大量求解二图匹配的近似算法,并在各个领域得到了较为广泛的应用.然而,受限于优化问题本身的理论困难和实际应用中数据质量的种种限制,各二图匹配算法在匹配精度上的性能日益趋近饱和.相比之下,由于引入了更多信息且往往更符合实际问题的设定,多图的协同匹配则逐渐成为了一个新兴且重要的研究方向.本文首先介绍了经典的二图匹配方法,随后着重介绍近年来多图匹配方法的最新进展和相关工作.最后,本文讨论了图匹配未来的发展.     

使用社区结构信息的子图匹配算法优化方法*

子图匹配是图数据查询处理技术中的一个重要研究问题。针对现有子图匹配算法运行效率不高且缺乏通用优化方法的现状,提出一种基于社区结构的子图匹配算法优化方法(community structure based subgraph matching optimization method,CSO)。首先,提出两种优化策略,即解析模式图信息以减少子图匹配过程的计算量,以及利用社区结构信息在子图匹配过程中进行剪枝;然后,结合上述两种优化策略提出基于社区结构的子图匹配算法优化方法,并进行了理论分析。真实数据集和合成数据集上的大量实验结果表明,CSO方法能有效减少子图匹配算法的时间开销。同时,不同规模数据集上的实验结果验证了CSO方法良好的可扩展性。     

基于分割Bregman方法的非负稀疏图构建算法

在基于图的机器学习算法中,构造一个能较好反映数据内在结构信息的图尤为重要.文中提出一种基于分割Bregman方法的非负稀疏图构建算法.该算法通过使用分割Bregman方法求解稀疏表示优化问题的一个等价形式,以此得到一个能将每个数据样本表示成其他样本的非负线性组合的图的边权矩阵.算法构建的稀疏图能较好描述数据之间存在的线性关系.在半监督学习的框架下进行测试的实验表明,文中算法能较好反映数据内部潜在的结构信息.     

基于非精确图匹配的CAD模型搜索方法

为了弥补现有的三维CAD模型搜索方法难以搜索到不同近似程度的相似模型的缺陷,提出一种基于面属性化邻接图非精确匹配的CAD模型搜索方法.首先提取CAD模型中的B-rep信息将CAD模型转化为面属性化邻接图;然后计算目标模型与被搜索模型的面属性化邻接图之间的顶点相容程度矩阵和边相容程度矩阵,并由此建立2个模型相似程度的度量作为选择不同顶点匹配矩阵M的优化目标函数;在对匹配矩阵M进行连续化松弛后,运用Sinkhorn行列交替规范化方法求解匹配优化问题.实验结果表明,采用该方法能够搜索到不同近似程度的相似模型;并且由于避免了具有NP复杂性的精确图匹配过程,检索效率也能满足实际要求.     

稀疏约束图正则非负矩阵分解

非负矩阵分解(NMF)是在矩阵非负约束下的一种局部特征提取算法。为了提高识别率,提出了稀疏约束图正则非负矩阵分解方法。该方法不仅考虑数据的几何信息,而且对系数矩阵进行稀疏约束,并将它们整合于单个目标函数中。构造了一个有效的乘积更新算法,并且在理论上证明了该算法的收敛性。在ORL和MIT-CBCL人脸数据库上的实验表明了该算法的有效性。     

非负局部约束低秩子空间聚类算法

在低秩表示算法的基础上,提出了一个新模型。新模型构建了揭示数据内在特征联系的亲和度图以实现聚类任务。首先,根据矩阵分解原理对原始数据重新生成数据字典,在算法初始输入时筛除部分噪声。其次,利用数据间的稀疏性加强局部约束,为给定的数据向量构建非负低秩亲和度图。亲和度图中边的权重由非负低秩稀疏系数矩阵获得,系数矩阵通过每个数据样本作为其他数据样本的线性组合完成构建,如此获得的亲和度图显示了数据的子空间结构,同时表现局部线性结构。与现存的子空间算法相比,非负局部约束低秩子空间算法在聚类效果上有明显的提升。     

Partial retrieval of CAD models based on the gradient flows in Lie group

Based on the gradient flows in Lie group, a partial retrieval approach for CAD models is presented in this paper. First, a representation of the face Attributed Relational Graph (ARG) for a CAD model is created from its B-rep model and thus partial retrieval is converted to a subgraph matching problem. Then, an optimization method is adopted to solve the matching problem, where the optimization variable is the vertex mapping and the objective function is the measurement of compatibility between the mapped vertices and between the mapped edges. Different from most previously proposed methods, a homogeneous transformation matrix is introduced to represent the vertex mapping in subgraph matching, whose translational sub-matrix gives the vertex selection in the larger graph and whose orthogonal sub-matrix presents the vertex permutation for the same-sized mapping from the selected vertices to the smaller graph's vertices. Finally, a gradient flow method is developed to search for optimal matching matrix in Special Euclidean group SE(n). Here, a penalty approach is used to handle the constraints on the elements of the matching matrix, which leads its orthogonal part to be a permutation matrix and its translational part to have different integer elements. Experimental results show that it is a promising method to support the partial retrieval of CAD models.     

A dynamical systems approach to weighted graph matching

Graph matching is a fundamental problem that arises frequently in the areas of distributed control, computer vision, and facility allocation. In this paper, we consider the optimal graph matching problem for weighted graphs, which is computationally challenging due the combinatorial nature of the set of permutations. Contrary to optimization-based relaxations to this problem, in this paper we develop a novel relaxation by constructing dynamical systems on the manifold of orthogonal matrices. In particular, since permutation matrices are orthogonal matrices with nonnegative elements, we define two gradient flows in the space of orthogonal matrices. The first minimizes the cost of weighted graph matching over orthogonal matrices, whereas the second minimizes the distance of an orthogonal matrix from the finite set of all permutations. The combination of the two dynamical systems converges to a permutation matrix, which provides a suboptimal solution to the weighted graph matching problem. Finally, our approach is shown to be promising by illustrating it on nontrivial problems.     

Blind separation of positive sources by globally convergent gradient search

The instantaneous noise-free linear mixing model in independent component analysis is largely a solved problem under the usual assumption of independent nongaussian sources and full column rank mixing matrix. However, with some prior information on the sources, like positivity, new analysis and perhaps simplified solution methods may yet become possible. In this letter, we consider the task of independent component analysis when the independent sources are known to be nonnegative and well grounded, which means that they have a nonzero pdf in the region of zero. It can be shown that in this case, the solution method is basically very simple: an orthogonal rotation of the whitened observation vector into nonnegative outputs will give a positive permutation of the original sources. We propose a cost function whose minimum coincides with nonnegativity and derive the gradient algorithm under the whitening constraint, under which the separating matrix is orthogonal. We further prove that in the Stiefel manifold of orthogonal matrices, the cost function is a Lyapunov function for the matrix gradient flow, implying global convergence. Thus, this algorithm is guaranteed to find the nonnegative well-grounded independent sources. The analysis is complemented by a numerical simulation, which illustrates the algorithm.     

基于Givens变换矩阵的时间结构信号盲源分离新算法

对于时间结构信号的盲源分离(Blind Source Separation,BSS),独立成分分析(Independent Component Analysis,ICA)是十分有效的方法。在对观测信号白化处理后,ICA的关键是寻找去除高阶相关性的正交分离矩阵。鉴于任意维数正交矩阵可以表示为Givens变换矩阵的乘积,提出了一种新的时间结构信号盲源分离算法。首先,利用Givens变换矩阵参数化表示正交分离矩阵,减少了要估计参数的个数;其次,以多步时延协方差矩阵的联合近似对角化为目标函数,将盲源分离问题转化为无约束优化问题,并利用拟牛顿法中的BFGS算法对Givens变换矩阵中的参数进行估计,得到分离矩阵;最后,以实际的混合语音信号分离做仿真实验,验证了该算法对时间结构信号的盲源分离是有效的。     

一种半监督机器学习的EM算法改进方法

EM(Expectation Maximization)算法是含有隐变量(latent variable)的概率参数模型最大似然估计、极大后验概率估计最有效的算法,但很容易进入局部最优现象,对此提出基于半监督机器学习机制的EM算法.本文方法是在最大似然函数中加入惩罚最小二乘因子,同时引入非负约束作为先验信息,结合半监督机器学习方法,将EM算法改进转化为最小化求解问题,再采用最大似然方法求解EM模型,有效估计了混合矩阵和高斯混合模型参数,实现EM算法的改进.仿真结果表明,该方法能够很好地解决了EM算法容易局部最优化问题.     

基于鱼群算法的高光谱图像稀疏分解研究

研究高光谱图像的稀疏分解问题,能够降低高光谱图像的数据量,便于后续处理,但传统正交匹配追踪算法的计算复杂度高、不能满足实时处理要求。针对上述问题,提出了一种利用人工鱼群算法实现高光谱图像稀疏分解的算法。算法采用人工鱼群自上而下的寻优模式,通过鱼群中各个体的局部寻优,实现全局最优值在群体中凸显出来的目的,以人工鱼群的更新过程对正交匹配追踪算法的匹配过程进行改进,完成稀疏分解。实验结果表明,与正交匹配追踪算法相比,所提算法计算复杂度低,计算效率提高15倍,且能够提高重构图像的峰值信噪比,充分说明改进算法能够满足实时性要求,更有利于实现高光谱图像的稀疏分解。     

稀疏性正则化非负矩阵分解的在线学习方法

针对非负矩阵分解效率低的不足,提出一种基于在线学习的稀疏性非负矩阵分解的快速方法.通过对目标函数添加正则化项来控制分解后系数矩阵的稀疏性,将问题转化成稀疏表示的字典学习问题,利用在线字典学习算法求解目标函数,并对迭代过程的矩阵更新进行转换,采取块坐标下降法进行矩阵更新,提高算法收敛速度.实验结果表明,该方法在有效保持图像特征信息的同时,运行效率得到提高.     

不确定规划中一种观察信息高效约简算法

在不确定规划中,可通过观察周围的信息来区分多个状态,但周围的观察信息较多,因此如何从大量的观察信息中筛选必须的信息非常重要。以往算法是在直接搜索过程中增加一些剪枝条件来达到优化的目的,存在一定的局限性。在对观察信息约简研究中,为提高搜索效率,设计一种高效的不确定规划中观察信息约筒算法。该算法将规划问题转化为求解O—l矩阵的覆盖问题,使用数据结构十字链表来表示O-1矩阵,通过维护十字链表并采用启发式函数来加速求解一个最小观察变量集。实验结果表明,该算法不仅能够找最小观察变量集,而且运行速度超过同类算法。     

基于势函数与压缩感知的欠定盲源分离

传统的基于K均值聚类算法及最小路径法的欠定盲源分离两步法存在K值难以确定,对初始值敏感,噪声和奇异点难以排除以及相对缺乏理论依据等诸多不足,针对以上问题,提出了基于势函数及压缩感知理论的新型两步算法。该算法首先利用多峰值粒子群寻优算法改进的势函数法来估计混合矩阵,然后利用估计矩阵来构建传感矩阵,并将基于正交匹配追踪的压缩感知算法引入欠定盲源分离过程中,最终实现源信号的重构。仿真实验结果表明,混合矩阵最高估计精度达到99.13%,重构信号干扰比均高于10dB,很好的满足了重构精度的要求,验证了本文算法的有效性。所提算法对一维混合信号的欠定盲源分离具有良好的普适性和较高的准确率。