A Path Following Algorithm for the Graph Matching Problem

We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art.     

Decision feedback data detection in frequency domain for single carrier cyclic prefix assisted CDMA systems: A sequential quadratic programming approach

This paper proposes a frequency domain decision feedback data receiver for the uplink transmission of broadband single carrier cyclic prefix-assisted CDMA systems. The optimum data detection problem based on the maximal-likelihood criteria for this system is addressed as a combinatorial optimization problem. A sequential quadratic programming approach is proposed to solve this problem. The parallel gradient projection method and projected successive over relaxation algorithm are proposed to solve the sequential quadratic programming problem, which corresponds to low-complexity nonlinear parallel and successive interference cancellation schemes in frequency domain. The convergence properties and the complexities of these methods are analyzed and compared with conventional methods. The simulation results show that, with a few iterations, the proposed scheme gives near single user performance even for fully loaded systems.     

考虑多编组站协调分工的枢纽重空车流组织优化

研究一类考虑多编组站协调分工的枢纽重空车流组织优化问题.基于枢纽内各编组站到达、解体、集结、编组、发车及转站能力限制,以重空车流进站走行、出站走行、转站走行、解体及集结总费用最小化为目标构建数学模型.鉴于传统算法求解大规模线性规划效率低下的缺陷,设计两阶段综合求解策略,根据到发约束组生成列车-编组站匹配方案,利用解集编约束组对匹配方案进行初次调整,再利用转站约束对匹配方案进行二次调整,从而得到列车-编组站初始匹配方案集合.在此基础上,对列车-编组站匹配方案进行编码,设置优选因子并据此从初始匹配方案集合中筛选出优选方案集,给出嵌入替换-自变异-交互更新的异步循环启发式,完成对优选方案集的群体迭代寻优.最后通过设计实验场景对模型的准确性以及所提方法的有效性进行验证.     

用于特征点配准的快速聚类凸集投影算法

提出一种用于特征点配准的快速聚类凸集投影算法. 该算法首先将模板点集和目标点集的配准问题通过聚类转化为相应类集合的配准问题，降低了算法的计算量；进而采用基于二次规划的凸集投影来求解类配准问题，避免了序贯凸集投影算法由于交替行列投影而引起的积累误差. 仿真表明，相对于现有的特征点配准算法，本文算法的配准精度和计算量均有所改善.     

Heuristics for cartographic label placement problems

The cartographic label placement problem is an important task in automated cartography and Geographical Information Systems. Positioning the texts requires that overlap among texts should be avoided, that cartographic conventions and preference should be obeyed. This paper examines the point-feature cartographic label placement problem (PFCLP) as an optimization problem. We formulate the PFCLP considering the minimization of existing overlaps and labeling of all points on a map. This objective improves legibility when all points must be placed even if overlaps are inevitable. A new mathematical formulation of binary integer linear programming that allows labeling of all points is presented, followed by some Lagrangean relaxation heuristics. The computational tests considered instances proposed in the literature up to 1000 points, and the relaxations provided good lower and upper bounds.     

An encoding scheme based on fractional number for querying and updating XML data

In order to facilitate the XML query processing, several labeling schemes have been proposed to directly determine the structural relationships between two arbitrary XML nodes without accessing the original XML documents. However, the existing XML labeling schemes have to re-label the pre-existing nodes or re-calculate the label values when a new node is inserted into the XML document during an update process. In this paper, we devise a novel encoding scheme based on the fractional number to encode the labels of the XML nodes. Moreover, we propose a mapping method to convert our proposed fractional number based encoding scheme to bit string based encoding scheme with the intention to minimize the label size and save the storage space. By applying our proposed bit string encoding scheme to the range-based labeling scheme and the prefix labeling scheme, the process of re-labeling the pre-existing nodes can be avoided when nodes are inserted as leaf nodes and sibling nodes without affecting the order of XML nodes. In addition, we propose an algorithm to control the increment of label size when new nodes are inserted frequently at a fix place of an XML tree. Experimental results show that our proposed bit string encoding scheme provides efficient support to the process of XML updating without sacrificing the query performance when it is applied to the range-based labeling schemes.     

Improving Border Localization of Multi-Baseline Stereo Using Border-Cut

This paper presents a novel algorithm that improves the localization of disparity discontinuities of disparity maps obtained by multi-baseline stereo. Rather than associating a disparity label to every pixel of a disparity map, it associates a position to every disparity discontinuity. This formulation allows us to find an approximate solution to a 2D labeling problem with robust smoothing term by minimizing multiple 1D problems, thus making possible the use of dynamic programming. Dynamic programming allows the efficient computation of the visibility of most of the cameras during the minimization. The proposed algorithm is not a stereo matcher on it own since it requires an initial disparity map. Nevertheless, it is a very effective way of improving the border localization of disparity maps obtained from a large class of stereo matchers. Whilst the proposed minimization strategy is particularly suitable for stereo with occlusion, it may be used for other labeling problems.     

基于路径空间层次划分的区域匹配算法

随着仿真应用在广度及深度上的发展,基于因特网的分布交互仿真成为未来的发展方向.其面临的主要挑战之一是系统可扩缩性问题.采用高效的数据过滤机制是解决问题的有效手段.首先讨论了分布交互仿真存在的可扩缩性问题,介绍了HLA(high level yarchitecture)框架下数据过滤机制的原理、实现及存在的问题.针对大规模系统过滤匹配计算量大的问题,提出了一种基于路径空间层次划分方法.该方法利用空间位置关系知识进行启发式搜索,从而排除大量不相关区域的匹配计算,有效地降低了过滤机制的计算复杂度.     

基于混合跳链条件随机场的异构Web记录集成方法

提出了一种混合跳链条件随机场序列统计学习模型,以实现异构Web记录与关系数据库的模式匹配.该模型可以在由手工标注样本和关系数据库记录组成的联合样本集上进行训练,减少了对繁琐手工标注样本的依赖.此外,通过在线性链条件随机场模型上增加对跳边的支持,使得该模型能够有效地处理状态变量间的长距离依赖.在多个领域的真实数据集上的实验结果表明,所提出的方法能够显著提高异构Web记录语义模式匹配的性能.     

Indexing and querying XML using extended Dewey labeling scheme

Finding all the occurrences of a tree pattern in an XML database is a core operation for efficient evaluation of XML queries. The Dewey labeling scheme is commonly used to label an XML document to facilitate XML query processing by recording information on the path of an element. In order to improve the efficiency of XML tree pattern matching, we introduce a novel labeling scheme, called extended Dewey, which effectively extends the existing Dewey labeling scheme to combine the types and identifiers of elements in a label, and to avoid the scan of labels for internal query nodes to accelerate query processing (in I/O cost). Based on extended Dewey, we propose a series of holistic XML tree pattern matching algorithms. We first present TJFast to answer an XML twig pattern query. To efficiently answer a generalized XML tree pattern, we then propose GTJFast, an optimization that exploits the non-output nodes. In addition, we propose TJFastTL and GTJFastTL based on the tag + level data partition scheme to further reduce I/O costs by level pruning. Finally, we report our comprehensive experimental results to show that our set of XML tree pattern matching algorithms are superior to existing approaches in terms of the number of elements scanned, the size of intermediate results and query performance.     

基于区域生长的多源遥感图像配准

多源遥感图像由于成像设备、所用光谱、拍摄时间等因素的不同,给配准带来极大的困难.尽管已经提出了多种匹配方法,但已有方法一般只能适用于特定的应用环境,开发出更加稳定和适用的配准算法仍然是一个极具挑战性的研究课题.提出一种基于区域生长的配准方法,首先,提取改进后的尺度不变特征,通过全局匹配确定种子点和种子区域并完成变换模型的初始化;然后,运用迭代区域生长和双向匹配策略,得到整个图像的可靠匹配点,从而实现多源遥感图像之间的配准.实验表明,该方法提取的匹配点的数量和正确率均远高于已有方法,能够对存在严重灰度差异的多源遥感图像实现高精度的配准,充分证明了该方法的鲁棒性和适用性.     

基于互关联后继树的XML索引技术

提出了一种新的根树节点编码方法——基于叶序区间的节点编码(LOINS)．编码方法只需对根树后序遍历一次即可完成,能实现常数时间内对任意两个树节点间前后代关系的判断．同时,结合互关联后继树模型(IRST)的标引性、可压缩性等特点,提出基于IRST的根树索引模型Ist3aRTI-Ⅰ,及对该模型空间优化的索引模型IstBaRTI-Ⅱ．IsBaRTI-Ⅰ,Ⅱ采用树节点名称(标签)及其在根树(XML文档树)中的出现计数索引节点间的父子关系和节点叶序区间编码,实现索引结构和节点编码的相互统一,IsBaRTI-Ⅰ,Ⅱ索引建立时间、空间代价小,可快速查询满足XPath表达式在XML文档树中的节点序列和路径．     

Augmented relaxation labeling and dynamic relaxation labeling

Current implementations of relaxation labeling are homogeneous, where each pixel is in an identical relationship to a static neighbor set. These systems maintain the iterative probabilistic labeling but use a nonhomogeneous dynamic neighborhood to establish a local consistency. Neighborhoods are created at each iteration through the broadcasting and reception of label information according to semantically established broadcasting patterns for each label. Augmented relaxation labeling is a two stage process which contains a separate relaxation stage with a top-down direction capability for specific pixel label updating. Dynamic relaxation is a one step process where every pixel label is updated through the dynamic neighborhoods. Both labeling processes are demonstrated on simple line drawings.     

基于量子遗传算法的高效匹配搜索策略

在大规模源图像上进行图像匹配时,最佳匹配点的搜索策略是匹配算法时间性能的决定因素,设计高效匹配搜索策略是提高算法性能的关键。为了减少搜索时间和提高匹配实时性,本文基于匹配源图像划分和量子遗传算法基本原理,提出了面向大规模源图像匹配的目标淘汰搜索策略TESS。TESS将基于整幅源图像的全空间随机搜索的过程变成基于各个子图像的子空间并行搜索和逐步淘汰的过程,实现了匹配区域粗定位与匹配点精搜索的有效结合,从而大大缩短了最佳匹配点的搜索时间。实验结果表明,TESS搜索策略带来了匹配速度的极大提高,且时间加速比随匹配源图像规模的增大而增大。     

An Evolutionary-Based Stereo Matching Method with a Multilevel Searching Strategy

Stereo matching is one of the fundamental problems in computer vision. It consists in identifying features in two or more stereo images that are generated by the same physical feature in the three-dimensional space. This paper presents an evolutionary approach with a multilevel searching strategy for matching edges extracted from two stereo images. The matching problem is turned into an optimization task, which is performed by means of a genetic algorithm with a new encoding scheme. For an effective exploitation of the genetic stereo matching algorithm for real-time obstacle detection, a multilevel searching strategy is proposed to match the edges at different levels by considering their gradient magnitudes. Experimental results and comparative analysis are presented to demonstrate the effectiveness of the proposed method for real-time obstacle detection in front of a moving vehicle using linear stereo vision.     

赋权图匹配问题的一种新的松弛模型

图匹配是一个NP难(NP-hard)问题. 基于置换矩阵是非负正交矩阵这一经典结论, 提出赋权图匹配(Weighted graph matching, WGM)的双向松弛障碍规划, 理论上证明新模型的解与原模型的解是一致的. 该规划是一个二元连续规划, 它是正交矩阵上的线性优化问题, 同时也是非负矩阵上的凸二次优化问题. 故设计求解新模型的交替迭代算法, 并证明算法的局部收敛性. 数值实验表明, 在匹配精度方面, 新方法强于线性规划方法和特征值分解方法.     

Supervised contrastive learning over prototype-label embeddings for network intrusion detection

Contrastive learning makes it possible to establish similarities between samples by comparing their distances in an intermediate representation space (embedding space) and using loss functions designed to attract/repel similar/dissimilar samples. The distance comparison is based exclusively on the sample features. We propose a novel contrastive learning scheme by including the labels in the same embedding space as the features and performing the distance comparison between features and labels in this shared embedding space. Following this idea, the sample features should be close to its ground-truth (positive) label and away from the other labels (negative labels). This scheme allows to implement a supervised classification based on contrastive learning. Each embedded label will assume the role of a class prototype in embedding space, with sample features that share the label gathering around it. The aim is to separate the label prototypes while minimizing the distance between each prototype and its same-class samples. A novel set of loss functions is proposed with this objective. Loss minimization will drive the allocation of sample features and labels in embedding space. Loss functions and their associated training and prediction architectures are analyzed in detail, along with different strategies for label separation. The proposed scheme drastically reduces the number of pair-wise comparisons, thus improving model performance. In order to further reduce the number of pair-wise comparisons, this initial scheme is extended by replacing the set of negative labels by its best single representative: either the negative label nearest to the sample features or the centroid of the cluster of negative labels. This idea creates a new subset of models which are analyzed in detail.The outputs of the proposed models are the distances (in embedding space) between each sample and the label prototypes. These distances can be used to perform classification (minimum distance label), features dimensionality reduction (using the distances and the embeddings instead of the original features) and data visualization (with 2 or 3D embeddings).Although the proposed models are generic, their application and performance evaluation is done here for network intrusion detection, characterized by noisy and unbalanced labels and a challenging classification of the various types of attacks. Empirical results of the model applied to intrusion detection are presented in detail for two well-known intrusion detection datasets, and a thorough set of classification and clustering performance evaluation metrics are included.     

Compositional metric learning for multi-label classification

Multi-label classification aims to assign a set of proper labels for each instance, where distance metric learning can help improve the generalization ability of instance-based multi-label classification models. Existing multi-label metric learning techniques work by utilizing pairwise constraints to enforce that examples with similar label assignments should have close distance in the embedded feature space. In this paper, a novel distance metric learning approach for multi-label classification is proposed by modeling structural interactions between instance space and label space. On one hand, compositional distance metric is employed which adopts the representation of a weighted sum of rank-1 PSD matrices based on component bases. On the other hand, compositional weights are optimized by exploiting triplet similarity constraints derived from both instance and label spaces. Due to the compositional nature of employed distance metric, the resulting problem admits quadratic programming formulation with linear optimization complexity w.r.t. the number of training examples.We also derive the generalization bound for the proposed approach based on algorithmic robustness analysis of the compositional metric. Extensive experiments on sixteen benchmark data sets clearly validate the usefulness of compositional metric in yielding effective distance metric for multi-label classification.     

近邻中心迭代策略的单标注视频行人重识别

为解决视频行人重识别数据集标注困难的问题,提出了基于单标注样本视频行人重识别的近邻中心迭代策略.该策略逐步利用伪标签视频片段迭代更新网络结构,以获得最佳的模型.针对预测无标签视频片段的伪标签准确率低的问题,提出了一种标签评估方法：每次训练后,将所选取的伪标签视频片段和有标签视频片段特征中每个类的中心点作为下一次训练中预测伪标签的度量中心点;同时提出基于交叉熵损失和在线实例匹配损失的损失控制策略,使得训练过程更加稳定,无标签数据的伪标签预测准确率更高.在MARS,DukeMTMC-VideoReID这两个大型数据集上的实验验证了该方法相比于最新的先进方法,在性能上得到非常好的提升.     

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

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