A Common Reasoning Model and Its Application in Knowledge-Based System

To use reasoning knowledge accurately and efficiently,many reasoning methods have been proposed.However,the differences in form among the methods may obstruct the systematical analysis and harmonious integration of them.In this paper,a common reasoning model JUM(Judgement Model)is introduced.According to JUM,a common knowledge representation form is abstracted from different reasoning methods and its limitation is reduced.We also propose an algorithm for transforming one type of JUMs into another.In some cases,the algorithm can be used to resolve the key problem of integrating different types of JUM in one system.It is possible that a new architecture of knowledge-based system can be realized under JUM.     

支持向量机及其在模式识别中的应用

Statistical learning theory(SLT)and support vector machine(SVM) are effective to solve problems of machine learning under the condition of finite samples.It is known that the performance of support vector machine is often better than that of some neural networks in pattern recognition,especially in high dimensional space,and they arewell used in many domains for recognition.This paper at first introduces the basic theory of SLT and SVM,then points out the key problems of SVM and its research situation in recent years,and at last describes some applications of SVM in the field of pattern recognition.     

Modelling and Reasoning in Metamodelling Enabled Ontologies

Ontologies are expected to play an important role in many application domains, as well as in software engineering in general. One problem with using ontologies within software engineering is that while UML, a widely used standard for specifying and constructing the models for a software-intensive system, has a four-layer metamodelling architecture, the standard Web Ontology Language (OWL) does not support reasoning over layered metamodels. OWL 2 provides simple metamodelling by using a punning approach, however, the interpretation function is different based on the context, which leads to non-intuitive results. The OWL FA Language has a well defined metamodelling architecture. However, there is no study and tool for supporting reasoning over OWL FA. In this paper, we discuss some reasoning tasks in OWL FA. We also introduce the OWL FA Tool kit, a simple tool kit for manipulating and reasoning with OWL FA.     

Continuous Probabilistic Subspace Skyline Query Processing Using Grid Projections

As an important type of multidimensional preference query, the skyline query can find a superset of optimal results when there is no given linear function to combine values for all attributes of interest. Its processing has been extensively investigated in the past. While most skyline query processing algorithms are designed based on the assumption that query processing is done for all attributes in a static dataset with deterministic attribute values, some advanced work has been done recently to remove part of such a strong assumption in order to process skyline queries for real-life applications, namely, to deal with data with multi-valued attributes （known as data uncertainty）, to support skyline queries in a subspace which is a subset of attributes selected by the user, and to support continuous queries on streaming data. Naturally, there are many application scenarios where these three complex issues must be considered together. In this paper, we tackle the problem of probabilistic subspace skyline query processing over sliding windows on uncertain data streams. That is, to retrieve all objects from the most recent window of streaming data in a user-selected subspace with a skyline probability no smaller than a given threshold. Based on the subtle relationship between the full space and an arbitrary subspace, a novel approach using a regular grid indexing structure is developed for this problem. An extensive empirical study under various settings is conducted to show the effectiveness and efficiency of our PSS algorithm.     

Social Network-Aware Interfaces as Facilitators of Innovation

Achieving continuous innovation in organizations requires a balance between exploiting yet acquired knowledge and exploring new knowledge.In addition to having the adequate resources,change and innovation capabilities require specific management support and organizational structures.Recent research has pointed out the importance of social network structure and of the activity of agents that work across domains or disciplines in the innovation-oriented behaviour of organizations.As a consequence,information systems should ideally be able to support the analysis,development and management of such social structure for the benefit of organizational objectives.Current social network interfaces provide an established mental model to workers that can be hypothesized to be adequate for supporting activities that foster innovative behaviour.That behaviour is facilitated through exposing the activities of other workers across organizational structures.This paper reports on the design of a user interface specifically targeted to manage the social aspects of innovation based on some aspects of Hargadon’s model of innovation and knowledge brokering.The emergent nature of interactions in social network sites is used as the metaphor to foster situated cognition.The interface design assessment is described and some metrics for innovative behaviour that could be derived for such an interface are sketched.     

Power Efficient Sub-Array in Reconfigurable VLSI Meshes

Given an m×n mesh-connected VLSI array with some faulty elements, the reconfiguration problem is to find a maximum-sized fault-free sub-array under the row and column rerouting scheme. This problem has already been shown to be NP-complete. In this paper, new techniques are proposed, based on heuristic strategy, to minimize the number of switches required for the power efficient sub-array. Our algorithm shows that notable improvements in the reduction of the number of long interconnects could be realized in linear time and without sacrificing on the size of the sub-array. Simulations based on several random and clustered fault scenarios clearly reveal the superiority of the proposed techniques.     

Efficient fingerprint matching algorithm for Integrated Circuit Cards

Fingerprint matching is a crucial step in fingerprint identification. Recently, a variety of algorithms for this issue have been developed. Each of them is application situation specific and has its advantages and disadvantages. It is highly desired to develop an efficient fingerprint verification technology for Integrated Circuit (IC) Cards or chips. IC cards have some special characteristics, such as very small storage space and slow processing speed, which hinder the use of most fingerprint matching algorithms in such situations. In order to solve this problem, the paper presents an improved minutia-pattern (minutiae-based) matching algorithm by employing the orientation field of the fingerprint as a new feature. Our algorithm not only inherits the advantages of the general minutia-pattern matching algorithms, but also overcomes their disadvantages. Experimental results show that the proposed algorithm can greatly improve the performance of fingerprint matching in both accuracy and efficiency, and it is very suitable for applications in IC cards.     

<Emphasis Type="Italic">LFTOP</Emphasis>: An <Emphasis Type="Italic">LF</Emphasis>-Based Approach to Domain-Specific Reasoning

A new approach to domain-specific reasoning is presented that is based on a type-theoretic logical framework(LF) but does not require the user to be an expert in type theory. The concepts of the domain and its related reasoning systems are formalized in LF, but the user works with the system through a syntax and interface appropriate to his/her work. A middle layer provides translation between the user syntax and LF, and allows additional support for reasoning(e.g., model checking). Thus, the complexity of the logical framework is hidden but the benefits of using type theory and its related tools are retained, such as precision and machine-checkable proofs. This approach is investigated through a number of case studies: here, the authors consider the verification of properties of concurrency. The authors have formalized a specification language (CCS) and logic (μ-calculus) in LF, together with useful lemmas, and a user-oriented syntax has been designed. The authors demonstrate the approach with simple examples. However, applying lemmas to objects introduced by the user may result in framework-level objects which cannot be translated back to the user level. The authors discuss this problem, define a notion of adequacy, and prove that in this case study, translation can always be reversed.     

Pricing Loss Leaders Can be Hard

Consider the problem of pricing n items under an unlimited supply with m single minded buyers,each of which is interested in at most k of the items.The goal is to price each item with profit margin p1,p2,...,pn so as to maximize the overall profit.There is an O(k)-approximation algorithm by Balcan and Blum when the price on each item must be above its margin cost;i.e.,each pi > 0.We investigate the above problem when the seller is allowed to price some of the items below their margin cost.It was shown by Balcan et al.that by pricing some of the items below cost,the seller could possibly increase the maximum profit by Ω(log n) times.These items sold at low prices to stimulate other profitable sales are usually called "loss leader".It is unclear what kind of approximation guarantees are achievable when some of the items can be priced below cost.Understanding this question is posed as an open problem by Balcan and Blum.In this paper,we give a strong negative result for the problem of pricing loss leaders .We prove that assuming the Unique Games Conjecture (UGC),there is no constant approximation algorithm for item pricing with prices below cost allowed even when each customer is interested in at most three items.Conceptually,our result indicates that although it is possible to make more money by selling some items below their margin cost,it can be computationally intractable to do so.     

粒子群优化算法在点模式匹配中的应用

点模式匹配技术是计算机视觉和模式识别领域中的一个重要课题.将每个点模式编码为一个称为粒子的实值向量,并利用两幅图像的灰度矩阵来构造粒子的适应度函数,提出一种基于粒子群优化算法的点模式匹配新算法.系统初始化为一组随机解,通过迭代使粒子在解空间中追随当前较优的粒子进行搜索,从而找到最优解.仿真实验结果证明算法的有效性.     

匹配与姿态估计的粒子群优化算法

点模式匹配问题是机器视觉与模式识别领域中一个基础问题,在目标识别、医学图像配准、遥感图像匹配、姿态估计等方面都得到广泛应用。提出一种在仿射变换下利用粒子群优化算法进行图像点模式下的匹配与姿态估计的方法。算法首先把点集匹配问题转化为解空间为仿射参数空间下的目标函数优化问题,然后运用粒子群算法对相应的变换参数进行搜索,获得问题最优解。本文贡献如下：1)给出一种仿射参数的初始估计方法,提高了后续算法搜索效率;2)引入阈值和次近点规则,改进了最近点匹配搜索方法,能较好地拒绝出格点（outliers）,并提高算法有效性;3)从两方面对PSO方法进行了改进,加强了原PSO的全局和局部搜索能力。实验结果表明,算法具有有效性和鲁棒性。     

一种基于极坐标变换的点模式匹配算法

点模式匹配是目标识别、图像配准与匹配、姿态估计等计算机视觉与模式识别应用方向的基础问题之一。提出了一种新的利用点特征进行匹配的算法,该算法根据点集的分布与点位置信息,构建了点的特征属性图,通过极坐标变换得到对数极坐标的特征图,并利用几何不变矩方法对特征图进行描述。由特征描述向量的比较,获得粗匹配结果,然后通过几何约束迭代的方法获取最终的点集匹配结果。本文贡献如下:一,构建了一种点的极坐标变换特征,并运用不变矩进行描述,使所提特征具有旋转与平移的不变性;二,提出了利用点特征与整体点集几何约束结合的匹配算法,能有效克服出格点与噪声带来的不利影响。最终实验说明了算法的有效性和鲁棒性。     

点模式匹配

利用不可约四和相对不变量理论提出了几种点模式新算法,它们可分别用来解决相似变换和上具有相同点数的两个点模式的匹配问题,这些算法的基本出发点 待匹配的两个二维占 分别转化成为一个ｎ维空间中的向量,只要对这两个向量中的各元素进行简单的排序就可解决对应的原来点模式的匹配问题,理论分析和仿真实验表明这些算法是有效的。     

点线特征融合的误匹配剔除算法

特征匹配作为计算机视觉的一项关键技术而备受关注。近年来,基于描述子的特征点匹配技术取得了一系列突破性进展,但曲线长度不一、端点定位不准确以及周围包含的重复性纹理较多等因素,导致了曲线匹配研究依旧是一个极具挑战性的热点研究课题,且现有曲线匹配方法大多出现匹配总数少、匹配正确率低的问题。为增加特征匹配的总数和正确率,利用特征点和特征曲线的位置关系提出一种点线特征融合的误匹配剔除算法(Point Line feature Fusion,PLF)。首先定义点到曲线的距离,利用点、曲线描述子提取图像的点、线特征;其次确定落入匹配曲线对应支撑区域内的匹配点对,并根据匹配点组和曲线间的距离约束剔除错误曲线匹配;最后利用点线距离约束剔除匹配曲线支撑区域内的错误点匹配。实验选取了3种不同的点线组合,即SIFT技术提取的点特征分别与IOCD曲线描述子、IOMSD曲线描述子、GOCD曲线描述子提取的曲线特征相融合, 验证算法 对多种点、线描述子具有适用性,且该算法不仅适用于特征点与特征曲线的融合,亦适用于特征点与特征直线的融合,从而验证了其对多种图像特征具有适用性。实验结果表明,在旋转、视角变化、光照变化、压缩、噪音、模糊等变换条件下,该算法均能有效提高曲线特征匹配的匹配总数和匹配正确率,同时提高点匹配的正确率。     

平面点匹配的一点校准算法

点模式匹配是一项重要的视觉课题。对于一个平面点集,由平移和旋转并伴有一定噪声作用产生另一点集,提出一个基于一点校准的点模式快速匹配算法,并推广到带有属性点的匹配问题中。基于一点校准的点模式匹配算法,其计算复杂性为O(mn),其中m,n分别是两个点集所含点的个数,比基于两点距离近似相等的校准匹配算法,其计算复杂性为O(m2nl)(其中l为第二个点集中与第一个点集中任两个点的距离近似相等的平均个数),极大地减少了计算量。     

Efficient Algorithms for Image Template and Dictionary Matching

Given a large text image and a small template image, the Template Matching Problem is that of finding every location within the text which looks like the pattern. This problem, which has received attention for low-level image processing, has been formalized by defining a distance metric between arrays of pixels and finding all subarrays of the large image which are within some threshold distance of the template. These so-called metric methods tends to be too slow for many applications, since evaluating the distance function can take too much time. We present a method for quickly eliminating most positions of the text from consideration as possible matches. The remaining candidate positions are then evaluated one by one against the template for a match. We are still guaranteed to find all matching positions, and our method gives significant speed-ups. Finally, we consider the problem of matching a dictionary of templates against a text. We present methods which are much faster than matching the templates individually against the input image.     

基于中心点的指纹细节结构匹配算法

指纹细节匹配算法是自动指纹识别系统(AFIS)中一项关键的任务,目前存在大量的研 究和算法.依据算法是否依赖中心点,指纹细节点匹配算法可以分为两类:基于中心点的匹配算 法和非中心点匹配算法.大多数非中心点匹配算法都非常耗时,因此不适合在线应用.而基于中 心点方法的效率相对较高,但是这类算法极度依赖于中心点的定位精度.在本文中,提出了一种 全新的基于中心点的指纹细节结构匹配算法,该算法综合了基于中心点匹配算法和非中心点匹 配算法的优点,同时又避免了二者的缺点.首先利用中心点检测算法获得中心点的位置,然后在 中心区域定义了一些局部的结构,同时利用这些局部结构寻找指纹细节的对应点,并通过对应点 和中心点的相对关系来确认这些对应细节点.其次利用这些细节对应点匹配全局的细节信息,最 后,利用匹配细节的全局距离和距离方差来判决最终匹配结果.实验结果表明,算法的匹配效果 非常好,同时匹配效率较高,非常适合在线指纹识别系统的应用.     

Simple algorithms for partial point set pattern matching under rigid motion

This paper presents simple and deterministic algorithms for partial point set pattern matching in 2D. Given a set P of n points, called sample set, and a query set Q of k points (n?k), the problem is to find a matching of Q with a subset of P under rigid motion. The match may be of two types: exact and approximate. If an exact matching exists, then each point in Q coincides with the corresponding point in P under some translation and/or rotation. For an approximate match, some translation and/or rotation may be allowed such that each point in Q lies in a predefined ε-neighborhood region around some point in P. The proposed algorithm for the exact matching needs O(n²) space and preprocessing time. The existence of a match for a given query set Q can be checked in time in the worst-case, where α is the maximum number of equidistant pairs of point in P. For a set of n points, α may be O(n^4/3) in the worst-case. Some applications of the partial point set pattern matching are then illustrated. Experimental results on random point sets and some fingerprint databases show that, in practice, the computation time is much smaller than the worst-case requirement. The algorithm is then extended for checking the exact match of a set of k line segments in the query set with a k-subset of n line segments in the sample set under rigid motion in time. Next, a simple version of the approximate matching problem is studied where one point of Q exactly matches with a point of P, and each of the other points of Q lie in the ε-neighborhood of some point of P. The worst-case time and space complexities of the proposed algorithm are and O(n), respectively. The proposed algorithms will find many applications to fingerprint matching, image registration, and object recognition.