The complexity of graph languages generated by hyperedge replacement

Summary Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.Parts of the results of this paper were presented at 15^th ICALP, [La88b]     

On the effect of hyperedge weights on hypergraph learning

Hypergraph is a powerful representation for several computer vision, machine learning, and pattern recognition problems. In the last decade, many researchers have been keen to develop different hypergraph models. In contrast, no much attention has been paid to the design of hyperedge weighting schemes. However, many studies on pairwise graphs showed that the choice of edge weight can significantly influence the performances of such graph algorithms. We argue that this also applies to hypergraphs. In this paper, we empirically study the influence of hyperedge weights on hypergraph learning via proposing three novel hyperedge weighting schemes from the perspectives of geometry, multivariate statistical analysis, and linear regression. Extensive experiments on ORL, COIL20, JAFFE, Sheffield, Scene15 and Caltech256 datasets verified our hypothesis for both classification and clustering problems. For each of these classes of problems, our empirical study concludes with suggesting a suitable hypergraph weighting scheme. Moreover, the experiments also demonstrate that the combinations of such weighting schemes and conventional hypergraph models can achieve competitive classification and clustering performances in comparison with some recent state-of-the-art algorithms.     

Contextual nets

Acta Informatica - We propose a new kind of nets, called contextual nets, where events may have both preconditions and postconditions, as in the classical case, and also positive or negative...     

Blogger-Centric Contextual Advertising

Web advertising (online advertising), a form of advertising that uses the World Wide Web to attract customers, has become one of the most commonly-used marketing channels. This paper addresses the concept of Blogger-Centric Contextual Advertising, which refers to the assignment of personal ads to any blog page, chosen in according to bloggers’ interests. As blogs become a platform for expressing personal opinions, they naturally contain various kinds of statements, including facts, comments and statements about personal interests, of both a positive and negative nature. To extend the concept behind the Long Tail theory in contextual advertising, we argue that web bloggers, as the constant visitors of their own blog-sites, could be potential consumers who will respond to ads on their own blogs. Hence, in this paper, we propose using text mining techniques to discover bloggers’ immediate personal interests in order to improve online contextual advertising. The proposed Blogger-Centric Contextual Advertising (BCCA) framework aims to combine contextual advertising matching with text mining in order to select ads that are related to personal interests as revealed in a blog and rank them according to their relevance. We validate our approach experimentally using a set of data that includes both real ads and actual blog pages. The results indicate that our proposed method could effectively identify those ads that are positively-correlated with a blogger’s personal interests.     

Contextual multi-dimensional browsing

Browsing efficiency depends to a large extent on the organization of the information being browsed. An emerging method of organizing Web content, called multi-faceted categorization, adopts a flat structure and treats different facets of the browsed content as equal and independent. The advantage of this structure is that it allows users to slice and dice the information space from any of the facets they wish to browse, and in any arbitrary order, thereby facilitating so-called multi-dimensional browsing. However, because of limited human information processing capacities, too many choices and too much browsing freedom tend to disorient users and increase the difficulty of information gathering. A more effective means of organizing information is therefore needed.In the literature, it is well documented that context plays a crucial role in making relevance judgments about categorical attributes. Since browsing always occurs in relation to certain contexts, we propose taking context into account for multi-faceted categorization to help organize different facets of information on the browsing interface. Our experiment results demonstrate that the context-sensitive arrangement of categories helps users find information more efficiently. Moreover, users perceive the context-sensitive interface as easier to use than non-contextual interfaces.     

Dynamic Contextual Adaptation

When developing systems based on COTS, components need to be adapted in most of the occasions to work under certain conditions which were not initially predicted by their developers. Thus, it is very important to provide systems with the skill to dynamically alter their behaviour while running, depending on the changing conditions of the environment. In this work we describe a context-dependent, dynamic mapping between the interfaces of the components being adapted, overcoming some of the limitations of the static mappings presented in previous works. This is achieved by means of contextual environments, which define flexible adaptation policies. We also present a case study, illustrating the proposal, and discuss the improvements these mappings represent in comparison with previous works, as well as some open issues.     

Contextual Mixture Tracking

Multiple Object Tracking (MOT) poses three challenges to conventional well-studied Single Object Tracking (SOT) algorithms: 1) Multiple targets lead the configuration space to be exponential to the number of targets; 2) Multiple motion conditions due to multiple targets' entering, exiting and intersection make the prediction process degrade in precision; 3) Visual ambiguities among nearby targets make the trackers error prone. In this paper, we address the MOT problem by embedding contextual proposal distributions and contextual observation models into a mixture tracker which is implemented in a Particle Filter framework. The proposal distributions are adaptively selected by motion conditions of targets which are determined by context information, and the multiple features are combined according to their discriminative power between ambiguity prone objects. The induction of contextual proposal distribution and observation model can help to surmount the incapability of conventional mixture tracker in handling object occlusions, meanwhile retain its merits of flexibility and high efficiency. The final experiments show significant improvement in variable number objects tracking scenarios compared with other methods.      

Contextual reasoning distilled

In this paper we provide a foundation of a theory of contextual reasoning from the perspective of a theory of knowledge representation. Starting from the so-called metaphor of the box, we firstly show that the mechanisms of contextual reasoning proposed in the literature can be classified into three general forms (called localized reasoning, push and pop, and shifting). Secondly, we provide a justification of this classification, by showing that each mechanism corresponds to operating on a fundamental dimension along which context dependent representations may vary (namely, partiality, approximation and perspective). From the previous analysis, we distill two general principles of a logic of contextual reasoning. Finally, we show that these two principles can be adequately formalized in the framework of MultiContext Systems. In the last part of the paper, we provide a practical illustration of the ideas discussed in the paper by formalising a simple scenario, called the Magic Box problem.     

情境计算研究综述

作为一种新的计算模式,情境计算得到了学术界和产业界越来越多的关注.随着物联网、云计算、大数据、社会计算等相关技术的不断发展成熟,情境计算进入了快速发展阶段.情境计算是一种通过对获取到的情境信息进行处理、从而得出用户所需服务并主动向用户提供相应情境感知服务的计算模式.这一新的计算模式为使用者的工作、生活带来了舒适和便利.对情境计算的诞生背景进行阐述,介绍情境、情境计算、情境感知、情境感知系统和情境感知服务等关键概念,总结情境数据获取、情境模型与建模、情境推理、主动服务提供、情境感知中间件和安全与隐私等重要研究内容以及其中使用到的关键技术,最后依托情境计算的一般性架构分析得出情境计算的未来发展挑战.     

基于多尺度上下文的图像标注算法

提出了一种在层次化分割框架下,通过结合图像的底层局部特征以及高层的上下文特征,进行图像自动语义标注的新算法. 该算法的核心思想在于对较大的图像区域的识别结果有利于对其包含的较小图像区域进行识别.算法首先对每层分割后的图像区域进行识别, 然后利用贝叶斯定理将各层区域识别的结果通过线性加权的方式进行融合,从而达到对整幅图像进行自动语义标注的目的.与现有的图像标注算法相比,仿真实验表明本文算法获得了最好的标注精度以及最快的标注速度.     

Contextual Priming for Object Detection

There is general consensus that context can be a rich source of information about an object's identity, location and scale. In fact, the structure of many real-world scenes is governed by strong configurational rules akin to those that apply to a single object. Here we introduce a simple framework for modeling the relationship between context and object properties based on the correlation between the statistics of low-level features across the entire scene and the objects that it contains. The resulting scheme serves as an effective procedure for object priming, context driven focus of attention and automatic scale-selection on real-world scenes.     

Contextual Probability and Neighbourhood Counting

In this paper, we review the concept of contextual probability, the resulting notion of neighbourhood counting and the various specialisations of this notion which result in new functions for measuring similarity, such as all common subsequences. We also provide new results on the generalisation of the all common subsequences similarity. Contextual probability was originally proposed as an alternative way of reasoning. It was later found to be an alternative way of estimating probability, and it led to the introduction of the neighbourhood counting notion. This notion was then found to be a generic similarity metric that can be applied to different types of data.     

上下文信息检索研究综述

上下文信息检索强调把有关用户、资源和查询的上下文与信息检索技术统一组织在一个整体框架内,以向用户提供最适合用户需求的检索信息。全面介绍了上下文信息检索的研究现状,概括了国内外研究者对上下文信息检索过程中涉及的上下文因素及其分类,并从用户上下文、文档上下文和系统上下文3个角度对国内外有关上下文信息检索技术的研究作了概述。最后从5个方面探讨了上下文信息检索领域存在的挑战,指出对用户检索背后需求的探究、基于语义的理解和融合上下文的信息检索模型等将是该领域目前亚需解决的问题。     

Mumford-Shah Regularizer with Contextual Feedback

We present a simple and robust feature preserving image regularization by letting local region measures modulate the diffusivity. The purpose of this modulation is to disambiguate low level cues in early vision. We interpret the Ambrosio-Tortorelli approximation of the Mumford-Shah model as a system with modulatory feedback and utilize this interpretation to integrate high level information into the regularization process. The method does not require any prior model or learning; the high level information is extracted from local regions and fed back to the regularization step. An important characteristic of the method is that both negative and positive feedback can be simultaneously used without creating oscillations. Experiments performed with both gray and color natural images demonstrate the potential of the method under difficult noise types, non-uniform contrast, existence of multi-scale patterns and textures.

Contextual Animation of Gestural Commands

Drawing a mark can be an efficient command input technique when using a pen-based computer. However, marks are not intrinsically self-explanatory as are other interactive techniques such as buttons and menus. We present design principles for interaction mechanisms which make marks self explanatory for novices but still allow experts to use efficient command marks. The key notion is that use of the explanation mechanism physically trains a novice to use the efficient command marks. Two novel interaction mechanisms we have developed using these principles are presented.     

Contextual Inference in Contour-Based Stereo Correspondence

Standard approaches to stereo correspondence have difficulty when scene structure does not lie in or near the frontal parallel plane, in part because an orientation disparity as well as a positional disparity is introduced. We propose a correspondence algorithm based on differential geometry, that takes explicit advantage of both disparities. The algorithm relates the 2D differential structure (position, tangent, and curvature) of curves in the left and right images to the Frenet approximation of the (3D) space curve. A compatibility function is defined via transport of the Frenet frames, and they are matched by relaxing this compatibility function on overlapping neighborhoods along the curve. The remaining false matches are concurrently eliminated by a model of “near” and “far” neurons derived from neurobiology. Examples on scenes with complex 3D structures are provided.     

Contextual classification of multispectral pixel data

Contextual statistical decision rules for classification of lattice-structured data such as pixels in multispectral imagery are developed. Their recursive implementation is shown to have a strong resemblance to relaxation algorithms. Experimental evaluation of the proposed algorithms demonstrates their effectiveness.     

利用上下文相关信息的汉字文本识别

为了改善汉字文本识别率, 本文提出了一种基于语料库统计概率的后处理方法, 该方法利用上下文相关信息, 超过词汇对于汉字文本识别, 把具有确定性边界的一个汉字序列多数情况为一个句子作为一个处理单元, 利用统计获得的字字同现概率,采用动态规划方法, 获得了令人满意的效果。