Geometric data acquired from real-world scenes,e.g., 2D depth images, 3D point clouds, and 4D dynamic point clouds, have found a wide range of applications including immersive telepresence, autonomous driving, surveillance,etc. Due to irregular sampling patterns of most geometric data, traditional image/video processing methodologies are limited, while Graph Signal Processing (GSP)—a fast-developing field in the signal processing community—enables processing signals that reside on irregular domains and plays a critical role in numerous applications of geometric data from low-level processing to high-level analysis. To further advance the research in this field, we provide the first timely and comprehensive overview of GSP methodologies for geometric data in a unified manner by bridging the connections between geometric data and graphs, among the various geometric data modalities, and with spectral/nodal graph filtering techniques. We also discuss the recently developed Graph Neural Networks (GNNs) and interpret the operation of these networks from the perspective of GSP. We conclude with a brief discussion of open problems and challenges.

Using hand skeleton data to understand complex hand actions, such as assembly tasks or kitchen activities, is an important yet challenging task. This paper introduces an unsupervised hand graph-based spatio-temporal feature extraction method. To evaluate the efficacy of the proposed representation, we consider action segmentation and recognition tasks. The segmentation problem involves an assembling task in an industrial setting, while the recognition problem deals with kitchen and office activities. For both tasks, we propose novel notions of stability, loss function stability (LFS) and estimation stability with cross-validation (ESCV), that are used to quantify the robustness of achieved solutions. Our proposed feature extraction leads to classification performance comparable to state of the art methods, while achieving significantly better accuracy and stability in a cross-person setting. The proposed method also outperforms the existing methods in the segmentation task in terms of accuracy and shows robustness to any change in the input hyper-parameters.

Analysis of hand skeleton data can be used to understand patterns in manipulation and assembly tasks. This paper introduces a graph-based representation of hand skeleton data and proposes a method to perform unsupervised temporal segmentation of a sequence of sub-tasks in order to evaluate the efficiency of an assembly task. We explore the properties of different choices of hand graphs and their spectral decomposition. A comparative performance of these graphs is presented in the context of complex activity segmentation. We show that the spectral graph features extracted from 2D hand motion data outperform the direct use of motion vectors as features. We also make the collected hand position data available to the research community to facilitate further development in this direction.

Understanding human activity based on sensor information is required in many applications and has been an active research area. With the advancement of depth sensors and tracking algorithms, systems for human motion activity analysis can be built by combining off-the-shelf motion tracking systems with application-dependent learning tools to extract higher semantic level information. Many of these motion tracking systems provide raw motion data registered to the skeletal joints in the human body. In this paper, we propose novel representations for human motion data using the skeleton-based graph structure along with techniques in graph signal processing. Methods for graph construction and their corresponding basis functions are discussed. The proposed representations can achieve comparable classification performance in action recognition tasks while additionally being more robust to noise and missing data.

To reduce storage and computational cost for processing and visualizing large-scale 3D point clouds, an efficient resampling strategy is needed to select a representative subset of 3D points that can preserve contours in the original 3D point cloud. We tackle this problem by using graph-based techniques as graphs can represent underlying surfaces and lend themselves well to efficient computation. We first construct a general graph for a 3D point cloud and then propose a graph-based metric to quantify the contour information via high-pass graph filtering. Finally, we obtain an optimal resampling distribution that preserves the contour information by solving an optimization problem. When browsing, the proposed graph-based resampling performs better than uniform resampling both for toy point clouds as well as real large-scale point clouds. Furthermore, as neither mesh construction nor surface normal calculation is involved, the proposed graph-based method is computationally more efficient than the mesh-based methods.

Learning graph topology from data is challenging. Previous work leads to learning graphs on which the graph signals used for training are smooth. In this paper, we propose an optimization framework for learning multiple graphs, each associated to a class of signals, such that representation of signals within a class and discrimination of signals in different classes are both taken into consideration. A Fisher-LDA-like term is included in the optimization objective function in addition to the conventional Gaussian ML objective. A block coordinate descent algorithm is then developed to estimate optimal graphs for different categories of signals, which are then used to efficiently classify the different signals. Experiments on synthetic data demonstrate that our proposed method can achieve better discrimination between the learned graphs, leading to improvements in subsequent classification tasks.

For applications such as virtual reality and mobile mapping, point clouds are an effective means for representing 3-D environments. The need for compressing such data is rapidly increasing, given the widespread use and precision of these systems. This paper presents a method for compressing organized point clouds. 3-D point cloud data is mapped to a 2-D organizational grid, where each element on the grid is associated with a point in 3-D space and its corresponding attributes. The data on the 2-D grid is hierarchically partitioned, and a Bezier patch is fit to the 3-D coordinates associated with each partition. Residual values are quantized and signaled along with data necessary to reconstruct the patch hierarchy in the decoder. We show how this method can be used to process point clouds captured by a mobile-mapping system, in which laser-scanned point locations are organized and compressed. The performance of the patch-fitting codec exceeds or is comparable to that of an octree-based codec.

We consider the problem of fusing multiple cloud-contaminated aerial images of a 3D scene to generate a cloud-free image, where the images are captured from multiple unknown view angles. In order to fuse these images, we propose an end-to-end framework incorporating epipolar geometry and low-rank matrix completion. In particular, we first warp the multi-angular images to single-angle ones based on the estimated fundamental matrices that relate the multi-angular images according to their projective relations to the 3D scene. Then we formulate the fusion process of the warpped images as a low-rank matrix completion problem where each column of the matrix corresponds to a vectorized image with missing entries corresponding to cloud or occluded areas. Results using DigitalGlobe high spatial resolution images demonstrate that our algorithm outperforms existing approaches.

It is challenging to measure the geometry distortion of point cloud introduced by point cloud compression. Conventionally, the errors between point clouds are measured in terms of point-to-point or point-to-surface distances, that either ignores the surface structures or heavily tends to rely on specific surface reconstructions. To overcome these drawbacks, we propose using point-to-plane distances as a measure of geometric distortions on point cloud compression. The intrinsic resolution of the point clouds is proposed as a normalizer to convert the mean square errors to PSNR numbers. In addition, the perceived local planes are investigated at different scales of the point cloud. Finally, the proposed metric is independent of the size of the point cloud and rather reveals the geometric fidelity of the point cloud. From experiments, we demonstrate that our method could better track the perceived quality than the point-to-point approach while requires limited computations.

With the increased proliferation of applications using 3-D capture technologies for applications such as virtual reality, mobile mapping, scanning of historical artifacts, and 3-D printing, representing these kinds of data as 3-Dpoint clouds has become a popular method for storing and conveying the data independently of how it was captured. A point cloud consists of a set of coordinates indicating the location of each point, along with one or more attributes such as color associated with each point. Because the size of point cloud data can be quite large, compression is needed to efficiently store or transmit this data. This paper, motivated by techniques currently being used for image and video coding, proposes methods using 3-D block-based prediction and transform coding to compress point cloud attributes. Experimental results using a modified shape-adaptive DCT tailored for use in 3-D point clouds and a benchmark using 3-D graph transforms are shown.

Moving object segmentation in video has uses in many applications and is a particularly challenging task when the video is acquired by a moving camera. Typical approaches that rely on principal component analysis (PCA) tend to extract scattered sparse components of the moving objects and generally fail in extracting dense object segmentations. In this paper, a novel label propagation framework based on motion vanishing point (MVP) analysis is proposed to address the challenges. A weighted graph is constructed with image pixels as nodes and the MVP-guided approach is used to define the graph weights. Label propagation is then performed by incorporating the graph Laplacian. In addition, a PCA result is used to initialize the foreground/background labels. Experiments on the Hopkins data set of outdoor sequences captured by a hand-held moving camera demonstrate that the proposed label propagation method outperforms state-of-the-art PCA and spectral clustering methods for a dense segmentation task. Moreover, the framework is capable of correcting mislabeled foreground pixels and thus does not require accurate initial label assignment.

Tensor robust principal component analysis (PCA) approaches have drawn considerable interests in many applications such as background subtraction, denoising, and outlier detection, etc. In this paper we propose an online tensor robust PCA where the multidimensional data (tensor) is revealed sequentially in online mode, and tensor PCA is updated based on the latest estimation and the newly collected data. Compared to the tensor robust PCA in batch mode, we significantly reduce the required memory and improve the computation efficiency. Application on fusing cloud-contaminated satellite images demonstrates that the proposed method shows superiority in both convergence speed and performance compared to the state-of-the-art approaches.

With the recent improvements in 3-D capture technologies for applications such as virtual reality, preserving cultural artifacts, and mobile mapping systems, new methods for compressing 3-D point cloud representations are needed to reduce the amount of bandwidth or storage consumed. For point clouds having attributes such as color associated with each point, several existing methods perform attribute compression by partitioning the point cloud into blocks and reducing redundancies among adjacent points. If, however, many blocks are sparsely populated, few or no points may be adjacent, thus limiting the compression efficiency of the system. In this paper, we present two new methods using block-based prediction and graph transforms to compress point clouds that contain sparsely-populated blocks. One method compacts the data to guarantee one DC coefficient for each graph-transformed block, and the other method uses a K-nearest-neighbor extension to generate more efficient graphs.

Segmentation of moving objects in a scene is difficult for non-stationary cameras, and especially challenging in the presence of fast and unstable egomotion, e.g., as encountered with car-mounted cameras or wearable devices. Based on an analysis of motion vanishing points of the scene and estimated depth, a geometric model that relates extracted 2D motion to a 3D motion field relative to the camera is derived. Observing that the 3D motion field is piece-wise smooth, a constrained optimization problem that considers group sparsity is formulated to recover the 3D motion field from the 2D motion. The recovered 3D motion field is then clustered to provide the segmentation of moving objects. Experiments are performed using the KITTI Vision Benchmark Suite and demonstrate that the proposed framework provides a dense segmentation of moving objects that is robust to the challenging conditions inherent with car driving sequences.

In contrast to still image analysis, motion information offers a powerful means to analyze video. In particular, motion trajectories determined from keypoints have become very popular in recent years for a variety of video analysis tasks, including search, retrieval and classification. Additionally, cloud-based analysis of media content has been gaining momentum, so efficient communication of salient video information to perform the necessary analysis of video at the cloud server is needed. This paper describes a novel framework to efficiently represent the keypoint trajectories. In particular, an interframe prediction is designed with the option to operate in a low-delay mode. Additionally, a scalable coding method is proposed that allows for a subset of the coded trajectories in a video segment to be easily accessed. Experimental results on several popular datasets including Stanford MAR and Hopkin155 demonstrate a significant rate saving of up to 25% with our proposed trajectory coding approaches relative to a state-of-the-art reference approach.

In this paper, we develop a dynamic mode decomposition algorithm that is robust to both inlier and outlier noise in the data. One application of our algorithm is the identification of multiple crowd or traffic flows from compressed video streams. Our method uses motion vectors that are readily available in the compressed bitstream, and do not require computationally expensive optical flow. These motion vectors are known to be very noisy, however, our algorithm is able to extract the underlying dynamical systems that define the flows. We formulate a rank regularized dynamic mode decomposition problem with total least squares constraints to estimate the Koopman modes of the motion dynamics. The estimated Koopman modes are then used to analyze the stability of the system and extract steady state and transient flows. We demonstrate the improved performance of our approach compared to state of the art schemes and illustrate it applicability in identifying transient and steady-state flows in real video sequences.

The High Efficiency Video Coding (HEVC) standard has recently been extended to support efficient representation of multiview video and depth-based 3D video formats. The multiview extension, MV-HEVC, allows efficient coding of multiple camera views and associated auxiliary pictures, and can be implemented by reusing single-layer decoders without changing the block-level processing modules since block-level syntax and decoding processes remain unchanged. Bit rate savings compared with HEVC simulcast are achieved by enabling the use of inter-view references in motion-compensated prediction. The more advanced 3D video extension, 3D-HEVC, targets a coded representation consisting of multiple views and associated depth maps, as required for generating additional intermediate views in advanced 3D displays. Additional bit rate reduction compared with MV-HEVC is achieved by specifying new block-level video coding tools, which explicitly exploit statistical dependencies between video texture and depth and specifically adapt to the properties of depth maps. The technical concepts and features of both extensions are presented in this paper.

This article provides an overview of standardized extensions of HEVC for the advanced coding of 3D and multiview video. In those extensions, new coding tools that better exploit the inter-view redundancy of the multiview texture videos have been developed. Additionally, dedicated tools for the improved coding of depth have been extensively studied and incorporated into the standard. In this paper, the performance of these extensions is assessed, and experimental results demonstrate notable gains in coding efficiency.

We propose a depth-weighted group-wise PCA (DG-PCA) approach to separate moving foreground pixels from the background of a video acquired by a moving camera. Our approach utilizes a corresponding depth signal in addition to the video signal. The problem is formulated as a weighted l2,1-norm PCA problem with depth-based group sparsity being introduced. In particularly, dynamic groups are first generated solely based on depth, and then an iterative solution using depth to define the weights in l2,1-norm is developed. In addition, we propose a depth-enhanced homography model for global motion compensation before the DG-PCA method is executed. We demonstrate through experiments on an RGB-D dataset the superiority of the proposed DG-PCA approach over conventional robust PCA methods.

Motion segmentation relies on identifying coherent relationships between image pixels that are associated with motion vectors. However, perspective differences can often deteriorate the performance of conventional techniques. In this paper, we develop a motion segmentation scheme that utilizes the motion map of a single frame to identify motion representations based on motion vanishing points. Segmentation is achieved using graph spectral clustering where a novel graph is constructed using the motion representation distances in the motion vanishing point image associated with the image pixels. Experimental results show that the proposed graph spectral motion segmentation algorithm outperforms state-of-the-art methods for dense segmentation on image sequences with strong perspective effects using motion vectors between only two images.

We propose a factorized robust matrix completion (FRMC) algorithm with global motion compensation to solve the video background subtraction problem. The algorithm decomposes a sequence of video frames into the sum of a low rank background component and a sparse motion component. The algorithm alternates between the solution of each component following a Pareto curve trajectory for each subproblem. For videos with moving background, we utilize the motion vectors extracted from the coded video bitstream to compensate for the change in the camera perspective. Performance evaluations show that our approach is faster than state-of-the-art solvers and results in highly accurate motion segmentation.

Depth images are often presented at a lower spatial resolution, either due to limitations in the acquisition of the depth or to increase compression efficiency. As a result, upsampling low-resolution depth images to a higher spatial resolution is typically required prior to depth image based rendering. In this paper, depth enhancement and up-sampling techniques are proposed using a graph-based formulation. In one scheme, the depth is first upsampled using a conventional method, then followed by a graph-based joint bilateral filtering to enhance edges and reduce noise. A second scheme avoids the two-step processing and upsamples the depth directly using the proposed graph-based joint bilateral upsampling. Both filtering and interpolation problems are formulated as regularization problems and the solutions are different from conventional approaches. Further, we also studied operations on different graph structures such as star graph and 8-connected graph. Experimental results show that the proposed methods produce slightly more accurate depth at the full resolution with improved rendering quality of intermediate views.

We consider the problem of extracting descriptors that represent visually salient portions of a video sequence. Most state-of-the-art schemes generate video descriptors by extracting features, e.g., SIFT or SURF or other keypoint-based features, from individual video frames. This approach is wasteful in scenarios that impose constraints on storage, communication overhead and on the allowable computational complexity for video querying. More importantly, the descriptors obtained by this approach generally do not provide semantic clues about the video content. In this paper, we investigate new feature-agnostic approaches for efficient retrieval of similar video content. We evaluate the efficiency and accuracy of retrieval when k-means clustering is applied to image features extracted from video frames. We also propose a new approach in which the extraction of compact video descriptors is cast as a Non-negative Matrix Factorization (NMF) problem. Initial experiments on video-based matching suggest that compact descriptors obtained via low-rank matrix factorization improve discriminability and robustness to parameter selection compared to k-means clustering.

In stereo video applications, the quality of the two views may vary based on different camera capturing conditions and setup, compression/transmission, and sensor noise. Although some studies show that the perceived video quality may not be significantly affected by the lower quality view, maintaining a similar video quality is still desired in order to prevent eye strain during extended viewing sessions. In this paper, we study a graph-based approach to enhance the lower quality views by referring to the high quality view in addition to an accompanying depth map. We construct a graphical signal model with joint bilateral edge weights and show that graph-based joint bilateral filtering can better suppress several types of noises, e.g., Gaussian, motion as well as quantization noise.

Many of the existing video coding standards in use today were developed primarily using camera-captured content as test material. Today, with the more widespread use of connected devices, there is an increased interest in developing video coding tools that target screen content video. Screen content video is often characterized by having sharp edges, noiseless graphics-generated region, repeated patterns, limited sets of colors, etc. This paper presents an independent uniform prediction (IUP) mode for improving the coding efficiency of screen content video. IUP chooses one color out of a small set of global colors to form a uniform prediction block. Unlike existing palette-based modes, IUP does not have to construct and signal a color index map for every block that is coded. Experimental results using IUP in the HEVC Range Extensions 6.0 framework are presented, along with results using techniques that reduce complexity so that the IUP-based encoder is faster than the reference encoder.

Advanced multiview video systems are able to generate intermediate viewpoints of a 3-D scene. To enable low-complexity free view generation, texture and its associated depth are used as input data for each viewpoint. To improve the coding efficiency of such content, view synthesis prediction (VSP) is proposed to further reduce interview redundancy in addition to traditional disparity compensated prediction. This paper describes and analyzes rate-distortion optimized VSP designs, which were adopted in the 3-D extensions of both Advanced Video Coding (AVC) and High Efficiency Video Coding (HEVC). In particular, we propose a novel backward-VSP scheme using a derived disparity vector, as well as efficient signalling methods in the context of AVC and HEVC. In addition, we put forward a novel depth-assisted motion vector prediction method to optimize the coding efficiency. A thorough analysis of coding performance is provided using different VSP schemes and configurations. Experimental results demonstrate average bit rate reductions of 2.5% and 1.2% in AVC and HEVC coding frameworks, respectively, with up to 23.1% bit rate reduction for dependent views.

We propose an analytical model to estimate the synthesized view quality in 3D video. The model relates errors in the depth images to the synthesis quality, taking into account texture image characteristics, texture image quality, and the rendering process. Especially, we decompose the synthesis distortion into texture-error induced distortion and depth-error induced distortion. We analyze the depth-error induced distortion using an approach combining frequency and spatial domain techniques. Experiment results with video sequences and coding/rendering tools used in MPEG 3DV activities show that our analytical model can accurately estimate the synthesis noise power. Thus, the model can be used to estimate the rendering quality for different system designs.

In this work, a new coding tool called Edge Mode is proposed for HEVC intra coding, aimed at improving coding efficiency for screen content video. A set of edge modes that correspond to edge positions are identified based upon intra prediction directions. Then, a simplified scheme is developed to select the best edge mode. To avoid applying a transform over strong edges, directional 2D separable transforms are applied to blocks partitioned using these edge modes. Experimental results show that HEVC with edge modes (HEVC/EM) can achieve up to an 18% reduction in bit-rate as compared to unmodified HEVC, with an average reduction of 10.4% for screen content video sequences.

Modern, state-of-the-art disparity estimation techniques are able to very accurately estimate the disparity for a wide variety of scene types. However all of these methods assume that the input images are epipolar rectified. When an image pair is not rectified, it must be pre-processed before any estimation can be done. In this paper we propose a disparity estimation scheme that is able to handle non-rectified images without requiring a rectification step. We show how a minor modification to an existing estimation framework can allow for any disparity estimation framework to produce disparity maps for non-rectified images.

We propose an analytical model to estimate the synthesized view quality in 3D video. Specifically, we estimate the depth-error induced distortion using an approach that combines frequency and spatial domain analysis. We also propose to decompose the spatial-variant video signals into gradient-based representations to capture the interaction between image gradients, depth errors and synthesis distortion. Experiment results with video sequences and coding/rendering tools used in MPEG 3DV activities show that our analytical model can accurately estimate the synthesis noise power.

View synthesis prediction provides an effective way to reduce inter-view redundancy of multiview video in addition to conventional disparity compensated prediction. Traditional forward warping techniques incur high complexity since an entire picture is typically warped from one viewpoint to another. To reduce this complexity, block-based backward warping is considered as an alternative solution. One difficulty with this approach is that it requires depth information of the current block prior to its encoding. To solve this problem, a novel method is proposed to derive the depth information from neighboring blocks with high accuracy. With the proposed approach, backward warping is enabled using depth information derived from either neighboring spatial (inter-view) compensated blocks or temporal compensated blocks. As a generalization, the proposed backward warping scheme is not only applied at the pixel level, but at the sub-block level as well. Simulation results demonstrate that the proposed scheme achieves an average bitrate savings of 1.2% for coded video vs coded video bitrate, 1.1% for coded video vs total bitrate, and 1.0% for synthesized video vs total bitrate under common test conditions for 3D video coding using HEVC, with maximum gains of greater than 10% for dependent views.

Advanced multiview video systems are able to generate intermediate viewpoints of a 3D scene. In addition to the texture content, corresponding depth is associated with each viewpoint. To improve the coding efficiency of such content, view synthesis prediction can be used to further reduce inter-view redundancy in addition to traditional disparity compensated prediction. However, the predictor generated from the view synthesis process is affected by several factors, including signal properties of the texture, the accuracy of the depth and complexity of the scene, as well as coding errors in both the texture and depth. This paper presents an analysis of view synthesis prediction performance considering these factors. Based on this analysis, an adaptive depth quantization scheme is proposed to improve the depth coding, leading to better view synthesis prediction and overall coding efficiency gains. The proposed scheme is able to achieve an average bit rate savings of 0.9% on the coded and synthesized video with a maximum gain of up to 11.7% on the dependent views in the context of an HEVC-based codec.

Traditional multi-view coding (MVC) systems compress the texture content captured from different view points, where temporal and inter-view redundancy are exploited to improve MVC coding efficiency. The advanced 3D video coding systems compress both the texture content and its corresponding depth captured from different view points, known as multiview video plus depth (MVD), to support low complexity free view point applications. However, MVD systems consist of a large amount of data including both texture and depth to be compressed and transmitted. To improve the coding efficiency of MVD systems, view synthesis prediction (VSP) can be used to further reduce inter-view redundancy using synthetic views as predictors. In this paper, an in-loop view synthesis framework is proposed, where the synthesized predictor is encoded as a special motion compensated predictor and the motion information is encoded as one of the motion predictors in skip/merge candidate list for HEVC-based 3D video coding. The proposed scheme is applicable to both texture coding and depth coding. The experimental results show that the proposed framework improved the coding performance up to 12.1% for dependent views.

We propose an analytical model to estimate the rendering quality in 3D video. The model relates errors in the depth images to the rendering quality, taking into account texture image characteristics, texture image quality, the camera configuration and the rendering process. Specifically, we derive position (disparity) errors from the depth errors, and the probability distribution of the position errors is used to calculate the power spectral density of the rendering errors. Experiment results with video sequences and coding/rendering tools used in MPEG 3DV activities show that the model can accurately estimate the synthesis noise up to a constant offset. Thus, the model can be used to estimate the change in rendering quality for different system designs.

The quality of the depth map is crucial for depth image based rendering (DIBR) which enables a variety of advanced 3D video related applications such as perceived depth adjustment for stereoscopic video and intermediate view generation for multiview auto-stereoscopic displays. However, the input depth map for DIBR may suffer from errors and noise, which could seriously impact the rendered view quality. In order to reduce the errors and suppress the noise in the depth map, a local depth image enhancement technique is proposed that leverages trellis-based optimization techniques. A cost function is used to evaluate candidate depth values based on the stereo cost as well as color and depth consistency. Sparse depth features are also used in the enhancement process. The experimental results show notable subjective improvements in terms of rendering quality.

The High Efficiency Video Coding (HEVC) standardization process currently underway includes many tools for the coding of intra pictures. HEVC allows for many more intra prediction modes or directions as compared to previous standards. Efficient coding of these modes is therefore important because the modes consume a non-negligible portion of the total bit-stream used for coding intra pictures. In this paper, a predictive coding method is proposed to reduce the number of bits needed for signaling the intra prediction modes, where the spatial angular correlation between the intra prediction mode of the current Prediction Unit (PU) and the neighboring PUs is computed using a few modulo-N arithmetic operations that do not impact encoder or decoder run-times. The proposed method provides similar or greater improvements in compression efficiency as compared to competing tools, while requiring no changes to the existing bit-stream syntax.

With the simplicity of its application together with compression efficiency, the Discrete Cosine Transform(DCT) plays a vital role in the development of video compression standards. For next-generation video coding, a new set of 2-D separable transforms has emerged as a candidate to replace the DCT. These separable transforms are learned from residuals of each intra prediction mode, hence termed as Mode dependent-directional transforms (MDDT). MDDT uses the Karhunen-Loeve Transform (KLT) to create sets of separable transforms from training data. Since the residuals after intra prediction have some structural similarities, transforms utilizing these correlations improve coding efficiency. However, the KLT is the optimal approach only if the data has a Gaussian distribution without outliers. Due to the nature of the least-square norm, outliers can arbitrarily affect the directions of the KLT components. In this paper, we will address robust learning of separable transforms by enforcing sparsity on the coefficients of the representations. With this new approach, it is possible to improve upon the video coding performance of H.264/AVC by up to 10.2% BD-rate for intra coding. At no additional cost, the proposed techniques can also provide up to 3.9% improvement in BD-rate for intra coding compared to existing MDDT schemes.

View synthesis is an essential function for a number of 3D video applications including free-viewpoint navigation and view generation for auto-stereoscopic displays. Depth Image Based Rendering (DIBR) techniques are typically applied for this purpose. However, the quality of the rendered views is very sensitive to the quality of the depth image. In this paper, a novel trellis-based view synthesis framework is proposed to overcome the above limitations in depth images and reduce artifacts in the rendered picture. Our results demonstrate that the proposed approach offers visible improvements in rendering quality compared to existing view synthesis techniques.

A distributed coding algorithm is presented for compression of wavelet-transformed data. Data structures based on zerotrees are exploited for efficient compression of the significance map of wavelet coefficients. The coefficients are scanned in two stages, with a significance pass and refinement pass, similar to the SPIHT algorithm. The bits resulting from these passes are Slepian-Wolf coded using an LDPC syndrome code selected from a bank of available codes. A key realization is that, for each bitplane of the wavelet coefficients, the significance pass of the source data can be synchronized with that of the side information. This allows distributed compression of the significance pass. This is substantially different from previous mixed approaches in which the refinement pass was Slepian-Wolf coded, but the significance pass was coded independently. Rate-distortion results are presented for images from the ALOS AVNIR-2 multispectral dataset and compared against those obtained with SPIHT and JPEG2000.

In this paper, we propose a novel dictionary based video coding technique with adaptive construction of over complete dictionaries and advanced coding methods tailored to sparse signal representations. A set of dictionaries is trained off-line using inter or intra predicted residual samples and is applied for encoding. New coding tools are developed so that the encoder can more compactly represent the residual signal. The same set of dictionary elements can be reused for neighboring blocks, and the optimal number of dictionary elements can be decided using rate-distortion optimization. Experimental results demonstrate that the proposed algorithm yields both improved coding performance and improved perceptual quality at low bit rates.

Significant improvements in video compression capability have been demonstrated with the introduction of the H.264/MPEG-4 advanced video coding (AVC) standard. Since developing this standard, the Joint Video Team of the ITU-T Video Coding Experts Group (VCEG) and the ISO/IEC Moving Picture Experts Group (MPEG) has also standardized an extension of that technology that is referred to as multiview video coding (MVC). MVC provides a compact representation for multiple views of a video scene, such as multiple synchronized video cameras. Stereo-paired video for 3-D viewing is an important special case of MVC. The standard enables inter-view prediction to improve compression capability, as well as supporting ordinary temporal and spatial prediction. It also supports backward compatibility with existing legacy systems by structuring the MVC bitstream to include a compatible “base view.” Each other view is encoded at the same picture resolution as the base view. In recognition of its high-quality encoding capability and support for backward compatibility, the stereo high profile of the MVC extension was selected by the Blu-Ray Disc Association as the coding format for 3-D video with high-definition resolution. This paper provides an overview of the algorithmic design used for extending H.264/MPEG-4 AVC towards MVC. The basic approach of MVC for enabling inter-view prediction and view scalability in the context of H.264/MPEG-4 AVC is reviewed. Related supplemental enhancement information (SEI) metadata is also described. Various “frame compatible” approaches for support of stereo-view video as an alternative to MVC are also discussed. A summary of the coding performance achieved by MVC for both stereo- and multiview video is also provided. Future directions and challenges related to 3-D video are also briefly discussed.

A depth image is 3-D information used for virtual view synthesis in 3-D video system. In depth coding, the object boundaries are hard to compress and severely affect the rendering quality since they are sensitive to coding errors. In this paper, we propose a depth boundary reconstruction filter and utilize it as an in-loop filter to code the depth video. The proposed depth boundary reconstruction filter is designed considering occurrence frequency, similarity, and closeness of pixels. Experimental results demonstrate that the proposed depth boundary reconstruction filter is useful for efficient depth coding as well as high-quality 3-D rendering.

This paper describes a new technique for embedding a message within structured shapes. It is desired that any changes in the shape owing to the embedded message are invisible to a casual observer but detectable by a specialized decoder. The message embedding algorithm represents shape outlines as a set of cubic Bezier curves and straight line segments. By slightly perturbing the Bezier curves, a single shape can spawn a library of similar-looking shapes each corresponding to a unique message. This library is efficiently stored using Adaptively Sampled Distance Fields (ADFs) which also facilitate rendering of the modified shapes at the desired resolution and fidelity. Given any modified shape, a forensic detector applies Procrustes analysis to determine the embedded message. Results of an extensive subjective test confirm that the shape modifications are indeed unobtrusive. Further, to test the recovery of the message bits in noisy physical environments, a text document is put through a print-photocopy-scan process. Message recovery is found to be stable even after multiple rounds of photocopying.

This paper presents a new approach for estimating the disparity search range in stereo video that enforces temporal consistency. Reliable search range estimation is very important since an incorrect estimate causes most stereo matching methods to get trapped in local minima or produce unstable results over time. In this work, the search range is estimated based on a disparity histogram that is generated with sparse feature matching algorithms such as SURF. To achieve more stable results over time, we further propose to enforce temporal consistency by calculating a weighted sum of temporally-neighboring histograms, where the weights are determined by the similarity of depth distribution between frames. Experimental results show that this proposed method yields accurate disparity search ranges for several challenging stereo videos and is robust to various forms of noise, scene complexity and camera configurations.

This paper describes our recent analysis on the security and privacy of biometric feature vectors obtained from fingerprint minutiae. A large number of contiguous regions (cuboids) are selected at random in the minutiae space, and several new features are extracted from the minutiae inside each such cuboid. Specifically, the features are extracted from the average minutia coordinate within a cuboid, the standard deviation of the minutiae coordinates, and the aggregate wall distance, i.e., the sum of distance of each minutia from the boundary of the cuboids. In terms of matching performance on a public database, the feature vectors provide an equal error rate of 3 % even if the imposter is allowed to use the same local patches as the genuine user. Performance within a secure biometrics framework is evaluated by applying an LDPC code to the feature vectors and storing only the syndrome at the access control device, for use in authentication. The paper concludes with a discussion on methods to analyze security and privacy of biometric systems that use such local-aggregate-based feature vectors in a secure biometric recognition framework. This discussion highlights security attacks via template injection, spoofing, and cancelability compromises and also considers the difficulty of privacy attacks via template inversion.

In this paper, we present 2-D direction-adaptive transforms for coding prediction residuals of video. These Direction-Adaptive Residual Transforms (DART) are shown to be more effective than the traditional 2-D DCT when coding residual blocks that contain directional features. After presenting the directional transform structures and improvements to their efficiency, we outline how they are used to code both Inter and Intra prediction residuals. For Intra coding, we also demonstrate the relation between the prediction mode and the optimal DART orientation. Experimental results exhibit up to 7% and 9.3% improvements in compression efficiency in JM 16.0 and JM-KTA 2.6r1 respectively, as compared to using only the conventional H.264/AVC transform.

This paper proposes a novel method for handling occluded pixels in stereo images based on a probabilistic voting framework that utilizes a novel support-and-decision process. Occlusion handling aims to assign a reasonable disparity value to occluded pixels in the disparity maps. In an initial step, disparities and their corresponding supports at the occluded pixels are calculated using a probabilistic voting method using the disparities at visible pixels. In this way, the visible pixel information is propagated when the disparities and supports at the occluded pixels are computed. The final disparities for occluded pixels are then computed through an iterative support-and-decision process to propagate the information inside the occluded pixel region. An acceleration technique is also proposed to improve the performance of the iterative support-and-decision process. Experimental results show that the proposed occlusion handling method works well for several challenging stereo images.

Stereoscopic video will soon be delivered to the home through various channels. To make this feasible for some channels, the representation of the stereo video is modified to accommodate certain constraints on legacy systems. Among the various constraints that must be considered include the capabilities of production equipment and transmission infrastructure, as well as existing receivers and uncompressed digital interfaces between devices within the home. This paper outlines the typical constraints that are encountered in these domains and provides an overview of the various frame-compatible formats that are being considered for distribution of 3D video through such legacy systems. The benefits and drawbacks of these formats are discussed and the current status in various industry forums is reviewed.

Alice and Bob possess sequences x and y respectively and would like to compute the ℓ1distance, namely || x - y ||1under privacy and communication constraints. The privacy constraint requires that Alice and Bob do not reveal their data to each other. The communication constraint requires that they accomplish the secure distance calculation with a small number of protocol transmissions and key exchanges. This paper describes and analyzes a privacy-preserving approximation protocol for the ℓ1distance that keeps the communication overhead manageable by performing a Johnson-Lindethe ℓ1distance that keeps the communication overhead manageable by performing a Johnson-Lindenstrauss embedding into the ℓ2space. Then, it performs secure two-party computation of ℓ2distances using Paillier homomorphic encryption. The protocol is implemented for private querying of face images, while maintaining a low communication overhead between the queryingnstrauss embedding into the ℓ2space. Then, it performs secure two-party computation of ℓ2distances using Paillier homomorphic encryption. The protocol is implemented for private querying of face images, while maintaining a low communication overhead between the querying party and a remote database of face feature vectors.

Most distributed source coding schemes involve the application of a channel code to the signal and transmission of the resulting syndromes. For low-complexity encoding with superior compression performance, graph-based channel codes such as LDPC codes are used to generate the syndromes. The encoder performs simple XOR operations, while the decoder uses belief propagation (BP) decoding to recover the signal of interest using the syndromes and some correlated side information. We consider parallelization of BP decoding on general-purpose multi-core CPUs. The motivation is to make BP decoding fast enough for realtime applications. We consider three different BP decoding algorithms: Sum-Product BP, Min-Sum BP and Algorithm E. The speedup obtained by parallelizing these algorithms is examined along with the tradeoff against decoding performance. Parallelization is achieved by dividing the received syndrome vectors among different cores, and by using vector operations to simultaneously process multiple check nodes in each core. While Min-Sum BP has intermediate decoding complexity, a “vectorized” version of Min-Sum BP performs nearly as fast as the much simpler Algorithm E with significantly fewer decoding errors. Our experiments indicate that, for the best compromise between speed and performance, the decoder should use Min-Sum BP when the side information is of good quality and Sum-Product BP otherwise.

This paper investigates the application of lossy distributed source coding to high resolution multispectral images. The choice of distributed source coding is motivated by the need for very low encoding complexity on space and airborne platforms. The data consists of red, blue, green and infra-red channels and is compressed in an asymmetric Wyner-Ziv setting. One image channel is compressed using traditional JPEG and transmitted to the ground station where it is available as side information for Wyner-Ziv coding of the other channels. Encoding is accomplished by quantizing the image data, applying a Low-Density Parity Check code to the remaining three image channels, and transmitting the resulting syndromes. At the ground station, the image data is recovered from the syndromes by exploiting the correlation in the frequency spectrum of the band being decoded and the JPEG-decoded side information band. In experiments with real uncompressed images obtained by a satellite, the rate-distortion performance is found to be vastly superior to JPEG compression of individual image channels and rivals that of JPEG2000 at much lower encoding complexity.

This paper describes a method for hiding data inside printed text documents that is resilient to print/scan and photocopying operations. Using the principle of channel coding with side information, the embedder inserts a message into a text document while treating the content of the document as known interference. The data is embedded by making small changes to text characters before the document is printed. Using a simple correlation-based detector in conjunction with an error correction code, the hidden data can be extracted from a photocopy of the printed document. By enhancing the detector with an optical character recognition algorithm, the embedded data can be extracted even after multiple rounds of photocopying. Results from subjective tests show that the changes made by the embedding algorithm, while perceptible, are not obtrusive to a lay reader.

Alice and Bob possess sequences xnand ynrespectively and would like to compute d(xn, yn) where d(· , ·) is a distortion measure. However, Alice and Bob do not trust each other and do not wish to reveal their data to each other. This paper describes and analyzes a protocol that uses homomorphic encryption for secure calculation of some special distortion functions without revealing xnand yn. The resulting distortion result is also in encrypted form. Two variants of the protocol are presented, one for the Hamming distance between binary vectors, and the other for squared error distortion between integer vectors. An application of the protocol for private biometric authentication is described in which Bob interacts with a remote encrypted fingerprint database (Alice) to achieve access control without revealing his own identity.

It is well-known that large depth-coding errors typically occurring around depth edge areas lead to distorted object boundaries in the synthesized texture images. This paper proposes a multi-layered coding approach for depth images as a complement to the popular edge-aware approaches such as those based on platelets. It is shown that guaranteeing a near-lossless bound on the depth values around the edges by adding extra enhancement layers is an effective way to improve the visual quality of the synthesized images.

A depth image represents three-dimensional (3-D) scene information and is commonly used for depth image-based rendering (DIBR) to support 3-D video and free-viewpoint video applications. The virtual view is generally rendered by the DIBR technique and its quality depends highly on the quality of depth image. Thus, efficient depth coding is crucial to realize the 3-D video system. In this letter, we propose a depth reconstruction filter and depth down/up sampling techniques to improve depth coding performance. Experimental results demonstrate that the proposed methods reduce the bit-rate for depth coding and achieve better rendering quality.

A fuzzy filter adaptive to both sample's activity and the relative position between samples is proposed to reduce the artifacts in compressed multidimensional signals. For JPEG images, the fuzzy spatial filter is based on the directional characteristics of ringing artifacts along the strong edges. For compressed video sequences, the motion compensated spatiotemporal filter (MCSTF) is applied to intraframe and interframe pixels to deal with both spatial and temporal artifacts. A new metric which considers the tracking characteristic of human eyes is proposed to evaluate the flickering artifacts. Simulations on compressed images and videos show improvement in artifact reduction of the proposed adaptive fuzzy filter over other conventional spatial or temporal filtering approaches.

We propose a novel method to reduce both blocking and ringing artifacts in compressed images and videos. Based on the directional characteristics of ringing artifacts along edges, we use a directional fuzzy filter which is adaptive to the direction of the ringing artifact. The filter exploits the spatial order, the rank order and the spread information of the signal together with the position of the pixels to enhance the quality of the compressed image. Simulations results on compressed images and videos having simple and complex edges show the improvement of the proposed directional fuzzy filter over the conventional fuzzy filtering and other approaches.

Supporting digital video cassette recording (VCR) trick-play functionalities (e.g. random access, fast-forward play, fast-reverse play) is desirable for compressed video streams. However, due to strong inter-frame dependencies introduced by motion compensated prediction (MCP), the computational complexity and memory requirement is drastically increased. Tradeoffs between coding efficiency and decoding complexity can be made with different group of pictures (GOP) structures. In this paper, we investigate two flexible GOP structures, named G-group and binary reference GOP structure (BRGS), which can achieve trick-play functionalities while keeping low decoder complexity and memory requirement for the state-of-the-art H.264/AVC video coding standard. The schemes are drift-free since they utilize the compression and memory management tools adopted in H.264/AVC. Our analysis and experimental results show that they can greatly reduce the decoder complexity and buffer size while introducing only about 4.0%-7.6% bitrate increase on average. The computational complexity saving for the worst case and average case can be up to 77.8% and 62.5%, respectively. The memory buffer for the fast-reverse play mode can be reduced to 33.3% compared to the conventional scheme. Moreover, the schemes are flexible and can be easily adapted to achieve a good tradeoff between compression performance and complexity saving for the trick-play modes.

We present an information-theoretically secure biometric storage system using graph-based error correcting codes in a Slepian-Wolf coding framework. Our architecture is motivated by the noisy nature of personal biometrics and the requirement to provide security without storing the true biometric at the device. The principal difficulty is that real biometric signals, such as fingerprints, do not obey the i.i.d. or ergodic statistics that are required for the underlying typicality properties in the Slepian-Wolf coding framework. To meet this challenge, we propose to transform the biometric data into binary feature vectors that are i.i.d. Bernoulli(0.5), independent across different users, and related within the same user through a BSC-p channel with small p< 0.5. Since this is a standard channel model for LDPC codes, the feature vectors are now suitable for LDPC syndrome coding. The syndromes serve as secure biometrics for access control. Experiments on a fingerprint database demonstrate that the system is information-theoretically secure, and achieves very low false accept rates and low false reject rates.

Multimedia information retrieval (MIR) and delivery plays an important role in many application domains due to the increasing need to identify, filter, and manage growing amounts of data, notably multimedia information. To efficiently manage and exchange multimedia information, interoperability between coded data and metadata is required and standardization is central to achieving the necessary level of interoperability. In the context of this paper, the term retrieval refers to the process by which a user, human or machine, identifies the content it needs, and the term delivery refers to the adaptive transport and consumption of the identified content in a particular context or usage environment. Both the retrieval and delivery processes may require content and context metadata. This paper will argue that maximum quality of experience depends not only on the content itself (and thus content metadata) but also on the consumption conditions (thus context metadata). Additionally, the rights and protection conditions have become critically important in recent years, especially with the explosion of electronic music commerce and different ldquoshoppingrdquo conditions. This paper will review existing multimedia standards related to information retrieval and adaptive delivery of multimedia content, emphasizing the need for such standards, and will show how these standards can help the development, dissemination, and valorization of MIR research results. Moreover, it will also discuss limitations of the current standards and anticipate what future standardization activities are relevant and needed. Due to space limitations, the paper will mainly concentrate on MPEG standards although many other relevant standards are also reviewed and discussed.

We describe a method to encode fingerprint biometrics securely for use, e.g., in encryption or access control. The system is secure because the stored data does not suffice to recreate the original fingerprint biometric. Therefore, a breach in database security does not lead to the loss of biometric data. At the same time the stored data suffices to validate a probe fingerprint. Our approach is based on the use of distributed source coding techniques implemented with graph-based codes. We present a statistical model of the relationship between the enrollment biometric and the (noisy) biometric measurement taking during authentication. We describe how to validate or reject a candidate biometric probe given the probe and the stored encoded data. We report the effectiveness of our method as tested on a database consisting of 579 data sets, each containing roughly 15 measurements of a single finger. We thereby demonstrate a working secure biometric system for fingerprints.

This paper addresses signal processing issues related to coded representation, reconstruction and rendering of multiview video for 3D displays. We provide an overview of standardization efforts for multiview video that are aimed at reducing data rates required to represent the multiview video in compressed form. We then present an anti-aliasing filtering technique that effectively eliminates ghosting artifacts when rendering multiview video on 3D displays. Since high-frequency components of the signal are removed, substantial reductions in the compressed data rate could also be realized. Finally, we discuss the importance of scalability in the context of multiview video coding and suggest a combined anti-aliasing and scalable decoding scheme to minimize decoding resources for a given 3D display.

We propose a rate-distortion optimized framework that incorporates view synthesis for improved prediction in multiview video coding. In the proposed scheme, block-based depth and correction vectors are encoded and used at the decoder to generate the view synthesis prediction data. The proposed method employs variable block-size depth/motion search, optimal mode decision including view synthesis prediction, and CABAC encoding of depth and correction vectors. A sub-pixel reference matching technique is also introduced to improve prediction accuracy of the view synthesis prediction. Novel variants of the skip and direct modes are presented, which infer the depth and correction vector information from neighboring blocks in a synthesized reference picture to reduce the bits needed for the view synthesis prediction mode. Experimental results demonstrate improved coding efficiency with the proposed techniques.

This paper describes novel motion mapping algorithms aimed for low-complexity MPEG-2 to AVC transcoding. The proposed algorithms efficiently map incoming MPEG-2 motion vectors to outgoing AVC motion vectors regardless of the block sizes that the motion vectors correspond to. Extensive simulation results show that our proposed transcoder incorporating the proposed algorithms achieves very good rate-distortion performance with low complexity. Compared with the cascaded decoder-encoder solution, the proposed approach could achieve similar coding efficiency while significantly reduce the complexity.

Multi-view 3D displays are preferable to other stereoscopic display technologies because they provide autostereoscopic viewing from any viewpoint without special glasses. However, they require a large number of pixels to achieve high image quality. Therefore, data compression is a major issue for this approach. In this paper, we present a framework for efficient compression of multi-view video streams for multi-view 3D displays. Our goal is to optimize image quality without increasing the required data bandwidth. We achieve this by taking into account a precise notion of the multi-dimensional display bandwidth. The display bandwidth implies that scene elements that appear at a given distance from the display become increasingly blurry as the distance grows. Our main contribution is to enhance conventional multi-view compression pipelines with an additional pre-filtering step that bandlimits the multi-view signal to the display bandwidth. This imposes a shallow depth of field on the input images, thereby removing high frequency content. We show that this pre-filtering step leads to increased image quality compared to state-of-the-art multi-view coding at equal bitrate. We present results of an extensive user study that corroborate the benefits of our approach. Our work suggests that display pre-filtering will be a fundamental component in signal processing for 3D displays, and that any multi-view compression scheme will benefit from our pre-filtering technique.

This paper presents a video surveillance system that displays mega-pixel streams effectively, while transmitting and processing the streams efficiently with limited resources such as bandwidth, computing power and display resolution. The proposed system stores high-resolution and high-quality video data and associated object metadata, which includes ROI (Region-of-Interest) information. To satisfy such resource constraints and display important parts in detail without missing the overall scene context, the stored images are efficiently transcoded in the compressed-domain based on the ROI information, display resolution and available bandwidth. Simulation results confirm the effectiveness of the proposed system in terms of objective measures and subjective evaluation.

Abstract Significant progress in digital video processing and communication technology has enabled the dream of high‐quality and real‐time video streaming over various networks. Compression technologies have bridged the gap between huge amount of visual data required for video streaming and limited bandwidth of communication channels. Communication networks, including wired and wireless networks, provide the platform for video streaming applications. However, video streaming is still a challenging problem due to limited network bandwidth, the presence of channel errors, and the variability in consumer terminals. In this article, we present an overview of scalable video streaming techniques that have been developed in recent years. These techniques include scalable video coding (SVC), video transcoding, and scalable video streaming methods. Copyright © 2007 John Wiley & Sons, Ltd.

The need for effective search for television content is growing as the number of choices for TV viewing and/or recording explodes. In this paper we describe a preliminary prototype of a multimodal Speech-In List-Out (SILO) interface in which users' input is unrestricted by vocabulary or grammar. We report on usability testing with a sample of six users. The prototype enables search through video content metadata downloaded from an electronic program guide (EPG) service. Our setup for testing included adding a microphone to a TV remote control and running an application on a PC whose visual interface was displayed on a TV.

We consider multiview video compression: the problem of jointly compressing multiple views of a scene recorded by different cameras. To take advantage of the correlation between views, we propose using disparity compensated view prediction and view synthesis and describe how these features can be implemented by extending the H.264/AVC compression standard. Finally, we discuss experimental results on the test sequences from the MPEG call for proposals on multiview video.

This paper describes a rate control algorithm for a streaming video system that dynamically transcodes stored JPEG 2000 frames. The proposed algorithm is designed to improve overall quality over a static rate control method by increasing bandwidth utilization, while satisfying buffer constraints and maintaining consistent quality over time. Simulation results confirm the effectiveness of the proposed algorithm in terms of both objective measures and subjective evaluation

This paper describes novel low-complexity transcoding techniques for an efficient MPEG-2 to H.264/AVC transcoder. We present a motion and mode mapping algorithm that directly maps incoming MPEG-2 motion information to H.264/AVC motion vectors as well as coding modes. Refinement strategies are also presented to improve performance. Experiment results demonstrate the effectiveness of the proposed low-complexity transcoder

We describe the architecture for our distributed video coding (DVC) system. Some key differences between our work and previous systems include a new method of enabling decoder motion compensation, and the use of serially concatenated accumulate syndrome codes for distributed source coding. To evaluate performance, we compare our system to the H.263+ and H.264/AVC video codecs. Experiments show that our system is comparable to DVC systems from Stanford and Berkeley in the sense that our system performs better than H.263+Intra, but worse than H.263+Inter and H.264/AVC

In this correspondence, we propose a constant quality rate allocation algorithm for fine granularity scalability (FGS) coded videos. The rate allocation problem is formulated as a constrained minimization of quality fluctuation. The minimization is solved using a composite rate distortion (R-D) analysis. For a set of video frames, a composite R-D curve is first computed and then used for computing the optimal rate allocation. This algorithm is efficient because it is neither iterative nor recursive. After the composite R-D curve is computed, it can be used for optimal rate allocation of any rate budget. Moreover, the composite R-D curve can be updated efficiently over sliding windows. Experimental results have shown both the effectiveness and the efficiency of the proposed algorithm.

The paper presents a new method using fuzzy filtering to remove the coding artifacts in compressed video. The method takes the interlaced video format into consideration and processes each field separately. For deblocking, a 1D fuzzy filter with different window sizes is used to remove the horizontal and vertical blocking artifacts respectively. For deringing, each 8/spl times/8 block in a field is first classified into one of the four categories, i.e., strong edge, weak edge, texture and smooth blocks. According to each block's type and the neighboring block's type, the spread parameter of a 2D fuzzy filter is adaptively decided and the filter is applied To speed up the process, the fuzzy filter weights are generated using a piecewise linear membership function instead of the conventional Gaussian function. Experimental results show that the proposed method has better detail preservation and lower computational costs than our previous method. It achieves comparable deblocking and superior deringing performance to the MPEG-4 standard method at similar computation costs.

The paper explores the use of a recently introduced 3D dual-tree discrete wavelet transform (DDWT) for video coding. The 3D DDWT is an attractive video representation because it isolates motion along different directions in separate subbands. However, it is an overcomplete transform with 8:1 or 4:1 redundancy. Based on the effectiveness of the iterative projection-based noise shaping scheme proposed by Kingsbury in reducing the number of coefficients, and our prior investigation about the correlation between subbands at the same spatial/temporal location, both in the significance map and in actual coefficient values, a new video coding scheme using 3D DDWT is proposed. The proposed video codec does not require motion compensation and provides better performance than the 3D SPIHT codec, both objectively and subjectively, despite the fact that the raw number of coefficients resulting from the 3D DDWT is much more than that of the conventional 3D DWT. The proposed coder allows full scalability in spatial, temporal and quality dimensions.

This paper presents an object-aware video surveillance system that is not only smart and friendly for users, but allows for transmission of the scene over limited bandwidth networks. The proposed system stores high-quality video data and associated object metadata, which includes ROI (region-of-interest) information. To satisfy bandwidth constraints and display important parts of the images fast and precisely, the stored images are efficiently transcoded in the compressed-domain based on the ROI information. At the receiver, effective display methods such as a mosaic style allow for an intuitive understanding of the important objects in the scene, as well as their movement over time

Video adaptation is an emerging field that offers a rich body of techniques for answering challenging questions in pervasive media applications. It transforms the input video(s) to an output in video or augmented multimedia form by utilizing manipulations at multiple levels (signal, structural, or semantic) in order to meet diverse resource constraints and user preferences while optimizing the overall utility of the video. There has been a vast amount of activity in research and standard development in this area. This paper first presents a general framework that defines the fundamental entities, important concepts (i.e., adaptation, resource, and utility), and formulation of video adaptation as constrained optimization problems. A taxonomy is used to classify different types of adaptation techniques. The state of the art in several active research areas is reviewed with open challenging issues identified. Finally, support of video adaptation from related international standards is discussed.

MPEG-21 Digital Item Adaptation (DIA) has recently been finalized as part of the MPEG-21 Multimedia Framework. DIA specifies metadata for assisting the adaptation of Digital Items according to constraints on the storage, transmission and consumption, thereby enabling various types of quality of service management. This paper provides an overview of DIA, describes its use in multimedia applications, and reports on some of the ongoing activities in MPEG on extending DIA for use in rights governed environments.

We propose an energy efficient JPEG 2000 image transmission system over point-to-point wireless sensor networks. The objective is to minimize the overall processing and transmission energy consumption with the expected end-to-end QoS guarantee, which is achieved by jointly adjusting the source coding schemes, channel coding rates, and transmitter power levels in an optimal way. The advantages of the proposed system lie in three aspects: adaptivity, optimality, and low complexity. Based on the characteristics of the image content, the estimated channel conditions, and the distortion constraint, the proposed low-complexity joint source channel coding and power control algorithm adjusts the coding and transmission strategies adaptively, which can approximate the optimal solution with a tight bound.

This paper examines the properties of a recently introduced 3D dual-tree discrete wavelet transform (DDWT) for video coding. The 3D DDWT is an attractive video representation because it isolates motion along different directions in separate subbands. However, it is an overcomplete transform with 8:1 redundancy. We examine the effectiveness of the iterative projection-based noise shaping scheme proposed by Kingsbury et al., (2002) on reducing the number of coefficients. We also investigate the correlation between subbands at the same spatial/temporal location, both in the significance map and in actual coefficient values.

Increasing bandwidth and diverse devices have led to a proliferation of options for the consumer of digital video. The user can easily be overwhelmed by the diversity of devices, bandwidth and content. In our view, maximizing the end-user experience involves first helping the user to easily search for and retrieve desired content, and then delivering the content to him by seamlessly adapting to his device and available bandwidth. The first part is therefore based on semantic criteria while the second part is based on purely signal-based criteria. We propose that scalable content summarization combined with dynamic content adaptation, and unobtrusive processing of user preferences comprise the key technologies for maximizing the end-user experience.

The work presents a new adaptive approach for blocking and ringing artifact reduction. In order to avoid smearing of the image details, the proposed method first performs visual artifact detection and then applies adaptive filtering to the corrupted blocks. Both visual artifact detection and filtering are guided by an edge map which is constructed based on local features. A fuzzy identity filter is used for image de-ringing. Since it possesses a good edge preserving property and the filtering operation is applied to the edge blocks only (smooth and textured blocks are unaltered), the proposed method shows great effectiveness of both artifact reduction and detail preservation. Experiments demonstrate better results compared with other methods.

Multiple description motion compensation (MDMC) is a multiple description video coding scheme that has shown good error resilience performance. MDMC enables one to vary coding parameters according to the desired trade-off between coding efficiency and error resilience. To fully utilize this advantage, one needs to establish a set of models, relating the rate, encoder distortion, and the end-to-end distortion after transmission, with the encoder parameters and channel parameters. Using these models, one can find the optimal coding parameters for given channel parameters and rate (or distortion) constraints. In this paper, we formulate and validate the rate and encoder distortion models.

This paper presents a new algorithm for MPEG-2 transcoding with spatial resolution reduction. The proposed method combines rate control and mode decision to achieve optimal transcoding performance using Lagrange multiplier algorithm. Since the proposed method incorporates motion vector mapping and mode decision into a single Lagrange multiplier formula, by minimizing the Lagrangian cost function, the optimal solution for mode decision can be obtained. The proposed transcoding scheme has demonstrated better subjective and objective results compared with other methods.

In this paper, we propose a constant quality rate allocation algorithm for MPEG-4 FGS (fine granularity scalability) coded video sequences. The rate allocation problem is formulated as a constrained minimization of quality fluctuation. The minimization is solved using a novel composite rate distortion analysis. For a set of video frames, a composite rate distortion curve is first computed and then used for computing the optimal rate allocation. The proposed algorithm is very efficient because it is neither iterative nor recursive. In addition, after the composite rate distortion curve is computed, it can be used to calculate optimal rate allocation for any rate budget. Therefore, it is suitable for FGS coded bitstreams, which need to be transmitted and decoded many times at many different rates. Moreover, the composite rate distortion curve can be updated efficiently over sliding windows. This further reduces the computational complexity. Experiments using both synthetic and real FGS coded videos have shown the effectiveness and the efficiency of the proposed algorithm.

Multiple description motion compensation (MDMC) is a multiple description video coding scheme that has shown good error resilience performance. MDMC enables one to vary coding parameters according to the desired trade-off between coding efficiency and error resilience. To fully utilize this advantage, one needs to establish a set of models, relating the rate, encoder distortion, and the end-to-end distortion after transmission, with the encoder parameters and channel parameters. Using these models, one can find the optimal coding parameters for given channel parameters and rate (or distortion) constraints. In this paper, we formulate and validate the rate and encoder distortion models.

This paper describes video coding and segmentation techniques that can be used to achieve significant increase in storage capacity. Specifically, we examine the possibility to use object- based coding for efficient long-term archiving of surveillance video. We consider surveillance systems with many camera sources in which we are required to store several months of video data for each source, thus storage capacity is a major concern. The paper considers several automatic segmentation algorithms. With each algorithm, we analyze the shape coding overhead and implication on overall storage requirements, as well as the effect each algorithm has on the reconstructed quality of frames. Additionally, this paper reviews techniques to dynamically control the temporal rate of objects in the scene and perform bit allocation. Experimental results show that up to 90% savings in storage can be achieved with the proposed method compared to frame-based video coding techniques. The cost for this savings is that the accuracy of the background is compromised; however, we feel that this is satisfactory for the application under consideration.

This paper describes rate-control algorithms that consider the tradeoff between coded quality and temporal rate. We target improved coding efficiency for both frame-based and object-based video coding. We propose models that estimate the rate-distortion characteristics for coded frames and objects, as well as skipped frames and objects. Based on the proposed models, we propose three types of rate-control algorithms. The first is for frame-based coding, in which the distortion of coded frames is balanced with the distortion incurred by frame skipping. The second algorithm applies to object-based coding, where the temporal rate of all objects is constrained to be the same, but the bit allocation is performed at the object level. The third algorithm also targets object-based coding, but in contrast to the second algorithm, the temporal rates of each object may vary. The algorithm also takes into account the composition problem, which may cause holes in the reconstructed frame when objects are encoded at different temporal rates. We propose a solution to this problem that is based on first detecting changes in the shape boundaries over time at the encoder, then employing a hole detection and recovery algorithm at the decoder. Overall, the proposed algorithms are able to achieve the target bit rate, effectively code frames and objects with different temporal rates, and maintain a stable buffer level.

This paper proposes an optimal rate-allocation scheme for fine-granular scalability (FGS) coded bitstreams that can achieve constant quality reconstruction of frames under a dynamic rate budget constraint. In doing so, we also aim to minimize the overall distortion at the same time. To achieve this, we propose a novel rate-distortion (R-D) labeling scheme to characterize the R-D relationship of the source coding process. Specifically, sets of R-D points are extracted during the encoding process and linear interpolation is used to estimate the actual R-D curve of the enhancement-layer signal. The extracted R-D information is then used by an enhancement-layer transcoder to determine the bits that should be allocated per frame. A sliding-window-based rate-allocation method is proposed to realize constant quality among frames. This scheme is first considered for a single FGS-coded source, then extended to operate on multiple sources. With the proposed scheme, the rate allocation can be performed in a single pass; hence, the complexity is quite low. Experimental results confirm the effectiveness of the proposed scheme under static and dynamic bandwidth conditions.

The purpose of this paper it to explore the relationship between the rate-distortion characteristics of multiscale binary shape and Markov random field (MRF) parameters. For coding, it is important that the input parameters that will be used to define this relationship be able to distinguish between the same shape at different scales, as well as different shapes at the same scale. We consider an MRF model, referred to as the Chien model, which accounts for high-order spatial interactions among pixels. We propose to use the statistical moments of the Chien model as input to a neural network to accurately predict the rate and distortion of the binary shape when coded at various scales.

The purpose of this paper it to explore the relationship between the rate-distortion (R-D) characteristics of multi scale binary shape and Markov Random Field (MRF) parameters. In our experiments, we consider two prior models. The first MRF model takes into account pair-wise interaction between pels, and for the binary case, is typically referred to as the auto-logistic model; the second MRF model accounts for higher order spatial interactions and is referred to as the Chien model. Experimental results indicate that the auto-logistic model is not sufficient to characterize the R-D characteristics of multi scale binary shape data. However, higher order models, such as the Chien model, do seem feasible. We propose to use the statistical moments of the Chien model as input to a neural network to accurately predict the rate and distortion of the binary shape when coded at various scales.

This paper describes a bit allocation algorithm to achieve a constant bit rate when coding multiple video objects (MVOs), while improving the rate-distortion (R-D) performance over the reference method for MPEG-4 object-based rate control. In object-based coding, bit allocation is performed at the object level and temporal rates of different objects may vary. In this paper, we deal with these two issues. We pay particular attention to maintenance of buffer occupancy levels and propose a new method for spatiotemporal trade-offs for object-based coding. The proposed algorithm is able to successfully achieve the target bit rate, effectively code arbitrarily-shaped MVOs with different temporal rates, and maintain a stable buffer level.

This paper presents two types of techniques suitable for rate-reduction transcoding for wireless video streaming applications. We begin this paper by reviewing existing approaches and addressing several issues related to transcoding. Next, we describe the first type of transcoding based on intra refresh architecture for spatial resolution reduction. Then, we present the second type of transcoding scheme based on rate-distortion (R-D) characteristics of the pre-encoded video. This R-D based approach can be applied to architecture simplification, rate control, frame dropping control, and channel adaptive transcoding. We conclude this paper by pointing out that transcoding is an integral part of wireless video streaming because it provide a flexible interface between the wired network and the wireless network.

This paper discusses the problem of reduced-resolution transcoding of compressed video bitstreams. An analysis of drift errors is provided to identify the sources of quality degradation when transcoding to a lower spatial resolution. Two types of drift error are considered: a reference picture error, which has been identified in previous works, and error due to the noncommutative property of motion compensation and down-sampling, which is unique to this work. To overcome these sources of error, four novel architectures are presented. One architecture attempts to compensate for the reference picture error in the reduced resolution, while another architecture attempts to do the same in the original resolution. We present a third architecture that attempts to eliminate the second type of drift error and a final architecture that relies on an intrablock refresh method to compensate for all types of errors. In all of these architectures, a variety of macroblock level conversions are required, such as motion vector mapping and texture down-sampling. These conversions are discussed in detail. Another important issue for the transcoder is rate control. This is especially important for the intra-refresh architecture since it must find a balance between number of intrablocks used to compensate for errors and the associated rate-distortion characteristics of the low-resolution signal. The complexity and quality of the architectures are compared. Based on the results, we find that the intra-refresh architecture offers the best tradeoff between quality and complexity and is also the most flexible.

Abstract Owing to the heterogeneity existing in wireless video streaming, such as terminal capabilities, network conditions, user preferences, and the natural environment in which a user is located, rate‐reduction transcoding is usually necessary to adjust the coding rate to the available channel bandwidth. We begin this paper by reviewing existing approaches and addressing several issues related to transcoding. Next, two types of rate‐reduction coding techniques are studied. The first type is based on standard coding schemes and specifically considers transcoding from MPEG‐2 to MPEG‐4 with a reduced spatial resolution. A method for drift compensation based on an intrarefresh technique is also presented. The second type of scheme is a rate‐reduction transcoder that makes use of frame‐level R‐D information that has already been extracted at the server before transmission. This R‐D‐based approach can be applied to architecture simplification, rate control, frame dropping control, and channel adaptive transcoding. We conclude this paper by pointing out that transcoding is an integral part of wireless video streaming because it provides a flexible interface between the wired network and the wireless network. Copyright © 2002 John Wiley & Sons, Ltd.

The general problem of optimized video encoding has received a great deal of attention in recent years. This paper focuses on the optimization of video coding with frameskip. We propose models that estimate the distortion for coded frames as well as non-coded frames. Using these models in conjunction with well-know models that estimate the rate allows us to formulate a rate control problem that trades-off spatial and temporal quality. Simulation results indicate moderate improvements for low motion test sequences.

This paper focuses on the problem of estimating the distortion for coded and non-coded frames in a video coder that employs variable frameskip. The distortion for coded frames is given by classic rate-distortion models, however the distortion for non-coded frames has not been considered. Based on the optical flow equation, we formulate a method for estimating the distortion of the non-coded frames.

In this paper, we present a novel system and effective algorithms for soccer video segmentation. The output, about whether the ball is in play, reveals high-level structure of the content. The first step is to classify each sample frame into 3 kinds of view using a unique domain-specific feature, grass-area-ratio. Here the grass value and classification rules are learned and automatically adjusted to each new clip. Then heuristic rules are used in processing the view label sequence, and obtain play/break status of the game. The results provide good basis for detailed content analysis in next step. We also show that lowlevel features and mid-level view classes can be combined to extract more information about the game, via the example of detecting grass orientation in the field. The results are evaluated under different metrics intended for different applications; the best result in segmentation is 86.5%. 1.

This paper introduces a new framework for video content delivery that is based on the transcoding of multiple video objects. Generally speaking, transcoding can be defined as the manipulation or conversion of data into another more desirable format. We consider manipulations of object-based video content, and more specifically, from one set of bit streams to another. Given the object-based framework, we present a set of new algorithms that are responsible for manipulating the original set of video bit streams. Depending on the particular strategy that is adopted, the transcoder attempts to satisfy network conditions or user requirements in various ways. One of the main contributions of this paper is to discuss the degrees of freedom within an object-based transcoder and demonstrate the flexibility that it has in adapting the content. Two approaches are considered: a dynamic programming approach and an approach that is based on available meta-data. Simulations with these two approaches provide insight regarding the bit allocation among objects and illustrates the tradeoffs that can be made in adapting the content. When certain meta-data about the content is available, we show that bit allocation can be significantly improved, key objects can be identified, and varying the temporal resolution of objects can be considered.

In this paper, we focus on the methods for delivering object-based video data. More specifically, me exploit the fact that a finer level of scalability can be achieved when the video frame has been decomposed into objects and coded using MPEG-4. A new framework is proposed.

In this paper, the rate-distortion (R-D) characteristics of binary shapes are modeled. Specifically we are interested in predicting the rate and distortion that is produced by the shape coding techniques that have been adopted into the MPEG-4 standard. The shape coding algorithm is a context-based arithmetic encoder and operates on a per block basis. Currently, there is no efficient way of estimating the rate and distortion at various levels of resolution. Consequently, we propose a model that is based on a set of parameters that can be easily extracted from the binary blocks. The parameters represent states that arise from the possible binary patterns that can occur in a small neighborhood around the current pixel. Symmetry is exploited to keep the number of states to a minimum. It is shown that the proposed model is computationally efficient and provides accurate estimates of the R-D characteristics of a binary shape.

This paper describes an algorithm which can achieve a constant bit rate when coding multiple video objects. The implementation is a nontrivial extension of the MPEG-4 rate control algorithm for single video objects which employs a quadratic rate quantizer model. The algorithm is organized into two stages: a pre- and a post-encoding stage. In the pre-encoding stage, an initial target estimate is made for each object. Based on the buffer fullness, the total target is adjusted and then distributed proportional to the relative size, motion, and variance of each object. Based on the new individual targets and rate-quantizer relation for texture, appropriate quantization parameters are calculated. After each object is encoded, the model parameters for each object are updated, and if necessary, frames are skipped to ensure that the buffer does not overflow. A preframeskip control is exercised to avoid buffer overflow when the motion and shape information occupies a significant portion of the bit budget. The rate control algorithm switches between two operation modes so that the coder can reduce the spatial coding accuracy for an improved temporal resolution. A shape-coding control mechanism is also proposed, which provides a tradeoff between texture and shape coding accuracy. Overall, the algorithm is able to successfully achieve the target bit rate, effectively code arbitrarily shaped objects, and maintain a stable buffer level. These techniques have been adopted by the MPEG committee in July 1997 as part of the video verification model (VM8).

In this paper, we present a video frame-rate up-conversion scheme that uses transmitted true motion vectors for motion-compensated interpolation. In a past work, we demonstrated that a neighborhood-relaxation motion tracker can provide more accurate true motion information than a conventional minimal-residue block-matching algorithm. Although the technique to estimate the true motion vectors is a novelty in its own right, the strength of this technique can be further demonstrated through various spatio-temporal interpolation applications. In this work, we focus on the particular problem of frame-rate up-conversion. In the proposed scheme, the true motion field is derived by the encoder and transmitted by normal means (e.g., MPEG or H.263 encoding). Then, it is recovered by the decoder and is used not only for motion compensated predictions but also used to reconstruct missing data. It is shown that the use of our neighborhood-relaxation motion estimation provides a method of constructing high quality image sequences in a practical manner.

The paper investigates the possible means of down converting an incoming HDTV signal into one which is suitable for display onto an NTSC monitor. We present a novel frequency synthesis algorithm which constructs a set of 8/spl times/8 DCT coefficients from four original 8/spl times/8 DCT blocks. Also, a down-conversion decoder employing a unique adaptive motion compensation algorithm is presented. Using this fixed motion compensation algorithm, the proposed down-conversion technique is compared to the conventional method. Both yield acceptable image sequences with different trade-offs in complexity and quality.

This paper describes an algorithm which achieves a constant bit rate when coding multiple video objects. This implementation is based on the current MPEG-4 video verification model. Each object maintains its own set of parameters. With these parameters an initial target estimate is made for each object. Based on the buffer fullness, the total target is adjusted and then distributed proportional to the size, motion, and variance of each object. Appropriate quantization parameters can be calculated for each video object based on the new individual targets and second order model parameters. This algorithm assures that the target bit rate is achieved for low latency video coding.

For pt.I see ibid., vol.6, no.6, p.636-46 (1996). This paper explores the use of the deformable mesh structure for motion/shape analysis and synthesis in an image sequence. We present algorithms for the analysis problem, including scene-adaptive mesh generation and node tracking over successive frames. We also describe a region-based video coder that integrates the analysis and synthesis algorithms presented. The coder describes each region by an ensemble of connected quadrilateral elements embedded in a mesh structure. For each region, its shape and texture are described by the nodal positions and image functions of the elements in this region in an initial frame, while its motion (including shape deformation) is characterized by the nodal trajectories in the following frames, which are in turn specified by a few motion parameters. This coder has been applied to a typical common intermediate format (CIF) resolution, head-and-shoulder type sequence. The visual quality is significantly better than the H.263-TMN4 algorithm at about 50 kb/s (for the luminance component only, 30 Hz).