为解决点刻式直接零件标志(Direct part mark,DPM)码基本单元分割困难、区域定位欠精确等问题,提出使用超像素分割和谱聚类相结合的算法,对含有DPM区域的图像进行初步分割和精确定位.首先为提高超像素分割的准确、快速和完整性,本文利...为解决点刻式直接零件标志(Direct part mark,DPM)码基本单元分割困难、区域定位欠精确等问题,提出使用超像素分割和谱聚类相结合的算法,对含有DPM区域的图像进行初步分割和精确定位.首先为提高超像素分割的准确、快速和完整性,本文利用近邻传播聚类思想实现自动聚类得到超像素区域,并引入边缘置信度调整超像素边缘,形成自适应边缘简单线性迭代聚类(Adaptive edge simple linear iterative clustering,AE-SLIC)算法.该算法改进了简单线性迭代聚类(Simple linear iterative clustering,SLIC)超像素分割算法存在的未明确界定超像素区域边缘信息和分割数目无法自适应确定等问题;其次,将超像素作为谱聚类中图的顶点进行二次聚类,DPM区域内超像素因相似度高而被聚集为一类,从而完成点刻式DPM区域的精确定位.经实验测试和分析,本文算法得到的超像素分割结果在完整性、运算复杂度等方面优于常见的超像素分割算法.与基于像素点运算的传统定位算法相比,本文算法具有良好的实时性、定位准确率和鲁棒性.展开更多
传统流形学习算法虽然是一种常用的有效降维方法,但由于其自身计算结构的限制,往往存在数据分析不足和计算时间较长等问题.为此提出一种基于谱聚类的流形学习算法(spectralclustering locally linear embedding,SCLLE),并对其机理以及...传统流形学习算法虽然是一种常用的有效降维方法,但由于其自身计算结构的限制,往往存在数据分析不足和计算时间较长等问题.为此提出一种基于谱聚类的流形学习算法(spectralclustering locally linear embedding,SCLLE),并对其机理以及优点给予了实例证明.在UCI和NCBI数据集上的实验结果表明,该算法具有较好的识别效果和计算性能.展开更多
Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications,such as simplification of social networks,least squares problems,and numerical solution of symmetric posit...Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications,such as simplification of social networks,least squares problems,and numerical solution of symmetric positive definite linear systems.In this paper,inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit(OMP),we introduce a deterministic,greedy edge selection algorithm,which is called the universal greedy approach(UGA)for the graph sparsification problem.For a general spectral sparsification problem,e.g.,the positive subset selection problem from a set of m vectors in R n,we propose a nonnegative UGA algorithm which needs O(mn^(2)+n^(3)/ϵ^(2))time to find a 1+ϵ/β/1-ϵ/β-spectral sparsifier with positive coefficients with sparsity at most[n/ϵ^(2)],where β is the ratio between the smallest length and largest length of the vectors.The convergence of the nonnegative UGA algorithm is established.For the graph sparsification problem,another UGA algorithm is proposed which can output a 1+O(ϵ)/1-O(ϵ)-spectral sparsifier with[n/ϵ^(2)]edges in O(m+n^(2)/ϵ^(2))time from a graph with m edges and n vertices under some mild assumptions.This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for.The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear,i.e.O(m^(1+o(1)))for some o(1)=O((log log(m))^(2/3)/log^(1/3)(m)).Finally,extensive experimental results,including applications to graph clustering and least squares regression,show the effectiveness of proposed approaches.展开更多
文摘为解决点刻式直接零件标志(Direct part mark,DPM)码基本单元分割困难、区域定位欠精确等问题,提出使用超像素分割和谱聚类相结合的算法,对含有DPM区域的图像进行初步分割和精确定位.首先为提高超像素分割的准确、快速和完整性,本文利用近邻传播聚类思想实现自动聚类得到超像素区域,并引入边缘置信度调整超像素边缘,形成自适应边缘简单线性迭代聚类(Adaptive edge simple linear iterative clustering,AE-SLIC)算法.该算法改进了简单线性迭代聚类(Simple linear iterative clustering,SLIC)超像素分割算法存在的未明确界定超像素区域边缘信息和分割数目无法自适应确定等问题;其次,将超像素作为谱聚类中图的顶点进行二次聚类,DPM区域内超像素因相似度高而被聚集为一类,从而完成点刻式DPM区域的精确定位.经实验测试和分析,本文算法得到的超像素分割结果在完整性、运算复杂度等方面优于常见的超像素分割算法.与基于像素点运算的传统定位算法相比,本文算法具有良好的实时性、定位准确率和鲁棒性.
文摘传统流形学习算法虽然是一种常用的有效降维方法,但由于其自身计算结构的限制,往往存在数据分析不足和计算时间较长等问题.为此提出一种基于谱聚类的流形学习算法(spectralclustering locally linear embedding,SCLLE),并对其机理以及优点给予了实例证明.在UCI和NCBI数据集上的实验结果表明,该算法具有较好的识别效果和计算性能.
基金supported by NSFC grant(Nos.12001026,12071019)supported by the National Science Fund for Distinguished Young Scholars grant(No.12025108)+1 种基金Beijing Natural Science Foundation(No.Z180002)NSFC grant(Nos.12021001,11688101).
文摘Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications,such as simplification of social networks,least squares problems,and numerical solution of symmetric positive definite linear systems.In this paper,inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit(OMP),we introduce a deterministic,greedy edge selection algorithm,which is called the universal greedy approach(UGA)for the graph sparsification problem.For a general spectral sparsification problem,e.g.,the positive subset selection problem from a set of m vectors in R n,we propose a nonnegative UGA algorithm which needs O(mn^(2)+n^(3)/ϵ^(2))time to find a 1+ϵ/β/1-ϵ/β-spectral sparsifier with positive coefficients with sparsity at most[n/ϵ^(2)],where β is the ratio between the smallest length and largest length of the vectors.The convergence of the nonnegative UGA algorithm is established.For the graph sparsification problem,another UGA algorithm is proposed which can output a 1+O(ϵ)/1-O(ϵ)-spectral sparsifier with[n/ϵ^(2)]edges in O(m+n^(2)/ϵ^(2))time from a graph with m edges and n vertices under some mild assumptions.This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for.The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear,i.e.O(m^(1+o(1)))for some o(1)=O((log log(m))^(2/3)/log^(1/3)(m)).Finally,extensive experimental results,including applications to graph clustering and least squares regression,show the effectiveness of proposed approaches.
