There has been increasing interest in 3D geometry compression. One reason is that the insufficient bandwidth between the graphics pipeline and the main memory is not able to handle the huge amount of 3D graphics data transferred between these two components. A variation of open-loop linear predictive quantization (OLPQ), a widely used but not well-studied coding technique, was proposed to become the geometry coding technique of MPEG4 3D model coding (3DMC). We compare the performance of OLPQ with the well-understood differential pulse code modulation (DPCM). Our results show that DPCM does not outperform OLPQ in the coding of vertex coordinates of 3D objects in the rate-distortion sense. Such results together with the lower complexity of OLPQ makes OLPQ a better geometry coding technique than DPCM.

We present a new approach for faster rendering of large synthetic environments using video-based representations. We decompose the large environment into cells and pre-compute video based impostors using MPEG compression to represent sets of objects that are far from each cell. At runtime, we decode the MPEG streams and use rendering algorithms that provide nearly constant-time random access to any frame. The resulting system has been implemented and used for an interactive walkthrough of a model of a house with 260,000 polygons and realistic lighting and textures. It is able to render this model at 16 frames per second (an eightfold improvement over simpler algorithms) on average on a Pentium II PC with an off-the-shelf graphics card.

The ability to construct intracoded frame from motion-compensated intercoded frames directly in the compressed domain is important for efficient video manipulation and composition. In the context of motion-compensated discrete cosine transform (DCT)-based coding of video as in MPEG video, this problem of DCT-domain inverse motion compensation has been studied and, subsequently, improved faster algorithms were proposed. These schemes, however, treat each 8/spl times/8 block as a fundamental unit, and do not take into account the fact that in MPEG, a macroblock consists of several such blocks. We show how shared information within a macroblock, such as a motion vector and common blocks, can be exploited to yield substantial speedup in computation. Compared to previous brute-force approaches, our algorithms yield about 44% improvement. Our technique is independent of the underlying computational or processor model, and thus can be implemented on top of any optimized solution. We demonstrate an improvement by about 19%, and 13.5% in the worst case, on top of the optimized solutions presented in existing literature.

MPEG-2 video standards are targeted for high-quality video broadcast and distribution and are optimized for efficient storage and transmission. However, it is difficult to process MPEG-2 for video browsing and database applications without first decompressing the video. Yeo and Liu (1995) have proposed fast algorithms for the direct extraction of spatially reduced images from MPEG-1 video. Reduced images have been demonstrated to be effective for shot detection, shot browsing and editing, and temporal processing of video for video presentation and content annotation. In this paper, we develop new tools to handle the extra complexity in MPEG-2 video for extracting spatially reduced images. In particular, we propose new classes of discrete cosine transform (DCT) domain and DCT inverse motion compensation operations for handling the interlaced modes in the different frame types of MPEG-2, and we design new and efficient algorithms for generating spatially reduced images of an MPEG-2 video. The algorithms proposed in this paper are fundamental for efficient and effective processing of MPEG-2 video.

In extended video sequences, individual frames are grouped into shots which are defined as a sequence taken by a single camera, and related shots are grouped into scenes which are defined as a single dramatic event taken by a small number of related cameras. This hierarchical structure is deliberately constructed, dictated by the limitations and preferences of the human visual and memory systems. We present three novel high-level segmentation results derived from these considerations, some of which are analogous to those involved in the perception of the structure of music. First and primarily, we derive and demonstrate a method for measuring probable scene boundaries, by calculating a short term memory-based model of shot-to-shot "coherence". The detection of local minima in this continuous measure permits robust and flexible segmentation of the video into scenes, without the necessity for first aggregating shots into clusters. Second, and independently of the first, we then derive and demonstrate a one-pass on-the-fly shot clustering algorithm. Third, we demonstrate partially successful results on the application of these two new methods to the next higher, "theme", level of video structure.

There have been many works on watermarking of 2D images and video. However, watermarking of three-dimensional (3D) objects has received little attentions. We introduce and investigate the watermarking of three-dimensional (3D) objects as compared to 2D images, study the watermarking of objects represented by polygonal models, and propose a new fragile watermarking technique that enables the verification of 3D polygonal models for detecting unauthorized alterations. Our proposed technique consists of a watermark encoding process which embeds a sequence of data bits by perturbing coordinates of the vertices in a 3D model, and a watermark decoding process which extracts bit information from 3D geometry, using secure verification keys. Fast 2D visualization of unauthorized modification to 3D objects is also proposed.

Digital watermarks have been proposed as a means for copyright protection of multimedia data. We address the capability of invisible watermarking schemes to resolve copyright ownership. We show that, in certain applications, rightful ownership cannot be resolved by current watermarking schemes alone. Specifically, we attack existing techniques by providing counterfeit watermarking schemes that can be performed on a watermarked image to allow multiple claims of rightful ownership. In the absence of standardization and specific requirements imposed on watermarking procedures, anyone can claim ownership of any watermarked image. In order to protect against the counterfeiting techniques that we develop, we examine the properties necessary for resolving ownership via invisible watermarking. We introduce and study invertibility and quasi-invertibility of invisible watermarking techniques. We propose noninvertible watermarking schemes, and subsequently give examples of techniques that we believe to be nonquasi-invertible and hence invulnerable against more sophisticated attacks proposed in the paper. The attacks and results presented in the paper, and the remedies proposed, further imply that we have to carefully reevaluate the current approaches and techniques in invisible watermarking of digital images based on application domains, and rethink the promises, applications and implications of such digital means of copyright protection.

Invertible wavelet transforms that map integers to integers are important for lossless representations. We present an approach to build integer to integer wavelet transforms based upon the idea of factoring wavelet transforms into lifting steps. This allows the construction of an integer version of every wavelet transform. We demonstrate the use of these transforms in lossless image compression.

We shall show that non-invertibility is a necessary but not sufficient condition in resolving ownership disputes. We then define quasi-invertible watermarking schemes, and, present analysis that links invertibility and quasi-invertibility to some classes of watermarking techniques with different properties (which may or may not require original versions in watermark decoding), as well as to the different classes of attacks we have developed.

We are witnessing today increasing use and popularity of digital video, from CD ROMs, Internet to digital TV broadcast. However as with analog video, these applications treat video as a sequence of moving images and the primary means of playback is sequential in nature, from the first to last frame. We describe new applications of creating and using digital video and discuss new paradigms of analysis and synthesis that spearheaded these applications. We highlight research issues and directions in and beyond image processing on the analysis and synthesis of digital video for a new generation of applications.

Digital video archives are likely to be accessible on distributed networks which means that the data are subject to network congestion and bandwidth constraints. To enable new applications and services of digital video, it is not only important to develop tools to analyze and browse video, view query results, and formulate better searches, but also to deliver the essence of the material in compact forms. Video visualization describes the joint process of analyzing video and the subsequent derivation of representative visual presentation of the essence of the content. We propose techniques to analyze video and build a compact pictorial summary for visual presentation. A video sequence is thus condensed into a few images-each summarizing the dramatic incident taking place in a meaningful segment of the video. In particular, we present techniques to differentiate the dominance of the content in subdivisions of the segment based on analysis results, select a graphic layout pattern according to the relative dominances, and create a set of video posters, each of which is a compact, visually pleasant, and intuitive representation of the story content. The collection of video posters arranged in temporal order then forms a pictorial summary of the sequence to tell the underlying story. The techniques and compact presentations proposed offer valuable tools for new applications and services of digital video including video browsing, query, search, and retrieval in the digital libraries and over the Internet.

Many video programs have story structures that can be recognized through the clustering of video contents based on low-level visual primitives, and the analysis of high level structures imposed by temporal arrangement of composing elements. In this paper time-constrained clustering of video shots is proposed to collapse visually similar and temporally local shots into a compact structure. We show that the proposed clustering formulations, when incorporated into the scene transition graph framework, allows the automatic segmentation of scenes and story units that cannot be achieved by existing shot boundary detection schemes. The proposed method is able to decompose video into meaningful hierarchies and provide compact representations that reflect the flow of story, thus offering efficient browsing and organization of video.

Reduced images formed from the collection of DC coefficients in intra-coded DCT compressed video retain a "global" feature which is useful for processing purposes. This paper examines the direct reconstruction of such DC images from motion-compensated P-frames and B-frames of MPEG compressed video. Exact expressions are derived and approximations are given for the computational speedup. The analysis and experimental results show that the approximations yield images that are very close to the true ones.

Abstract This paper describes the implementation of a constraint‐based parser, PARSEC (Parallel ARchitecture SEntence Constrainer), which has the required flexibility that a user may easily construct a custom grammar and test it. Once the user designs grammar parameters, constraints, and a lexicon, our system checks them for consistency and creates a parser for the grammar. The parser has an X‐windows interface that allows a user to view the state of a parse of a sentence, test new constraints, and dump the constraint network to a file. The parser has an option to perform the computationally expensive constraint propagation steps on the MasPar MP‐1. Stream and socket communication was used to interface the MasPar constraint parser with a standard X‐windows interface on our Sun Sparcstation. The design of our heterogeneous parser has benefitted from the use of object‐oriented techniques. Without these techniques, it would have been more difficult to combine the processing power of the MasPar with a Sun Sparcstation. Also, these techniques allowed the parser to gracefully evolve from a system that operated on single sentences, to one capable of processing word graphs containing multiple sentences, consistent with speech processing. This system should provide an important component of a real‐time speech understanding system.

Several rapid scene analysis algorithms for detecting scene changes and flashlight scenes directly on compressed video are proposed. These algorithms operate on the DC sequence which can be readily extracted from video compressed using Motion JPEG or MPEG without full-frame decompression. The DC images occupy only a small fraction of the original data size while retaining most of the essential "global" information. Operating on these images offers a significant computation saving. Experimental results show that the proposed algorithms are fast and effective in detecting abrupt scene changes, gradual transitions including fade-ins and fade-outs, flashlight scenes and in deriving intrashot variations.

The paper proposes a scheme to perform volume rendering from compressed scalar data. Instead of decompressing the entire data set before rendering, blocks of data are decompressed as needed. Discrete cosine transform based compression technique is used to illustrate the method. The data is partitioned into overlapping blocks to permit local rendering and allow easy parallelization. Compression by factor of 20 to 30 produces rendering virtually indistinguishable from rendering using the original uncompressed data. Speedup is obtained by making use of spatial homogeneity detected in the transform domain. Rendering time using the proposed approach is less than that of direct rendering from the entire uncompressed data. The proposed method thus offers an attractive option to reduce storage, computation, and transmission overhead of otherwise huge data sets.>

This paper presents a 3D image registration approach to 3D CT angiography (CTA). We extend the interest operator from 2D to 3D in order to extract 3D feature points and develop a 3D image flow algorithm to find matches of feature points between the mask and the contrast data sets. A robust 3D motion estimation algorithm is also developed which handles outliers up to 50% of all computed image flow vectors. The subtracted volume after motion correction is rendered on the display. The proposed algorithm has been successfully applied to a clinical CTA data set and the result is very promising.>

Proposes a low-complexity fixed-rate vector quantizer for DCT transformed images based on the packing of scalar quantized DCT coefficients into pyramid-bounded integer lattices. A closed form expression for the size of pyramid-bounded integer lattices is derived and a method of bit-rate allocation to the various coefficients is described. The proposed scheme is simple and has performed well for various bit rates.>