Furht, Borko

Video compression technology promises to be the key to the transmission of motion video. A number of techniques have been introduced in the past few years, particularly that developed by the Motion Picture Experts Group (MPEG). The MPEG algorithm uses Motion Estimation to reduce the amount of data that is stored for each frame. Motion Estimation uses a reference frame as a codebook for a modified Vector Quantization process. While an exhaustive search for Motion Estimation Vectors is time-consuming, various fast search algorithms have been developed. These techniques are surveyed, and the theoretical framework for a new search algorithm is developed: Densely-Centered Uniform P-Search. The time complexity of Densely-Centered Uniform P-Search is comparable to other popular Motion Estimation techniques, and shows superior results on a variety of motion video sources.

The home computer user represents a significant portion of the multimedia market. To the home user, multimedia is the ability to play, edit and even create movies (video and sound) on his home computer system. While there are many studies that concentrate on large multimedia servers which support hundreds (even thousands) of simultaneous users, there are very few that focus attention on the home computer configuration. This thesis presents the mechanisms for generating, compressing, transmitting and decompressing multimedia data as a framework for the long-term storage and retrieval of multimedia data on disk drives. After developing the framework, the thesis presents an in-depth design and analysis of a disk-based multimedia storage system, proposes a scheduling algorithm for data retrieval (DAN-SCAN) and presents the results of a simulation of the algorithm.

This thesis presents a survey of multimedia networks and the techniques to improve the capacity of video on demand systems. A survey was conducted and comparative evaluation was done to determine the multimedia capabilities of various networks. Video on demand is an electronic video rental system in which clients request and play videos on-demand. Video on-demand system can be implemented over an existing cable TV network or an upgraded ADSL network. The two techniques used to improve the capacity of video on-demand systems are segmentation and multicasting. Segmentation consists of dividing the video into several fixed length segments, and then transmitting the segments at regular intervals instead of transmitting the video continuously. With multicasting, more than one user requesting the same video are served by a single video stream. Multicasting further assumes that each subscriber has a limited storage space, so same video segments can be multicast to subscribers simultaneously even if the requests for a video are not synchronous.

In this thesis we applied wavelet transforms to image and video coding. First, a survey of various wavelets and their features is presented, including continuous, discrete, and orthogonal wavelets. Theories and concepts underlying one and two-dimensional wavelet transforms are introduced and compared to Fourier transform and sub-band coding. The core of the thesis is the implementation of two-dimensional and three-dimensional codec architectures and their application to coding images and videos, respectively. We studied performance of the wavelet codec by comparing it to DCT and JPEG coding techniques. We applied these techniques for compression of a variety of test images and videos. We also analyzed the adaptability and scalability of 2D and 3D codec. Experimental results, presented in the thesis, illustrate the superior performance of wavelets compared to other coding techniques.

A Content-Based Image Retrieval (CBIR) system is a mechanism intended to retrieve a particular image from a large image repository without resorting to any additional information about the image. Query-by-example (QBE) is a technique used by CBIR systems where an image is retrieved from the database based on an example given by the user. The effectiveness of a CBIR system can be measured by two main indicators: how close the retrieved results are to the desired image and how fast we got those results. In this thesis, we implement some classical image processing operations in order to improve the average rank of the desired image, and we also implement two object recognition techniques to improve the subjective quality of the best ranked images. Results of experiments show that the proposed system outperforms an equivalent CBIR system in QBE mode, both from the point of view of precision as well as recall.

The Interlaced Pixel Delta (IPD) Video Codec is a real time video compression and decompression engine. It is specifically designed to be used for video phone or video conferencing applications that are to be run under very low bandwidth networking conditions. The example network used throughout this dissertation is the Internet where users are typically connected at transmission speeds of 33.3 K bits per second or less. In order to accomplish this goal, the IPD codec must achieve very high compression ratios. This feat is further complicated by the fact that the IPD codec is to be fully realized using a software approach in order to be considered a viable solution for the average Internet user. The demonstrated test results show that the IPD codec is capable of achieving these ambitious goals. The IPD compressor operates in a pipelined manner. Each stage in the IPD compression pipeline has its own complexities and challenges, which are individually addressed in detail. The ultimate goal of the IPD compressor is to maintain a constant compression ratio that is sufficiently high enough to allow bi-directional video communication to take place across low bandwidth transmission lines. These compression ratios must be achieved using a software compressor and decompressor. Strict CPU utilization requirements must be met by the IPD codec in order for it to be able to operate in real time. The IPD compressor defines a unique video interlacing scheme to sample the pixels that comprise the incoming video frames. The properties of the interlacing schemes aid the video compressor in its quest for high compression ratios. Later in the decompression stage, the IPD decompressor uses the properties of the interlacing schemes to reverse the sampling process to bring back the original picture quality. The IPD compressor also employs a custom variation of the error diffusion algorithm in its color reduction phase. A pixel delta algorithm is used to build a new frame from a previous frame. The pixel delta algorithm defines a unique bitmask representation of pixel locations that are flagged for refresh. These pixel locations will be used to build a subsequent frame. The bitmask representation of pixel locations is further compressed using a variation of the Huffman compression algorithm. An IPD delta frame is built by the IPD compressor. The IPD delta frame contains a header, the compressed bitmask of pixel locations flagged for change and the actual compressed pixel intensity values used used to build a new frame from a previous frame. The IPD decompressor also operates in a pipelined manner. The IPD decompressor also has strict requirements with respect to CPU utilization. The IPD decompressor applies several image processing algorithms to the video output stream in order to enhance the visual quality of the reconstructed output video frames. Custom test programs are used to derive and validate the algorithms presented in this dissertation. A working prototype of the complete IPD codec is also presented to aid in the visual analysis of the final video picture quality.

XYZ Video Compression denotes a video compression algorithm that operates in three dimensions, without the overhead of motion estimation. The smaller overhead of this algorithm as compared to MPEG and other "standards-based" compression algorithms using motion estimation suggests the suitability of this algorithm to real-time applications. The demonstrated results of compression of standard motion video benchmarks suggest that XYZ Video Compression is not only a faster algorithm, but develops superior compression ratios as well. The algorithm is based upon the three-dimensional Discrete Cosine Transform (DCT). Pixels are organized as 8 x 8 x 8 cubes by taking 8 x 8 squares out of 8 consecutive frames. A fast three-dimensional transform is applied to each cube, generating 512 DCT coefficients. The energy-packing property of the DCT concentrates the energy in the cube into few coefficients. The DCT coefficients are quantized to maximize the energy concentration at the expense of introduction of a user-determined level of error. A method of adaptive quantization that generates optimal quantizers based upon statistics gathered for the 8 consecutive frames is described. The sensitivity of the human eye to various DCT coefficients is used to modify the quantizers to create a "visually equivalent" cube with still greater energy concentration. Experiments are described that justify choice of Human Visual System factors to be folded into the quantization step. The quantized coefficients are then encoded into a data stream using a method of entropy coding based upon the statistics of the quantized coefficients. The bitstream generated by entropy coding represents the compressed data of the 8 motion video frames, and typically will be compressed at 50:1 at 5% error. The decoding process is the reverse of the encoding process: the bitstream is decoded to generate blocks of quantized DCT coefficients, the DCT coefficients are dequantized, and the Inverse Discrete Cosine Transform is performed on the cube to recover pixel data suitable for display. The elegance of this technique lies in its simplicity, which lends itself to inexpensive implementation of both encoder and decoder. Finally, real-time implementation of the XYZ Compressor/Decompressor is discussed. Experiments are run to determine the effectiveness of the implementation.

Multimedia applications incorporate the use of more than one type of media, i.e., voice, video, data, text and image. With the advances in high-speed communication, the ability to transmit multimedia is becoming widely available. One of the means of transport for multimedia in distributed networks is Broadband Integrated Services Digital Network (B-ISDN). B-ISDN supports the transport of large volumes of data with a low error rate. It also handles the burstiness of multimedia traffic by providing dynamic bandwidth allocation. When multimedia is requested for transport in a distributed network, different Quality of Service (QOS) may be required for each type of media. For example, video can withstand more errors than voice. In order to provide, the most efficient form of transfer, different QOS media are sent using different channels. By using different channels for transport, jitter can impose skews on the temporal relations between the media. Jitter is caused by errors and buffering delays. Since B-ISDN uses Asynchronous Transfer Mode (ATM) as its transfer mode, the jitter that is incurred can be assumed to be bounded if traffic management principles such as admission control and resource reservation are employed. Another network that can assume bounded buffering is the 16 Mbps token-ring LAN when the LAN Server (LS) Ultimedia(TM) software is applied over the OS/2 LAN Server(TM) (using OS/2(TM)). LS Ultimedia(TM) reserves critical resources such as disk, server processor, and network resources for multimedia use. In addition, it also enforces admission control(1). Since jitter is bounded on the networks chosen, buffers can be used to realign the temporal relations in the media. This dissertation presents a solution to this problem by proposing a Feedback-based Multimedia Synchronization Technique (FMST) to correct and compensate for the jitter that is incurred when media are received over high speed communication channels and played back in real time. FMST has been implemented at the session layer for the playback of the streams. A personal computer was used to perform their synchronized playback from a 16 Mbps token-ring and from a simulated B-ISDN network.

The aim of this work is to explore the utilization of permutation-based transformations to achieve compression, encryption and steganography in the domain of digital videos. The main contribution of this dissertation is a novel type of digital video encryption that has several advantages over other currently available digital video encryption methods. An extended classification of digital video encryption algorithms is presented in order to clarify these advantages. The classification itself represents an original work, since to date, no such comprehensive classification is provided in known scientific literature. Both security and performance aspects of the proposed method are thoroughly analyzed to provide evidence for high security and performance efficiency. Since the basic model is feasible only for a certain class of video sequences and video codecs, several extensions providing broader applicability are described along with the basic algorithm. An additional significant contribution is the proposition of a novel type of digital video steganography based on disguising a given video by another video. Experimental results are generated for a number of video sequences to demonstrate the performance of proposed methods.

Object segmentation in a video sequence is an essential task in video processing and forms the foundation of content analysis, scene understanding, object-based video encoding (e.g. MPEG-4), various surveillance and 2D-to-pseudo-3D conversion applications. Popularization and availability of video sequences with increased spatial resolution requires development of new, more efficient algorithms for object detection and segmentation. This dissertation discusses a novel neural-network-based approach to background modeling for motion-based object segmentation in video sequences. In particular, we show how Probabilistic Neural Network (PNN) architecture can be extended to form an unsupervised Bayesian classifier for the domain of video object segmentation. The constructed Background Modeling Neural Network (BNN) is capable of efficiently handling segmentation in natural-scene sequences with complex background motion and changes in illumination. The weights of the proposed neural network serve as an exclusive model of the background and are temporally updated to reflect the observed background statistics. The proposed approach is designed to enable an efficient, highly-parallelized hardware implementation. Such a system would be able to achieve real-time segmentation of high-resolution image sequences.