A motion-based scene tree for browsing and retrieval of compressed videos

This paper describes a fully automatic content-based approach for browsing and retrieval of MPEG-2 compressed video. The first step of the approach is the detection of shot boundaries based on motion vectors available from the compressed video stream. The next step involves the construction of a scene tree from the shots obtained earlier. The scene tree is shown to capture some semantic information as well as to provide a construct for hierarchical browsing of compressed videos. Finally, we build a new model for video similarity based on global as well as local motion associated with each node in the scene tree. To this end, we propose new approaches to camera motion and object motion estimation. The experimental results demonstrate that the integration of the above techniques results in an efficient framework for browsing and searching large video databases.     

Replication and retrieval strategies for resource-effective admission control in multi-resolution video servers

Video-on-demand (VOD) service requires balanced use of system resources, such as disk bandwidth and buffer, to accommodate more clients. The data retrieval size and data rates of video streams directly affect the utilization of these resources. Given the data rates which vary widely in multi-resolution video servers, we need to determine the appropriate data retrieval size to balance the buffer with the disk bandwidth. Otherwise, the server may be unable to admit new clients even though one of the resources is available for use. To address this problem, we propose the following new schemes that work together: (1) A replication scheme called Splitting Striping units by Replication (SSR). To increase the number of admitted clients, SSR defines two sizes of striping unit, which allow data to be stored on the primary and backup copies in different ways. (2) A retrieval scheduling method which combines the merits of existing SCAN and grouped sweeping scheme (GSS) algorithms to balance the buffer and disk bandwidth usage. (3) Admission control algorithms which decide whether to read data from the primary or the backup copy. The effectiveness of the proposed schemes is demonstrated through simulations. Results show that our schemes are able to cope with various workloads efficiently and thus enable the server to admit a much larger number of clients.     

A compressed sensing approach for query by example video retrieval

Recently, compressed Sensing (CS) has theoretically been proposed for more efficient signal compression and recovery. In this paper, the CS based algorithms are investigated for Query by Example Video Retrieval (QEVR) and a novel similarity measure approach is proposed. Combining CS theory with the traditional discrete cosine transform (DCT), better compression efficiency for spatially sparse is achieved. The similarity measure from three levels (frame level, shot level and video level, respectively) is also discussed. For several different kinds of natural videos, the experimental results demonstrate the effectiveness of system by the proposed method.     

Document retrieval from compressed images

With the emergence of digital libraries, more and more documents are stored and transmitted through the Internet in the format of compressed images. It is of significant meaning to develop a system which is capable of retrieving documents from these compressed document images. Aiming at the popular compression standard-CCITT Group 4 which is widely used for compressing document images, we present an approach to retrieve the documents from CCITT Group 4 compressed document images in this paper. The black and white changing elements are extracted directly from the compressed document images to act as the feature pixels, and the connected components are detected simultaneously. Then the word boxes are bounded based on the merging of the connected components. Weighted Hausdorff distance is proposed to assign all of the word objects from both the query document and the document from database to corresponding classes by an unsupervised classifier, whereas the possible stop words are excluded. Document vectors are built by the occurrence frequency of the word object classes, and the pair-wise similarity of two document images is represented by the scalar product of the document vectors. Nine groups of articles pertaining to different domains are used to test the validity of the presented approach. Preliminary experimental results with the document images captured from students’ theses show that the proposed approach has achieved a promising performance.     

压缩视频流关键帧快速抽取方法

关键帧获取是视频内容分析的前提。目前的视频关键帧提取算法往往需要经过较多的计算才能确定,不适合海量视频数据处理的需求。面对互联网数据流的监控应用,分析了MPEG压缩视频流的特点,提出了一种新的关键帧快速抽取方法。该方法考虑了所抽取关键帧的覆盖面和视频动态性检测的需要,根据视频长度抽取多段关键帧,段首帧反馈定位,段内按稀疏系数抽取。通过视频库和IDC机房网络数据流的检测实验表明,提出的方法是快速有效的,能较好地应用于高速网络的视频监控中。     

An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique

Random Duplicated Assignment (RDA) is an approach in which video data is stored by assigning a number of copies of each data block to different, randomly chosen disks. It has been shown that this approach results in smaller response times and lower disk and RAM costs compared to the well-known disk stripping techniques. Based on this storage approach, one has to determine, for each given batch of data blocks, from which disk each of the data blocks is to be retrieved. This is to be done in such a way that the maximum load of the disks is minimized. The problem is called the Retrieval Selection Problem (RSP). In this paper, we propose a new efficient algorithm for RSP. This algorithm is based on the breadth-first search approach and is able to guarantee optimal solutions for RSP in O(n²+mn), where m and n correspond to the number of data blocks and the number of disks, respectively. We will show that our proposed algorithm has a lower time complexity than an existing algorithm, called the MFS algorithm.     

Performability of disk-array-based video servers

Video services are likely to dominate the traffic in future broadband networks. Most of these services will be provided by large- scale public-access video servers. Research to date has shown that disk arrays are a promising technology for providing the storage and throughput required to serve many independent video streams to a large customer population. Large disk arrays, however, are susceptible to disk failures which can greatly affect their reliability. In this paper, we discuss suitable redundancy mechanisms to increase the reliability of disk arrays and compare the performance of the RAID-3 and RAID-5 redundancy schemes. We use cost and performability analyses to rigorously compare the two schemes over a variety of conditions. Accurate cost models are developed and Markov reward models (with time-dependent reward structures) are developed and used to give insight into the tradeoffs between system cost and revenue earning potential. The paper concludes that for large-scale video servers, coarse-grained striping in a RAID-5 style of disk array is most cost effective.     

Tiny videos: a large data set for nonparametric video retrieval and frame classification

In this paper, we present a large database of over 50,000 user-labeled videos collected from YouTube. We develop a compact representation called "tiny videos" that achieves high video compression rates while retaining the overall visual appearance of the video as it varies over time. We show that frame sampling using affinity propagation-an exemplar-based clustering algorithm-achieves the best trade-off between compression and video recall. We use this large collection of user-labeled videos in conjunction with simple data mining techniques to perform related video retrieval, as well as classification of images and video frames. The classification results achieved by tiny videos are compared with the tiny images framework [24] for a variety of recognition tasks. The tiny images data set consists of 80 million images collected from the Internet. These are the largest labeled research data sets of videos and images available to date. We show that tiny videos are better suited for classifying scenery and sports activities, while tiny images perform better at recognizing objects. Furthermore, we demonstrate that combining the tiny images and tiny videos data sets improves classification precision in a wider range of categories.     

Perceptual video hashing based on Tucker decomposition with application to indexing and retrieval of near-identical videos

The perceptual video hash function defines a feature vector that characterizes a video depending on its perceptual contents. This function must be robust to the content preserving manipulations and sensitive to the content changing manipulations. In the literature, the subspace projection techniques such as the reduced rank PARAllel FACtor analysis (PARAFAC), have been successfully applied to extract perceptual hash for the videos. We propose a robust perceptual video hash function based on Tucker decomposition, a multi-linear subspace projection method. We also propose a method to find the optimum number of components in the factor matrices of the Tucker decomposition. The Receiver Operating Characteristics (ROC) curves are used to evaluate the performance of the proposed algorithm compared to the other state-of-the-art projection techniques. The proposed algorithm shows superior performance for most of the image processing attacks. An application for indexing and retrieval of near-identical videos is developed using the proposed algorithm and the performance is evaluated using average recall/precision curves. The experimental results show that the proposed algorithm is suitable for indexing and retrieval of near-identical videos.     

视频网格服务器存储容量模型研究

针对基于内容分发网络(CDN)技术的视频网格中中心与区域服务器存储系统的不同职能,分析了在不同影片数量规模和分布特征情况下,随着区域服务器相对存储容量的增加,本地服务率上升的规律,在本地服务率增长的临界点附近得出了较为经济的、以中心服务器存储容量为基准的区域服务器的相对存储容量,该容量兼顾了区域服务器本地服务率和存储系统的硬件投资,能够为实际视频网格的建设提供参考。     

An experimental analysis of digital video library servers

Much work on video servers has concentrated on movies on demand, in which a relatively small number of titles are viewed and users are given basic VCR-style controls. This paper concentrates on analyzing video server performance for non-linear access applications. In particular, we study two non-linear video applications: video libraries, in which users select from a large collection of videos and may be interested in viewing only a small part of the title; and video walk-throughs, in which users can move through an image-mapped representation of a space. We present a characterization of the workloads of these applications. Our simulation studies show that video server architectures developed for movies on demand can be adapted to video library usage, though caching is less effective and the server can support a smaller user population for non-linear video applications. We also show that video walk-throughs require extremely large amounts of RAM buffering to provide adequate performance for even a small number of users.     

Enabling broadcast of user-generated live video without servers

We are witnessing the unprecedented popularity of User-Generated-Content (UGC) on the Internet. While YouTube hosts pre-recorded video clips, in near future, we expect to see the emergence of User-Generated Live Video, for which any user can create its own temporary live video channel from a webcam or a hand-held wireless device. Hosting a large number of UG live channels on commercial servers can be very expensive. Server-based solutions also involve various economic, copyright and content control issues between users and the companies hosting their content. In this paper, leveraging on the recent success of P2P video streaming, we study the strategies for end users to directly broadcast their own live channels to a large number of audiences without resorting to any server support. The key challenge is that end users are normally bandwidth constrained and can barely send out one complete video stream to the rest of the world. Existing P2P streaming solutions cannot maintain a high level of user Quality-of-Experience (QoE) with such a highly constrained video source. We propose a novel Layered P2P Streaming (LPS) architecture, to address this challenge. LPS introduces playback delay differentiation and constructs virtual servers out of peers to boost end users’ capability of driving large-scale video streaming. Through detailed packet-level simulations and PlanetLab experiments, we show that LPS enables a source with upload bandwidth slightly higher than the video streaming rate to stream video to tens of thousands of peers with premium quality of experience.     

Semi-blind quality estimation of compressed videos using digital watermarking

A semi-blind method that estimates the quality of a video distorted by H.264/AVC compression/decompression is introduced. The method embeds pseudo-random binary watermarks in the I-frames of the original undistorted video. To assess the quality of a segment of a distorted watermarked video, the watermark bits are extracted and the quality is estimated based on the similarity between the embedded and the extracted watermarks. To enable quality assessment for a large range of distortions, the derivative vectors of different scaled versions of each I-frame of the original video are obtained, using wavelet transform. The watermark bits that are embedded in the small wavelet scales are used to estimate the small distortions, while the bits embedded in the large wavelet scales are used to estimate large distortions. This is because the latter bits are more robust (to distortions) than those bits embedded in the small wavelet scales. The proposed method was tested on different video sequences which were distorted by compression/decompression using H.264/AVC with different quality factors. The simulation results show that the proposed method can accurately estimate the quality of a video and its frames in terms of the peak signal-to-noise ratio (PSNR) and the structural similarity (SSIM) quality measures.     

A new paradigm for analysis of MPEG compressed videos

The increasing use of multimedia streams nowadays necessitates the development of efficient and effective methodologies for manipulating databases storing these streams. Moreover, content-based access to multimedia databases requires in its first stage to parse the video stream into separate shots then apply a method to summarize the huge amount of data involved in each shot. This work proposes a new paradigm capable of robustly and effectively analyzing the compressed MPEG video data. First, an abstract representation of the compressed MPEG video stream is extracted and used as input to a neural network module (NNM) that performs the shot detection task. Second, we propose two adaptive algorithms to effectively select key frames from segmented video shots produced by the segmentation stage. Both algorithms apply a two-level adaptation mechanism in which the first level is based on the dimension of the input video file while the second level is performed on a shot-by-shot basis in order to account for the fact that different shots have different levels of activity. Experimental results show the efficiency and robustness of the proposed system in detecting shot boundaries and flashlights occurring within shots and in selecting the near optimal set of key frames (KFs) required to represent each shot.     

Robust super resolution of compressed video

This paper presents a robust algorithm to recover high-frequency information from compressed low-resolution (LR) video sequences. Previous super-resolution (SR) approaches have succeeded in resolution enhancement when the motion in the LR sequence is simple. However, when the motion is complex, new artifacts will be introduced in the SR processing. To solve this problem, we develop a robust Bayesian SR algorithm with two steps. We first isolate the frames individually to get their corresponding initial SR solutions within the Bayesian framework. Secondly, with a robust cost function to reject outliers and noise, final SR images are achieved with multiple LR frames. In the mean time, we impose the constraint that the distribution of high-resolution (HR) image gradient should be equal to one of the corresponding decompressed LR images to sharpen the edges of the results. As a result of these steps, we are able to produce high-quality deblurred results, which show a suppressing of high-frequency artifacts and less ringing artifacts, with a higher peak signal-to-noise ratio (PSNR).     

近似重复视频检索方法研究

随着互联网的飞速发展,越来越多的视频被上传和下载,然而这些海量的视频中有很大的比例是近似重复的,这些近似重复的视频会给版权控制、视频检索准确性等造成一定影响,同时也会增加运营商的存储和处理成本。如何在大规模的视频集中找出近似重复的视频变得日益重要。本文对近几年关于近似重复视频检索方面的相关工作和研究成果进行了深入调研,详细论述了当前近似视频检索技术的现状及关键技术,并对其发展进行了展望。     

Shape-based retrieval of video objects

The increasing availability of object-based video content requires new technologies for automatically extracting and matching of the low level features of arbitrarily shaped video. This paper proposes methods for shape retrieval of arbitrarily shaped video objects. Our methods take into account not only the still shape features but also the shape deformations that may occur in an object's lifespan. We compute the shape similarity of video objects by comparing the similarity of their representative temporal instances. We also describe motion of a video object via describing the deformations in an object's shape. Experimental results show that our proposed methods offer very good retrieval performance and match closely with the human ranking.     

Modeling and performance comparison of reliability strategies fordistributed video servers

Large scale video servers are typically based on disk arrays that comprise multiple nodes and many hard disks. Due to the large number of components, disk arrays are susceptible to disk and node failures that can affect the server reliability. Therefore, fault tolerance must be already addressed in the design of the video server. For fault tolerance, we consider parity-based as well as mirroring-based techniques with various distribution granularities of the redundant data. We identify several reliability schemes and compare them in terms of the server reliability and per stream cost. To compute the server reliability, we use continuous time Markov chains that are evaluated using the SHARPE software package. Our study covers independent disk failures and dependent component failures. We propose a new mirroring scheme called Grouped One-to-One scheme that achieves the highest reliability among all schemes considered. The results of this paper indicate that dividing the server into independent groups achieves the best compromise between the server reliability and the cost per stream. We further find that the smaller the group size, the better the trade-off between a high server reliability and a low per stream cost