Multiresolution volume visualization with a texture-based octree

Although 3D texture-based volume rendering guarantees image quality almost interactively, it is difficult to maintain an interactive rate when the technique has to be exploited on large datasets. In this paper, we propose a new texture memory representation and a management policy that substitute the classical one-texel per voxel approach for a hierarchical approach. The hierarchical approach benefits nearly homogeneous regions and regions of lower interest. The proposed algorithm is based on a simple traversal of the octree representation of the volume data. Driven by a user-defined image quality, defined as a combination of data homogeneity and importance, a set of octree nodes (the cut) is selected to be rendered. The degree of accuracy applied for the representation of each one of the nodes of the cut in the texture memory is set independently according to the user-defined parameters. The variable resolution texture model obtained reduces the texture memory size and thus texture swapping, improving rendering speed.     

Motion compensated film restoration

Motion picture films are susceptible to local degradations such as dust spots. Other deteriorations are global such as intensity and spatial jitter. It is obvious that motion needs to be compensated for before the detection/correction of such local and dynamic defects. Therefore, we propose a hierarchical motion estimation method ideally suited for high resolution film sequences. This recursive block-based motion estimator relies on an adaptive search strategy and Radon projections to improve processing speed. The localization of dust particles then becomes straightforward. Thus, it is achieved by simple inter-frame differences between the current image and motion compensated successive and preceding frames. However, the detection of spatial and intensity jitter requires a specific process taking advantage of the high temporal correlation in the image sequence. In this paper, we present our motion compensation-based algorithms for removing dust spots, spatial and intensity jitter in degraded motion pictures. Experimental results are presented showing the usefulness of our motion estimator for film restoration at reasonable computational costs. Received: 9 July 2000 / Accepted: 13 January 2002 Correspondence to:S. Boukir     

Effective timestamping in databases

Many existing database applications place various timestamps on their data, rendering temporal values such as dates and times prevalent in database tables. During the past two decades, several dozen temporal data models have appeared, all with timestamps being integral components. The models have used timestamps for encoding two specific temporal aspects of database facts, namely transaction time, when the facts are current in the database, and valid time, when the facts are true in the modeled reality. However, with few exceptions, the assignment of timestamp values has been considered only in the context of individual modification statements. This paper takes the next logical step: It considers the use of timestamping for capturing transaction and valid time in the context of transactions. The paper initially identifies and analyzes several problems with straightforward timestamping, then proceeds to propose a variety of techniques aimed at solving these problems. Timestamping the results of a transaction with the commit time of the transaction is a promising approach. The paper studies how this timestamping may be done using a spectrum of techniques. While many database facts are valid until now, the current time, this value is absent from the existing temporal types. Techniques that address this problem using different substitute values are presented. Using a stratum architecture, the performance of the different proposed techniques are studied. Although querying and modifying time-varying data is accompanied by a number of subtle problems, we present a comprehensive approach that provides application programmers with simple, consistent, and efficient support for modifying bitemporal databases in the context of user transactions. Received: March 11, 1998 / Accepted July 27, 1999     

Indexing of now-relative spatio-bitemporal data

Real-world entities are inherently spatially and temporally referenced, and database applications increasingly exploit databases that record the past, present, and anticipated future locations of entities, e.g., the residences of customers obtained by the geo-coding of addresses. Indices that efficiently support queries on the spatio-temporal extents of such entities are needed. However, past indexing research has progressed in largely separate spatial and temporal streams. Adding time dimensions to spatial indices, as if time were a spatial dimension, neither supports nor exploits the special properties of time. On the other hand, temporal indices are generally not amenable to extension with spatial dimensions. This paper proposes the first efficient and versatile index for a general class of spatio-temporal data: the discretely changing spatial aspect of an object may be a point or may have an extent; both transaction time and valid time are supported, and a generalized notion of the current time, now, is accommodated for both temporal dimensions. The index is based on the R-tree and provides means of prioritizing space versus time, which enables it to adapt to spatially and temporally restrictive queries. Performance experiments are reported that evaluate pertinent aspects of the index. Edited by T. Sellis. Received: 7 December 2000 / Accepted: 1 September 2001 Published online: 18 December 2001     

HMAP– A temporal data model managing intervals with different granularities and indeterminacy from natural language sentences

The granularity of given temporal information is the level of abstraction at which information is expressed. Different units of measure allow one to represent different granularities. Indeterminacy is often present in temporal information given at different granularities: temporal indeterminacy is related to incomplete knowledge of when the considered fact happened. Focusing on temporal databases, different granularities and indeterminacy have to be considered in expressing valid time, i.e., the time at which the information is true in the modeled reality. In this paper, we propose HMAP (The term is the transliteration of an ancient Greek poetical word meaning “day”.), a temporal data model extending the capability of defining valid times with different granularity and/or with indeterminacy. In HMAP, absolute intervals are explicitly represented by their start,end, and duration: in this way, we can represent valid times as “in December 1998 for five hours”, “from July 1995, for 15 days”, “from March 1997 to October 15, 1997, between 6 and 6:30 p.m.”. HMAP is based on a three-valued logic, for managing uncertainty in temporal relationships. Formulas involving different temporal relationships between intervals, instants, and durations can be defined, allowing one to query the database with different granularities, not necessarily related to that of data. In this paper, we also discuss the complexity of algorithms, allowing us to evaluate HMAP formulas, and show that the formulas can be expressed as constraint networks falling into the class of simple temporal problems, which can be solved in polynomial time. Received 6 August 1998 / Accepted 13 July 2000 Published online: 13 February 2001     

A hierarchical representation of form documents for identification and retrieval

In this paper, we present a logical representation for form documents to be used for identification and retrieval. A hierarchical structure is proposed to represent the structure of a form by using lines and the XY-tree approach. The approach is top-down and no domain knowledge such as the preprinted data or filled-in data is used. Geometrical modifications and slight variations are handled by this representation. Logically identical forms are associated to the same or similar hierarchical structure. Identification and the retrieval of similar forms are performed by computing the edit distances between the generated trees. Received: August 21, 2001 / Accepted: November 5, 2001     

A case study towards validation of global illumination algorithms: progressive hierarchical radiosity with clustering

In this paper, we present an efficient global illumination technique, and then we discuss the results of its extensive experimental validation. The technique is a hybrid of cluster-based hierarchical and progressive radiosity techniques, which does not require storing links between interacting surfaces and clusters. We tested our technique by applying a multistage validation procedure, which we designed specifically for global illumination solutions. First, we experimentally validate the algorithm against analytically derived and measured real-world data to check how calculation speed is traded for lighting simulation accuracy for various clustering and meshing scenarios. Then we test the algorithm performance and rendering quality by directly comparing the virtual and real-world images of a complex environment.     

Password hardening based on keystroke dynamics

We present a novel approach to improving the security of passwords. In our approach, the legitimate user’s typing patterns (e.g., durations of keystrokes and latencies between keystrokes) are combined with the user’s password to generate a hardened password that is convincingly more secure than conventional passwords alone. In addition, our scheme automatically adapts to gradual changes in a user’s typing patterns while maintaining the same hardened password across multiple logins, for use in file encryption or other applications requiring a long-term secret key. Using empirical data and a prototype implementation of our scheme, we give evidence that our approach is viable in practice, in terms of ease of use, improved security, and performance. Published online: 26 October 2001     

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     

Defect detection in textured surfaces using color ring-projection correlation

In this paper, we present a correlation scheme that incorporates a color ring-projection representation for the automatic inspection of defects in textured surfaces. The proposed color ring projection transforms a 2-D color image into a 1-D color pattern as a function of radius. For a search window of width W, data dimensionality is reduced from in the 2-D image to O(W) in the 1-D ring-projection space. The complexity of computing a correlation function is significantly reduced accordingly. Since the color ring-projection representation is invariant to rotation, the proposed method can be applied for both isotropic and oriented textures at arbitrary orientations. Experiments on regular textured surfaces have shown the efficacy of the proposed method. Received: 30 March 2000 / Accepted: 24 July 2001 Correspondence to: D.-M. Tsai (e-mail: iedmtsai@saturn.yzu.edu.tw)     

Efficiently publishing relational data as XML documents

XML is rapidly emerging as a standard for exchanging business data on the World Wide Web. For the foreseeable future, however, most business data will continue to be stored in relational database systems. Consequently, if XML is to fulfill its potential, some mechanism is needed to publish relational data as XML documents. Towards that goal, one of the major challenges is finding a way to efficiently structure and tag data from one or more tables as a hierarchical XML document. Different alternatives are possible depending on when this processing takes place and how much of it is done inside the relational engine. In this paper, we characterize and study the performance of these alternatives. Among other things, we explore the use of new scalar and aggregate functions in SQL for constructing complex XML documents directly in the relational engine. We also explore different execution plans for generating the content of an XML document. The results of an experimental study show that constructing XML documents inside the relational engine can have a significant performance benefit. Our results also show the superiority of having the relational engine use what we call an “outer union plan” to generate the content of an XML document. Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 28 June 2001     

Concurrency control in hierarchical multidatabase systems

Over the past decade, significant research has been done towards developing transaction management algorithms for multidatabase systems. Most of this work assumes a monolithic architecture of the multidatabase system with a single software module that follows a single transaction management algorithm to ensure the consistency of data stored in the local databases. This monolithic architecture is not appropriate in a multidatabase environment where the system spans multiple different organizations that are distributed over various geographically distant locations. In this paper, we propose an alternative multidatabase transaction management architecture, where the system is hierarchical in nature. Hierarchical architecture has consequences on the design of transaction management algorithms. An implication of the architecture is that the transaction management algorithms followed by a multidatabase system must be composable– that is, it must be possible to incorporate individual multidatabase systems as elements in a larger multidatabase system. We present a hierarchical architecture for a multidatabase environment and develop techniques for concurrency control in such systems. Edited by R. Sacks-Davis. Received June 27, 1994 / Accepted September 26, 1995     

MING-I: a distributed interactive multimedia document development mechanism

The next generation of interactive multimedia documents can contain both static media, e.g., text, graph, image, and continuous media, e.g., audio and video, and can provide user interactions in distributed environments. However, the temporal information of multimedia documents cannot be described using traditional document structures, e.g., Open Document Architecture (ODA) and Standard Generalized Mark-up Language (SGML); the continuous transmission of media units also raises some new synchronization problems, which have not been met before, for processing user interactions. Thus, developing a distributed interactive multimedia document system should resolve the issues of document model, presentation control architecture, and control scheme. In this paper, we (i) propose a new multimedia document model that contains the logical structure, the layout structure, and the temporal structure to formally describe multimedia documents, and (ii) point out main interaction-based synchronization problems, and propose a control architecture and a token-based control scheme to solve these interaction-based synchronization problems. Based on the proposed document model, control architecture, and control scheme, a distributed interactive multimedia document development mechanism, which is called MING-I, is developed on SUN workstations.     

Searching in metric spaces by spatial approximation

We propose a new data structure to search in metric spaces. A metric space is formed by a collection of objects and a distance function defined among them which satisfies the triangle inequality. The goal is, given a set of objects and a query, retrieve those objects close enough to the query. The complexity measure is the number of distances computed to achieve this goal. Our data structure, called sa-tree (“spatial approximation tree”), is based on approaching the searched objects spatially, that is, getting closer and closer to them, rather than the classic divide-and-conquer approach of other data structures. We analyze our method and show that the number of distance evaluations to search among n objects is sublinear. We show experimentally that the sa-tree is the best existing technique when the metric space is hard to search or the query has low selectivity. These are the most important unsolved cases in real applications. As a practical advantage, our data structure is one of the few that does not need to tune parameters, which makes it appealing for use by non-experts. Edited by R. Sacks-Davis Received: 17 April 2001 / Accepted: 24 January 2002 / Published online: 14 May 2002     

Interval routing schemes allow broadcasting with linear message-complexity

Summary. The purpose of compact routing is to provide a labeling of the nodes of a network and a way to encode the routing tables, so that routing can be performed efficiently (e.g., on shortest paths) whilst keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing may also assist in the performance of distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows broadcasting with a message-complexity of O(n), where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving the previous known bound of O(m+n). A general consequence of our result is that a shortest path interval routing scheme contains ample structural information to avoid developing ad-hoc or network-specific solutions for basic problems that distributed systems must handle repeatedly. Received: December 2000 / Accepted: July 2001     

Extracting characters of license plates from video sequences

In this paper, we present a new approach to extract characters on a license plate of a moving vehicle, given a sequence of perspective-distortion-corrected license plate images. Different from many existing single-frame approaches, our method simultaneously utilizes spatial and temporal information. We first model the extraction of characters as a Markov random field (MRF), where the randomness is used to describe the uncertainty in pixel label assignment. With the MRF modeling, the extraction of characters is formulated as the problem of maximizing a posteriori probability based on a given prior knowledge and observations. A genetic algorithm with local greedy mutation operator is employed to optimize the objective function. Experiments and comparison study were conducted and some of our experimental results are presented in the paper. It is shown that our approach provides better performance than other single frame methods. Received: 13 August 1997 / Accepted: 7 October 1997     

Tracking the human arm using constraint fusion and multiple-cue localization

Abstract. The use of hand gestures provides an attractive means of interacting naturally with a computer-generated display. Using one or more video cameras, the hand movements can potentially be interpreted as meaningful gestures. One key problem in building such an interface without a restricted setup is the ability to localize and track the human arm robustly in video sequences. This paper proposes a multiple-cue localization scheme combined with a tracking framework to reliably track the dynamics of the human arm in unconstrained environments. The localization scheme integrates the multiple cues of motion, shape, and color for locating a set of key image features. Using constraint fusion, these features are tracked by a modified extended Kalman filter that exploits the articulated structure of the human arm. Moreover, an interaction scheme between tracking and localization is used for improving the estimation process while reducing the computational requirements. The performance of the localization/tracking framework is validated with the help of extensive experiments and simulations. These experiments include tracking with calibrated stereo camera and uncalibrated broadcast video. Received: 19 January 2001 / Accepted: 27 December 2001 Correspondence to: R. Sharma     

The reconstruction of dynamic 3D structure of biological objects using stereo microscope images

In this paper, we address the analysis of 3D shape and shape change in non-rigid biological objects imaged via a stereo light microscope. We propose an integrated approach for the reconstruction of 3D structure and the motion analysis for images in which only a few informative features are available. The key components of this framework are: 1) image registration using a correlation-based approach, 2) region-of-interest extraction using motion-based segmentation, and 3) stereo and motion analysis using a cooperative spatial and temporal matching process. We describe these three stages of processing and illustrate the efficacy of the proposed approach using real images of a live frog's ventricle. The reconstructed dynamic 3D structure of the ventricle is demonstrated in our experimental results, and it agrees qualitatively with the observed images of the ventricle.