Interactive authoring of multimedia documents in a constraint-based authoring system

As multimedia applications spread widely, it is crucial for programming and design support systems to handle “time” in multimedia documents effectively and flexibly. This paper presents a set of interactive system support tools for designing and maintaining the temporal behavior of multimedia documents. The tool set provides mechanisms for anomaly detection, temporal query processing, and interactive scheduling. It is based on a fast incremental constraint solver we have developed, which can be adapted by any constraint-based system. The incremental constraint solver provides immediate feedback to the user, supporting a highly interactive design process. Combined with existing optimal layout generation mechanisms proposed in the literature, our tools effectively utilize the flexibility provided by constraint-based systems.     

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.     

Adaptive multimedia synchronization in a teleconference system

In this paper, we present an adaptive buffering scheme for implementing intra-stream and inter-stream synchronization in real-time multimedia applications. The essence of the proposed scheme is to dynamically enforce equalized delays to incoming media streams, in order to piece-wise smooth the network delay variations and to synchronize the streams at the sink. An adaptive control mechanism based on an event-counting algorithm is employed to calibrate the PlayOut Clocks (POCs), which manages the presentations of multimedia data. The algorithm does not rely on globally synchronized clock and makes minimal assumption on underlying network delay distribution. Also, the user defined quality of service (QoS) specifications can be directly incorporated into the design parameters of the synchronization algorithm. The proposed synchronization scheme has been experimentally implemented in a teleconference system which consists of separately controllable audio, video, and data channels. The modular structure of the synchronization control provides the flexibility to maintain an arbitrary synchronization group in conjunction with a distributed conference management scheme. This paper also shows the experimental results of the test implementation and the suitability of the proposed scheme with respect to the multimedia traffic across an FDDI/Ethernet network.     

A computer-based system to support forensic studies on handwritten documents

Computer-based forensic handwriting analysis requires sophisticated methods for the pre-processing of digitized paper documents, in order to provide high-quality digitized handwriting, which represents the original handwritten product as accurately as possible. Due to the requirement of processing a huge amount of different document types, neither a standardized queue of processing stages, fixed parameter sets nor fixed image operations are qualified for such pre-processing methods. Thus, we present an open layered framework that covers adaptation abilities at the parameter, operator, and algorithm levels. Moreover, an embedded module, which uses genetic programming, might generate specific filters for background removal on-the-fly. The framework is understood as an assistance system for forensic handwriting experts and has been in use by the Bundeskriminalamt, the federal police bureau in Germany, for two years. In the following, the layered framework will be presented, fundamental document-independent filters for textured, homogeneous background removal and for foreground removal will be described, as well as aspects of the implementation. Results of the framework-application will also be given. Received July 12, 2000 / Revised October 13, 2000     

An empirical measure of the performance of a document image segmentation algorithm

Document image segmentation is the first step in document image analysis and understanding. One major problem centres on the performance analysis of the evolving segmentation algorithms. The use of a standard document database maintained at the Universities/Research Laboratories helps to solve the problem of getting authentic data sources and other information, but some methodologies have to be used for performance analysis of the segmentation. We describe a new document model in terms of a bounding box representation of its constituent parts and suggest an empirical measure of performance of a segmentation algorithm based on this new graph-like model of the document. Besides the global error measures, the proposed method also produces segment-wise details of common segmentation problems such as horizontal and vertical split and merge as well as invalid and mismatched regions. Received July 14, 2000 / Revised June 12, 2001[-1mm]     

Control of perceived quality of service in multimedia retrieval services: prediction-based mechanism vs. compensation buffers

In multimedia systems end-to-end delay jitter has a great impact on the continuity of information playback. Therefore, it is necessary to introduce appropriate mechanisms to compensate for delay variations, so that the intramedia and intermedia temporal relationships can be preserved. In this paper, two methods for compensation of the network delay jitter in a distributed multimedia retrieval service are compared: the first is based on prediction of the network delay jitter suffered by each information unit and retrieval time modification at the source site; the second is based on a compensation buffer at the destination site. Comparison is made by assuming a master/slave relationship between the monomedia streams composing the multimedia data flow.     

Increasing multimedia system throughput with consumption-based buffer management

In a multimedia server, multiple media streams are generally serviced in a cyclic fashion. Due to non-uniform playback rates and asynchronous arrivals of queries, there tends to be spare disk bandwidth in each service cycle. In this paper, we study the issue of dynamically using spare disk bandwidth and buffer to maximize the system throughput of a multimedia server. We introduce the concept of minimizing buffer consumption as the criterion to select an appropriate media stream to utilize the spare system resources. Buffer consumption measures not only the amount of buffer but also the amount of time such buffer space is occupied (i.e., the space-time product). Different alternatives to utilizing spare disk bandwidth are examined, including different rate-adjustable retrievals of an already activated stream and prefetching the next waiting stream. For rate-adjustable retrievals, we study buffer consumption-based and remaining-time-based criteria for selecting an active stream to increase retrievals. Simulations are conducted to evaluate and compare different cases. The results show that (1) minimizing buffer consumption is the right criterion for maximizing the system throughput with spare disk bandwidth; (2) in general, prefetching a waiting stream incurs more buffer consumption, and thus is less effective than rate-adjustable retrieval of active streams in maximizing the system throughput; and (3) the advantage of rate-adjustable retrieval over prefetching is especially significant when service cycle time is small.     

Exploring relations among college students’ prior knowledge,implicit theories of intelligence,and self-regulated learning in a hypermedia environment

Researchers and educators continue to explore how to assist students in the acquisition of conceptual understanding of complex science topics. While hypermedia learning environments (HLEs) afford unique opportunities to display multiple representations of these often abstract topics, students who do not engage in self-regulated learning (SRL) with HLEs often fail to achieve conceptual understanding. There is a lack of research regarding how student characteristics, such as prior knowledge and students’ implicit theory of intelligence (ITI), interact with SRL to influence academic performance. In this study, structural equation modeling was used to investigate these issues. It was found that prior knowledge and ITI were related to SRL and performance, and that SRL acted as a benevolent moderator, enhancing the positive effects of prior knowledge upon learning, and diminishing the negative effects of having a maladaptive ITI.     

A complete system for the intelligent interpretation of engineering drawings

Converting paper-based engineering drawings into CAD model files is a tedious process. Therefore, automating the conversion of such drawings represents tremendous time and labor savings. We present a complete system which interprets such 2D paper-based engineering drawings, and outputs 3D models that can be displayed as wireframes. The system performs the detection of dimension sets, the extraction of object lines, and the assembly of 3D objects from the extracted object lines. A knowledge-based method is used to remove dimension sets and text from ANSI engineering drawings, a graphics recognition procedure is used to extract complete object lines, and an evidential rule-based method is utilized to identify view relationships. While these methods are the subject of several of our previous papers, this paper focuses on the 3D interpretation of the object. This is accomplished using a technique based on evidential reasoning and a wide range of rules and heuristics. The system is limited to the interpretation of objects composed of planar, spherical, and cylindrical surfaces. Experimental results are presented. Received December 2, 1998 / Revised June 18, 1999     

Structured document storage and refined declarative and navigational access mechanisms in HyperStorM

The combination of SGML and database technology allows to refine both declarative and navigational access mechanisms for structured document collection: with regard to declarative access, the user can formulate complex information needs without knowing a query language, the respective document type definition (DTD) or the underlying modelling. Navigational access is eased by hyperlink-rendition mechanisms going beyond plain link-integrity checking. With our approach, the database-internal representation of documents is configurable. It allows for an efficient implementation of operations, because DTD knowledge is not needed for document structure recognition. We show how the number of method invocations and the cost of parsing can be significantly reduced. Edited by Y.C. Tay. Received April 22, 1996 / Accepted March 16, 1997     

Issues in the design of a storage server for video-on-demand

We examine issues related to the design of a storage server for video-on-demand (VOD) applications. The storage medium considered is magnetic disks or arrays of disks. We investigate disk scheduling policies, buffer management policies and I/O bus protocol issues. We derive the number of sessions that can be supported from a single disk or an array of disks and determine the amount of buffering required to support a given number of users. Furthermore, we propose a scheduling mechanism for disk accesses that significantly lowers the buffer-size requirements in the case of disk arrays. The buffer size required under the proposed scheme is independent of the number of disks in the array. This property allows for striping video content over a large number of disks to achieve higher concurrency in access to a particular video object. This enables the server to satisfy hundreds of independent requests to the same video object or to hundreds of different objects while storing only one copy of each video object. The reliability implications of striping content over a large number of disks are addressed and two solutions are proposed. Finally, we examine various policies for dealing with disk thermal calibration and the placement of videos on disks and disk arrays.     

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     

Disk placement for arbitrary-rate playback in an interactive video server

Multimedia data, especially continuous media including video and audio objects, represent a rich and natural stimulus for humans, but require large amount of storage capacity and real-time processing. In this paper, we describe how to organize video data efficiently on multiple disks in order to support arbitrary-rate playback requested by different users independently. Our approach is to segment and decluster video objects and to place the segments in multiple disks using a restricted round-robin scheme, called prime round-robin (PRR). Its placement scheme provides uniform load balance of disks for arbitrary retrieval rate as well as normal playback, since it eliminates hot spots. Moreover, it does not require any additional disk bandwidth to support VCR-like operations such as fast-forward and rewind. We have studied the various effects of placement and retrieval schemes in a storage server by simulation. The results show that PRR offers even disk accesses, and the failure in reading segment by deadline occurs only at the beginning of new operations. In addition, the number of users admitted is not decreased, regardless of arbitrary-rate playback requests.     

A stereovision system for a planetary rover: calibration, correlation, registration, and fusion

This paper describes a complete stereovision system, which was originally developed for planetary applications, but can be used for other applications such as object modeling. A new effective on-site calibration technique has been developed, which can make use of the information from the surrounding environment as well as the information from the calibration apparatus. A correlation-based stereo algorithm is used, which can produce sufficient dense range maps with an algorithmic structure for fast implementations. A technique based on iterative closest-point matching has been developed for registration of successive depth maps and computation of the displacements between successive positions. A statistical method based on the distance distribution is integrated into this registration technique, which allows us to deal with such important problems as outliers, occlusion, appearance, and disappearance. Finally, the registered maps are expressed in the same coordinate system and are fused, erroneous data are eliminated through consistency checking, and a global digital elevation map is built incrementally.     

Real-time spatial processing of sounds for music, multimedia and interactive human-computer interfaces

This paper gives an overview of the principles and methods for synthesizing complex 3D sound scenes by processing multiple individual source signals. Signal-processing techniques for directional sound encoding and rendering over loudspeakers or headphones are reviewed, as well as algorithms and interface models for synthesizing and dynamically controling room reverberation and distance effects. A real-time modular spatial-sound-processing software system, called Spat, is presented. It allows reproducing and controling the localization of sound sources in three dimensions and the reverberation of sounds in an existing or virtual space. A particular aim of the Spatialisateur project is to provide direct and computationally efficient control over perceptually relevant parameters describing the interaction of each sound source with the virtual space, irrespective of the chosen reproduction format over loudspeakers or headphones. The advantages of this approach are illustrated in practical contexts, including professional audio, computer music, multimodal immersive simulation systems, and architectural acoustics.     

Merging video streams in a multimedia storage server: complexity and heuristics

Due to recent advances in network, storage and data compression technologies, video-on-demand (VOD) service has become economically feasible. It is a challenging task to design a video storage server that can efficiently service a large number of concurrent requests on demand. One approach to accomplishing this task is to reduce the I/O demand to the VOD server through data- and resource-sharing techniques. One form of data sharing is the stream-merging approach proposed in [5]. In this paper, we formalize a static version of the stream-merging problem, derive an upper bound on the I/O demand of static stream merging, and propose efficient heuristic algorithms for both static and dynamic versions of the stream-merging problem.     

A multi-level abstraction and modeling in video databases

In this paper, we propose a multi-level abstraction mechanism for capturing the spatial and temporal semantics associated with various objects in an input image or in a sequence of video frames. This abstraction can manifest itself effectively in conceptualizing events and views in multimedia data as perceived by individual users. The objective is to provide an efficient mechanism for handling content-based queries, with the minimum amount of processing performed on raw data during query evaluation. We introduce a multi-level architecture for video data management at different levels of abstraction. The architecture facilitates a multi-level indexing/searching mechanism. At the finest level of granularity, video data can be indexed based on mere appearance of objects and faces. For management of information at higher levels of abstractions, an object-oriented paradigm is proposed which is capable of supporting domain specific views.     

Transformation and exchange of multimedia objects in distributed multimedia systems

One of the challenges in the design of a distributed multimedia system is devising suitable specification models for various schemas in different levels of the system. Another important research issue is the integration and synchronization of heterogeneous multimedia objects. In this paper, we present our models for multimedia schemas and transformation algorithms. They transform high-level multimedia objects into schemas that can be used to support the presentation and communication of the multimedia objects. A key module in the system is the Object Exchange Manager (OEM). In this paper, we present the design and implementation of the OEM module, and discuss in detail the interaction between the OEM and other modules in a distributed multimedia system.