基于加权相邻关系的形状轮廓点匹配

轮廓点匹配是形状匹配的一种典型方法。在各种形变情况下,形状轮廓点的相邻关系往往比其他全局关系更稳定。本文在保持局部邻居结构的点匹配算法基础上,引入了邻居的权的概念。首先基于点到邻居的距离为每个点的邻居关系赋权,然后结合形状上下文距离把点匹配问题转化为有向属性关系图匹配问题,用松弛迭代法求解。引入邻居关系系的权,使匹配不仅保持邻居集的一致性,同时还保持邻居之间的距离相对关系。实验证明,本文方法能够提高匹配效果,加快匹配算法收敛速度。     

耳廓点云形状特征匹配的路径跟随算法

路径跟随算法结合凸松弛方法与凹松弛方法,通过跟随凸凹问题的解路径,近似地求解图匹配问题,具有较高的匹配精度.将路径跟随算法用于耳廓特征图的匹配问题:首先,基于PCA方法构造耳廓点云的显著性关键点集合;然后,采用乘积型参数域上的单值二次曲面方法拟合关键点邻域内的点集,并将曲面的局部形状特征定义为耳廓的局部形状相似测度;第三,对关键点集合进行Delaunay三角剖分,得到关键点集合在三维空间内的拓扑结构图,并定义关键点图的整体结构差异测度;最后,记耳廓关键点图的组合差异测度为关键点图的整体结构差异测度与关键点上的局部形状相似测度的线性组合,并基于路径跟随算法快速求解关键点图之间的精确匹配.相关实验结果表明:与其他相关算法相比,该算法具有较高的匹配效率和匹配精度.     

基于最大权团的曲面粗匹配算法

提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.     

Deformable 3D Shape Registration Based on Local Similarity Transforms

In this paper, a new method for deformable 3D shape registration is proposed. The algorithm computes shape transitions based on local similarity transforms which allows to model not only as‐rigid‐as‐possible deformations but also local and global scale. We formulate an ordinary differential equation (ODE) which describes the transition of a source shape towards a target shape. We assume that both shapes are roughly pre‐aligned (e.g., frames of a motion sequence). The ODE consists of two terms. The first one causes the deformation by pulling the source shape points towards corresponding points on the target shape. Initial correspondences are estimated by closest‐point search and then refined by an efficient smoothing scheme. The second term regularizes the deformation by drawing the points towards locally defined rest positions. These are given by the optimal similarity transform which matches the initial (undeformed) neighborhood of a source point to its current (deformed) neighborhood. The proposed ODE allows for a very efficient explicit numerical integration. This avoids the repeated solution of large linear systems usually done when solving the registration problem within general‐purpose non‐linear optimization frameworks. We experimentally validate the proposed method on a variety of real data and perform a comparison with several state‐of‐the‐art approaches.     

Structure-oriented contour representation and matching for engineering shapes

Conventional shape matching for engineering models primarily considers rigid shape similarity. They do not seek global shape similarity while considering large local deformations. However, engineering models created by some parametric-based design can involve large parametric changes. As a result, they do not share similarity in their global shape. Hence our goal is to develop shape representations for global matching of part models that can have large dissimilarity through stretching and/or bending.This paper presents a strategy of an integrated shape matching for contours of engineering drawings inspired by the divide-and-conquer paradigm. The original shape is decoupled into two levels of shape representations namely, higher-level structure and lower-level geometry. The higher-level structure matching is then achieved driven by optimal integrated solutions from matching of lower-level local geometry. Feature points are first extracted using curve evolution to attain the two levels of representations. In order to suit engineering semantics, a new significance function for a point is defined to suppress small features using discrete curve evolution. To conduct the integrated shape matching, a mechanism of using lookup tables is employed to associate these two levels of representations. Dynamic Time Warping and Elastic Matching are employed at different levels of shape representations in order to achieve the optimal integration.To demonstrate the advantages of the proposed work for engineering shapes, experiments for contour evolution, feature point registration, and shape-based similarity for retrieval are conducted. They are also compared with the existing methods. The experimental results show that the structure-oriented contour representation and matching are more meaningful and consistent from an engineering perspective.     

混合算法的邻域结构变更研究及在排样问题上的应用

本文研究了全局搜索算法和局部搜索算法的混合机制,设计了基于邻域搜索和遗传算法的混合搜索算法。该算法结合了遗传算法的全局搜索特性和邻域局部贪婪搜索特性;在分析排样问题碰靠过程特征的基础上,构建了排样问题邻域假设,当邻域假设满足时,遗传算法+邻域搜索能很好发挥作用;当不能判断邻域结构是否满足邻域假设时,提出了建立遗传算法+匹配变邻域的搜索算法,该算法兼顾了组合优化中邻域搜索的局部搜索无效的情况,实现了匹配的变邻域混合算法在排样优化问题中的应用。实例结果标明,排样图形不一样,其求解难度不一样,该算法均搜索到了更好的排样模式,验证了算法的有效性。     

采用树表示的全局最优形状匹配算法

提出一种全局优化算法，用于相似不变地在一场景中匹配一个形状。该算法采用支撑树来表示形状，匹配问题被转化成在目标点集中定位这棵树的问题。通过最小化边的空间变换同一个全局空间变换之间的差别，树的每条边的空间变换被强制是一致的。目标函数归结为一个关于边匹配变量的凹二次函数。该函数具有低秩Hessian矩阵，可以通过分支定界法快速地解出。还提出一种新颖的求下界的方案，它可以通过动态规划高效地解出。实验结果表明，所提算法相比主流算法有更好的鲁棒性，特别对于两点集只有部分重叠的情形。     

Closed‐form Blending of Local Symmetries

We present a closed‐form solution for the symmetrization problem, solving for the optimal deformation that reconciles a set of local bilateral symmetries. Given as input a set of point‐pairs which should be symmetric, we first compute for each local neighborhood a transformation which would produce an approximate bilateral symmetry. We then solve for a single global symmetry which includes all of these local symmetries, while minimizing the deformation within each local neighborhood. Our main motivation is the symmetrization of digitized fossils, which are often deformed by a combination of compression and bending. In addition, we use the technique to symmetrize articulated models.     

Matching point features under small nonrigid motion

This paper describes a method for matching point features between images of objects that have undergone small nonrigid motion. Feature points are assumed to be available and, given a properly extracted set of feature points, a robust matching is established under the condition that the local nonrigid motion of each point is restricted to a circle of radius δ, where δ is not too large. This is in contrast to other techniques for point matching which assume either rigid motion or nonrigid motion of a known kind. The point matching problem is viewed in terms of weighted bipartite graph matching. In order to account for the possibility that the feature selector can be imprecise, we incorporate a greedy matching strategy with the weighted graph matching algorithm. Our algorithm is robust and insensitive to noise and missing features. The resulting matching can be used with image warping or other techniques for nonrigid motion analysis, image subtraction, etc. We present our experimental results on sequences of mammograms, images of a deformable clay object and satellite cloud images. In the first two cases we provide quantitative comparison with known ground truth.     

Cellular matrix model for parallel combinatorial optimization algorithms in Euclidean plane

We propose a parallel computation model, called cellular matrix model (CMM), to address large-size Euclidean graph matching problems in the plane. The parallel computation takes place by partitioning the plane into a regular grid of cells, each cell being affected to a single processor. Each processor operates on local data, starting from its cell location and extending its search to the neighborhood cells in a spiral search way. In order to deal with large-size problems, memory size and processor number are fixed as O(N), where N is the problem size. Then one key point is that closest point searching in the plane is performed in O(1) expected time for uniform or bounded distribution, for each processor independently. We define a generic loop that models the parallel projection between graphs and their matching, as executed by the many cells at a given level of computation granularity. To illustrate its efficacy and versatility, we apply the CMM, on GPU platforms, to two problems in image processing: superpixel segmentation and stereo matching energy minimization. Firstly, we propose an extended version of the well-known SLIC superpixel segmentation algorithm, which we call SPASM algorithm, by using a parallel 2D self-organizing map instead of k-means algorithm. Secondly, we investigate the idea of distributed variable neighborhood search, and propose a parallel search heuristic, called distributed local search (DLS), for global energy minimization of stereo matching problem. We evaluate the approach with regards to the state-of-the-art graph cut and belief propagation algorithms. For each problem, we argue that the parallel GPU implementation provides new competitive quality/time trade-offs, with substantial acceleration factors as the problem size increases.     

基于形状先验和图割的彩色图像分割

基于图割理论的图像分割方法在二值标号问题中可以获取全局最优解,而在多标号问题中可以获取带有很强特征的局部最优解。但对于含有噪声或遮挡物等复杂的图像,分割结果不完整,效果并不令人满意,提出了一种基于形状先验和图割的图像分割方法。以图割算法为基础,加入形状先验知识,使该算法包含更多约束信息,从而限制感兴趣区域的搜寻空间,能够更好地分割出完整的目标,增加了算法的精确度。针对形状的仿射变换,运用特征匹配算法进行处理,使算法更加具有灵活性,能够应对不同类型的情况。实验表明了该算法的有效性。     

遗传算法的全局动力学形态分析

目前，对遗传算法的运行机理分析大都集中在算法的极限收敛性等问题，对算法的全局动力学形态研究较少．从一个具有代表性的、简化的2—bit问题入手，可以对遗传算法中常用的各种进化算子及其组合进行形式化描述，从而全面分析GA的全局动力学形态．针对各种参数的选取，分别建立了4个数学模型．通过分析这些模型中各个不动点的吸引性，揭示出不同进化算子对动力学形态的影响．对于这个问题，证明了算法的全局收敛性．并指出，当存在两个被此竞争的局部极值点时，模型中只有两个吸引点和一个鞍点(或排斥点)，不存在其他的不动点或周期点．算法的收敛结果完全由初始条件处于状态空间中的位置所决定，相应的收敛区域的比例完全由模型的参数决定．