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.     

基于权重学习的图像最大权对集胚配模型

在图匹配模型中权重的设置对匹配性能有很大影响,但直接计算的权重往往不符合匹配图像的实际情况。为此,参照二次分配问题的图匹配学习思想,给出一阶和二阶最大权对集模型的权重学习计算方法。一阶最大权对集模型直接采用图像特征点作为图的顶点,而二阶最大权对集模型则采用某些特征点之间的连接边作为顶点,2个模型都可以通过Kuhn—Munkras算法求解。一阶最大权对集模型在本质上等价于二次分配问题的线性情况。在CMUHouse数据库上的图像匹配实验结果表明,二阶最大权对集模型优于一阶最大权对集模型,且两者在学习计算时的性能也优于直接计算的情况。     

蜂窝下含D2D系统基于二部超图的资源分配

针对蜂窝下含D2D系统的资源分配问题,提出一种基于二部超图的资源分配算法。首先,以最大化系统和速率为目标,将该问题建模为一个整数规划问题。为求解该NP-hard问题,相继提出二部超图的概念、二部超图边的感知比较构造法则以及基于二部超图的链路匹配算法。仿真结果表明,与二部图算法相比,所提算法在同等条件下可将系统频谱效率提升40b/s/Hz左右,同时可将系统容量提升0.5倍左右。     

基于加权二部图匹配的中文段落相似度计算

为了改进传统以向量空间模型（VSM）为代表的基于词频统计的方法在中文段落相似度计算时存在的精度不高问题,在基于加权二部图匹配的思想上提出了一种计算中文段落之间相似度的方法。该方法将相似度计算分为段落和句子两个层次,将句子作为简单段落看待,也使用二部图匹配进行相似度计算。首先利用句子主干词汇提取算法来提取句子的主干词汇,将主干词汇作为二部图的顶点,把主干词汇之间的相似度作为二部图顶点之间的权值系数,进行句子相似度的计算。其次,将句子作为加权二部图的顶点,把句子之间的相似度作为二部图顶点之间的权值系数,进行段落之间的相似度计算。实验结果表明,该方法与VSM相比,由于它能准确识别同义词,自动匹配两个在段落中不同位置的相似词语,因而在准确度上有了很大的提高。     

面向性能仿真的非连续微分代数模型的指标分析

针对物理系统性能仿真形成的非连续高指标微分代数模型,提出一种基于加权二部图的指标转换方法．该方法将微分代数系统表示为加权二部图,基于二部图匹配算法可以判定微分代数系统是否为高指标系统．对于高指标系统,采用文中方法可以找出需要求导的最小结构奇异方程子集,以便将高指标系统转换为低指标形式．最后,针对定结构与变结构的非连续微分代数模型给出了相应的指标分析策略．文中策略与相关算法已在基于Modelica语言的建模仿真平台MWorks上实现．     

Three-Dimensional Reconstruction of Points and Lines with Unknown Correspondence across Images

Three-dimensional reconstruction from a set of images is an important and difficult problem in computer vision. In this paper, we address the problem of determining image feature correspondences while simultaneously reconstructing the corresponding 3D features, given the camera poses of disparate monocular views. First, two new affinity measures are presented that capture the degree to which candidate features from different images consistently represent the projection of the same 3D point or 3D line. An affinity measure for point features in two different views is defined with respect to their distance from a hypothetical projected 3D pseudo-intersection point. Similarly, an affinity measure for 2D image line segments across three views is defined with respect to a 3D pseudo-intersection line. These affinity measures provide a foundation for determining unknown correspondences using weighted bipartite graphs representing candidate point and line matches across different images. As a result of this graph representation, a standard graph-theoretic algorithm can provide an optimal, simultaneous matching and triangulation of points across two views, and lines across three views. Experimental results on synthetic and real data demonstrate the effectiveness of the approach.An erratum to this article can be found at     

一种潜在文档相似模型

提出一种潜在文档相似模型（LDSM）,把每对文档看作一个二分图,把文档的潜在主题看作二分图的顶点,用主题问的加权相似度为相应边赋权值,并用二分图的最佳匹配表示文档的相似度。实验结果表明,LDSM的平均查准率和平均查全率都优于用TextTiling和二分图最佳匹配方法构建的文档相似模型。     

3D object retrieval via range image queries in a bag-of-visual-words context

3D object retrieval based on range image queries that represent partial views of real 3D objects is presented. The complete 3D models of the database are described by a set of panoramic views, and a Bag-of-Visual-Words model is built using SIFT features extracted from them. To address the problem of partial matching, we suggest a histogram computation scheme, on the panoramic views, that represents local information by taking into account spatial context. Furthermore, a number of optimization techniques are applied throughout the process for enhancing the retrieval performance. Its superior performance is shown by evaluating it against state-of-the-art methods on standard datasets.     

OM-based video shot retrieval by one-to-one matching

This paper proposes a new approach for shot-based retrieval by optimal matching (OM), which provides an effective mechanism for the similarity measure and ranking of shots by one-to-one matching. In the proposed approach, a weighted bipartite graph is constructed to model the color similarity between two shots. Then OM based on Kuhn–Munkres algorithm is employed to compute the maximum weight of a constructed bipartite graph as the shot similarity value by one-to-one matching among frames. To improve the speed efficiency of OM, two improved algorithms are also proposed: bipartite graph construction based on subshots and bipartite graph construction based on the same number of keyframes. Besides color similarity, motion feature is also employed for shot similarity measure. A motion histogram is constructed for each shot, the motion similarity between two shots is then measured by the intersection of their motion histograms. Finally, the shot similarity is based on the linear combination of color and motion similarity. Experimental results indicate that the proposed approach achieves better performance than other methods in terms of ranking and retrieval capability.

基于分布式图计算的学术论文推荐算法

针对海量论文数据导致的应用效率低下问题,提出一个基于层次混合模型的推荐算法WSVD++。该模型根据学术论文良好的结构特征,构建一个加权的论文二部图模型。首先对论文进行特征提取,按不同特征的权重构建论文的复合关系图;其次对关系图采用一种改进的PPR算法,计算每篇论文的重要程度,依此来对用户—论文关系进行加权;然后在构建好的加权二部图模型上混合SVD++图算法进行推荐。实验结果表明,改善了推荐算法学术论文的推荐效果,并且基于分布式图计算框架GraphX,扩展性好,适合大数据处理。     

面向子流的低延迟数据调度算法

P2P流媒体是分发流媒体数据的高效方式,而数据传输延迟是决定P2P流媒体系统性能的重要参数。在分析"拉"模式数据调度模式传输延迟的基础上,本文在"推"、"拉"混合的调度模式下提出一种新的面向子流的低延迟数据调度算法。首先子流的调度问题被转换成等价的带权二部图匹配问题,其次针对转换后的二部图改进匈牙利算法,提出最小延迟、最大匹配的启发式匹配算法。该算法在保证最大匹配的同时使得每条子流的延迟尽可能地低。模拟实验表明本文的算法能够极大降低数据传输延迟。     

基于赋权二部图的记录簇匹配模型及其算法

通过一组成员记录表示实体时,相似记录匹配问题被扩展为记录簇匹配问题。提出2种记录簇匹配模式,应用赋权二部图理论建立记录簇匹配数学模型,设计记录簇上下界匹配算法。快速推导出记录簇匹配阈值的上下界,以减少记录簇子记录最大权的匹配次数。实验结果证明该算法能提高记录簇匹配精度和计算效率。     

A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms

We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node s and a target set T is specified and the goal is to compute a shortest path from s to a node in T . Our interest in the shortest path problem with many targets stems from its use in weighted bipartite matching algorithms. A weighted bipartite matching in a graph with n nodes on each side reduces to n SSMTSP problems, where the number of targets varies between n and 1 . The SSMTSP problem can be solved by Dijkstra's algorithm. We describe a heuristic that leads to a significant improvement in running time for the weighted matching problem; in our experiments a speed-up by up to a factor of 12 was achieved. We also present a partial analysis that gives some theoretical support for our experimental findings.     

Graph cut based panoramic 3D modeling and ground truth comparison with a mobile platform – The Wägele

Efficient and comfortable acquisition of large 3D scenes is an important topic for many current and future applications in the field of robotics, factory and office visualization, 3DTV and cultural heritage.In this paper we present both an omnidirectional stereo vision approach for 3D modeling based on graph cut techniques and also a new mobile 3D model acquisition platform where it is employed. The platform comprises a panoramic camera and a 2D laser range scanner for self localization by scan matching. 3D models are acquired just by moving the platform around and recording images in regular intervals. Additionally, we concurrently build 3D models using two supplementary laser range scanners. This enables the investigation of the stereo algorithm’s quality by comparing it with the laser scanner based 3D model as ground truth. This offers a more objective point of view on the achieved 3D model quality.     

面向云计算的期限约束的MapReduce作业调度方法

提出一种面向异构云计算环境的截止时间约束的MapReduce作业调度方法。使用加权偶图建模MapReduce作业调度问题,将Map任务及Reduce任务与资源槽分为2个节点集合,连接2个节点集合的边的权重为任务在资源槽上的执行时间。进而,使用整数线性规划求解最小加权偶图匹配,从而得到任务到资源槽的调度方案。本文考虑了云计算环境下异构节点任务处理时间的差异性,在线动态评估和调整任务的截止时间,从而提升了MapReduce作业处理的性能。实验结果表明,所提出的方法缩短了作业数据访问的时间,最小化了截止时间冲突的作业数量。     

Efficient 3D reflection symmetry detection: A view-based approach

Symmetries exist in many 3D models while efficiently finding their symmetry planes is important and useful for many related applications. This paper presents a simple and efficient view-based reflection symmetry detection method based on the viewpoint entropy features of a set of sample views of a 3D model. Before symmetry detection, we align the 3D model based on the Continuous Principal Component Analysis (CPCA) method. To avoid the high computational load resulting from a directly combinatorial matching among the sample views, we develop a fast symmetry plane detection method by first generating a candidate symmetry plane based on a matching pair of sample views and then verifying whether the number of remaining matching pairs is within a minimum number. Experimental results and two related applications demonstrate better accuracy, efficiency, robustness and versatility of our algorithm than state-of-the-art approaches.     

MDSM: Microarray database schema matching using the Hungarian method

Current microarray databases use different terminologies and structures and thereby limit the sharing of data and collating of results between laboratories. Consequently, an effective integrated microarray data model is required. One important process to develop such an integrated database is schema matching. In this paper, we propose an effective schema matching approach called MDSM, to syntactically and semantically map attributes of different microarray schemas. The contribution from this work will be used later to create microarray global schemas. Since microarray data is complex, we use microarray ontology to improve the measuring accuracy of the similarity between attributes. The similarity relations can be represented as weighted bipartite graphs. We determine the best schema matching by computing the optimal matching in a bipartite graph using the Hungarian optimisation method. Experimental results show that our schema matching approach is effective and flexible to use in different kinds of database models such as; database schema, XML schema, and web site map. Finally, a case study on an existing public microarray schema is carried out using the proposed method.     

三维模型的空间匹配与拼接

为获得敦煌莫高窟第172窟的全景三维模型,实现文化遗产数字化保护,提出一种三维模型的空间匹配与拼接方法。首先通过基于四目立体视觉系统的复杂场景三维重建方法,获取单一场景的三维模型;然后以场景真实三维点云数据的对应图像坐标为约束条件,进行高精度特征点匹配;最后以两对同名点在相邻两场景中的空间距离应该一致为条件,保留匹配精度高的点,用于计算旋转矩阵和平移矩阵,进行三维模型间的空间拼接。实验结果表明:与传统拼接方法相比,本文的模型拼接处无明显错位现象,视觉效果更好,传统方法与本方法的匹配误差分别为0.008 2和0.001 6,拼接精度得到显著改善。