Zodiac: A history-based interactive video authoring system

Easy-to-use audio/video authoring tools play a crucial role in moving multimedia software from research curiosity to mainstream applications. However, research in multimedia authoring systems has rarely been documented in the literature. This paper describes the design and implementation of an interactive video authoring system called Zodiac, which employs an innovative edit history abstraction to support several unique editing features not found in existing commercial and research video editing systems. Zodiac provides users a conceptually clean and semantically powerful branching history model of edit operations to organize the authoring process, and to navigate among versions of authored documents. In addition, by analyzing the edit history, Zodiac is able to reliably detect a composed video stream's shot and scene boundaries, which facilitates interactive video browsing. Zodiac also features a video object annotation capability that allows users to associate annotations to moving objects in a video sequence. The annotations themselves could be text, image, audio, or video. Zodiac is built on top of MMFS, a file system specifically designed for interactive multimedia development environments, and implements an internal buffer manager that supports transparent lossless compression/decompression. Shot/scene detection, video object annotation, and buffer management all exploit the edit history information for performance optimization.     

Movement Awareness for Ubiquitous Game Control

This paper describes a sensing system for recognising and characterising human movements and its application to ubiquitous gaming. In particular this paper considers the control of computer games through players interacting with the physical environment around them in a natural and appropriate manner. This pushes the interface into the environment, and pulls ubiquitous computing into the game. This is achieved using a sentient computing system. Such a system senses the location, motions, actions and even physiological responses of users. This sensory data can be used to interface and control a game. A good example is 3D first-person games and we demonstrate a system in which actions in the game are mapped to similar actions in the real world. Correspondence to: R. Headon, Laboratory for Communications Engineering, Department of Engineering, University of Cambridge, Trumpington Street, Cambridge CB2 1PZ, UK. Email: rph25@cam.ac.uk     

Location Models for Augmented Environments

In this paper we describe two projects on contextualized computer systems and audio augmented environments we are currently working on at the Fraunhofer Institutes FIT and IMK. In this paper we will only focus on the world models and the augmentation layer. Both projects are based on completely different technologies, and use different representation methods and interaction facilities. While in hippie users are moving with small laptop computers or wearable computers with a small visual display, in LISTEN users will have only a wireless headphone displaying spatially rendered sound-scenes. Correspondence to: J. Goβmann, Fraunhofer-IMK, Schloss Birlinghoven, D-53754 St Augustin, Germany.     

Contextual Virtual Interaction as Part of Ubiquitous Game Design and Development

This paper relates to the problems of designing rich interaction, in the context of multi-player games, that would adequately support communication, control and co-ordination. The aspects of fun and rich experiences, usually required within the entertainment context, are easily overlooked in technologically driven system design. The concepts of a future ubiquitous game can be difficult to comprehend and evaluate in cases where a fully functioning physical prototype is not an option. One solution for the problem is Contextual Virtual Reality Prototyping that adds the missing context to the design simulations. The product can be designed and demonstrated in the corresponding environment, thus making it easier to understand the use-cases of, for example, a mobile device that has various location-dependent features. The main contribution of this research is the design and development approach that supports the creation of rich interaction. The primary emphasis of the approach is to avoid purely technologically driven design and development, but rather to provide a supporting, or even a guiding, approach that focuses on the creative process and conceptual understanding of rich interaction. This conceptually grounded content production-oriented approach to interactive system design is described and evaluated. Correspondence to: T. Manninen, Department of Information Processing Science, University of Oulu, PO Box 3000, 90014 Oulun Yliopisto, Finland. Email: tony.manninen@oulu.fi     

Yoda,an adaptive soft classification model: content-based similarity queries and beyond

Abstract. Providing a customized result set based upon a user preference is the ultimate objective of many content-based image retrieval systems. There are two main challenges in meeting this objective: First, there is a gap between the physical characteristics of digital images and the semantic meaning of the images. Secondly, different people may have different perceptions on the same set of images. To address both these challenges, we propose a model, named Yoda, that conceptualizes content-based querying as the task of soft classifying images into classes. These classes can overlap, and their members are different for different users. The “soft” classification is hence performed for each and every image feature, including both physical and semantic features. Subsequently, each image will be ranked based on the weighted aggregation of its classification memberships. The weights are user-dependent, and hence different users would obtain different result sets for the same query. Yoda employs a fuzzy-logic based aggregation function for ranking images. We show that, in addition to some performance benefits, fuzzy aggregation is less sensitive to noise and can support disjunctive queries as compared to weighted-average aggregation used by other content-based image retrieval systems. Finally, since Yoda heavily relies on user-dependent weights (i.e., user profiles) for the aggregation task, we utilize the users' relevance feedback to improve the profiles using genetic algorithms (GA). Our learning mechanism requires fewer user interactions, and results in a faster convergence to the user's preferences as compared to other learning techniques. Correspondence to: Y.-S. Chen (E-mail: yishinc@usc.edu) This research has been funded in part by NSF grants EEC-9529152 (IMSC ERC) and IIS-0082826, NIH-NLM R01-LM07061, DARPA and USAF under agreement nr. F30602-99-1-0524, and unrestricted cash gifts from NCR, Microsoft, and Okawa Foundation.     

Toward overcoming culture, skill and situation hurdles in Human-Computer Interaction

This paper proposes a new effective strategy for designing and implementing interactive systems overcoming culture, skill and situation hurdles in Human-Computer Interaction (HCI). The strategy to identify and reduce these hurdles is developed in the framework of a methodology based on a recently introduced model of HCI, and exploits the technological innovations of XML (Extensible Markup Language). HCI is modelled as a cyclic process in which the user and the interactive system communicate by materializing and interpreting a sequence of messages. The interaction process is formalized by specifying both the physical message appearance and the computational aspect of the interaction. This formalization allows the adoption of notation traditionally adopted by users in their workplaces as the starting point of the interactive system design. In this way, the human–system interaction language takes into account the users’ culture. Moreover, the methodology permits user representatives to build a hierarchy of systems progressively adapted to users’ situations, skills and habits, according to the work organization in the domain considered. The strategy is proved to be effective by describing how to implement it using BANCO (Browsing Adaptive Network for Changing user Operativity), a feasibility prototype based on XML, which allows the hierarchy implementation and system adaptations. Several examples from an environmental case under study are used throughout the paper to illustrate the methodology and the effectiveness of the technology adopted. Published online: 4 June 2002     

Personalized, interactive news on the Web

We present Krakatoa Chronicle, an interactive, personalized newspaper on the World Wide Web implemented as a Java applet. The newspaper is similar in appearance to newspapers in the real world, with a multi-column layout and justified text. At the same time, it provides various interaction techniques for browsing the content of articles, giving relevance feedback, and dynamically changing layout. As users interact with the system, individual ‘user profiles’ are built up at the webserver site. These are used to tailor the newspaper's content and layout to each user's declared and inferred preferences. The system allows for a balancing of personal and community interests, allowing the user to navigate through a space of newspapers corresponding to a range of viewpoints.     

Problem-Driven Approach to the Design of Information Technology Systems Supporting Complex Cognitive Tasks

The present paper proposes a methodological framework for the design and evaluation of information technology systems supporting complex cognitive tasks. The aim of the methodological framework is to permit the design of systems which: (1) address the cognitive difficulties met by potential users in performing complex problem-solving tasks; (2) improve their potential users’ problem-solving performance; and (3) achieve compatibility with potential users’ competences and working environment. After a short review of the weaknesses of existing systems supposed to support complex cognitive tasks, the theoretical foundations of the proposed methodology are presented. These are the ergonomic work analysis of French ergonomists, cognitive engineering, cognitive anthropology–ethnomethodology and activity theory. The third section of the paper describes the generic ergonomic model, which constitutes a frame of reference useful for the analyst of the work situation to which the information technology system is addressed. In the fourth section, the proposed methodology is outlined, and in the fifth a case study demonstrating an application of the methodology is summarised. In the epilogue, the differences between the proposed methodological framework and other more conventional approaches are discussed. Finally, directions for future developments of the problem-driven approach are proposed.     

An Evaluation of the Potential of Task Analysis in the Evolution of Interactive Work Systems

Developed forms of task analysis allow designers to focus on both utility and usability issues in the development of interactive work systems. The models they generate represent aspects of the human, computer and domain elements of an interactive work system. Many interactive work systems are embedded in an organisational context. Pressure for changes are present in this context and provide impetus to stakeholders to change work tasks and the supporting tools. Interactive work systems also provide evolutionary pressures of their own, changing the very task they were designed to support. One approach to coping with change has been to evolve interactive work systems. Currently none of these techniques place focus on the performance of tasks as central, and consideration of usability is minimal. However, an evolutionary design approach forces an evolutionary experience upon users, and we cannot be sure whether this approach enhances the user’s experience or degrades their performance. Given the strength of task analysis it is likely that it will be applied within evolutionary contexts. Yet, little work has been undertaken to examine whether its role will, or could be different. We ask how we can move task analysis towards being used in a principled manner in the evolution of interactive work systems. This paper examines a number of features of the approach called task knowledge structures that may be useful in evolving interactive work systems. We look at tasks and their representativeness, roles, goals, objects (their attributes, relationships, typicality and centrality) and actions. We present a developing framework for examining other task analysis approaches for their utility in supporting interactive work systems evolution. Finally, we discuss future work within the area of applying task analysis in the evolution of interactive work systems.     

Linguistic Problems with Requirements and Knowledge Elicitation

Human and conversational aspects of requirements and knowledge identification are employed to show that requirements ‘engineering’ is not the same as civil engineering or scientific problem solving. Not only can requirements not be made fully explicit at the start of a project, they cannot be made fully explicit at all. A need is identified to enhance computer-based information systems (CBIS) development methods to accommodate: plurality of incommensurable perspectives, languages and agendas; dynamic representations of system features that can be experienced rather than abstracted and forced into an abstract paper-based representation; recognition that CBIS development is in general a continuous process where users changing their minds is a natural and necessary indication or organisational vitality.  It is suggested that prototyping and rapid application development go some way to addressing these requirements but that they require further development in the light of the theoretical light thrown on the nature of the problem.     

Managing database server performance to meet QoS requirements in electronic commerce systems

The performance of electronic commerce systems has a major impact on their acceptability to users. Different users also demand different levels of performance from the system, that is, they will have different Quality of Service (QoS) requirements. Electronic commerce systems are the integration of several different types of servers and each server must contribute to meeting the QoS demands of the users. In this paper we focus on the role, and the performance, of a database server within an electronic commerce system. We examine the characteristics of the workload placed on a database server by an electronic commerce system and suggest a range of QoS requirements for the database server based on this analysis of the workload. We argue that a database server must be able to dynamically reallocate its resources in order to meet the QoS requirements of different transactions as the workload changes. We describe Quartermaster, which is a system to support dynamic goal-oriented resource management in database management systems, and discuss how it can be used to help meet the QoS requirements of the electronic commerce database server. We provide an example of the use of Quartermaster that illustrates how the dynamic reallocation of memory resources can be used to meet the QoS requirements of a set of transactions similar to transactions found in an electronic commerce workload. We briefly describe the memory reallocation algorithms used by Quartermaster and present experiments to show the impact of the reallocations on the performance of the transactions. Published online: 22 August 2001     

View management in multimedia databases

Abstract. Though there has been extensive work on multimedia databases in the last few years, there is no prevailing notion of a multimedia view, nor there are techniques to create, manage, and maintain such views. Visualizing the results of a dynamic multimedia query or materializing a dynamic multimedia view corresponds to assembling and delivering an interactive multimedia presentation in accordance with the visualization specifications. In this paper, we suggest that a non-interactive multimedia presentation is a set of virtual objects with associated spatial and temporal presentation constraints. A virtual object is either an object, or the result of a query. As queries may have different answers at different points in time, scheduling the presentation of such objects is nontrivial. We then develop a probabilistic model of interactive multimedia presentations, extending the non-interactive model described earlier. We also develop a probabilistic model of interactive visualization where the probabilities reflect the user profiles, or the likelihood of certain user interactions. Based on this probabilistic model, we develop three utility-theoretic based types of prefetching algorithms that anticipate how users will interact with the presentation. These prefetching algorithms allow efficient visualization of the query results in accordance with the underlying specification. We have built a prototype system that incorporates these algorithms. We report on the results of experiments conducted on top of this implementation. Received June 10, 1998 / Accepted November 10, 1999     

A Location Model for Communicating and Processing of Context

Location is one of the most important elements of context in ubiquitous computing. In this paper we describe a location model, a spatial-aware communication model and an implementation of the models that exploit location for processing and communicating context. The location model presented describes a location tree, which contains human-readable semantic and geometric information about an organisation and a structure to describe the current location of an object or a context. The proposed system is dedicated to work not only on more powerful devices like handhelds, but also on small computer systems that are embedded into everyday artefact (making them a digital artefact). Model and design decisions were made on the basis of experiences from three prototype setups with several applications, which we built from 1998 to 2002. While running these prototypes we collected experiences from designers, implementers and users and formulated them as guidelines in this paper. All the prototype applications heavily use location information for providing their functionality. We found that location is not only of use as information for the application but also important for communicating context. In this paper we introduce the concept of spatial-aware communication where data is communicated based on the relative location of digital artefacts rather than on their identity. Correspondence to: Michael Biegl, Telecooperation Office (TecO), University of Karlsruhe, Vincenz-Prieβritz-Str. 1 D-76131 Karlsruhe, Germany. Email: michael@teco.edu     

People, Information Systems and Change

Information systems are the glue between people and computers. Both the social and business environments are in a continual, some might say chaotic, state of change while computer hardware continues to double its performance about every 18 months. This presents a major challenge for information system developers.  The term user-friendly is an old one, but one which has come to take on a multitude of meanings. However, in today’s context we might well take a user-friendly system to be one where the technology fits the user’s cognitive models of the activity in hand. This article looks at the relationship between information systems and the changing demands of their users as the underlying theme for the current issue of Cognition, Technology and Work.  People, both as individuals and organisations, change. The functionalist viewpoint, which attempts to freeze and inhibit such change, has failed systems developers on numerous occasions. Responding to, and building on, change in the social environment is still a significant research issue for information systems specialists who need to be able to create living information systems.     

New Active Tools for Supporting Narrative Structures

Constructing stories is a type of playing that involves mobilizing the storyteller’s imagination and finding original ways to convey narrative intentions. When a child invents a story, there is a natural interaction with the local environment and the use of various means of expression. We adopted a user-centered approach to design POGO, a playful environment which utilizes the child’s physical environment and sensory modalities. Pogo is a system of active tools that enable children to create stories by connecting physical and virtual environments. By providing children with the possibility of capturing and manipulating images and various media, and combining them in sequential form, Pogo triggered new strategies in the construction of narrative logic, time and space, in the construction of the episodes and in the visual narration. Correspondence to: Fran?oise Decortis, Psychology and Education Sciences Department, University of Liege, 4000 Liege, Belgium. Email:francoise.decortis@ulg.ac.be     

Detecting and reconstructing subdivision connectivity

inverse subdivision algorithms , with linear time and space complexity, to detect and reconstruct uniform Loop, Catmull–Clark, and Doo–Sabin subdivision structure in irregular triangular, quadrilateral, and polygonal meshes. We consider two main applications for these algorithms. The first one is to enable interactive modeling systems that support uniform subdivision surfaces to use popular interchange file formats which do not preserve the subdivision structure, such as VRML, without loss of information. The second application is to improve the compression efficiency of existing lossless connectivity compression schemes, by optimally compressing meshes with Loop subdivision connectivity. Our Loop inverse subdivision algorithm is based on global connectivity properties of the covering mesh, a concept motivated by the covering surface from Algebraic Topology. Although the same approach can be used for other subdivision schemes, such as Catmull–Clark, we present a Catmull–Clark inverse subdivision algorithm based on a much simpler graph-coloring algorithm and a Doo–Sabin inverse subdivision algorithm based on properties of the dual mesh. Straightforward extensions of these approaches to other popular uniform subdivision schemes are also discussed. Published online: 3 July 2002     

Efficient support for interactive scanning operations in MPEG-based video-on-demand systems

In this paper, we present an efficient approach for supporting fast-scanning (FS) operations in MPEG-based video-on-demand (VOD) systems. This approach is based on storing multiple, differently encoded versions of the same movie at the server. A normal version is used for normal playback, while several scan versions are used for FS. Each scan version supports forward and backward FS at a given speedup. The server responds to an FS request by switching from the normal version to an appropriate scan version. Scanning versions are produced by encoding a sample of the raw frames using the same GOP pattern of the normal version. When a scanning version is decoded and played back at the normal frame rate, it gives a perceptual motion speedup. By being able to control the traffic envelopes of the scan versions, our approach can be integrated into a previously proposed framework for distributing archived, MPEG-coded video streams. FS operations are supported using no or little extra network bandwidth beyond what is already allocated for normal playback. Mechanisms for controlling the traffic envelopes of the scan versions are presented. The actions taken by the server and the client's decoder in response to various types of interactive requests are described in detail. The latency incurred in implementing various interactive requests is shown to be within an acceptable range. Striping and disk-scheduling strategies for storing various versions at the server are presented. Issues related to the implementation of our approach are discussed.     

Progressive evaluation of nested aggregate queries

In many decision-making scenarios, decision makers require rapid feedback to their queries, which typically involve aggregates. The traditional blocking execution model can no longer meet the demands of these users. One promising approach in the literature, called online aggregation, evaluates an aggregation query progressively as follows: as soon as certain data have been evaluated, approximate answers are produced with their respective running confidence intervals; as more data are examined, the answers and their corresponding running confidence intervals are refined. In this paper, we extend this approach to handle nested queries with aggregates (i.e., at least one inner query block is an aggregate query) by providing users with (approximate) answers progressively as the inner aggregation query blocks are evaluated. We address the new issues pose by nested queries. In particular, the answer space begins with a superset of the final answers and is refined as the aggregates from the inner query blocks are refined. For the intermediary answers to be meaningful, they have to be interpreted with the aggregates from the inner queries. We also propose a multi-threaded model in evaluating such queries: each query block is assigned to a thread, and the threads can be evaluated concurrently and independently. The time slice across the threads is nondeterministic in the sense that the user controls the relative rate at which these subqueries are being evaluated. For enumerative nested queries, we propose a priority-based evaluation strategy to present answers that are certainly in the final answer space first, before presenting those whose validity may be affected as the inner query aggregates are refined. We implemented a prototype system using Java and evaluated our system. Results for nested queries with a level and multiple levels of nesting are reported. Our results show the effectiveness of the proposed mechanisms in providing progressive feedback that reduces the initial waiting time of users significantly without sacrificing the quality of the answers. Received April 25, 2000 / Accepted June 27, 2000     

The BG distributed simulation algorithm

We present a shared memory algorithm that allows a set of f+1 processes to wait-free “simulate” a larger system of n processes, that may also exhibit up to f stopping failures. Applying this simulation algorithm to the k-set-agreement problem enables conversion of an arbitrary k-fault-tolerant{\it n}-process solution for the k-set-agreement problem into a wait-free k+1-process solution for the same problem. Since the k+1-processk-set-agreement problem has been shown to have no wait-free solution [5,18,26], this transformation implies that there is no k-fault-tolerant solution to the n-process k-set-agreement problem, for any n. More generally, the algorithm satisfies the requirements of a fault-tolerant distributed simulation.\/ The distributed simulation implements a notion of fault-tolerant reducibility\/ between decision problems. This paper defines these notions and gives examples of their application to fundamental distributed computing problems. The algorithm is presented and verified in terms of I/O automata. The presentation has a great deal of interesting modularity, expressed by I/O automaton composition and both forward and backward simulation relations. Composition is used to include a safe agreement\/ module as a subroutine. Forward and backward simulation relations are used to view the algorithm as implementing a multi-try snapshot\/ strategy. The main algorithm works in snapshot shared memory systems; a simple modification of the algorithm that works in read/write shared memory systems is also presented. Received: February 2001 / Accepted: February 2001