Real-Time GPU Silhouette Refinement using Adaptively Blended Bézier Patches

We present an algorithm for detecting and extracting the silhouette edges of a triangle mesh in real time using Graphical Processing Units (GPUs). We also propose a tessellation strategy for visualizing the mesh with smooth silhouettes through a continuous blend between Bézier patches with varying level of detail. Furthermore, we show how our techniques can be integrated with displacement and normal mapping. We give details on our GPU implementation and provide a performance analysis with respect to mesh size.     

Faster ARMA maximum likelihood estimation

A new likelihood based AR approximation is given for ARMA models. The usual algorithms for the computation of the likelihood of an ARMA model require O(n) flops per function evaluation. Using our new approximation, an algorithm is developed which requires only O(1) flops in repeated likelihood evaluations. In most cases, the new algorithm gives results identical to or very close to the exact maximum likelihood estimate (MLE). This algorithm is easily implemented in high level quantitative programming environments (QPEs) such as Mathematica, MatLab and R. In order to obtain reasonable speed, previous ARMA maximum likelihood algorithms are usually implemented in C or some other machine efficient language. With our algorithm it is easy to do maximum likelihood estimation for long time series directly in the QPE of your choice. The new algorithm is extended to obtain the MLE for the mean parameter. Simulation experiments which illustrate the effectiveness of the new algorithm are discussed. Mathematica and R packages which implement the algorithm discussed in this paper are available [McLeod, A.I., Zhang, Y., 2007. Online supplements to “Faster ARMA Maximum Likelihood Estimation”, 〈http://www.stats.uwo.ca/faculty/aim/2007/faster/〉]. Based on these package implementations, it is expected that the interested researcher would be able to implement this algorithm in other QPEs.     

Quasi-Upward Planarity

Abstract. An upward planar drawing of a directed graph (digraph) is a planar drawing such that all the edges are represented by curves monotonically increasing in the vertical direction. In this paper we introduce and study the concept of quasi-upward planarity. Quasi-upward planarity allows us to extend the upward planarity theory to a large class of digraphs including digraphs that also have directed cycles. First, we characterize the digraphs that have a quasi-upward planar drawing. Second, we give a polynomial time algorithm for computing ``optimal' quasi-upward planar drawings within a given planar embedding. Further, we apply branch and bound techniques to the problem of computing optimal quasi-upward planar drawings, considering all possible planar embeddings. The paper also contains experimental results about the proposed techniques.     

A framework for simulating real-time multi-agent systems

In this paper, we describe an implementation of use in demonstrating the effectiveness of architectures for real-time multi-agent systems. The implementation provides a simulation of a simplified RoboCup Search and Rescue environment, with unexpected events, and includes a simulator for both a real-time operating system and a CPU. We present experimental evidence to demonstrate the benefit of the implementation in the context of a particular hybrid architecture for multi-agent systems that allows certain agents to remain fully autonomous, while others are fully controlled by a coordinating agent. In addition, we discuss the value of the implementation for testing any models for the construction of real-time multi-agent systems and include a comparison to related work.

Multilayer hybrid visualizations to support 3D GIS

In this paper, we present a unique hybrid visualization system for spatial data. Although some existing 3D GIS systems offer 2D views they are typically isolated from the 3D view in that they are presented in a separate window. Our system is a novel hybrid 2D/3D approach that seamlessly integrates 2D and 3D views of the same data. In our interface, multiple layers of information are continuously transformed between the 2D and 3D modes under the control of the user, directly over a base terrain. In this way, our prototype system is able to depict 2D and 3D views within the same window. This has advantages, since 2D and 3D visualizations can each be easier to interpret in different contexts.In this work we develop this concept of a hybrid visualization by presenting a comprehensive set of capabilities within our distinctive system. These include new facilities such as: hybrid landmark, 3D point, and chart layers, the grouping of multiple hybrid layers, layer painting, the merging of layer controls and consistent zooming functionality.     

A privacy preserving technique for distance-based classification with worst case privacy guarantees

There has been relatively little work on privacy preserving techniques for distance based mining. The most widely used ones are additive perturbation methods and orthogonal transform based methods. These methods concentrate on privacy protection in the average case and provide no worst case privacy guarantee. However, the lack of privacy guarantee makes it difficult to use these techniques in practice, and causes possible privacy breach under certain attacking methods. This paper proposes a novel privacy protection method for distance based mining algorithms that gives worst case privacy guarantees and protects the data against correlation-based and transform-based attacks. This method has the following three novel aspects. First, this method uses a framework to provide theoretical bound of privacy breach in the worst case. This framework provides easy to check conditions that one can determine whether a method provides worst case guarantee. A quick examination shows that special types of noise such as Laplace noise provide worst case guarantee, while most existing methods such as adding normal or uniform noise, as well as random projection method do not provide worst case guarantee. Second, the proposed method combines the favorable features of additive perturbation and orthogonal transform methods. It uses principal component analysis to decorrelate the data and thus guards against attacks based on data correlations. It then adds Laplace noise to guard against attacks that can recover the PCA transform. Third, the proposed method improves accuracy of one of the popular distance-based classification algorithms: K-nearest neighbor classification, by taking into account the degree of distance distortion introduced by sanitization. Extensive experiments demonstrate the effectiveness of the proposed method.     

Conceptual equivalence for contrast mining in classification learning

Learning often occurs through comparing. In classification learning, in order to compare data groups, most existing methods compare either raw instances or learned classification rules against each other. This paper takes a different approach, namely conceptual equivalence, that is, groups are equivalent if their underlying concepts are equivalent while their instance spaces do not necessarily overlap and their rule sets do not necessarily present the same appearance. A new methodology of comparing is proposed that learns a representation of each group’s underlying concept and respectively cross-exams one group’s instances by the other group’s concept representation. The innovation is fivefold. First, it is able to quantify the degree of conceptual equivalence between two groups. Second, it is able to retrace the source of discrepancy at two levels: an abstract level of underlying concepts and a specific level of instances. Third, it applies to numeric data as well as categorical data. Fourth, it circumvents direct comparisons between (possibly a large number of) rules that demand substantial effort. Fifth, it reduces dependency on the accuracy of employed classification algorithms. Empirical evidence suggests that this new methodology is effective and yet simple to use in scenarios such as noise cleansing and concept-change learning.     

Interference automata

We propose a computing model, the Two-Way Optical Interference Automata (2OIA), that makes use of the phenomenon of optical interference. We introduce this model to investigate the increase in power, in terms of language recognition, of a classical Deterministic Finite Automaton (DFA) when endowed with the facility of interference. The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA) [A. Ambainis, J. Watrous, Two-way finite automata with quantum and classical states, Theoret. Comput. Sci. 287 (1) (2002) 299–311] wherein the classical DFA is augmented with a quantum component of constant size. We test the power of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA algorithms to recognize languages for which 2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA has been posed as open questions. Having a DFA as a component, it trivially recognizes regular languages. We show that our model can recognize all languages recognized by 1-way deterministic blind counter automata. Finally we show the existence of a language that cannot be recognized by a 2OIA but which can be recognized by an O(n³)$O\left(n^3\right)$ space Turing machine.     

Motif patterns in 2D

Motif patterns consisting of sequences of intermixed solid and don’t-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. The remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms.     

The development of a formative scenario-based computer assisted assessment tool in psychology for teachers: The PePCAA project

Formative computer assisted assessment has become increasingly attractive in Higher Education where providing useful feedback to large numbers of students can be difficult. However, the nature of such assessments has often been limited to objective questions such as multiple-choice. This paper reports on the development and initial trialling of a more innovative, formative use of computer assisted assessment in a Higher Education context. The European funded PePCAA (Pedagogical Psychology Computer Assisted Assessment) project developed a series of scenario-based computer-delivered formative assessments of pedagogical psychology for teachers and trainee teachers, using a range of software features, including the addition of confidence measurement. The project had a two-fold aim: to provide a tool to improve understanding of pedagogical psychology and to explore the potential of more innovative techniques of computer assisted assessment to motivate students and to assess deeper learning. The combination of computer-delivered formative assessment with innovative question styles and confidence ratings is believed to be unique for pedagogical psychology. Scenarios were based on realistic classroom situations and focused on problem solving or on utilising best practice. The PePCAA Learning Assessment Circle (PLAC) provided a framework for indexing the kinds of processes required of users. In the UK, small scale trialling involved a total of 23 teacher trainees such that each assessment was attempted by about seven participants. Participants completed evaluation questionnaires after each assessment. Responses from learners indicated that the UK scenarios were generally very well received and had at least partly achieved the aim of stimulating deeper learning. Transfer of assessments between countries proved more difficult than expected. The next stage of development should be to conduct a larger pilot, thus allowing full investigation of the reliability and validity of the assessments. There is also scope for further development of the PePCAA approach and for its application in other subjects.